《数据结构二叉排序树 哈希表.docx》由会员分享，可在线阅读，更多相关《数据结构二叉排序树 哈希表.docx（16页珍藏版）》请在三一办公上搜索。
1、数据结构实验报告实验内容：排序二叉树，及哈希表系别班级：网络工程1001学号：201022074姓名：杨帆一、实验目的：熟悉排序二叉树和哈希表的结构及部分算法二、实验内容及要求：1、构造排序二叉树，并实现增删改查。2、构造哈希表，key值油随机数获得，自己选择解决冲突的算法。 并且计算查找次数及平均查找次数。三、算法描述：排序二叉树：节点的结构：typedef struct treeint data;struct tree *left;struct tree *right;Sorttree,*BiTree;1、插入：以输入的第一个数为树的根节点，之后输入的数若小于 根节点则插入为左孩子，若大于
2、根节点则插入为右孩子，若左右孩 子均已存在，则将小于根节点的与根节点的左孩子比较，将大于根 节点的与根节点的又孩子比较，然后重复上述操作。2、查找：递归，中序遍历二叉树。3、删除：首先找到与要删除的数相等的节点，若该节点为叶子节 点，则直接删除。当非叶子节点时，如果该节点在根节点的左边， 则用该节点的右子树中最大的节点将它替换掉，同理，如果该节点 在根节点的右边，则用该节的左子树中最小的节点将它替换掉。4、修改：查找到该节点，将其删除，然后在插入修改后的节点。函数说明：1、int CreatST(BiTree &T)/建 立排序二叉树2、void Inorder(BiTree T)/ 中序遍历
3、二叉树3、int Search(BiTree T,int e)/S 找4、void Add(BiTree &T,int e)/插入5、void Delete(BiTree &T,int e)/M 除6、void modify(BiTree &T,int e)/修改哈希表：哈希表即通过key值将数据存储到不同位置而建立起的表，通过key可 值直接找到数据的存储位置，减少查找所消耗的时间。所以我们需要 表节点中添加一个key来存储key值。当添加元素的key值与表中元素 key值相同时，查看下一个存储位置是否有元素，若没有将该元素存储 在新找到的位置否则继续找下一位置，直到找到可存储的位置。Key
4、值随机产生。哈希表结构：typedef struct eleint data;int key;Elemtype;typedef struct hashtableElemtype 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 struct treeint data;struct
5、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(ndata
6、)j=1;p=p-left;elsej=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;return 1;void Inorder(BiTree T)if(T)Inorder(T-left);printf(%d
7、,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-left;elsej=2；p=p-right;if(j=1)q-left=(Sorttree*)malloc(sizeof(Sorttree);p=q-left
8、;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(edata)j=1;if(eT-data)j=2;if(p-data=e)if (p-left=NULL)&(p-right=NULL)T=NULL;p=NULL;printf(树已为空!n”
9、);elseif(p-right=NULL)T=T-left;else if (p-left=NULL)T=T-right;elses=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-right;s=s-right;q-ri
10、ght=NULL;else t=true;q-left=NULL;while(p)if(e=p-data)break;q=p;if(edata)p=p-left;elsep=p-right;if(j=1)if(p-left=NULL)&(p-right=NULL) q-left=NULL;else if(p-left=NULL)q-left=p-right;else if(p-right=NULL)q-left=p-left;elses=p-right;q=s;data=s-data;while (s-left)data=s-left-data;if(t)t=false;else q=q-le
11、ft;s=s-left;if(t)p-data=data;if (s-right=NULL)p-data=data;p-right=NULL;elsewhile (s-right)s-data=s-right-data;if(t)t=false;else q=q-right;s=s-right;q-right=NULL;elset=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-r
12、ight=p-left;elses=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-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;elset=true;q-left=NULL;void modify(BiTree &T,int e
13、)int newelem;if (Search(T,e)Delete(T,e);printf(enter the new elem:n);scanf(%d”,&newelem);Add(T,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
14、number have already existed!n);else Add(T,e);Inorder(T);printf(n);printf(pease enter 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);I
15、norder(T);printf(n);运行结果：建立二叉排序树：输入数据;数据：翰入数据，9输入数据，输入数据：诚数据：弟入数据，踊入数据;-13 4 5 6 7 8 ?添加数据:please enter the nuher you u-ant to add: 10 3456789 IB删除数据:pease enter the nunber you uant to delete E4 5 6 7 8 9 10修改数据:please enter tlie numbep you. uant to modify 8enter the neu clen:114 5 6 7 9 10 11Ppess
16、anu heu to continu.e_3、哈希表代码：#include #include #include #define Max_num 15#define No_key -1#define No_data -1 bool success=false;int visit;typedef struct eleint data;int key;Elemtype;typedef struct hashtableElemtype elemMax_num;int count;int sizeindex;HashTable;int Hash(int key)return key%13;int Cre
17、ateHas(HashTable &H)int i;int c;Elemtype 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+
18、)printf(%4d”,H.elemi.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=fals
19、e;int visit;typedef struct eleint data;int key;struct ele *next;Elemtype;typedef struct hashtableElemtype 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()%
20、100;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、运行结果:
