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

1南昌航空大学实验报告课程名称：数据结构实验名称：实验一线性表的顺序存储结构班级：XXX学生姓名：XXX学号：XXXXX指导教师评定：XXX签名:XXX设计并实现以下算法：有两张非递增有序的线性表A，B，采用顺序存储结构，两张表合并用C表存，要求C仍为非递增有序的，并删除C表中值相同的多余元素。一、需求分析⒈本程序中，要求输入到表A,B中的元素是整形的，并且要按非递增顺序输入，否则系统会给出“出错信息”。输出结果应该是一个不含有重复元素的非递增的表。⒉本程序以用户和计算机的对话方式执行，即在计算机演示界面上显示“提示信息”后，由用户在键盘上输入相应的信息；相应的输入数据和运算结果显示在其后。⒊程序执行的命令包括：（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:|ai∈ElemSet,i=1…n,n≥0}数据关系：R1={ai-1,ai|ai-1,ai∈D,i=2,…n}基本操作:init(list*L)操作结果：构造一个空的线性表L。InputList(List*L)初始条件：线性表L已经存在操作结果：人工输入了一张表。CheckList(List*L)初始条件：线性表L已经存在操作结果：判断L是否非递增有序，若为否，则重新输入。MergeList(List*La,List*Lb,List*Lc)初始条件：非递增线性表La，Lb已经存在操作结果：合并La，Lb得到Lc，Lc仍按非递增有序排列。2DeleteSame(List*L)初始条件：非递增线性表L已经存在操作结果：删除了L中值相同的元素。PrintList(ListL)初始条件：线性表L已经存在操作结果：打印出表L。}ADTList2.本程序有三个模块：⑴主程序模块voidmain(){初始化；do{接受命令；显示结果；｝while(执行完毕)｝⑵线性表单元模块：实现线性表抽象数据类型；⑶结点结构单元模块：定义线性表中的结点结构。三、详细设计⒈元素类型，结点类型typedefintElemType;//元素类型structLIST{ElemType*elem;intlength;intlistsize;};typedefstructLISTlist;//结点类型2.对抽象数据类型中的部分基本操作的伪码算法如下：intinit(List*L){//初始化表LL→elem=(ElemType*)malloc(sizeof(ElemType)*LIST_INIT_SIZE);//为线性表顺序结构分配空间If(!L→elem)exit(ERROR);L→length=0;L→listsize=LIST_INIT_SIZE;ReturnOK;}//initListvoidInputList(List*L){//构造表Ｌ3intflag=-32768;//输入结束的标志scanf(%d,&n);//输入元素while(n!=flag){//继续输入L→elem[j++]=n;L→length=j;Scanf(%d,&n);}}//InputListvoidCheckList(List*L){for(i=0;iL→length-1;i++){if(L→elem[i]L→elem[i+1])InputList(L);//输入为递增时，要重新输入i=0;}}//CheckListvoidMergeList(List*La,List*Lb,List*Lc){//表La和Lb合并为LcPa=La→elem;pb=Lb→elem;//pa,pb分别指向La,Lb的第一个元素Lc→Listsize=La→length+Lb→length;Lc→elem==(ElemType*)malloc(Lc→listsize*sizeof(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++;//将Lb的剩余部分接到Lc}//MergeListvoidDeleteSame(List*L){//删除表中相同的元素intj=0;for(i=1;i=L→length-1;i++)4if(L→elem[i]!=L→elem[j])L→elem[++j]=L→elem[i];//前后不等时i,j均往后移。L→length=++j;}3.主函数和其他函数的伪码算法voidmain(){Initialization();//初始化do{input(ListL);//输入一个线性表LOperate(ListL);//对表进行操作}while(未执行DeleteSame)}//mainvoidInitialization(){clrscr();//清屏屏幕出现提示信息；nowinputthelistofA:}//InitializationvoidInput(ListL){//输入线性表Ldo{L=getch();}while(L!=-32768);}//InputvoidOperate(ListL){//对刚输入的表L进行操作do{CheckList(La);InputList(La);}while(La不是非递增有序的);printlist(La);do{CheckList(La);InputList(La);}while(Lb不是非递增有序的);printlist(Lb);MergeList(La,Lb,Lc);DeleteSame(Lc);printlist(Lc);}54函数调用关系mainInitializationOperateListInputDeleteSameprintlistMergeListCheckListInputList四、调试分析⒈由于对指针部分的C语言成分有所淡忘，导致一些变量的&，*使用混乱，使调试费时不少。比如MergeList函数中有if(*pa=*pb)，一开始写成了if(pa=pb)，结束程序运行结果不正确。⒉输入时，元素间隔应为空格。一开始调试用的是，，使程序无法运行。因此应注意输入的格式。3.本程序模块划分合格，使各部分基本独立，因而具有较高的可重用性。4.算法的时空分析各操作的算法时间复杂度比较合理其中init为O(1),InputList,CheckList,MergeList,DeleteSame,printlist为O(n)。5.本次实验采用数据抽象的程序设计方法，将程序化为三层次结构：元素结点、线性顺序表、主控模块，使得设计时思路清晰，使调试也较顺利，各模块有较好的可重用性，受到了一次良好的程序设计训练。五、用户手册⒈本程序的运行环境为windows98操作系统，执行文件为Exp1Wsh2.c；⒉进入演示程序后，完成编译，连接（即同时按下CtrlF9）进入演示界面：根据提示信息，用户输入数据（整型），以-32768为输入结束的标志。4.输入完毕（两张表）后，用户只需键入回车键，就能观看操作结果了。六、测试结果(1)同时键入CtrlF9，进入用户界面，屏幕上出现：NowinputthelistofA:(2)输入：1__2__3__-32768,键入回车键，屏幕上出现：Yourinputiswrong.Pleasetryagain:(3)输入：9__5__0__-2__-32768，回车，出现：950-2回车，出现：NowinputtheListofB:(4)输入：10__5__0__-1__-3__-5__-10，回车，出现：1050-1-3-5-10(5)回车，出现：6NowmergetheListAandB:1095500-1-2-3-5-10(6)回车，出现：NowdeletethesameelementsinListC:10950-1-2-3-5-10(7)回车，退出用户界面，返回编辑状态。七、附录：源程序//------头文件#includestdio.h#includemalloc.h#includeconio.h//符号常量#defineERRORO#defineOK1#defineOVERFLOW-1#defineLIST_INIT_SIZE100//线性表存储空间的初始分配量#defineLISTINCREMENT10//线性表存储空间的分配增量typedefintElemType;//类型声明typedefstructLIST{ElemType*elem;intlength;intlistsize;}List;intinit(List*L);//初始化，创建一张空表voidInputList(List*L);//人工输入一张表LvoidCheckList(List*L);//检验表L是否是非递增有序的voidMergeList(List*La,List*Lb,List*Lc);//合并La,Lb，用Lc存储voidDeleteSame(List*L);//删除L中值相同的元素voidprintlist(List*L);//打印表Lmain(){ListLa,Lb,Lc;//定义结构体变量，即表La,Lb,Lcinit(&La);init(&Lb);init(&Lc);printf(NowpleaseinputtheListofA:\n);InputList(&La);CheckList(&La);printf(\n);printlist(&La);printf(\n);7getch();printf(NowpleaseinputtheListofB:\n);InputList(&Lb);CheckList(&Lb);printf(\n);printlist(&Lb);printf(\n);getch();printf(NowMergetheListofAandB:\n);MergeList(&La,&Lb,&Lc);printlist(&Lc);printf(\n\n);getch();printf(NowdeletethesameelementsinListC:\n\n);DeleteSame(&Lc);printlist(&Lc);getch();}intinit(List*L){//构造一个空的线性表L-elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L-elem)exit(OVERFLOW);//存储分配失败L-length=0;//空表长度为0L-listsize=LIST_INIT_SIZE;//初始存储容量returnOK;}voidInputList(List*L){intn,j=0;intflag=-32768;//输入结束标志scanf(%d,&n);while(n!=flag){L-elem[j++]=n;L-length=j;scanf(%d,&n);}}voidCheckList(List*L)8{inti;for(i=0;iL-length-1;i++)if(L-elem[i]L-elem[i+1]){printf(Yourinputiswrong.Pleasetryagain:\n);InputList(L);//重新输入表Li=0