资源预览内容
第1页 / 共5页
第2页 / 共5页
第3页 / 共5页
第4页 / 共5页
第5页 / 共5页
亲,该文档总共5页全部预览完了,如果喜欢就下载吧!
资源描述
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 且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看了书代码写出来了,编译无错,就是运行有问题,不知道怎么搞,后来向同学请教了代码,看懂了,写得也和人家的差不多五、测试结果六、用户使用说明(可选)本程序在DOS下运行程序运行时请输入记录的个数n: 请输入 n个记录(整数):请输入你想查找的关键记录: 关键记录已被找到.比较次数为: 请按任意键继续. . .七、实验心得(可选)感慨万千,不知从何说起。好好学习数据结构吧七、附录(可选)Gcd.c 主程序
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号