實(shí)現(xiàn)兩個(gè)鏈表的合并？
#include
#include
int m, n;
int count = 1;
struct Node
{
int data;
struct Node *next;
}*A,*B,*C,*D;
//打印AList列表
void printList(struct Node *AList)
{
struct Node *post;
post = AList->next;
switch(count)
{
case 1:
printf("\nListA: ");
break;
case 2:
printf("\nListB: ");
break;
case 3:
printf("\nListC: ");
break;
case 4:
printf("\nListD: ");
break;
default:
printf("\nList: ");
break;
}
while (post)
{
printf("%d ",post->data);
post = post->next;
}
count ++;
}
//初始化表頭,列表含有表頭
void init()
{
A = (struct Node*)malloc(sizeof(struct Node));
A->data = 0;
A->next = 0;
B = (struct Node*)malloc(sizeof(struct Node));
B->data = 0;
B->next = 0;
C = (struct Node*)malloc(sizeof(struct Node));
C->data = 0;
C->next = 0;
D = (struct Node*)malloc(sizeof(struct Node));
D->data = 0;
D->next = 0;
}
//讀取列表A和B
void ReadListAB()
{
int i;
struct Node *post;
struct Node *pre;
// 輸入列表長(zhǎng)度
printf("m="); scanf("%d",&m);
printf("n="); scanf("%d",&n);
//讀取列表A
pre = A;
for(i=1; i
{
post = (struct Node*)malloc(sizeof(struct Node));
printf("A%d = ", i);
scanf("%d", &post->data);
post->next = 0;
pre->next = post;
pre = post;
}
//讀取列表B
pre = B;
for(i=1; i
{
post = (struct Node*)malloc(sizeof(struct Node));
printf("B%d = ", i);
scanf("%d", &post->data);
post->next = 0;
pre->next = post;
pre = post;
}
}
//合并列表A和B
void MergeABToC()
{
int i;
struct Node *pre, *postA, *postB, *postC;
pre = C;
postA = A->next;
postB = B->next;
if(m >= n)
{
for(i=1; i
{
postC = (struct Node*)malloc(sizeof(struct Node));
postC->data = postA->data;
postC->next = 0;
pre->next = postC;
pre = postC;
postC = (struct Node*)malloc(sizeof(struct Node));
postC->data = postB->data;
postC->next = 0;
pre->next = postC;
pre = postC;
postA = postA->next;
postB = postB->next;
}
for(i=n+1; i
{
postC = (struct Node*)malloc(sizeof(struct Node));
postC->data = postA->data;
postC->next = 0;
pre->next = postC;
pre = postC;
postA = postA->next;
}
}
else
{
for(i=1; i
{
postC = (struct Node*)malloc(sizeof(struct Node));
postC->data = postB->data;
postC->next = 0;
pre->next = postC;
pre = postC;
postC = (struct Node*)malloc(sizeof(struct Node));
postC->data = postA->data;
postC->next = 0;
pre->next = postC;
pre = postC;
postA = postA->next;
postB = postB->next;
}
for(i=m+1; i
{
postC = (struct Node*)malloc(sizeof(struct Node));
postC->data = postB->data;
postC->next = 0;
pre->next = postC;
pre = postC;
postB = postB->next;
}
}
}
//使用直接插入法，將C排序輸出D
void SortCToD()
{
struct Node *pre, *postC, *postD, *lopD;
int len;
//表示總的長(zhǎng)度
len = m + n;
pre = D; //指向D有序數(shù)列的尾指針
postC = C->next; //指向C列表
//列表D第一個(gè)節(jié)點(diǎn)加入
postD = (struct Node*)malloc(sizeof(struct Node));
postD->data = postC->data;
postD->next = 0;
pre->next = postD;
pre = postD;
postC = postC->next;
while (postC)
{
//pre為指向插入的前一個(gè)節(jié)點(diǎn)，lopD是指向插入的后一個(gè)節(jié)點(diǎn)
pre = D;
lopD = D->next;
while (lopD)
{
if (lopD->data > postC->data)
break;
else
{
pre = lopD;
lopD = lopD->next;
}
}
//將節(jié)點(diǎn)插入
postD = (struct Node*)malloc(sizeof(struct Node));
postD->data = postC->data;
postD->next = 0;
pre->next = postD;
postD->next = lopD;
//循環(huán)條件
postC = postC->next;
}
}
void main(void)
{
init();
ReadListAB();
MergeABToC();
SortCToD();
printList(A);
printList(B);
printList(C);
printList(D);
}
以上代碼可以運(yùn)行，并且結(jié)果正確。
