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

HUNAN UNIVERSITY

课程实习报告

题 目： BST

学生姓名 康小雪
学生学号 20090810310
专业班级 计科三班
指导老师 李晓鸿
完 成 日 期 2010-12—11

一、 需求分析
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｝ 且D1∩Dr=空集；
（3） 若D1≠空集，则D1中存在唯一元素x1，〈root，x1〉∈H，且存在D1shang de guanxi H1=H；ruo Dr≠空集，则Dr中存在唯一的元素，xr，<root，xr>∈H，且存在Dr上的关系Hr∈H；H=｛<root，x1〉,<root,xr〉,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；｝//初始化根节点为0

BST：:～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（key〈root—>value)
{
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(key<rootParent—>value）
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(key<root-〉value)
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．看了书代码写出来了，编译无错，就是运行有问题，不知道怎么搞，后来向同学请教了代码，看懂了，写得也和人家的差不多
五、测试结果

六、用户使用说明（可选）
本程序在DOS下运行
程序运行时
请输入记录的个数n:
请输入 n个记录(整数）：
请输入你想查找的关键记录：
关键记录已被找到.
比较次数为:
请按任意键继续。 . .
七、实验心得（可选)
感慨万千,不知从何说起。。。好好学习数据结构吧

七、附录（可选）

Gcd.c 主程序