数据结构实验报告一

数据结构实验报告一数据结构实验报告一全文共6页，当前为第1页。数据结构实验报告一数据结构实验报告一全文共6页，当前为第1页。

数据结构实验报告

评分满分——5分学号：20XX111990姓名：陶瑜专业：计算机科学与技术知识范畴：线性表完成日期：20XX年03月19日实验题目：两个有序线性表的归并算法实验内容及要求：

从键盘输入数据，建立两个有序线性表(每个线性表的输入数据按小到大次序输入来建立线性表，不必考虑排序算法)；输出建好的这两个有序线性表；将这两个有序线性表归并为一个有序线性表；输出归并后的有序线性表。

从键盘实现数据输入与输出的格式自拟；要求完成两个同样功能的程序，一个程序采用顺序存储结构，另一个程序采用链表实现线性表的存储。其中链表实现时，要求利用两个升序链表的结点实现归并，即归并时不能新建结点，归并后原来两个升序链表的存储空间不在存在。实验目的：掌握两个有序线性表的归并算法。

数据结构设计简要描述：采用带附加头结点方式建立单向链表；每个结点包括整型类型的数据域和一个指针域。第一个程序以数组的形式建立单向顺序存储的线性表，第二个程序以指针的形式建立链式存储的线性表。

算法设计简要描述：线性表排序采用比较大小交换位置数据结构实验报告一全文共6页，当前为第2页。的算法实现；线性表的归并采用先比较两个线性表的结点数据大小，按顺序将数据插入原线性表的方法重构链表。

输入/输出设计简要描述：从键盘输入若干整数数据，以回车作为输入结束标志，将输入数据按从小到大顺序排序好后输出。当输入好两个线性表的数据时，回车显示归并后的线性表数据。输出各结点的整数值时，每个整数采用6列字符域宽。输入与输出有文字提示。

编程语言说明：使用VisualC++编程。主要代码采用C语言实现；动态存储分配采用C的malloc和free操作符实现；输入与输出采用C++的cin和cout流；程序注释采用C/C++规范。

主要函数说明：

voidInitList(SqList&L);//输入若干整数，建立带附加头结点的单向顺序存储链表voidShowList(SqList&L)//显示线性表中的所有元素

SqListUnionList(SqList&L1,SqList&L2)//按从小到大的顺序归并两个顺序存储的链表voidSortList(SqList&L)//线性表元素排序

LinkList*CreateList//输入若干整数，建立带附加头结点的单向链式存储链表SqListMergeList(SqListL1,SqListL2)//按从小到大顺序归并两个链式存储的有序链表

数据结构实验报告一全文共6页，当前为第3页。程序测试简要报告：测试实例1

1/7

结论程序输出结果与期望输出结果相符。测试实例2

结论程序输出结果与期望输出结果相符。测试实例3

结论程序输出结果与期望输出结果相符。

源程序代码：//试验1_:顺序存储结构实现两个有序链表的归并#include\#include#includeusingnamespacestd;

#defineN1000//线性表大小

#defineLIST_SIZE1000//线性表最大长度

typedefstruct{

intp[N];intlength;intlist_size;

2/7

}SqList;

voidInitList(SqList&L){//初始化线性表}

voidShowList(SqList&L){//显示线性表中的所有元素}

SqListUnionList(SqList&L1,SqList&L2){//按从小到大的顺序组合两个线性表

SqListL3;

_size=LIST_SIZE;//初始化线性表最大长度

数据结构实验报告一全文共6页，当前为第4页。if(+>temp;charc=getchar;[++]=temp;

if(c=='\\n')break;//输入回车结束数据输入

for(inti=0;i[j]){//交换元素位置，确保小的在前}

intt=[i];[i]=[j];[j]=t;

SqListL1,L2;InitList(L1);SortList(L1);ShowList(L1);InitList(L2);SortList(L2);ShowList(L2);

SqListL3=UnionList(L1,L2);ShowList(L3);system(\

//数据机构实验1_:链式存储结构实现两个有序链表的归并#include\#include#include#include#includeusingnamespacestd;

typedefstructData{

LinkList*CreateList{

//建立单向链表

LinkList*pHead,*pLast,*pTemp;inttemp;

pLast=pHead=(LinkList*)malloc(sizeof(LinkList));cout>temp;//使用temp用来存储用户输入的当前数据pTemp->num=temp;//将temp中的数据存入数据节点中intnum;Data*next;

}LinkList,*SqList;

数据结构实验报告一全文共6页，当前为第5页。pLast->next=pTemp;//指针指向下一节点pLast=pTemp;}

voidShowList(LinkList*pHead){

//显示链表中的素有数据

LinkList*p=pHead->next;//定义p指针来从头到位读取链表中的数据while(p){

5/7

}

charc=getchar;

if(c=='\\n')break;//调用getchar函数来获取用户输入的回车键，结束输入

pLast->next=NULL;returnpHead;

}

}

coutnext;

coutnext;while(q){}

returnL1;

6/7

//对链表中所有数据按从小到大顺序排列LinkList*p1,*p2;p1=pHead->next;

for(;p1->next;p1=p1->next){}

for(p2=p1->next;p2;p2=p2->next){}

数据结构实验报告一全文共6页，当前为第6页。if(p1->num>p2->num){}

intt=p1->num;p2->num=t;p1->num=p2->num;

pr=L1;p=L1->next;s=q;q=q->next;

while(p&&p->numnum){//判断p非空，且p指针指向的数据小于s指针指向}

s->next=p;pr->next=s;

pr=p;p=p->next;

的数据，执行while循环

}

voidmain{LinkList*pHead1,*pHead2,*pHead3;pHead1=CreateList;SortList(pHead1);ShowList(pHead1);pHead2=CreateList;SortList(pHead2);ShowList(pHead2);

pHead3=Me