代码2.txt

实用数据结构课后习题解答

//二叉排序树的删除
template <class T>
int BS_Tree<T>∷delete_BS_Tree(T x)
{ BSnode<T> *p, *q, *t, *s;
int flag;
p=BT; q=NULL; flag=0;
while ((p!=NULL)&&(flag==0))//寻找被删元素
{ if (p->d==x)flag=1; //找到被删元素
else if (x<p->d)//沿左子树找
 { q=p; p=p->lchild; }
else//沿右子树找
 { q=p; p=p->rchild; }
}
if (p==NULL)//找不到
{ cout <<"找不到!" <<endl; return(flag); }
flag=1;
if ((p->lchild==NULL)&&(p->rchild==NULL))//p为叶子结点
{ if (p==BT)BT=NULL;//p为根结点
else if (p==q->lchild)q->lchild=NULL;
elseq->rchild=NULL;
delete p;//释放结点p
}
else if ((p->lchild==NULL)||(p->rchild==NULL))//p为单支子树
{ if (p==BT)//p为根结点
{ if (p->lchild==NULL)BT=p->rchild; 
elseBT=p->lchild;
}
else//p为单支子树,但p不是根结点
{ if ((p==q->lchild)&&(p->lchild!=NULL))//p是q的左子结点
q->lchild=p->lchild; //将p的左子树链接到q的左指针上
else if ((p==q->lchild)&&(p->rchild!=NULL)) //p是q的左子结点
q->lchild=p->rchild; //将p的右子树链接到q的左指针上
else if ((p==q->rchild)&&(p->lchild!=NULL)) //p是q的右子结点
q->rchild=p->lchild; //将p的左子树链接到q的右指针上
else //if ((p==q->rchild)&&(p->rchild!=NULL)) //p是q的右子结点
q->rchild=p->rchild;//将p的右子树链接到q的右指针上
}
delete p;//释放结点p
}
else //if ((p->lchild!=NULL)&&(p->rchild!=NULL)) //p的左右子树均不空
{ t=p;
s=t->lchild;//从p的左子结点开始
while (s->rchild!=NULL) //沿右链寻找右指针为空的结点s
 { t=s; s=s->rchild; } 
p->d=s->d; //结点s的值赋给p的值域
if (t==p)
p->lchild=s->lchild;//p的左子结点的左子树链接到p的左指针上
else
t->rchild=s->lchild;// s的左子树链接到p的右指针上
delete s; //释放结点s
}
return(flag);
}


//二叉排序树的查找
template <class T>
BSnode<T>* BS_Tree<T>∷serch_BS_Tree(T x)
{ BSnode<T> *p=NULL;
int flag;
p=BT; flag=0;
while ((p!=NULL)&&(flag==0))//寻找被删元素
{ if (p->d==x)flag=1; //找到被删元素
else if (x<p->d) p=p->lchild; //沿左子树找
else p=p->rchild; //沿右子树找
}
if (p==NULL)//找不到
{ cout <<"找不到!" <<endl; return(p); }
return(p);
}


//文件名L7_2.cpp
#include "BS_Tree.h"
int main()
{ int k;
int d\[12\]={04,18,13,79,33,45,06,23,35,12,34,76};
BS_Tree<int> b;//建立一个二叉排序树对象b，数据域为整型
for (k=0; k<12; k++)//依次将元素插入到二叉排序树b
b.insert_BS_Tree(d\[k\]);
cout <<"第1次输出中序序列:" <<endl;
b.intrav_BS_Tree();
for (k=0; k<6; k++)//在二叉排序树中依次删除原序列中的前6个元素
b.delete_BS_Tree(d\[k\]);
cout <<"第2次输出中序序列:" <<endl;
b.intrav_BS_Tree();
cout <<"查找结果:" <<endl;
for (k=0; k<12; k++)//在二叉排序树中查找原序列中的所有元素
cout <<b.serch_BS_Tree(d\[k\]) <<endl;
return 0;
}


第1次输出中序序列:
4
6
12
13
18
23
33
34
35
45
76
79
第2次输出中序序列:
6
12
23
34
35
76
查找结果:
找不到!
00000000
找不到!
00000000
找不到!
00000000
找不到!
00000000
找不到!
00000000
找不到!
00000000
00481EA0
00481F20
00481EE0
00480030
00481DA0
00481D60


//定义B-树中的结点类型
template <class T>
struct mb1node
{ int num; //记录结点中的关键字个数
mb1node *prt;//指向父结点的指针
T key\[2*M\];//2m个关键字域
mb1node *link\[2*M+1\];//2m+1个指向各子树的指针
};


//文件名MB1.h
#define M2
#include <iostream>
using namespace std;
//定义B-树中的结点类型
template <class T>
struct mb1node
{ int num; //记录结点中的关键字个数
mb1node *prt;//指向父结点的指针
T key\[2*M\];//2m个关键字域
mb1node *link\[2*M+1\];//2m+1个指向各子树的指针
};
//定义B-树类
template <class T>
class MB1
{ private:
mb1node<T> *BTH; //B-树根结点指针
public: //成员函数
MB1() { BTH=NULL; return; }//B-树初始化
mb1node<T> *MB1_search(T, int *, int *); //B-树的查找
void MB1_insert(T);//B-树的插入
void MB1_delete(T); //B-树的删除
void MB1_prt(); //按值大小输出B-树
};


//在B-树中查找元素x所在结点的存储位置以及在该结点中的关键字序号k
//函数返回结点存储空间首地址，flag=0表示查找失败。
template <class T>
mb1node<T>* MB1<T>∷MB1_search(T x, int *k, int *flag)
{ mb1node<T>*p,*q;
p=BTH; *flag=0; q=p;
while ((p!=NULL)&&(*flag==0))// 未到叶子结点且并未找到该元素
{ *k=1; q=p;
while ((*k<q->num)&&(q->key\[*k-1\]<x)) //与各关键字比较
*k=*k+1;
if (q->key\[*k-1\]==x)//查找成功
*flag=1;
else if ((*k==q->num)&&(q->key\[*k-1\]<x))//向下搜索
p=q->link\[*k\];
else//向下搜索
 { p=q->link\[*k-1\];*k=*k-1; }
}
return(q);//返回被查元素x应在结点的首地址
}


//在B-树中插入x
template <class T>
void MB1<T>∷MB1_insert(T x)
{ intflag,j,k,t;
Ty;
mb1node<T>*p,*q,*u,*s;
if (BTH==NULL)//B-树为空
{ p=new mb1node<T>;//申请一个结点
p->num=1;//置该结点中只有1个关键字
p->key\[0\]=x; //置关键字
p->prt=NULL; //指向父结点的指针为空
for (j=1; j<=2*M+1; j++) //置所有指针为空
p->link\[j-1\]=NULL;
BTH=p; //B-树根结点指针 
return;
}
q=(mb1node<T> *)MB1_search(x,&k,&flag);//寻找插入位置
if (flag==1)//B-树中已有元素x，不能再插入
{ cout <<"ERR!\\n"; return; }
p=NULL; 
t=0;//未插入完标志
while (t==0)//未插入完
{ if (k==(q->num)) //插入到结点q的最后
{ y=x;//记录结点q的最后应插入的关键字
u=p;//记录结点q的最后应插入的向下指针
}
else//插入到结点q的中间某位置处
{ y=q->key\[q->num-1\]; //记录结点q中的最后一个关键字 
u=q->link\[q->num\];//记录结点q中最后一个向下指针
for (j=(q->num)-1; j>=k+1; j--)//结点q中最后第二个关键字到
{ q->key\[j\]=q->key\[j-1\];//插入位置处的关键字以及对应的
q->link\[j+1\]=q->link\[j\];//向下指针均后移一个位置。
}
q->key\[k\]=x;//在插入位置处插入关键字x 
q->link\[k+1\]=p; //在插入位置后插入关键字x的向下指针
if (p!=NULL)
p->prt=q;//改变结点p中指向父结点的指针
}
if (q->num<2*M)//结点q中关键字未满，可直接插入
{ q->num=(q->num)+1; //结点q中的关键字个数增1
q->key\[(q->num)-1\]=y; //将记录的关键字插入到q的最后
q->link\[q->num\]=u;//将记录的向下指针插入到q的最后
if (u!=NULL)
u->prt=q; //改变结点u中指向父结点的指针
t=1;//置插入完成标志
}
else//结点q中关键字已满，应进行分裂
{ p=new mb1node<T>; //申请一个新结点
p->num=M; //新结点中存放结点q中的一半关键字
q->num=M; //结点q中保留原一半的关键字
p->prt=q->prt;//结点q的父结点也是新结点p的父结点
x=q->key\[M\];//记录原结点q中的中间关键字，应插入到父结点
for (j=1; j<=M-1; j++)
{ p->key\[j-1\]=q->key\[M+j\]; //将原结点q中的后半部的关键字
p->link\[j-1\]=q->link\[M+j\]; //和向下指针复制到结点p中
if (q->link\[M+j\]!=NULL)
(q->link\[M+j\])->prt=p; //改变子结点中指向父结点的指针 
}
p->link\[M-1\]=q->link\[2*M\]; //将q中的最后一个指针复制到p中
if (q->link\[2*M\]!=NULL)
(q->link\[2*M\])->prt=p; //改变子结点中指向父结点的指针
p->key\[M-1\]=y; //将记录的关键字插入到p的最后
p->link\[M\]=u; //将记录的向下指针插入到p的最后
if (u!=NULL)
u->prt=p; //改变结点u中指向父结点的指针
for (j=M+2; j<=2*M+1; j++)
{ q->link\[j-1\]=NULL; //置结点q后半部分指针为空
p->link\[j-1\]=NULL; //置结点p后半部分指针为空
}
if (q->prt==NULL)//q为根结点
{ s=new mb1node<T>; //申请一个新结点作为新的根结点
s->key\[0\]=x; //插入原结点q分裂时的中间关键字x
s->link\[0\]=q;//第一个指针指向q
s->link\[1\]=p;//第二个指针指向p
s->num=1;//根结点中关键字个数为1
s->prt=NULL; //根结点无父结点
q->prt=s; p->prt=s;//结点p与q的父结点均为根结点s
for (j=3; j<=2*M+1; j++)
s->link\[j-1\]=NULL;//置根结点中后面的指针为空
BTH=s; //s为B-树的根结点
t=1;//置插入完成标志
}
else//q不是根结点
{ q=q->prt;//原结点q分裂时的中间关键字x应插入到q的父结点
k=1;
while ((k<=q->num)&&(q->key\[k-1\]<x))//寻找插入位置
k=k+1; 
k=k-1;
}
}
}
return;
}


//在B-树中删除x
template <class T>
void MB1<T>∷MB1_delete(T x)
{ intflag,j,k,t;
Ty; 
mb1node<T>*u,*s=NULL,*p,*q;
q=(mb1node<T> *)MB1_search(x,&k,&flag); //寻找需要删除的关键字x
if (flag==0)//要删除的关键字x不存在
 { cout <<"not this key!\\n"; return; }
p=q->link\[k\];//关键字x右边的指针
if (p!=NULL)//要删除的关键字x不在叶子结点上
{ while (p->link\[0\]!=NULL)//寻找最左边的叶子结点p
p=p->link\[0\];
q->key\[k-1\]=p->key\[0\]; //用该叶子结点p中的第一个关键字
 //代替结点q中的x
k=1; q=p; //删除结点p中的第一个关键字
}
for (j=k; j<=q->num-1; j++)//删除结点q中的第k个关键字
q->key\[j-1\]=q->key\[j\];
q->num=q->num-1;//结点q中的关键字个数减1
while ((q!=BTH)&&(q->num<M)) //结点q非根结点且其中关键字个数小于M
{ p=q->prt; j=1;
while (p->link\[j-1\]!=q) //寻找结点q在父结点p中的指针位置
j=j+1;
if ((j<=p->num)&&((p->link\[j\])->num>M))
{ s=p->link\[j\];//从右兄弟结点中借关键字
y=s->key\[0\];//借最左边的关键字
u=s->link\[0\]; //最左边的指针
for (k=1; k<=s->num-1; k++)
{ s->key\[k-1\]=s->key\[k\]; //关键字左移
s->link\[k-1\]=s->link\[k\]; //指针左移
}
s->link\[s->num-1\]=s->link\[s->num\];//最后一个指针左移
s->link\[s->num\]=NULL;//置最后一个指针为空
s->num=s->num-1;//右兄弟结点中的关键字个数减1
q->num=q->num+1;//结点q的关键字个数增1
q->key\[q->num-1\]=p->key\[j-1\]; //复制父结点中的关键字
p->key\[j-1\]=y; //借的关键字复制到父结点
q->link\[q->num\]=u; //复制指针
if (u!=NULL)
u->prt=q;//改变指向父结点的指针
}
else if ((j>1)&&((p->link\[j-2\])->num>M))
{ s=p->link\[j-2\];//从左兄弟结点中借关键字
q->num=q->num+1; //结点q的关键字个数增1
q->link\[q->num\]=q->link\[q->num-1\];//最后一个关键字右移
for (k=q->num-1; k>=1; k--) 
{ q->key\[k\]=q->key\[k-1\];//关键字右移
q->link\[k\]=q->link\[k-1\];//指针右移
}
q->key\[0\]=p->key\[j-2\];//复制父结点中的关键字
q->link\[0\]=s->link\[s->num\]; //复制左兄弟结点中的指针
u=s->link\[s->num\];
if (u!=NULL)
u->prt=q;//改变指向父结点的指针
p->key\[j-2\]=s->key\[s->num-1\]; //借的关键字复制到父结点
s->link\[s->num\]=NULL;//置左兄弟结点中最后一个指针为空
s->num=s->num-1;//左兄弟结点中的关键字个数减1
}
else//需要合并
{ if (j==p->num+1) //结点q在父结点p中的最后指针位置
{ q=p->link\[j-2\]; //要合并的结点之一
s=p->link\[j-1\]; //要合并的结点之二
j=j-1;
}
elses=p->link\[j\]; //要合并的结点之二
q->key\[q->num\]=p->key\[j-1\];//父结点中的关键字复制到q结点最后
t=q->num+1;//记录结点q中关键字个数增1
for (k=1; k<=s->num; k++) //邻近两个结点合并
{ q->key\[t+k-1\]=s->key\[k-1\];
q->link\[t+k-1\]=s->link\[k-1\];
u=s->link\[k-1\];
if (u!=NULL)
u->prt=q;//改变指向父结点的指针
}
q->link\[t+s->num\]=s->link\[s->num\]; //最后的指针合并
u=s->link\[s->num\];
if (u!=NULL)
u->prt=q;//改变指向父结点的指针
q->num=2*M;//结点q中的关键字个数
delete s; //释放结点s
for (k=j; k<=p->num-1; k++)//父结点中的关键字与指针左移
{ p->key\[k-1\]=p->key\[k\];
p->link\[k\]=p->link\[k+1\];
}
p->num=p->num-1; //父结点中关键字个数减1
s=q; q=p; 
}
}
if ((q==BTH)&&(q->num==0))//合并到了B-树的根结点，且其中无关键字
{ delete BTH;
if (s!=NULL)//s为B-树的根结点
{ BTH=s; BTH->prt=NULL; }
else//B-树为空
{ BTH=NULL; delete s;}
}
return;
}


//按值大小输出B-树
template <class T>
void MB1<T>∷MB1_prt()
{ 
MB1_out(BTH);//从根结点开始搜索
return;
}
template <class T>
static MB1_out(mb1node<T> *p)
{ int n;
if (p!=NULL) //该结点不空
 { for (n=0; n<p->num; n++)//对于该结点中的每一个关键字
{ MB1_out(p->link\[n\]); //沿关键字左指针向下搜索
cout <<p->key\[n\] <<endl; //输出关键字值
}
 MB1_out(p->link\[n\]); //沿最后一个指针向下搜索
 }
return 0;
}


//文件名L7_3.cpp
#include "MB1.h"
int main()
{ int x, k;
int d\[12\]={04,18,13,79,33,45,06,23,35,12,34,76};
MB1<int> mb1; //定义B-树对象
for (k=0; k<12; k++)//生成B-树
 { x=d\[k\]; mb1.MB1_insert(x); }
cout <<"第1次按值大小输出B-树:" <<endl;
mb1.MB1_prt();
for (k=0; k<6; k++) //在B-树中删除前6个插入的关键字
 { x=d\[k\]; mb1.MB1_delete(x); }
cout <<"第2次按值大小输出B-树:" <<endl;
mb1.MB1_prt();
return 0;
}


第1次按值大小输出B-树:
4
6
12
13
18
23
33
34
35
45
76
79
第2次按值大小输出B-树:
6
12
23
34
35
76


//定义B+树中的结点类型
template <class T>
struct mb2node
{ int num; //记录结点中的关键字个数
mb2node *prt;//指向父结点的指针
T key\[2*M\];//2m个关键字域
mb21node *link\[2*M+1\];//2m+1个指向各子树的指针