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

《西南交大赵宏宇数据结构实验报告线性表》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

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

2、存储。其中链表实现时，要求利用两个升序链表的结点实现归并，即归并时不能新建结点，归并后原来两个升序链表的存储空间不在存在。实验目的：掌握两个有序线性表的归并算法。数据结构设计简要描述：顺序存储结构使用结构体，结构体中带有数组以及数组的最大存储空间。链式存储结构同样使用结构体定义结点，用带附加头结点单向链表，每个结点包括整型或浮型类型的数据域和一个指针域。算法设计简要描述：顺序与链式两种存储均为依次互相比较两线性表中值的大小。顺序存储是新申请存储空间将数据依次存入静态数组中，链式存储是利用原有空间将结点按照

3、数据大小进行重新连接。输入/输出设计简要描述：从键盘以从小到大的顺序输入以空格(或CR或TAB)分隔的若干不等于0的整数，直到输入0时停止输入，按整数输入次序建立结点并顺序连接结点。编程语言说明：使用VisualC++和C编程。顺序表结构部分采用C语言实现；各函数使用的是C语言的编写规范，输出与输入使用的是printf和scanf；链式表结构部分使用的是C++语言；输入和输出分别采用cin和cout;注释采用C/C++规范。主要函数说明：LinkListcrt()//创建链表voidMergeList(L

4、inkList&La,LinkList&Lb,LinkList&Lc)//归并算法排序voidprt(LinkListh)//输出存储的元素程序测试简要报告：测试1：9/9测试2：源程序代码：1.顺序存储：#include"stdafx.h"#include#defineMAX_N10typedefstruct{intelem[MAX_N];intn;intmaxsize;}SqList;voidinitiate(SqList*pL){inta;pL->n=0;pL->maxsize=M

5、AX_N;while(1){scanf("%d",&a);if(a==0

6、

7、pL->n>=MAX_N)break;pL->elem[pL->n++]=a;}}intmerge(SqList*a,SqList*b,SqList*c)9/9{if(a->n+b->n>c->n)return-1;inti=0;intj=0;intk=0;c->n=a->n+b->n;while(in&&jn){if((a->elem[i]elem[j]))c->elem[k++]=a->elem[i++

8、];elsec->elem[k++]=b->elem[j++];}while(in)c->elem[k++]=a->elem[i++];while(jn)c->elem[k++]=b->elem[j++];return0;}voidoutput(SqList*pL){for(inti=0;in;i++){printf("%3d",pL->elem[i]);}printf("");}intmain(){SqLista,b,c;initiate(&a);initiate(&b);

9、c.n=MAX_N;merge(&a,&b,&c);output(&c);return0;}2.链表：#include#include9/9#includetypedefintElemType;typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;#defineCreateNode(p)p=(LinkList)malloc(sizeof(LNode))#defineDel

10、eteNode(p)free((void*)(p))LinkListcrt(){LinkListp,last,h;CreateNode(h);last=h;inte;while(1){scanf("%d",&e);if(e==0)break;CreateNode(p);p->data=e;last->next=p;last=p;}last->next=NULL;returnh;}voidprt(LinkListh){LinkL