代码2.txt

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

};


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


//B+树的顺序查找
//函数返回包含元素x的结点存储地址；指针变量k指向的变量中
//存放元素x在存储结点中的序号；指针变量flag指向的变量值为0时，
//表示查找失败，值为1时表示查找成功。
template <class T>
mb2node<T>* MB2<T>∷MB2_shch(T x, int *k, int *flag)
{ mb2node<T>*p,*q;
p=SH; //从顺序链第一个结点开始
*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; //在当前叶子结点中寻找关键字值不小于x的位置
if (q->key\[*k-1\]==x)
*flag=1;//查找成功
else if ((*k==q->num)&&(q->key\[*k-1\]<x))
 { p=q->link\[0\]; //顺序链中下一个结点
 if ((p!=NULL)&&(p->key\[0\]>x))
 p=NULL;//查找失败
 }
else { *k=*k-1; p=NULL; } //查找失败
}
return(q);
}


//B+树的随机查找
//函数返回包含元素x的结点存储地址；指针变量k指向的变量中
//存放元素x在存储结点中的序号；指针变量flag指向的变量值为0时，
//表示查找失败，值为1时表示查找成功。
template <class T>
mb2node<T>* MB2<T>∷MB2_search(T x, int *k, int *flag)
{ mb2node<T>*p,*q;
p=BTH;//从根结点开始
*flag=0; q=p;
if (p==NULL) return(q);//B+树为空
while ((p!=NULL)&&(*flag==0)) //未到叶子结点且还未查到
{ *k=1; q=p;
while ((*k<q->num)&&(q->key\[*k-1\]<x))
*k=*k+1;//在当前结点中寻找索引值不小于x的位置
if (q->key\[*k-1\]==x)//当前结点中的索引值等于x
{ if (q->link\[*k\]==NULL) //索引的右指针为空
*flag=1;//当前结点为叶子结点，查找成功
else p=q->link\[*k\];//沿索引的右指针向下搜索
}
else if ((*k==q->num)&&(q->key\[*k-1\]<x))
p=q->link\[*k\]; //沿索引的右指针向下搜索
else if (*k<2) //被查值在最左边的叶子结点中
{ q=MB2_shch(x,k,flag); p=NULL; }//采用顺序查找
else //沿索引的左指针向下搜索
{ p=q->link\[*k-1\];*k=*k-1; }
}
return(q);
}


//B+树的插入
template <class T>
void MB2<T>∷MB2_insert(T x)
{ intflag,j,k,t;
Ty; 
mb2node<T>*p,*q,*u,*s,*w;
if (BTH==NULL)//B+树为空
{ p=new mb2node<T>;//申请一个新结点
p->num=1; //新结点中关键字个数为1
p->key\[0\]=x;//新结点的第1个关键字
p->prt=NULL;//新结点为根结点，无父结点
for (j=1; j<=2*M+1; j++)
p->link\[j-1\]=NULL; //新结点中的所有指针为空
BTH=p; SH=p; //置根结点指针和顺序链头指针
return; //插入结束
}
q=MB2_shch(x,&k,&flag);//用顺序查找法查找插入位置
//q=MB2_search(x,&k,&flag); //也可以用随机查找法查找插入位置 
w=q;
if (flag==1)//B+树中已有该关键字，不能再插入
{ 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\];//插入位置处的关键字均后移一位置
if (w-q!=0) //若q不是叶子结点，则指针也后移一个位置
q->link\[j+1\]=q->link\[j\];
}
q->key\[k\]=x;//插入新关键字x
if (w-q!=0)//若q不是叶子结点,则插入关键字x的向下指针
q->link\[k+1\]=p;
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的最后
if (w-q!=0)//若q不是叶子结点
q->link\[q->num\]=u;//则将记录的向下指针插入到最后
if (u!=NULL)
u->prt=q; //改变结点u中指向父结点的指针
t=1; //置插入完成标志
}
else //结点q中关键字已满，应进行分裂
{ p=new mb2node<T>; //申请新结点
for (j=1; j<=2*M+1; j++)
p->link\[j-1\]=NULL; //置新结点中所有指针为空
p->num=M+1;//新结点关键字个数
q->num=M;//结点q中只保留一半关键字
p->prt=q->prt; //结点q的父结点也是新结点的父结点
x=q->key\[M\];//记录原结点q中的中间关键字，应插入到父结点
for (j=1; j<=M; j++)
{ p->key\[j-1\]=q->key\[M+j-1\];//将原结点q中的后半部的关键字
p->link\[j\]=q->link\[M+j\];//和向下指针复制到结点p中
if (q->link\[M+j\]!=NULL)
(q->link\[M+j\])->prt=p;//改变子结点中指向父结点的指针 
}
p->link\[M+1\]=u;//将记录的向下指针插入到p的最后
p->key\[M\]=y;//将记录的关键字插入到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\[0\]=q->link\[0\]; //将新结点p插入到顺序链中
q->link\[0\]=p;//即将新结点p链接到结点q的后面
if (q->prt==NULL)//q为根结点
{ s=new mb2node<T>; //申请一个新结点作为新的根结点
s->key\[0\]=q->key\[0\];//复制q中的第1个关键字到结点s
s->key\[1\]=x; //插入结点q分裂时的中间关键字x
s->link\[1\]=q; //第二个指针指向q
s->link\[2\]=p; //第三个指针指向p
s->num=2;//根结点中关键字个数为2
s->prt=NULL; //根结点无父结点
q->prt=s; p->prt=s; //结点p与q的父结点均为根结点s
s->link\[0\]=NULL;//根结点第一个指针为空
for (j=3; j<=2*M; j++)
s->link\[j\]=NULL;//置根结点中后面的指针为空
BTH=s;//置根结点指针
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+树的删除
template <class T>
void MB2<T>∷MB2_delete(T x)
{ intflag,j,k,t;
Ty; 
mb2node<T>*u,*s=NULL,*p,*q;
q=MB2_shch(x,&k,&flag); //用顺序查找法寻找被删除关键字的位置
//q=MB2_search(x,&k,&flag);//也可用随机查找法查找被删关键字的位置
if (flag==0)//B+树中没有该关键字
 { cout <<"not this key!\\n"; return; }
for (j=k; j<=q->num-1; j++)
q->key\[j-1\]=q->key\[j\]; //删除关键字
q->num=q->num-1;//结点q中关键字个数减1
if (q==BTH)//结点q为根结点
{ if (q->num==0)//关键字个数变为0，即B+树变空
{ delete BTH; BTH=NULL; SH=NULL; }
return;
}
while ((q!=BTH)&&(q->num<M))//q不是根结点且关键字个数小于M
{ p=q->prt; j=1;
while (p->link\[j\]!=q)
j=j+1;//寻找结点q在父结点中的指针位置
if ((j<p->num)&&((p->link\[j+1\])->num>M))
{ s=p->link\[j+1\]; //从右兄弟结点中借关键字
y=s->key\[0\];//借最左边的关键字
u=s->link\[1\]; //最左边的第二个指针
for (k=1; k<=s->num-1; k++)
{ s->key\[k-1\]=s->key\[k\];//关键字左移
s->link\[k\]=s->link\[k+1\]; //指针左移

}
s->link\[s->num\]=NULL; //置最后一个指针为空
q->key\[q->num\]=y;//借的关键字复制到父结点 
q->link\[q->num+1\]=u; //借的指针复制到父结点
p->key\[j\]=s->key\[0\];//在父结点中置新的路标值
if (u!=NULL)
u->prt=q;//改变指向父结点的指针
s->num=s->num-1;//右兄弟结点中的关键字个数减1
q->num=q->num+1;//结点q的关键字个数增1
}
else if ((j>1)&&((p->link\[j-1\])->num>M))
{ s=p->link\[j-1\]; //从左兄弟结点中借关键字
for (k=q->num; k>=1; k--)
{ q->key\[k\]=q->key\[k-1\];//关键字右移
q->link\[k+1\]=q->link\[k\]; //指针右移
}
q->key\[0\]=s->key\[s->num-1\]; //复制左兄弟结点中的关键字
u=s->link\[s->num\];
q->link\[1\]=u;//复制左兄弟结点中的指针
if (u!=NULL)
u->prt=q;//改变指向父结点的指针
p->key\[j-1\]=q->key\[0\]; //置父结点中的路标值
s->link\[s->num\]=NULL; //置左兄弟结点最后一个指针为空 
s->num=s->num-1; //左兄弟结点s的关键字个数减1
q->num=q->num+1; //结点q的关键字个数增1
}
else //需要合并
{ if (j==p->num)//结点q在父结点p中的最后指针位置
{ q=p->link\[j-1\];//要合并的结点之一
s=p->link\[j\];//要合并的结点之二
j=j-1;
}
elses=p->link\[j+1\]; //要合并的结点之二
t=q->num;//记录结点q中关键字个数
for (k=1; k<=s->num; k++) //邻近两个结点合并
{ q->key\[t+k-1\]=s->key\[k-1\];
q->link\[t+k\]=s->link\[k\];
u=s->link\[k\];
if (u!=NULL)
u->prt=q; //改变指向父结点的指针
}
q->num=t+(s->num);//结点q中的关键字个数
q->link\[0\]=s->link\[0\];//顺序链中结点q的指针
delete s; //释放结点s
for (k=j+1; k<=p->num-1; k++)
{ p->key\[k-1\]=p->key\[k\];//父结点中关键字左移 
p->link\[k\]=p->link\[k+1\];//父结点中指针左移
}
p->link\[p->num\]=NULL; //父结点中最后一个指针为空
p->num=p->num-1;//父结点中关键字个数减1
s=q; q=p; 
}
}
if ((q==BTH)&&(q->num==1))//合并到了B+树的根结点，且只有一个关键字
{ delete BTH; BTH=s; BTH->prt=NULL;
if (s->num==0)
{ BTH=NULL; SH=NULL; delete s; }
}
return;
}


//按值大小输出B+树
template <class T>
void MB2<T>∷MB2_prt()
{ mb2node<T>*p;
int k;
p=SH;//从顺序链第一个结点开始
while (p!=NULL) //结点不空
{ for (k=0; k<p->num; k++) //输出该结点中的所有关键字值
cout <<p->key\[k\] <<endl;
p=p->link\[0\];//取顺序链中下一个结点
}
return;
}


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


//文件名Linear_hash.h
#include <iostream>
using namespace std;
//线性hash表结点类型
template <class T>
struct Hnode
{ int flag; //标志表项的空与非空
Tkey; //关键字
};
template <class T>//模板声明，数据元素虚拟类型为T
classLinear_hash //线性Hash表类
{ private://数据成员
int NN; //线性Hash表长度
Hnode<T> *LH; //线性Hash表存储空间首地址
public: //成员函数
Linear_hash(){ NN=0; return;}
Linear_hash(int);//建立线性Hash表存储空间
void prt_L_hash();//顺序输出线性Hash表中的元素
int flag_L_hash();//检测线性Hash表中空项个数
void ins_L_hash(int (*f)(T), T); //在线性Hash表中填入新元素
int sch_L_hash(int (*f)(T), T); //在线性Hash表中查找元素
};//建立线性Hash表存储空间
template <class T>
Linear_hash<T>∷Linear_hash(int m)
{ int k;
NN=m;//存储空间容量
LH=new Hnode<T>\[NN\]; //动态申请线性Hash表存储空间
for (k=0; k<NN; k++)//线性Hash表各项均为空
LH\[k\].flag=0;
return;
}

//顺序输出线性Hash表中的元素
template <class T>
void Linear_hash<T>∷prt_L_hash()
{ int k;
for (k=0; k<NN; k++)
if (LH\[k\].flag==0)//该项为空
cout <<"<NULL>" <<" ";
else//该项不空
cout <<"<" <<LH\[k\].key <<">";
cout <<endl;
return;
}

//检测线性Hash表中空项个数
template <class T>
int Linear_hash<T>∷flag_L_hash()
{ int k, count=0;
for (k=0; k<NN; k++)
if (LH\[k\].flag==0) count=count+1;
return(count);
}

//在线性Hash表中填入新元素
template <class T>
void Linear_hash<T>∷ins_L_hash(int (*f)(T), T x)
{ int k;
if (flag_L_hash()==0)//线性Hash表中已没有空项
{ cout <<"线性Hash表已满!" <<endl; return; }
k=(*f)(x);//计算Hash码
while (LH\[k-1\].flag) //该项不空
{ k=k+1;//下一项
if (k==NN+1) k=1;
}
LH\[k-1\].key=x; LH\[k-1\].flag=1;//填入并置标志
return;
}

//在线性Hash表中查找元素
template <class T>
int Linear_hash<T>∷sch_L_hash(int (*f)(T), T x)
{ int k;
k=(*f)(x);//计算hash码
while ((LH\[k-1\].flag)&&(LH\[k-1\].key!=x))
{ k=k+1;
if (k==NN+1) k=1;
}
if ((LH\[k-1\].flag)&&(LH\[k-1\].key==x))//找到返回
return(k);
return(0);//表中没有这个关键字，返回
}


//文件名L8_2.cpp
#include "Linear_hash.h"
int hashf(int k);
int main()
{ int a\[13\]={9,31,26,19,1,13,2,11,27,16,5,21};
int k;
Linear_hash<int> h(12);//建立容量为12的线性Hash表空间
cout <<"填入的原序列:" <<endl;
for (k=0; k<12; k++)
cout <<a\[k\] <<"";
cout <<endl;
for (k=0; k<12; k++)
h.ins_L_hash(hashf, a\[k\]);
cout <<"依次输出线性Hash表中的关键字:" <<endl;
h.prt_L_hash();
cout <<"查找序列各关键字在线性Hash表中的位置(表项序号):" <<endl;
for (k=0; k<12; k++)
cout <<h.sch_L_hash(hashf, a\[k\]) <<"";
cout <<endl;
return 0;
}
int hashf(int k)//Hash函数
{ return(k/3+1); }


填入的原序列:
93126191132112716521
依次输出线性Hash表中的关键字:
<1><2><5><9><13><11><19><16><26><27><31><21>
查找序列各关键字在线性Hash表中的位置(表项序号):
411971526108312