1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

Need urgent help in linked list

Discussion in 'C++' started by Cassandra, Mar 12, 2009.

  1. Cassandra

    Cassandra New Member

    Joined:
    Mar 12, 2009
    Messages:
    3
    Likes Received:
    0
    Trophy Points:
    0
    I encounter some problem in linked list coding. I extarcted part of the coding from a C++ book and I have been studied it for so long but still cant fix the error.
    The error is the variable "counter". In the book, "counter" is the variable to store the number of elements in the linked list and it's defined in private part of the class. In the constructor, they let counter=0 where the compiler shows that it's an error. Another errors are all the "counter++" in "insert2". I tried to correct those errors but i just can't fix them... Below are my coding. I'm struggling in this coding and i hope someone can help me... :nonod:
    Code:
    #include <iostream>
    using namespace std;
    class linkedList
    {
     private:
             struct node
             {
                int info;   //integer to be stored in the pointer
       int counter;  //variable to store the number of elements in the list
                node *link;
             }*p;
     public:
             linkedList();
             void insert(int num);
       void insert2(int num); //insert node at a particular position
             void del(int num);
       void sort();   //insertion sort
       bool search(int num);
             void display();
             int count();
       void destroyList();
             ~linkedList();
    };
    linkedList::linkedList()
    {
        p = NULL;
     counter = 0;
    }
    void linkedList::insert(int num)
    {
       node *q, *t;
       if(p==NULL)
       {
          p = new node;    //create a new node, p
          p->info = num;
          p->link = NULL;
       }
       else
       {
            q = p;
      while(q->link != NULL)
      q = q->link;   //advance q to the next node
          t = new node;
          t->info = num;
          t->link = NULL;
          q->link = t;
       }
    }
    void linkedList::insert2(int num)
    {
     node *q, *r, *s;   //q = pointer to traverse the list
            //r = pointer just before q
            //s = pointer to create a node
     bool found;
     s = new node;
     if(s!=NULL)
     {
      s->info = num;   //store the new item in the node
      s->link = NULL;   //set the link field to NULL
     }
     if(p==NULL)     //case1: the list is initially empty and the node in it is the only node,
     {       //so the first node in the list
      p = new node;
      //counter++;
     }
     else
     {
      q = p;
      found = false;
      while(q!=NULL && !found)  //search the list
       if(q->info >= num)
        found = true;
       else
       {
        r = q;
        q = q->link;
       }
      if(q==p)   //case2: the list isn't empty and the new item is smaller than the smallest item in the list.
      {     //the new item goes in front of the list 
       s->link = p;
       p = new node;
       //counter++;
      }
      else    //case3: the list isn't empty and the new item is larger than the first item in the list.
      {     //the new item is to be inserted somewhere in the list
       r->link = s;
       s = new node;
       //counter++;
      }
     }
    }
    void linkedList::del(int num)
    {
       node *q, *r;
       q = p;
       if(q->info == num)
       {
          p = q->link;    //make p points to the next node of q
          delete q;
          return;
       }
       r = q;
       while(q!=NULL)
       {
            if(q->info == num)
          {
             r->link = q->link;
             delete q;
             return;
          }
          r = q;
          q = q->link;
       }
       cout<<"\nElement "<<num<<" not Found."<<endl;
    }
    void linkedList::display()
    {
       node *q;
       for(q = p; q!=NULL; q=q->link)
            cout<<endl<<q->info;
    }
    int linkedList::count()
    {
       node *q;
       int c=0;
       for(q=p; q!=NULL; q=q->link)
       c++;
       return c;
    }
    void linkedList::sort()
    {
     node *q, *r, *s, *t;  //q = the pointer to the last node of the sorted list
            //r = the pointer to the node that is to be moved to its proper location
            //s = current pointer
            //t = the pointer which points to the node just before current pointer, s
     q = p;
     if(p==NULL)
      cout<<"Cannot sort an empty list."<<endl;
     else if(p->link==NULL)
      cout<<"The list is of length 1. "
       <<"It is already in order."<<endl;
     else
      while(q->link!=NULL)
      {
       r = q->link;
       if(r->info < p->info)
       {
        q->link = r->link;
        r->link = p;
        p = r;
       }
       else
       {
        t = p;
        s = p->link;
        while(s->info < r->info)
        {
         t = s;
         s = s->link;
        }
        if(s!=r)
        {
         q->link = r->link;
         r->link = s;
         t->link = r;
        }
        else
         q = q->link;
       }
      }
    }
    bool linkedList::search(int num)
    {
     node *q;    //pointer to traverse the list
     bool found;
     q = p;     //set current to point to the first node
     found = false;
     while(q!=NULL && !found)   //search the list
      if(q->info==num)    //the item is found
       found = true;
      else
       q = q->link;    //make current point to the next node
     return found;
    }
    void linkedList::destroyList()
    {
     node *q;   //pointer to deallocate the memory occupied by the node
     while(p!=NULL)  //while there are nodes in the list
     {
      q = p;
      p = p->link; //advance p to the next node
      delete q;
     }
    }
    linkedList::~linkedList()
    {
       node *q;
       if(p==NULL)
     return;
       while(p!=NULL)
       {
          q = p->link;
          delete p;
          p = q;
       }
    }
    int main()
    {
       linkedList list;
       int choice, i, x;
    start:
       cout<<"*****************************************************"<<endl;
       cout<<"                    ~ Main menu ~                    "<<endl;
       cout<<"    (1) Insertion of an integer into a sorted list.  "<<endl;
       cout<<"    (2) Delection of an integer in a list.           "<<endl;
       cout<<"    (2) Searching integer in a list.                 "<<endl;
       cout<<"    (3) Sorting integers in a list.                  "<<endl;
       cout<<"    (4) Exit.                                        "<<endl;
       cout<<"*****************************************************"<<endl;
       cout<<endl;
       cout<<"Please choose an operation that you would like to perform: "<<endl;
       cin>>choice;
       cout<<endl;
       if(choice==1)
       {
        cout<<"Enter integers ending with -1:"<<endl;;
        cin>>i;
        
        while(i!=-1)
        {
         list.insert(i);
         cin>>i;
        }
        cout<<endl;
        cout<<"The sequence of integers before sorting is:";
        list.display();
        cout<<endl;
        
        list.sort();
        cout<<"The sequence of integers after sorting is:";
        list.display();
        cout<<endl;
        cout<<"Enter an integer that you want to insert into the list: ";
        cin>>x;
        cout<<endl;
        list.insert2(x);
        cout<<"The sequence of integers after insertion of integer "<<x<<" is:";
        list.display();
        cout<<endl;
        list.destroyList();
        goto start;
       }
       else if(choice==2)
       {
        cout<<"Enter integers ending with -1:"<<endl;;
        cin>>i;
        
        while(i!=-1)
        {
         list.insert(i);
         cin>>i;
        }
        
        cout<<endl;
        cout<<"Number of integers entered is: "<<list.count();
        list.display();
        cout<<endl<<endl;;
        cout<<"Enter the integer to be deleted: ";
        cin>>i;
        
        list.del(i);
        cout<<endl;
        
        cout<<"The remaining integers are: "<<endl;
        list.display();
        cout<<endl;
        list.destroyList();
        goto start;
       }
       else if(choice==2)
       {
        cout<<"Enter integers ending with -1:"<<endl;
        cin>>i;
        
        while(i!=-1)
        {
         list.insert(i);
         cin>>i;
        }
      
      cout<<endl;
      
      cout<<"Enter the integer that you want to search: ";
      cin>>x;
      cout<<endl;
      
      list.search(x);
      
      if(x==i)
       cout<<"The search integer is found in the list."<<endl<<endl;
      else
       cout<<"The search integer is not found in the list."<<endl<<endl;
      list.destroyList();
      goto start;
       }
       else if(choice==3)
       {
        cout<<"Enter integers ending with -1:"<<endl;
        cin>>i;
        
        while(i!=-1)
        {
         list.insert(i);
         cin>>i;
        }
      cout<<endl;
      
      cout<<"The sequence of integers before sorting is:";
      list.display();
      cout<<endl<<endl;
      list.sort();
      cout<<"The sequence of integers after sorting is:";
      list.display();
      cout<<endl;
      list.destroyList();
      goto start;
       }
       else if(choice==4)
       {
        cout<<"See you next time! Bye Bye!"<<endl;
        system("PAUSE");
       }
       else
       {
        cout<<"Wrong input!!!"<<endl;
        goto start;
       }
       return 0;
    }
     
    Last edited by a moderator: Mar 12, 2009
  2. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,285
    Likes Received:
    364
    Trophy Points:
    83
    There are lots of code related to linked list and searching can help you a lot
     
  3. Cassandra

    Cassandra New Member

    Joined:
    Mar 12, 2009
    Messages:
    3
    Likes Received:
    0
    Trophy Points:
    0
    hi,
    actually other templates and the main body is functioning well, only the template for "insert2", that is inserting a node into a particular position in the linked list.
    I have no choice but to use this function as i'm required to do so.. Is there any recommandation for it?
     
  4. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,012
    Likes Received:
    203
    Trophy Points:
    0
    Occupation:
    Senior Support Engineer
    Location:
    England
    What exactly is the problem?
    Are you getting compile-time errors, and if so what are they?

    If I complie the code I get "'counter' : undeclared identifier" in linkedList::linkedList(), which is correct as there is no such variable linkedList::counter. Look carefully at the linkedlist class definition and you'll see the problem. If you can't, then tell me where you think linkedList::counter is defined (give the surrounding lines for context rather than line numbers).

    By the way, there's a good reason to use indenting correctly. Fix that and all sorts of problems will become immediately apparent, including I think this one. Has the inaccurate indentation of linkedlist::node::counter fooled you?
     

Share This Page