首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
在用除余法作为散列函数线性探测解决冲突的散列表中,写一删除关键字的算法,要求将所有可以前移的元素前移去填充被删除的空位,以保证探测序列不至于断裂。
在用除余法作为散列函数线性探测解决冲突的散列表中,写一删除关键字的算法,要求将所有可以前移的元素前移去填充被删除的空位,以保证探测序列不至于断裂。
admin
2019-08-01
78
问题
在用除余法作为散列函数线性探测解决冲突的散列表中,写一删除关键字的算法,要求将所有可以前移的元素前移去填充被删除的空位,以保证探测序列不至于断裂。
选项
答案
首先计算关键字的散列地址,若该地址为空,则空操作;若该地址有关键字,但与给定值不等,则用解决冲突的方法去查找给定值;若该地址有关键字且与给定值相等,则执行删除。题目要求将所有可以前移的元素前移去填充被删除的空位,以保证探测序列不断裂。由于用线性探测解决冲突,设被删除元素的散列地址为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
学硕统考专业
相关试题推荐
中国政府第一次公开提出和平解决台湾问题的方针是在()。
二月革命后,为俄国无产阶级革命奠定思想基础的文献是()。
概述第二帝国时期法国经济发展的特点。
新文化运动前期的指导思想是()。
巴黎和会上,英美主张把原德国在山东的权利转让给日本,华盛顿会议又表示支持中国让日本归还山东的要求,英美态度发生变化的根本原因是()。
系统阐明社会主义初级阶段理论是在()。
试就MutualExclusion、Progress、BoundedWaiting论述以下解决双进程临界区问题的算法是错误的:ProcessPO:do{flag[0]=true;While(flag[1]);
若二叉树的前序序列为DABCEFG,中序序列为BACDFGE,则其层次序列为()。
假设在一台单处理机上执行如下表所示的进程,且假定这些进程在时刻0以1,2,3,4,5的顺序创建。时间单位为时间片,优先级以数值大者为优。(1)请说明分别使用FCFS、RR(时间片=1)、SPF以及非抢夺式优先级调度算法时,这些进程的执行
随机试题
运动会将准时开始,除非天下雨。以下断定中与上述断定含义相同的是:Ⅰ.如果天下雨,则运动会不会准时开始。Ⅱ.如果运动会准时开始,则天没下雨。Ⅲ.如果天不下雨,运动会将准时开始。
气焊()金属材料时必须使用熔剂。
A.急性胃炎B.慢性胰腺炎C.自身免疫性胃炎D.十二指肠溃疡E.胃癌能引起恶性贫血的疾病是
热适应是人体在热环境下,经过一段时间后产生的对热负荷的适应能力。体内下列各种改变不属于热适应表现的是
关于新生儿保健要点,错误的是
当双端固定桥两端固位力不相等时会引起
患者,男,30岁。便后肛门部疼痛、出血反复发作10年。检查:肛门外观截石位6点有结缔组织外痔,并有梭形裂口通向肛内,边缘不齐,创面较深,术中见肛管狭窄明显。应首选的治疗措施是
甲公司2002年12月,由于产品销售不畅,公司面临亏损。公司董事长责令财会部经理对会计报表做技术处理,实现当年盈利目标,并承诺给予奖励。财务经理通过虚拟交易、向子公司转移支出等方法,将公司会计报表从亏损做成盈利。分析上述案例中,下列对财务经理行为的认定中正
社区工作的具体目标有()。
实用主义教育学的基本观点是()
最新回复
(
0
)