数据结构课程设计图的实现.docx
- 文档编号:2837214
- 上传时间:2023-05-04
- 格式:DOCX
- 页数:25
- 大小:21.78KB
数据结构课程设计图的实现.docx
《数据结构课程设计图的实现.docx》由会员分享,可在线阅读,更多相关《数据结构课程设计图的实现.docx(25页珍藏版)》请在冰点文库上搜索。
数据结构课程设计图的实现
数据结构课程设计
图的基本操作与实现
#include
usingnamespacestd;
typedefcharVertexType;
#include"Graph.h"
#include"UDGraph.h"
#include"UNGraph.h"
#include"DGraph.h"
#include"DNGraph.h"
voidShowMainMenu()
{
cout<<"\n";
cout<<" ***************图的基本操作及应用******************\n";
cout<<" * 1无向图的基本操作及应用 *\n";
cout<<" * 2无向网的基本操作及应用 *\n";
cout<<" * 3有向图的基本操作及应用 *\n";
cout<<" * 4有向网的基本操作及应用 *\n";
cout<<" * 5退出 *\n";
cout<<" ***************************************************\n";
}
voidUDG()
{
MGraphMG;
ALGraphALG;
intn;
do
{
cout<<"\n";
cout<<" ***************无向图的基本操作及应用***************\n";
cout<<" * 1创建无向图的邻接矩阵 *\n";
cout<<" * 2创建无向图的邻接表 *\n";
cout<<" * 3无向图的深度优先遍历 *\n";
cout<<" * 4无向图的广度优先遍历 *\n";
cout<<" * 5退出 *\n";
cout<<" *************************************************\n";
cin>>n;
switch(n){
case1:
CreatUDG_M(MG);
break;
case2:
CreatUDG_ALG(ALG);
dispgraph(ALG);
break;
case3:
CreatUDG_ALG(ALG);
dfstraverse(ALG);
break;
case4:
CreatUDG_M(MG);
BFSTraver(MG);
break;
default:
if(n!
=5)
cout<<"错误,重新输入\n";
}
}while(n!
=5);
}
voidUDN()
{
MGraphMG;
ALGraphALG;
intn;
do{
cout<<"\n";
cout<<" ***************无向网的基本操作及应用***************\n";
cout<<" * 1创建无向网的邻接矩阵 *\n";
cout<<" * 2创建无向网的邻接表 *\n";
cout<<" * 3prim算法求最小生成树 *\n";
cout<<" * 4kraskal算法求最小生成树 *\n";
cout<<" * 5退出 *\n";
cout<<" ****************************************************\n";
cin>>n;
switch(n){
case1:
CreateUDN_M(MG);
break;
case2:
CreateUDN(ALG);
dispUDN(&ALG);
break;
case3:
CreateUDN_M(MG);
prim(MG);
break;
case4:
CreateUDN_M(MG);
Kruskal(MG);
break;
default:
if(n!
=5)
cout<<"错误,重新输入\n";
}
}while(n!
=5);
}
voidDG()
{
MGraphMG;
ALGraphALG;
intn;
do
{
cout<<"\n";
cout<<" ***************有向图的基本操作及应用***************\n";
cout<<" * 1创建有向图的邻接矩阵 *\n";
cout<<" * 2创建有向图的邻接表 *\n";
cout<<" * 3拓扑排序 *\n";
cout<<" * 4退出 *\n";
cout<<" ****************************************************\n";
cin>>n;
switch(n){
case1:
CreatDG_M(MG);
break;
case2:
CreatDG_ALG(ALG);
dispgraph(ALG);
break;
case3:
CreatDG_ALG(ALG);
TopologicalSort(ALG);
break;
default:
if(n!
=4)
cout<<"错误,重新输入\n";
}
}while(n!
=4);
}
voidDN()
{
MGraphMG;
ALGraphALG;
intn;
PathMatrixp1;
ShortPathTabled1;
dist2d;
path2p;
do{
cout<<"\n";
cout<<" ***************有向网的基本操作及应用***************\n";
cout<<" * 1创建有向网的邻接矩阵 *\n";
cout<<" * 2创建有向网的邻接表 *\n";
cout<<" * 3关键路径 *\n";
cout<<" * 4单源顶点最短路径问题 *\n";
cout<<" * 5每对顶点最短路径问题 *\n";
cout<<" * 6退出 *\n";
cout<<" ****************************************************\n";
cin>>n;
switch(n){
case1:
CreateDNG_M(MG);
break;
case2:
CreateDN(ALG);
dispDN(&ALG);
break;
case3:
CreateDN(ALG);
CriticalPath(ALG);
break;
case4:
CreateDNG_M(MG);
ShortestPath(MG,1,p1,d1);
break;
case5:
CreateDNG_M(MG);
Floyd(MG,p,d);
break;
default:
if(n!
=6)
cout<<"错误,重新输入\n";
}
}while(n!
=6);
}
voidmain()
{
intn;
do{
ShowMainMenu();
cin>>n;
switch(n){
case1:
UDG();
break;
case2:
UDN();
break;
case3:
DG();
break;
case4:
DN();
break;
default:
if(n!
=5)
cout<<"错误,重新输入\n";
}
}while(n!
=5);
}
//Graph.h(图的定义)
#defineMAXVEX30
#defineMAXCOST1000
typedefintInfoType;
typedefstruct{
VertexTypevexs[MAXVEX];
intarcs[MAXVEX][MAXVEX];
intvexnum,arcnum;
}MGraph;
typedefstructarcnode{
intadjvex;//邻接点序号
intw;//边或狐上的权
InfoType*info;
structarcnode*next;
}ArcNode;
typedefstructvnode{
VertexTypedata; //顶点信息
intindegree;
ArcNode*firstarc; //指向下一个边结点
}Vnode,AdjList[MAXVEX];
typedefstruct{
AdjListvertices;
intvexnum,arcnum;
}ALGraph;
//UDGraph.h(无向图的基本操作及应用)
voidCreatUDG_M(MGraph&G)
{
inti,j,c;
cout<<"请输入顶点数,边数:
";
cin>>G.vexnum;
cin>>G.arcnum;
cout<<"请输入结点信息,如“123..."< for(i=1;i<=G.vexnum;i++) { cin>>G.vexs[i]; } for(i=1;i<=G.vexnum;i++) for(j=1;j<=G.vexnum;j++) G.arcs[i][j]=0; for(c=1;c<=G.arcnum;c++) {printf("第%d条边=>起点序号,终点序号: ",c); cin>>i>>j; G.arcs[i][j]=1; G.arcs[j][i]=1; } cout<<"创建的邻接矩阵为: "< for(inti=1;i<=G.vexnum;i++) {for(intj=1;j<=G.vexnum;j++) cout< cout< } cout<<"邻接矩阵创建完毕"< } ///////////////////////////////////////////////////////////////////////// voidCreatUDG_ALG(ALGraph&G) { inti,s,d; ArcNode*p,*q; cout<<"请输入顶点数,边数: "; cin>>G.vexnum; cin>>G.arcnum; cout<<"请输入结点信息,如“123..."< for(i=1;i<=G.vexnum;i++) { cin>>G.vertices[i].data; G.vertices[i].firstarc=NULL; } for(i=1;i<=G.arcnum;i++) { printf("第%d条边=>起点序号,终点序号: ",i); cin>>s>>d; p=(ArcNode*)malloc(sizeof(ArcNode)); q=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=d; q->adjvex=s; p->next=G.vertices[s].firstarc; //p插入顶点s的邻接表中 G.vertices[s].firstarc=p; q->next=G.vertices[d].firstarc; //q插入顶点d的邻接表中 G.vertices[d].firstarc=q; } } voiddispgraph(ALGraphG) { inti; ArcNode*p; printf("图的邻接表表示如下: \n"); for(i=1;i<=G.vexnum;i++) { printf(" [%d,%c]=>",i,G.vertices[i].data); p=G.vertices[i].firstarc; while(p! =NULL) { printf("[%d→]",p->adjvex); p=p->next; } printf("∧\n"); } } //////////////////////////////////////////////////////////////////////// intvisit[20]; voiddfs(ALGraphG,intv)//从顶点v出发深度优先搜索 {visit[v]=1; cout< ArcNode*p; p=G.vertices[v].firstarc; while(p){ if(visit[p->adjvex]! =1) dfs(G,p->adjvex); p=p->next; }//while } voiddfstraverse(ALGraphG)//对一个图进行深度优先搜索 { intv; for(v=1;v<=G.vexnum;v++) if(! visit[v]) dfs(G,1); } /////////////////////////////////////////////////////////////////////// #include"CirQueue.h" intFirstAdjVex(MGraphG,intvex) { intw,i; for(i=1;i<=G.vexnum;i++) { if(G.arcs[vex][i]==1&&visit[i]==0) {w=i;break; } elsew=0; } returnw; } //获取下一个未被访问的邻接节点 intNextAdjVex(MGraphG,intvex,intw) { inti; for(i=w;i<=G.vexnum;i++)//从w开始 { if(G.arcs[vex][i]==1&&visit[i]==0) {w=i; break; } elsew=0; } returnw; } voidBFSTraver(MGraphG) { Queueq; InitQueue(&q); inti,w,u; for(i=1;i<=G.vexnum;i++) visit[i]=0; for(i=1;i<=G.vexnum;i++)//确保所有的节点被访问到的一个循环 { if(visit[i]==0) { visit[i]=1; cout< EnQueue(&q,i); while(! QueueEmpty(&q))//当队列非空时一直做 { DeQueue(&q,u);//取出队列头元素并置为u w=FirstAdjVex(G,u); while(w>0) { if(visit[w]==0) { visit[w]=1; cout< EnQueue(&q,w); w=NextAdjVex(G,u,w); } } } } } } //UNGraph.h(无向网的基本操作及应用) voidCreateUDN_M(MGraph&G) {inti,j,k,n; cout<<"请输入顶点数和边数"< cin>>G.vexnum; cin>>G.arcnum; cout<<"输入顶点"< for(i=1;i<=G.vexnum;i++) cin>>G.vexs[i]; for(i=1;i<=G.vexnum;i++) for(j=1;j<=G.vexnum;j++) G.arcs[i][j]=999; cout<<"输入边的起点到终点的序号及权值"< for(k=1;k<=G.arcnum;k++) { cin>>i>>j>>n; G.arcs[i][j]=n; G.arcs[j][i]=G.arcs[i][j]; } cout<<"创建的邻接矩阵为: "< for(inti=1;i<=G.vexnum;i++) {for(intj=1;j<=G.vexnum;j++) cout< cout< } cout<<"邻接矩阵创建完毕"< } //建立无向网的邻接矩阵存储结构 /////////////////////////////////////////////////////// voidCreateUDN(ALGraph&G) //邻接表建立无向网 { int i,s,d,w1; ArcNode*p,*q; cout<<"输入节点数和边数"< cin>>G.vexnum>>G.arcnum; cout<<"输入顶点,如“123...”"< for(i=1;i<=G.vexnum;i++) //输入顶点 { cin>>G.vertices[i].data; //输入顶点 G.vertices[i].firstarc=NULL; //首先初始化为NULL } cout<<"输入边的起点到终点的序号及权值"< for(i=1;i<=G.arcnum;i++) { cin>>s>>d>>w1; //输入一条边依附的起点序号和终点序号 p=(ArcNode*)malloc(sizeof(ArcNode)); q=(ArcNode*)malloc(sizeof(ArcNode)); p->info=(InfoType*)malloc(sizeof(InfoType)); q->info=(InfoType*)malloc(sizeof(InfoType)); p->adjvex=d; //保存该弧所指向的顶点位置 q->adjvex=s; //保存该弧所指向的顶点位置 *(p->info)=w1; //保存权值到一个结点里 *(q->info)=w1; //保存权值到一个结点里 p->next=G.vertices[s].firstarc; G.vertices[s].firstarc=p; q->next=G.vertices[d].firstarc; G.vertices[d].firstarc=q; } } voiddispUDN(ALGraph*G) /*打印无向网每个结点的单链表*/ { inti,j; cout<<"[起点权值终点]"< for(i=1;i<=G->vexnum;i++) { while(G->vertices[i].firstarc->next) { cout<<"["< j=G->vertices[i].firstarc->adjvex; cout<<*(G->vertices[i].firstarc->info)<<""< G->vertices[i].firstarc=G->vertices[i].firstarc->next; } cout<<"["< j=G->vertic
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课程 设计图 实现