代码2.txt

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

g.bfs_Link_GP();//横向优先搜索法遍历图g
return 0;
}


6 35 8 20 4 55 3 30 -1 -1
7 35 4 45 3 10 -1 -1
2 10 1 30 8 25 6 35 5 30 -1 -1
2 45 1 55 7 55 5 10 -1 -1
4 10 3 30 7 50 6 15 -1 -1
5 15 3 35 8 20 1 35 -1 -1
5 50 4 55 8 15 2 35 -1 -1
1 20 3 25 6 20 7 15 -1 -1图g邻接表:
A--->3,30--->4,55--->8,20--->6,35
B--->3,10--->4,45--->7,35
C--->5,30--->6,35--->8,25--->1,30--->2,10
D--->5,10--->7,55--->1,55--->2,45
E--->6,15--->7,50--->3,30--->4,10
F--->1,35--->8,20--->3,35--->5,15
G--->2,35--->8,15--->4,55--->5,50
H--->7,15--->6,20--->3,25--->1,20
纵向优先搜索法遍历图g:
A C E F H G B D
横向优先搜索法遍历图g:
A C D H F E B G


//求指定结点到其余各结点的最短距离
template <class T1, class T2>
void Link_GP<T1,T2>∷short_Link_GP(int m)
{ int *mark,k,j,h;
T1 *e;
node<T1>*p;
sq_Queue<int> q(nn);//建立循环队列空间并初始化
e=new T1\[nn\];//申请距离数组空间
mark=new int\[nn\];//申请标志数组空间
for (k=0; k<nn; k++) //标志数组初始化
mark\[k\]=0;
for (k=0; k<nn; k++)//距离数组初始化
e\[k\]=-1;
q.ins_sq_Queue(m);//起始结点入队
mark\[m-1\]=1; //置起始结点入队标志
e\[m-1\]=0; //到起始结点的距离为0
while (q.flag_sq_Queue())//队列非空
{ k=q.del_sq_Queue();//从队列取出一个结点编号k
p=(gp+k-1)->link;//结点后件的单链表头指针
while(p!=NULL)//还有后件
{ j=p->num;//该后件结点编号
h=e\[k-1\]+p->val; //计算该后件结点到起始结点的距离
if ((e\[j-1\]==-1)||(e\[j-1\]>h)) //如果距离更小
{ e\[j-1\]=h; //记录该更小的距离
if (mark\[j-1\]==0)//如果该后件结点未入队过，则入队
{ mark\[j-1\]=1;
q.ins_sq_Queue(j);
}
}
p=p->next; //单链表中下一个后件结点
}
}
cout <<"K " <<"PATH" <<endl;
for (k=0; k<nn; k++) //输出指定结点到其余各结点的最短距离
cout <<k+1 <<" " <<e\[k\] <<endl;
delete mark; delete e;
return;
}


//定义最短距离与路径顺序存储空间结点类型
template <class T1>
structpathnode
{ T1path; //最短距离
node<T1>*elink; //路径单链表指针
};


//求指定结点到其余各结点的最短距离与路径
//定义最短距离与路径顺序存储空间结点类型
template <class T1>
structpathnode
{ T1path; //最短距离
node<T1>*elink; //路径单链表指针
};
template <class T1, class T2>
void Link_GP<T1,T2>∷short_path_Link_GP(int m)
{ int *mark,k,j,h;
pathnode<T1>*e;
node<T1>*p,*pp;
sq_Queue<int> q(nn); //建立循环队列空间并初始化
e=new pathnode<T1>\[nn\];//申请最短距离与路径顺序存储空间
mark=new int\[nn\]; //申请标志数组空间
for (k=0; k<nn; k++)//标志数组初始化
mark\[k\]=0;
for (k=0; k<nn; k++)//最短距离与路径顺序存储空间初始化
 { (e+k)->path=-1; (e+k)->elink=NULL; }
(e+m-1)->path=0;//起始结点的最短距离为0
q.ins_sq_Queue(m);//起始结点入队
mark\[m-1\]=1;//置起始结点入队标志
while (q.flag_sq_Queue())//队列非空
{ k=q.del_sq_Queue(); //从队列中取出一个结点
p=(gp+k-1)->link; //该结点后件单链表头指针
while(p!=NULL)//还有后件结点
{ j=p->num;//当前后件结点编号
h=((e+k-1)->path)+p->val;//当前后件结点到起始结点新距离
if (((e+j-1)->path==-1)||((e+j-1)->path>h))//若新距离更小
{ (e+j-1)->path=h; //置更小的距离
pp=(e+j-1)->elink; //最短距离的最后一个路径
if (pp==NULL) //路径为空则申请一个最短距离路径结点
pp=new node<T1>;
pp->num=j; pp->val=p->val; //置新路径
pp->next=(e+k-1)->elink; (e+j-1)->elink=pp;//连接新路径
if (mark\[j-1\]==0)//当前后件结点未入队过
{ mark\[j-1\]=1; //置当前后件结点入队标志
q.ins_sq_Queue(j);//当前后件结点入队
}
}
p=p->next; //取下一个后件结点
}
}
cout <<"K" <<"PATH" <<"ELINK" <<endl;
for (k=0; k<nn; k++) //依次输出各结点到起始结点的最短距离与路径
{ cout <<k+1 <<" " <<(e+k)->path <<" ";//输出结点编号与最短距离
p=(e+k)->elink;
while (p!=NULL)//输出路径
{ cout <<"--->";
cout <<p->num <<"," <<p->val;
p=p->next;
}
cout <<endl;
}
delete mark; delete e;
return;
}


//文件名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;
g.bfs_Link_GP();//横向优先搜索法遍历图g
cout <<"第3个结点到其余各结点的最短距离:" <<endl;
g.short_Link_GP(3);
cout <<"第3个结点到其余各结点的最短距离与路径:" <<endl;
g.short_path_Link_GP(3);
return 0;
}


图g邻接表:
A--->3,30--->4,55--->8,20--->6,35
B--->3,10--->4,45--->7,35
C--->5,30--->6,35--->8,25--->1,30--->2,10
D--->5,10--->7,55--->1,55--->2,45
E--->6,15--->7,50--->3,30--->4,10
F--->1,35--->8,20--->3,35--->5,15
G--->2,35--->8,15--->4,55--->5,50
H--->7,15--->6,20--->3,25--->1,20
纵向优先搜索法遍历图g:
A C E F H G B D
横向优先搜索法遍历图g:
A C D H F E B G
第3个结点到其余各结点的最短距离:
K PATH
1 30
2 10
3 0
4 40
5 30
6 35
7 40
8 25
第3个结点到其余各结点的最短距离与路径:
KPATHELINK
1 30 --->1,30
2 10 --->2,10
3 0
4 40 --->4,10--->5,30
5 30 --->5,30
6 35 --->6,35
7 40 --->7,15--->8,25
8 25 --->8,25


//文件名SL_List.h
#include <iostream.h>
//using namespace std;
template <class T>//模板声明，数据元素虚拟类型为T
classSL_List //顺序有序表类
{ private://数据成员
int mm; //存储空间容量
int nn; //有序表长度
T *v;//有序表存储空间首地址
public: //成员函数
SL_List(){ mm=0; nn=0; return; }//只定义对象名
SL_List(int);//顺序有序表初始化（指定存储空间容量）
int search_SL_List(T);//顺序有序表查找
int insert_SL_List(T);//顺序有序表插入
int delete_SL_List(T); //顺序有序表删除
void prt_SL_List(); //顺序输出有序表中的元素与有序表长度
friend SL_List operator+(SL_List &, SL_List &);//有序表合并
};
//顺序有序表初始化
template <class T>
SL_List<T>∷SL_List(int m)
{ mm=m;//存储空间容量
v=new T\[mm\]; //动态申请存储空间
nn=0;//有序表长度
return;
}
//顺序有序表查找
template <class T>
int SL_List<T>∷search_SL_List(T x)
{ int i, j, k;
i=1; j=nn;
while (i<=j)
 { k=(i+j)/2;//中间元素下标
 if (v\[k-1\]==x) return(k-1);//找到返回
 if (v\[k-1\]>x) j=k-1;//取前半部
 else i=k+1;//取后半部
 }
return(-1);//找不到返回
}
//顺序有序表的插入
template <class T>
int SL_List<T>∷insert_SL_List(T x)
{ int k;
if (nn==mm)//存储空间已满
{ cout <<"上溢!" <<endl; return(-1); }
k=nn-1;
while (v\[k\]>x) //从最后一个元素到被删元素之间的元素均后移
{ v\[k+1\]=v\[k\]; k=k-1; }
v\[k+1\]=x; //进行插入
nn=nn+1;//长度增1
return(1); //成功插入返回
}
//顺序有序表的删除
template <class T>
int SL_List<T>∷delete_SL_List(T x)
{ int i, k;
k=search_SL_List(x);//查找删除元素的位置
if (k>=0) //表中有这个元素
 { for (i=k; i<nn-1; i++)
 v\[i\]=v\[i+1\]; //被删元素到最后一个元素之间的元素均前移
 nn=nn-1;//长度减1
 }
else //表中没有这个元素
cout <<"没有这个元素!" <<endl;
return(k); //返回删除是否成功标志
}
//顺序输出有序表中的元素与顺序表长度
template <class T>
void SL_List<T>∷prt_SL_List()
{ int i;
cout <<"nn=" <<nn <<endl;//输出长度
for (i=0; i<nn; i++)//依次输出元素
cout <<v\[i\] <<endl;
return;
}
//有序表合并（运算符+重载为友元函数）
template <class T>
SL_List<T> operator+(SL_List<T> &s1, SL_List<T> &s2)
{ intk=0, i=0, j=0;
SL_List<T> s;
s.v=new T\[s1.nn+s2.nn\];//动态申请存储空间
while((i<s1.nn)&&(j<s2.nn))
{ if (s1.v\[i\]<=s2.v\[j\])//复制有序表s1的元素
{ s.v\[k\]=s1.v\[i\]; i=i+1; }
else//复制有序表s2的元素
{ s.v\[k\]=s2.v\[j\]; j=j+1; }
k=k+1;
}
if (i==s1.nn) //复制有序表s2中剩余的元素
for (i=j; i<s2.nn; i++)
{ s.v\[k\]=s2.v\[i\]; k=k+1; }
else //复制有序表s1中剩余的元素
for (j=i; j<s1.nn; j++)
{ s.v\[k\]=s1.v\[j\]; k=k+1; }
s.mm=s1.mm+s2.mm;
s.nn=s1.nn+s2.nn;
return(s);
}


#include <iostream.h>
//using namespace std;


#include <iostream>
using namespace std;


//文件名L7_1.cpp
#include "SL_List.h"
int main()
{ int k;
double a\[5\]={1.5,5.5,2.5,4.5,3.5};
double b\[7\]={1.0,7.5,2.5,4.0,5.0,4.5,6.5};
SL_List<double> s1(20);//建立容量为20长度为5的有序表对象s1
SL_List<double> s2(30);//建立容量为30长度为7的有序表对象s2
for (k=0; k<5; k++)//依次插入有序表s1的元素
 s1.insert_SL_List(a\[k\]);
for (k=0; k<7; k++)//依次插入有序表s2的元素
 s2.insert_SL_List(b\[k\]);
cout <<"输出有序表对象s1:" <<endl;
s1.prt_SL_List();//输出有序表对象s1
cout <<"输出有序表对象s2:" <<endl;
s2.prt_SL_List();//输出有序表对象s2
SL_List<double> s3;//建立合并后的有序表对象s3
s3=s1+s2; //有序表合并
cout <<"输出合并后的有序表对象s3:" <<endl;
s3.prt_SL_List();//输出合并后的有序表对象s3
s3.delete_SL_List(a\[0\]);//在有序表s3中删除1.5
s3.delete_SL_List(b\[0\]);//在有序表s3中删除1.0
s3.delete_SL_List(123.0);//在有序表s3中删除123.0
cout <<"输出删除后的有序表对象s3:" <<endl;
s3.prt_SL_List();//输出合并后的有序表对象s3
return 0;
}


输出有序表对象s1:
nn=5
1.5
2.5
3.5
4.5
5.5
输出有序表对象s2:
nn=7
1
2.5
4
4.5
5
6.5
7.5
输出合并后的有序表对象s3:
nn=12
1
1.5
2.5
2.5
3.5
4
4.5
4.5
5
5.5
6.5
7.5
没有这个元素! //指删除的元素123.0
输出删除后的有序表对象s3:
2.5
2.5
3.5
4
4.5
4.5
5
5.5
6.5
7.5


template <class T>
structindnode
{ Tkey；//数据域，存放子表中的最大值，其类型与线性表中元素的数据类型相同
intk； //指针域，指示子表中第一个元素在线性表中的序号
}；


//定义二叉排序树结点类型
template <class T>
struct BSnode
{ T d;//数据域
BSnode *lchild; //左指针域
BSnode *rchild; //右指针域
};


//文件名BS_Tree.h
#include <iostream>
using namespace std;
//定义二叉链表结点类型
template <class T>
struct BSnode
{ T d;//数据域
BSnode *lchild; //左指针域
BSnode *rchild; //右指针域
};
//二叉排序树类
template <class T>//类模板，T为虚拟类型
class BS_Tree 
{ private:
BSnode<T> *BT;//二叉排序树根结点指针
public: //成员函数
BS_Tree() { BT=NULL; return; }//二叉排序树初始化
void insert_BS_Tree(T);//二叉排序树的插入
int delete_BS_Tree(T); //二叉排序树的删除
BSnode<T> *serch_BS_Tree(T);//二叉排序树的查找
void intrav_BS_Tree(); //中序遍历二叉排序树
};


//中序遍历二叉排序树
template <class T>
void BS_Tree<T>∷intrav_BS_Tree()
{ BSnode<T> *p;
p=BT;
intrav(p); //从根结点开始后序遍历
return;
}
template <class T>
static intrav(BSnode<T> *p)
{ if (p!=NULL)
 { intrav(p->lchild);//中序遍历左子树
 cout <<p->d <<endl; //输出根结点值
 intrav(p->rchild);//中序遍历右子树
 }
return 0;
}


//二叉排序树的插入
template <class T>
void BS_Tree<T>∷insert_BS_Tree(T x)
{ BSnode<T> *p, *q;
p=new BSnode<T>;//申请一个新结点
p->d=x;//置新结点的值域
p->lchild=NULL; p->rchild=NULL; //置新结点左右指针均为空
q=BT;//从根结点开始
if (q==NULL)BT=p; //树空，新结点为根结点
else
 { while ((q->lchild!=p)&&(q->rchild!=p)) //未到叶子结点
{ if (x<q->d)//插入到左子树
{ if (q->lchild!=NULL)q=q->lchild;
elseq->lchild=p;
}
else//插入到右子树
{ if (q->rchild!=NULL)q=q->rchild;
elseq->rchild=p;
}
}
}
return;
}