首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
在用除余法作为散列函数线性探测解决冲突的散列表中,写一删除关键字的算法,要求将所有可以前移的元素前移去填充被删除的空位,以保证探测序列不至于断裂。
在用除余法作为散列函数线性探测解决冲突的散列表中,写一删除关键字的算法,要求将所有可以前移的元素前移去填充被删除的空位,以保证探测序列不至于断裂。
admin
2019-08-15
58
问题
在用除余法作为散列函数线性探测解决冲突的散列表中,写一删除关键字的算法,要求将所有可以前移的元素前移去填充被删除的空位,以保证探测序列不至于断裂。
选项
答案
首先计算关键字的散列地址,若该地址为空,则空操作;若该地址有关键字,但与给定值不等,则用解决冲突的方法去查找给定值;若该地址有关键字且与给定值相等,则执行删除。题目要求将所有可以前移的元素前移去填充被删除的空位,以保证探测序列不断裂。由于用线性探测解决冲突,设被删除元素的散列地址为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
学硕统考专业
相关试题推荐
在华盛顿会议上,美英支持中国要求的意图是()
我国古代文献中记载了许多有关部落和部落联盟之间发生大规模战争的传说,如炎帝和黄帝两个部落曾战于(),结果黄帝取得了胜利。
论述秦国商鞅变法的内容、过程以及重要意义。
20世纪30年代,美国推行“中立”的外交政策。对这一政策的正确表达是()。①适应国内外形势,维护自身利益②反映国际形势走向缓和③维护凡尔赛一华盛顿体系④不利于地区冲突的缓和与解决⑤不关心美洲地区以外
关于一战后构筑的凡尔赛体系,说法不正确的是()。
某计算机有8个主设备需要竞争总线的使用权,其设备号为0~7。现欲设计其判优控制方法,试回答下述问题。(1)集中式总线判优控制与分布式总线判优控制的区别是什么?(2)若采用集中式判优控制,则在链式查询、计数器定时查询和独立请求三种方式下,
图的D搜索类似于BFS,不同之处在于使用栈代替BFS中的队列,入/出队列的操作作为入/出栈的操作,即当一个顶点的所有邻接结点被搜索后,下一个搜索出发点应该是最近入栈(栈顶)的顶点。(1)用邻接表作为存储结构,写一个D搜索算法;(2)用D搜索方法
以数组Data[m+1]作为循环队列SQ的存储空间,front为头指针,rear为队尾指针,则执行出队操作的语句是()。
给定序列{3,5,7,9,11,13,15,17),(1)按表中元素的顺序依次插入一棵初始为空的二叉排序树,画出插入完成后的二叉排序树,并求在等概率情况下查找成功的平均查找长度。(2)按表中元素的顺序构造一棵平衡二叉树,并求其在等概率情
下列叙述正确的个数是()。(1)m=2的平衡m路查找树是AVL树(2)m=3的平衡m路查找树是2—3树(3)m=2的平衡m路查找树的叶结点不一定在同一层(4)m阶B一树的叶结点必须在同一层(5)m阶B一树是平衡m路查找树(6)平衡m路查
随机试题
艺术家具有特殊的审美文化心理结构,使得他具备了艺术敏感的可能性,形成这种结构主要是因为()
胶体金取代传统三大标记物,用于肉眼水平的免疫检测中的优点为
引起牛创伤性心包炎的异物主要来自于
识别转录起始点的是
下列方法可用于血细胞比容测定的是()。
某公司采用剩余股利政策分配股利,董事会正在制订2009年度的股利分配方案。在计算股利分配额时,不需要考虑的因素是()。2010年
出国旅游目的地国家由国务院旅游行政部门会同国务院有关部门提出,报国务院批准后,由国务院旅游行政部门公布。()
服装工业是劳动密集型,服装生产需要雇佣相对大量的人。汽车工业是资金密集型,大量的钱投资于精细的设备,由相对少量的人来操作。如果小额福利不被考虑,1979年美国一个典型的服装工人的工资是汽车工人的46%。下面哪一项,如果正确,最有可能是说明服装工人和汽车工
Theword"gladiators"inthefirstparagraphprobablymeansTheauthor’sattitudetotheparents’claim"ourmotivesareselfle
Itisnecessarythattheadministration______newworkers.
最新回复
(
0
)