首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
在用除余法作为散列函数线性探测解决冲突的散列表中,写一删除关键字的算法,要求将所有可以前移的元素前移去填充被删除的空位,以保证探测序列不至于断裂。
在用除余法作为散列函数线性探测解决冲突的散列表中,写一删除关键字的算法,要求将所有可以前移的元素前移去填充被删除的空位,以保证探测序列不至于断裂。
admin
2019-08-01
71
问题
在用除余法作为散列函数线性探测解决冲突的散列表中,写一删除关键字的算法,要求将所有可以前移的元素前移去填充被删除的空位,以保证探测序列不至于断裂。
选项
答案
首先计算关键字的散列地址,若该地址为空,则空操作;若该地址有关键字,但与给定值不等,则用解决冲突的方法去查找给定值;若该地址有关键字且与给定值相等,则执行删除。题目要求将所有可以前移的元素前移去填充被删除的空位,以保证探测序列不断裂。由于用线性探测解决冲突,设被删除元素的散列地址为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]=nuu; //将哈希地址last的关键字移到哈希地址j } 算法讨论:由于用线性探测解决冲突,可能发生“二次聚集”(两个第一哈希地址不同的记录争夺同一后继哈希地址)。像上面这样处理后,对于哈希地址为i的记录没有问题了,但由于将地址j置空,有可能截断了其他记录的探测通路。最明显的是哈希地址为j的记录就查不到了。解决的办法是继续调整,直到当前哈希表中的每个记录的查找都是正确的为止。这里不再深入讨论。
解析
转载请注明原文地址:https://kaotiyun.com/show/zkCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
在加强对边疆地区的治理方面,明清两朝推行的相同措施是()。
戊戌政变发生的时间是()。
最早以立法形式巩固大化改新成果的法令是()。
下列不是空想社会主义产生的历史背景的是()。
日本三个月亡华计划破产的标志是()。
在下列查找的方法中,平均查找长度与结点个数n无关的查找方法是()。
某中央处理器的数据通路如图所示。MDR为内存数据寄存器,PC为程序计数器,IR为指令寄存器。所有的单线箭头为控制微命令。(1)请说明图中部件X的名称和功能、寄存器Y的名称和功能。(2)请解释:为什么要设置T暂存器?(3)假定指
已知在二叉树中,T为根结点,*p和*q为二叉树中两个结点,试编写求距离它们最近的共同祖先的算法。
已知加权有向图G如下,回答下列问题:(1)画出该有向图G的邻接矩阵;(2)试利用Dijkstra算法求G中从顶点a到其他各顶点间的最短路径,并给出求解过程。
随机试题
登兹楼以四望兮,聊暇日以销忧,览斯宇之所处兮,实显敞而寡仇。挟清漳之通浦兮,倚曲沮之长洲,背坟衍之广陆兮,临皋隰之沃流。北弥陶牧,西接昭丘,华实蔽野,黍稷盈畴。虽信美而非吾土兮,曾何足以少留?这段文字出自哪篇课文?作者是谁?
A.多饮、多食、多尿、消瘦B.乏力、纳差、血压低、皮肤色素黑C.蛋白尿、水肿、高脂、低蛋白血症D.怕热多汗、疲乏无力、急躁易怒E.蛋白尿、血尿、高血压
可能导致财务报表不一定能反映公司的客观实际的因素有( )。
企业保留盈余资金成本的实质是一种()。
在一手房贷款中,在房屋办妥抵押登记前,一般由()承担阶段性保证责任。
企业应支付的各种赔偿不通过“应付账款”核算。()
Disagreementsamongeconomistsarelegendary,butnotontheissueoffreetrade.Arecentsurveyofprominenteconomistsbothc
吕某听到别人说自己漂亮,最可能的症状是()。从测验结果来看,该求助者筛查阳性的因子是()。
中央银行可以主动用于调节外汇市场的手段包括()。
Researchershavestudiedthepoorasindividuals,asfamiliesandhouseholds,asmembersofpoorcommunities,neighborhoodsand
最新回复
(
0
)