首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
在用除余法作为散列函数线性探测解决冲突的散列表中,写一删除关键字的算法,要求将所有可以前移的元素前移去填充被删除的空位,以保证探测序列不至于断裂。
在用除余法作为散列函数线性探测解决冲突的散列表中,写一删除关键字的算法,要求将所有可以前移的元素前移去填充被删除的空位,以保证探测序列不至于断裂。
admin
2017-01-04
30
问题
在用除余法作为散列函数线性探测解决冲突的散列表中,写一删除关键字的算法,要求将所有可以前移的元素前移去填充被删除的空位,以保证探测序列不至于断裂。
选项
答案
首先计算关键字的散列地址,若该地址为空,则空操作;若该地址有关键字,但与给定值不等,则用解决冲突的方法去查找给定值;若该地址有关键字且与给定值相等,则执行删除。题目要求将所有可以前移的元素前移去填充被删除的空位,以保证探测序列不断裂。由于用线性探测解决冲突,设被删除元素的散列地址为i,则其余m一1(m为表长)个位置均可能是同义词。查找同义词的操作直到碰到空地址或循环一圈回到i才能结束。为了提高算法效率,减少数据移动,应将最后一个同义词前移填充被删除关键字。 void HsDelete(rectype HS[],K){ //在以除余法为散列函数线性探测解决冲突的散列表HS中,删除关键字K int i=K%P: //以造表所用的除余法计算关键字K的散列地址 if(HS[i]==null){printf(”散列表中无被删关键字”); exit(0); } //此处null代表散列表初始化时的空值 switch(HS[i]==k){ case true:del(HS,i,j,K);break; case false:di=1;j=(i+di)%m; //m为表长 while(HS[j]!=null&&HS[j]!=K&&J!=i){ //查找关键字K di=di+1: j=(i+di)%m; } if(HS[j]==K)del(HS,i,j,K); else{printf(”散列表中无被删关键字”);exit(0);} }//switch } void del(rectype Hs[],in i,int j,rectype K){ //在散列表HS中,删除关键字K,K的散列地址是i,因解决冲突而将其物理地 //置于表中位置j。算法查找关键字K的同义词,将其最后一个同义词移到位置j, //并将其同义词的位置置空 di=1:last=j;x=(j+di)%m; //探测地址序列,last记K的最后一个同义词的位置 while(x!=i){ //可能要探测一圈 if(HS[x]==null)break; //探测到空位置,结束探测 else if(HS[x]%P==i)last=x; //关键字K的同义词 di=di+1;x=(j+di)%m; //取下一地址探测 } HS[j]=HS[last];HS[last]=null; //将哈希地址last的关键字移到哈希地址j } 算法讨论:由于用线性探测解决冲突,可能发生“二次聚集”(两个第一哈希地址不同的记录争夺同一后继哈希地址)。像上面这样处理后,对于哈希地址为i的记录没有问题了,但由于将地址j置空,有可能截断了其他记录的探测通路。最明显的是哈希地址为j的记录就查不到了。解决的办法是继续调整,直到当前哈希表中的每个记录的查找都是正确的为止。这里不再深入讨论。
解析
转载请注明原文地址:https://kaotiyun.com/show/eQRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
简述隋唐民族关系的特点、作用。
简述雅典民主政治的形成过程。
1925年爆发的当时世界上罢工时间最长的一次斗争是()。
光绪元年七月,清政府迫于()强烈要求派一位使臣到其国,()成为中国第一个驻外公使
宋文帝于元嘉年间发动的对北魏的北伐战争,此战又称()。
在下面哪本著作中以异化劳动理论的形式阐述了一种新的科学世界观的雏形?()
1940年毛泽东的《新民主主义论》:“而所谓民主主义,现在已不是旧范畴的民主主义,已不是日民主主义,而是新范畴的民主主义,而是新民主主义”。毛泽东分民主革命的两个阶段主要依据是
唐朝时期,每丁服徭役二十天,是为正役,国家若不需要其服役,则每丁可按照每天交纳绢三尺或布三尺七寸五分的标准,交足二十天的数额以代役,称为()。
高度为4的4阶B树最多可容纳()个关键字(根是第1层)。
假定采用带头结点的单链表保存单词,当两个单词有相同的后缀时,则可共享卡H同的后缀存储空间。例如,“loading”和“being”的存储映像如下图所示。设str1和m2分别指向两个单词所在单链表的头结点,链表结点结构为请设计一个时间上尽可能高效的算法,找出
随机试题
Ishallrememberthedays________weworkedonthefarmtoexperiencelife.
男性尿道的分部及走行
患者曾发高热,热退则口鼻、皮肤干燥,形瘦,目陷,唇舌干燥,舌质紫绛边有瘀斑、瘀点。其病机是
依据我国土地管理法的规定,国家编制土地利用总体规划,划定土地用途,将土地分为()。
从风险管理的角度,商业银行所面临的风险损失通常分为()。
关于企业公平市场价值的以下表述中,正确的有()。
对以公允价值计量且其变动计入其他综合收益的权益工具投资,下列项目中错误的是()。
直辖市人民政府房地产行政主管部门负责()物业服务企业资质证书的颁发和管理。
假如一个教师非常关心如“学生喜欢我吗?”这样的问题,并把大量的时间用于与学生搞好个人关系,那么他处于教师成长的()。
Readthearticlebelowaboutfocusoncustomer,andthequestionsontheoppositepage.Foreachquestion(13-18),markonelette
最新回复
(
0
)