全站数据
8 4 2 0 5 8 1

c语言中链表合并怎么弄详解

消防与法 | 简单学习,快乐成才!         
问题更新日期:2024-10-13 22:43:22

问题描述

c语言中链表合并怎么弄详解,麻烦给回复
精选答案
最佳答案

函数接口定义:

List Merge( List L1, List L2 );

其中List结构定义如下:

typedef struct Node *PtrToNode;

struct Node {

ElementType Data;

PtrToNode Next;

};

typedef PtrToNode List;

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

裁判测试程序样例:

#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 );

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;

}

输入样例:

3

1 3 5

5

2 4 6 8 10

输出样例:

1 2 3 4 5 6 8 10

NULL

NULL

由后面打印出的两个NULL可以看出,这个操作是将L1,L2的节点重新挂在L3的节点上,L1,L2,L3均为头节点,最后实现代码

List Merge( List L1, List L2 )

{

List pa,pb,pc,L;

L = (List)malloc(sizeof(struct Node));

pa=L1->Next;// 指向pa第一个元素

pb=L2->Next;// 指向pb第一个元素

pc = L;

while(pa && pb)

{

if(pa->Data <= pb->Data)

{

pc->Next = pa;

pc = pa;

pa = pa->Next;

}

else

{

pc->Next = pb;

pc = pb;

pb = pb->Next;

}

}

if(pa)

{

pc->Next = pa;

}

if(pb)

{

pc->Next = pb;

}

L1->Next = NULL;

L2->Next = NULL;

return L;

}