URGENT HELP on doubly linked lists! Sort function not working

davitek's Avatar, Join Date: Nov 2010
Newbie Member
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! 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 shabbir; 18Nov2010 at 21:38.. Reason: Code blocks
virxen's Avatar, Join Date: Nov 2009
Pro contributor
try here

http://www.daniweb.com/forums/thread293711.html
xpi0t0s's Avatar, Join Date: Aug 2004
Mentor
"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?