need help with Linked list - Programmers Heaven

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

Welcome to the new platform of Programmer's Heaven! We apologize for the inconvenience caused, if you visited us from a broken link of the previous version. The main reason to move to a new platform is to provide more effective and collaborative experience to you all. Please feel free to experience the new platform and use its exciting features. Contact us for any issue that you need to get clarified. We are more than happy to help you.

need help with Linked list

com123com123 Posts: 26Member
i have to 1. Develop a sorted linked list in ascending order.
The node info is (int)
InsertNode( ) operation needs to search for the proper insertion point for the information being added to the list prior to inserting the node into the list.
Hint: you need to use 2 pointers in order to insert node in place (same as deleteNode( ) operation.
Test and verify your ordered linked list. (print output)

i have been tring to get this program to run for the past week.
it works sometimes but the output is wrong.

this is the program that needs to be modified for this assignment
any help will be greatly appreciated.

//LINKED LIST CLASS DECLARATION FILE (list.h)
#ifndef LIST_H
#define LIST_H

#include //FOR cin, cout, AND NULL

//NODE STRUCTURE DECLARATION
struct node
{
char info; //INFORMATION PART OF NODE
node *next; //POINTER TO NEXT NODE
}; //END node

class List
{
public:
List(); //CONSTRUCTOR TO
//IMPLEMENT createList()
~List(); //DESTRUCTOR TO DEALLOCATE LIST MEMORY
void insertNode(char c); //FUNCTION TO INSERT A NODE
void deleteNode(char c); //FUNCTION TO DELETE A
//SPECIFIED NODE
void traverseList(); //FUNCTION TO TRAVERSE LIST
bool emptyList(); //FUNCTION TO TEST FOR
//EMPTY LIST
private:
node *first; //DEFINE first AS A POINTER TO NODE STRUCT
}; //END List
#endif




Link.cpp

//LINKED LIST IMPLEMENTATION FILE (listop.cpp)

#include "list.h" //FOR list CLASS
#include //FOR cin AND cout

//IMPLEMENTATION OF CONSTRUCTOR List()
List :: List()
{
first = NULL;
} //END List()

//IMPLEMENTATION OF DESTRUCTOR, ~List()
List :: ~List()
{
node *p; //DEFINE p AS A POINTER TO
//THE NODE STRUCT
node *temp; //DEFINE temp AS POINTER TO
//THE NODE STRUCT
p = first; //SET p = first
while (p!= NULL) //TRAVERSE LIST UNTIL p = NULL
{
temp = p -> next; //MAKE temp POINT TO NEXT NODE IN LIST
delete p; //DEALLOCATE node(p)
p = temp; //MAKE p POINT TO NEXT NODE
} //END WHILE
} //END ~List()

//IMPLEMENTATION OF insertNode()
void List :: insertNode(char c)
{
node *p; //DEFINE p AS A POINTER TO
//THE NODE STRUCT
p = new node; //ALLOCATE MEMORY FOR node(p)
p -> info = c; //PLACE CHAR IN info(p)
p -> next = first; //INSERT node(p) AT BEGINNING
first = p; //MOVE first TO node(p)
} //END insertNode()

//IMPLEMENTATION OF deleteNode()
void List :: deleteNode(char c)
{
bool found = false; //INITIALIZE found TO FALSE
node *p; //DEFINE p AS A POINTER TO NODE STRUCT
node *predP; //DEFINE predP AS A POINTER TO NODE STRUCT
p = first; //START p AT first NODE
predP = NULL; //START predP AT NULL

//IF LIST EMPTY, WRITE EMPTY MESSAGE. ELSE
//SEARCH FOR ELEMENT TO BE DELETED
if (emptyList())
cout << "
You cannot delete a node from an empty list!" << endl;
else
{
while (!found && p != NULL) //TRAVERSE LIST UNTIL FOUND //OR p == NULL
{
if (p -> info == c) //TEST info(p)
found = true;
else //ADVANCE POINTERS
{
predP = p; //CATCH predP UP TO p
p = p-> next; //ADVANCE p
} //END ADVANCE ELSE
} //END SEARCH LOOP

//DELETE NODE IF FOUND. ELSE WRITE NOT FOUND MESSAGE
if (found)
{
//DOES node(p) HAVE A PREDECESSOR?
//IF NOT, DELETE first NODE. ELSE DELETE node(p)
if (predP == NULL)
{
first = p -> next; //MOVE first TO SECOND NODE
delete p; //DEALLOCATE node(p)
} //END DELETE first NODE
else
{
predP -> next = p -> next; //MAKE NEXT(predP) JUMP
//AROUND node(p)
delete p; //DEALLOCATE node(p)
} //END DELETE node(p)
} //END IF FOUND
else //WRITE NOT FOUND MESSAGE
cout << "
The character '" << c << "' is not in the list!" << endl;
} //END SEARCH ELSE
} //END deleteNode()

//IMPLEMENTATION OF traverseList()
void List :: traverseList()
{
node *p; //DEFINE p AS A POINTER TO NODE STRUCT
p = first; //START p AT first NODE

//IF LIST IS NOT EMPTY, TRAVERSE LIST
//AND WRITE info(p). ELSE WRITE LIST EMPTY MESSAGE
if (!emptyList())
{
while (p != NULL) //TRAVERSE LIST UNTIL p = NULL
{
cout << p -> info << " -> "; //WRITE info(p)
p = p -> next; //ADVANCE p
} //END WHILE
cout << "NULL " << endl; //WRITE "NULL"
} //END IF NOT EMPTY
else //WRITE EMPTY LIST MESSAGE
cout << "
The list is empty!" << endl;
} //END traverseList()

//IMPLEMENTATION OF emptyList()
bool List :: emptyList()
{
if (first == NULL)
return true;
else
return false;
} //END emptyList()



//LinkMain

//PREPROCESSOR DIRECTIVES
#include "list.h" //FOR list CLASS
#include <iostream.h> //FOR cin AND cout

//MAIN FUNCTION
int main()
{
char c; //CHARACTER TO BE INSERTED INTO LIST

List l; //DEFINE LIST OBJECT

cout << "Enter 0 when finished" << endl;

while (c != '0')
{
cout << "
Enter a character element: ";
cin >> c;
if(c != '0')
{
l.insertNode(c);
}
} //END WHILE

//TRAVERSE AND WRITE LIST ELEMENTS
cout << "

The contents of the list are: ";
l.traverseList();

//DELETE A SPECIFIED CHARACTER FROM THE LIST
cout << "
Which character element do you want to delete? ";
cin >> c;
l.deleteNode(c);

//TRAVERSE AND WRITE LIST ELEMENTS
cout << "
The contents of the list are: ";
l.traverseList();

//RETURN
return 0;
} //END main()


Sign In or Register to comment.