课程名称： 数据结构 实验名称： 线性表 班 级： 学生姓名： 学号： 指导教师评定： 签 名:
题目：有两张非递增有序的线性学生表A，B，采用顺序存储结构，两张表合并用c表存，要求C为非
递减有序的，然后删除C表中值相同的多余元素。
一、需求分析
⒈ 本演示程序根据已有的两张表的信息，实现两张表的合并及删除值相同元素的操作，需要用户输入学生的信息。
⒉ 在演示过程序中，用户输入需要合并的顺序表，即可观看合并结果。 ⒊ 程序执行的命令包括：
（1）构造线性表A （2）构造线性表B （3）求两张表的并 （4）删除C中值相同的元素
二、概要设计
⒈ 为实现上述算法，需要线性表的抽象数据类型：
ADT Stack {
数据对象：D={ai:|ai∈ElemSet,i=1„n,n≥0} 数据关系：R1={ 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) 1 初始条件：非递减线性表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。 2. 本程序有三个模块： ⑴ 主程序模块 void main(){ 初始化； { 接受命令； 显示结果； ｝ ｝ ⑵ 线性表单元模块：实现线性表抽象数据类型； ⑶ 结点结构单元模块：定义线性表中的结点结构。 }ADT List 三、详细设计 ⒈线性表的存储结构 typedef struct {int *elem; int length; int listsize;}sqlist; 2.对抽象数据类型中的部分基本操作的伪码算法如下： void initlist(sqlist *L) { int i; L->length=len; L->elem=(int *)malloc(40); for(i=0;i void init(sqlist *L) { 2 L->elem=(int *)malloc(40); L->length=0; L->listsize=LIST_INIT_SIZE;}//给链表分配空间 void output(sqlist *L) { int i; for(i=0;i void merry(sqlist *A,sqlist*B,sqlist *C) { int i,j,k; k=0; i=A->length-1;j=B->length-1; while(i>=0&&j>=0) { if(A->elem[i] if(A->elem[i]==B->elem[j]) {C->elem[k]=B->elem[j]; i--;j--;k++;} else {C->elem[k]=B->elem[j]; j--;k++;} } while(i>=0) { C->elem[k]=A->elem[i]; k++;i--; } while(j>=0) { C->elem[k]=B->elem[j]; k++;j--;} C->length=k; }//将链表A，B按要求放入C中 3.主函数和其他函数的伪码算法 void main() 3 { sqlist *A,*B,*C; printf(\"请输入单调不增线性表A\\n\"); initlist(A); printf(\"请输入单调不增线性表B\\n\"); initlist(B); init(C); printf(\"输出单调不增线性表A：\"); output(A); printf(\"输出单调不增线性表B：\"); output(B); merry(A,B,C); printf(\"输出合并后的单调不减线性表C：\"); output(C); getch(); } 4 函数调用关系 Main调用initlist，init，output，merry； 四、调试分析 ⒈ 刚开始输入时，漏掉了一些变量参数的标记\"&\"，有的则错加了\，还有的少了“;”,使得程序运行出来的结果不正确，使调试程序时费时不少。 ⒉ 程序采用逐个输入的方法创建La,Lb,在元素较多时，会使得程序很庞大，不利于检查错误等。 ⒊ 算法的时空分析 各操作的算法时间复杂度比较合理 init为O(1)；initlist，output为O(len); merry为O(len*len); 4.本次实验采用数据抽象的程序设计方法，将程序化为三层次结构，设计时思路清晰，使调试也较顺利，各模块有较好的可重用性。 五、用户手册 ⒈ 本程序的运行环境为windows xp操作系统，执行文件为Win-TC； ⒉ 进入演示程序后，完成编译，进入演示界面,然后输入相应的内容后按Enter便可出结果。 六、测试结果 请输入单调不增线性表A 98 87 82 76 65 54 请输入单调不增线性表B 89 86 79 76 62 32 输出单调不增线性表A：98 87 82 76 65 54 输出单调不增线性表B：89 86 79 76 62 32 4 输出合并后的单调不减线性表C：32 54 62 65 76 79 82 86 87 89 98 七、附录：题一源程序 #include #define LIST_INIT_SIZE 100/*线性表存储空间的初始分配量*/ #define len 6 typedef struct {int *elem; int length; int listsize;}sqlist; void initlist(sqlist *L) { int i; L->length=len; L->elem=(int *)malloc(40); for(i=0;i void init(sqlist *L) { L->elem=(int *)malloc(40); L->length=0; L->listsize=LIST_INIT_SIZE;} void output(sqlist *L) { int i; for(i=0;i void merry(sqlist *A,sqlist*B,sqlist *C) { int i,j,k; k=0; i=A->length-1;j=B->length-1; while(i>=0&&j>=0) { if(A->elem[i] 5 {C->elem[k]=A->elem[i]; i--;k++;} else if(A->elem[i]==B->elem[j]) {C->elem[k]=B->elem[j]; i--;j--;k++;} else {C->elem[k]=B->elem[j]; j--;k++;} } while(i>=0) { C->elem[k]=A->elem[i]; k++;i--; } while(j>=0) { C->elem[k]=B->elem[j]; k++;j--;} C->length=k; } void main() { sqlist *A,*B,*C; printf(\"请输入单调不增线性表A\\n\"); initlist(A); printf(\"请输入单调不增线性表B\\n\"); initlist(B); init(C); printf(\"输出单调不增线性表A：\"); output(A); printf(\"输出单调不增线性表B：\"); output(B); merry(A,B,C); printf(\"输出合并后的单调不减线性表C：\"); output(C); getch(); } 6 因篇幅问题不能全部显示，请点此查看更多更全内容