第九章 查找.txt

严蔚敏《数据结构(c语言版)习题集》 参考答案

　　if(p->rtag) p=p->rtag;
　　else
　　{
　　　p=p->rchild;
　　　while(!p->ltag) p=p->lchild;
　　} //转到中序后继
　　last=p;
　}//while //借助中序遍历找到元素x及其前驱和后继结点
　if(!ptr) return ERROR; //未找到待删结点
　Delete_BSTree(ptr); //删除x结点
　if(pre&&pre->rtag)
　　pre->rchild=suc; //修改线索
　return OK;
}//BSTree_Delete_key

void Delete_BSTree(BiThrTree &T)//课本上给出的删除二叉排序树的子树T的算法,按照线索二叉树的结构作了一些改动
{
　q=T;
　if(!T->ltag&&T->rtag) //结点无右子树,此时只需重接其左子树
　　T=T->lchild;
　else if(T->ltag&&!T->rtag) //结点无左子树,此时只需重接其右子树
　　T=T->rchild;
　else if(!T->ltag&&!T->rtag) //结点既有左子树又有右子树
　{
　　p=T;r=T->lchild;
　　while(!r->rtag)
　　{
　　　s=r;
　　　r=r->rchild; //找到结点的前驱r和r的双亲s
　　}
　　T->data=r->data; //用r代替T结点
　　if(s!=T)
　　　s->rchild=r->lchild;
　　else s->lchild=r->lchild; //重接r的左子树到其双亲结点上
　　q=r;
　}//else
　free(q); //删除结点
}//Delete_BSTree
分析:本算法采用了先求出x结点的前驱和后继,再删除x结点的办法,这样修改线索时会比较简单,直接让前驱的线索指向后继就行了.如果试图在删除x结点的同时修改线索,则问题反而复杂化了.

9.38

void BSTree_Merge(BiTree &T,BiTree &S)//把二叉排序树S合并到T中
{
　if(S->lchild) BSTree_Merge(T,S->lchild);
　if(S->rchild) BSTree_Merge(T,S->rchild); //合并子树
　Insert_Key(T,S); //插入元素
}//BSTree_Merge

void Insert_Node(Bitree &T,BTNode *S)//把树结点S插入到T的合适位置上
{
　if(S->data>T->data)
　{
　　if(!T->rchild) T->rchild=S;
　　else Insert_Node(T->rchild,S);
　}
　else if(S->data<T->data)
　{
　　if(!T->lchild) T->lchild=S;
　　else Insert_Node(T->lchild,S);
　}
　S->lchild=NULL; //插入的新结点必须和原来的左右子树断绝关系
　S->rchild=NULL; //否则会导致树结构的混乱
}//Insert_Node
分析:这是一个与课本上不同的插入算法.在合并过程中,并不释放或新建任何结点,而是采取修改指针的方式来完成合并.这样,就必须按照后序序列把一棵树中的元素逐个连接到另一棵树上,否则将会导致树的结构的混乱.

9.39

void BSTree_Split(BiTree &T,BiTree &A,BiTree &B,int x)//把二叉排序树T分裂为两棵二叉排序树A和B,其中A的元素全部小于等于x,B的元素全部大于x
{
　if(T->lchild) BSTree_Split(T->lchild,A,B,x);
　if(T->rchild) BSTree_Split(T->rchild,A,B,x); //分裂左右子树
　if(T->data<=x) Insert_Node(A,T);
　else Insert_Node(B,T); //将元素结点插入合适的树中
}//BSTree_Split

void Insert_Node(Bitree &T,BTNode *S)//把树结点S插入到T的合适位置上
{
　if(!T) T=S; //考虑到刚开始分裂时树A和树B为空的情况
　else if(S->data>T->data) //其余部分与上一题同
　{
　　if(!T->rchild) T->rchild=S;
　　else Insert_Node(T->rchild,S);
　}
　else if(S->data<T->data)
　{
　　if(!T->lchild) T->lchild=S;
　　else Insert_Node(T->lchild,S);
　}
　S->lchild=NULL;
　S->rchild=NULL;　
}//Insert_Key

9.40

typedef struct {
　　 　　　　　　　  int data;
　　　　　　　　　　int bf;
　　　　　　　　　　 int lsize; //lsize域表示该结点的左子树的结点总数加1
　　　　　  　　　　 BlcNode *lchild,*rchild;
　　　　　　　　  } BlcNode,*BlcTree; //含lsize域的平衡二叉排序树类型

BTNode *Locate_BlcTree(BlcTree T,int k)//在含lsize域的平衡二叉排序树T中确定第k小的结点指针
{
　if(!T) return NULL; //k小于1或大于树结点总数
　if(T->lsize==k) return T; //就是这个结点
　else if(T->lsize>k)
　　return Locate_BlcTree(T->lchild,k); //在左子树中寻找
　else return Locate_BlcTree(T->rchild,k-T->lsize); //在右子树中寻找,注意要修改k的值
}//Locate_BlcTree

9.41


typedef struct {
　　　　　　　　 enum {LEAF,BRANCH} tag; //结点类型标识
　　　　　　　　 int keynum;
　　　　　　　　 BPLink parent; //双亲指针
　　　　　　　　 int key[MAXCHILD]; //关键字
　　　　　　　　 union {
　　　　　　　　　　　　 BPLink child[MAXCHILD];//非叶结点的孩子指针
　　　　　　　　　　　　 struct {
　　　　　　　　　　　　　　　　　rectype *info[MAXCHILD];//叶子结点的信息指针
　　　　　　　　　　　　　　　　　BPNode *next; //指向下一个叶子结点的链接
　　　　　　　　　　　　　　　　  } leaf;
　　　　　　　　　　　　 }
　　　　　  　} BPNode,*BPLink,*BPTree;//B+树及其结点类型

Status BPTree_Search(BPTree T,int key,BPNode *ptr,int pos)//B+树中按关键字随机查找的算法,返回包含关键字的叶子结点的指针ptr以及关键字在叶子结点中的位置pos
{
　p=T;
　while(p.tag==BRANCH) //沿分支向下查找
　{
　　for(i=0;i<p->keynum&&key>p->key[i];i++); //确定关键字所在子树
　　if(i==p->keynum) return ERROR; //关键字太大
　　p=p->child[i];
　}
　for(i=0;i<p->keynum&&key!=p->key[i];i++); //在叶子结点中查找
　if(i==p->keynum) return ERROR; //找不到关键字
　ptr=p;pos=i;
　return OK;
}//BPTree_Search　

9.42

void TrieTree_Insert_Key(TrieTree &T,StringType key)//在Trie树T中插入字符串key,StringType的结构见第四章
{
　q=(TrieNode*)malloc(sizeof(TrieNode));
　q->kind=LEAF;
　q->lf.k=key; //建叶子结点
　klen=key[0];
　p=T;i=1;
　while(p&&i<=klen&&p->bh.ptr[ord(key[i])])
　{
　　last=p;
　　p=p->bh.ptr[ord(key[i])];
　　i++;
　} //自上而下查找
　if(p->kind==BRANCH) //如果最后落到分支结点(无同义词):
　{
　　p->bh.ptr[ord(key[i])]=q; //直接连上叶子
　　p->bh.num++;
　}
　else //如果最后落到叶子结点(有同义词):
　{
　　r=(TrieNode*)malloc(sizeof(TrieNode)); //建立新的分支结点
　　last->bh.ptr[ord(key[i-1])]=r; //用新分支结点取代老叶子结点和上一层的联系
　　r->kind=BRANCH;r->bh.num=2;
　　r->bh.ptr[ord(key[i])]=q;
　　r->bh.ptr[ord(p->lf.k[i])]=p; //新分支结点与新老两个叶子结点相连
　}
}//TrieTree_Insert_Key
分析:当自上而下的查找结束时,存在两种情况.一种情况,树中没有待插入关键字的同义词,此时只要新建一个叶子结点并连到分支结点上即可.另一种情况,有同义词,此时要把同义词的叶子结点与树断开,在断开的部位新建一个下一层的分支结点,再把同义词和新关键字的叶子结点连到新分支结点的下一层.

9.43

Status TrieTree_Delete_Key(TrieTree &T,StringType key)//在Trie树T中删除字符串key
{
　p=T;i=1;
　while(p&&p->kind==BRANCH&&i<=key[0]) //查找待删除元素
　{
　　last=p;
　　p=p->bh.ptr[ord(key[i])];
　　i++;
　}
　if(p&&p->kind==LEAF&&p->lf.k=key) //找到了待删除元素
　{
　　last->bh.ptr[ord(key[i-1])]=NULL;
　　free(p);
　　return OK;
　}
　else return ERROR; //没找到待删除元素
}//TrieTree_Delete_Key

9.44

void Print_Hash(HashTable H)//按第一个字母顺序输出Hash表中的所有关键字,其中处理冲突采用线性探测开放定址法
{
　for(i=1;i<=26;i++)
　　for(j=i;H.elem[j].key;j=(j+1)%hashsize[sizeindex]) //线性探测
　　　if(H(H.elem[j].key)==i) printf("%s\n",H.elem[j]);
}//Print_Hash

int H(char *s)//求Hash函数
{
　if(s) return s[0]-96; //求关键字第一个字母的字母序号(小写)
　else return 0;
}//H

9.45

typedef *LNode[MAXSIZE] CHashTable; //链地址Hash表类型

Status Build_Hash(CHashTable &T,int m)//输入一组关键字,建立Hash表,表长为m,用链地址法处理冲突.
{
　if(m<1) return ERROR;
　T=malloc(m*sizeof(WORD)); //建立表头指针向量
　for(i=0;i<m;i++) T[i]=NULL;
　while((key=Inputkey())!=NULL) //假定Inputkey函数用于从键盘输入关键字
　{
　　q=(LNode*)malloc(sizeof(LNode));
　　q->data=key;q->next=NULL;
　　n=H(key);
　　if(!T[n]) T[n]=q; //作为链表的第一个结点
　　else
　　{
　　　for(p=T[n];p->next;p=p->next);
　　　p->next=q; //插入链表尾部.本算法不考虑排序问题.
　　}
　}//while
　return OK;
}//Build_Hash

9.46

Status Locate_Hash(HashTable H,int row,int col,KeyType key,int &k)//根据行列值在Hash表表示的稀疏矩阵中确定元素key的位置k
{
　h=2*(100*(row/10)+col/10); //作者设计的Hash函数
　while(H.elem[h].key&&!EQ(H.elem[h].key,key))
　　h=(h+1)%20000;
　if(EQ(H.elem[h].key,key)) k=h;
　else k=NULL;
}//Locate_Hash
分析:本算法所使用的Hash表长20000,装填因子为50%,Hash函数为行数前两位和列数前两位所组成的四位数再乘以二,用线性探测法处理冲突.当矩阵的元素是随机分布时,查找的时间复杂度为O(1).