云南大学软件学院数据结构实验7.doc
文本预览下载声明
^.
云南大学软件学院 数据结构实验报告
云南大学软件学院 数据结构实验报告
实验难度： 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%)
（本部分应包括：自己在实验中完成的任务，及存在的问题，所完成实验过程中的具体经验总结、心得）
哈希表问题，在于存储位置和关键字之间建立对应关系f，根据对应关系f找到定值K。若结构中存在关键字和定值K相等的记录，必定在f（K）的存储位置上，由此可以省去比较过程，直接找到所查记录。哈希表其实不难，课程设计考验的是我们的学习态度、独立思考问题、和解决问题的能力。在学习哈希表的过程中要注意对应关系和关键字的建立，并且要和二叉树结合学习，不然很容易出错。
六、思考题或【项目运作描述（Operate）】(10%)
（注：选择C难度的才需要填写“项目运作描述”，其他难
显示全部