首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
在用除余法作为散列函数线性探测解决冲突的散列表中,写一删除关键字的算法,要求将所有可以前移的元素前移去填充被删除的空位,以保证探测序列不至于断裂。
在用除余法作为散列函数线性探测解决冲突的散列表中,写一删除关键字的算法,要求将所有可以前移的元素前移去填充被删除的空位,以保证探测序列不至于断裂。
admin
2016-03-29
45
问题
在用除余法作为散列函数线性探测解决冲突的散列表中,写一删除关键字的算法,要求将所有可以前移的元素前移去填充被删除的空位,以保证探测序列不至于断裂。
选项
答案
首先计算关键字的散列地址,若该地址为空,则空操作;若该地址有关键字,但与给定值不等,则用解决冲突的方法去查找给定值;若该地址有关键字且与给定值相等,则执行删除。题目要求将所有可以前移的元素前移去填充被删除的空位,以保证探测序列不断裂。由于用线性探测解决冲突,设被删除元素的散列地址为i,则其余m一1(m为表长)个位置均可能是同义词。查找同义词的操作直到碰到空地址或循环一圈回到i才能结束。为了提高算法效率,减少数据移动,应将最后_个同义词前移填充被删除关键字。 void:Hs[)elete(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);breaki case false;di=l;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[1ast];HS[1ast]=null; //将哈希地址last的关键字移到哈希地址j } 算法讨论:由于用线性探测解决冲突,可能发生“二次聚集”(两个第一哈希地址不同的记录争夺同一后继哈希地址)。像上面这样处理后,对于哈希地址为i的记录没有问题了,但由于将地址,置空,有可能截断了其他记录的探测通路。最明显的是哈希地址为j的记录就查不到了。解决的办法是继续调整,直到当前哈希表中的每个记录的查找都是正确的为止。这里不再深入讨论。
解析
转载请注明原文地址:https://kaotiyun.com/show/bhRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
元代对边疆地区的统治方式不同于其他三地的一地是()。
十六国时期的历史,可以划分为前后两个时期,其分界线是()。
论述《独立宣言》的主要内容及影响
1962年初,中共召开了中央工作会议,即“七千人大会”,其议题主要是()。
1948年,南斯拉夫对从苏联照搬来的“行政命令式的国家集权式”体制进行改革逐步形成有自己特色的建设社会主义的理论和方法,其核心是()。
以下称呼不是指代李自成的是()。
下面哪项条约没有涉及德国的赔款问题?()
(1)以太网采用了曼彻斯特编码,一个比特的数据需要两个信号来传输,那么为了达到100Mbps的数据传送速率,需要线路达到200Mbps的带宽。(2)以太网的最小帧长度是64字节,那么发送一个最小帧需要的时间T1=64×8/(100×106),
真值0在原码、反码和补码机器数形式下()。
在请求分页存储管理中,若采用FIFO的页面淘汰算法,当分配的页面数增加时,缺页中断的次数()。
随机试题
以下属于脉象要素的是
A.发散、行气、行血B.收敛固涩C.软坚散结、泻下D.燥湿E.渗湿利水淡味中药的作用是
参与先天性免疫的效应分子不包括()
与中国封建制度相适应的税法在不同朝代也发生着不同的变革,体现出时代特征。有关中国封建社会税法变革,下列表述正确的有()。
完全竞争市场和垄断竞争市场的主要区别在于( )。
根据《教师资格条例》的规定,对符合认定条件的,应当在受理期限终止之日起()日内颁发相应的教师资格证书。
根据《联合国海洋法公约》,下列四幅示意图中,关于三个区域位置,表示正确的是()。
设函数f(x)具有二阶导数,且f”(x)>0,又函数u(x)在区间[0,a]上连续,证明:∫0af[u(t)]dt≥f[∫0au(t)dt].
Whyhasthecouplecometotherestaurant?
A、Toremindthewomantolockthedoorwhengoingout.B、Toremindthemantotakehiskeyswhengoingout.C、Topreventthethi
最新回复
(
0
)