数据结构二叉排序树 哈希表.docx
《数据结构二叉排序树 哈希表.docx》由会员分享，可在线阅读，更多相关《数据结构二叉排序树 哈希表.docx（24页珍藏版）》请在冰点文库上搜索。
数据结构二叉排序树哈希表
数据结构
实验报告
实验内容：
排序二叉树，及哈希表
系别班级：
网络工程1001
学号：
201022074
姓名：
杨帆
一、实验目的：
熟悉排序二叉树和哈希表的结构及部分算法
二、实验内容及要求：
1、构造排序二叉树，并实现增删改查。
2、构造哈希表，key值油随机数获得，自己选择解决冲突的算法。
并且计算查找次数及平均查找次数。
三、算法描述：
排序二叉树：
节点的结构：
typedefstructtree
{
intdata;
structtree*left;
structtree*right;
}Sorttree,*BiTree;
1、插入：
以输入的第一个数为树的根节点，之后输入的数若小于根节点则插入为左孩子，若大于根节点则插入为右孩子，若左右孩子均已存在，则将小于根节点的与根节点的左孩子比较，将大于根节点的与根节点的又孩子比较，然后重复上述操作。
2、查找：
递归，中序遍历二叉树。
3、删除：
首先找到与要删除的数相等的节点，若该节点为叶子节点，则直接删除。
当非叶子节点时，如果该节点在根节点的左边，则用该节点的右子树中最大的节点将它替换掉，同理，如果该节点在根节点的右边，则用该节的左子树中最小的节点将它替换掉。
4、修改：
查找到该节点，将其删除，然后在插入修改后的节点。
函数说明：
1、intCreatST（BiTree&T）//建立排序二叉树
2、voidInorder（BiTreeT）//中序遍历二叉树
3、intSearch（BiTreeT,inte）//查找
4、voidAdd（BiTree&T,inte）//插入
5、voidDelete（BiTree&T,inte）//删除
6、voidmodify（BiTree&T,inte）//修改
哈希表：
哈希表即通过key值将数据存储到不同位置而建立起的表，通过key可值直接找到数据的存储位置，减少查找所消耗的时间。
所以我们需要表节点中添加一个key来存储key值。
当添加元素的key值与表中元素key值相同时，查看下一个存储位置是否有元素，若没有将该元素存储在新找到的位置否则继续找下一位置，直到找到可存储的位置。
Key值随机产生。
哈希表结构：
typedefstructele
{
intdata;
intkey;
}Elemtype;
typedefstructhashtable
{
Elemtypeelem[Max_num];
intcount;
intsizeindex;
}HashTable;
1、宏定义表中最大存储个数
#defineMax_num15
2、表中元素初始化
Key值和数据值均为-1表示没有存储数据
#defineNo_key-1
#defineNo_data-1
四、程序代码：
1、二叉排序树代码：
#include
#include
typedefstructtree
{
intdata;
structtree*left;
structtree*right;
}Sorttree,*BiTree;
intCreatST（BiTree&T）
{
BiTreep,q;
intj,n=1;
while（n>0）
{
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）
{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;
}
elseif（j==2）
{q->right=（Sorttree*）malloc（sizeof（Sorttree））;
p=q->right;p->data=n;p->left=NULL;p->right=NULL;}
}
return1;
}
voidInorder（BiTreeT）
{
if（T）
{
Inorder（T->left）;
printf（"%d",T->data）;
Inorder（T->right）;
}
}
intSearch（BiTreeT,inte）
{
BiTreep;
p=T;
while（p）
{
if（e==p->data）
return1;
elseif（e>p->data）
p=p->right;
elsep=p->left;
}
return0;
}
voidAdd（BiTree&T,inte）
{
BiTreep,q;
p=T;
intj=0;
while（p）
{
q=p;
if（edata）
{
j=1;
p=p->left;
}
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;}
}
voidDelete（BiTree&T,inte）
{
BiTreep,q,s;
intdata;
boolt=true;
p=T;
intj=0;
if（edata）
j=1;
if（e>T->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;
elseif（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;
elseq=q->left;
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;
elseq=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;
elseif（p->left==NULL）
q->left=p->right;
elseif（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;
elseq=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;
elseq=q->right;
s=s->right;
}
q->right=NULL;
}
else
{t=true;
q->left=NULL;}
}
}
elseif（j==2）
{
if（（p->left==NULL）&&（p->right==NULL））
q->right=NULL;
elseif（p->left==NULL）
q->right=p->right;
elseif（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->data=data;
if（s->left==NULL）
{
p->data=data;
p->left=NULL;
}
elsewhile（s->left）
{
s->data=s->left->data;
if（t）
t=false;
elseq=q->left;
s=s->left;
}
q->left=NULL;
}
else
{t=true;
q->left=NULL;}
}
}
}
voidmodify（BiTree&T,inte）
{
intnewelem;
if（Search（T,e））
{
Delete（T,e）;
printf（"enterthenewelem:
\n"）;
scanf（"%d",&newelem）;
Add（T,newelem）;
}
elseprintf（"cannotfindthenumber:
\n"）;
}
voidmain（）
{
BiTreeT;
inte;
T=NULL;
CreatST（T）;
Inorder（T）;printf（"\n"）;
printf（"pleaseenterthenuberyouwanttoadd:
\n"）;//插入
scanf（"%d",&e）;
if（Search（T,e））
printf（"thenumberhavealreadyexisted!
\n"）;
elseAdd（T,e）;
Inorder（T）;printf（"\n"）;
printf（"peaseenterthenumberyouwanttodelete:
\n"）;//删除
scanf（"%d",&e）;
if（!
Search（T,e））
printf（"cannotfindthenumber!
\n"）;
elseDelete（T,e）;
Inorder（T）;printf（"\n"）;
printf（"pleaseenterthenumberyouwanttomodify:
\n"）;
scanf（"%d",&e）;
modify（T,e）;
Inorder（T）;printf（"\n"）;
}
运行结果：
建立二叉排序树：
添加数据：
删除数据：
修改数据：
3、哈希表代码：
#include
#include
#include
#defineMax_num15
#defineNo_key-1
#defineNo_data-1
boolsuccess=false;
intvisit;
typedefstructele
{
intdata;
intkey;
}Elemtype;
typedefstructhashtable
{
Elemtypeelem[Max_num];
intcount;
intsizeindex;
}HashTable;
intHash（intkey）
{
returnkey%13;
}
intCreateHas（HashTable&H）
{
inti;
intc;
Elemtypeelem;
printf（"pleaseenterthedata:
\n"）;
for（i=0;i<13;i++）
{
elem.key=rand（）%100;
scanf（"%d",&elem.data）;
printf（"zhekeyis:
%4d\n",elem.key）;
c=Hash（elem.key）;
while（!
success）
{
visit++;
if（H.elem[c].key==No_key）
{
H.elem[c]=elem;
H.count++;
success=true;
}
else
if（c>=13）
c=0;
elsec++;
}
success=false;
}
return1;
}
voidmain（）
{
HashTableH;
inti;
visit=0;
H.count=0;
H.sizeindex=15;
srand（unsigned（time（NULL）））;
for（i=0;i<13;i++）
{
H.elem[i].data=No_data;
H.elem[i].key=No_key;
}
CreateHas（H）;
for（i=0;i<13;i++）
printf（"%4d",H.elem[i].data）;
printf（"\n"）;
printf（"查找次数：
\n"）;
printf（"%d\n",visit）;
printf（"平均查找次数:
\n"）;
printf（"%d\n",visit/13）;
}
运行结果：
五、课后练习：
构造哈希表，用链地址法解决冲突。
1、算法描述：
将哈希表每个节点添加一个next指针，当遇到与该节点有key值相同的元素是，将该元素的地址赋给next。
2、程序代码：
#include
#include
#include
#defineMax_num15
#defineNo_key-1
#defineNo_data-1
boolsuccess=false;
intvisit;
typedefstructele
{
intdata;
intkey;
structele*next;
}Elemtype;
typedefstructhashtable
{
Elemtypeelem[Max_num];
intcount;
intsizeindex;
}HashTable;
intHash（intkey）
{
returnkey%13;
}
intCreateHas（HashTable&H）
{
Elemtype*elem,*p;
intc,i;
printf（"pleaseenterthedata:
\n"）;
for（i=0;i<13;i++）
{
elem=（Elemtype*）malloc（sizeof（Elemtype））;
scanf（"%d",&elem->data）;
elem->key=rand（）%100;
elem->next=NULL;
printf（"thekeyis%d:
\n",elem->key）;
c=Hash（elem->key）;
if（!
H.elem[c].next）
{
H.elem[c].next=elem;
H.count++;
}
else{
p=H.elem[c].next;
while（p->next）
{
H.count++;
p=p->next;
}
p->next=elem;
}
}
return1;
}
voidmain（）
{
HashTableH;
Elemtype*p;
inti;
visit=0;
H.count=0;
H.sizeindex=15;
srand（unsigned（time（NULL）））;
for（i=0;i<13;i++）
{
H.elem[i].data=No_data;
H.elem[i].key=No_key;
H.elem[i].next=NULL;
}
CreateHas（H）;
for（i=0;i<13;i++）
{
printf（"%dthis:
",i）;
p=H.elem[i].next;
while（p）
{
printf（"%4d",p->data）;
p=p->next;
}
printf（"\n"）;
}
printf（"\n"）;
printf（"查找次数：
\n"）;
printf（"%d\n",H.count）;
printf（"平均查找次数:
\n"）;
printf（"%d\n",H.count/13）;
}
4、运行结果：
升级会员 