数据结构二叉排序树 哈希表Word下载.docx
《数据结构二叉排序树 哈希表Word下载.docx》由会员分享，可在线阅读，更多相关《数据结构二叉排序树 哈希表Word下载.docx（24页珍藏版）》请在冰点文库上搜索。
查找到该节点，将其删除，然后在插入修改后的节点。
函数说明：
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
intkey;
}Elemtype;
typedefstructhashtable
Elemtypeelem[Max_num];
intcount;
intsizeindex;
}HashTable;
1、宏定义表中最大存储个数
#defineMax_num15
2、表中元素初始化
Key值和数据值均为-1表示没有存储数据
#defineNo_key-1
#defineNo_data-1
四、程序代码：
1、二叉排序树代码：
#include<
stdio.h>
stdlib.h>
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;
left=NULL;
right=NULL;
continue;
}
p=T;
while（p）
if（n==p->
data）
printf（"
该数已经存在，请重新输入!
break;
q=p;
if（n<
p->
{j=1;
p=p->
left;
}
else
{j=2;
right;
}
if（p）continue;
if（j==1）
q->
left=（Sorttree*）malloc（sizeof（Sorttree））;
p=q->
elseif（j==2）
{q->
right=（Sorttree*）malloc（sizeof（Sorttree））;
return1;
voidInorder（BiTreeT）
if（T）
Inorder（T->
left）;
printf（"
%d"
T->
data）;
right）;
intSearch（BiTreeT,inte）
BiTreep;
p=T;
while（p）
if（e==p->
return1;
elseif（e>
p=p->
elsep=p->
return0;
voidAdd（BiTree&
T,inte）
intj=0;
q=p;
if（e<
j=1;
p=p->
else
{j=2;
data=e;
else
p=q->
voidDelete（BiTree&
BiTreep,q,s;
boolt=true;
T->
j=1;
if（e>
j=2;
if（p->
data==e）
if（（p->
left==NULL）&
&
（p->
right==NULL））
T=NULL;
p=NULL;
树已为空!
right==NULL）
T=T->
elseif（p->
left==NULL）
s=p->
q=s;
data=s->
data;
while（s->
left）
{
data=s->
left->
if（t）
t=false;
elseq=q->
s=s->
}
if（t）
p->
data=data;
if（s->
{
p->
}
elsewhile（s->
right）
s->
data=s->
right->
if（t）
t=false;
elseq=q->
s=s->
q->
else
{t=true;
q->
break;
if（j==1）
if（（p->
elseif（p->
left=p->
else
while（s->
t=false;
p->
if（s->
s->
elseq=q->
{t=true;
elseif（j==2）
right=p->
q=q->
if（s->
elsewhile（s->
{
voidmodify（BiTree&
intnewelem;
if（Search（T,e））
Delete（T,e）;
enterthenewelem:
scanf（"
newelem）;
Add（T,newelem）;
elseprintf（"
cannotfindthenumber:
voidmain（）
BiTreeT;
inte;
CreatST（T）;
Inorder（T）;
printf（"
pleaseenterthenuberyouwanttoadd:
//插入
e）;
if（Search（T,e））
thenumberhavealreadyexisted!
elseAdd（T,e）;
peaseenterthenumberyouwanttodelete:
//删除
if（!
Search（T,e））
cannotfindthenumber!
elseDelete（T,e）;
pleaseenterthenumberyouwanttomodify:
modify（T,e）;
运行结果：
建立二叉排序树：
添加数据：
删除数据：
修改数据：
3、哈希表代码：
time.h>
boolsuccess=false;
intvisit;
intHash（intkey）
returnkey%13;
intCreateHas（HashTable&
H）
inti;
intc;
Elemtypeelem;
pleaseenterthedata:
for（i=0;
i<
13;
i++）
elem.key=rand（）%100;
elem.data）;
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;
voidmain（）
HashTableH;
visit=0;
H.count=0;
H.sizeindex=15;
srand（unsigned（time（NULL）））;
H.elem[i].data=No_data;
H.elem[i].key=No_key;
CreateHas（H）;
i++）
%4d"
H.elem[i].data）;
查找次数：
%d\n"
visit）;
平均查找次数:
visit/13）;
五、课后练习：
构造哈希表，用链地址法解决冲突。
1、算法描述：
将哈希表每个节点添加一个next指针，当遇到与该节点有key值相同的元素是，将该元素的地址赋给next。
2、程序代码：
structele*next;
Elemtype*elem,*p;
intc,i;
elem=（Elemtype*）malloc（sizeof（Elemtype））;
elem->
elem->
key=rand（）%100;
next=NULL;
thekeyis%d:
elem->
key）;
c=Hash（elem->
if（!
H.elem[c].next）
H.elem[c].next=elem;
H.count++;
else{
p=H.elem[c].next;
while（p->
next）
p=p->
next;
next=elem;
Elemtype*p;
H.elem[i].data=No_data;
H.elem[i].key=No_key;
H.elem[i].next=NULL;
%dthis:
"
i）;
p=H.elem[i].next;
while（p）
p->
H.count）;
H.count/13）;
4、运行结果：
升级会员 