年南昌航空大学实验报告（用实验报告纸，手写）课程名称：数据结构实验名称：实验一线性表的顺序存储结构班级： 080611 学生姓名：赖凌学号： 08061101 指导教师评定：签名:题目：有两张非递减有序的线性学生表A，B，采用顺序存储结构，两张表合并用c表存，要求C仍为非递减有序的，并删除C中值相同的表。

一、需求分析⒈本演示程序根据已有的6位学生的信息，实现两张表的合并及删除值相同元素的操作，不需要用户重新输入学生的信息。

⒉在演示过程序中，用户敲击键盘，即可观看演示结果。

⒊程序执行的命令包括：（1）构造线性表A （2）构造线性表B （3）求两张表的并（4）删除C中值相同的元素二、概要设计⒈为实现上述算法，需要线性表的抽象数据类型：ADT Stack {数据对象：D={a i:|a i∈ElemSet,i=1…n,n≥0}数据关系：R1={<a i-1,a i>|a i-1,a i∈D,i=2,…n≥0}基本操作:init(list *L)操作结果：构造一个空的线性表L。

ListLength(List *L)初始条件：线性表L已经存在操作结果：返回L中数据元素的个数。

GetElem(List L, int i, ElemType *e)初始条件：线性表L已经存在，1≤i≤ListLength(&L)操作结果：用e返回L中第i个数据元素的值。

EqualList(ElemType *e1,ElemType *e2)初始条件：数据元素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仍按非递减有序排列。

UnionList(List *La ,List *Lb)初始条件：线性表La，Lb已经存在操作结果：将所有在Lb而不在La中的元素插入到La中表尾的位置。

PrintList(List L)初始条件：线性表L已经存在操作结果：打印出表L。

ListInsert(List *L, int i, struct STU e)初始条件：线性表L已经存在，1≤i≤ListLength(&L)+1操作结果：在表L中第i个位置前插入元素e，L的长度加1。

}ADT List2. 本程序有三个模块：⑴主程序模块void main(){初始化；{接受命令；显示结果；｝｝⑵线性表单元模块：实现线性表抽象数据类型；⑶结点结构单元模块：定义线性表中的结点结构。

三、详细设计⒈元素类型，结点类型struct STU{char name[20]; //学生名字、学号、年龄、分数char stuno[10];int age;int score;};typedef struct STU ElemType; //元素类型struct LIST{ElemType *elem;int length; //表的长度、大小int listsize;};typedef struct LIST list; //结点类型2.对抽象数据类型中的部分基本操作的伪码算法如下：int init(List *L){L→elem=(ElemType *)malloc(sizeof(ElemType)*LIST_INIT_SIZE);If(!L→elem) exit (OVERFLOW);L→length=0;L→listsize= LIST_INIT_SIZE;Return OK;}//初始化表int ListLength(List *L){return L→length;}//返回表长void GetElem(List L, int i, ElemType *e){*e=L.elem[i];} //返回元素int locateElem(List *La, ElemType e, int type){int I;switch(type) //确定元素在表中的位置{case EQVAL;for(i=0;i<La→length;i++)if(EqualList(&La→elem[i],&e))return 1;break;default;break;}return 0;}void MergeList(List *La, List *Lb, List *Lc){ //将两个表合并成Lc ElemType *pa,*pb,*pc,*pa_last,*pb_last;Pa=La→elem;pb=Lb→elem;Lc→Listsize=Lc→length=La→length+Lb→length;Pc=Lc→elem==(ElemType *)malloc(Lc→listsize*sizeof(ElemType));if (!Lc→elem) exit(OVERFLOW);pa_last=La→elem+La→length-1;pb_last=Lb→elem+Lb→length-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;i<Lb_len;i++){GetElem(*Lb,i,&e);If (!LocateElem(La,e,EQUAL))ListInsert(La,++La_len,e);}}int ListInset(List *L,int i,struct STU e){ //将元素插入表Ｌ中if(i<1||i>L→length+1) return ERROR;q=&(L→elem[i-1]);for(p=L→elem[L→length-1];p>=q;p--)*(p+1)=*p;*q=e;++(L→length);return OK;}//ListInsert Before i3.主函数和其他函数的伪码算法void main(){Initialization();//初始化ReadCommand(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 函数调用关系Less_EqualListInit ListInsert LocateElemEqualList四、调试分析⒈刚开始输入时，漏掉了一些变量参数的标记"&"，有的则错加了"&"，使得程序运行出来的结果不正确，使调试程序时费时不少。

⒉程序采用逐个输入的方法创建La,Lb,在元素较多时，会使得程序很庞大，不利于检查错误等。

⒊算法的时空分析各操作的算法时间复杂度比较合理init,ListLength,GetElem,EqualList,Less_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 is InsertList functionname stuno age scorestu1 100001 80 1000stu3 100002 80 1000(2)键入任意字符，演示为：name stuno age scorestu1 100001 80 1000stu3 100002 80 1000stu5 100003 80 1000List A length now is 3.(3)键入任意字符，演示为：name stuno age scorestu2 100001 80 1000stu4 100002 80 1000stu6 100001 80 1000List B length now is 3.(4)键入任意字符，演示为：name stuno age scorestu1 100001 80 1000stu2 100001 80 1000stu3 100002 80 1000stu4 100002 80 1000stu5 100003 80 1000stu6 100001 80 1000Second is UnionList function.Now union List A and List B...name stuno age scorestu1 100001 80 1000stu2 100002 80 1000stu3 100003 80 1000stu4 100001 80 1000stu5 100002 80 1000stu6 100001 80 1000List A length now is 6.(5) 键入任意字符，退出演示界面，回到编辑状态。