056312409数据结构（C语言版）（夏燕张兴科）--习题答案--第9章(2)

else

if (ps->rchild == NULL) max=p->lchild; else

{ q=ps;

max=q->lchild;

while (max->rchild != NULL) { q=max;

max=q->rchild; }

max->rchild=ps->rchild; if (q != ps)

{ q->rchild=max->lchild; max->lchild=q->lchild; } }

if (ps == fa->lchild) fa->lchild=max; else

fa->rchild=max; free(ps); }

(2) 设计一个用“开放定址法”解决冲突的哈希表上删除一个指定关键字的算法。 编程提示：

设哈希函数为Hash(key)=key % n

开放定址法的线性探测再散列法探测公式为 d0=Hash(key)

di=(di-1+1)% n (0≤i≤n-1)

对于要删除的关键字key，先求出所在的位置，将该位置赋值NULL，然后将后面关联的关键字前移。

void delkey(int Ha[ ], int n, int key) { int h,h0,h1; h=key % n;

while (Ha[h] != key) h=(h+1) % n; Ha[h]=NULL;

while ( h0 != (key%n)) { h=(h0+1)%n; Ha[h1]=Ha[h0]; Ha[h0]=NULL; h1=h0;

h0=(h0+1) % n; } }