第九章 查找
9.25
int Search_Sq(SSTable ST,int key)//在有序表上顺序查找的算法,监视哨设在高下标端
{
ST.elem[ST.length+1].key=key;
for(i=1;ST.elem[i].key>key;i++);
if(i>ST.length||ST.elem[i].key<key) return ERROR;
return i;
}//Search_Sq
分析:本算法查找成功情况下的平均查找长度为ST.length/2,不成功情况下为ST.length,
9.26
int Search_Bin_Recursive(SSTable ST,int key,int low,int high)//折半查找的递归算法
{
if(low>high) return 0; //查找不到时返回0
mid=(low+high)/2;
if(ST.elem[mid].key==key) return mid;
else if(ST.elem[mid].key>key)
return Search_Bin_Recursive(ST,key,low,mid-1);
else return Search_Bin_Recursive(ST,key,mid+1,high);
}
}//Search_Bin_Recursive
9.27
int Locate_Bin(SSTable ST,int key)//折半查找,返回小于或等于待查元素的最后一个结点号
{
int *r;
r=ST.elem;
if(key<r.key) return 0;
else if(key>=r[ST.length].key) return ST.length;
low=1;high=ST.length;
while(low<=high)
{
mid=(low+high)/2;
if(key>=r[mid].key&&key<r[mid+1].key) //查找结束的条件
return mid;
else if(key<r[mid].key) high=mid;
else low=mid;
} //本算法不存在查找失败的情况,不需要return 0;
}//Locate_Bin
9.28
typedef struct {
int maxkey;
int firstloc;
} Index;
typedef struct {
int *elem;
int length;
Index idx[MAXBLOCK]; //每块起始位置和最大元素,其中idx[0]不利用,其内容初始化为{0,0}以利于折半查找
int blknum; //块的数目
} IdxSqList; //索引顺序表类型
int Search_IdxSeq(IdxSqList L,int key)//分块查找,用折半查找法确定记录所在块,块内采用顺序查找法
{
if(key>L.idx[L.blknum].maxkey) return ERROR; //超过最大元素
low=1;high=L.blknum;
found=0;
while(low<=high&&!found) //折半查找记录所在块号mid
{
mid=(low+high)/2;
if(key<=L.idx[mid].maxkey&&key>L.idx[mid-1].maxkey)
found=1;
else if(key>L.idx[mid].maxkey)
low=mid+1;
else high=mid-1;
}
i=L.idx[mid].firstloc; //块的下界
j=i+blksize-1; //块的上界
temp=L.elem[i-1]; //保存相邻元素
L.elem[i-1]=key; //设置监视哨
for(k=j;L.elem[k]!=key;k--); //顺序查找
L.elem[i-1]=temp; //恢复元素
if(k<i) return ERROR; //未找到
return k;
}//Search_IdxSeq
分析:在块内进行顺序查找时,如果需要设置监视哨,则必须先保存相邻块的相邻元素,以免数据丢失,
9.29
typedef struct {
LNode *h; //h指向最小元素
LNode *t; //t指向上次查找的结点
} CSList;
LNode *Search_CSList(CSList &L,int key)//在有序单循环链表存储结构上的查找算法,假定每次查找都成功
{
if(L.t->data==key) return L.t;
else if(L.t->data>key)
for(p=L.h,i=1;p->data!=key;p=p->next,i++);
else
for(p=L.t,i=L.tpos;p->data!=key;p=p->next,i++);
L.t=p; //更新t指针
return p;
}//Search_CSList
分析:由于题目中假定每次查找都是成功的,所以本算法中没有关于查找失败的处理.由微积分可得,在等概率情况下,平均查找长度约为n/3,
9.30
typedef struct {
DLNode *pre;
int data;
DLNode *next;
} DLNode;
typedef struct {
DLNode *sp;
int length;
} DSList; //供查找的双向循环链表类型
DLNode *Search_DSList(DSList &L,int key)//在有序双向循环链表存储结构上的查找算法,假定每次查找都成功
{
p=L.sp;
if(p->data>key)
{
while(p->data>key) p=p->pre;
L.sp=p;
}
else if(p->data<key)
{
while(p->data<key) p=p->next;
L.sp=p;
}
return p;
}//Search_DSList
分析:本题的平均查找长度与上一题相同,也是n/3,
9.31
int last=0,flag=1;
int Is_BSTree(Bitree T)//判断二叉树T是否二叉排序树,是则返回1,否则返回0
{
if(T->lchild&&flag) Is_BSTree(T->lchild);
if(T->data<last) flag=0; //与其中序前驱相比较
last=T->data;
if(T->rchild&&flag) Is_BSTree(T->rchild);
return flag;
}//Is_BSTree
9.32
int last=0;
void MaxLT_MinGT(BiTree T,int x)//找到二叉排序树T中小于x的最大元素和大于x的最小元素
{
if(T->lchild) MaxLT_MinGT(T->lchild,x); //本算法仍是借助中序遍历来实现
if(last<x&&T->data>=x) //找到了小于x的最大元素
printf("a=%d\n",last);
if(last<=x&&T->data>x) //找到了大于x的最小元素
printf("b=%d\n",T->data);
last=T->data;
if(T->rchild) MaxLT_MinGT(T->rchild,x);
}//MaxLT_MinGT
9.33
void Print_NLT(BiTree T,int x)//从大到小输出二叉排序树T中所有不小于x的元素
{
if(T->rchild) Print_NLT(T->rchild,x);
if(T->data<x) exit(); //当遇到小于x的元素时立即结束运行
printf("%d\n",T->data);
if(T->lchild) Print_NLT(T->lchild,x); //先右后左的中序遍历
}//Print_NLT
9.34
void Delete_NLT(BiTree &T,int x)//删除二叉排序树T中所有不小于x元素结点,并释放空间
{
if(T->rchild) Delete_NLT(T->rchild,x);
if(T->data<x) exit(); //当遇到小于x的元素时立即结束运行
q=T;
T=T->lchild;
free(q); //如果树根不小于x,则删除树根,并以左子树的根作为新的树根
if(T) Delete_NLT(T,x); //继续在左子树中执行算法
}//Delete_NLT
9.35
void Print_Between(BiThrTree T,int a,int b)//打印输出后继线索二叉排序树T中所有大于a且小于b的元素
{
p=T;
while(!p->ltag) p=p->lchild; //找到最小元素
while(p&&p->data<b)
{
if(p->data>a) printf("%d\n",p->data); //输出符合条件的元素
if(p->rtag) p=p->rtag;
else
{
p=p->rchild;
while(!p->ltag) p=p->lchild;
} //转到中序后继
}//while
}//Print_Between
9.36
void BSTree_Insert_Key(BiThrTree &T,int x)//在后继线索二叉排序树T中插入元素x
{
if(T->data<x) //插入到右侧
{
if(T->rtag) //T没有右子树时,作为右孩子插入
{
p=T->rchild;
q=(BiThrNode*)malloc(sizeof(BiThrNode));
q->data=x;
T->rchild=q;T->rtag=0;
q->rtag=1;q->rchild=p; //修改原线索
}
else BSTree_Insert_Key(T->rchild,x);//T有右子树时,插入右子树中
}//if
else if(T->data>x) //插入到左子树中
{
if(!T->lchild) //T没有左子树时,作为左孩子插入
{
q=(BiThrNode*)malloc(sizeof(BiThrNode));
q->data=x;
T->lchild=q;
q->rtag=1;q->rchild=T; //修改自身的线索
}
else BSTree_Insert_Key(T->lchild,x);//T有左子树时,插入左子树中
}//if
}//BSTree_Insert_Key
9.37
Status BSTree_Delete_key(BiThrTree &T,int x)//在后继线索二叉排序树T中删除元素x
{
BTNode *pre,*ptr,*suc;//ptr为x所在结点,pre和suc分别指向ptr的前驱和后继
p=T;last=NULL; //last始终指向当前结点p的前一个(前驱)
while(!p->ltag) p=p->lchild; //找到中序起始元素
while(p)
{
if(p->data==x) //找到了元素x结点
{
pre=last;
ptr=p;
}
else if(last&&last->data==x) suc=p; //找到了x的后继
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).
9.25
int Search_Sq(SSTable ST,int key)//在有序表上顺序查找的算法,监视哨设在高下标端
{
ST.elem[ST.length+1].key=key;
for(i=1;ST.elem[i].key>key;i++);
if(i>ST.length||ST.elem[i].key<key) return ERROR;
return i;
}//Search_Sq
分析:本算法查找成功情况下的平均查找长度为ST.length/2,不成功情况下为ST.length,
9.26
int Search_Bin_Recursive(SSTable ST,int key,int low,int high)//折半查找的递归算法
{
if(low>high) return 0; //查找不到时返回0
mid=(low+high)/2;
if(ST.elem[mid].key==key) return mid;
else if(ST.elem[mid].key>key)
return Search_Bin_Recursive(ST,key,low,mid-1);
else return Search_Bin_Recursive(ST,key,mid+1,high);
}
}//Search_Bin_Recursive
9.27
int Locate_Bin(SSTable ST,int key)//折半查找,返回小于或等于待查元素的最后一个结点号
{
int *r;
r=ST.elem;
if(key<r.key) return 0;
else if(key>=r[ST.length].key) return ST.length;
low=1;high=ST.length;
while(low<=high)
{
mid=(low+high)/2;
if(key>=r[mid].key&&key<r[mid+1].key) //查找结束的条件
return mid;
else if(key<r[mid].key) high=mid;
else low=mid;
} //本算法不存在查找失败的情况,不需要return 0;
}//Locate_Bin
9.28
typedef struct {
int maxkey;
int firstloc;
} Index;
typedef struct {
int *elem;
int length;
Index idx[MAXBLOCK]; //每块起始位置和最大元素,其中idx[0]不利用,其内容初始化为{0,0}以利于折半查找
int blknum; //块的数目
} IdxSqList; //索引顺序表类型
int Search_IdxSeq(IdxSqList L,int key)//分块查找,用折半查找法确定记录所在块,块内采用顺序查找法
{
if(key>L.idx[L.blknum].maxkey) return ERROR; //超过最大元素
low=1;high=L.blknum;
found=0;
while(low<=high&&!found) //折半查找记录所在块号mid
{
mid=(low+high)/2;
if(key<=L.idx[mid].maxkey&&key>L.idx[mid-1].maxkey)
found=1;
else if(key>L.idx[mid].maxkey)
low=mid+1;
else high=mid-1;
}
i=L.idx[mid].firstloc; //块的下界
j=i+blksize-1; //块的上界
temp=L.elem[i-1]; //保存相邻元素
L.elem[i-1]=key; //设置监视哨
for(k=j;L.elem[k]!=key;k--); //顺序查找
L.elem[i-1]=temp; //恢复元素
if(k<i) return ERROR; //未找到
return k;
}//Search_IdxSeq
分析:在块内进行顺序查找时,如果需要设置监视哨,则必须先保存相邻块的相邻元素,以免数据丢失,
9.29
typedef struct {
LNode *h; //h指向最小元素
LNode *t; //t指向上次查找的结点
} CSList;
LNode *Search_CSList(CSList &L,int key)//在有序单循环链表存储结构上的查找算法,假定每次查找都成功
{
if(L.t->data==key) return L.t;
else if(L.t->data>key)
for(p=L.h,i=1;p->data!=key;p=p->next,i++);
else
for(p=L.t,i=L.tpos;p->data!=key;p=p->next,i++);
L.t=p; //更新t指针
return p;
}//Search_CSList
分析:由于题目中假定每次查找都是成功的,所以本算法中没有关于查找失败的处理.由微积分可得,在等概率情况下,平均查找长度约为n/3,
9.30
typedef struct {
DLNode *pre;
int data;
DLNode *next;
} DLNode;
typedef struct {
DLNode *sp;
int length;
} DSList; //供查找的双向循环链表类型
DLNode *Search_DSList(DSList &L,int key)//在有序双向循环链表存储结构上的查找算法,假定每次查找都成功
{
p=L.sp;
if(p->data>key)
{
while(p->data>key) p=p->pre;
L.sp=p;
}
else if(p->data<key)
{
while(p->data<key) p=p->next;
L.sp=p;
}
return p;
}//Search_DSList
分析:本题的平均查找长度与上一题相同,也是n/3,
9.31
int last=0,flag=1;
int Is_BSTree(Bitree T)//判断二叉树T是否二叉排序树,是则返回1,否则返回0
{
if(T->lchild&&flag) Is_BSTree(T->lchild);
if(T->data<last) flag=0; //与其中序前驱相比较
last=T->data;
if(T->rchild&&flag) Is_BSTree(T->rchild);
return flag;
}//Is_BSTree
9.32
int last=0;
void MaxLT_MinGT(BiTree T,int x)//找到二叉排序树T中小于x的最大元素和大于x的最小元素
{
if(T->lchild) MaxLT_MinGT(T->lchild,x); //本算法仍是借助中序遍历来实现
if(last<x&&T->data>=x) //找到了小于x的最大元素
printf("a=%d\n",last);
if(last<=x&&T->data>x) //找到了大于x的最小元素
printf("b=%d\n",T->data);
last=T->data;
if(T->rchild) MaxLT_MinGT(T->rchild,x);
}//MaxLT_MinGT
9.33
void Print_NLT(BiTree T,int x)//从大到小输出二叉排序树T中所有不小于x的元素
{
if(T->rchild) Print_NLT(T->rchild,x);
if(T->data<x) exit(); //当遇到小于x的元素时立即结束运行
printf("%d\n",T->data);
if(T->lchild) Print_NLT(T->lchild,x); //先右后左的中序遍历
}//Print_NLT
9.34
void Delete_NLT(BiTree &T,int x)//删除二叉排序树T中所有不小于x元素结点,并释放空间
{
if(T->rchild) Delete_NLT(T->rchild,x);
if(T->data<x) exit(); //当遇到小于x的元素时立即结束运行
q=T;
T=T->lchild;
free(q); //如果树根不小于x,则删除树根,并以左子树的根作为新的树根
if(T) Delete_NLT(T,x); //继续在左子树中执行算法
}//Delete_NLT
9.35
void Print_Between(BiThrTree T,int a,int b)//打印输出后继线索二叉排序树T中所有大于a且小于b的元素
{
p=T;
while(!p->ltag) p=p->lchild; //找到最小元素
while(p&&p->data<b)
{
if(p->data>a) printf("%d\n",p->data); //输出符合条件的元素
if(p->rtag) p=p->rtag;
else
{
p=p->rchild;
while(!p->ltag) p=p->lchild;
} //转到中序后继
}//while
}//Print_Between
9.36
void BSTree_Insert_Key(BiThrTree &T,int x)//在后继线索二叉排序树T中插入元素x
{
if(T->data<x) //插入到右侧
{
if(T->rtag) //T没有右子树时,作为右孩子插入
{
p=T->rchild;
q=(BiThrNode*)malloc(sizeof(BiThrNode));
q->data=x;
T->rchild=q;T->rtag=0;
q->rtag=1;q->rchild=p; //修改原线索
}
else BSTree_Insert_Key(T->rchild,x);//T有右子树时,插入右子树中
}//if
else if(T->data>x) //插入到左子树中
{
if(!T->lchild) //T没有左子树时,作为左孩子插入
{
q=(BiThrNode*)malloc(sizeof(BiThrNode));
q->data=x;
T->lchild=q;
q->rtag=1;q->rchild=T; //修改自身的线索
}
else BSTree_Insert_Key(T->lchild,x);//T有左子树时,插入左子树中
}//if
}//BSTree_Insert_Key
9.37
Status BSTree_Delete_key(BiThrTree &T,int x)//在后继线索二叉排序树T中删除元素x
{
BTNode *pre,*ptr,*suc;//ptr为x所在结点,pre和suc分别指向ptr的前驱和后继
p=T;last=NULL; //last始终指向当前结点p的前一个(前驱)
while(!p->ltag) p=p->lchild; //找到中序起始元素
while(p)
{
if(p->data==x) //找到了元素x结点
{
pre=last;
ptr=p;
}
else if(last&&last->data==x) suc=p; //找到了x的后继
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).
