首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
在用除余法作为散列函数线性探测解决冲突的散列表中,写一删除关键字的算法,要求将所有可以前移的元素前移去填充被删除的空位,以保证探测序列不至于断裂。
在用除余法作为散列函数线性探测解决冲突的散列表中,写一删除关键字的算法,要求将所有可以前移的元素前移去填充被删除的空位,以保证探测序列不至于断裂。
admin
2017-11-14
43
问题
在用除余法作为散列函数线性探测解决冲突的散列表中,写一删除关键字的算法,要求将所有可以前移的元素前移去填充被删除的空位,以保证探测序列不至于断裂。
选项
答案
首先计算关键字的散列地址,若该地址为空,则空操作;若该地址有关键字,但与给定值不等,则用解决冲突的方法去查找给定值;若该地址有关键字且与给定值相等,则执行删除。题目要求将所有可以前移的元素前移去填充被删除的空位,以保证探测序列不断裂。由于用线性探测解决冲突,设被删除元素的散列地址为i,则其余m—1(m为表长)个位置均可能是同义词。查找同义词的操作直到碰到空地址或循环一圈回到i才能结束。为了提高算法效率,减少数据移动,应将最后一个同义词前移填充被删除关键字。 void HsDelete(rectype HS[],K){ //在以除余法为散列函数线性探测解决冲突的散列表HS中,删除关键字K jnt j=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/stRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
文艺复兴运动兴起的时间是()。
“我不想变成上帝,或居住在永恒之中,或者把天地抱在怀里,属于人的那种光荣对我就够了。我自己是凡人,我只要求凡人的幸福。”这句话体现的思想是()
第一国际成立前,各国无产阶级强烈要求加强国际团结的直接原因是()。
法国里昂工人起义提出:“我们只有一个口号‘人人自由平等!’”英国宪章运动请愿书提出:“我们竭尽自由人的义务,就应享受自由人的权利。我们要求普遍选举。”这些要求表明()。①带有空想社会主义色彩②当时工人的要求还没有超出资产阶级民主主义的范畴
第一个五年计划的具体时间段是()。
根据越南战争的起源和发展,分析“冷战”时期美国对第三世界政策的目标和动机。
16世纪中期,德意志资产阶级迫切要求实现国家的统一,其首要的目的是()。
1922年2月,美、英、法、意、日五国通过了《五国海军条约》,规定了各国海军主力舰和航空母舰的限额,以及在东亚设置海军基地的要求等内容。该条约的缔结表明()
随机试题
湖北省十堰市郧阳区检察院诉郧阳区林业局案2015年5月,郧阳区检察院在履职中发现:2013年3月至4月间,吴某等人在未经林业主管部门审批同意、未办理林地使用手续的情况下,在该区的国家级、省级生态公益林内开采石料,擅自改变林地用途,郧阳区林业局对吴某等人的
比较身高和体重两组数据变异度的大小宜用()
一小儿身高85em,前囟已闭,头围48em,乳牙20枚,已会跳并能用简单的语言表达自己的需要,对人、事有喜乐之分。此小儿的年龄最大的可能是
根据《建设工程施工劳务分包合同(示范文本)》(GF—2003—0214),劳务分包人在施工场地内自有施工机械设备的保险手续应由()办理,并支付保险费用。
下列关于资源税的说法,正确的是()。
项目组织的结构经常制约着组织在________。
亚历山大大帝有一次大送礼物,表示他的慷慨。他给了甲一大笔钱,给了乙一个省份,给了丙一个高官。他的朋友听到这件事后,对他说:“你要是一直这样做下去,你自己会一贫如洗。”亚历山大回答说:“我哪会一贫如洗,我为我自己留下的是一份最伟大的礼物。我所留下的是我的希望
自我设限是指个体针对可能到来的失败威胁,事先设置障碍,为失败创造一分合理的借口,从而保护自我价值,维护自我形象。根据上述定义,下列属于自我设限的是()。
Thedoctorsdon’t______thatthepatientwilllivemuchlonger.
ThemayorofCountyClubHillshelpedarresttwomenWednesdaynightsuspectedintherandomshootinga15-year-oldboyashewa
最新回复
(
0
)