线性表的顺序存储结构实验报告样例.doc

年南昌航空大学实验报告（用实验报告纸，手写）课程名称： 数据结构 实验名称： 实验一 线性表的顺序存储结构 班 级： 080611 学生姓名： 赖凌 学号： 08061101 指导教师评定： 签 名: 题目：有两张非递减有序的线性学生表A，B，采用顺序存储结构，两张表合并用c表存，要求C仍为非递减有序的，并删除C中值相同的表。一、需求分析 本演示程序根据已有的6位学生的信息，实现两张表的合并及删除值相同元素的操作，不需要用户重新输入学生的信息。 在演示过程序中，用户敲击键盘，即可观看演示结果。 程序执行的命令包括：（1）构造线性表A （2）构造线性表B （3）求两张表的并 （4）删除C中值相同的元素二、概要设计 为实现上述算法，需要线性表的抽象数据类型：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)初始条件：数据元素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已经存在，1iListLength(&L)+1操作结果：在表L中第i个位置前插入元素e，L的长度加1。 ADT List2. 本程序有三个模块： 主程序模块void main()初始化；接受命令；显示结果； 线性表单元模块：实现线性表抽象数据类型； 结点结构单元模块：定义线性表中的结点结构。三、详细设计元素类型，结点类型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(ElemType)*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;iLalength;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) exit(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+)GetElem(*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();/初始化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 函数调用关系mainInitialization MakeList OperateList ReadCommand printList UnionList MergeListLess_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 stunoagescorestu1100001801000stu3100002801000(2)键入任意字符，演示为：name stunoagescorestu1100001801000stu3100002801000stu5100003801000List A length now is 3.(3)键入任意字符，演示为：name stunoagescorestu2100001801000stu4100002801000stu6100001801000List B length now is 3.(4)键入任意字符，演示为：name stunoagescorestu1100001801000stu2100001801000stu3100002801000stu4100002801000stu5100003801000stu6100001801000Second is UnionList function.Now union List A and List B.name stunoagescorestu1100001801000stu2100002801000stu3100003801000stu4100001801000stu5100002801000stu6100001801000List A length now is 6.(5) 键入任意字符，退出演示界面，回到编辑状态。七、附录：题一源程序/-头文件#include#include#include/符号常量#define ERROR O#define OK 1#define EQUAL 1#define OVERFLOW -1#define LIST_INIT_SIZE 100/线性表存储空间的初始分配量#define LISTINCREMENT 10/线性表存储空间的分配增量/类型声明struct STU/定义学生结构体类型，包括姓名，学号，年龄，成绩char name20;char stuno10;int age;int score;stu50;typedef struct STU ElemType;/用ElemType代替学生struct LIST/定义表LIST为结构体类型ElemType *elem;/存储空间基址int length;/当前长度int listsize;/当前分配的存储容量;typedef struct LIST List;/用list代表结构体LISTint init(List *L)/构造一个空的线性表Lelem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType);If (!Lelem) exit(OVERFLOW);/ 存储分配失败Llength=0;/空表长度为0Llistsize=LIST_INIT_SIZE;/初始存储容量Return ok;int ListLength(List *L)/求表L的长度return Llength;void GetElem(List L, int i, ElemType *e)*e=L.elemi;int EqualList(ElemType *e1,ElemType *e2)/以元素e1,e2中的姓名项是否相等作为判定e1,e2是否相等的标准if (strcmp(e1name,e2name)=0)return 1;elsereturn 0;int Less_EqualList(ElemType *e1,ElemType *e2)/以姓名（字符串）的作为判定e1e2的标准if (strcmp(e1name,e2name)=0)return 1;elsereturn 0;int LocateElem(List *La,ElemType e,int type)/判断La中是否有与e符合关系type的元素int i;suitch(type)case EQUAL;for(i=0;iLalength;i+)if (EqualList(&Laelemi,&e)return 1;break;default;break;return 0;void MergeList(List *La,List *Lb,List *Lc)/合并表La,Lb,用Lc存储。已知La,Lb元素值按非递减排列，Lc中值也按非递减排列ElemType *pa,*pb,*pc,*pa_last,*pb_last;pa=Laelem;pb=Lbelem;Lclistsize=Lclength=Lalength+Lblength;Pc=Lcelem=(ElemType *)malloc(Lclistsize*sizeof(ElemType);if (!Lcelem) exit(OVERFLOW);/存储分配失败pa_last=Laelem+Lalength-1;pb_last=Lbelem+Lblength-1;while(pa=pa_last&pb=pb_last)/合并，Lc元素按非递减排列if (Less_EqualList(pa,pb) *pc+=*pa+;else *pc+=*pb+;while (pa=pa_last) *pc+=*pa+ /插入La的剩余元素while (pb=pb_last) *pc+=*pb+ /插入Lb的剩余元素void UnionList(List *La ,List *Lb)/将所有在Lb中而不在La中的元素插入到La中int La_len,Lb_len;int i;ElemType e;La_len=Listlength(La);Lb_len=Listlength(Lb);/求线性表长度for(i=0;iLb_len;i+)GetElem(*Lb,I,&e);If (!LocateElem(La,e,EQUAL)ListInsert(La,+La_len,e);int printlist(List L)/输入表Lint i;printf(name stuno age scoren);for (i=0;iL.length;i+)printf(%-cos%st%dt%dn,L.,L.elemi.stuno,L.elemi.age,L.elemi.score);printf(n);int ListInsert(List *L,int i,struct STU e)/在表L中第i位上插入estruct STU *p,*q;if (*iLlength+1) return ERROR;/i值不合法q=&(Lelemi-1);for(p=&LelemLlength-1;p=q;-p)*(p+1)=*p;*q=e;+Llength;return ok;mainstruct STU e;/定义结构体变量eList La,Lb,Lc;/定义结构体变量，即表La,Lb,LcClrscr();Printf(nn-List Demo is running -nn);Printf(First is InsertList function.n);init(&La);/创建一个新表Lastrcpy(, stu1);strcpy(e.stuno, 100001);e.age=80;e.score=1000;ListInsert(&La,1,e);/在La的第1位上插入stu1的数据元素strcpy(, stu3);strcpy(e.stuno, 100002);e.age=80;e.score=1000;ListInsert(&La,2,e);/在La的第2位上插入stu3的数据元素Printlist(La);/输出LaPrintf(List A length now is %d.nn,La.length);Getch();strcpy(, stu5);strcpy(e.stuno, 100003);e.age=80;e.score=1000;ListInsert(&La,3,e)