/*
gia su da co 2 danh sach l1 va l2 va 2 ds nay da dc sap xep tang dan.
toi chi demo phan tron 2 ds tang nay lai thoi.
*/
#include <stdio.h>
#include <conio.h>
typedef int ElementType;
struct Node
{
ElementType Element;
Node *Next;
};
typedef Node *List;
typedef Node *List;
typedef Node *Position;
void makenulllist(List L)
{
L->Next=NULL;
}
void insertlastlist(List L,ElementType X)
{
Node *newnode=new Node;
newnode->Element=X;
Position P=L;
while(P->Next!=NULL)
{
P=P->Next;
}
P->Next=newnode;
newnode->Next=NULL;
}
void showlist(List L)
{
Position P=L->Next;
while(P!=NULL)
{
printf("|%d|",P->Element);
P=P->Next;
}
}
void tron2ds(List L1,List L2)
{
Position P1=L1->Next;
Position P2=L2->Next;
while(L2->Next!=NULL)
{
// truong hop l2 dai hon l1 thi khi cuoi l1 chi can gan phan
//con lai cua l2 cho l1 la xong.
// con l1 dai hon l2 thi viet chen cac phan tu l2 vao l1 binh thuong
if(P1->Next==NULL&&P2->Element>=P1->Element)
{
P1->Next=P2;
break;
}
if(P2->Element<P1->Element) // thi chen p2 vao truoc p1
{
Position truocp1;
//tim p truoc p1
truocp1=L1;
while(truocp1->Next!=P1)
{
truocp1=truocp1->Next;
}
//tach p2 ra khoi L2 va chen vao L1 o vi tri truoc P1.
L2->Next=P2->Next;
P2->Next=P1;
truocp1->Next=P2;
P1=P2;
P2=L2->Next;
}
else //nguoc lai thi P1=P1->Next roi xet tiep de tim vi tri chen cho p2 trong p1
{
P1=P1->Next;
}
}
}
void main()
{
clrscr();
List L1,L2;
makenulllist(L1);
makenulllist(L2);
// tao 2 list L1 {1,3,5,7,9} va list L2 {0,2,4,6,8,10} nhu da thay la ca 2 list deu sap xep tang dan
for(int i=0;i<=10;i++)
{
if(i<10)
{
insertlastlist(L1,i);
}
else
{
insertlastlist(L2,i);
}
}
printf("2 DS\n");
printf("L1: ");
showlist(L1);
printf("\n");
printf("L2: ");
showlist(L2);
printf("\nSau khi tron L2 vao L1\n");
tron2ds(L1,L2);
showlist(L1);
getch();
}
Hy vọng hữu ích với bạn!
Nosomovo
