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

《线性表的顺序存储结构实验报告样例.doc》由会员分享，可在线阅读，更多相关《线性表的顺序存储结构实验报告样例.doc（11页珍藏版）》请在装配图网上搜索。

年南昌航空大学实验报告（用实验报告纸，手写） 课程名称： 数据结构 实验名称： 实验一 线性表的顺序存储结构 班 级： 080611 学生姓名： 赖凌 学号： 08061101 指导教师评定： 签 名: 题目：有两张非递减有序的线性学生表A，B，采用顺序存储结构，两张表合并用c表存，要求C仍为非递减有序的，并删除C中值相同的表。 一、需求分析 ⒈ 本演示程序根据已有的6位学生的信息，实现两张表的合并及删除值相同元素的操作，不需要用户重新输入学生的信息。 ⒉ 在演示过程序中，用户敲击键盘，即可观看演示结果。 ⒊ 程序执行的命令包括： （1）构造线性表A （2）构造线性表B （3）求两张表的并 （4）删除C中值相同的元素 二、概要设计 ⒈ 为实现上述算法，需要线性表的抽象数据类型： ADT Stack { 数据对象：D={ai:|ai∈ElemSet,i=1…n,n≥0} 数据关系：R1={|ai-1,ai∈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 List 2. 本程序有三个模块： ⑴ 主程序模块 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;iL→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 i 3.主函数和其他函数的伪码算法 void main() { Initialization();//初始化 ReadCommand(cmd);//读入一个操作符 MakeList(La);printList(La);//产生并打印La MakeList(Lb);printList(Lb);// 产生并打印Lb OperateList(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 函数调用关系 main Initialization MakeList OperateList ReadCommand printList UnionList MergeList Less_EqualList Init ListInsert LocateElem EqualList 四、调试分析 ⒈ 刚开始输入时，漏掉了一些变量参数的标记"&"，有的则错加了"&"，使得程序运行出来的结果不正确，使调试程序时费时不少。 ⒉ 程序采用逐个输入的方法创建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 function name stuno age score stu1 100001 80 1000 stu3 100002 80 1000 (2)键入任意字符，演示为： name stuno age score stu1 100001 80 1000 stu3 100002 80 1000 stu5 100003 80 1000 List A length now is 3. (3)键入任意字符，演示为： name stuno age score stu2 100001 80 1000 stu4 100002 80 1000 stu6 100001 80 1000 List B length now is 3. (4)键入任意字符，演示为： name stuno age score stu1 100001 80 1000 stu2 100001 80 1000 stu3 100002 80 1000 stu4 100002 80 1000 stu5 100003 80 1000 stu6 100001 80 1000 Second is UnionList function. Now union List A and List B... name stuno age score stu1 100001 80 1000 stu2 100002 80 1000 stu3 100003 80 1000 stu4 100001 80 1000 stu5 100002 80 1000 stu6 100001 80 1000 List 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 name[20]; char stuno[10]; int age; int score; }stu[50]; typedef struct STU ElemType;//用ElemType代替学生 struct LIST {//定义表LIST为结构体类型 ElemType *elem;//存储空间基址 int length;//当前长度 int listsize;//当前分配的存储容量 }; typedef struct LIST List;//用list代表结构体LIST int init(List *L) {//构造一个空的线性表 L→elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType)); If (!L→elem) exit(OVERFLOW);// 存储分配失败 L→length=0;//空表长度为0 L→listsize=LIST_INIT_SIZE;//初始存储容量 Return ok; } int ListLength(List *L) {//求表L的长度 return L→length; } void GetElem(List L, int i, ElemType *e) { *e=L.elem[i]; } int EqualList(ElemType *e1,ElemType *e2) {//以元素e1,e2中的姓名项是否相等作为判定e1,e2是否相等的标准 if (strcmp(e1→name,e2→name)==0) return 1; else return 0; } int Less_EqualList(ElemType *e1,ElemType *e2) {//以姓名（字符串）的≤作为判定e1≤e2的标准 if (strcmp(e1→name,e2→name)<=0) return 1; else return 0; } int LocateElem(List *La,ElemType e,int type) {//判断La中是否有与e符合关系type的元素 int i; suitch(type) { case EQUAL; for(i=0;iL→length+1) return ERROR;//i值不合法 q=&(L→elem[i-1]); for(p=&L→elem[L→length-1];p>=q;--p) *(p+1)=*p; *q=e; ++L→length; return ok; } main { struct STU e;//定义结构体变量e List La,Lb,Lc;//定义结构体变量，即表La,Lb,Lc Clrscr(); Printf("\n\n--------List Demo is running ----------\n\n"); Printf("First is InsertList function.\n"); init(&La);//创建一个新表La strcpy(e.name, "stu1"); strcpy(e.stuno, "100001"); e.age=80; e.score=1000; ListInsert(&La,1,e);//在La的第1位上插入stu1的数据元素 strcpy(e.name, "stu3"); strcpy(e.stuno, "100002"); e.age=80; e.score=1000; ListInsert(&La,2,e);//在La的第2位上插入stu3的数据元素 Printlist(La);//输出La Printf("List A length now is %d.\n\n",La.length); Getch(); strcpy(e.name, "stu5"); strcpy(e.stuno, "100003"); e.age=80; e.score=1000; ListInsert(&La,3,e);//在表La的第3位上插入stu5的数据表 printlist(La);//输出表La printf("List A length now is %d.\n\n",La.length); getch(); init(&Lb);//创建一张新表Lb strcpy(e.name, "stu2"); strcpy(e.stuno, "100001"); e.age=80; e.score=1000; ListInsert(&Lb,1,e);//在表Lb的第1位上插入stu2的数据 strcpy(e.name, "stu4"); strcpy(e.stuno, "100002"); e.age=80; e.score=1000; ListInsert(&Lb,2,e);// 在表Lb的第2位上插入stu4的数据 strcpy(e.name, "stu6"); strcpy(e.stuno, "100001"); e.age=80; e.score=1000; ListInsert(&Lb,3,e);// 在表Lb的第3位上插入stu6的数据 printlist(Lb);//输出表Lb printf("List B length now is %d.\n\n",Lb.length); getch(); MergeList(&La,&Lb,&Lc);//合并表La,Lb,用表Lc存储（非递减有序） Printlist(Lc);//输出表Lc getch(); printf("Second is UnionList function.\n "); printf("Now Union List A and List B---\n "); UnionLIst(&La,&Lb);//合并La,Lb，并删除值相同的元素，用La存储 Printlist(La);//输出La Printf("List A length now is %d.\n\n ",La.length); getch(); }