首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
在用除余法作为散列函数线性探测解决冲突的散列表中,写一删除关键字的算法,要求将所有可以前移的元素前移去填充被删除的空位,以保证探测序列不至于断裂。
在用除余法作为散列函数线性探测解决冲突的散列表中,写一删除关键字的算法,要求将所有可以前移的元素前移去填充被删除的空位,以保证探测序列不至于断裂。
admin
2017-11-14
45
问题
在用除余法作为散列函数线性探测解决冲突的散列表中,写一删除关键字的算法,要求将所有可以前移的元素前移去填充被删除的空位,以保证探测序列不至于断裂。
选项
答案
首先计算关键字的散列地址,若该地址为空,则空操作;若该地址有关键字,但与给定值不等,则用解决冲突的方法去查找给定值;若该地址有关键字且与给定值相等,则执行删除。题目要求将所有可以前移的元素前移去填充被删除的空位,以保证探测序列不断裂。由于用线性探测解决冲突,设被删除元素的散列地址为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
学硕统考专业
相关试题推荐
《齐民要求.序》中写道:“今采摭经传,爰及歌谣,洵之老成,验之行事,起自农耕,终于醯醢(酱醋),资生之靡不毕书书;号日《齐民要术》……舍本逐末,贤哲所非……故商贾之事,阙而不录。”这段材料表明作者()。①采取古今资料的编撰原则②
文艺复兴运动兴起的时间是()。
下列城市:①南京②厦门③天津④杭州,按其在近代历史上开放为商埠的时间先后顺序排列应该是()
在阿拉伯()统治时期,阿拉伯军队曾与当时中国的唐朝军队发生冲突。
简要分析英、法20世纪30年代绥靖法西斯国家的表现及影响。
第一个五年计划的具体时间段是()。
16世纪中期,德意志资产阶级迫切要求实现国家的统一,其首要的目的是()。
随机试题
确定工装夹具的结构时应注意()。
原发性肾病综合征,最常出现
五碳糖是六碳酮糖是
村民古奇向海德借款人民币4万元,古奇出具的借条上写明8个月后归还,双方并且口头商定不支付利息。借款12个月后古奇欲归还所借款项。双方对归还4万元本金没有异议,但对是否要偿付利息双方发生争议,对于这一问题,以下意见中错误的是:
M公司为增值税一般纳税人,适用的增值税税率为17%,2017年发生如下交易事项:(1)2月购入需要安装的生产线设备一台,取得增值税专用发票注明的价款为2630万元,增值税税额为447.1万元,发生运费取得运费增值税专用发票注明的运费金额为20万元,增值税
税务机关针对纳税人的不同情况可以采取不同的税款征收方式。根据税收法律制度的规定,对于纳税人财务制度不健全,生产经营不固定,零星分散的,适用的税款征收方式是()。
钠是一种非常活泼的金属,它可以和冷水直接反应生成氢气,但是它与煤油不会发生反应。把一块银白色的金属钠投入盛有蒸馏水的烧杯中(如图所示),可以看到钠块浮在水面上,与水发生剧烈反应,反应放出的热量使钠熔成小球,甚至会使钠和生成的氢气都发生燃烧。如果在
IsStanfordstillauniversity?TheWallStreetJournalrecentlyreportedthatmorethanadozenstudentshaveleftschooltowo
进程创建原语的任务是______。
MinorityReportA)Americanuniversitiesareacceptingmoreminoritiesthanever.Graduatingthemisanothermatter.B)BarryMill
最新回复
(
0
)