西南交大赵宏宇数据结构实验报告线性表.pdfVIP

数据结构实验报告

评分

学号：2014112024姓名：宋思雨专业：计算机科学与技术

知识范畴：线性表完成日期：2016年03月17日

实验题目：两个有序线性表的归并算法满分——5分

实验内容及要求：

从键盘输入数据，建立两个有序线性表(每个线性表的输入数据按由小到大次序输入来建

立线性表，不必考虑排序算法)；输出建好的这两个有序线性表；将这两个有序线性表归并为

一个有序线性表；输出归并后的有序线性表。

从键盘实现数据输入与输出的格式自拟；要求完成两个同样功能的程序，一个程序采用顺

序存储结构，另一个程序采用链表实现线性表的存储。其中链表实现时，要求利用两个升序链

表的结点实现归并，即归并时不能新建结点，归并后原来两个升序链表的存储空间不在存在。

实验目的：掌握两个有序线性表的归并算法。

数据结构设计简要描述：

顺序存储结构使用结构体，结构体中带有数组以及数组的最大存储空间。

链式存储结构同样使用结构体定义结点，用带附加头结点单向链表，每个结点包括整型或

浮型类型的数据域和一个指针域。

算法设计简要描述：

顺序与链式两种存储均为依次互相比较两线性表中值的大小。顺序存储是新申请存储空间

将数据依次存入静态数组中，链式存储是利用原有空间将结点按照数据大小进行重新连接。

输入/输出设计简要描述：

从键盘以从小到大的顺序输入以空格(或CR或TAB)分隔的若干不等于0的整数，直到输

入0时停止输入，按整数输入次序建立结点并顺序连接结点。

编程语言说明：

使用VisualC++和C编程。顺序表结构部分采用C语言实现；各函数使用的是C语言的

编写规范，输出与输入使用的是printf和scanf；链式表结构部分使用的是C++语言；输入和

输出分别采用cin和cout;注释采用C/C++规范。

主要函数说明：

LinkListcrt()//创建链表

voidMergeList(LinkListLa,LinkListLb,LinkListLc)//归并算法排序

voidprt(LinkListh)//输出存储的元素

程序测试简要报告：

测试1：

1/9

测试2：

源程序代码：

1.顺序存储：

#includestdio.h

#defineMAX_N10

typedefstruct

{

intelem[MAX_N];

intn;

intmaxsize;

}SqList;

voidinitiate(SqList*pL)

{

inta;

pL-n=0;

pL-maxsize=MAX_N;

while(1)

{{

if(a==0||pL-n=MAX_N)break;

pL-elem[pL-n++]=a;

}

}

intmerge(SqList*a,SqList*b,SqList*c)

2/9

{

if(a-n+b-nc-n)

return-1;

inti=0;intj=0;intk=0;

c-n=a-n+b-n;

while(ia-njb-n)

{

if((a-elem[i]b-elem[j]))

c-elem[k++]=a-elem[i++];

elsec-elem[k++]=b-el