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