C++ RSS C++ RSS

Linked list problem

Please support our C++ advertiser: Intel Parallel Studio Home
Reply

•
•
Join Date: Jul 2007
Posts: 30
Reputation: Reg74 is an unknown quantity at this point 
Solved Threads: 1
Reg74 Reg74 is offline Offline
Light Poster

Linked list problem

 
0
  #1
Feb 25th, 2009
C++ Syntax (Toggle Plain Text) 
  1. //Pg.288
  2. #include <cassert>
  3. #include <iostream>
  4. using namespace std;
  5.  
  6. void deleteKthElement(int k, int& count);
  7.  
  8. int main()
  9. {
  10.  
  11. struct nodeType {
  12.   int info;
  13.   nodeType *link;  
  14. };
  15.  
  16.  
  17.   nodeType *first, *newNode, *last, *traverse;  
  18.   int num;
  19.   int count = 0;
  20.  
  21.   cout << "Enter a list of integers ending with -999.\n";
  22.   cin  >> num;
  23.   first = NULL;
  24.  
  25.   while (num != -999)
  26.   {
  27.     newNode = new nodeType;
  28.     assert(newNode !=NULL);
  29.  
  30.     newNode ->info = num;
  31.     newNode ->link = NULL;
  32.  
  33.     if(first == NULL)
  34.     {
  35.       first = newNode;
  36.       last = newNode;
  37.     }
  38.     else
  39.     {
  40.       last -> link = newNode;
  41.       last = newNode;
  42.     }
  43.     cin >> num;
  44.     count++;    //increment the counter to keep track of no. of elements
  45.   } // end while  
  46.  
  47.   //print the linked list prior to deleting the 5th element
  48.   cout << "The linked list before:" << endl;
  49.   traverse = new nodeType;
  50.   assert(traverse != NULL);
  51.   traverse = first;
  52.  
  53.   while (traverse != NULL)
  54.   {
  55.     cout << traverse->info << endl;
  56.     traverse = traverse->link;
  57.   } 
  58.  
  59.   deleteKthElement(5,count);
  60.  
  61.   //print the linked list after deleting the 5th element !!
  62.   cout << "The linked list after deleting the 5th element:" << endl;
  63.   traverse = new nodeType;
  64.   assert(traverse != NULL);
  65.   traverse = first;
  66.  
  67.   while (traverse != NULL)
  68.   {
  69.     cout << traverse->info << endl;
  70.     traverse = traverse->link;
  71.   } 
  72.  
  73. }  // end main
  74.  
  75. void deleteKthElement(int k, int& count)
  76. {
  77.   assert(k <= count);  
  78.   nodeType *current, *trailCurrent;
  79.   int i;
  80.  
  81.   if (first ==NULL)
  82.     cerr << "Cannot delete from an empty list!" << endl;
  83.   else
  84.      if (k == 1)
  85.      {
  86.        current = first;
  87.        first = first->link;
  88.  
  89.        if (first == NULL)
  90.           last = NULL;
  91.  
  92.        delete current;
  93.      }
  94.      else
  95.      {
  96.          trailCurrent = first;
  97.          current = first->link;
  98.  
  99.           i = 2;
  100.           while(i < k)
  101.           {
  102.             trailCurrent = current;
  103.             current = current->link;
  104.             i++;
  105.           }
  106.  
  107.           trailCurrent->link = current->link;
  108.           if (current == last)
  109.             last = trailCurrent;
  110.       }       
  111. }

I'm struggling to get the 5th element deleted in the list
Compiler giving me a lot of errors ; eg. nodeType undeclared, etc.
Please help ?
Reply With Quote Quick reply to this message  
•
•
Join Date: Aug 2008
Posts: 83
Reputation: nmaillet is an unknown quantity at this point 
Solved Threads: 18
nmaillet nmaillet is offline Offline
Junior Poster in Training

Re: Linked list problem

 
0
  #2
Feb 25th, 2009
The nodeType struct should be declared outside the main function.
Reply With Quote Quick reply to this message  
•
•
Join Date: Jul 2007
Posts: 30
Reputation: Reg74 is an unknown quantity at this point 
Solved Threads: 1
Reg74 Reg74 is offline Offline
Light Poster

Re: Linked list problem

 
0
  #3
Feb 26th, 2009
I did what you said and i'm still experiencing some problems.Could you please paste the code into your compiler and run it ?
Thanks once again for your previous reply !
Reply With Quote Quick reply to this message  
•
•
Join Date: Jul 2007
Posts: 30
Reputation: Reg74 is an unknown quantity at this point 
Solved Threads: 1
Reg74 Reg74 is offline Offline
Light Poster

Re: Linked list problem

 
0
  #4
Feb 26th, 2009
Thanks ... i seem to have found help .
Here's the adapted code
c++ Syntax (Toggle Plain Text) 
  1. //Pg.288
  2. #include <cassert>
  3. #include <iostream>
  4. using namespace std;
  5.  
  6. struct nodeType 
  7. {
  8.   int info;
  9.   nodeType *link;  
  10. };
  11.  
  12. void deleteKthElement(nodeType *firstElement, int k, const int& count);
  13.  
  14. int main()
  15. {
  16.   nodeType *first, *newNode, *last, *traverse;  
  17.   int num;
  18.   int count = 0;
  19.  
  20.   cout << "Enter a list of integers ending with -999.\n";
  21.   cin  >> num;
  22.   first = NULL;
  23.  
  24.   while (num != -999)
  25.   {
  26.     newNode = new nodeType;
  27.     assert(newNode !=NULL);
  28.  
  29.     newNode ->info = num;
  30.     newNode ->link = NULL;
  31.  
  32.     if(first == NULL)
  33.     {
  34.       first = newNode;
  35.       last = newNode;
  36.     }
  37.     else
  38.     {
  39.       last -> link = newNode;
  40.       last = newNode;
  41.     }
  42.     cin >> num;
  43.     count++;    //increment the counter to keep track of no. of elements    
  44.   } // end while  
  45.  
  46.   //print the linked list prior to deleting the 3rd element
  47.   cout << "The linked list before:" << endl;
  48.   //traverse = new nodeType;
  49.   //assert(traverse != NULL);
  50.   traverse = first;
  51.  
  52.   while (traverse != NULL)
  53.   {
  54.     cout << traverse->info << endl;
  55.     traverse = traverse->link;
  56.   } 
  57.  
  58.  
  59.   deleteKthElement(first->link,2,count);
  60.  
  61.   //print the linked list after deleting the 3rd element 
  62.   cout << "The linked list after deleting the 3rd element:" << endl;
  63.   //traverse = new nodeType;
  64.   //assert(traverse != NULL);
  65.   traverse = first;
  66.  
  67.   while (traverse != NULL)
  68.   {
  69.     cout << traverse->info << endl;
  70.     traverse = traverse->link;
  71.   } 
  72. }  // end main
  73.  
  74.  
  75. void deleteKthElement( nodeType *firstElement,int k, const int& count)
  76. {
  77.   assert(k <= count);  
  78.   nodeType *first ,*last, *current, *trailCurrent;
  79.   int i;
  80.  
  81.   first = firstElement;
  82.  
  83.   if (firstElement == NULL)
  84.     cerr << "Cannot delete from an empty list!" << endl;
  85.   else
  86.      if (k == 1)
  87.      {
  88.        current = firstElement;
  89.        firstElement = firstElement->link;
  90.  
  91.        if (firstElement == NULL)
  92.           last = NULL;
  93.  
  94.        delete current;
  95.      }
  96.      else
  97.      {
  98.          trailCurrent = firstElement;
  99.          current = firstElement->link;
  100.  
  101.           i = 2;
  102.           while(i < k)
  103.           {
  104.             trailCurrent = current;
  105.             current = current->link;
  106.             i++;
  107.           }
  108.  
  109.           trailCurrent->link = current->link;
  110.           if (current == last)
  111.             last = trailCurrent;
  112.       }       
  113. }  //end deleteKthElement
Last edited by Reg74; Feb 26th, 2009 at 8:37 am. Reason: my message not stated clearly
Reply With Quote Quick reply to this message  
•
•
Join Date: Jul 2007
Posts: 30
Reputation: Reg74 is an unknown quantity at this point 
Solved Threads: 1
Reg74 Reg74 is offline Offline
Light Poster

Re: Linked list problem

 
0
  #5
Feb 26th, 2009
c++ Syntax (Toggle Plain Text) 
  1. //Pg.288
  2. #include <cassert>
  3. #include <iostream>
  4. using namespace std;
  5.  
  6. struct nodeType 
  7. {
  8.   int info;
  9.   nodeType *link;  
  10. };
  11.  
  12. void deleteKthElement(nodeType *firstElement, int k, const int& count);
  13.  
  14. int main()
  15. {
  16.   nodeType *first, *newNode, *last, *traverse;  
  17.   int num;
  18.   int count = 1;
  19.  
  20.   cout << "Enter a list of integers ending with -999.\n";
  21.   cin  >> num;
  22.   first = NULL;
  23.  
  24.   while (num != -999)
  25.   {
  26.     newNode = new nodeType;
  27.     assert(newNode !=NULL);
  28.  
  29.     newNode ->info = num;
  30.     newNode ->link = NULL;
  31.  
  32.     if(first == NULL)
  33.     {
  34.       first = newNode;
  35.       last = newNode;
  36.     }
  37.     else
  38.     {
  39.       last -> link = newNode;
  40.       last = newNode;
  41.     }
  42.     cin >> num;
  43.     count++;    //increment the counter to keep track of no. of elements    
  44.   } // end while  
  45.  
  46.   //print the linked list prior to deleting the 3rd element
  47.   cout << "The linked list before:" << endl;
  48.   //traverse = new nodeType;
  49.   //assert(traverse != NULL);
  50.   traverse = first;
  51.  
  52.   while (traverse != NULL)
  53.   {
  54.     cout << traverse->info << endl;
  55.     traverse = traverse->link;
  56.   } 
  57.  
  58.  
  59.   deleteKthElement(first,2,count);
  60.  
  61.   //print the linked list after deleting the 2nd element 
  62.   cout << "The linked list after deleting the 2nd element:" << endl;
  63.   //traverse = new nodeType;
  64.   //assert(traverse != NULL);
  65.   traverse = first;
  66.  
  67.   while (traverse != NULL)
  68.   {
  69.     cout << traverse->info << endl;
  70.     traverse = traverse->link;
  71.   } 
  72. }  // end main
  73.  
  74.  
  75. void deleteKthElement( nodeType *firstElement,int k, const int& count)
  76. {
  77.   assert(k <= count);  
  78.   nodeType *first ,*last, *current, *trailCurrent;
  79.   int i = 1;
  80.  
  81.  // first = firstElement;
  82.  
  83.   if (firstElement == NULL)
  84.     cerr << "Cannot delete from an empty list!" << endl;
  85.   else
  86.      if (k == 1)
  87.      {
  88.        current = firstElement;
  89.        firstElement = firstElement->link;
  90.  
  91.        if (firstElement == NULL)
  92.           last = NULL;
  93.  
  94.        delete current;
  95.      }
  96.      else
  97.      {
  98.          trailCurrent = firstElement;
  99.          current = firstElement->link;
  100.  
  101.           i = 2;
  102.           while(i < k)
  103.           {
  104.             trailCurrent = current;
  105.             current = current->link;
  106.             i++;
  107.           }
  108.  
  109.           trailCurrent->link = current->link;
  110.           if (current == last)
  111.             last = trailCurrent;
  112.       }       
  113. }  //end deleteKthElement
Reply With Quote Quick reply to this message  
•
•
Join Date: Jul 2007
Posts: 30
Reputation: Reg74 is an unknown quantity at this point 
Solved Threads: 1
Reg74 Reg74 is offline Offline
Light Poster

Re: Linked list problem

 
0
  #6
Mar 3rd, 2009
I thought i had this problem solved but i've just one last issue:
Why is the program displaying a zero (0) after deleting the node with the smallest info ??
Note: The program seems to work fine if the node with the smallest info is not the first node in the linked list. Why is this ?
(Please refer to my attachments for the code as well as the input and output of the program)
Attached Files
File Type: doc LinkList.doc (42.0 KB, 1 views)
File Type: doc Input_output.doc (23.5 KB, 0 views)
Reply With Quote Quick reply to this message  
•
•
Join Date: Jul 2007
Posts: 30
Reputation: Reg74 is an unknown quantity at this point 
Solved Threads: 1
Reg74 Reg74 is offline Offline
Light Poster

Re: Linked list problem

 
0
  #7
Mar 3rd, 2009
•
•
•
•
Originally Posted by Reg74 View Post
I thought i had this problem solved but i've just one last issue:
Why is the program displaying a zero (0) after deleting the node with the smallest info ??
Note: The program seems to work fine if the node with the smallest info is not the first node in the linked list. Why is this ?
(Please refer to my attachments for the code as well as the input and output of the program)
cpp Syntax (Toggle Plain Text) 
  1. #include <cassert>
  2. #include <iostream>
  3. using namespace std;
  4.  
  5. struct nodeType 
  6. {
  7.   int info;
  8.   nodeType *link;  
  9. };
  10.  
  11. void deleteKthElement(nodeType *firstElement, int k, const int& count);
  12. void deletesmallestInfoNode(nodeType *firstType);
  13. void deleteNode(nodeType *firstNode, const int& deleteItem);
  14. void deletegivenInfoNode(nodeType *fNode, const int& deleteInfo);
  15.  
  16. /* ------------------------------------------------------------------------ */
  17.  
  18. int main()
  19. {
  20.   nodeType *first, *newNode, *last, *traverse;  
  21.   int num;
  22.   int count = 0;
  23.  
  24.   cout << "Enter a list of integers ending with -999.\n";
  25.   cin  >> num;
  26.   first = NULL;
  27.  
  28.   while (num != -999)
  29.   {
  30.     newNode = new nodeType;
  31.     assert(newNode !=NULL);
  32.  
  33.     newNode ->info = num;
  34.     newNode ->link = NULL;
  35.  
  36.     if(first == NULL)
  37.     {
  38.       first = newNode;
  39.       last = newNode;
  40.     }
  41.     else
  42.     {
  43.       last -> link = newNode;
  44.       last = newNode;
  45.     }
  46.     cin >> num;
  47.     count++;    //increment the counter to keep track of no. of elements    
  48.   } // end while  
  49.  
  50.   //print the linked list prior to deleting the 2nd element
  51.   cout << "The linked list before:" << endl;
  52.   traverse = first;  
  53.   while (traverse != NULL)
  54.   {
  55.     cout << traverse->info << endl;
  56.     traverse = traverse->link;
  57.   } 
  58.  
  59.  
  60.   deleteKthElement(first,2,count);
  61.  
  62.   //print the linked list after deleting the 2nd element 
  63.   cout << "The linked list after deleting the 2nd element:" << endl;
  64.   traverse = first;  
  65.   while (traverse != NULL)
  66.   {
  67.     cout << traverse->info << endl;
  68.     traverse = traverse->link;
  69.   } 
  70.  
  71.   deletesmallestInfoNode(first);
  72.  
  73.   //print the linked list after deleting the node with the smallest info
  74.   cout << "The linked list after deleting the node with the smallest info:" << endl;
  75.   traverse = first;  
  76.   while (traverse != NULL)
  77.   {
  78.     cout << traverse->info << endl;
  79.     traverse = traverse->link;
  80.   } 
  81.  
  82.    deletegivenInfoNode(first,15);
  83.  
  84.   //print the linked list after removing all occurences of 15 in the list 
  85.   cout << "The linked list after deleting all occurences of 15 in the list:" << endl;
  86.   traverse = first;  
  87.   while (traverse != NULL)
  88.   {
  89.     cout << traverse->info << endl;
  90.     traverse = traverse->link;
  91.   }  
  92. }  // end main
  93.  
  94. /* ------------------------------------------------------------------------ */
  95.  
  96. void deleteKthElement( nodeType *firstElement,int k, const int& count)
  97. {
  98.   assert(k <= count);  
  99.   nodeType *first ,*last, *current, *trailCurrent;
  100.   int i = 1;
  101.  
  102.  // first = firstElement;
  103.  
  104.   if (firstElement == NULL)
  105.     cerr << "Cannot delete from an empty list!" << endl;
  106.   else
  107.      if (k == 1)
  108.      {
  109.        current = firstElement;
  110.        firstElement = firstElement->link;
  111.  
  112.        if (firstElement == NULL)
  113.           last = NULL;
  114.  
  115.        delete current;
  116.      }
  117.      else
  118.      {
  119.          trailCurrent = firstElement;
  120.          current = firstElement->link;
  121.  
  122.           i = 2;
  123.           while(i < k)
  124.           {
  125.             trailCurrent = current;
  126.             current = current->link;
  127.             i++;
  128.           }
  129.  
  130.           trailCurrent->link = current->link;
  131.           if (current == last)
  132.             last = trailCurrent;
  133.       }       
  134. }  //end deleteKthElement
  135.  
  136.  
  137. void deletesmallestInfoNode(nodeType *firstType)
  138. {   
  139.     nodeType *first;
  140.     first = firstType;
  141.     if (first == NULL)               // the list has only one node
  142. 	cerr << "Cannot delete from an empty list!" << endl;		
  143.     else
  144.     {
  145.        nodeType* newNode;
  146.        bool found = false;              
  147.        newNode = first;         // newNode points to the first node
  148.  
  149.        while (newNode != NULL && !found)
  150.         {
  151.         if (newNode->link == NULL) //only 1 node in list or the last 
  152. 	    {
  153. 	    	 deleteNode(first,newNode->info); //call function to delete node
  154. 			 found = true;			//smallest info found !
  155. 	    }
  156. 	    else if (newNode->info <= newNode->link->info)
  157.            {
  158.             deleteNode(first,newNode->info); //call function to delete node
  159.             found = true;                  //smallest info found !
  160.            }
  161.            else
  162.              newNode = newNode->link; //advance newNode 
  163.         }  // end while   
  164.     } // endif
  165. }//end deletesmallestInfoNode
  166.  
  167.  
  168. void deleteNode(nodeType *firstNode ,const int& deleteItem)
  169. {
  170.     nodeType *first, *last;
  171. 	nodeType *current; //pointer to traverse the list
  172. 	nodeType *trailCurrent; //pointer just before current
  173. 	bool found;
  174.  
  175. 	first = firstNode;
  176.  
  177. 	if(first == NULL)    //Case 1; list is empty. 
  178. 		cerr<<"Cannot delete from an empty list.\n";
  179. 	else
  180. 	{
  181. 		if(first->info == deleteItem) //Case 2 
  182. 		{
  183. 			current = first;
  184. 			first = first->link;			
  185. 			if(first == NULL)    //list only had 1 node			
  186.              	last = NULL;
  187.      			delete current;	   
  188. 		}
  189. 		else  //search the list for the node with the given info
  190. 		{
  191. 			found = false;
  192. 			trailCurrent = first;   //set trailCurrent to point to
  193.                                  //the first node
  194. 			current = first->link;  //set current to point to the 
  195.     			   //second node
  196.  
  197. 			while(current != NULL && !found)
  198. 			{
  199.   				if(current->info != deleteItem) 
  200. 				{
  201. 					trailCurrent = current;
  202. 					current = current->link;
  203. 				}
  204. 				else
  205. 					found = true;
  206. 			} // end while
  207.  
  208. 			if(found) //Case 3; if found, delete the node
  209. 			{
  210. 				trailCurrent->link = current->link;
  211. 				//count--;
  212.  
  213. 				if(last == current)      //node to be deleted was 
  214.                                      //the last node
  215. 					last = trailCurrent;  //update the value of last
  216.  
  217. 				delete current;  //delete the node from the list
  218. 			}
  219. 			else
  220. 				cout<<"Item to be deleted is not in the list."<<endl;
  221. 		} //end else
  222. 	} //end else
  223. } //end deleteNode
  224.  
  225.  
  226.  
  227. //function to delete all occurences of a given info in the list
  228. void deletegivenInfoNode(nodeType *fNode, const int& deleteInfo)
  229. { 
  230.    nodeType *first;
  231.    first = fNode; 
  232.    bool found = false;
  233.    if (first == NULL)               // the list has only one node
  234. 	cerr << "Cannot delete from an empty list!" << endl;		
  235.     else
  236.     {
  237.        nodeType *traversePtr;         //pointer to traverse the list
  238.        traversePtr = first;         // traversePtr points to the first node
  239.        while (traversePtr != NULL)
  240.        { 	
  241.          if (traversePtr->info == deleteInfo)
  242.          {
  243.             deleteNode(first,deleteInfo);
  244.      		found = true; 
  245.    		 }
  246.          else
  247.              traversePtr = traversePtr->link; 		//advance traversePtr
  248.        }   // end while
  249.      }  // end if
  250.  
  251.       if (!(found))
  252. 	     cout << "Item to be deleted is not in the list!" << endl; 		
  253.  }  // end deletegivenInfoNode
Reply With Quote Quick reply to this message  
Reply

Quick Reply to Thread
This thread is more than three months old.
Perhaps start a new thread instead?
•
•
•
•
•
•
•
•
Message:
•
•
•
•



Similar Threads
Other Threads in the C++ Forum
Thread Tools Search this Thread



api array arrays based binary c++ c/c++ calculator char char* class classes code coding compile compiler console conversion convert count database delete deploy desktop developer directshow dll download dynamic dynamiccharacterarray email encryption error file forms fstream function functions game generator givemetehcodez google graph gui homeworkhelp iamthwee ifstream input int java lib linkedlist linker list loop looping loops map math matrix memory multiple news number numbertoword output pointer problem program programming project python random read recursion recursive reference rpg sorting string strings temperature template templates test text text-file tree unix url variable vector video visual visualstudio win32 windows winsock wordfrequency wxwidgets
About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC