02-线性结构1 两个有序链表序列的合并 (15分)(数据结构)(C语言实现)

78 阅读 0 评论 52 点赞

我是靠谱客的博主不安机器猫，这篇文章主要介绍02-线性结构1 两个有序链表序列的合并 (15分)(数据结构)(C语言实现)，现在分享给大家，希望可以做个参考。

本题要求实现一个函数，将两个链表表示的递增整数序列合并为一个非递减的整数序列。

函数接口定义：

复制代码

1
2
List Merge( List L1, List L2 );

其中List结构定义如下：

复制代码

1
2
3
4
5
6
7
typedef struct Node *PtrToNode;
struct Node {
    ElementType Data; /* 存储结点数据 */
    PtrToNode   Next; /* 指向下一个结点的指针 */
};
typedef PtrToNode List; /* 定义单链表类型 */

L1和L2是给定的带头结点的单链表，其结点存储的数据是递增有序的；函数Merge要将L1和L2合并为一个非递减的整数序列。应直接使用原序列中的结点，返回归并后的带头结点的链表头指针。

裁判测试程序样例：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <stdio.h>
#include <stdlib.h>

typedef int ElementType;
typedef struct Node *PtrToNode;
struct Node {
    ElementType Data;
    PtrToNode   Next;
};
typedef PtrToNode List;

List Read(); /* 细节在此不表 */
void Print( List L ); /* 细节在此不表；空链表将输出NULL */

List Merge( List L1, List L2 );

int main()
{
    List L1, L2, L;
    L1 = Read();
    L2 = Read();
    L = Merge(L1, L2);
    Print(L);
    Print(L1);
    Print(L2);
    return 0;
}

/* 你的代码将被嵌在这里 */

输入样例：

复制代码

输出样例：

复制代码

1
2
3
4
1 2 3 4 5 6 8 10 
NULL
NULL

本题不要求你实现链表的read()操作，只要求你对两个链表进行合并。Merge这个函数如何实现呢?
在Merge函数中，我们首选需要创造一个新的链表，来存两个链表的合并，链表首先都有个头，无论空还是不空，
所以我们直接进行个判断，如果a空或者b空，那么新的链表的next都会指向不空的那一方，如果都为空的话，那么新的链表也会指向空。
如果链表都不为空的情况下，我们需要进行判断，首先a和b都指向两个链表的next，如果a指向的值比b指向的值要大的话，那么新链表的下一个就是a，并且a要指向a的next，以此往复，进行判断，知道表尾，循环结束。这就是文章的大概思路。
我们来看一下代码的具体实现:

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
List Merge(List L1, List L2)
{
    List L;
    L = (List)malloc(sizeof(struct Node)); //
    PtrToNode a,b,c;
    a = L1->Next; b = L2->Next;
    c = L;
    while (a != NULL&&b != NULL)
    {
        if (a->Data <= b->Data)
        {
            c->Next = a; c = a; a = a->Next;
        }
        else {
            c->Next = b; c = b; b= b->Next;
        }
    }
    c->Next=a?a:b;
    L1->Next = NULL;   
    L2->Next = NULL; 
    return L;
}