- 1、本文档共24页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
课程设计报告
问题描述:
(1) 散列法中,散列函数构造方法多种多样,同时对于同一散列函数解决冲突的方法也可以不同。两者是影响查询算法性能的关键因素。几种典型的散列函数构造方法,不同的解决冲突方法对查询性能的影响。typedef struct
{
int key;
int si;
}HashTable1;
void CreateHashTable1(HashTable1 *H,int *a,int num)//哈希表线性探测在散列;
{
int i,d,cnt;
for(i=0;iHashSize;i++)
{
H[i].key=0;
H[i].si=0;
}
for(i=0;inum;i++)
{
cnt=1;
d=a[i]%HashSize;
if(H[d].key==0)
{
H[d].key=a[i];
H[d].si=cnt;
}
else
{
do
{
d=(d+1)%HashSize;
cnt++;
}while(H[d].key!=0);
H[d].key=a[i];
H[d].si=cnt;
}
}
printf(\n线性再探索哈希表已建成!);
}
用二次探测再散列建立哈希表,代码实现如下:
void CreateHash3(HashTable3 *h,int *a,int num)//二次探索表
{
int i,p=-1,c,pp;
for(i=0;inum;i++)
{
c=0;
p=a[i]%HashSize;
pp=p;
while(h-elem[pp]!=NULL)
{
pp=Collision(p,c);
if(pp0)
{
printf(第%d个记录无法解决冲突\n,i+1);
continue;
}
}
h-elem[pp]=(a[a[i]]);
h-count++;
printf(第%d个记录冲突次数为%d\n,i+1,c);
}
printf(\n建表完成!\n此哈希表容量为%d,当前表内存储的记录个数%d.\n,HashSize,h-count);
}
二次探测再散列法解决冲突
int Collision(int p,int c)
{
int i,q;
i=c/2+1;
while(iHashSize)
{
if(c%2==0)
{
c++;
q=(p+i*i)%HashSize;
if(q=0)
return q;
else
i=c/2+1;
}
else
{
q=(p-i*i)%HashSize;
c++;
if(q=0)return q;
else i=c/2+1;
}
}
return (-1);
}
用线性再散列法查找,代码实现如下:
void SearchHash1(HashTable1 *h,int data)
{
int d;
d=data%HashSize;
if(h[d].key==data)
printf(数字%d的探查次数为:%d\n,h[d].key,h[d].si);
else
{
do
d=(d+1)%HashSize;
while(h[d].key!=data dHashSize);
if(dHashSize)
printf(数字%d的探查次数为:%d\n,h[d].key,h[d].si);
else
printf(没有查找到你所输入的数\n);
}
用二次探测再散列法查找
void SearchHash2(HashTable2 * h[],int data,int num)
{
int d;
Node *q;
d=data%num;
q=h[d]-link;
while(q-key!=data q-next!=NULL)
q=q-next;
if(q-next!=NULL)
printf(数字%d的查找次数为:%d\n,q-key,q-next);
else
printf(没有找到你要查找的那个数\n);
}
用链地址法查找,代码实现如下:
void CreateHashTable2(HashTable2 *ht[],int *a,int num)//哈希表链地址;
{
int i,d,cnt;
Node *s,*q;
for(i=0;inum; i++)
{
ht[i]=(HashTable2 *)m
文档评论(0)