首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
在用除余法作为散列函数线性探测解决冲突的散列表中,写一删除关键字的算法,要求将所有可以前移的元素前移去填充被删除的空位,以保证探测序列不至于断裂。
在用除余法作为散列函数线性探测解决冲突的散列表中,写一删除关键字的算法,要求将所有可以前移的元素前移去填充被删除的空位,以保证探测序列不至于断裂。
admin
2019-08-15
31
问题
在用除余法作为散列函数线性探测解决冲突的散列表中,写一删除关键字的算法,要求将所有可以前移的元素前移去填充被删除的空位,以保证探测序列不至于断裂。
选项
答案
首先计算关键字的散列地址,若该地址为空,则空操作;若该地址有关键字,但与给定值不等,则用解决冲突的方法去查找给定值;若该地址有关键字且与给定值相等,则执行删除。题目要求将所有可以前移的元素前移去填充被删除的空位,以保证探测序列不断裂。由于用线性探测解决冲突,设被删除元素的散列地址为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://jikaoti.com/ti/ToGjFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
20世纪五六十年代经济高速增长时期,西欧经济增长最快的国家是()。
鸦片战争失败后,西方列强强迫清政府签订了中国近代史上第一批不平等条约。鸦片战争是中国历史的转折点,对中国历史产生了深远的影响。中国开始逐步沦为半殖民地半封建社会。据此回答以下问题:中英《南京条约》所规定开放的通商口岸分布于()
基督教产生的时间是()。
设计一个算法求图的中心点。设v是有向图G的一个顶点,把v的偏心度定义为:MAX{从w到v的最短距离|w属于V(G))如果v是有向图G中具有的最小偏心度的顶点,则称顶点v是G的中心点。
某定点机字长8位(含1位符号位),现该机中一个寄存器的内容为43H,则将其算术左移一位、算术右移一位的结果分别为()。
在一个长度为n(n>1)的带头结点的单链表h上,设有尾指针r(指向尾结点),则执行()操作与链表的长度有关。
什么是域名解析?域名解析中采取了什么措施提高效率?对同一个域名向DNS服务器发出多次的DNS请求报文后,得到IP地址都不一样,可能吗?为什么?
关于分页系统,回答下列问题:(1)在页表中,哪些数据项是为实现换页而设置的?(2)设某系统为每个作业进程分配3个内存块,某作业进程在运行访问中的轨迹为1,4,3,1,6,8,1,且每一页都是按请求装入的。问:先进先出页面置换算法(FIF
下图所示为双总线结构机器的数据通路,IR为指令寄存器,PC为程序计数器(具有自增功能),M为主存(受R/W信号控制),AR为地址寄存器,DR为数据缓冲寄存器,ALU由加、减控制信号决定完成何种操作,控制信号G控制的是一个门电路。另外,线上标注有小圈表示有控
用链接方式存储的队列,在进行删除运算时,下面正确的是()。
随机试题
肺胀痰浊壅肺证的治法是
我国国民经济和社会发展系统中最重要的一对关系是()。
无风险利率与期权的价值呈正相关关系。()
某企业2005年末现金余额为10万元;2005年实现销售收入1000万元,2006年预计销售收入1500万元,该公司每年实现的销售收入在当年收现60%,第二年收现40%,2006年预计其他现金收入80万元;2005年末应付账款余额120万元,2006年预
下列各项,会影响企业资本公积总额的有()。
东林公司是一家民营高科技企业,专门研发、生产和销售户外LED屏幕。经过多年的发展,公司产品在本省占有率达到40%,控股子公司有8个,总经理由职业经理人担任。公司的实际控制人张某深感内部控制制度的建立健全对公司可持续发展的重要性。公司给办公大楼都安装了24小
被苏轼赞为“诗中有画,画中有诗”的唐代诗人是()。
根据下列资料,回答问题。2014年3月,全国居民消费价格总水平同比上涨2.4%,其中,城市上涨2.5%,农村上涨2.1%,食品价格上涨4.1%,非食品价格上涨1.5%。消费品价格上涨2.2%,服务价格上涨2.81%。1—3月平均,全国居民消费价格
作风建设的核心是()
关于派生类的说法,不正确的是()。
最新回复
(
0
)