2. 考研
  3. 在用除余法作为散列函数线性探测解决冲突的散列表中，写一删除关键字的算法，要求将所有可以前移的元素前移去填充被删除的空位，以保证探测序列不至于断裂。

在用除余法作为散列函数线性探测解决冲突的散列表中，写一删除关键字的算法，要求将所有可以前移的元素前移去填充被删除的空位，以保证探测序列不至于断裂。

admin2017-01-04  39
问题 在用除余法作为散列函数线性探测解决冲突的散列表中，写一删除关键字的算法，要求将所有可以前移的元素前移去填充被删除的空位，以保证探测序列不至于断裂。
选项
答案首先计算关键字的散列地址，若该地址为空，则空操作；若该地址有关键字，但与给定值不等，则用解决冲突的方法去查找给定值；若该地址有关键字且与给定值相等，则执行删除。题目要求将所有可以前移的元素前移去填充被删除的空位，以保证探测序列不断裂。由于用线性探测解决冲突，设被删除元素的散列地址为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]=null； ／／将哈希地址last的关键字移到哈希地址j } 算法讨论：由于用线性探测解决冲突，可能发生“二次聚集”(两个第一哈希地址不同的记录争夺同一后继哈希地址)。像上面这样处理后，对于哈希地址为i的记录没有问题了，但由于将地址j置空，有可能截断了其他记录的探测通路。最明显的是哈希地址为j的记录就查不到了。解决的办法是继续调整，直到当前哈希表中的每个记录的查找都是正确的为止。这里不再深入讨论。
解析
转载请注明原文地址:https://jikaoti.com/ti/u6fjFFFM
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)