贵州大学数据结构实验1线性表及应用

实验一 线性表及应用一、实验目的1复习C语言的上机环境，掌握C语言的基本结构;2会定义线性表的顺序存储结构和链表的存储结构;3 熟悉对顺序表的一些基本操作和具体的函数定义。4掌握顺序表和单链表的存储结构及相关运算5掌握顺序表和单链表的基本应用二、实验硬软件环境 硬件环境：赛扬433以上CPU，10GB以上硬盘，64MB以上内存 软件环境：DOS+Turbo C 2.0 或 Borland C+ 3.1以上 Windowx 9X+VC+ 5.0以上三、实验要求1认真阅读和掌握本实验内容所给的全部程序。2保存和打印出程序运行结果，并结合程序进行分析。3 按照你对顺序表操作的需要，屏幕考贝运行结果到实验报告中。4撰写实验报告并准时上交四、注意事项在做第一次“数据结构”课程实验之前，要在硬盘上建立好自己的工作目录，专门用来存储你所做的实验程序及相关信息，以后每次做实验都采用这个目录。工作目录建议如下建立，最后注明实验作者（张三）：D:数据结构实验（张三） | +-实验一 |+-实验二 |. +-实验九实验一至九的有关材料请同学在网上下载（下载网址：），本实验设计完全由老师设计，版权限本班同学使用，勿外传。实验材料下载到本机后，请用winrar软件释放到你的电脑磁盘的“数据结构实验（张三）”文件夹中，形成如上图的文件夹结构。上交实验报告时，请把“实验一”的所有内容（含实验报告）用winrar打包成.rar文件后一并交上来。上传名字为“实验一（张三）.rar”五、基本理论 线性表：线性表（linear list）是这样的数据对象，其实例形式为： (e1 , e2 ,. en )，其中n 是有穷自然数。ei 是表中的元素，n 是表的长度。元素可以被视为原子，因为它们本身的结构与线性表的结构无关。当n = 0 时，表为空；当n 0时，e1 是第一个元素，en 是最后一个元素，可以认为el优先于e2，e2 优先于e3，如此等等。除了这种优先关系之外，在线性表中不再有其他的结构。 基本操作： 创建一个线性表。 确定线性表是否为空。 确定线性表的长度。 查找第k个元素。 查找指定的元素。 删除第k个元素。 在第k个元素之后/之前插入一个新元素。 线性表ADT（图1）：图1 线性表抽象数据类型 顺序表：采用数组来表示一个对象的实例，数组中的每个位置被称之为单元（cell）或节点（node），每个数组单元应该足够大，以便能够容纳数据对象实例中的任意一个元素。在某些情况下，每个实例可分别用一个独立的数组来描述，而在其他情况下，可能要使用一个数组来描述几个实例。实例中每个元素在数组中的位置可以用一个数学公式来指明。假定使用一个数组来描述表，需要把表中的每个元素映射到数组的具体位置上。第一个元素在什么地方？第二个元素在什么地方？在公式化描述中，可用一个数学公式来确定每个元素的位置。一个简单的映射公式如下：location(i)= i - 1 （式1-1） 式1-1表明第i个元素的存储位置在数组的第i-1个位置; 如果每个元素的长度为m，则可以通过公式计算第i个元素的存储地址： Address(i)=Address(1)+(i-1)*m (式1-2) Address(1)为第1个元素的址，即数组的首地址。特别要记住的是第1个元素保存在数组的第0个位置。 图2 表性表实例简而言之，顺序表就是把线性表的元素存储在数组中，元素之间的关系直接通过相邻元素的位置来表达。优点：简单，数据元素的提取速度快；缺点：（1）静态存储，无法预知问题规模的大小，可能空间不足，或浪费存储空间；（2）插入元素和删除元素时间复杂度高O（n） 链 表： 在存储线性表List中的每个元素ei时，同时存储元素的下一个元素的首地址（指针）Address(i+1),通过这种方法建立起元素之间的关系，从“逻辑”上看所有元素构成了图3所示的“链”，所以称为链表。图3 一个单链表从图3可以看出元素之间的链接关系，为了“访问”每个元素ei的，必须知道ei的首地址，而这个首地址存储在其“直接前驱”结点ei-1中，按此规律，可以回推到元素e1的首地址。即要访问List中任一元素ei,都必须从第一个元素e1开始，所以，必须保存首元素e1的地址在一个变量中(first),有的书使用Head作为变量名。图3的单链表的首元素的地址在first中，我们可以直接用“first”称呼此单链表。List中所有元素可以占用连续的存储空间，也可以占用不连续的存储空间。但是从“逻辑”上来看所有元素仍然满足“一对一”的关系，即：（1）首元素没有“直接前驱”，尾元素没有“直接后继”。（2）中间元素有且仅有一个“直接前驱”和“直接后继”为了实现这种存储结构，可以使用C语言作如下定义：typedef struct Lnode DataType data; struct Lnode *next; /*递归定义，保存下一个元素的首地址*/LinkNode;关键字“typedef”的作用把结构体类型定义成一种新的类型LinkNode,即链表中的一个结点类型（用以存储一个数据元素，这样可以定义一个结点变量存储一个数据元素： LinkNode a; 也可定义一个“结点”指针保存某个结点的首地址： LinkNode *p; 对于其它可能不支持动态存储分配的高级语言来说，上述LinkNode类型定义时就内部就不能使用地址，但是我们可以利用数组“模拟”链表的功能，这种链表可以这样定义： typedef strut node DataType data; int next; LinkNode; “指针”域用一个整型变量（next）来表示，用于存储下一个元素位于数组中的“位置”，这样定义的链表如图4所示：图4 静态链表 链表还有“循环链表”（图5）和“双链表”（图6），无论多么复杂的链表，其基础都是单链表，因此，完全掌握单链表后，学习其它有关链接存储将会变得简单得多，这是本章我们的重点任务。 循环单链表，实际上是利用链表的“尾结点”的空指针来指向链表的首结点。有循环链表后，只要知道链表中任一结点的地址，就可以访问链表中所所有结点。注意图5b引入了一“头结点”，目的是让空链表与非空链表统一，方便操作实现。图5 循环单链表 双链表是在单链表的基础上，在数据元素中再增加一个冗余项，用以保存结点的“直接前驱”结点的地址，这样结点既可以指向“直接后继”，也可以指向“直接前驱”，实现链表的双向查找。图6 双向链表链表最大的优点是在某个元素之后插入结点或删除结点非常方便，时间复杂度为常数O（1）。缺点是空间利用率低，存取指定元素效率低O（n）。六、实验内容与过程 本实验用到的文件有（在文件夹“实验一实验材料”中） Lineast.h、Lineast.cpp、LineastTest.cpp 、Link.h、Link.cpp、LinkTest.cpp 前三个文件保存在子目录“SqList”中，后三个保存在子目录“Link”中后缀有“Test”的文件用以测试顺序表和链表的各项操作的正确性，里面包含了主函数“main”。*.h文件中包含了数据结构的定义，对应的同名cpp文件包含了对数据结构进行的各种操作的实现。请按以下提示完成所有实验。（一）文件Lineast.cpp是顺序表的实现，其中有三个函数没有完全实现，请同学认真阅读整个程序，然后根据所学的知识完善，完善后编译Lineast.cpp，然后运行LineastText.CPP,屏幕出现菜单：Lineast.CPP中需要补充的代码如下：int InsertElem(SqList *L,int i, ElemType *e) /*在第i个位置插入元素,插入成功返回1*/int j;/*请在以下部分插入程序代码*/if(GetLength(L)=LINEASTMAXSIZE|iGetLength(L)+1|iLength+1;ji;j-)L-dataj=L-dataj-1; L-Length+;L-datai=*e;/*插入代码结束*/return 1;int DeleteElem(SqList *L,int i) /*删除第i个元素,删除成功返回1*/ int j; int n=GetLength(L); /*请在以下部分插入程序代码*/ if(n=0|in)printf(error);return 0;elsefor(j=i;jLength;j+) L-dataj=L-dataj+1; L-Length-; /*插入代码结束*/ return 1;.int SearchElem(SqList *L,ElemType *e) /*查找元素*e的位置j,找到返回,失败返回-1 */int j;int n=GetLength(L);/*请在下面插入你的代码*/ j=GetLength(L)+1;for(int m=1;mdatam=*e)j=m;break;elsecontinue; /*插入代码结束*/return jlength+1之间（12）输入4，回车后，根据屏幕提示输入：5 -1，回车屏显：原因：插入元素必须为在1到L-length+1之间（13）输入4，回车后，根据屏幕提示输入：90 9，回车屏显：（13）输入4，回车后，根据屏幕提示输入：95 10，回车屏显：（14）输入4，回车后，根据屏幕提示输入：100 12，回车屏显：原因：插入元素必须为在1到L-length+1之间（15）输入5，回车屏显：（16）输入6，回车后，根据屏幕提入示输入：70 4，回车屏显：（17）输入6，回车后，根据屏幕提入示输入：5 0，回车屏显：原因：对表操作必须在1到L-length（18）输入6，回车后，根据屏幕提入示输入：100 9，回车屏显：（19）输入6，回车后，根据屏幕提入示输入：110 11，回车屏显：原因 修改元素后并为对L-length进行+（20）输入7，回车后，根据屏幕提入示输入：6，回车屏显：（21）输入7，回车后，根据屏幕提入示输入：0，回车屏显：原因 数组是从1开始的（22）输入7，回车后，根据屏幕提入示输入：10，回车屏显：原因：第10号元素存在，并且为95（23）输入8，回车屏显：（24）输入2，回车屏显：原因：L-length被清0进一步思考并回答：（1）步骤1、2分别用来干什么？答：初始化一个顺序表（2）步骤2-8用来干什么？其中步骤5-8有什么用？ 答：2到8是用来删除一个元素，5到8是用来验证当删除条件不满足时是否能执行删除。（3）步骤9-14用来干什么？其中11、12、13、14的目的是什么？答：9到14是用来加入一个元素，11到14是用来验证当插入条件不满足时是否能进行插入。（4）步骤16-19作用是什么？答：是用来改变一个表内元素的值。（5）步骤20-21作用是什么？答：是用来验证当改变条件不满足时，是否能改变一个表内元素的值。（二）单链表的操作实现放在Link.CPP中，其中有几个函数未完成（如下），请同学们认真这个文件中的所有操作的实现，在适当的地方补充完成本实验：.LKList FindElem(LKList *L,int i) /*查找第i个元素的操作,近到返回元素地址,找不到返回空*/ LKList p=*L; int j=0; /*以下补充代码*/if(*L=NULL)return NULL; int n=GetLength(L); if(in) return NULL; if(i=1)return p; for(j=0;jnext; else break; /*代码补充结束*/ return p;.int InsertElem(LKList *L,int i, ElemType *e) /*在第i个位置插入元素*/ LKList p=FindElem(L,i-1); LNode *s; /*构造待插入的结点*/ s=(LNode*)malloc(sizeof(LNode); s-data=*e;s-next=NULL; /*以下补充代码*/ if(i=1) s-next=*L;*L=s;return 1; if(p=NULL) printf(error); return 0; elses-next=p-next; p-next=s; /*代码补充结束*/return 1;int DeleteElem(LKList *L,int i) /*删除第i个元素,成功,返回1*/ LKList p,q; if(*L=NULL)return 0; /*以下补充代码*/ p=FindElem(L, i-1); if(i=1) q=*L;*L=(*L)-next;return 1;if(p=NULL|p-next=NULL)printf(invaild position to delete!n); return 0;elseq=p-next;p-next=q-next;free(q); /*代码补充结束*/ return 1; 函数补充正确、编译运行后，出现运行屏幕菜单如图8：图8 链表操作菜单 屏幕出现图8菜单后，请按(一)中的数据和操作步骤（1）-（24）测试所有功能选项，并写出每步的显示结果并分析原因：（1）输入1，回车，然后输入一组数据(数之间用空格隔开，-9999)为结束标志 10 20 30 40 50 60 70 80 90 -9999（2）输入2，回车，观察屏幕并显示结果； 屏显：（3）输入3，回车后，根据屏幕提示输入1，回车 屏显：（4）输入3，回车后，根据屏幕提示输入3，回车 屏显：（5）输入3，回车后，根据屏幕提示输入7，回车 屏显：（6）输入3，回车后，根据屏幕提示输入大等于7的数，回车 屏显：（7）输入3，回车后，根据屏幕提示输入：0，回车屏显：原因：因为链表是从1开始的，不存在0号元素（8）输入3，回车后，根据屏幕提示输入小于等于0的数，回车屏显：原因：此表是从1开始的，不存在-1号元素（9）输入4，回车后，根据屏幕提示输入：35 3，回车 屏显：（10）输入4，回车后，根据屏幕提示输入：10 1，回车屏显：（11）输入4，回车后，根据屏幕提示输入：5 0，回车屏显：原因：链表是从1开始的，不存在0号位置（12）输入4，回车后，根据屏幕提示输入：5 -1，回车屏显：原因：插入元素必须为在1到链表的长度+1之间（13）输入4，回车后，根据屏幕提示输入：90 9，回车屏显：（13）输入4，回车后，根据屏幕提示输入：95 10，回车屏显：（14）输入4，回车后，根据屏幕提示输入：100 12，回车屏显：原因：插入元素必须为在1到链表的长度+1之间（15）输入5，回车屏显：（16）输入6，回车后，根据屏幕提入示输入：70 4，回车屏显：（17）输入6，回车后，根据屏幕提入示输入：5 0，回车屏显：原因：对表操作必须在1到链表的长度之间（18）输入6，回车后，根据屏幕提入示输入：100 9，回车屏显：（19）输入6，回车后，根据屏幕提入示输入：110 11，回车屏显：原因 修改元素必须在1到链表长度之间（20）输入7，回车后，根据屏幕提入示输入：6，回车屏显：（21）输入7，回车后，根据屏幕提入示输入：0，回车屏显：原因 查找元素必须在1到链表长度之间（22）输入7，回车后，根据屏幕提入示输入：10，回车屏显：原因：该链表的第10项为95（23）输入8，回车屏显：（24）输入2，回车屏显：原因：L中的结点被释放，且L指向空 比对（一）与（二）的运行结果，你发现了什么？你认为这说明了什么问题？ 答：运行结果相似，说明顺序表和链表都可以实现相同功能。（三）请分别在顺序表与链表中添加一个作操作Reverst( )，实现表元素的就地“逆置”的操作,并测试程序的正确性，每种结构有三个地方需要添加1.线性表有三处地方需要你添加相应的代码： (1)Lineast.h ./*以下是要添加的操作:顺序表逆置*/ void inverse (SqList *L); /*添加结束*/(2)Lineast.cppvoid ClearList(SqList *L) /*清除线性表*/L-Length=0;./* 以下为补充顺序表逆置操作实现 */void inverse (SqList *L)int n1=int (GetLength(L)/2);int n=GetLength(L);int i=0;int t;while(n1-i)i+;t=L-datai;L-datai=L-datan+1-i;L-datan+1-i=t;/* 补充结束 */(3)LineastTest.cppcase 8:ClearList(&L); if(GetLength(&L)=0) printf(Now,you list has no element!n);break; /* 以下补充对功能9的测试代码*/case 9:inverse(&L); printf(now your list isn); TraversList(&L); break; /* 补充结束 */ case 0: .2.单链表需要补充的地方(1)Link.h./*以下补充单链表的逆序操作说明*/ void inverse(LKList *L);/*补充结束*/. (2)Link.cpp /* 以下补充逆序单链表的实现*/void inverse(LKList *L)int i=1,m;LKList p,q,r;int n=GetLength(L);int n1=int(GetLength(L)/2);q=*L; r=NULL;if(GetLength(L)next;if(i=1)(*L)=p-next; p-next=q;elser=p-next;p-next=q-next;q-next=r;if(i1)q=q-next;i+;/* 补充结束 */ . (3)LinkTest.cppbreak; /* 以下补充测试 就地逆序 链表的功能选项*/case9: inverse(&L); printf(now,your list is n); TraversList(&L); break; /* 结束补充 */ default: 3.要求每个实验自己设计至少5组有代表性的数据测试“操作”的正确性 （1）测试顺序表结果： 用例1： 结果1： 用例2： 结果2： . 用例5： 结果5： （2）测试单链表结果： 用例1： 结果1： 用例2： 结果2： . 用例5： 结果5： （四）正确完成前面三项工作后，继续做顺序表的应用实验、本实验用到的三个函数分别放在“实验一实验材料四”文件夹中的pra1-1.cpp、pra1-2.cpp、pra1-3.cpp程序文件中： （1）pra1-1.cpp用来合并两个“有序”顺序表A和B到另放另一个顺序表C中，结果仍保持有序，函数名Combine；文件中，Combine的实现为空，请补充完整：/*检查一个表是否有序,有序返回1,无序返回0*/int IsSort(SqList *L)/*以下填入代码*/int i,j;int n=GetLength(L);if(n2) return 1;for(j=1;jdataj=L-dataj+1) continue;else break;if(j=n&L-dataj-1=L-dataj) return 1;for(i=1;idataidatai+1) continue;else break; if(i=n&L-datai-1datai) return 1;/*填入代码结束*/return 0;/*合并函数*/int Combine(SqList *A,SqList *B,SqList *C)/*以下填入程序代码*/if(!IsSort(A) return 0;if(!IsSort(B) return 0;int na= GetLength(A);int nb= GetLength(B);if(na+nbLINEASTMAXSIZE) return 0;int r,z;int j;int n=GetLength(A)+GetLength(B);if(nLINEASTMAXSIZE) printf(error);return 0;for(j=1;j=n;j+)if(jdataj=A-dataj;elseC-dataj=B-dataj-na; C-Length=j; if(IsSort(C)return 1;for(int k=1;kLength;k+)r=k;for(int m=k+1;mLength;m+)if(C-datarC-datam)r=m;else continue;z=C-datak;C-datak=C-datar;C-datar=z;/*填入代码结束*/return 1;. 本实例要求用以下9组数据测试: 用例1：A=2,5,8,9， B=1,6,10 12,13 结果：C= 用例2：A= ，B=1,6,10 12,13 结果：C= 用例3：A=2,5,8,9， B= 结果：C= 用例4：A=10，B= 结果：C= 用例5：A=1,2,3,B=4,5,6,7,8,9 结果：C= 用例6：A=4,5,6,7,8,9,B=1,2,3 结果：C= 用例7：A=1,3,5,7,9,11,B=2,4,6,8,10,12 结果：C= 用例8：A=1,2,3,4,5,B=1,2,3,4,5 结果：C= 用例9：A=1，B=2 结果：C= （2）分解一个顺序表A，所有奇数存入表A1，所有偶数存入表A2，函数名Split；程序名为pra1-2.cpp,请补充完整；/*分解A到A1和A2中,分解以后,A置空*/int Split(SqList *A,SqList *A1,SqList *A2)/*以下填入程序代码*/int s=GetLength(A);int i=0,j=0;int m=0,n=0; while(s-i) i+; if(A-datai%2) m+; A1-datam=A-datai; else n+; A2-datan=A-datai; A1-Length=m; A2-Length=n; /*填写代码结束*/return 1;以下为7组测试数据，根据测试结果，把运行结果硬拷贝后，复制到你的实验报告中。 用例1：A=1,2,3,4,5,6,7,8,9,10 用例2：A=1,3,5,7,9 用例3：A=2,4,6,8,10 用例4：A=1 用例5：A=2 用例6：A= 用例7：A=1,3,5,7,2,4,6,8,10 （3）合并两个顺序表A和B，结果放入到另一个顺序表C，在C中A与B两个顺表中的元素“交替”顺序存放，函数名Alternate；程序文件名为pra1-3.cpp,请补充完整/*交替合并函数,C直接使用A与B的结点*/int Alternate(LKList *A,LKList *B,LKList *C)/*以下填入程序代码*/int j;int n=GetLength(A)+GetLength(B);int na=GetLength(A);int nb=GetLength(B);if(!IsSort(A)return 0;if(!IsSort(B)return 0;for(j=1;j=n;j+)if(j+1)/2=na&j/2dataj=A-data(j+1)/2; else C-dataj=B-dataj/2; elseif(na-nb0)C-dataj=A-dataj-nb; if(na-nbdataj=B-dataj-na;C-Length=j-1;/*补充结束*/return 1; 请采用（1）的用例测试，然后观察结果。 用例1：A=2,5,8,9， B=1,6,10 12,13 结果：C= 用例2：A= ，B=1,6,10 12,13 结果：C= 用例3：A=2,5,8,9， B= 结果：C= 用例4：A=10，B= 结果：C= 用例5：A=1,2,3,B=4,5,6,7,8,9 结果：C= 用例6：A=4,5,6,7,8,9,B=1,2,3 结果：C= 用例7：A=1,3,5,7,9,11,B=2,4,6,8,10,12 结果：C= 用例8：A=1,2,3,4,5,B=1,2,3,4,5 结果：C= 用例9：A=1，B=2 结果：C= （五）正确完成前面三项工作后，继续做“链表”的应用实验、本实验用到的三个函数分别放在“实验一实验材料五”文件夹中的pra1-4.cpp、pra1-5.cpp、pra1-6.cpp程序文件中： （1）合并两个“有序链表”A和B，结果放入到另一个“链表”C中，仍保持有序，函数名Combine；程序文件为pra1-4.cpp。 测试用例与（四）同 （2）分解一个“链表”A，所有奇数存入表A1，所有偶数存入表A2，函数名Split；程序文件为pra1-5。 测试用例与（四）同 （3）合并两个“链表”A和B，结果放入到另一个“链表”C，在C中A与B两个顺表中的元素“交替”顺序存放，函数名Alternate；放在程序文件pra1-6中测试用例与（四）同(六)请完成一元多项式的类型定义和实