Linked list problem

Question

Reg74 0 Light Poster

15 Years Ago

//Pg.288
#include <cassert>
#include <iostream>
using namespace std;

void deleteKthElement(int k, int& count);

int main()
{

struct nodeType {
  int info;
  nodeType *link;  
};


  nodeType *first, *newNode, *last, *traverse;  
  int num;
  int count = 0;

  cout << "Enter a list of integers ending with -999.\n";
  cin  >> num;
  first = NULL;

  while (num != -999)
  {
    newNode = new nodeType;
    assert(newNode !=NULL);

    newNode ->info = num;
    newNode ->link = NULL;

    if(first == NULL)
    {
      first = newNode;
      last = newNode;
    }
    else
    {
      last -> link = newNode;
      last = newNode;
    }
    cin >> num;
    count++;    //increment the counter to keep track of no. of elements
  } // end while  
  
  //print the linked list prior to deleting the 5th element
  cout << "The linked list before:" << endl;
  traverse = new nodeType;
  assert(traverse != NULL);
  traverse = first;
  
  while (traverse != NULL)
  {
    cout << traverse->info << endl;
    traverse = traverse->link;
  } 
  
  deleteKthElement(5,count);
 
  //print the linked list after deleting the 5th element !!
  cout << "The linked list after deleting the 5th element:" << endl;
  traverse = new nodeType;
  assert(traverse != NULL);
  traverse = first;
  
  while (traverse != NULL)
  {
    cout << traverse->info << endl;
    traverse = traverse->link;
  } 
  
}  // end main

void deleteKthElement(int k, int& count)
{
  assert(k <= count);  
  nodeType *current, *trailCurrent;
  int i;
  
  if (first ==NULL)
    cerr << "Cannot delete from an empty list!" << endl;
  else
     if (k == 1)
     {
       current = first;
       first = first->link;
       
       if (first == NULL)
          last = NULL;
       
       delete current;
     }
     else
     {
         trailCurrent = first;
         current = first->link;
         
          i = 2;
          while(i < k)
          {
            trailCurrent = current;
            current = current->link;
            i++;
          }
          
          trailCurrent->link = current->link;
          if (current == last)
            last = trailCurrent;
      }       
}

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 ?

c++

2 Contributors
6 Replies
122 Views
6 Days Discussion Span
Latest Post 15 Years Ago Latest Post by Reg74

nmaillet 97 Posting Whiz in Training

15 Years Ago

The nodeType struct should be declared outside the main function.

Reply to this topic

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

Reg74 0 Light Poster · Answer 1 · 2009-02-26T12:34:29+00:00

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 !

Reg74 0 Light Poster · Answer 2 · 2009-02-26T18:35:00+00:00

Thanks ... i seem to have found help .
Here's the adapted code

//Pg.288
#include <cassert>
#include <iostream>
using namespace std;

struct nodeType 
{
  int info;
  nodeType *link;  
};

void deleteKthElement(nodeType *firstElement, int k, const int& count);

int main()
{
  nodeType *first, *newNode, *last, *traverse;  
  int num;
  int count = 0;

  cout << "Enter a list of integers ending with -999.\n";
  cin  >> num;
  first = NULL;

  while (num != -999)
  {
    newNode = new nodeType;
    assert(newNode !=NULL);

    newNode ->info = num;
    newNode ->link = NULL;

    if(first == NULL)
    {
      first = newNode;
      last = newNode;
    }
    else
    {
      last -> link = newNode;
      last = newNode;
    }
    cin >> num;
    count++;    //increment the counter to keep track of no. of elements    
  } // end while  
  
  //print the linked list prior to deleting the 3rd element
  cout << "The linked list before:" << endl;
  //traverse = new nodeType;
  //assert(traverse != NULL);
  traverse = first;
  
  while (traverse != NULL)
  {
    cout << traverse->info << endl;
    traverse = traverse->link;
  } 
  
  
  deleteKthElement(first->link,2,count);
 
  //print the linked list after deleting the 3rd element 
  cout << "The linked list after deleting the 3rd element:" << endl;
  //traverse = new nodeType;
  //assert(traverse != NULL);
  traverse = first;
  
  while (traverse != NULL)
  {
    cout << traverse->info << endl;
    traverse = traverse->link;
  } 
}  // end main


void deleteKthElement( nodeType *firstElement,int k, const int& count)
{
  assert(k <= count);  
  nodeType *first ,*last, *current, *trailCurrent;
  int i;
  
  first = firstElement;
  
  if (firstElement == NULL)
    cerr << "Cannot delete from an empty list!" << endl;
  else
     if (k == 1)
     {
       current = firstElement;
       firstElement = firstElement->link;
       
       if (firstElement == NULL)
          last = NULL;
       
       delete current;
     }
     else
     {
         trailCurrent = firstElement;
         current = firstElement->link;
         
          i = 2;
          while(i < k)
          {
            trailCurrent = current;
            current = current->link;
            i++;
          }
          
          trailCurrent->link = current->link;
          if (current == last)
            last = trailCurrent;
      }       
}  //end deleteKthElement

Reg74 0 Light Poster · Answer 3 · 2009-02-26T20:17:12+00:00

//Pg.288
#include <cassert>
#include <iostream>
using namespace std;

struct nodeType 
{
  int info;
  nodeType *link;  
};

void deleteKthElement(nodeType *firstElement, int k, const int& count);

int main()
{
  nodeType *first, *newNode, *last, *traverse;  
  int num;
  int count = 1;

  cout << "Enter a list of integers ending with -999.\n";
  cin  >> num;
  first = NULL;

  while (num != -999)
  {
    newNode = new nodeType;
    assert(newNode !=NULL);

    newNode ->info = num;
    newNode ->link = NULL;

    if(first == NULL)
    {
      first = newNode;
      last = newNode;
    }
    else
    {
      last -> link = newNode;
      last = newNode;
    }
    cin >> num;
    count++;    //increment the counter to keep track of no. of elements    
  } // end while  
  
  //print the linked list prior to deleting the 3rd element
  cout << "The linked list before:" << endl;
  //traverse = new nodeType;
  //assert(traverse != NULL);
  traverse = first;
  
  while (traverse != NULL)
  {
    cout << traverse->info << endl;
    traverse = traverse->link;
  } 
  
  
  deleteKthElement(first,2,count);
 
  //print the linked list after deleting the 2nd element 
  cout << "The linked list after deleting the 2nd element:" << endl;
  //traverse = new nodeType;
  //assert(traverse != NULL);
  traverse = first;
  
  while (traverse != NULL)
  {
    cout << traverse->info << endl;
    traverse = traverse->link;
  } 
}  // end main


void deleteKthElement( nodeType *firstElement,int k, const int& count)
{
  assert(k <= count);  
  nodeType *first ,*last, *current, *trailCurrent;
  int i = 1;
  
 // first = firstElement;
  
  if (firstElement == NULL)
    cerr << "Cannot delete from an empty list!" << endl;
  else
     if (k == 1)
     {
       current = firstElement;
       firstElement = firstElement->link;
       
       if (firstElement == NULL)
          last = NULL;
       
       delete current;
     }
     else
     {
         trailCurrent = firstElement;
         current = firstElement->link;
         
          i = 2;
          while(i < k)
          {
            trailCurrent = current;
            current = current->link;
            i++;
          }
          
          trailCurrent->link = current->link;
          if (current == last)
            last = trailCurrent;
      }       
}  //end deleteKthElement

Reg74 0 Light Poster · Answer 4 · 2009-03-03T14:11:32+00:00

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)

Reg74 0 Light Poster · Answer 5 · 2009-03-03T15:19:49+00:00

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)

#include <cassert>
#include <iostream>
using namespace std;

struct nodeType 
{
  int info;
  nodeType *link;  
};

void deleteKthElement(nodeType *firstElement, int k, const int& count);
void deletesmallestInfoNode(nodeType *firstType);
void deleteNode(nodeType *firstNode, const int& deleteItem);
void deletegivenInfoNode(nodeType *fNode, const int& deleteInfo);

/* ------------------------------------------------------------------------ */

int main()
{
  nodeType *first, *newNode, *last, *traverse;  
  int num;
  int count = 0;

  cout << "Enter a list of integers ending with -999.\n";
  cin  >> num;
  first = NULL;

  while (num != -999)
  {
    newNode = new nodeType;
    assert(newNode !=NULL);

    newNode ->info = num;
    newNode ->link = NULL;

    if(first == NULL)
    {
      first = newNode;
      last = newNode;
    }
    else
    {
      last -> link = newNode;
      last = newNode;
    }
    cin >> num;
    count++;    //increment the counter to keep track of no. of elements    
  } // end while  
  
  //print the linked list prior to deleting the 2nd element
  cout << "The linked list before:" << endl;
  traverse = first;  
  while (traverse != NULL)
  {
    cout << traverse->info << endl;
    traverse = traverse->link;
  } 
  
  
  deleteKthElement(first,2,count);
 
  //print the linked list after deleting the 2nd element 
  cout << "The linked list after deleting the 2nd element:" << endl;
  traverse = first;  
  while (traverse != NULL)
  {
    cout << traverse->info << endl;
    traverse = traverse->link;
  } 
  
  deletesmallestInfoNode(first);
  
  //print the linked list after deleting the node with the smallest info
  cout << "The linked list after deleting the node with the smallest info:" << endl;
  traverse = first;  
  while (traverse != NULL)
  {
    cout << traverse->info << endl;
    traverse = traverse->link;
  } 
  
   deletegivenInfoNode(first,15);
   
  //print the linked list after removing all occurences of 15 in the list 
  cout << "The linked list after deleting all occurences of 15 in the list:" << endl;
  traverse = first;  
  while (traverse != NULL)
  {
    cout << traverse->info << endl;
    traverse = traverse->link;
  }  
}  // end main

/* ------------------------------------------------------------------------ */

void deleteKthElement( nodeType *firstElement,int k, const int& count)
{
  assert(k <= count);  
  nodeType *first ,*last, *current, *trailCurrent;
  int i = 1;
  
 // first = firstElement;
  
  if (firstElement == NULL)
    cerr << "Cannot delete from an empty list!" << endl;
  else
     if (k == 1)
     {
       current = firstElement;
       firstElement = firstElement->link;
       
       if (firstElement == NULL)
          last = NULL;
       
       delete current;
     }
     else
     {
         trailCurrent = firstElement;
         current = firstElement->link;
         
          i = 2;
          while(i < k)
          {
            trailCurrent = current;
            current = current->link;
            i++;
          }
          
          trailCurrent->link = current->link;
          if (current == last)
            last = trailCurrent;
      }       
}  //end deleteKthElement


void deletesmallestInfoNode(nodeType *firstType)
{   
    nodeType *first;
    first = firstType;
    if (first == NULL)               // the list has only one node
	cerr << "Cannot delete from an empty list!" << endl;		
    else
    {
       nodeType* newNode;
       bool found = false;              
       newNode = first;         // newNode points to the first node
       
       while (newNode != NULL && !found)
        {
        if (newNode->link == NULL) //only 1 node in list or the last 
	    {
	    	 deleteNode(first,newNode->info); //call function to delete node
			 found = true;			//smallest info found !
	    }
	    else if (newNode->info <= newNode->link->info)
           {
            deleteNode(first,newNode->info); //call function to delete node
            found = true;                  //smallest info found !
           }
           else
             newNode = newNode->link; //advance newNode 
        }  // end while   
    } // endif
}//end deletesmallestInfoNode


void deleteNode(nodeType *firstNode ,const int& deleteItem)
{
    nodeType *first, *last;
	nodeType *current; //pointer to traverse the list
	nodeType *trailCurrent; //pointer just before current
	bool found;
	
	first = firstNode;

	if(first == NULL)    //Case 1; list is empty. 
		cerr<<"Cannot delete from an empty list.\n";
	else
	{
		if(first->info == deleteItem) //Case 2 
		{
			current = first;
			first = first->link;			
			if(first == NULL)    //list only had 1 node			
             	last = NULL;
     			delete current;	   
		}
		else  //search the list for the node with the given info
		{
			found = false;
			trailCurrent = first;   //set trailCurrent to point to
                                 //the first node
			current = first->link;  //set current to point to the 
    			   //second node
	
			while(current != NULL && !found)
			{
  				if(current->info != deleteItem) 
				{
					trailCurrent = current;
					current = current->link;
				}
				else
					found = true;
			} // end while

			if(found) //Case 3; if found, delete the node
			{
				trailCurrent->link = current->link;
				//count--;

				if(last == current)      //node to be deleted was 
                                     //the last node
					last = trailCurrent;  //update the value of last

				delete current;  //delete the node from the list
			}
			else
				cout<<"Item to be deleted is not in the list."<<endl;
		} //end else
	} //end else
} //end deleteNode



//function to delete all occurences of a given info in the list
void deletegivenInfoNode(nodeType *fNode, const int& deleteInfo)
{ 
   nodeType *first;
   first = fNode; 
   bool found = false;
   if (first == NULL)               // the list has only one node
	cerr << "Cannot delete from an empty list!" << endl;		
    else
    {
       nodeType *traversePtr;         //pointer to traverse the list
       traversePtr = first;         // traversePtr points to the first node
       while (traversePtr != NULL)
       { 	
         if (traversePtr->info == deleteInfo)
         {
            deleteNode(first,deleteInfo);
     		found = true; 
   		 }
         else
             traversePtr = traversePtr->link; 		//advance traversePtr
       }   // end while
     }  // end if
	
      if (!(found))
	     cout << "Item to be deleted is not in the list!" << endl; 		
 }  // end deletegivenInfoNode