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

HUNAN UNIVERSITY课程实习报告题 目： BST 学生姓名 康小雪 学生学号 20090810310 专业班级 计科三班 指导老师 李晓鸿 完 成 日 期 2010-1211 一、 需求分析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） 若Droot空集，则存在D-root的一个划分D1,Dr 且D1Dr=空集；（3） 若D1空集，则D1中存在唯一元素x1，root，x1H，且存在D1shang de guanxi H1=H；ruo Dr空集，则Dr中存在唯一的元素，xr，H，且存在Dr上的关系HrH；H=root，x1,value) count+; return true； else if（keyrootvalue) 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(keyleftChildPtr,key,root）； else return BSTInsertHelp(root-rightChildPtr,key,root)；void BST:BSTDestoryHelp(BSTNode root)/销毁二叉树 if(root=0） return ； BSTDestoryHelp(rootleftChildPtr); BSTDestoryHelp(rootrightChildPtr）; delete root；算法的时空分析遍历所有的结点上限是O(n），动态查找的增长率上限O(log(n)）=F(n)=O（n）,故此算法的增长率上限为O（n）输入和输出的格式请输入记录的个数n： 请输入 n个记录（整数)：请输入你想查找的关键记录: 关键记录已被找到。比较次数为： .四、调试分析1看了书代码写出来了，编译无错，就是运行有问题，不知道怎么搞，后来向同学请教了代码，看懂了，写得也和人家的差不多五、测试结果六、用户使用说明（可选）本程序在DOS下运行程序运行时请输入记录的个数n: 请输入 n个记录(整数）：请输入你想查找的关键记录： 关键记录已被找到.比较次数为: 请按任意键继续。 . .七、实验心得（可选)感慨万千,不知从何说起。好好学习数据结构吧七、附录（可选）Gcd.c 主程序