数据结构 实验报告 实验内容:排序二叉树,及哈希表 系别班级:网络工程 1001 学号:201022074 姓名:杨帆 一、实验目的: 熟悉排序二叉树和哈希表的结构及部分算法 二、实验内容及要求: 1、 构造排序二叉树,并实现增删改查。 2、 构造哈希表,key 值油随机数获得,自己选择解决冲突的算法。并且计算查找次数及平均查找次数。 三、算法描述: 排序二叉树: 节点的结构: typedef struct tree { int data; struct tree *left; struct tree *right; }Sorttree,*BiTree; 1、 插入:以输入的第一个数为树的根节点,之后输入的数若小于根节点则插入为左孩子,若大于根节点则插入为右孩子,若左右孩子均已存在,则将小于根节点的与根节点的左孩子比较,将大于根节点的与根节点的又孩子比较,然后重复上述操作。 2、 查找:递归,中序遍历二叉树。 3、 删除:首先找到与要删除的数相等的节点,若该节点为叶子节点,则直接删除。当非叶子节点时,如果该节点在根节点的左边,则用该节点的右子树中最大的节点将它替换掉,同理,如果该节点在根节点的右边,则用该节的左子树中最小的节点将它替换掉。 4、 修改:查找到该节点,将其删除,然后在插入修改后的节点。 函数说明: 1、 int CreatST(BiTree &T)//建立排序二叉树 2、 void Inorder(BiTree T)//中序遍历二叉树 3、 int Search(BiTree T,int e)//查找 4、 void Add(BiTree &T,int e)//插入 5、 void Delete(BiTree &T,int e)//删除 6、 void modify(BiTree &T,int e)//修改 哈希表: 哈希表即通过 key 值将数据存储到不同位置而建立起的表,通过 key 可值直接找到数据的存储位置, 减少查找所消耗的时间。所以我们需要表节点中添加一个 key 来存储 key 值。当添加元素的 key 值与表中元素key 值相同时,查看下一个存储位置是否有元素,若没有将该元素存储在新找到的位置否则继续找下一位置,直到找到可存储的位置。 Key 值随机产生。 哈希表结构: typedef struct ele { int data; int key; }Elemtype; typedef struct hashtable { Elemtype elem[Max_num]; int count; int sizeindex; }HashTable; 1、 宏定义表中最大存储个数 #define Max_num 15 2、 表中元素初始化 Key 值和数据值均为-1 表示没有存储数据 #define No_key -1 #define No_data -1 四、程序代码: 1、...