数据结构 第八章 查找表 下载本文

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)