图.docx
《图.docx》由会员分享，可在线阅读，更多相关《图.docx（25页珍藏版）》请在冰点文库上搜索。
图
实验报告
（2015/2016学年第2学期）
课程名称
数据结构A
实验名称
图的基本运算及飞机换乘次数最少问题
实验时间
2016
年
5
月
23
日
指导单位
计算机科学与技术系
指导教师
骆健
学生姓名
班级学号
学院（系）
管理学院
专业
信息管理与信息系统
图的基本运算
一、问题陈述
1验证教材中关于邻接矩阵和邻接表存储结构实现图的基本运算的算法
2在邻接矩阵存储结构上实现图的深度和广度优先遍历算法
3设计主函数测试上述运算
二、概要设计
编写构造函数MGraph，Insert（）插入函数，Remove（）删除函数，Exist（）查找函数，扩充MGraph类，在扩充类上增加DFS（）和BFS（）函数进行深度遍历和广度遍历。
三、详细设计
四、程序代码
#include
constintINFTY=2147483640;
enumResultCode{Underflow,Duplicate,Failure,Success,NotPresent};
template
classGraph
{
public:
virtualResultCodeInsert（intu,intv,T&w）=0;
virtualResultCodeRemove（intu,intv）=0;
virtualboolExist（intu,intv）const=0;
protected:
intn,e;
};
template
classSeqQueue
{
public:
SeqQueue（intmSize）;
~SeqQueue（）{delete[]q;}
boolIsEmpty（）const{returnfront==rear;}
boolIsFull（）const{return（rear+1）%maxSize==front;}
boolFront（T&x）const;
boolEnQueue（Tx）;
boolDeQueue（）;
voidClear（）{front=rear=0;}
private:
intfront,rear;
intmaxSize;
T*q;
};
template
SeqQueue:
:
SeqQueue（intmSize）
{
maxSize=mSize;
q=newT[maxSize];
front=rear=0;
}
template
boolSeqQueue:
:
Front（T&x）const
{
if（IsEmpty（））
{
returnfalse;
}
x=q[（front+1）%maxSize];
returntrue;
}
template
boolSeqQueue:
:
EnQueue（Tx）//在队尾插入
{
if（IsFull（））
{
cout<<"Full"<returnfalse;
}
q[rear=（rear+1）%maxSize]=x;
returntrue;
}
template
boolSeqQueue:
:
DeQueue（）//删除队头元素
{
if（IsEmpty（））
{
cout<<"Underflow"<returnfalse;
}
front=（front+1）%maxSize;
returntrue;
}
template
classMGraph:
publicGraph//邻接矩阵类
{
public:
MGraph（intmSize,constT&noedg）;
~MGraph（）;
ResultCodeInsert（intu,intv,T&w）;
ResultCodeRemove（intu,intv）;
boolExist（intu,intv）const;
voidDFS（）;
voidBFS（）;
protected:
T**a;
TnoEdge;
voidDFS（intv,bool*visited）;
voidBFS（intv,bool*visited）;
};
template
MGraph:
:
MGraph（intmSize,constT&noedg）//构造函数
{
n=mSize;
e=0;
noEdge=noedg;
a=newT*[n];
for（inti=0;i{
a[i]=newT[n];
for（intj=0;ja[i][j]=noEdge;
a[i][j]=0;
}
}
template
MGraph:
:
~MGraph（）//析构函数
{
for（inti=0;idelete[]a[i];
delete[]a;
}
template
ResultCodeMGraph:
:
Insert（intu,intv,T&w）//插入函数
{
if（u<0||v<0||u>n-1||v>n-1||u==v）
returnFailure;
if（a[u][v]!
=noEdge）
returnDuplicate;
a[u][v]=w;
e++;
returnSuccess;
}
template
ResultCodeMGraph:
:
Remove（intu,intv）//删除函数
{
if（u<0||v<0||u>n-1||v>n-1||u==v）
returnFailure;
if（a[u][v]==noEdge）
returnNotPresent;
a[u][v]=noEdge;
e--;
returnSuccess;
}
template
boolMGraph:
:
Exist（intu,intv）const//判断边是否存在
{
if（u<0||v<0||u>n-1||v>n-1||u==v||a[u][v]==noEdge）
returnfalse;
returntrue;
}
template
voidMGraph:
:
DFS（）//深度遍历
{
bool*visited=newbool[n];
for（inti=0;ivisited[i]=false;
for（i=0;iif（!
visited[i]）
DFS（i,visited）;
delete[]visited;
}
template
voidMGraph:
:
DFS（intv,bool*visited）
{
visited[v]=true;
cout<<""<for（inti=0;iif（a[v][i]!
=noEdge&&a[v][i]!
=0&&!
visited[i]）
DFS（i,visited）;
}
template
voidMGraph:
:
BFS（）//广度遍历
{
bool*visited=newbool[n];
for（inti=0;ivisited[i]=false;
for（i=0;iif（!
visited[i]）
BFS（i,visited）;
delete[]visited;
}
template
voidMGraph:
:
BFS（intv,bool*visited）
{
SeqQueueq（n）;
visited[v]=true;
cout<<""<q.EnQueue（v）;
while（!
q.IsEmpty（））
{
q.Front（v）;
q.DeQueue（）;
for（inti=0;iif（a[v][i]!
=noEdge&&a[v][i]!
=0&&!
visited[i]）
{
visited[i]=true;
cout<<""<q.EnQueue（i）;
}
}
}
template//结点类
classENode
{
public:
ENode（）{nextArc=NULL;}
ENode（intvertex,Tweight,ENode*next）
{
adjVex=vertex;
w=weight;
nextArc=next;
}
intadjVex;
Tw;
ENode*nextArc;
};
template
classLGraph:
publicGraph//邻接表类
{
public:
LGraph（intmSize）;
~LGraph（）;
ResultCodeInsert（intu,intv,T&w）;
ResultCodeRemove（intu,intv）;
boolExist（intu,intv）const;
protected:
ENode**a;
};
template
LGraph:
:
LGraph（intmSize）//构造函数
{
n=mSize;
e=0;
a=newENode*[n];
for（inti=0;ia[i]=NULL;
}
template
LGraph:
:
~LGraph（）
{
ENode*p,*q;
for（inti=0;i{
p=a[i];
q=p;
while（p）
{
p=p->nextArc;
deleteq;
q=p;
}
}
delete[]a;
}
template
boolLGraph:
:
Exist（intu,intv）const//判断边是否存在
{
if（u<0||v<0||u>n-1||v>n-1||u==v）
returnfalse;
ENode*p=a[u];
while（p&&p->adjVex!
=v）
p=p->nextArc;
if（!
p）
returnfalse;
elsereturntrue;
}
template
ResultCodeLGraph:
:
Insert（intu,intv,T&w）//插入
{
if（u<0||v<0||u>n-1||v>n-1||u==v）
returnFailure;
if（Exist（u,v））
returnDuplicate;
ENode*p=newENode（v,w,a[u]）;
a[u]=p;
e++;
returnSuccess;
}
template
ResultCodeLGraph:
:
Remove（intu,intv）//删除
{
if（u<0||v<0||u>n-1||v>n-1||u==v）
returnFailure;
ENode*p=a[u],*q;
q=NULL;
while（p&&p->adjVex!
=v）
{
q=p;
p=p->nextArc;
}
if（!
p）
returnNotPresent;
if（q）
q->nextArc=p->nextArc;
else
a[u]=p->nextArc;
deletep;
e--;
returnSuccess;
}
intmain（）//主函数
{
intn,g,operate;
cout<<"请输入元素的个数：
";
cin>>n;
MGraphA（n,INFTY）;
LGraphB（n）;
cout<<"请输入边的条数:
";
cin>>g;
int*a=newint[g];
int*b=newint[g];
int*w=newint[g];
for（inti=0;i{
cout<<"请输入边及权值：
";
cin>>a[i]>>b[i]>>w[i];
A.Insert（a[i],b[i],w[i]）;
B.Insert（a[i],b[i],w[i]）;
}
cout<<"该图的深度优先遍历为:
"<A.DFS（）;
cout<cout<<"该图的广度优先遍历为：
"<A.BFS（）;
cout<do
{
do
{
cout<<"请输入您要的操作\n1：
查找2：
删除3：
退出\n";
cin>>operate;
}while（operate!
=1&&operate!
=2&&operate!
=2）;
if（operate==1）
{
cout<<"请输入要搜索的边：
";
intc,d;
cin>>c>>d;
if（A.Exist（c,d））
cout<<"邻接矩阵中该边存在！
"<else
cout<<"邻接矩阵中该边不存在！
"<if（B.Exist（c,d））
cout<<"邻接表中该边存在！
"<else
cout<<"邻接表中该边不存在！
"<}
elseif（operate==2）
{
cout<<"请输入要删除的边：
";
inte,f;
cin>>e>>f;
if（A.Remove（e,f）==Success）
cout<<"邻接矩阵中删除该边成功！
"<elseif（A.Remove（e,f）==NotPresent）
cout<<"邻接矩阵中该边不存在！
"<else
cout<<"输入错误！
"<if（B.Remove（e,f）==Success）
cout<<"邻接表中删除该边成功！
"<elseif（B.Remove（e,f）==NotPresent）
cout<<"邻接表中该边不存在！
"<else
cout<<"邻接表中输入错误！
"<cout<<"删除后该图的深度优先遍历为：
"<A.DFS（）;
cout<cout<<"删除后该图的广度优先遍历为：
"<A.BFS（）;
}
elseif（operate==3）
{
cout<return0;
}
}while（0==0）;
}
五、测试与调试
六、实验小结
本次实验很难，运行成功后不仅加深了我对图的理解，更加增长了我的士气，那种敢于解决问题的勇气，以及解决问题的方法。
在进行编程时，不可能一次成功，要勤加注释，方便在修正错误时进行更改。
飞机最少换乘次数问题：
一、问题陈述
设有n个城市，编号为0∽n-1,m条航线的起点和终点由用户输入提供。
寻找一条换乘次数最少的线路方案。
二、概要设计
实用有向图表示城市间的航线，航线权值是零，使用Dijkstra算法实现求换乘最少方案。
三、
详细设计
四、程序代码
#include
#include
constintINF=2147483647;
enumResultCode{Underflow,Duplicate,Failure,Success,NotPresent,OutOfBounds};
template
classGraph//抽象类
{
public:
virtualResultCodeInsert（intu,intv,Tw）=0;
virtualResultCodeRemove（intu,intv）=0;
virtualboolExist（intu,intv）const=0;
protected:
intn,e;
};
template
classMGraph:
publicGraph//邻接矩阵类
{
public:
MGraph（intmSize,constTnoedg）;
~MGraph（）;
ResultCodeInsert（intu,intv,Tw）;
ResultCodeRemove（intu,intv）;
boolExist（intu,intv）const;
intChoose（int*d,bool*s）;
voidDijkstra（intv,T*d,int*path）;
protected:
T**a;
TnoEdge;
};
template
MGraph:
:
MGraph（intmSize,constTnoedg）
{
n=mSize;
e=0;
noEdge=noedg;
a=newT*[n];
for（inti=0;i{
a[i]=newT[n];
for（intj=0;ja[i][j]=noEdge;
a[i][i]=0;
}
}
template
MGraph:
:
~MGraph（）
{
for（inti=0;idelete[]a[i];
delete[]a;
}
template
ResultCodeMGraph:
:
Insert（intu,intv,Tw）
{
if（u<0||v<0||u>n-1||v>n-1||u==v）
returnFailure;
if（a[u][v]!
=noEdge）
returnDuplicate;
a[u][v]=w;
e++;
returnSuccess;
}
template
ResultCodeMGraph:
:
Remove（intu,intv）
{
if（u<0||v<0||u>n-1||v>n-1||u==v）
returnFailure;
if（a[u][v]==noEdge）
returnNotPresent;
a[u][v]=noEdge;
e--;
returnSuccess;
}
template
boolMGraph:
:
Exist（intu,intv）const
{
if（u<0||v<0||u>n-1||v>n-1||u==v||a[u][v]==noEdge）
returnfalse;
returntrue;
}
template
intMGraph:
:
Choose（int*d,bool*s）//求最小d[i]
{
inti,minpos;
Tmin;
min=INF;
minpos=-1;
for（i=0;iif（d[i]<=min&&!
s[i]）
{
min=d[i];
minpos=i;
}
returnminpos;
}
template
voidMGraph:
:
Dijkstra（intv,T*d,int*path）//迪杰斯特拉算法
{
inti,k,w;
if（v<0||v>n-1）
throwOutOfBounds;
bool*s=newbool[n];
for（i=0;i{
s[i]=false;
d[i]=a[v][i];
if（i!
=v&&d[i]path[i]=v;
else
path[i]=-1;
}
s[v]=true;
d[v]=0;
for（i=1;i{
k=Choose（d,s）;
s[k]=true;
for（w=0;wif（!
s[w]&&（d[k]+a[k][w]）{
d[w]=d[k]+a[k][w];
path[w]=k;
}
}
}
intmain（）
{
intn,m;
cout<<"城市总数：
";
cin>>n;
cout<<"航线总数：
";
cin>>m;
MGraphA（n,INF）;
intc,f;
cout<<"请输入每条航线的起点和终点：
"<for（inti=0;i{
cout<<"第"<";
cin>>c>>f;
A.Insert（c,f,1）;
}
chars;
do{
intv,w;
cout<<"请输入你的起点和终点：
";
cin>>v>>w;
while（v<0||w<0||w>n-1||v>n-1）
{
cout<<"输入错误！
请重新输入：
";
cin>>v>>w;
}
int*b=newint[n];
int*d=newint[n];
int*path=newint[n];
A.Dijkstra（v,d,path）;
inte=n-1;
for（intj=0;jb[j]=-2;
if（w!
=v）
{
j=w;
while（path[j]!
=-1）
{
b[e]=path[j];
e--;
j=path[j];
}
if（e==n-1||d[j]==INF）
cout<<"该路间无线路！
"<else
{
cout<<"从"<";
for（intk=0;k{
if（b[k]!
=-2）
cout<
升级会员 