2010数据结构实验指导书1464hf.doc

数据结构B实验指导书电子工程学院数据结构与算法分析教学小组编前 言数据结构B是电子工程学院测控技术与仪器和电子信息科学与技术专业的专业必修课。由于教科书选材的变动，原来使用的数据结构实验指导书与授课内容关联不够密切。为了能更好的将理论教学和实验教学结合在在一起，我们调整了实验内容的安排，加大了实验的实践力度，并重新编写了实验指导书。要学好数据结构这门课，加强算法的设计并上机加以实现是非常重要的，希望同学们充分利用实验条件，认真完成实验，从实验得到相应的锻炼和培养。另外，仅仅依靠本实验教材中的实验想达到透彻理解数据结构的相关算法和实现是远远不够的，有条件有兴趣的学生可以针对学习和实践中出现的问题主动地思考和设计算法，编写程序，进一步提高自己分析问题和解决问题的能力。希望同学们在使用本实验指示书及进行实验的过程中，对本实验指导书中的不足之处提出建议，使数据结构B课程的教学得到不断的改进和提高。本实验指导书在编写过程中，参考了原来的电子工程系的数据结构实验指导书、计算机系的实验指导书。由于编者水平有限，难免有不足之处，敬请批评指正。 电子工程学院数据结构与算法分析教学小组 2008年4月目 录前 言1目 录2实验说明及要求3实验一 线性表4实验二 栈6实验三 队列8实验四 树10实验五 散列表14实验六 排序16实验七 查找19实验八 图22综合设计考核25附录1 在Visual S 2003中建立、编译和运行程序26附录2 使用教材提供的参考文件的方法31附录3 如何设置编译器生成C代码34参考文献35实验说明及要求一 实验说明数据结构B实验是为了辅助数据结构B(双语教学)而开展的。因为理论教学采用了两种教材（数据结构与算法分析的C+版和C语言描述版），所以在实验时程序的编写既允许采用C语言，又允许采用C语言。若采用C语言编程，C语言版本的数据结构教材上给出的基本结构，均已包含在头文件中，具体实验时可以从计算机的“E:DataStruSourceCodeC”目录下获取。若采用C+语言编程，数据结构与算法分析(C+)（第3版）教材上给出的一些源码可以从计算机的“E:DataStruSourceCodeCPP”目录下获取。编程的工具建议使用Visual C+开发环境，该编译环境对C和C+代码均支持。 具体操作：在“F:DataStru”目录下面创建自己以自己学号作为名字的文件夹。自己所有的实验程序均放在该文件夹下面。如学号为“0600820101”的同学，在“F:DataStru”目录下创建一个名为0600820101的文件夹，自己整个数据结构实验过程中设计的实验程序，都放在“F:DataStru0600820101”目录下即可。 二 实验要求在数据结构B的课程实验过程中，要求学生做到： （1）预习实验，认真做好实验内容的准备，对实验可能出现的情况提前做出思考和分析，并写成实验预习报告，需要编写程序的实验，提前做好实验的分析和设计工作。 （2）仔细观察上机编程操作时出现的各种现象，记录主要数据、信息，做出必要说明和分析。对实验中遇到的问题及对应的解决方案，要及时加以记录并写在实验报告上。 （3）认真书写实验报告。实验报告包括实验目的和要求，实验情况及其分析。对需编程的实验，写出程序设计说明，给出主要源程序流程图和清单。 （4）遵守机房纪律，每人每次实验固定一台机器，不得随意换用其他机器。服从实验教师的安排和指挥，爱护实验设备，开关机时注意保护机器。 （5）实验课不得迟到、早退。如有事不能参加实验，须提前向实验教师请假，申请调换批次。 （6）根据学校规定，无故缺少任一次实验操作或任一次实验报告，实验总成绩为0分。平时实验的验收将分为两个部分。第一部分是上机操作，包括检查预习报告、实验操作、程序运行和即时提问。第二部分是提交书面的实验报告。此外，针对以前教学中出现的问题，实验将采用阶段检查方式，每个实验都应当在规定的时间内完成，过期视为未完成该实验，以避免期末集中检查产生的诸多不良问题，希望同学们抓紧时间，合理安排，认真完成。 三 实验步骤1 选择自己的实验课题，写出预习报告，预习报告中应给出自己解决问题使用的实现算法以及对应算法的代码编写（注意不要把教材已经给出的文件代码重复抄写）。2利用预习报告，在上机实验时完成自己设计的实现，完成后举手示意让老师验收。3回去后完成自己的实验报告。实验报告中应有算法的复杂度分析、实现以及遇到的问题及其解决方案和实验后的心得。实验报告在下一次实验时上交。实验一 线性表实验目的1、 掌握线性表的逻辑结构和物理实现；2、 掌握线性表的顺序存储结构和链式存储结构，熟悉对线性表的基本操作；3、 在学有余力的情况下，掌握循环链表的实现及其基本操作；4、 根据实验要求设计并完成程序，把理论的基本操作知识转化到实际的实践应用中。实验原理线性表是最简单的一种数据结构。线性表是由n（n=0）个数据元素组成的有限序列。线性表中的数据元素可以是各种各样的，但同一线性表中的数据元素必须有相同的属性，因此是属于同一数据类型的。在计算机内，可以用不同的方式来表示线性表，其中最简单和最常用的方式是用一组地址连续存储单元依次存储线性表中的元素。其特点是逻辑关系上相邻的两个元素在物理位置上也相邻。一般地，线性表的顺序存储结构可用一个一维数组结构来描述。用这种方法存储的线性表简称为顺序表。线性表的链式存储结构（也称链表）的特点是用一组任意的存储单元存储线性表中的数据元素，不要求逻辑上相邻的元素在物理位置上也相邻。链表中的结点可用C语言中的结构数据类型来描述，也可以用C+语言中类来实现。链表中的结点只有一个链域的链表称为单链表。循环链表则是一种首尾相接的链表。对线性表首先要掌握作为抽象数据类型（ADT）的那些基本操作，其次才是具体实现的细节。实验要求（课题一必做，课题二选做）实验课题一：a、（C+语言实现）：1、 使用教材参考代码中给出的线性表类构造一个表，查找表内是否有某元素，如果有则交换该元素和它相邻的下一元素的位置；2、 （2和3中选一个即可）为链表类List增加一个成员函数reverse，使其具备能倒置链表中元素的功能。写好的表倒置函数的时间复杂度应该是Q(n)；3、 为List链表实现增加逆转迭代器类（reverse iterators），并增加方法rbegin和rend，具体要求参见教科书109页习题3.16。b、（C语言实现）在给出参考代码中给出的线性表结构体以及与之相关的函数的基础上，编写程序，实现以下操作：1、构造一个表，然后查找表内是否有某元素，如果有则交换该元素和它相邻的下一元素的位置；2、写一个函数reverse，使其能倒置线性表中元素。这个表倒置函数的时间复杂度应该是Q(n)。课题一的具体实验内容 1、构造元素类型为整型的线性表，将以下元素插入分别插入线性表： 2、查找表中是否存在元素20，实现元素20与元素9的交换；3、按照课题要求编写函数，实现线性表元素的倒置，即倒置后的表应为。*实验课题二：约瑟夫（Josephus）问题的求解（循环链表的使用，使用C和C+语言均可）。假设有编号为1，2，n的n个人围坐成一圈，约定从编号为k（n=k=1）的人开始报数，数到m的那个人出列，他的下一个人从1开始重新报数，数到m的那个人出列，依次类推，直到所有的人全部出列为止，由此产生一个出队编号的序列。 1、给定一个8个人的圈（n=8），约定从第3个人开始报数（k3），数到第4个人时的那个人出列（m4），使用循环链表，产生一个出队编号的序列。2、参考的出队序列为：。实验步骤：1、 在“F:DataStru”目录下面创建自己以自己学号作为名字的文件夹。自己所有的实验程序均放在该文件夹下面。2、 创建项目，文件保存到第1步说的目录。3、 每台计算机的教材参考代码在“E：DataStru”，先解压至“F:DataStru”。4、 通过“工具/选项/vc+目录/包含文件”把相应的F:DataStru”的代码包含进去，以便编程的时候，包含相关头文件，或参考测试程序。5、 弄懂教材参考代码中给出的线性表类（c+）或线性表结构体以及与之相关的函数（c）;构造一个表，进行实验要求的课题。实验二 栈【实验目的】1、 掌握栈的LIFO（后进先出）特点和栈的存储结构；2、熟悉栈的各种操作；3、掌握栈的应用方法，理解栈的重要应用；4、根据实验要求设计并完成程序，把理论的基本操作知识转化到实际的实践应用中。【实验原理】 栈是一种特殊的线性表，这种线性表只能在固定的一端（称为栈顶（top）进行插入和删除操作。由于只允许在栈顶进行插入和删除操作，所以栈的操作是按照“后进先出”（Last In First Out，缩写为LIFO）原则进行的。本实验要求用栈作为基本的数据结构解决各实验课题。【实验要求】（实验课题一必做，其他选做）实验课题一： 将一个十进制数转换成另外一个P进制数字符串（可以是二进制到十六进制）。转换函数的原型为：void Convert (int n, char str, unsigned P);n：输入，待转换的数str：输出，转换好的P进制字符串P：输入，要转换的进制，取值可从2到16。如果在这范围之外，可认为输入错，不做转换。将一个整数转换成P进制的数，我们可以采用如下的方法：例：十进制转换成八进制（P等于8）：(66)10=(102)866/8=8 余 28/8 =1 余 01/8 =0 余 1当商为0时转换结束，转换结果为上述过程余数序列的逆序：102。先求得的余数在写出结果时最后写出，最后求出的余数最先写出，符合栈的LIFO性质，故可用栈来实现数制转换。*实验课题二：用2个栈实现一个队列，并对使用这种方法实现的队列执行入队、出队操作的时间进行分析。用C实现的同学，应该实现教科书第76页Figure 3.56（参考代码的queue.h）中定义的队列类型的那些操作函数；用C+实现作为ADT的队列，应以以下抽象类VQueue作为与用户的界面接口：template class VQueue public:virtual void enqueue (const Object&) = 0;virtual void dequeue (Object&) = 0;virtual void dequeue () = 0;virtual const Object& front () const = 0;virtual bool empty () const = 0;出队函数dequeue()有2个原型，如QueueQ; int x; x = Q.front(); Q.dequeue (); 等价于Q.dequeue(x); 前面的用法符合STL的习惯，后面一个有时会觉得方便，所以2个都放在接口里。*实验课题三： 将一个普通代数表达式（infix expression）转换为后缀表达式（postfix expression）。转换规则描述参见：描述C语言描述的课本pp.68-71，C+语言描述的课本pp.99-102。在本实验中，也只用、（、）作为算符，优先级自低至高为、*、（）。栈的ADT接口：用C+描述的教科书中没给栈的ADT，可以用以下Stack类模版：template class Stack public: bool empty( ) const return theList.empty( ); const Object & top( ) const return theList.front( ); void push( const Object & x ) theList.push_front( x ); void pop( Object & x ) x = theList.front( ); theList.pop_front( ); void pop( ) theList.pop_front( ); private: List theList;实验三 队列【实验目的】1、 掌握队列的FIFO的特点（先进先出）特点和队列的存储结构；2、熟悉队列的各种操作；3、掌握队列的应用方法，理解队列的重要应用；4、根据实验要求设计并完成程序。【实验原理】 队列是限定只能在表的一端进行插入，而在表的另一端进行删除的线性表。是一种“先进先出”（First In First Out，缩写为 FIFO）的线性表。队列可以有多种实现形式，本实验要求将队列作为一个抽象数据类型（ADT）来解决各实验课题。【实验要求】（实验课题一必做，课题二选做）实验课题一：回文（palindrome）是指一个字符串从前面读和从后面读都一样，仅使用若干栈和队列、栈和队列的ADT函数以及若干个int类型和char类型的变量，设计一个算法来判断一个字符串是否为回文。假设字符串从标准输入设备一次读入一个字符，算法的输出结果为true或者false。可以用一些字符串测试输出结果，如： abcdeabcde， madamimadam 等实验课题二：打印扬辉三角形。111121133114641151010511615201561172135352171打印二项式 ( a + b )i 的展开系数，也就是扬辉三角，国外叫做Pascals triangle。如右下图为扬辉三角的前8行数据。按照如右图所示的方式，完成对应杨辉三角的打印输出。杨辉三角队列的ADT接口：用C+描述的教科书中没给队列的ADT，可以根据上次实验给出的抽象类VQueue写一个实现，也可以用以下Queue类模版：template class Queue public: bool empty( ) const return theList.empty( ); const Object & front( ) const return theList.front( ); void enqueue( const Object & x ) theList.push_back( x ); void dequeue( Object & x ) x = theList.front( ); theList.pop_front( ); void dequeue( ) theList.pop_front( ); private: List theList;如果要用STL的queue，可以包含头文件：#include 要注意在STL的queue中，入队、出队函数不是用enqueue和dequeue，而是类似stack，用push和pop。实验四 树【实验目的】1、 掌握树这种数据结构的特点和树的存储结构；2、掌握二叉树的建立（二叉链表的建立）；3、掌握并灵活运用各种次序的遍历算法；4、根据实验要求设计并完成程序，把理论的基本操作知识转化到实际的实践应用中。【实验原理】 由于树的定义是递归的，对树的处理原则上也应是用递归的方式。二叉树是一种非常重要的类型。针对二叉树的操作主要有三种遍历（先序遍历、中序遍历、后序遍历），遍历二叉树是二叉树中各种运算的基础。【实验要求】（实验课题一必做，课题二、三选做）实验课题一：将下图中的二叉树用二叉链表表示：ABCDEFGH1 用三种遍历算法遍历该二叉树，给出对应的输出结果；2 写一个函数对二叉树搜索，若给出一个结点，根据其是否属于该树，输出true或者false。3 写函数完成习题4.31（C+版）或4.28（C版教科书）。实验课题二：构造表达式树。可参考教科书4.2.2（具体规则用C+描述教材的见p.122，用C描述教材的见p.87）。实验课题3：哈夫曼编码的生成当哈夫曼树生成后，对由根节点到各叶结点（对应于待编码的符号）的路径作0-1编码就得到相应的哈夫曼编码。任何一棵满二叉树（a full binary tree）都可以看作是一棵哈夫曼树，所以本课题要求：造一棵满二叉树，根据这棵二叉树生成相应的哈夫曼编码。附录：二叉树的ADT接口用C+描述的教科书中没有给出一个二叉树的ADT接口，我们在这里给出一个二叉树类模板，供同学们使用。/ Binary tree node abstract classtemplate class BinaryNode public: / Return the nodes element virtual Object& val() = 0; / Set the nodes element virtual void setVal(const Object&) = 0; / Return the nodes left child virtual BinaryNode* left() const = 0; / Set the nodes left child virtual void setLeft(BinaryNode*) = 0; / Return the nodes right child virtual BinaryNode* right() const = 0; / Set the nodes right child virtual void setRight(BinaryNode*) = 0; / Return true iff the node is a leaf virtual bool isLeaf() = 0;/ Binary tree node class, an implementation of the abstract class BinaryNodetemplate class BinNode : public BinaryNode private: Object it; / The nodes value BinNode* lc; / Pointer to left child BinNode* rc; / Pointer to right childpublic: / Two constructors - with and without initial values BinNode() : lc(NULL), rc(NULL) BinNode(Object e, BinNode* l =NULL, BinNode* r =NULL) : it(e), lc(l), rc(r) BinNode () / Destructor Object& val () return it; void setVal (const Object& e) it = e; inline BinaryNode* left() const return lc; void setLeft(BinaryNode* b) lc = (BinNode*)b; inline BinaryNode* right() const return rc; void setRight(BinaryNode* b) rc = (BinNode*)b; bool isLeaf() return (lc = NULL) & (rc = NULL); ;生成二叉树根据不同的应用规则可以有各种生成二叉树的方法，如二叉搜索树、表达式树、哈夫曼树等。我们在这里描述一个根据对二叉树各节点遍历所得序列生成二叉树的方法，一般从这样一个序列不一定能生成这棵二叉树。但如果把这二叉树的所有空指针都画出来就得到一棵满的扩充的树，根据对这棵扩充树的遍历得到的序列，可以生成那棵二叉树。例如，用表示空指针，那么课题一图中那棵扩充二叉树的先序遍历得到的节点序列是：char *extendedPreOrd = ABDFEGHC;用它做为下列二叉树建造函数的输入就得到前图所示的树。BinNode *BinTreeBuildFrmStr(char *& str)if (*str != )BinNode* root = new BinNode(*str+);root-setLeft(BinTreeBuildFrmStr (str);root-setRight(BinTreeBuildFrmStr (str);return root;else/ the NULL pointer , just skip itstr+;return NULL;注：把这个函数的参数类型由对二叉树节点指针的引用改为指向指针的指针，很容易把它改为C的函数。二叉树的打印与教科书上的二叉树图相比，这里打出的数向左旋转了90度。当然了，这里还是递归。改成C函数也很容易。template void printTree(BinaryNode* subroot, int depth = 0) if (subroot = NULL) return; / Empty treeprintTree(subroot-right(), depth +1); / Do right subtreefor (int i=0; idepth; i+) / Indent to depthcout ;cout val() left(), depth +1); / Do left subtree实验五 散列表【实验目的】1 掌握散列表的构造方法；2 观察冲突现象及其解决；3 掌握使用散列法进行查找的方法。【实验原理】 散列（hashing）的基本思想是：通过一个确定的散列函数关系H，把数据对象的关键字K映射到相应的散列值H (K)，这个值就是该对象在散列表中的存储位置，又称散列地址。查找时根据要查找的关键字k用同样的散列函数计算地址H（k），然后在散列表相应的单元取要找的对象。对于散列表，最重要的是构造散列函数和对冲突的处理。影响散列表查找效率的因素是装填因子（load factor）。【实验要求】实验课题：做这个实验时采用Open Addressing框架，也可加做Separate Chaining以形成比较。1 构造散列表，把字符串数组中的各项加入到散列表中string MyBirds13 = robin, sparrow, hawk, eagle, seagull, bluejay, owl, cardinal, Jakana, Moa, Egret, Penguin, hawk ;用C表示，可以是char * MyBirds13 = robin, sparrow, hawk, eagle, seagull, bluejay, owl, cardinal, Jakana, Moa, Egret, Penguin, hawk ;为便于观察冲突现象，初始构造散列表时，表的容量不要过大，对Open Addressing，装载因子为0.5左右，对于Separate Chaining，装载因子为1左右即可。也不要做rehash（应该改源代码的哪里，如何改）。建议对源代码做些改动、增加一些输出（建议用条件编译控制这些输出），以便于观察冲突的发生和解决；对于Open Addressing，参考代码的冲突解决方案是用的平方探测（quadratic probing），如果用线性探测（linear probing）的策略，应该对函数findPos做什么修改（冲突解决的策略都集中在那里）？2 观察不同的散列函数产生冲突散列地址的情况教科书上给了3个以字符串作输入的散列函数（两教科书第3个不一样），观察记录它们产生冲突散列地址的情况，写入你的实验报告。还可对下列散列函数（所谓ELF hash，Unix System V用的）作观察38int hash (char * key) / C version unsigned long h = 0; while ( *key ) h = (h 24; h &= g; return h; / % Mint hash (const string & key) / C+ version unsigned long h = 0; for ( int i = 0; i key.length( ); i+ ) h = (h 24; h &= g; return h; / % M3 对散列表做查找。【提示】伴随课本的参考源程序中相关的部分，提供了一个现成的框架，可在此基础上修改（C+描述）：Separate Chaining：TestSeparateChaining.cppSeparateChaining.hSeparateChaining.cppOpen Addressing:TestQuadraticProbing.cppQuadraticProbing.hQuadraticProbing.cpp用C描述课本的同学可参考：hashfunc.c、hashquad.c、hashquad.h、hashsep.c、hashsep.h和testhash.c实验六 排序【实验目的】1、 掌握常用的几种内部排序算法，理解各种内部排序算法的基本思想和特点；2、熟悉内部排序法的排序过程；3、掌握内部排序算法的时间复杂度，针对不同的问题能选择出合适的排序方法。【实验原理】 排序是将一个无序的数据元素（或记录）序列，重新排列成一个按关键字递增（或递减）的有序序列的过程。在计算机算法设计中，排序占有相当重要的地位。排序分为内排序和外排序。我们只讨论内排序。本课程涉及的主要的内排序算法有：插入排序、Shell排序、归并排序、快速排序等。排序算法有稳定和不稳定之分。【实验内容】（实验课题一必做，课题二选做）实验课题一：【用C描述课本的同学】有以下结构体构成的数组：struct StudentInfochar ID10;char * name;float score;StuInfo12=0800301105, JACK, 95,0800201505, LUN, 85,0400820115, MARY, 75.5,0400850122, KATE, 78.9,0500201011, LILI, 88,0800401105, JACK, 96,0600830105, JAN, 98.4,0952520012, SAM, 75,9721000045, OSCAR, 64,0700301105, JACK, 97,0458003312, ZOE, 68.9,0400830211, BOBI, 87.6 ; 1 使用直接插入的排序方法按照学号的顺序对以上数组进行排序（递增）；2 分别用归并排序和快速排序按照姓名的顺序对以上数组进行排序（递增），有3人的名字是JACK，注意观察排序是否稳定。【用C+描述课本的同学】对实验5中的Bird类数组排序class Bird int ID;/ 代表其它信息 string name; / 当作 keypublic: Bird() / 缺省构造函数 Bird (int k, const string& str = string():ID(k), name(str) int getInfo() const return ID; const string& getkey () const return name; ;由于排序是基于比较的，所以可排序的对象一定要定义比较算符，有的排序算法需要比较算符operator 有的需要operator =，这和能放入散列表的对象不同（要定义!=和/或=）。它们应该是类成员还是友元？试用内插排序、归并排序和快速排序对以下数组以name做关键字排序Bird MyBirds14 = Bird(19, robin), Bird(14, sparrow), Bird(23, hawk), Bird( 1, eagle), Bird(68, seagull), Bird(20, bluejay), Bird(24, hawk), Bird(84, owl), Bird(27, cardinal), Bird(55, Jakana), Bird(11, Moa), Bird(10, Egret), Bird(79, Penguin), Bird(25, hawk);注意：1、 这个数组和实验5略有不同，name为hawk的有3项，其ID不同，是为了让同学们观察排序算法是否稳定；2、 教科书给的排序算法都是对vector类型的，也就是应该对vector V排序，但vector没有 的初始化形式，所以这里以数组的形式初始化。实验中做各种排序时，可以用循环把数组的各元素赋给vector。实验课题二：实测比较各排序算法的运行时间。1、定义长度为N的数组（C）或vector（C+），用0到N-1之间的随机整数对各元素赋值；2、用内插排序、归并排序和快速排序对其排序，记录排序的时间；3、用不同的N做几次测试，比较各排序算法所用的时间。最初可以取N = 1000，你可能得不到有效的测试结果，接下来，你可能会令N = 10000，这时的测试数据会比较有意义了，再接着你可能想把N再扩大10倍，这里要提醒同学们，内插排序的时间复杂度是O (N2)，当N扩大10倍，它需要的排序时间大致要扩大上百倍，你有这个耐心等待吗？所以请同学们小心，对较大的N，只应对O(N log N)的算法测试；4、当测试框架搭好后，很方便对其它排序作测试，所以鼓励同学们对Shell排序、堆排序等，甚至STL 中的sort、stable_sort（用迭代器指定排序范围），都可一并作比较测试；5、注意记录整理测试结果好写入实验报告。【实验参考程序】C和C+描述的排序算法的实现分别在各自的Sort.h内。C+ 版还有：TestSort.cpp和Random.h、Random.cpp，后面2个用于产生伪随机数。TestSort已经搭了一个测试框架，对书中各种排序甚至选择算法作了测试，但没有测排序时间，用C写的同学也可以参考（时间测试见下面）。用C的同学可以用C标准库的随机数产生器（C+版实际用的也是它）：#include / 这个头文件包含下列函数的说明void srand (unsigned seed);/ 随机数产生器初始化，一般应用只需自选seed初始化一次/ seed就决定了后面调用random产生的序列int random (int num);/ 产生 0, num-1 之间的随机数【时间测试函数】C和C+都可以用#include / Used by timing functions/ Timing variables and functionsclock_t tstart = 0; / Time at beginning of timed sectionvoid Settime ()/ Initialize the program timer tstart = clock(); double Gettime()/ Return the elapsed time since the last call to Settime return (double)(double)clock() - (double)tstart)/ (double)CLOCKS_PER_SEC; 测试例：Settime ();/ 开始计时，这之后到调用Gettime ()之间是要测试时间的程序段/ 待测的语句段double elapsedTime = Gettime (); / elapsedTime 就是这段时间（以秒计）实验七 查找【实验目的】1、 掌握几种常用的内部查找算法；2、熟悉二分查找算法和二叉搜索树的查找过程。【实验原理】 查找又称为检索，就是根据给定的某一个值从一个数据元素集合中找出某个特定的数据元素。查找和排序一样，是数据处理中经常使用的运算，查找算法的优劣对整个软件系统的影响很大。在一个数据元素集合中进行查找可选用的方法和该数据元素集合的存储结构有很大关系。查找有内查找和外查找之分。对于线性表，主要的内查找算法有顺序查找、二分查找等。但要注意，二分查找只适合于有序的线性表。第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主要函数是：template class BinarySearchTreeconst Comparable & findMin( ) const;const Comparable & findMax( ) const;bool contains( const Comparable & x ) const;void insert( const Comparable & x );void remove( const Comparable & x );现在要添加一个类模版参数Key，以及根据Key来查找和删除的函数find和remove：template class BinarySearchTree bool find(const Key& k, Comparable &) const;const Comparable & findMin( ) const;const Comparable & findMax( ) const;bool contains( const Comparable & x ) const;void insert( const Comparable & x );void remove( const Comparable & x );void remove( const Key & x );这样，就可以根据Key来对BST搜索和删除。读一下参考源码（或教科书pp.126-34），就知道还应该添加/修改相应的私有成员函数。接下来，对MyBirds数组的数据以name为关键字（Key）建立一棵二叉搜索树（BST），如果打印这棵树，注意是不是少了什么？是什么原因，如果以ID作Key呢？建好BST后，对其作相应的查找。【实验参考程序】二分查找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的一个域；cmp 是指向比较函数的指针，取代原先函数中的、等。与上面原型等价的是int BinarySearch (const ElementType A, int N, Key X, int (*cmp)(Key, ElementType) );C+版教科书的二分查找在p.59 Figure 2.9，源程序在Fig02_09.cpp