By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
432,257 Members | 928 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 432,257 IT Pros & Developers. It's quick & easy.

problem with pointers when sorting a double linked list using merge sort

nabh4u
P: 62
hi friends,

i have a program where i have to sort a double linked list using merge sort. i am having problem with changing the pointers of the list, like the previous and the next pointers of a node. i am unable to understand how can i change those. i tried something but that is not working. please help me as soon as possible as i have a deadline. here is a sample :

Expand|Select|Wrap|Line Numbers
  1. int merge(low,mid,high)
  2. {
  3.    int i,j,k;
  4.    i=low;
  5.    j=mid+1;
  6.    list *temp,*temp1;
  7.    while(i<=mid && j<=high)
  8.    {
  9.       if(current->n <= current->next->n)
  10.       {
  11.          current=current->next;
  12.          i++;
  13.       }
  14.       else
  15.       {
  16.          temp->prev=current->prev;
  17.          temp->next=current->next;
  18.          current->prev=current->next->prev;
  19.          current->next=current->next->next;
  20.          temp1->prev=temp->prev;
  21.          temp1->next=temp->next;
  22.          j++;
  23.       }
  24.    }
current is the pointer pointing to the current node of the list.

this is a kind of implementation i tried. please tell me how should i change the pointers in the list. plese help me, its urgent.

thanx in advance.
Mar 16 '07 #1
Share this Question
Share on Google+
2 Replies


Ganon11
Expert 2.5K+
P: 3,652
Is this the exact code you wre using? The function header needs to declare the types of the parameters (i.e. "int low, int mid, int high" instead of "low, mid, high"). Also, there is a curly bracket missing to close the function.

Next, this line

Expand|Select|Wrap|Line Numbers
  1. current->prev=current->next->prev;
is kind of redundant. current->next->prev should bring you back to current, so why not write

Expand|Select|Wrap|Line Numbers
  1. current->prev = current;
Mar 16 '07 #2

nabh4u
P: 62
Is this the exact code you wre using? The function header needs to declare the types of the parameters (i.e. "int low, int mid, int high" instead of "low, mid, high"). Also, there is a curly bracket missing to close the function.

Next, this line

Expand|Select|Wrap|Line Numbers
  1. current->prev=current->next->prev;
is kind of redundant. current->next->prev should bring you back to current, so why not write

Expand|Select|Wrap|Line Numbers
  1. current->prev = current;
well tht was the sample code i was using but now i changed it. now when i print the list it goes into an infinte loop but when i print the list in reverse it doesnt print all the nodes and the sequence is also wrong (prints the earlier reverse version where the list is not sorted).
eg: the list is 4 3 1 2
after sorting it should be 1 2 3 4 (forward print)
but when printing in forward it goes into infinte loop with 4
and for reverse print i get 1 2 3 only but it should be 4 3 2 1.

here's the changed code:

Expand|Select|Wrap|Line Numbers
  1. int merge(int low,int mid,int high)
  2. {
  3.    int i,j,k;
  4.    i=low;
  5.    j=mid+1;
  6.    list *temp = new list();
  7.    list *temp1=new list();
  8.    current=first;
  9.    temp=current->next;
  10.    temp1->next=current->next;
  11.    temp1->prev=current->prev;
  12.  
  13.    while(i<=mid && j<=high)
  14.    {
  15.       if(current->n <= temp->n)
  16.       {
  17.          current=current->next;
  18.          temp=current->next;
  19.          temp1->next=current->next;
  20.          temp1->prev=current->prev;
  21.          i++;
  22.       }
  23.       else
  24.       {
  25.          current->next=temp->next;
  26.          current->prev=temp;
  27.          temp->next=current;
  28.          temp->prev=temp1->prev;     
  29.          j++;
  30.       }
  31.    } 
  32. }
what about the remaining part of the list? please tell me if this code successfully sorts the link list or not and what is the problem.
please tell me how exactly i should change the pointers.. this is creating a lot of confusion..please correct my code.
thank you in advance...
Mar 16 '07 #3

Post your reply

Sign in to post your reply or Sign up for a free account.