I need u to help me correct this code of implementing NATURAL MERGE FOR LINKED LIST ( NOT FOR FILE ), I base on the ideas of natural merge on file to do it.
HERE IS MY SOURCE CODE
typedef struct NODE{
elem data;
struct NODE *next;
} NODE;
typedef NODE *list;
////////////////// NATURAL SORT FILE USE LINKED LIST //////////////////////
void copyrun2(list &l1, list &l2)
{
list p2 = l2;
list pl1 = l1;
list pl2 = l1->next;
while(p2->next!=NULL)
{
p2 = p2->next;
}
while(pl2!=NULL && pl2->data >= l1->data)
{
l1 = l1->next;
pl2 = pl2->next;
}
p2 = pl1;
l1->next = NULL;
l1 = pl2;
}
void distribute2(list &l1, list &l2, list &l3)
{
do
{
copyrun2(l1,l2);
if(l1!=NULL)
copyrun2(l1,l3);
}
while(l1!=NULL);
}
void mergerun2(list &l1, list &l2, list &l3)
{
l1 = new NODE;
list p2 = l2->next;
list p4 = l3->next;
while(l2->data < p2->data && l3->data < p4->data && p2 !=NULL && p4!= NULL)
{
if(l2->data < l3->data)
{
l1->next = l2;
l2 = l2->next;
l1 = l1->next;
p2 = p2->next;
}
else
{
l1->next = l3;
l3 = l3->next;
l1 = l1->next;
p4 = p4->next;
}
}
while(l2->data < p2->data)
{
l1->next = l2;
l2 = l2->next;
l1 = l1->next;
p2 = p2->next;
}
while(l3->data < p4->data)
{
l1->next = l3;
l3 = l3->next;
l1 = l1->next;
p4 = p4->next;
}
}
void merge2(list &l1, list &l2, list &l3, int &R)
{
R=0;
list p1 = new NODE;
cout<<"AAAAAAAAAAAAAAAAAAAAAAAAAAAA";
while(l2!=NULL && l3!=NULL)
{
mergerun2(l1,l2,l3);
R++;
}
while(l2!=NULL)
{
copyrun2(l2,l1);
R++;
}
while(l3!=NULL)
{
copyrun2(l3,l1);
R++;
}
l1 = p1;
}
void natural_list_sort(list &l1)
{
int R;
list l2=NULL, l3=NULL;
do
{
distribute2(l1,l2,l3);
merge2(l1,l2,l3,R);
}
while(R>1);
}
IN MAIN FUNCTION u CALL natural_list_sort(list &l1) to run it
by: KdoPosted on 2007-04-10 at 06:46:12ID: 18882257
Hi bpc1985,
It looks like you've made this natural sort process a lot harder than it needs to be. :(
Coding stype can be recursive or iterative. If you can get your head wrapped around the recursive calls, this generally results in cleaner and shorter code.
The recursive call looks something like this:
call X(root)
within X:
Find Run1 (length x)
Find Run2 (length y)
Merge in place (generating run of length x+y)
call X (start +(x+y))
Merge returned string with Run1.
or
call X(root)
within X:
Find run1 (length x)
call X (start + x)
Merge in place (run1 and the run returned by (X)