线性表的顺序存储结构实验报告.doc

《线性表的顺序存储结构实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、南昌航空大学实验报告课程名称：数据结构实验名称：实验一线性表的顺序存储结构班级：XXX学生姓名：XXX学号：XXXXX指导教师评定：XXX签名:XXX设计并实现以下算法：有两张非递增有序的线性表A，B，采用顺序存储结构，两张表合并用C表存，要求C仍为非递增有序的，并删除C表中值相同的多余元素。一、需求分析⒈本程序中，要求输入到表A,B中的元素是整形的，并且要按非递增顺序输入，否则系统会给出“出错信息”。输出结果应该是一个不含有重复元素的非递增的表。⒉本程序以用户和计算机的对话方式执行，即在计算机演示界面上显示“提示信息”后，由用户在键盘上输入相应的信息；相应

2、的输入数据和运算结果显示在其后。⒊程序执行的命令包括：（1）构造线性表A（2）构造线性表B（3）检验表A,B是否非递减有序（4）求表A与B的合并（5）删除表中值相同的多余元素（6）结束。4.测试数据（1）A=123（2）A=950-2B=1050-1-3-5-10二、概要设计⒈为实现上述算法，需要线性表的抽象数据类型：ADTStack{数据对象：D={ai:

3、ai∈ElemSet,i=1…n,n≥0}数据关系：R1={

4、ai-1,ai∈D,i=2,…n}基本操作:init(list*L)操作结果：构造一个空的线性表L。InputList(L

5、ist*L)初始条件：线性表L已经存在操作结果：人工输入了一张表。CheckList(List*L)初始条件：线性表L已经存在操作结果：判断L是否非递增有序，若为否，则重新输入。MergeList(List*La,List*Lb,List*Lc)初始条件：非递增线性表La，Lb已经存在操作结果：合并La，Lb得到Lc，Lc仍按非递增有序排列。9DeleteSame(List*L)初始条件：非递增线性表L已经存在操作结果：删除了L中值相同的元素。PrintList(ListL)初始条件：线性表L已经存在操作结果：打印出表L。}ADTList2.本程序有三个模块

6、：⑴主程序模块voidmain(){初始化；do{接受命令；显示结果；｝while(执行完毕)｝⑵线性表单元模块：实现线性表抽象数据类型；⑶结点结构单元模块：定义线性表中的结点结构。三、详细设计⒈元素类型，结点类型typedefintElemType;//元素类型structLIST{ElemType*elem;intlength;intlistsize;};typedefstructLISTlist;//结点类型2.对抽象数据类型中的部分基本操作的伪码算法如下：intinit(List*L){//初始化表LL→elem=(ElemType*)malloc(

7、sizeof(ElemType)*LIST_INIT_SIZE);//为线性表顺序结构分配空间If(!L→elem)exit(ERROR);L→length=0;L→listsize=LIST_INIT_SIZE;ReturnOK;}//initListvoidInputList(List*L){//构造表Ｌintflag=-32768;//输入结束的标志9scanf("%d",&n);//输入元素while(n!=flag){//继续输入L→elem[j++]=n;L→length=j;Scanf("%d",&n);}}//InputListvoidChe

8、ckList(List*L){for(i=0;i

9、f(ElemType));pc=Lc→elem;//pc指向表Lc的第一个元素pa_last=La→elem+La→length-1;//表La最后一个元素的地址pb_last=Lb→elem+Lb→length-1;//表Lb最后一个元素的地址while(pa<=pa_last&&pb<=pb_last){//表La,Lb都未操作完时if(*pa<=*pb)*pc++=*pb++;else*pc++=*pa++;}while(pa<=pa_last)*pc++=*pa++;//将La的剩余部分接到Lcwhile(pb<=pb_last)*pc++=*pb+

10、+;//将Lb的剩余部分接到Lc}//MergeLi