数据结构课程实验报告实验6.doc

数据结构课程实验指导书HUNAN UNIVERSITY课程实习报告题 目： BST 学生姓名 康小雪 学生学号 20090810310 专业班级 计科三班 指导老师 李晓鸿 完 成 日 期 2010-12-11 5 一、 需求分析1 该程序可以从通过从键盘输入结点的个数和结点信息（数字）来建立一个新的二叉树，输入的数字可以不按大小顺序，但大小不能重复；2 还可以输入新的数据，计算机可通过在二叉树中比较查找是否有该数据，若有，则计算机返回“查找成功”及查找时比较的次数，若没有则返回“查找不成功”及查找时比较的次数，由此形成一个动态查找表输入输出举例输入：8/BST的节点个数34, 76, 45, 18, 26, 54, 92, 65 /8个数据45/查找 45输出：查找成功 3 /返回成功和查找时比较的次数 34/查找 34输出：查找成功 1 /返回成功和查找时比较的次数100/查找 100输出：查找不成功 3 /返回成功和查找时比较的次数二、 概要设计抽象数据类型二叉树ADT BiTree数据对象 D：D是具有相同特性的数据元素集合数据关系 R：若D为空集，则R为空集，则称BinaryTree为空二叉树；若D不为空集，否则R=H，H是如下二元关系：（1） 在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；（2） 若D-root空集，则存在D-root的一个划分D1,Dr 且D1Dr=空集；（3） 若D1空集，则D1中存在唯一元素x1，H,且存在D1shang de guanxi H1=H;ruo Dr空集，则Dr中存在唯一的元素，xr，H，且存在Dr上的关系HrH;H=,H1,Hr;（4） (D1,H1)是一棵符合本定义的二叉树，称为根的左子树，(Dr，Hr)是一棵符合本定义的二叉树，称为根的右子树基本操作P:Bool BST:BSTSearch(int key,int& count)/在BST中查找元素 bool BST:BSTInsert(int key)/在BST中插入一个新的元素bool BST:BSTSearchHelp(BSTNode* root,int key,int& count)/查找的辅助函数，判断两个关键记录是否相等，若相等则返回，若大于则在右子树中查找，若小于就在左子树中查找bool BST:BSTInsertHelp(BSTNode* root,int key,BSTNode* rootParent)/插入的辅助函数，在当前节点的左或右子树插入一个节点void BST:BSTDestoryHelp(BSTNode* root)/销毁二叉树ADT Tree算法的基本思想先输入元素，构建一棵二叉树，再输入需要查找的元素，在二叉树中查找是否存在该元素。程序的流程程序由二个模块组成：（1）输入建立模块：在主函数中输入结点数和结点信息并建立相应的二叉树（2）输入查找模块：输入需要查找的数据，并在二叉树中查找最后返回查找信息三、详细设计物理数据类型二叉树class BST/二叉树private:class BSTNode/二叉树节点 BSTNode* leftChildPtr;/左孩子 BSTNode* rightChildPtr;/右孩子 int value;/值 BSTNode* root;/根节点;算法的具体步骤/基本操作的函数原型BST:BST() root=0;/初始化根节点为0BST:BST() BSTDestoryHelp(root);/析构函数销毁二叉树bool BST:BSTSearch(int key,int& count) return BSTSearchHelp(root,key,count);/在二叉树中查找bool BST:BSTInsert(int key)/插入新元素 if(root=0) root=new BSTNode(key,0,0); return true; return BSTInsertHelp(root,key,0);bool BST:BSTSearchHelp(BSTNode* root,int key,int& count)/查找 if(root=0) return false; if(key=root-value) count+; return true; else if(keyvalue) count+; return BSTSearchHelp(root-leftChildPtr,key,count); else count+; return BSTSearchHelp(root-rightChildPtr,key,count); bool BST:BSTInsertHelp(BSTNode* root,int key,BSTNode* rootParent)/插入 if(root=0) if(keyvalue) rootParent-leftChildPtr=new BSTNode(key,0,0); else rootParent-rightChildPtr=new BSTNode(key,0,0); return true; if(key=root-value) return false; else if(keyvalue) return BSTInsertHelp(root-leftChildPtr,key,root); else return BSTInsertHelp(root-rightChildPtr,key,root);void BST:BSTDestoryHelp(BSTNode* root)/销毁二叉树 if(root=0) return ; BSTDestoryHelp(root-leftChildPtr); BSTDestoryHelp(root-rightChildPtr); delete root;算法的时空分析遍历所有的结点上限是O(n),动态查找的增长率上限O(log(n)=F(n)=O(n),故此算法的增长率上限为O(n)输入和输出的格式请输入记录的个数n: 请输入 n个记录(整数):请输入你想查找的关键记录: 关键记录已被找到.比较次数为: .四、调试分析1看了书代码写出来了，编译无错，就是运行有问题，不知道怎么搞，后来向同学请教了代码，看懂了，写得也和人家的差不多五、测试结果六、