发布时间 : 星期六 文章数据结构 第八章 查找表更新完毕开始阅读8bb4a50ccc17552707220851
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]； 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 13．[题目分析]首先计算关键字的散列地址，若该地址为空，则空操作；若该地址有关键字，但与给定值不等，则用解决冲突的方法去查找给定值；若该地址有关键字且与给定值相等，则实行删除。题目要求将所有可以前移的元素前移去填充被删除的空位，以保证探测序列不断裂。由于用线性探测解决冲突，设被删除元素的散列地址为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）