Solved
IMPLEMENTING NATURAL MERGE FOR LINKED LIST ( NOT FOR FILE )
Posted on 2007-04-10
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