一、实验内容
1. 单链表的插入和删除：要求单链表的数据域是字符串，完成单链表的初始化、插入、删除操作，插入时不允许重复的串插入表中。
2. 栈操作：采用顺序存储结构,完成建栈、数据元素入栈与出栈、判断栈空、判断栈满等操作。
3. 二叉树操作：采用二叉链表作为存储结构,完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作等。
4. 图的遍历操作：可采用邻接矩阵或邻接表作为存储结构，完成有向图和无向图的DFS和BFS操作。
5. 数据查找：实现顺序查找、折半查找以及在二叉排序树上的查找算法，比较它们的查找速度。实验时所输入的数据可按有序和随机产生去组织。
6. 排序：实现直接插入、冒泡、直接选择、快速、堆、归并等排序算法，比较各种排序算法的速度。
二、实验要求
在实验内容中选择一个完整的题目，在VC++环境下完成实验。要求写出实验报告，上交电子DOC文档。
三、考核标准
1. 上交实验报告前，指导教师检查程序和实验结果。通过若干个提问，检查实验的独立完成情况。
2. 依据实验报告，检查实验内容是否符合要求。
四、实验报告样本
数据结构实验报告
设计者：***** 考号：******************* 联系电话*****************
1. 实验选题 查找、排序算法的实现和效率分析。
2. 实验要求和目的
要求: 随机产生 N=100、200、500、1000、2000个整数并存放于数组A[N]中。用顺序查找、冒泡排序实现各组数字的查找和排序，并计算出平均比较次数和平均移动次数。
目的: 通过这次实验，了解查找、排序算法的实现，并对算法的效率进行分析。
3. 实验设计
数据结构设计: 数学模型为动态一维整型数组。
4. 测试
⑴ 顺序查找算法测试
在DOS界面下运行SEARCH程序,在界面提示出"请输入需查找数组中数字的个数:"后，打入数组的N值，界面上将显示出数组中所有数字，然后在界面提示出"请输入需查找的数字:"后，键入一个查找数开始进行查找，运行结束后如果找到该数，界面上将显示该数在数组中所在的位置，否则显示"未找到!"，同时还会显示查找的比较次数。
例：N值为50时，键入数组中存在的任一数值，屏幕上出现该数在数组中的位置。同时显示出比较的次数。
顺序查找的平均查找长度为(N+1)/2.
⑵ 冒泡排序算法测试
在DOS界面下运行SORT程序，在界面提示出"请输入需排序数组的个数:"后，打入数组的N值，界面上将数组中数字按原有的顺序予以显示，程序运行完毕后，显示出排序后的数组数字，同时显示出数据交换的次数。
例：N值为50时，屏幕上将数组中数字按原有的顺序予以显示，程序运行完毕后，显示出排序后的数组数字，同时显示出数据交换的次数为547。
5. 心得
通过该次实验，掌握了查找和排序算法的实现方法，熟悉了C语言的使用。顺序查找算法平均查找长度较大，特别是当N很大时，查找效率较低，但具有算法简单的优点。冒泡排序是内部排序算法中较好的一种排序方法。
〖附〗顺序查找和冒泡排序算法源程序
// 顺序查找算法
#include
#include
#include
void main()
{ int *a;int i,k,n,j,s;
printf("请输入需查找数组中数字的个数:");
scanf("%d",&n);
a=(int *)malloc(sizeof(int) *(n+1));
for(i=1;i<=n;i++) a[i]=random(1000); // 随机数赋值
printf("数组中的数据为:\n");
i=1;
while (i<=n) {
for(j=1;j<=10;j++) { printf("%5d",a[i]); i++; }
printf("\n");
} // 一行十个显示随机数
printf("请输入需查找的数字:");
scanf("%d",&k);
i=n;
s=1;
a[0]=k; //a[0]为监视哨
while(a[i]!=k) { s++; i--; }
if(i!=0) printf("找到数组中第%d 个数\n",i);
else printf("未找到!\n");
printf("比较次数为:%5d次",s);
}
// 冒泡排序法
#include
#include
#include
void main()
{
int *a,n,i,j,t,c;
printf("请输入需排序数组的个数:");
scanf("%d",&n);
a=(int *)malloc(sizeof(int) *(n+1));
for(i=1;i<=n;i++) a[i]=random(1000); //产生N个随机数
printf("需排序的数字为：\n" );
i=1;
while (i<=n) {
for(j=1;j<=10;j++) { printf("%5d",a[i]); i++; }
printf("\n");
} // 一行十个显示随机数
c=0;
for(j=1;j<=n-1;j++)
for(i=1;i<=n-j;i++)
if (a[i]>a[i+1]) { t=a[i]; a[i]=a[i+1]; a[i+1]=t; c=c+1; }
printf("已排序的数据为：\n");
i=1;
while (i<=n) {
for(j=1;j<=10;j++) { printf("%5d",a[i]); i++; }
printf("\n");
} //一行十个显示排序数
printf("交换次数为:%5d",c); //显示排序中交换次数
