《线性表的顺序存储结构实验报告样例》由会员分享，可在线阅读，更多相关《线性表的顺序存储结构实验报告样例（11页珍藏版）》请在金锄头文库上搜索。
1、 年南昌航空大学实验报告（用实验报告纸，手写）课程名称： 数据结构 实验名称： 实验一 线性表的顺序存储结构 班 级： 080611 学生姓名： 赖凌 学号： 08061101 指导教师评定： 签 名: 题目：有两张非递减有序的线性学生表A，B，采用顺序存储结构，两张表合并用c表存，要求C仍为非递减有序的，并删除C中值相同的表。一、需求分析 本演示程序根据已有的6位学生的信息，实现两张表的合并及删除值相同元素的操作，不需要用户重新输入学生的信息。 在演示过程序中，用户敲击键盘，即可观看演示结果。 程序执行的命令包括：（1）构造线性表A （2）构造线性表B （3）求两张表的并 （4）删除C中值相
2、同的元素二、概要设计 为实现上述算法，需要线性表的抽象数据类型：ADT Stack 数据对象：D=ai:|aiElemSet,i=1n,n0数据关系：R1=|ai-1,aiD,i=2,n0基本操作:init(list *L)操作结果：构造一个空的线性表L。ListLength(List *L)初始条件：线性表L已经存在操作结果：返回L中数据元素的个数。 GetElem(List L, int i, ElemType *e)初始条件：线性表L已经存在，1iListLength(&L)操作结果：用e返回L中第i个数据元素的值。EqualList(ElemType *e1,ElemType *e2)
3、初始条件：数据元素e1,e2存在操作结果：以e1,e2中的姓名项作为判定e1,e2是否相等的依据。Less_EquaList(ElemType *e1,ElemType *e2)初始条件：数据元素e1,e2存在操作结果：以e1,e2中的姓名项(为字符串)的来判定e1,e2是否有的关系。LocateElem(List *La,ElemType e,int type)初始条件：线性表La已经存在操作结果：判断La中是否有与e相同的元素。MergeList(List *La,List *Lb,List *Lc)初始条件：非递减线性表La，Lb已经存在操作结果：合并La，Lb得到Lc，Lc仍按非递减有
4、序排列。UnionList(List *La ,List *Lb)初始条件：线性表La，Lb已经存在操作结果：将所有在Lb而不在La中的元素插入到La中表尾的位置。PrintList(List L)初始条件：线性表L已经存在操作结果：打印出表L。ListInsert(List *L, int i, struct STU e)初始条件：线性表L已经存在，1iListLength(&L)+1操作结果：在表L中第i个位置前插入元素e，L的长度加1。 ADT List2. 本程序有三个模块： 主程序模块void main()初始化；接受命令；显示结果； 线性表单元模块：实现线性表抽象数据类型； 结点结
5、构单元模块：定义线性表中的结点结构。三、详细设计元素类型，结点类型struct STUchar name20; /学生名字、学号、年龄、分数char stuno10;int age;int score;typedef struct STU ElemType; /元素类型struct LISTElemType *elem;int length; /表的长度、大小int listsize;typedef struct LIST list; /结点类型2.对抽象数据类型中的部分基本操作的伪码算法如下：int init(List *L)Lelem=(ElemType *)malloc(sizeof(E
6、lemType)*LIST_INIT_SIZE);If(!Lelem) exit (OVERFLOW);Llength=0;Llistsize= LIST_INIT_SIZE;Return OK;/初始化表int ListLength(List *L)return Llength;/返回表长void GetElem(List L, int i, ElemType *e)*e=L.elemi; /返回元素int locateElem(List *La, ElemType e, int type)int I;switch(type) /确定元素在表中的位置case EQVAL;for(i=0;iL
7、alength;i+)if(EqualList(&Laelemi,&e)return 1;break;default;break;return 0;void MergeList(List *La, List *Lb, List *Lc) /将两个表合并成LcElemType *pa,*pb,*pc,*pa_last,*pb_last;Pa=Laelem;pb=Lbelem; LcListsize=Lclength=Lalength+Lblength;Pc=Lcelem=(ElemType *)malloc(Lclistsize*sizeof(ElemType);if (!Lcelem) exi
8、t(OVERFLOW);pa_last=Laelem+Lalength-1;pb_last=Lbelem+Lblength-1;while (pa=pa_last&pb=pb_last)if (Less_EqualList(pa,pb) *pc+=*pa+;else *pc+=*pb+;while (pa=pa_last) *pc+=*pa+;while (pb=pb_last) *pc+=*pb+;void UnionList(List *La, List *Lb)La_len=ListLength(La);Lb_len=ListLength(Lb);For(i=0;iLb_len;i+)G
9、etElem(*Lb,i,&e);If (!LocateElem(La,e,EQUAL)ListInsert(La,+La_len,e);int ListInset(List *L,int i,struct STU e) /将元素插入表中if(iLlength+1) return ERROR; q=&(Lelemi-1);for(p=LelemLlength-1;p=q;p-)*(p+1)=*p;*q=e;+(Llength);return OK;/ListInsert Before i3.主函数和其他函数的伪码算法void main()Initialization();/初始化ReadCom
10、mand(cmd);/读入一个操作符MakeList(La);printList(La);/产生并打印LaMakeList(Lb);printList(Lb);/ 产生并打印LbOperateList(La,Lb);void Initialization()/系统初始化clrscr();int ReadCommand(cmd)/任意键入一个字符cmd=getch();return 1;void MakeList(La)ListInsert(&La,i,e);void OperateList(La,Lb)MergeList(&La,&Lb,&Lc);UnionList(&La,&Lb);4 函数
11、调用关系mainInitialization MakeList OperateList ReadCommand printList UnionList MergeListLess_EqualListInit ListInsert LocateElemEqualList四、调试分析 刚开始输入时，漏掉了一些变量参数的标记&，有的则错加了&，使得程序运行出来的结果不正确，使调试程序时费时不少。 程序采用逐个输入的方法创建La,Lb,在元素较多时，会使得程序很庞大，不利于检查错误等。 算法的时空分析各操作的算法时间复杂度比较合理init,ListLength,GetElem,EqualList,Le
12、ss_EqualList为O(1)LocateElem,ListInsert,printList为O(n),UnionList为O(mn),MergeList为O(n)。4.本次实验采用数据抽象的程序设计方法，将程序化为三层次结构，设计时思路清晰，使调试也较顺利，各模块有较好的可重用性。五、用户手册 本程序的运行环境为windows xp操作系统，执行文件为Exp1Prb1.c； 进入演示程序后，完成编译，连接（即同时按下Ctrl F9）进入演示界面，用户键入任一符号，都能看完整个演示过程。六、测试结果(1)同时键入Ctrl F9，演示为：-List Demo is running-First
13、 is InsertList functionname stunoagescorestu1100001801000stu3100002801000(2)键入任意字符，演示为：name stunoagescorestu1100001801000stu3100002801000stu5100003801000List A length now is 3.(3)键入任意字符，演示为：name stunoagescorestu2100001801000stu4100002801000stu6100001801000List B length now is 3.(4)键入任意字符，演示为：name stunoagescorestu
