数据结构实验报告一.docx

《数据结构实验报告一.docx》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、数据结构实验报告评分满分——5分学号：姓名：陶瑜专业：计算机科学与技术知识范畴：线性表完成日期：2016年03月19日实验题目：两个有序线性表的归并算法实验内容及要求：从键盘输入数据，建立两个有序线性表(每个线性表的输入数据按由小到大次序输入来建立线性表，不必考虑排序算法)；输出建好的这两个有序线性表；将这两个有序线性表归并为一个有序线性表；输出归并后的有序线性表。从键盘实现数据输入与输出的格式自拟；要求完成两个同样功能的程序，一个程序采用顺序存储结构，另一个程序采用链表实现线性表的存储。其中链表实现时，要求利用两

2、个升序链表的结点实现归并，即归并时不能新建结点，归并后原来两个升序链表的存储空间不在存在。实验目的：掌握两个有序线性表的归并算法。数据结构设计简要描述：采用带附加头结点方式建立单向链表；每个结点包括整型类型的数据域和一个指针域。第一个程序以数组的形式建立单向顺序存储的线性表，第二个程序以指针的形式建立链式存储的线性表。算法设计简要描述：线性表排序采用比较大小交换位置的算法实现；线性表的归并采用先比较两个线性表的结点数据大小，按顺序将数据插入原线性表的方法重构链表。输入/输出设计简要描述：从键盘输入若干整数数据，以回

3、车作为输入结束标志，将输入数据按从小到大顺序排序好后输出。当输入好两个线性表的数据时，回车显示归并后的线性表数据。输出各结点的整数值时，每个整数采用6列字符域宽。输入与输出有文字提示。编程语言说明：使用VisualC++编程。主要代码采用C语言实现；动态存储分配采用C的malloc和free操作符实现；输入与输出采用C++的cin和cout流；程序注释采用C/C++规范。主要函数说明：voidInitList(SqList&L);//输入若干整数，建立带附加头结点的单向顺序存储链表voidShowList(SqLi

4、st&L)//显示线性表中的所有元素SqListUnionList(SqList&L1,SqList&L2)//按从小到大的顺序归并两个顺序存储的链表voidSortList(SqList&L)//线性表元素排序LinkList*CreateList()//输入若干整数，建立带附加头结点的单向链式存储链表SqListMergeList(SqListL1,SqListL2)//按从小到大顺序归并两个链式存储的有序链表程序测试简要报告：·测试实例1结论程序输出结果与期望输出结果相符。·测试实例2结论程序输出结果与期望输

5、出结果相符。·测试实例3结论程序输出结果与期望输出结果相符。源程序代码：//试验1_1.cpp:顺序存储结构实现两个有序链表的归并#include"stdafx.h"#include#includeusingnamespacestd;#defineN1000//线性表大小#defineLIST_SIZE1000//线性表最大长度typedefstruct{intp[N];intlength;intlist_size;}SqList;voidInitList(SqList&L){

6、//初始化线性表cout<<"输入线性表数据：";inttemp;L.length=0;//初始化线性表实际长度为0L.list_size=LIST_SIZE;//初始化线性表最大长度while(1){cin>>temp;charc=getchar();L.p[L.length++]=temp;if(c=='')break;//输入回车结束数据输入}}voidShowList(SqList&L){//显示线性表中的所有元素for(inti=0;i

7、(4);}cout<

8、i=0,j=0,k=0;while(k