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

URGENT HELP on doubly linked lists! Sort function not working

Discussion in 'C++' started by davitek, Nov 18, 2010.

  1. davitek

    davitek New Member

    Joined:
    Nov 18, 2010
    Messages:
    1
    Likes Received:
    0
    Trophy Points:
    0
    How do you sort a doubly linked list? This is the code i'v written. But its not working! I have to submit this tomorrow. Tried everything! :disappoin everything except the sort function works.please help
    Code:
    #include<iostream.h>
    #include<conio.h>
    #include<process.h>
    
    struct node
    {
     int data;
     node *prev;
     node *next;
     };
    
     class dlist
     {
      node *first, *last;
      public:
      dlist()
      {
       first=last=NULL;
       }
      void append(int);
      void insertfront(int);
      void insertafter(int,int);
      void delfront();
      void dellast();
      void nodesearch(int);
      void display();
      void sort();
      };
    
      void dlist::append(int d)
      {
       node *t;
       t=new node;
       t->data=d;
       if(first==NULL)
       {
        first=last=t;
        first->prev=NULL;
        first->next=NULL;
        return;
        }
        last->next=t;
        t->prev=last;
        t->next=NULL;
        last=t;
       }
    
       void dlist::insertfront(int d)
       {
        node * t;
        t= new node;
        t->data=d;
        if(first==NULL)
        {
         cout<<"\n list empty";
         return;
         }
        first->prev=t;
        t->next=first;
        t->prev=NULL;
        first=t;
        }
    void dlist::sort()
    {
    node *q,*p;
    p=new node;
    if(first==NULL)
       {
        cout<<"\n list empty..";
        return;
    }
    if(first->next==NULL)
    {
    cout<<"Cannot sort with 1 node\n";
    return;
    }
    else
    {
    q=first;
    while(q->next!=NULL)
    {
    q=q->next;
    if(q->data>p->data)
    {
    q->next=p->next;
    p->prev=q->prev;
    p->next=q;
    q->prev=p;
    }
    q=q->next;
    }
    }
    }
    
      void dlist::insertafter(int c,int d)
      {
       node *t, *q;
       if(first==NULL)
       {
        cout<<"\n list empty..";
        return;
        }
        q= first;
        for(int i=1;i<c;i++)
        {
         if(q==NULL)
         {
          cout<<"\n lesser no of nodes";
          return;
          }
         q=q->next;
         }
        t= new node;
        t->data=d;
        t->prev=q;
        t->next=q->next;
        q->next=t;
        q=t->next;
        q->prev=t;
       }
    
      void dlist::delfront()
      {
       node *q;
       if(first==NULL)
       {
        cout<<"\n list is empty";
        return;
        }
        q=first;
        cout<<"\n node deleted "<<first->data;
        if(first==last)
         first=last=NULL;
         else
         {
          first=first->next;
          first->prev=NULL;
           }
          delete q;
         }
    
      void dlist::dellast()
      { node *q;
       if(first==NULL)
       {
        cout<<"\n list empty";
         return;
         }
       q=last;
       if(first==last)
        first=last=NULL;
        else
        {
         last=last->prev;
         last->next=NULL;
         }
         delete q;
        }
    
      void dlist::nodesearch(int d)
      {
       node *q;
       if(first==NULL)
       {
        cout<<"\n list empty";
        return;
        }
       q=first;
        while(q !=NULL)
        {
         if(q->data==d)
         {
          cout<<"\n node with data "<<d <<"is found" <<endl;
          return;
          }
         q=q->next;
         }
         cout<<"\n node with data "<<d<<"is not found"<<endl;
       }
    
       void dlist::display()
       {
        node *q;
        if(first==NULL)
        {
         cout<<"\n list empty";
         return;
         }
          q=first;
          cout<<"\n list elements";
          while(q !=NULL)
        {
         cout<<q->data <<"\t";
         q= q->next;
         }
       }
    void main()
    {
     clrscr();
     int choice,num,c;
     dlist q;
     while(1)
     {
      cout<<"\n options....\n";
      cout<<"\n 1. append \n 2.insertfront \n 3.insertafter \n 4.deletefront \n 5.deletelast \n 6. nodesearch \n 7. display \n 8.exit";
      cout<<"\n Enter your options";
      cin>>choice;
      switch(choice)
      {
       case 1: cout<<"\n Enter data to be appended ";
           cin>>num;
           q.append(num);
           break;
       case 2:cout<<"\n enter data to be inserted in front";
         cin>>num;
          q.insertfront(num);
           break;
       case 3:cout<<"\n Enter position of insert";
         cin>>c;
         cout<<"\n Enter element to be inserted";
         cin>>num;
          q.insertafter(c,num);
          break;
       case 4: q.delfront();
          break;
       case 5: q.dellast();
          break;
       case 6: cout<<" Enter data to be searched";
           cin>>c;
           q.nodesearch(c);
           break;
       case 7: cout<<" Elements in list";
           q.display();
           break;
    
       case 8: exit(1);
        case 9:q.sort()
        break;
       }
      }
     }
     
    Last edited by a moderator: Nov 18, 2010
  2. virxen

    virxen New Member

    Joined:
    Nov 24, 2009
    Messages:
    387
    Likes Received:
    90
    Trophy Points:
    0
  3. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,012
    Likes Received:
    203
    Trophy Points:
    0
    Occupation:
    Senior Support Engineer
    Location:
    England
    "Not working" isn't a very clear description. How exactly isn't it working? What do you observe? What do you expect? Where does the program start going wrong? What input did you give? Were there any compiler warnings?

    Managing all the pointers in a double linked list can be tricky. Have you figured out on paper exactly what should happen?
     

Share This Page