云南大学软件学院数据结构试验汇报试验难度:A□B□C□序号学号姓名成绩指导老师(署名)学期: 秋季学期任课老师: 刘宇试验题目: 组员及组长: 负担工作: 联络电话: 电子邮件: 完成提交时间:年月日一、【试验构思(Conceive)】(10%)(本部分应包含:描述试验实现基础思绪,包含所用到离散数学、工程数学、程序设计等相关知识,对问题进行概要性地分析)(一)二叉排序树查找算法及算法原理:对给定二叉排序树,假如想知道某元素是否在其中出现,能够和根结点比较,假如相等结束;假如不等,若比其大,进入右子树;不然进入左子树;继续根据上面方法,直到出现相等或到某分支结束为止,返回查找信息。(二)哈希表查找算法及其原理:给定K值,依据造表时设定哈希函数求得哈希地址,若表中此位置上没有统计,则查找不成功;不然比较关键字,若和给定值相等,则查找成功;不然依据造表时设定处理冲突方法找到“下一地址”,直至哈希表中某个位置为“空”或表中所统计关键字等于给定值时为止。二、【试验设计(Design)】(20%)(本部分应包含:抽象数据类型定义和基础操作说明,程序包含模块和各模块间调用关系,关键算法伪码描述及程序步骤图等,如有界面则需包含界面设计,功效说明等)抽象数据类型定义:typedefintKeyType;typedefstruct{char*name;intnamenum;}Name;typedefstruct{Namedata;intpos;}HashTable;typedefstructHash//链地址结构{Namedata;intpos;structHash*next;}*Hash_P,Hash_L;typedefstructBSTNode{KeyTypekey;structBSTNode*lc,*rc;}*BSTree;算法及各模块实现见第七部分【代码】调用关系:三、【实现(Implement)】(30%)(本部分应包含:抽象数据类型各操作具体实现代码、关键操作具体算法实现、函数实现,主程序实现等,并给出关键算法时间复杂度分析。如有界面则需包含界面关键实现方法等。)具体实现代码见第七部分【代码】算法时间复杂度分析:哈希表查找:O(1)插入一个元素时,最坏情况下时间复杂度为O(N),因为它有可能探测了N-1个元素!假如二叉排序树是平衡,则n个节点二叉排序树高度为Log2n+1,其查找效率为O(Log2n),近似于折半查找。假如二叉排序树完全不平衡,则其深度可达成n,查找效率为O(n),退化为次序查找。通常,二叉排序树查找性能在O(Log2n)到O(n)之间。四、【测试结果(Testing)】(10%)(本部分应包含:对试验测试结果,应具体列出每次测试所输入数据和输出数据,并对测试结果进行分析,可附截图)主菜单:哈希表线性探测查找:初始化:查找:显示:哈希表二次探测查找: 初始化: 查找: 显示:哈希表链地址探测查找:初始化: 查找: 显示:建立二叉排序树:查询建立好二叉排序树:查询成功:查询失败:删除元素:
云南大学软件学院数据结构实验7样本 来自淘豆网m.daumloan.com转载请标明出处.
