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

1、数据结构二叉排序树 哈希表数据结构实验报告实验内容：排序二叉树，及哈希表 系别班级：网络工程 1001学号：201022074姓名：杨帆一、 实验目的：熟悉排序二叉树和哈希表的结构及部分算法二、 实验内容及要求：1、 构造排序二叉树，并实现增删改查。2、 构造哈希表，key值油随机数获得，自己选择解决冲突的算法。并且计算查找次数及平均查找次数。三、 算法描述：排序二叉树：节点的结构：typedef struct tree int data; struct tree *left; struct tree *right;Sorttree,*BiTree;1、 插入：以输入的第一个数为树的根节点，之

2、后输入的数若小于根节点则插入为左孩子，若大于根节点则插入为右孩子，若左右孩子均已存在，则将小于根节点的与根节点的左孩子比较，将大于根节点的与根节点的又孩子比较，然后重复上述操作。2、 查找：递归，中序遍历二叉树。3、 删除：首先找到与要删除的数相等的节点，若该节点为叶子节点，则直接删除。当非叶子节点时，如果该节点在根节点的左边，则用该节点的右子树中最大的节点将它替换掉，同理，如果该节点在根节点的右边，则用该节的左子树中最小的节点将它替换掉。4、 修改：查找到该节点，将其删除，然后在插入修改后的节点。函数说明：1、 int CreatST(BiTree &T)/建立排序二叉树2、 void In

3、order(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值相同时，查看下一个存储位置是否有元素，若没有将该元素存储在新找到的位置否则继续找

4、下一位置，直到找到可存储的位置。Key值随机产生。哈希表结构：typedef struct ele int data; int key;Elemtype;typedef struct hashtable Elemtype elemMax_num; int count; int sizeindex;HashTable;1、 宏定义表中最大存储个数#define Max_num 152、 表中元素初始化Key值和数据值均为-1表示没有存储数据#define No_key -1#define No_data -1四、程序代码：1、二叉排序树代码：#include #include typedef s

5、truct 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-dat

6、a) printf(该数已经存在，请重新输入!n); break; q=p; if(ndata) 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); p=q-right;p-data=n;p-left=NULL;p-right=NULL; retur

7、n 1;void Inorder(BiTree T) if(T) Inorder(T-left); printf(%d ,T-data); Inorder(T-right); int Search(BiTree T,int e) BiTree p; p=T; while(p) if(e=p-data) return 1; else if(ep-data) p=p-right; else p=p-left; return 0;void Add(BiTree &T,int e) BiTree p,q; p=T; int j=0; while(p) q=p; if(edata) j=1; p=p-l

8、eft; else j=2; p=p-right; if(j=1) q-left=(Sorttree*)malloc(sizeof(Sorttree); p=q-left;p-data=e;p-left=NULL;p-right=NULL; else q-right=(Sorttree*)malloc(sizeof(Sorttree); p=q-right;p-data=e;p-left=NULL;p-right=NULL;void Delete(BiTree &T,int e) BiTree p,q,s; int data; bool t=true; p=T; int j=0; if(eda

9、ta) j=1; if(eT-data) j=2; if(p-data=e) if (p-left=NULL)&(p-right=NULL) T=NULL; p=NULL; printf(树已为空!n); else if(p-right=NULL) T=T-left; else if (p-left=NULL) T=T-right; else s=p-right; q=s; data=s-data; while (s-left) data=s-left-data; if(t) t=false; else q=q-left; s=s-left; if(t) p-data=data; if (s-

10、right=NULL) p-data=data; p-right=NULL; else while (s-right) s-data=s-right-data; if(t) t=false; else q=q-right; s=s-right; q-right=NULL; else t=true; q-left=NULL; while(p) if(e=p-data) break; q=p; if(edata) p=p-left; else p=p-right; if(j=1) if(p-left=NULL)&(p-right=NULL) q-left=NULL; else if(p-left=

11、NULL) q-left=p-right; else if(p-right=NULL) q-left=p-left; else s=p-right; q=s; data=s-data; while (s-left) data=s-left-data; if(t) t=false; else q=q-left; s=s-left; if(t) p-data=data; if (s-right=NULL) p-data=data; p-right=NULL; else while (s-right) s-data=s-right-data; if(t) t=false; else q=q-righ

12、t; s=s-right; q-right=NULL; else t=true; q-left=NULL; else if(j=2) if(p-left=NULL)&(p-right=NULL) q-right=NULL; else if(p-left=NULL) q-right=p-right; else if(p-right=NULL) q-right=p-left; else s=p-left; q=s; data=s-data; while (s-right) data=s-right-data; if(t) q=q-right; t=false; s=s-right; if(t) p

13、-data=data; if (s-left=NULL) p-data=data; p-left=NULL; else while (s-left) s-data=s-left-data; if(t) t=false; else q=q-left; s=s-left; q-left=NULL; else t=true; q-left=NULL; void modify(BiTree &T,int e) int newelem; if (Search(T,e) Delete(T,e); printf(enter the new elem:n); scanf(%d,&newelem); Add(T

14、,newelem); else printf(can not find the number:n);void main () BiTree T; int e; T=NULL; CreatST(T); Inorder(T);printf(n); printf(please enter the nuber you want to add:n);/插入 scanf(%d,&e); if(Search(T,e) printf(the number have already existed!n); else Add(T,e); Inorder(T);printf(n); printf(pease ent

15、er the number you want to delete:n);/删除 scanf(%d,&e); if(!Search(T,e) printf(can not find the number!n); else Delete(T,e); Inorder(T);printf(n); printf(please enter the number you want to modify:n); scanf(%d,&e); modify(T,e); Inorder(T);printf(n);运行结果：建立二叉排序树：添加数据：删除数据：修改数据：3、 哈希表代码：#include #includ

16、e #include #define Max_num 15#define No_key -1#define No_data -1bool success=false;int visit;typedef struct ele int data; int key;Elemtype;typedef struct hashtable Elemtype elemMax_num; int count; int sizeindex;HashTable;int Hash(int key) return key%13;int CreateHas(HashTable &H) int i; int c; Elemt

17、ype elem; printf(please enter the data:n); for (i=0;i=13) c=0; else c+; success=false; return 1;void main() HashTable H; int i; visit=0; H.count=0; H.sizeindex=15; srand(unsigned(time(NULL); for (i=0;i13;i+) H.elemi.data=No_data; H.elemi.key=No_key; CreateHas(H); for (i=0;i13;i+) printf(%4d,H.elemi.

18、data); printf(n); printf(查找次数：n); printf(%dn,visit); printf(平均查找次数:n); printf(%dn,visit/13);运行结果：五、课后练习：构造哈希表，用链地址法解决冲突。1、算法描述：将哈希表每个节点添加一个next指针，当遇到与该节点有key值相同的元素是，将该元素的地址赋给next。2、程序代码：#include #include #include #define Max_num 15#define No_key -1#define No_data -1bool success=false;int visit;typed

19、ef struct ele int data; int key; struct ele *next;Elemtype;typedef struct hashtable Elemtype elemMax_num; int count; int sizeindex;HashTable;int Hash(int key) return key%13;int CreateHas(HashTable &H) Elemtype *elem,*p; int c,i; printf(please enter the data:n); for (i=0;idata); elem-key=rand()%100;

20、elem-next=NULL; printf(the key is %d:n,elem-key); c=Hash(elem-key); if(!H.elemc.next) H.elemc.next=elem; H.count+; else p=H.elemc.next; while (p-next) H.count+; p=p-next; p-next=elem; return 1;void main() HashTable H; Elemtype *p; int i; visit=0; H.count=0; H.sizeindex=15; srand(unsigned(time(NULL); for (i=0;i13;i+) H.elemi.data=No_data; H.elemi.key=No_key; H.elemi.next=NULL; CreateHas(H); for (i=0;idata); p=p-next; printf(n); printf(n); printf(查找次数：n); printf(%dn,H.count); printf(平均查找次数:n); printf(%dn,H.count/13);4、 运行结果：