图.docx
- 文档编号:7348543
- 上传时间:2023-05-11
- 格式:DOCX
- 页数:25
- 大小:124.92KB
图.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;j a[i][j]=noEdge; a[i][j]=0; } } template MGraph : ~MGraph()//析构函数 { for(inti=0;i delete[]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;i visited[i]=false; for(i=0;i if(! visited[i]) DFS(i,visited); delete[]visited; } template voidMGraph : DFS(intv,bool*visited) { visited[v]=true; cout<<""< for(inti=0;i if(a[v][i]! =noEdge&&a[v][i]! =0&&! visited[i]) DFS(i,visited); } template voidMGraph : BFS()//广度遍历 { bool*visited=newbool[n]; for(inti=0;i visited[i]=false; for(i=0;i if(! visited[i]) BFS(i,visited); delete[]visited; } template voidMGraph : BFS(intv,bool*visited) { SeqQueue visited[v]=true; cout<<""< q.EnQueue(v); while(! q.IsEmpty()) { q.Front(v); q.DeQueue(); for(inti=0;i if(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 }; template LGraph : LGraph(intmSize)//构造函数 { n=mSize; e=0; a=newENode for(inti=0;i a[i]=NULL; } template LGraph : ~LGraph() { ENode 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 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 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 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; MGraph LGraph 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;j a[i][j]=noEdge; a[i][i]=0; } } template MGraph : ~MGraph() { for(inti=0;i delete[]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;i if(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;w if(! 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; MGraph 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;j b[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<
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- docx