一、实验内容及要求：
1.从键盘输入数据，建立两个有序线性表(每个线性表的输入数据按由小到大次序输入来建立线性表，不必考虑排序算法)；输出建好的这两个有序线性表；将这两个有序线性表归并为一个有序线性表；输出归并后的有序线性表。
2.从键盘实现数据输入与输出的格式自拟；要求完成两个同样功能的程序，一个程序采用顺序存储结构，另一个程序采用链表实现线性表的存储。其中链表实现时，要求利用两个升序链表的结点实现归并，即归并时不能新建结点，归并后原来两个升序链表的存储空间不在存在。
二、主要说明
1.数据结构设计简要描述：
顺序存储结构使用结构体，结构体中带有数组以及数组的最大存储空间。
链式存储结构同样使用结构体定义结点，用带附加头结点单向链表，每个结点包括整型或浮型类型的数据域和一个指针域。
2.算法设计简要描述：
顺序与链式两种存储均为依次互相比较两线性表中值的大小。顺序存储是新申请存储空间将数据依次存入静态数组中，链式存储是利用原有空间将结点按照数据大小进行重新连接。
第一个程序是通过动态分配内存，初始化两个线性表，然后通过两表相同索引之间值的比较，将其重新赋给新建立的第三个表从而实现两表的合并；
第二个程序是通过建立表头，设置循环分别建立两个链表，然后通过两表中data数值的比较，使第三个表等于第一个表，排序后全部插入第一个表，最后释放第二个表，从而实现量表的合并。
3.输入/输出设计简要描述：
第一个程序从键盘以从小到大的顺序输入以空格(或CR或TAB)分隔的若干不等于0的整数，直到输入0时停止输入，按整数输入次序建立结点并顺序连接结点。
第二个程序从键盘乱序输入以空格(或CR或TAB)分隔的若干不等于0的整数，直到输入0时停止输入，按排序后整数输入次序建立结点并顺序连接结点。
4.编程语言说明：
编程平台：Visual Stdio 2019。编程语言：c语言。
5.主要函数说明：
第一个程序：首先通过InitList函数为线性表动态分配空间，然后通过Input为线性表赋值，初始化好后通过MergeList函数合并两线性表，最后通过Output函数输出线性表。
第二个程序：首先通过CreateList函数在动态创建表头的同时依次指向下一个节点并赋值，再用函数SortList给输入的数排序，然后通过MergeList合并两线性表，最后用OutputList输出线性表。
三、源程序代码：
程序一：
运行示例：
程序源码：
#include<stdio.h>
#include<stdlib.h>
#define LIST_INIT_SIZE 100
typedef struct {
int *elem;
int length;
int listsize;
}SqList;
void InitList(SqList &L) {
L.elem = (int *)malloc(LIST_INIT_SIZE * sizeof(int));
if (!L.elem) exit(1);
L.length = 0;
L.listsize = LIST_INIT_SIZE;
}
void Input(SqList& L) {
int x;
while (1) {
scanf_s("%d", &x);
if (x == 0 || L.length >= LIST_INIT_SIZE) break;
L.elem[L.length++] = x;
}
}
void Output(SqList &L) {
for (int i = 0; i < L.length; i++) {
printf("%3d", L.elem[i]);
}
}
void MergeList(SqList &La, SqList &Lb, SqList &Lc) {
int i = 0, j = 0, k = 0;
Lc.length = La.length + Lb.length;
while (i < La.length && j < Lb.length) {
if (La.elem[i] < Lb.elem[j]) {
Lc.elem[k] = La.elem[i];
i++;
}
else {
Lc.elem[k] = Lb.elem[j];
j++;
}
k++;
}
while (k < Lc.length) {
if (i == La.length) {
Lc.elem[k] = Lb.elem[j];
j++;
}
else {
Lc.elem[k] = La.elem[i];
i++;
}
k++;
}
}
int main()
{
SqList a, b, c;
InitList(a);
InitList(b);
InitList(c);
printf("输入第一个线性表数据:");
Input(a);
printf("输入第二个线性表数据:");
Input(b);
printf("第一个有序线性表:");
Output(a);
printf("\n");
printf("第二个有序线性表:");
Output(b);
printf("\n");
MergeList(a, b, c);
printf("归并后的有序线性表:");
Output(c);
}程序二：
运行示例：
程序源码：
#include<stdio.h>
#include<stdlib.h>
#define LIST_INIT_SIZE 100
typedef struct LNode {
int data;
struct LNode* next;
}LNode,*LinkList;
LinkList CreatList() {
LinkList head, tail,p;
int e;
head = (LinkList )malloc(sizeof(LNode)*LIST_INIT_SIZE);
tail = head;
scanf_s("%d", &e);
while (e) {
p = (LinkList )malloc(sizeof(LNode) * LIST_INIT_SIZE);
p->data = e;
tail->next = p;
tail = p;
scanf_s("%d", &e);
}
tail->next = NULL;
return head;
}
void OutputList(LinkList L) {
LinkList p = L->next;
while (p) {
printf("%3d", p->data);
p = p->next;
}
}
void SortList(LinkList L) {
LinkList p, q;
int temp;
for(p=L;p!=NULL;p=p->next)
for (q = p->next; q != NULL; q = q->next)
{
if (p->data >q->data) {
temp = p->data;
p->data = q->data;
q->data = temp;
}
}
}
void MergeList(LinkList La, LinkList Lb) {
LinkList pa, pb, pc;
pa = La->next;
pb = Lb->next;
pc = La;
free(Lb);
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;
else pc->next = pb;
}
int main()
{
LinkList La,Lb;
printf("输入第一个链表:");
La = CreatList();
SortList(La);
printf("输入第二个链表:");
Lb = CreatList();
SortList(Lb);
printf("第一个排序后的链表:");
OutputList(La);
printf("\n");
printf("第二个排序后的链表:");
OutputList(Lb);
MergeList(La, Lb);
printf("\n");
printf("归并后的链表:");
OutputList(La);
}