浙大版《数据结构(第2版)》题目集-习题2.5 两个有序链表序列的合并
#include <stdio.h>
#include <stdlib.h>
typedef int ElementType;
typedef struct Node *PtrToNode;
struct Node {
ElementType Data;
PtrToNode Next;
};
typedef PtrToNode List;
void Read(List &L, ElementType a[], int n); /* 细节在此不表 */
void Print( List L ); /* 细节在此不表;空链表将输出NULL */
List Merge( List L1, List L2 );
int main()
{
ElementType a1[3] = {1, 3, 5};
ElementType a2[5] = {2, 4, 6, 8, 10};
List L1, L2, L;
Read(L1, a1, 3);
Read(L2, a2, 5);
L = Merge(L1, L2);
Print(L);
Print(L1);
Print(L2);
return 0;
}
/* 你的代码将被嵌在这里 */
List Merge( List L1, List L2 ) // 合并函数
{
List L, pre1, pre2, pre;
L = (List)malloc(sizeof(List));
L -> Next = NULL;
pre1 = L1 -> Next;
pre2 = L2 -> Next;
pre = L;
while(pre1 != NULL && pre2 != NULL)
{
if(L1 -> Next -> Data <= L2 -> Next -> Data)
{
L1 -> Next = pre1 -> Next;
pre1 -> Next = pre -> Next;
pre -> Next = pre1;
pre = pre1;
pre1 = L1 -> Next;
}
else
{
L2 -> Next = pre2 -> Next;
pre2 -> Next = pre -> Next;
pre -> Next = pre2;
pre = pre2;
pre2 = L2 -> Next;
}
}
while(pre1 != NULL)
{
L1 -> Next = pre1 -> Next;
pre1 -> Next = pre -> Next;
pre -> Next = pre1;
pre = pre1;
pre1 = L1 -> Next;
}
while(pre2 != NULL)
{
L2 -> Next = pre2 -> Next;
pre2 -> Next = pre -> Next;
pre -> Next = pre2;
pre = pre2;
pre2 = L2 -> Next;
}
return L;
}
void Read(List &L, ElementType a[], int n) //尾插法函数
{
List s, r;
L = (List)malloc(sizeof(List));
r = L;
for(int i = 0; i < n; i++)
{
s = (List)malloc(sizeof(List));
s -> Data = a[i];
r -> Next = s;
r = s;
}
r -> Next = NULL;
}
void Print( List L ) //输出函数
{
List p = L -> Next;
while(p != NULL)
{
printf("%d ", p -> Data);
p = p -> Next;
}
printf("\n");
}