数据结构实验报告
实验0：顺序表与链表
专 业： 班 级： 姓 名： 学 号： 指导教师： 日 期：
一、实验目的
（1）掌握顺序表的存储结构形式及其描述和基本运算的实。 （2）熟练掌握动态链表结构及有关算法的设计。
（3）掌握用链表表示特定形式的数据的方法，并能编写出有关运算的算法。 （4）理解单循环链表及双循环链表的特点。
二、实验内容
（1）顺序表的应用 （2）链表的应用
三、需求分析
1. 输入的形式和输入值的范围
2. 建立链表时输入的都是整数,输入0代表输入的结束，插入元素时需要输入插入的
位置和元素的值，删除元素时输入删除元素的值。 3. 输出形式
4. 所有操作在出现错误时都会有提示，并且在任意一个操作结束后都会输出操作后的
链表。
5. 程序所能达到的功能
6. 完成链表的生成，任意位置插入元素、删除，实现链表数据的排序，删除链表中相
同的元素，并且比较两个链表是否相等以及将两链表合成一个有序的链表。 7. 4.测试数据：见第八部分。
四、概要设计 实验一：
(1) 本程序包含的函数如下:
其中main函数负责操作其他的函数。 (2)各函数的功能设计为：
Creat(student & L)：建立一个链表L(尾部插入建立的链表)，并且返回这个链表的头指针。
find（student L，int e）：在链表L中寻找一样元素e。 print(student L):依次输出链表 L 的内容。 insert(student & L)：插入元素。
spilt(student & L)：从后向前寻找奇数在偶数前的情况，如果一个奇数或偶数之后还是一个奇数和偶数，就让代表奇数和偶数的变量自增，在每次所有符合连续情况的奇偶数交换完成后，偶数要从新计数。
symmetry(student L)：判断是否是对称的链表。
unite(student L1, student L2, Student & L3)：将链表A和B合成一个非递减的链表，返回新链表的头指针.
五、详细设计
(1)结点类型和指针类型:
typedef struct {
int *elem;//数组指针elem指示线性表的基地址。 int length;//线性表的当前实际长度。
int listsize;//当前分配的存储容量(以sizeof(ElemType)为单位。
}student;
(2)单链表的基本操作
A. 函数的算法:
A. Creat(student & L)：建立一个链表L(尾部插入建立的链表)，动态分配初始
大小的INT型空间。并且返回这个链表的头指针。
B. find（student L，int e）：在链表L中寻找一样元素e，所有符合查找条件
的元素都设置其标志为flag=1。
C. print(student L):依次输出链表 L 的内容。 D. insert(student & L)：插入元素。
E. spilt(student & L)：从后向前寻找奇数在偶数前的情况，如果一个奇数或偶
数之后还是一个奇数和偶数，就让代表奇数和偶数的变量自增，在每次所有符合连续情况的奇偶数交换完成后，偶数要从新计数。 F. symmetry(student L)：判断是否是对称的链表。
G. unite(student L1, student L2, Student & L3)：将链表A和B合成
一个非递减的链表，返回新链表的头指针.
六、调试分析
老师给出的代码加上网上借助了一些参考资料。主要就是将算法变成真正可用的函数。对称的那个功能用到了离散数学以前的知识点吧，额，也是一样根据算法写代码。奇数偶数自认觉得这个功能很新颖，但是分析后发现先计算出奇数偶数的个数，创建适当长度的链表进行。
七、使用说明
运行后会有以下的菜单:
八、测试结果
1 、 建立单链表：
选择 1 ，11、12、13、14、15。得到单链表（ 11，12，13，14，15 ） 2 、遍历：
3、 查找某一元素：
4、判断是否对称
5、将奇数排在偶数前
6、插入
7、合并有序表
8、退出
九、附录：部分代码
#include typedef struct { int *elem;//数组指针elem指示线性表的基地址。 int length;//线性表的当前实际长度。 int listsize;//当前分配的存储容量(以sizeof(ElemType)为单位。 }student; //创建单向无序链表 void Creat(student &L) { int go=1;//循环输入结点条件 L.elem=(int *)malloc(INIT_SIZE *sizeof(int));//动态分配初始大小的INT型空间。 L.listsize=INIT_SIZE;//把当前链表的存储袒赋值为链表动态分配的初始长度。 L.length=0;//链表的初始长度为0。 while(go==1) { if(L.length>=L.listsize)//如果所建链表长度超过当前分配的空间，则增加大小为初始增量的空间。 { printf(\"\\n所建链表长度超过当前分配的空间，将增加大小为初始增量的空间！\\n\"); L.elem=(int *)realloc(L.elem,(L.listsize+ADD_SIZE)*sizeof(int)); L.listsize+=ADD_SIZE; } printf(\"请输入整数元素：\"); scanf(\"%d\输入结点。 L.length++; printf(\"\\n继续创建操作请输入1，退出创建请输入0：\"); scanf(\"%d\ } } //遍历链表 void print(student L) { int i; for(i=0;i //查找链表中某一元素 void find(student L,int e) { int i=0,flag=0,k=0; while(i if(k==0) { printf(\"\\n在顺序表中找到该元素，位于第\"); k=1; } flag=1;//所有符合查找条件的元素都设置其标志为flag=1; } if(flag==1)printf(\"%d,\输出所有符合查找条件的元素的位置序号。 i++; } if(flag==1)printf(\"号位置！\\n\"); else printf(\"\\n在该顺序表中找不到该元素！\\n\"); } //判断所建链表是否对称。 void symmetry(student L) { int i,ave; if(L.length==1)printf(\"\\n该顺序表中仅有一个元素！\\n\"); else { ave=L.length/2;//使ave的值为链表的中间变量，作为循环结束条件。 for(i=0;i printf(\"\\n该顺序表为非对称表！\\n\");//如果在循环过程中出现不相等的情况， break;//即可判断此链表是一非对称表。 } else if(i=ave-1)printf(\"\\n该顺序表为对称表！\\n\");//否则如果一直到最后都相等，则是对称链表。 } } } //奇数排在偶数之前 void split(student &L) { int temp,i,m=0,n,c,b,JShu=0,OShu=0;//i代表各元素所在位置的序号 for(i=L.length-1;i>=0;)//从后向前寻找奇数在偶数前的情况，如果一个奇数或偶数之后还是一个奇数和偶数， { OShu=0;//就让代表奇数和偶数的变量自增，在每次所有符合连续情况的奇偶数交换完成后，偶数要从新计数。 while((L.elem[i]%2)!=0&&(i>=0)) { JShu++; i--; }//此循环从后往前查找奇数，直到遇到一个偶数结束， while((L.elem[i]%2)==0&&(i>=0)) { m=i+1; OShu++; i--; }//此循环从后往前查找偶数，直到遇到一个奇数结束 if((L.elem[i]%2)!=0)//如果一器奇数在偶数之前，交换它们，使这一串奇数位于偶数之前。 { n=i+1;//此处的n值是根据实例推测出来就等于序号加1. if(JShu<=OShu)//如果这一串奇数的数量于位于其前面的一串偶数个数，就只交换奇数数量的数据。 for(b=0;b L.elem[n]=L.elem[n+OShu];//n+OShu也是根据实例推出来 L.elem[n+OShu]=temp; n++; } else//否则就交换偶数数量的元素，即以最少操作达到所有奇数排在所有偶数之前的目的。 { n=i+1; for(b=0;b L.elem[c]=L.elem[n]; L.elem[n]=temp; c--; n++; } } } } } //插入函数 void insert(student &L) { int e,i,j,go=1; while(go==1) { if(L.length==0)//长度为0即是顺序表未创建任何元素，应首先创建。 { printf(\"\\n顺序表中尚未有任何元素，请输入元素创建顺序表。\\n\"); Creat(L); } else { if(L.length>=L.listsize)//如果所建链表长度超过当前分配的空间，则增加大小为初始增量的空间。 { printf(\"\\n所建链表长度超过当前分配的空间，将增加大小为初始增量的空间！\\n\"); L.elem=(int *)realloc(L.elem,(L.listsize+ADD_SIZE)*sizeof(int)); L.listsize+=ADD_SIZE; } printf(\"\\n请输入要插入的元素：\");scanf(\"%d\ i=0;//i值初始化为0使对比从顺序表第一个元素开始。 while(L.elem[i] for(j=L.length;j>i;j--)//如果符合条件，则第i个元素及其以后的元素的值顺序后移，以腾出第i个位置 L.elem[j]=L.elem[j-1]; L.elem[i]=e;//以便能成功插入新的元素。 } else L.elem[i+1]=e;//假如顺序表中没有元素比新元素大，就把新元素插入到表尾。 L.length++; } printf(\"\\n继续插入操作请输入1，中止请输入0。\");scanf(\"%d\ } } //合并顺序表（非递减合并到非递减） void unite(student L1,student L2,student &L3) { } int i=0,j=0,k=0; L3.length=0; L3.elem=(int *)malloc(L1.length+L2.length *sizeof(int)); L3.listsize=L1.length+L2.length; while(i L3.elem[k]=L1.elem[i]; L3.length++; i++; k++; } else { L3.elem[k]=L2.elem[j]; L3.length++; j++; k++; } } while(i L3.length++; } while(j L3.length++; } //主函数 void main() { student L,L1,L2,L3; L.length=0; L.listsize=0; L1.length=L1.listsize=0; L2.length=L2.listsize=0; int number,e; printf(\"\\n *************欢迎进入链表操作系统,请选择操作************************\"); printf(\"\\n 1.创建顺序表\"); printf(\"\\n 2.遍历顺序表\"); printf(\"\\n 3.在该顺序表中进行顺序查找某一元素，查找成功返回1，否则返回0\"); printf(\"\\n 4.判断该顺序表中元素是否对称，对称返回1，否则返回0\"); printf(\"\\n 5.把顺序表中所有奇数排在偶数之前\"); printf(\"\\n 6.输入整型元素序列利用有序表插入算法建立一个有序表\"); printf(\"\\n 7.利用算法6建立两个非递减表，并合并成非递减表\"); printf(\"\\n 8.退出\"); printf(\"\\n ******************************************************************\\n\"); printf(\"\\n请输入选择序号：\");scanf(\"%d\while(number!=8) { switch(number) { case 1:Creat(L); break; case 2:print(L); break; case 3:printf(\"\\n请输入要查找的元素：\");scanf(\"%d\ find(L,e); break; case 4:symmetry(L); break; case 5:split(L); printf(\"\\n调换奇偶数元素的位置后的顺序表如下：\\n\"); print(L); break; case 6:insert(L); break; case 7:printf(\"\\n利用算法6创建表L1.\\n\"); insert(L1); printf(\"\\n利用算法6创建的表L1如下：\\n\"); print(L1); printf(\"\\n利用算法6创建表L2.\\n\"); insert(L2); printf(\"\\n利用算法6创建的表L2如下：\\n\"); print(L2); printf(\"\\n正在合并表L1和表L2……\\n\"); unite(L1,L2,L3); printf(\"\\n表L1和表L2合并后的表L3如下：\\n\"); print(L3); break; case 8: break; } printf(\"\\n继续操作请输入1~7之间的数字，退出请输入8：\"); scanf(\"%d\ } } 因篇幅问题不能全部显示，请点此查看更多更全内容