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

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=9 5 0 -2B=1050-1-3-5 -10二、概要设计 为实现上述算法，需要线性表的抽象数据类型：ADT Stack 数据对象：D=ai:|aiElemSet,i=1n,n0数据关系：R1=|ai-1,aiD,i=2,n基本操作:init(list *L)操作结果：构造一个空的线性表L。InputList(List *L)初始条件：线性表L已经存在操作结果：人工输

3、入了一张表。 CheckList(List *L)初始条件：线性表L已经存在操作结果：判断L是否非递增有序，若为否，则重新输入。MergeList(List *La,List *Lb,List *Lc)初始条件：非递增线性表La，Lb已经存在操作结果：合并La，Lb得到Lc，Lc仍按非递增有序排列。DeleteSame(List *L)初始条件：非递增线性表L已经存在操作结果：删除了L中值相同的元素。PrintList(List L)初始条件：线性表L已经存在操作结果：打印出表L。ADT List2. 本程序有三个模块： 主程序模块void main()初始化；do接受命令；显示结果；whil

4、e(执行完毕) 线性表单元模块：实现线性表抽象数据类型； 结点结构单元模块：定义线性表中的结点结构。三、详细设计元素类型，结点类型typedef int ElemType; /元素类型struct LISTElemType *elem;int length;int listsize;typedef struct LIST list; /结点类型2.对抽象数据类型中的部分基本操作的伪码算法如下：int init(List *L) /初始化表LLelem=(ElemType *)malloc(sizeof(ElemType)*LIST_INIT_SIZE);/为线性表顺序结构分配空间If(!Lel

5、em) exit (ERROR);Llength=0;Llistsize= LIST_INIT_SIZE; Return OK;/init Listvoid InputList(List *L) /构造表int flag=-32768;/输入结束的标志scanf(%d,&n); /输入元素while(n!=flag)/继续输入Lelemj+=n;Llength=j;Scanf(%d,&n);/InputListvoid CheckList(List *L) for (i=0;iLlength-1;i+)if (LelemiLelemi+1)InputList(L);/输入为递增时，要重新输入i

6、=0;/CheckListvoid MergeList(List *La, List *Lb, List *Lc) /表La和Lb合并为LcPa=Laelem;pb=Lbelem;/pa,pb分别指向La,Lb的第一个元素LcListsize= Lalength+Lblength;Lcelem=(ElemType *)malloc(Lclistsize*sizeof(ElemType);pc=Lcelem;/pc指向表Lc的第一个元素pa_last=Laelem+Lalength-1;/表La最后一个元素的地址pb_last=Lbelem+Lblength-1;/ 表Lb最后一个元素的地址wh

7、ile (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/MergeListvoid DeleteSame(List *L) /删除表中相同的元素int j=0;for(i=1;i=Llength-1;i+)if(Lelemi!=Lelemj) Lelem+j=Lelemi;/前后不等时i,j均往后移。Llength=+j;3.主

8、函数和其他函数的伪码算法void main()Initialization();/初始化do input (List L);/输入一个线性表LOperate(List L);/对表进行操作while (未执行DeleteSame)/mainvoid Initialization()clrscr();/清屏屏幕出现提示信息；now input the list of A:/ Initializationvoid Input(List L)/输入线性表LdoL=getch();while(L!=-32768);/Inputvoid Operate(List L)/对刚输入的表L进行操作doChec

9、kList(La);InputList(La); while(La不是非递增有序的);printlist(La);doCheckList(La);InputList(La); while(Lb不是非递增有序的);printlist(Lb);MergeList(La,Lb,Lc);DeleteSame(Lc);printlist(Lc);4 函数调用关系mainInitialization OperateList Input DeleteSame printlist MergeList CheckList InputList四、调试分析 由于对指针部分的C语言成分有所淡忘，导致一些变量的&，*使

10、用混乱，使调试费时不少。比如MergeList函数中有if(*pa=*pb)，一开始写成了if(pa=pb)，结束程序运行结果不正确。输入时，元素间隔应为空格。一开始调试用的是，使程序无法运行。因此应注意输入的格式。3.本程序模块划分合格，使各部分基本独立，因而具有较高的可重用性。4. 算法的时空分析各操作的算法时间复杂度比较合理其中init为O(1),InputList,CheckList,MergeList,DeleteSame,printlist为O(n)。5.本次实验采用数据抽象的程序设计方法，将程序化为三层次结构：元素结点、线性顺序表、主控模块，使得设计时思路清晰，使调试也较顺利，各

11、模块有较好的可重用性，受到了一次良好的程序设计训练。五、用户手册 本程序的运行环境为windows 98操作系统，执行文件为Exp1Wsh2.c； 进入演示程序后，完成编译，连接（即同时按下Ctrl F9）进入演示界面：根据提示信息，用户输入数据（整型），以-32768为输入结束的标志。4.输入完毕（两张表）后，用户只需键入回车键，就能观看操作结果了。六、测试结果(1)同时键入Ctrl F9，进入用户界面，屏幕上出现：Now input the list of A:(2)输入：1_2_3_-32768,键入回车键，屏幕上出现：Your input is wrong.Please try aga

12、in:(3)输入：9_5_0_-2_-32768，回车，出现：950-2回车，出现：Now input the List of B: (4)输入：10_5_0_-1_-3_-5_-10，回车，出现：1050-1-3-5-10(5) 回车，出现：Now merge the List A and B:1095500-1-2-3-5-10(6) 回车，出现：Now delete the same elements in List C:10950-1-2-3-5-10(7) 回车，退出用户界面，返回编辑状态。七、附录：源程序/-头文件#include#include#include/符号常量#defi

13、ne ERROR O#define OK 1#define OVERFLOW -1#define LIST_INIT_SIZE 100/线性表存储空间的初始分配量#define LISTINCREMENT 10/线性表存储空间的分配增量typedef int ElemType;/类型声明typedef struct LIST ElemType *elem;int length;int listsize; List;int init(List *L);/初始化，创建一张空表void InputList(List *L);/人工输入一张表Lvoid CheckList(List *L);/检验表L

14、是否是非递增有序的void MergeList(List *La,List *Lb,List *Lc);/合并La,Lb，用Lc存储void DeleteSame(List *L);/删除L中值相同的元素void printlist(List *L);/打印表Lmain()List La,Lb,Lc;/定义结构体变量，即表La,Lb,Lcinit(&La); init(&Lb); init(&Lc);printf(Now please input the List of A:n );InputList(&La);CheckList(&La); printf(n);printlist(&La);

15、 printf(n);getch();printf(Now please input the List of B:n );InputList(&Lb);CheckList(&Lb); printf(n);printlist(&Lb); printf(n);getch();printf(Now Merge the List of A and B:n );MergeList(&La,&Lb,&Lc);printlist(&Lc); printf(n n);getch();printf(Now delete the same elements in List C:nn );DeleteSame(&L

16、c);printlist(&Lc);getch();int init(List *L)/构造一个空的线性表L-elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType);if(!L-elem) exit(OVERFLOW);/ 存储分配失败L-length=0;/空表长度为0L-listsize=LIST_INIT_SIZE;/初始存储容量return OK;void InputList(List *L)int n,j=0;int flag=-32768;/输入结束标志scanf(%d ,&n);while(n!=flag)L-elemj+=

17、n;L-length=j;scanf(%d ,&n);void CheckList(List *L)int i;for(i=0;ilength-1;i+)if (L-elemielemi+1)printf(Your input is wrong.Please try again:n );InputList(L);/重新输入表Li=0;void MergeList(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-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+;/将较大者插入Lc中，从而Lc为非递增有序els