二叉排序树的查找算法的设计和性能分析实验报告.docVIP

“数据结构”课程设计报告 二叉排序树的查找算法的设计和性能分析 学生姓名： 王玉 杨甜利 指导教师： 陈 少 军 所 在 系： 电 子 信 息 系 所学专业： 计 算 机 科 学 与 技 术 年 级： 2010级计算机（1）班 目录 第一章 需求分析 1 1．1 选题要求 2 1.2选题的背景与意义 2 1.3 课程设计目标 3 1.4 人员组成和分工 4 第二章 概要分析 5 2、1设计流程图 5 2、2部分数据（截图） 5 2、3模块划分 5 第三章 详细设计 6 3.1概要设计 6 3.2函数调用图 7 3.3主要函数 7 第四章 用户手册 8 4.1 运行程序 8 4.2 程序出现问题 8 第五章 系统测试 9 第五章 项目总结 9 参考文献 10 附录 数据结构课程设计评分表 第一章 需求分析 1．1 选题要求 (1) 根据提供的文件读取数据以姓名做关键字创建二叉排序树 (2) 输入关键字在建立好的二叉树中查找，并输出相关信息。 (3) 输出比较查找次数，平均查找长度做性能分析。 1.2选题的背景与意义 （1） 选题背景 文件系统和数据库系统一般都采用树的数据结构数据，主要为排序和检索的效率。二叉树是一种最基本最典型的排序树，用于教学和研究树的特性，本身很少在实际中进行应用，因为缺点太明显了。二叉排序树是一种比较有用的折衷方案。数组的有哪些信誉好的足球投注网站比较方便，可以直接用下标链表与之相反，删除和插入元素很快，但查找很慢二叉排序树就既有链表的好处，也有数组的好处。在处理大批量的动态的数据是比较有用。A、熟练掌握二叉排序树的创建。 B、掌握二叉排序树的查找 C、掌握二叉排序树查找时的查找次数。 D、加深对二叉排序树结构和性质的理解，逐步培养解决实际问题的编程能力 1.3 课程设计目标 (1) 掌握一些基本算法框架的架构。 (2) 对比了解二叉排序树的优劣。 (3) 巩固课程知识的学习。 1.4 人员组成和分工 小组成员 主要分工细则 备注 王玉 二叉排序树的建立 细节方面相互探讨不断纠错察错不断改进 杨甜利 关键字查找 第二章 概要分析 2.1设计流程图 流程概述：以姓名做关键建立二叉排序树，并从键盘输入在二叉排序树中进行查找及性能分析。 2．2 部分数据（截图） 2.3模块划分 第三章 详细设计 3.1概要设计 ①读文件函数：fp=fopen(c:\\a.txt,r); ②插入并建立二叉排序树：Insert(BiTreeNode *root, DataType item) ③查找关键字：Search(BiTreeNode **root, DataType item) ④查找性能分析：SearchCount; 3.2函数调用图如下： 3.3主要函数 int main() { DataType A; FILE *fp; fp=fopen(c:\\a.txt,r); while(fscanf(fp,%s %d %s,A.ID,A.number,A.key )!=EOF){ int Insert(BiTreeNode *root, DataType item); } fclose(fp); return OK; BiTreeNode *root = NULL; while(1){ int p; char ID; printf(\n输入要查找的姓名(输入0查找结束)：); scanf(%s,ID); if(ID==0) break; InTraverse(root); if(p==0) printf(没有找到！); else printf(\n查找结果:报名号=%s 编号=%d 姓名=%s,A.ID,A.number ,A.key ); } } 第四章 用户手册 4.1 运行程序 读取文件创建二叉排序树，按照提示输入关键字，查找关键字。 4.2 程序运行出现的问题及解决办法 程序运行过程中会出现各种各样的问题，其中最主要的问题有 1.查找过程中出现了关键字输入时，却未像预期那样输出关键字信息，而总是输出最后个人的信息。 解决方法：在老师的纠正下发现函数的返回值的参数类型传递错。 2.查找次数的与总计数混合 解决方法：由于能力有限所以未能更好的对此点进行改正，所以选择了返回总计数并进行了性能分析。（希望以后可以有机会做的更好） 第五章 项目总结 本程序由我很一名成员对各个模块进行编写，之后由我们共同对各个模块进行进行组合调试，期间经过了老师的指导，让我们发现了我们许多的不足之处： ( 1 ) 许多概念性的知识