两个有序链表序列的合并

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

函数接口定义：

1	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 ); /* 细节在此不表；空链表将输出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;

}

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

List Merge( List L1, List L2 )

{

List L3=(struct Node *)malloc(sizeof(struct Node));

List L=L3;

List p=L1->Next;

List q=L2->Next;

while (p && q){

if (p->Data < q->Data){

L->Next=p;

p=p->Next;

}

else{

L->Next=q;

q=q->Next;

}

L=L->Next;

}

L->Next=NULL;

if (p) L->Next=p;

if (q) L->Next=q;

L1->Next=NULL;

L2->Next=NULL;

return L3;

}

输入样例：

1 3 5

2 4 6 8 10

输出样例：

1 2 3 4 5 6 8 10

NULL

用数组表示一元多项式并计算
用数组如何表示多项式： 1.多项式项数n： ?将数组个数定义时比n大就可以表示出n项 2.各项系数ai ：? 数组内值表示项式系数 3.指数i? ：? ? ? ? ? ? ? 数组的下标用来表示多项式系数...
链表结构表示一元多项式非零项并计算相加
一元多项式用链表表示，只用表示非零项。每个非零项都包含指数和系数两部份，这样可以用链表结构来表示。注：存一元多项式非零项时，要按指数大小有序存储，为了方便相加计算。...
线性表结构、描述、操作
什么是线性表？线性表的一些概念线性表主要操作 ...
用数组实现线性表详解代码
用数组实现线性表，就是将数据都存放到数组中，然后写函数实现线性表的基本操作。数组实现线性表基本操作代码：数组实现线性表优点：数组实现线性表缺点： ...
用链式存储实现线性表详解代码
用链式存储实现思想：不要求逻辑上相邻的两个元素物理上相邻，通过“链”建立起数据之间的逻辑关系。逻辑相邻：指两个元素是挨着的，（比如1，2，3）物理相邻：指两个元素存在内存上是挨着的，地址相邻（比如0x00000000, 0x00000004)...
C++ Lists（链表）
Lists将元素按顺序储存在链表中. 与向量(vectors)相比, 它允许快速的插入和删除，但是随机访问却比较慢. assign() 给list赋值 back() 返回最后一个元素 begin() 返回指向第一个元素的迭代器 clear() 删除所有元素 empty() 如果list是空的则返回true end() 返回末尾的迭代器 erase() 删除一个元素 front() 返回第一个元素...
数据结构概念和分类
数据结构（data structure)数据结构是相互之间存在一种或多种特定关系的数据元素的集合。数据元素间的关系称为结构。客观事物之间存在着各种不同的联系，但将其抽象为数据以后再来研究它们所具有的共性关系就简单得多。...
最大子列和问题
给定K个整数组成的序列{ N1, N2, ..., NK }，“连续子列”被定义为{ Ni, Ni+1, ..., Nj }，其中 1≤i≤j≤K。“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列{ -2, 11, -4, 13, -5, -2 }，其连续子列{ 11,...
二分查找算法
本题要求实现二分查找算法。函数接口定义：Position BinarySearch( List L, ElementType X );其中List结构定义如下：typedef int Position; typedef struct LNode *List; struct LNode { ElementType Data[MAXSIZE]; Position Last;...
结构数组表示一元多项式并计算相加
一元多项式用数组表示，只用表示非零项。每个非零项都包含指数和系数两部份，这样可以用结构数组来表示。这样表示后做相加运算时，一定要先排好序。...

函数接口定义：

裁判测试程序样例：

输入样例：

输出样例：

相关文章: