实验九查找算法及其应用.doc

实验九 查找算法及其应用 一、实验目的 掌握二叉排序树的链式存储结构实现； 掌握二叉排序树的插入、删除和查找操作原理并编程实现； （选作）设计并实现哈希(Hash)表存储结构及查找算法。 二、实验环境 PC微机，Windows，Visual C++ 三、实验内容 1、二叉排序树的链式实现及操作 1）创建测试工程 1）启动VC++6.0，选择菜单“文件”－“新建”； （2）在打开的对话框中选中“工程”选项卡； （3）选择工程类型“Win32 Console Application”； （4）在“工程名称”处输入工程的名字lab9； （5）在“位置”处点击按钮，选择工程存放的目录位置； （6）按“确定”按钮，在出现的向导对话框中，选择“一个空工程”，按“完成”。 说明：完成以上步骤后，VC++6.0将在指定的目录位置下创建与工程名同名的目录（如c:\lab9）；该目录包含了测试工程的所有文件，其中lab9.dsw是工程文件，是工程的主文件。 2）创建定义二叉排序树的头文件 （1）按照以上步骤完成新建工程（lab9）后，选择菜单“文件”-“新建”； （2）在打开的对话框中选中“文件”选项卡； （3）选择文件类型“C/C++ Header File”； （4）在“文件名”处输入程序文件的名字btree； （5）按“确定”按钮，进入代码编写窗口。 说明：完成以上步骤后，VC++6.0将在工程的文件目录下创建头文件btree.h。 （6）输入以下参考程序代码段（类似实验6中二叉树的实现）。 typedef int BTElemType; //二叉树结点的数据类型 //二叉树结点类型 typedef struct BiTNode{ BTElemType data; struct BiTNode *lchild, *rchild; //左右孩子指针 }BiTNode, *BiTree; //在二叉排序树 bt 中递归查找值等于 key 的元素是否存在 //若在则返回其结点指针 BiTree searchBST (BiTree bt , BTElemType key); //在二叉排序树 bt 中插入新数据结点 s BiTree insertBST (BiTree bt, BiTree s); //中序遍历二叉排序树并显示遍历序列 void inorder (BiTree bt); //建立二叉排序树, 数据从键盘输入, 直到输入值等于- 1 为止 BiTree createBST(void); 3）创建实现二叉排序树的源文件 （1）选择菜单“文件”-“新建”； （2）在打开的对话框中选中“文件”选项卡； （3）选择文件类型“C++ Source File”； （4）在“文件名”处输入程序文件的名字bitree； （5）按“确定”按钮，进入代码编写窗口。 说明：完成以上步骤后，VC++6.0将在工程的文件目录下创建源文件bitree.cpp。 （6）输入以下参考程序代码段，仔细阅读、认真理解代码含义。 #include stdio.h #include stdlib.h #include malloc.h #include btree.h //包含进二叉排序树的定义头文件 //在二叉排序树 bt 中递归查找值等于 key 的元素是否存在 //若在则返回其结点指针 BiTree searchBST (BiTree bt , BTElemType key) { if ( bt == NULL) //树空或已超过叶子 return NULL; else if ( bt-data == key) //根结点等于给定值 return bt; else if ( key bt-data) //给定值小于根结点，进入左子树 return searchBST ( bt-lchild, key) ; else //给定值大于根结点，进入右子树 return searchBST ( bt-rchild, key) ; } //在二叉排序树 bt 中插入新数据结点 s BiTree insertBST (BiTree bt, BiTree s) { //s 在函数被调用前已创建好 if ( bt==NULL) //空树，s 成为树根 bt = s; else if ( s-data bt-data) //新结点小于根，递归进入左子树寻找插入位置 bt-lchild=insertBST ( bt-lchild, s); else if ( s-data bt-data) //新结点大于根，递归进入右子树寻找插入位置 bt-rchild=insertBST ( bt-rchild, s) ; ret