首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
在用除余法作为散列函数线性探测解决冲突的散列表中,写一删除关键字的算法,要求将所有可以前移的元素前移去填充被删除的空位,以保证探测序列不至于断裂。
在用除余法作为散列函数线性探测解决冲突的散列表中,写一删除关键字的算法,要求将所有可以前移的元素前移去填充被删除的空位,以保证探测序列不至于断裂。
admin
2019-08-01
32
问题
在用除余法作为散列函数线性探测解决冲突的散列表中,写一删除关键字的算法,要求将所有可以前移的元素前移去填充被删除的空位,以保证探测序列不至于断裂。
选项
答案
首先计算关键字的散列地址,若该地址为空,则空操作;若该地址有关键字,但与给定值不等,则用解决冲突的方法去查找给定值;若该地址有关键字且与给定值相等,则执行删除。题目要求将所有可以前移的元素前移去填充被删除的空位,以保证探测序列不断裂。由于用线性探测解决冲突,设被删除元素的散列地址为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://jikaoti.com/ti/edGjFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
在巴黎和会上,列强讨论的中心问题是()。
现代人种出现于人类发展过程中的哪一个时期?()
20世纪的两次世界大战给人类造成巨大灾难,使这两次世界性大战得以发生的因素是()①少数大国争夺世界霸权②以欧洲为中心的国家格局开始发生变化③军国主义政策的推行④英法等大国在战前对法西斯的侵略采取了纵容姑息政策
1918年美国总统威尔逊提出“十四点原则”,内容有“海洋上的航行有绝对自由”、“取消一切经济障碍和确立贸易条件的平等”、“成立一个一般性的各国联合组织”。其最终目的是()。
两极格局结束后,世界形势发展的总态势的基本特点()
曾经来华留学,并在日本大化改新中发挥重要作用的是()。
西周的分封制相当发达,是西周的重要政治制度,也是西周历史的一个显著特点。根据所学知识,回答问题在武王灭商和周公东征的过程中立有大功,或与周有世代同盟关系的异姓贵族也被分封去建立诸侯国家,继续为周王室效力,下列国家:①齐②鲁③燕④宋,属于异姓诸侯国的是(
编写判定给定的二叉树是否是二叉排序树的函数。
假设某计算机的存储系统由Cache和主存组成j某程序执行过程中访存1000次,其中访问Cache缺失(未命中)50次,则Cache的命中率是()。
“乘法减少”和“加法增大”备用在什么情况下?
随机试题
男性,30岁。呼吸困难2天就诊,发病前有鼻痒,喷嚏。继往有类似病史。体检:呼吸20次/分,双肺可闻及呼气末哮鸣音,心率96次/分,律齐。动脉血气分析PaCO238mmHg,PaO296mmHg,pH7.39。根据临床表现和血气分析结果,其病情程度分级为
A.抗甲状腺药物联合甲状腺素、免疫抑制剂、球后放射治疗B.突眼度2mmC.局部用药、眼罩、利尿、限盐等D.视力减退、眼肌麻痹、复视E.以上都是非浸润性突眼
A.磷酸盐类B.硅橡胶印模材C.琼脂D.印模膏E.氧化锌印模材料非弹性不可逆的印模材料是
A.抗生素药膜局部贴敷B.口服维生素AC.去除刺激因素D.强的松E.2%硫酸氢钠溶液治疗白斑的首要措施是
要做到“安全第一”,就必须()。
下列各项属于其他业务成本的是()。
银行资本内部融资的主要来源是()。
按预期假说,如果人们预期未来短期利率下降,债券回报率(债券利率)曲线呈()。
"Whereistheuniversity?"isaquestionmanyvisitorstoCambridgeask,butnoonecangivethemaclearanswerforthereisno
—Youwillhearfiveshortrecordings.Eachspeakerissayinganad.—Foreachrecording,decidewhichthespeakeristalkingabo
最新回复
(
0
)