代码2.txt

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

p=new TTTnode<T>; //申请三叉链表结点
p->d=x; p->lchild=NULL; p->rchild=NULL;
p->lflag=0; p->rflag=0; p->pre=NULL;
BT=p;
creat(p, 1, end);//输入左子结点值
creat(p, 2, end);//输入右子结点值
return;
}
template <class T>
static creat(TTTnode<T> *p, int k, T end)
{ TTTnode<T> *q;
T x;
cin >>x;//输入结点值
if (x!=end) //结点值为非结束符值
 { q=new TTTnode<T>; //申请一个三叉链表结点
q->d=x; q->lchild=NULL; q->rchild=NULL;
q->lflag=0; q->rflag=0;
if (k==1) //链接到左子树
{ p->lchild=q;q->pre=p; }
if (k==2)//链接到右子树
{ p->rchild=q;q->pre=p; }
creat(q, 1, end); //输入左子结点值
creat(q, 2, end); //输入右子结点值
}
return 0;
}

//生成后序线索三叉链表
template <class T>
void pos_threaded_BT<T>∷creat_threaded_BT()
{ TTTnode<T> *p, *q=NULL;
p=BT;
pos_threaded(p, &q);
return;
}
template <class T>
static pos_threaded(TTTnode<T> *p, TTTnode<T> **h)
{ if (p!=NULL)
 { pos_threaded(p->lchild, h);
 pos_threaded(p->rchild, h);
 //若上次访问到的结点的右指针为空
 //则将当前访问到的结点序号填入，并置右标志域为1
 if ((*h!=NULL)&&((*h)->rchild==NULL))
 { (*h)->rchild=p; (*h)->rflag=1; }
 //若当前访问到的结点的左指针为空
 //则将上次访问到的结点序号填入，并置左标志域为1
 if ((*h!=NULL)&&(p->lchild==NULL))
 { p->lchild=(*h); p->lflag=1; }
 *h=p;//记住当前访问到的结点
 }
return 0;
}

//遍历后序线索三叉链表
template <class T>
void pos_threaded_BT<T>∷intrav_threaded_BT()
{ TTTnode<T> *p, *h;
if (BT==NULL) return;//三叉链表为空
h=BT;
while ((h->lchild!=NULL)||((h->rflag==0)&&(h->rchild!=NULL)))
{ if (h->lchild!=NULL) h=h->lchild;
else h=h->rchild;
}//按后序遍历找第一个结点
cout <<h->d <<" "; //输出后序序列中的第一个结点值
while (h->pre!=NULL)//当前结点不是根结点
{ if (h->rflag!=0) h=h->rchild;//按标志值找到了后件
else
{ p=h->pre;//父结点
if ((p->rchild==h)||
(p->lchild==h)&&
((p->rflag!=0)||(p->rchild==NULL)))
h=p;//父结点为后件
else
{ h=p->rchild;
while (((h->lflag==0)&&(h->lchild!=NULL))||
((h->rflag==0)&&(h->rchild!=NULL)))
{ if ((h->lflag==0)&&(h->lchild!=NULL))
 h=h->lchild;
else h=h->rchild;
}//按后序遍历找后件结点
}
}
cout <<h->d <<" ";//输出后序序列中的结点值
}
cout <<endl;
return;
}


//文件名L5_4.cpp
#include "pos_threaded_BT.h"
int main()
{ pos_threaded_BT<int> b;//建立一个二叉树对象b，数据域为整型
cout <<"输入各结点值(-1作为结束符值):" <<endl;
b.creat_Binary_Tree(-1); //从键盘输入二叉树各结点值，以-1作为结束符值
b.creat_threaded_BT();//生成后序线索
cout <<"后序序列:" <<endl;
b.intrav_threaded_BT(); //遍历后序线索二叉树
return 0;
}


输入各结点值(-1为结束符值):
18 20 09 –1 –1 25 47 –1 –1 –1 36 –1 12 06 –1 –1 33 –1 -1
后序序列:
9 47 25 20 6 33 12 36 18


//定义最优二叉树结点类型
template <class T>
structhufnode
{ Twei;//权值
int prt;//指向父结点的指针域（结点元素下标）
int lch;//左指针域（结点元素下标）
int rch;//右指针域（结点元素下标）
};


//文件名hufman_BT.h
#include <iostream>
#include <iomanip>
using namespace std;
//定义最优二叉树结点类型
template <class T>
structhufnode
{ Twei;//权值
int prt;//指向父结点的指针域（结点元素下标）
int lch;//左指针域（结点元素下标）
int rch;//右指针域（结点元素下标）
};
//最优二叉树类
template <class T>//类模板，T为虚拟类型
class hufman_BT
{ private:
int nn;//叶子结点数
hufnode<T> *BT;//最优二叉树顺序存储空间首地址
public: //成员函数
hufman_BT() { BT=NULL; return; }//最优二叉树初始化
void creat_hufm_BT(int, T \[\]);//生成最优二叉树
void prt_hufm_BT(); //输出最优二叉树存储空间状态
};
//生成最优二叉树
template <class T>
void hufman_BT<T>∷creat_hufm_BT(int n, T w\[\])
{ hufnode<T>*p;
intk,i,j,m;
nn=n;
m=2*n-1;
BT=new hufnode<T>\[m\]; //申请最优二叉树存储空间
p=BT;
for (k=0; k<m; k++)//设置初始状态（所有结点指针为空）
 { (p+k)->prt=-1;
(p+k)->lch=-1;
(p+k)->rch=-1;
}
for (k=0; k<n; k++)//前n个结点的权值分别为各叶子结点的权值
(p+k)->wei=w\[k\];
for (k=n; k<m; k++) //构造最优二叉树
 { select(p,k,&i,&j); //在前k-1个结点中选择权值最小的两个根结点i与j
 (p+i)->prt=k; (p+j)->prt=k;//合并构造新的二叉树
 (p+k)->lch=i; (p+k)->rch=j;
 (p+k)->wei=(p+i)->wei+(p+j)->wei;
 }
return;
}
//在前k-1个结点中选择权值最小的两个根结点i与j
template <class T>
static select(hufnode<T> *p, int k, int *i, int *j)
{ T w;
intn;
n=0;
while ((n<k)&&((p+n)->prt!=-1))
n=n+1; //寻找指向父结点指针为空的起始结点
w=(p+n)->wei; *i=n;
while (n<k) //寻找指向父结点指针为空且权值为最小的结点
 { if ((((p+n)->wei)<w)&&((p+n)->prt==-1))
 { *i=n; w=(p+n)->wei; }
 n=n+1;
 }
n=0;
while ((n<k)&&((p+n)->prt!=-1)||(n==(*i)))
n=n+1; //寻找指向父结点指针为空且权值不是最小的起始结点
w=(p+n)->wei; *j=n;
while (n<k)//寻找指向父结点指针为空且权值为次小的结点
 { if (((p+n)->wei<w)&&(n!=(*i))&&((p+n)->prt==-1))
 { *j=n; w=(p+n)->wei; }
 n=n+1;
 }
if ((*i)>(*j)) //对两个结点按序号排序
{ n=(*i); *i=(*j); *j=n; }
return 0;
}

//输出最优二叉树存储空间状态
template <class T>
void hufman_BT<T>∷prt_hufm_BT()
{ hufnode<T> *p;
int k;
p=BT;
cout <<"k" <<setw(7) <<"WEI" <<setw(7) <<"PRT"
<<setw(7) <<"LCH" <<setw(7) <<"RCH" <<endl;
for (k=0; k<2*nn-1; k++)
cout <<k <<setw(7) <<(p+k)->wei <<setw(7) <<(p+k)->prt
<<setw(7) <<(p+k)->lch <<setw(7) <<(p+k)->rch <<endl;
return;
}


//文件名L5_7.cpp
int main()
{ int w\[5\]={16,12,19,16,28};//叶子结点的权值
hufman_BT<int> b;//定义一个最优二叉树对象
b.creat_hufm_BT(5, w); //生成最优二叉树
b.prt_hufm_BT(); //输出最优二叉树存储空间状态
return 0;
}


kWEIPRTLCHRCH
0 165 -1 -1
1 125 -1 -1
2 196 -1 -1
3 166 -1 -1
4 287 -1 -1
5 28701
6 35823
7 56845
8 91 -167


//定义图邻接表中单链表结点类型
template <class T1>
struct node
{ int num; //图中结点编号
T1 val;//求值函数
node *next;//指向链表中下一个结点的指针域
};
//定义图邻接表中顺序存储空间结点类型
template <class T1, class T2>
struct gpnode
{ T2 data; //图中的结点值
node<T1> *link;//指向各单链表第一个结点的指针域
};


//文件名Link_GP.h
#include <iostream>
#include <fstream>
#include "sq_Queue.h"
using namespace std;
//定义图邻接表中单链表结点类型
template <class T1>
struct node
{ int num; //图中结点编号
T1 val;//求值函数
node *next;//指向链表中下一个结点的指针域
};
//定义图邻接表中顺序存储空间结点类型
template <class T1, class T2>
struct gpnode
{ T2 data; //图中的结点值
node<T1> *link;//指向各单链表第一个结点的指针域
};
//定义图邻接表类
template <class T1, class T2>
class Link_GP
{ private:
int nn; //图中结点个数
gpnode<T1,T2> *gp; //图邻接表中顺序存储空间首地址
public: //成员函数
Link_GP() { gp=NULL; return; }//图邻接表初始化
void creat_Link_GP(int, T2 \[\]); //由键盘输入生成图邻接表
void creat_Link_GP(int,T2 \[\],char *);//由文件数据生成图邻接表
void prt_Link_GP(); //输出图邻接表
void dfs_Link_GP(); //纵向优先搜索法遍历图
void bfs_Link_GP(); //横向优先搜索法遍历图
void short_Link_GP(int); //求指定结点到其余各结点的最短距离
void short_path_Link_GP(int);//求指定结点到其余各结点的最短距离与路径
};


2<空格>63<回车或空格>
3<空格>95<回车或空格>
4<空格>84<回车或空格>
-1<空格>-1<回车>（结点A的后件）
1<空格>63<回车或空格>
3<空格>49<回车或空格>
4<空格>44<回车或空格>
5<空格>37<回车或空格>
-1<空格>-1<回车>（结点B的后件）
1<空格>95<回车或空格>
2<空格>49<回车或空格>
-1<空格>-1<回车>（结点C的后件）
1<空格>84<回车或空格>
2<空格>44<回车或空格>
5<空格>35<回车或空格>
-1<空格>-1<回车>（结点D的后件）
2<空格>37<回车或空格>
4<空格>35<回车或空格>
-1<空格>-1<回车>（结点E的后件）


//由键盘输入生成图邻接表
template <class T1, class T2>
void Link_GP<T1,T2>∷creat_Link_GP(int n, T2 d\[\])
{ node<T1>*p;
intk, m;
T1 v;
nn=n;//图中结点个数
gp=new gpnode<T1,T2>\[nn\];//申请图邻接表中顺序存储空间
for (k=0; k<n; k++)//依次对图中的每一个结点建立链接所有后件的
//单链表
 { (gp+k)->data=d\[k\]; //置顺序存储空间的结点值
 (gp+k)->link=NULL; //置顺序存储空间结点的指针域为空
 cout <<"输入图中第" <<k <<"个结点的后件信息:" <<endl;
 cin >>m >>v;//输入后件信息
 while (m>=0) //输入后件信息未结束
{ p=new node<T1>;//申请单链表结点
 p->num=m; p->val=v;//置后件结点编号与求值函数值
 p->next=(gp+k)->link;//新结点指针指向原头结点
 (gp+k)->link=p; //将新结点链接到单链表链头
 cin >>m >>v;//继续输入后件信息
 }
 }
return;
}


//由文件数据生成图邻接表
template <class T1, class T2>
void Link_GP<T1,T2>∷creat_Link_GP(int n, T2 d\[\], char *filename)
{ node<T1>*p;
intk, m;
T1 v;
ifstream infile(filename, ios∷in); //打开文件
nn=n;//图中结点个数
gp=new gpnode<T1,T2>\[nn\];//申请图邻接表中顺序存储空间
for (k=0; k<n; k++)//依次对图中的每一个结点建立链接所有后件的
//单链表
 { (gp+k)->data=d\[k\]; //置顺序存储空间的结点值
 (gp+k)->link=NULL; //置顺序存储空间结点的指针域为空
 infile >>m >>v;//读入后件信息
 while (m>=0) //读入后件信息未结束
{ p=new node<T1>;//申请单链表结点
 p->num=m; p->val=v;//置后件结点编号与求值函数值
 p->next=(gp+k)->link;//新结点指针指向原头结点
 (gp+k)->link=p; //将新结点链接到单链表链头
 infile >>m >>v;//继续读入后件信息
 }
 }
return;
}


图中的结点值--->后件结点编号，求值函数值--->…


//输出图邻接表
template <class T1, class T2>
void Link_GP<T1,T2>∷prt_Link_GP()
{ node<T1> *q;
int k;
for (k=0; k<nn; k++)
{ cout <<(gp+k)->data;//输出图结点值
q=(gp+k)->link;
while (q!=NULL)//依次输出各后件结点的编号与求值函数
{ cout <<"--->";
cout <<q->num <<"," <<q->val; //输出后件结点编号与求值函数
q=q->next;
}
cout <<endl;
}
return;
}


//纵向优先搜索法遍历图
template <class T1, class T2>
void Link_GP<T1,T2>∷dfs_Link_GP()
{ intk, *mark;
mark=new int\[nn\];//申请标志数组空间
for (k=0; k<nn; k++) //标志数组初始化
mark\[k\]=0;
for (k=0; k<nn; k++) //对每个图结点纵向优先搜索
 if (mark\[k\]==0)dfs(gp,k,mark);
cout <<endl;
delete mark;
return;
}
template <class T1, class T2>
static dfs(gpnode<T1,T2> *q, int k, int *mark)
{ node<T1>*p;
cout <<(q+k)->data <<" "; //输出当前图结点值
mark\[k\]=1; //记录当前结点已查访标志
p=(q+k)->link; //当前结点的第一个后件结点
while (p!=NULL)
{ if (mark\[p->num-1\]==0) //该后件结点未查访过
 dfs(q, p->num-1, mark);
p=p->next;//下一个后件结点
}
return 0;
}


//横向优先搜索法遍历图
template <class T1, class T2>
void Link_GP<T1,T2>∷bfs_Link_GP()
{ int *mark, k;
sq_Queue<int> q(nn);//建立循环队列空间并初始化
node<T1>*p;
mark=new int\[nn\]; //申请标志数组空间
for (k=0; k<nn; k++) //标志数组初始化
mark\[k\]=0;
for (k=0; k<nn; k++)//对每个图结点横向优先搜索
{ if (mark\[k\]==0) //当前结点未查访过
{ mark\[k\]=1;//记录当前结点已查访标志
cout <<gp->data <<" ";//输出当前结点值
q.ins_sq_Queue(k); //当前结点编号入队
while (q.flag_sq_Queue())//队列不空
{ k=q.del_sq_Queue(); //从队列中退出一个结点作为当前结点
p=(gp+k)->link; //所有后件结点链表指针
while(p!=NULL)//还有后件
{ k=p->num-1;
if (mark\[k\]==0)//该结点未查访过
{ cout <<(gp+k)->data <<" ";//输出该结点值
mark\[k\]=1; //记录该结点已查访标志
q.ins_sq_Queue(k);//该结点编号入队
}
p=p->next;//下一个后件
}
}
}
}
cout <<endl;
delete mark;
return;
}


void short_Link_GP(int);//求指定结点到其余各结点的最短距离
void short_path_Link_GP(int);//求指定结点到其余各结点的最短距离与路径


//文件名L6_1.cpp
#include "Link_GP.h"
int main()
{ char d\[8\]={'A','B','C','D','E','F','G','H'};
Link_GP<int, char> g;
g.creat_Link_GP(8, d, "f1.txt");//由数据文件生成图g邻接表
cout <<"图g邻接表:" <<endl;
g.prt_Link_GP(); //输出图邻接表
cout <<"纵向优先搜索法遍历图g:" <<endl;
g.dfs_Link_GP();//纵向优先搜索法遍历图g
cout <<"横向优先搜索法遍历图g:" <<endl;