数据结构实验报告——两个有序线性表的归并算法_数据结构实验顺序存储归并

一、实验内容及要求：

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