数据结构 实验报告 实验内容：排序二叉树，及哈希表 系别班级：网络工程 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、...
VIP
