发布时间 : 星期二 文章2014数据结构实验指导书 doc更新完毕开始阅读
【提示】
用C描述课本的同学可参考：
hashfunc.c、hashquad.c、hashquad.h、hashsep.c、hashsep.h和testhash.c
实验六 排序
【实验目的】
1、 掌握常用的几种内部排序算法，理解各种内部排序算法的基本思想和特点； 2、熟悉内部排序法的排序过程；
3、掌握内部排序算法的时间复杂度，针对不同的问题能选择出合适的排序方法。
【实验原理】
排序是将一个无序的数据元素（或记录）序列，重新排列成一个按关键字递增（或递
减）的有序序列的过程。在计算机算法设计中，排序占有相当重要的地位。排序分为内排序和外排序。我们只讨论内排序。本课程涉及的主要的内排序算法有：插入排序、Shell排序、归并排序、快速排序等。排序算法有稳定和不稳定之分。
【实验内容】（实验课题一必做，课题二选做）
实验课题一：
【用C描述课本的同学】有以下结构体构成的数组：
struct StudentInfo { {
{\{\{\{\{\{\{\{\{\char ID[10]; char * name; float score;
}StuInfo[12]=
13
{\{\{\ };
1 使用直接插入的排序方法按照学号的顺序对以上数组进行排序（递增）；
2 分别用归并排序和快速排序按照姓名的顺序对以上数组进行排序（递增），有3人的名字是\，注意观察排序是否稳定。
实验课题二：实测比较各排序算法的运行时间。
1、定义长度为N的数组（C），用0到N-1之间的随机整数对各元素赋值； 2、用内插排序、归并排序和快速排序对其排序，记录排序的时间； 3、用不同的N做几次测试，比较各排序算法所用的时间。
最初可以取N = 1000，你可能得不到有效的测试结果，接下来，你可能会令N = 10000，这时的测试数据会比较有意义了，再接着你可能想把N再扩大10倍，这里要提醒同学们，内插排序的时间复杂度是O (N2)，当N扩大10倍，它需要的排序时间大致要扩大上百倍，你有这个耐心等待吗？所以请同学们小心，对较大的N，只应对O(N log N)的算法测试； 4、当测试框架搭好后，很方便对其它排序作测试，所以鼓励同学们对Shell排序、堆排序等，都可一并作比较测试；
5、注意记录整理测试结果好写入实验报告。
【实验参考程序】
C描述的排序算法的实现在Sort.h内。
TestSort已经搭了一个测试框架，对书中各种排序甚至选择算法作了测试，但没有测排序时间，用C写的同学也可以参考（时间测试见下面）。
用C的同学可以用C标准库的随机数产生器（C++版实际用的也是它）： #include
// seed就决定了后面调用random产生的序列 // 产生 [0, num-1] 之间的随机数
// 这个头文件包含下列函数的说明
// 随机数产生器初始化，一般应用只需自选seed初始化一
void srand (unsigned seed);
int random (int num);
【时间测试函数】C和C++都可以用
#include
// Time at beginning of timed section
14
void Settime ()
double Gettime()
// Return the elapsed time since the last call to Settime
{ return (double)((double)clock() - (double)tstart)/ (double)CLOCKS_PER_SEC; } 测试例： Settime ();
// 开始计时，这之后到调用Gettime ()之间是要测试时间的程序段
// elapsedTime 就是这段时间（以秒计）
// Initialize the program timer
{ tstart = clock(); }
// ……待测的语句段 double elapsedTime = Gettime ();
实验七 查找
【实验目的】
1、 掌握几种常用的内部查找算法；
2、熟悉二分查找算法和二叉搜索树的查找过程。
【实验原理】
查找又称为检索，就是根据给定的某一个值从一个数据元素集合中找出某个特定的数
据元素。查找和排序一样，是数据处理中经常使用的运算，查找算法的优劣对整个软件系统的影响很大。在一个数据元素集合中进行查找可选用的方法和该数据元素集合的存储结构有很大关系。查找有内查找和外查找之分。对于线性表，主要的内查找算法有顺序查找、二分查找等。但要注意，二分查找只适合于有序的线性表。第4章学的二叉搜索树是搜索性能优良的存储结构。
【实验要求】（实验课题一必做，课题二选做）
实验课题：
1 编写程序对实验六中的数组进行查找：
用C版教科书的同学：对数组StuInfo按照学号（ID）递增排序，然后用二分查找的方法进行学号查找，若找到则输出该学生的全部信息，若找不到相应记录也给出提示；接下来，对
15
该数组按照学分绩（score）递减排序后，使用二分查找法以学分绩作关键字进行查找。
2 对二叉搜索树查找
用C版教科书的同学：对StuInfo数组的数据以姓名（name）为关键字（key）建立一棵二叉搜索树（BST），然后以姓名为关键字进行搜索，并输出该记录相应的其它信息。要做到对关键字查找和删除，需要改变Find和Delete函数的原型，把对ElementType的查找和删除变成对KeyType的查找和删除，即把
Position Find( ElementType X, SearchTree T ); SearchTree Delete( ElementType X, SearchTree T ); 改为
Position Find( KeyType X, SearchTree T ); SearchTree Delete( KeyType X, SearchTree T ); 当然，对这些函数也要做相应的改动。
【实验参考程序】
二分查找
C版教科书在p.24 Figure 2.9，相应的程序名是fig2_9.c。二分查找函数原型是： int BinarySearch ( const ElementType A[ ], ElementType X, int N );
用它只能对C的基本算术类型（整型、浮点、指针）进行搜索，要对其它构造类型搜索，需对其进行改写，其原型应该是：
int BinarySearch (const ElementType A[ ], int N, Key X, int cmp(Key, ElementType) ); 其中类型Key一般是ElementType的一个域；
二叉搜索树（BST）
C版教科书：tree.h 、tree.c和 testtree.c，注意程序中标注的图和教科书中的图编号有差别。
cmp 是指向比较函数的指针，取代原先函数中的'>'、'<'等。与上面原型等价的是
int BinarySearch (const ElementType A[], int N, Key X, int (*cmp)(Key, ElementType) );
实验八 图
【实验目的】
1、 掌握图的邻接矩阵表示方法和邻接表表示法； 2、掌握图的深度优先遍历和宽度优先遍历方法；
16