首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
在用除余法作为散列函数线性探测解决冲突的散列表中,写一删除关键字的算法,要求将所有可以前移的元素前移去填充被删除的空位,以保证探测序列不至于断裂。
在用除余法作为散列函数线性探测解决冲突的散列表中,写一删除关键字的算法,要求将所有可以前移的元素前移去填充被删除的空位,以保证探测序列不至于断裂。
admin
2019-08-15
25
问题
在用除余法作为散列函数线性探测解决冲突的散列表中,写一删除关键字的算法,要求将所有可以前移的元素前移去填充被删除的空位,以保证探测序列不至于断裂。
选项
答案
首先计算关键字的散列地址,若该地址为空,则空操作;若该地址有关键字,但与给定值不等,则用解决冲突的方法去查找给定值;若该地址有关键字且与给定值相等,则执行删除。题目要求将所有可以前移的元素前移去填充被删除的空位,以保证探测序列不断裂。由于用线性探测解决冲突,设被删除元素的散列地址为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=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[last]; HS[last]=null; //将哈希地址last的关键字移到哈希地址j } 算法讨论:由于用线性探测解决冲突,可能发生“二次聚集”(两个第一哈希地址不同的记录争夺同一后继哈希地址)。像上面这样处理后,对于哈希地址为i的记录没有问题了,但由于将地址j置空,有可能截断了其他记录的探测通路。最明显的是哈希地址为j的记录就查不到了。解决的办法是继续调整,直到当前哈希表中的每个记录的查找都是正确的为止。这里不再深入讨论。
解析
转载请注明原文地址:https://kaotiyun.com/show/o0Ci777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
论述秦国商鞅变法的内容、过程以及重要意义。
1929~1933年经济危机加剧了世界局势的紧张,这主要是指()。①各国人民强烈要求改善生活状况,罢工运动高涨②法西斯分子在各国兴风作浪③资本主义加紧掠夺国际市场,加剧了各国间的矛④资本主义加紧掠夺殖民地和半
(1)页面长度为1KB=210B,因此页内偏移地址占10位。主存大小为16KB=214B,所以物理地址占14位。0AC5H=0000101011000101B,除去后10位,得到页号为2,则查找页表可知物理块号为4,所以物理地址是0100101100
已知某CPU有16根地址线、8根数据线,并用MREQ作为访存控制信号(低电平有效)。现有下列存储芯片:1K×4位ROM、2K×4位ROM、4K×8位ROM、4K×8位RAM、8K×4位RAM、8K×8位RAM和非门、与非门、或非门若干,如下图所
如图所示一台路由器连接3个以太网。请根据图中给出的参数回答如下问题:(1)该TCP/IP网络使用的是哪一类IP地址?(2)写出该网络划分子网后所采用的子网掩码。(3)系统管理员将计算机D和E按照图中所示结构连入网络并使用所分配的地址对TC
操作数地址存放在寄存器的寻址方式叫()。
假设有k个关键字互为同义词,若用线性探查法把这k个关键字存入,至少要进行的探查次数是()。
m阶B一树是一棵()。
下列叙述中,不符合m阶B一树定义要求的是()。
关于B一树,下列说法中不正确的是()。
随机试题
化脓性关节炎分为________、________和________3期。
听诊时心律不规则的心律失常可见于
A、0.5%盐酸普鲁卡因注射液B、10%维生素C注射液C、5%葡萄糖注射液D、静脉注射用脂防乳E、丹参注射液制备过程中需调节溶液的pH值3.5~5.0及加入适量氯化钠
甲市人民法院一审对林某强奸案作出判决,如果该案判决有错误,有权按照第二审程序提起抗诉的是()
建设投资估算的基础资料与依据主要包括()。
【2015年真题】通过应用价值工程优化设计,使某房屋建筑主体结构工程达到了缩小结构构件几何尺寸,增加使用面积,降低单方造价的效果。该提高价值的途径是()。
在账务系统中填制记账时,在以下几种操作情况中,不能顺利执行的有()。
让渡资产使用权所获得的收入主要有()。
会计资料的质量特征主要体现在()两个方面。
中华民族在漫长的历史发展中()起了十分成熟的道德价值体系。
最新回复
(
0
)