{if（i<1 || i>id.k）printf（“无第%d个集合\\n”，i）；exit（0）；}
if（i==1）first=0；else first=id.a[i-1]+1； //first指向第i个集合在数据表的首址
last= id.a[i]；//last是第i个集合在数据表中的末址
for（j=first；j≤last；j++） if（R[j]==x）return （j）；//查找成功 for（j=id.a[id.k]；j>id.a[i]；j--） //查找失败，将x插入数据表 R[j+1]=R[j]；//元素后移
R[j+1]=x； //将x插入到原第i个集合最后一个元素之后。
for（j=i；j≤k；j++）id.a[j]++；//修改索引表中各集合最后一个元素的下标 }结束SetSearch_Insert
由于各集合元素个数不等，各块长度不等且块间无序，索引表中用数组表示，数组中元素值是各集合最后一个元素在数据表中的下标。按本算法插入（2,11.2）和（1,5.3），数据表前后状态如下：
0 插入前 10.2 1.7 4.8 16.2 1.7 8.4 0.5 4.8 4.2 3.6 2.7 5.1 3.9 插入后 10.2 1.7 4.8 16.2 5.3 1.7 8.4 0.5 11.2 4.8 4.2 3.6 2.7 5.1 3.9 3． void Delete（BSTree t，p）
// 在二叉排序树t中，删除f所指结点的右孩子（由p所指向）的算法 {if（p->lchild==null）{f->rchild=p->rchild；free（p）；} //p无左子女 else //用p左子树中的最大值代替p结点的值 {q=p->lchild；s=q；
while（q->rchild）{s=q；q=q->rchild ；}//查p左子树中序序列最右结点 if（s==p->lchild） //p左子树的根结点无右子女
{p->data=s->data；p->lchild=s->lchild；free（s）；} else{p->data=q->data；s->rchild=q->lchild；free（q）；} }
}//Delete
4．[题目分析]上题用被删结点左子树中最大值结点代替被删结点，本题用被删结点右子树中最小值（中序遍历第一个）结点代替被删结点。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 void Delete(BSTree bst,p,fp)
//在二叉排序树bst上，删除fp所指结点的左子女（由p所指向）的算法。
{if（!p->lchild）{fp->lchild=p->rchild；free（p）；} //p无左子女 else if（!p->rchild）{fp->lchild=p->lchild；free（p）；} //p无右子女
else // p有左子女和右子女
{q=p->rchild；s=q；//用p右子树中的最小值代替p结点的值
while（q->lchild）{s=q；q=q->lchild ；}//查p右子树中序序列最左结点 if（s==p->rchild） //p右子树的根结点无左子女 {p->data=s->data；p->rchild=s->rchild；free（s）；} else{p->data=q->data；s->lchild=q->rchild；free（q）；} }//Delete
5．[题目分析] 在二叉排序树上删除结点，首先要查找该结点。查找成功后，若该结点无左子树，则可直接将其右子树的根结点接到其双亲结点上；若该结点有左子树，则将其左子树中按中序遍历的最后一个结点代替该结点，从而不增加树的高度。
void Delete(BSTree bst, keytype X)
//在二叉排序树bst上，删除其关键字为X的结点。 {BSTree f,p=bst;
while (p && p->key!=X) //查找值为X的结点 if (p->key>X) {f=p; p=p->lchild;} else {f=p; p=p->rchild;}
if (p==null) {printf(“无关键字为X的结点\\n”); exit(0);} if {p->lchild==null} //被删结点无左子树
if (f->lchild==p) f->lchild=p->rchild;//将被删结点的右子树接到其双亲上 else f->rchild=p->rchild;
else {q=p; s=p->lchild; //被删结点有左子树
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); } }//算法结束
6．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。 7．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 keynum=m-1，则要产生结点的分裂，分裂可能持续到根结点，使树的高度增加1，不再细述。 8．略。 9．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）。 10．[题目分析] 在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 11．[题目分析] 用链地址法解决冲突的哈希表是一个指针数组，数组分量均是指向单链表的指针，（第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 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]；