浙江工业大学自学考试数据结构(实践)大纲

浙江工业大学自学考试数据结构(实践)大纲

《数据结构》实验

点此查看>>浙江自考教材真题资料大全

一、实验内容

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); //显示排序中交换次数

}