问答题 写出从哈希表中删除关键字为K的一个记录的算法。设哈希函数为H,解决冲突的方法为链地址法。
【正确答案】
【答案解析】用链地址法解决冲突的哈希表是一个指针数组,数组分量均是指向单链表的指针,(第i个)单链表结点有两个域,一个是哈希地址为i的关键字,另一个是指向同义词结点的指针。删除算法与单链表上删除算法类似。
typedef struct node{
keytype key;
struct node *next;
}HSNode *HSList;
typedef struct node *HLK;
void Delete(HLK HT[], keytype K){
//用链地址法解决冲突,从哈希表中删去关键字为K的记录
int i=H(K); //用哈希函数确定关键字K的哈希地址
if(HT[i]==null){ printf("无被删除记录/n"); exit(0); }
HLK p, q; p=H[i]; q=p; //p指向当前记录(关键字),q是p的前驱
while(p && p->key !=k){ q=p; p=p->next; }
if(p==null){ printf("无被删除记录"); exit(0); }
if(q==H[i]){ HT[i]=HT[i].next; free(p); } //被删除关键字是链表中第一个结点
else{q->next=p->next; free(p); }
}