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

南昌航空大学实验报告课程名称:班级：据结构XXX指导教师评定：课程名称:班级：据结构XXX指导教师评定：XXX实验名称：实验一线性表的顺序存储结构学生姓名：XXX学号：XXXXX签名:XXX设计并实现以下算法：有两张非递增有序的线性表A，B，采用顺序存储结构，两张表合并用C表存，要求C仍为非递增有序的，并删除C表中值相同的多余元素。一、需求分析本程序中，要求输入到表A,B中的元素是整形的，并且要按非递增顺序输入，否则系统会给出“出错信息”。输出结果应该是一个不含有重复元素的非递增的表。本程序以用户和计算机的对话方式执行，即在计算机演示界面上显示“提示信息”后，由用户在键盘上输入相应的信息；相应的输入数据和运算结果显示在其后。程序执行的命令包括：构造线性表A(2)构造线性表B(3)检验表A,B是否非递减有序(4)求表A与B的合并(5)删除表中值相同的多余元素(6)结束。测试数据(1)A=12（2）A=95-2（2）A=95-2B=100-1-3-5-10二、概要设计需要线性表的抽象数据类型:为实现上述算法，ADTStack{数据对象：D={a.:|a.EElemSet,i=1・・・n,nN0}数据关系：R1={<ai-1，ai>|ai-1，aiGD,i=2,…出基本操作：需要线性表的抽象数据类型: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仍按非递增有序排列。DeleteSame(List*L)初始条件：非递增线性表L已经存在操作结果：删除了匚中值相同的元素。PrintList(ListL)初始条件：线性表L已经存在操作结果：打印出表L。}ADTList本程序有三个模块：⑴主程序模块voidmain(){初始化；do{接受命令；显示结果；}while(执行完毕)}⑵线性表单元模块：实现线性表抽象数据类型；⑶结点结构单元模块：定义线性表中的结点结构。三、详细设计元素类型，结点类型typedefintElemType;//元素类型structLIST{ElemType*elem;intlength;intlistsize;}；typedefstructLISTlist;//结点类型对抽象数据类型中的部分基本操作的伪码算法如下：intinit(List*L){//初始化表LL^elem=(ElemType*)malloc(sizeof(ElemType)*LIST_INIT_SIZE);//为线性表顺序结构分配空间If(!L—elem)exit(ERROR);Lflength=0;L—listsize=LIST_INIT_SIZE;ReturnOK;}//initListvoidInputList(List*L){//构造表Lintflag=-32768;//输入结束的标志scanf("%d”,&n);//输入元素while(n!=flag){//继续输入Lfelem[j++]=n;Lflength=j;Scanf("%d”,&n);}}//InputListvoidCheckList(List*L){for(i=0;i<L^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=Lafelem;pb=Lbfelem;//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++)if(L^elem[i]!=L^elem[j])L^elem[++j]=L^elem[i];//前后不等时i,j均往后移。L—length=++j;}主函数和其他函数的伪码算法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);

4函数调用关系mainInitializationOperateListInputDeleteSameprintlistMergeListCheckListInputList四、调试分析由于对指针部分的C语言成分有所淡忘，导致一些变量的〃&〃，〃*〃使用混乱，使调试费时不少。比如MergeList函数中有if(*pa<=*pb),一开始写成7if(pa<=pb)，结束程序运行结果不正确。4函数调用关系mainInitializationOperateListInput输入时，元素间隔应为空格。一开始调试用的是〃，〃，使程序无法运行。因此应注意输入的格式。本程序模块划分合格，使各部分基本独立，因而具有较高的可重用性。算法的时空分析各操作的算法时间复杂度比较合理其中init为O(1),InputList,CheckList,MergeList,DeleteSame,printlist为O(n)。本次实验采用数据抽象的程序设计方法，将程序化为三层次结构：元素结点、线性顺序表、主控模块，使得设计时思路清晰，使调试也较顺利，各模块有较好的可重用性，受到了一次良好的程序设计训练。五、用户手册本程序的运行环境为windows98操作系统，执行文件为Exp1Wsh2.c；进入演示程序后，完成编译，连接(即同时按下CtrlF9)进入演示界面：根据提示信息，用户输入数据(整型)，以-32768为输入结束的标志。输入完毕(两张表)后，用户只需键入回车键，就能观看操作结果了。六、测试结果同时键入CtrlF9,进入用户界面，屏幕上出现：NowinputthelistofA:输入：1_2__3__-32768，键入回车键，屏幕上出现：Yourinputiswrong.Pleasetryagain:输入：9__5__0__-2__-32768，回车，出现：50-2回车，出现：NowinputtheListofB:(4)输入：10_5_0_-1_-3_-5_-10，回车，出现：50-1-3-5-10(5)回车，出现：NowmergetheListAandB:10955(6)回车，出现：0-1-2-3-5-10NowdeletethesameelementsinListC:-110950-1(7)回车，退出用户界面-2-3-5-10返回编辑状态。七、附录：源程序//头文件#include<stdio.h>#include<malloc.h>#include<conio.h>〃符号常量#defineERRORO#defineOK1#defineOVERFLOW-1#defineLIST_INIT_SIZE100//线性表存储空间的初始分配量#defineLISTINCREMENT10//线性表存储空间的分配增量typedefintElemType;〃类型声明typedefstructLIST{ElemType*elem;intlength;intlistsize;}List;intinit(List*L);//初始化，创建一张空表voidInputList(List*L);//A工输入一张表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");getch();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)inti;for(i=0;i<L->length-1;i++)if(L->elem[i]<L->elem[i+1]){printf("Yourinputiswrong.Pleasetryagain:\n");InputList(L);//重新输入表匚i=0;}}voidMergeList(List*La,List*Lb,List*Lc){ElemType*pa,*pb,*pc,*pa_last,*pb_last;pa=La->elem;pb=Lb->elem;Lc->length=La->length+Lb->length;Lc->listsize=La->length+Lb->length;Lc->elem=(ElemType*)malloc(Lc->listsize*sizeof(ElemType));pc=Lc->elem;pa_last=La-〉elem+La-〉lengthT;//La最后一个元素的地址pb_last=Lb-〉elem+Lb-〉lengthT;//Lb最后一个元素的地址while(pa<=pa_last&&pb<=pb_last){//表La,Lb都还未操作完时if(*pa<=*pb)*pc++=*pb++;//将较大者插入Lc中，从而Lc为非递增有序else*pc++=*pa++;}while(pa<=pa_la