云南大学软件学院数据结构实验7.docVIP

实验难度： A □ B □ C □ 序号 学号 姓名 成绩 指导教师 （签名） 学　　期：　　2017秋季学期 任课教师: 　　 刘宇 　　 实验题目: 组员及组长: 　 　　 承担工作：　 　　 联系电话: 　 　　　　　 电子邮件: 　 完成提交时间： 年 月 日 　 一、【实验构思（Conceive）】(10%) （本部分） 对给定的二叉排序树，如果想知道某元素是否在其中出现，可以和根结点比较，如果相等结束；如果不等，若比其大，进入右子树；否则进入左子树；继续按照上面的方法，直到出现相等或者到某分支结束为止，返回查找信息。 （二）哈希表的查找算法及其原理： 给定K值，根据造表时设定的哈希函数求得哈希地址，若表中此位置上没有记录，则查找不成功；否则比较关键字，若和给定值相等，则查找成功；否则根据造表时设定的处理冲突的方法找到“下一地址”，直至哈希表中某个位置为“空”或者表中所记录的关键字等于给定值时为止。 二、【实验设计(Design)】(20%) （本部分） 抽象数据类型定义： typedef int KeyType; typedef struct { char *name; int namenum; }Name; typedef struct { Name data; int pos; }HashTable; typedef struct Hash //链地址结构 { Name data; int pos; struct Hash *next; }*Hash_P,Hash_L; typedef struct BSTNode { KeyType key; struct BSTNode *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%) （本部分） 主菜单： 哈希表的线性探测查找： 初始化： 查找： 显示： 哈希表的二次探测查找： 初始化： 查找： 显示： 哈希表的链地址探测查找： 初始化： 查找： 显示： 建立二叉排序树： 查询建立好的二叉排序树： 查询成功： 查询失败： 删除元素： 删除后查询： 添加元素： 插入后查询： 退出： 五、【实验总结】(10%) （本部分）Operate）】(10%) （注：选择C难度的才需要填写“项目运作描述”，其他难度的只需完成思考题） （） 采用链地址法： (1)拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短； (2)由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况； (3)开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间； (4)在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放地址法构造的散列表，删除结点不能简单地将被删结点的空间置为空，否则将截断在它之后填人散列表的同义词结点的查找路径。这是因为各种开放地址法中，空地址单元(即开放地址)都是查找失败的条件。因此在用开放地址法处理冲突的散列表上执行删除操作，只能在被删结点上做删除标记，而不能真正删除结点 七、【代码】(10%) （本部分）#includestdio.h #includemath.h #includeconio.h #includemalloc.h #includestdlib.h #define NameNum 30 //人名个数 #define HashNum 50 //哈希表的大小 #define H