while (s->rchild !=null) //查左子树中最右下的结点（中序最后结点） {q=s; s=s->rchild;}
p->key=s->key; //结点值用其左子树最右下的结点的值代替 if (q==p) p->lchild=s->lchild;//被删结点左子树的根结点无右子女 else q->rchild=s->lchild; //s是被删结点左子树中序序列最后一个结点
free(s); }
}//算法结束
7．int Search（rectype r[ ]，int n，keytype k）
//在n个关键字从小到大排列的顺序表中，查找关键字为k的结点。 {r[n+1].key=MAXINT；//在高端设置监视哨 i=1；
while（r[i].key if (r[n+1].key==k) return （i%（n+1））； else return (0) }//算法search结束 查找过程的判定树是单枝树，限于篇幅不再画出。本题中虽然表按关键字有序，但进行顺序查找，查找成功的平均查找长度亦为（n+1）/2。 8．FUNC Srch_Mtree（t:mblink；k：keytp）：result； //在根结点指针为t的m阶B-树上查找关键字k，返回记录（pt，i，tag）。若查找成 功， //置tag=1，等于k的关键字即pt所指结点中第i个关键字；若查找失败，关键字k应插入 //pt所指结点的第i和第i+1个关键字之间。 p:=t；q:=null；found:=false；i:=0；//p指向待查结点，q指向p的双亲结点 WHILE（p<>NIL）AND NOT found DO [n:=p↑.keynum；i:=search（p,k）；//在p↑.key[1..n]中查找 IF（i>0）AND（p↑.key[i]=k）THEN found：=true ELSE[q:=p；p:=p↑.ptr[i]；] ] IF found THEN return （p,i,1）//查找成功 ELSE return （q，i，0）//查找失败，返回插入位置 [算法讨论] 插入时，若所在结点关键字keynum 9．请参见上面题3(1)。 10．int BinSrch（rectype r[ ]，int k，low，high） //在长为n的有序表中查找关键字k，若查找成功，返回k所在位置，查找失败返回0。 {if（low≤high） //low和high分别是有序表的下界和上界 {mid=（low+high）/2； if（r[mid].key==k）return （mid）； else if（r[mid].key>k）return （BinSrch（r,k，mid+1，high））; else return （BinSrch（r,k，low，mid-1））; } else return （0）；//查找失败。 }//算法结束 算法时间复杂度为O（logn）。 11．[题目分析] 在Trie树上查找给定值KEY的过程如下：沿和给定值相应的指针向下，直至叶子结点，若叶子中的关键字和KEY相等，则查找成功；若分枝结点中和给定值相应的指针为空，或叶子结点中的关键字和给定值不等，则查找不成功。 typedef enum{LEAF，BRANCH}NodeKind；//结点种类{叶子，分枝} typedef struct TrieNode {NodeKind kind； union {struct{KeyType K；Record *infoptr} lf； //叶子结点 struct{TrieNode *ptr[27]；int num} bh； //分枝结点 }； }TrieNode，*TrieTree；//键树类型 Record *SearchTrie（TrieTree T，KeyType KEY） //在Trie树T中查找关键字等于K 的记录。 {for（P=T，i=0； //对KEY的每个字符逐个查找 P && P->kind==BRANCH && i P=P->bh.ptr[ord（KEY.ch[i]）]，++i）；//ord求字符在字母表中的序号 if（P && P->kind==LEAF && P->lf.K==KEY ）return P->lf.infoptr；//查找成功 else return null； }//结束SearchTrie 12．[题目分析] 用链地址法解决冲突的哈希表是一个指针数组，数组分量均是指向单链表的指针，（第i个）单链表结点有两个域，一个是哈希地址为i的关键字，另一个是指向同义词结点的指针。删除算法与单链表上删除算法类似。 typedef struct node {keytype key； struct node *next； }HSNode；*HSList typedef struct node *HLK； void Delete（HLK HT[]，keytype K） //用链地址法解决冲突，从哈希表中删去关键字为K的记录 {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）；} }//结束Delete 13．[题目分析] 本题仍用上面第12题定义的存储结构。首先计算关键字k的哈希地址，若该哈希地址的头指针为空，则直接插入；否则，先在该链表上查找，若查找失败，则插入链表；若查找成功，则不再插入。 void Insert（HLK HT[]，keytype K） // 用链接表解决冲突的哈希表插入函数 {i=H（K）；// 计算关键字K的哈希地址 if（HT[i]==null）// 关键字K所在链表为空 {s=(HSNode *)malloc（sizeof （HSNode））；s->key=k; s->next=HT[i]；HT[i]=s；} else //在链表中查询关键字K {p=HT[i]； while（p && p->key！=k）p= p->next； if（！p）//链表中无关键字K，应该插入 { s=（HSNode *）malloc（sizeof （HSNode））； s->next= HT[i]；HT[i]=s；} // 插入后成为哈希地址为i的链表中的第一个结点 } }//Insert 14．[题目分析]首先计算关键字的散列地址，若该地址为空，则空操作；若该地址有关键字，但与给定值不等，则用解决冲突的方法去查找给定值；若该地址有关键字且与给定值相等，则实行删除。题目要求将所有可以前移的元素前移去填充被删除的空位，以保证探测序列不断裂。由于用线性探测解决冲突，设被删除元素的散列地址为i，则其余m-1（m为表长）个位置均可能是同义词。查找同义词的操作直到碰到空地址或循环一圈回到i才能结束。为了提高算法效率，减少数据移动，应将最后一个同义词前移填充被删除关键字。 void HsDelete（rectype HS[]，K） //在以除余法为散列函数、线性探测解决冲突的散列表HS中，删除关键字K {i=K % P； // 以造表所用的除余法计算关键字K的散列地址 if（HS[i]==null）{printf（“散列表中无被删关键字”）；exit（0）；} // 此处null代表散列表初始化时的空值 switch {case HS[i]==K：del(HS，i，i，K)；break； case HS[i]!=K：di=1；j=(i+ di)%m； // m为 表长 while（HS[j]!=null && HS[j]!=K && j!=i）// 查找关键字K {di=di+1； j=(i+di)%m； }// 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的记录就查不到了。解决的办法是继续调整，直到当前哈希表中的每个记录的查找都是正确的为止。这里不再深入讨论。 15．[题目分析]利用二叉排序树的性质，从根结点开始查找，若根结点的值小于等于x，则根结点及其左子树均应删除，然后以右子树的根结点为树根，重新开始查找。若根结点的值大于x，则顺左子树向下查找，直到某结点的值小于等于x，则该结点及其左子树均应删除。下面设计一查找算法，确定被删除子树的根结点，再设计一删除算法，删除以被删结点为根的子树。 typedef struct node {int data； struct node *left，*right; }BiTNode，*BSTree； void DelTree(BSTree r） //非递归删除以r为根的二叉排序树 {BSTree S[]；// 栈，容量足够大，栈中元素是二叉排序树结点的指针 top=0； while （r!=null || top>0） {while（r!=null） // 沿左分枝向下 {S[++top]=r；r=r->left ；} if（top>0） // 退栈，沿栈顶结点的右子树向下删除，释放被删除结点空间 {p=S[top--]；r=p->right；free（p）；} } }// DelTree void DeleteAllx(BSTree Ｔ，int x） //在二叉排序树Ｔ中，删除所有小于等于x的结点 {BSTree p=T，q； while（T && T->data≤x） //根结点的值小于等于x {p=T；T=T->right；p->right=null； DelTree（p）；} //删除二叉树p,删除持续到“根”结点值大于x或T为空树为止 if (T) {q=T；p=T->left； while（p && p->data>x） //沿根结点左分枝向下，查小于等于x的结点 {while（p && p->data>x） { q=p；p=p->left；} // q记p的双亲 if（p） //p结点的值小于等于x {q->left=p->right；p->right=null；DelTree（p）； } p=q->left；// 再查原p的右子树中小于等于x的结点 }} }// DeleteAllx 16．typedef struct node {datatype data；