2010数据结构实验指导书48

查找又称为检索，就是根据给定的某一个值从一个数据元素集合中找出某个特定的数

据元素。查找和排序一样，是数据处理中经常使用的运算，查找算法的优劣对整个软件系统的影响很大。在一个数据元素集合中进行查找可选用的方法和该数据元素集合的存储结构有很大关系。查找有内查找和外查找之分。对于线性表，主要的内查找算法有顺序查找、二分查找等。但要注意，二分查找只适合于有序的线性表。第4章学的二叉搜索树是搜索性能优良的存储结构。

【实验要求】（实验课题一必做，课题二选做）

实验课题：

1 编写程序对实验六中的数组进行查找：

用C版教科书的同学：对数组StuInfo按照学号（ID）递增排序，然后用二分查找的方法进行学号查找，若找到则输出该学生的全部信息，若找不到相应记录也给出提示；接下来，对该数组按照学分绩（score）递减排序后，使用二分查找法以学分绩作关键字进行查找。 用C++版教科书的同学：对MyBirds分别以name和ID为关键字排序，然后进行二分查找。

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++教材的同学，和实验五（散列）的进阶类似，要改进二叉搜索树（BST）ADT定义，原来的BST ADT主要函数是：