数据结构二叉排序树哈希表.docVIP

数据结构 实验报告 实验内容：排序二叉树，及哈希表 系别班级：网络工程 1001 学号：201022074 姓名：杨帆 实验目的： 熟悉排序二叉树和哈希表的结构及部分算法 实验内容及要求： 构造排序二叉树，并实现增删改查。 构造哈希表，key值油随机数获得，自己选择解决冲突的算法。并且计算查找次数及平均查找次数。 算法描述： 排序二叉树： 节点的结构： typedef struct tree { int data; struct tree *left; struct tree *right; }Sorttree,*BiTree; 插入：以输入的第一个数为树的根节点，之后输入的数若小于根节点则插入为左孩子，若大于根节点则插入为右孩子，若左右孩子均已存在，则将小于根节点的与根节点的左孩子比较，将大于根节点的与根节点的又孩子比较，然后重复上述操作。 查找：递归，中序遍历二叉树。 删除：首先找到与要删除的数相等的节点，若该节点为叶子节点，则直接删除。当非叶子节点时，如果该节点在根节点的左边，则用该节点的右子树中最大的节点将它替换掉，同理，如果该节点在根节点的右边，则用该节的左子树中最小的节点将它替换掉。 修改：查找到该节点，将其删除，然后在插入修改后的节点。 函数说明： int CreatST(BiTree T)//建立排序二叉树 void Inorder(BiTree T)//中序遍历二叉树 int Search(BiTree T,int e)//查找 void Add(BiTree T,int e)//插入 void Delete(BiTree T,int e)//删除 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; 宏定义表中最大存储个数 #define Max_num 15 表中元素初始化 Key值和数据值均为-1表示没有存储数据 #define No_key -1 #define No_data -1 四、程序代码： 1、二叉排序树代码： #include stdio.h #include stdlib.h typedef struct tree { int data; struct tree *left; struct tree *right; }Sorttree,*BiTree; int CreatST(BiTree T) { BiTree p,q; int j,n=1; while (n0) { printf(输入数据：\n); scanf(%d,n); if(n==-1) break; if(T==NULL) { T=(Sorttree*)malloc(sizeof(Sorttree)); T-data=n; T-left=NULL; T-right=NULL; continue; } p=T; while (p) { if(n==p-data) { printf(该数已经存在，请重新输入!\n); break; } q=p; if(np-data) {j=1;p=p-left;} else {j=2;p=p-right;} } if(p)continue; if(j==1) { q-left=(Sorttree*)malloc(sizeof(Sorttree)); p=q-left;p-data=n;p-left=NULL;p-right=NULL; } else if(j==2) { q-right=(Sorttree*)malloc(sizeof(Sorttree));