第九章习题(3)

else Insert_Key(B,T); //将元素结点插入合适的树中 }//BSTree_Split

void Insert_Key(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_Key(T->rchild,S); }

else if(S->datadata) {

if(!T->lchild) T->lchild=S; else Insert_Key(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;ikeynum&&key>p->key[i];i++); //确定关键字所在子树 if(i==p->keynum) return ERROR; //关键字太大

p=p->child[i]; }

for(i=0;ikeynum&&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(\}//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

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) 000;

if(EQ(H.elem[h].key,key)) k=h; else k=NULL; }//Locate_Hash

分析:本算法所使用的Hash表长20000,装填因子为50%,Hash函数为行数前两位和列数前两位所组成的四位数再乘以二,用线性探测法处理冲突.当矩阵的元素是随机分布时,查找的时间复杂度为O(1).