《数据结构》课程设计报告
|
??
题目0：校园最短路径问题
GDOU是真是一个好地方，校园如一座大花园，美丽而宽广。校园有许多建筑如教学楼、饭堂、宿舍楼、图书馆、体育馆、运动场、商业街、医院等，还有一些著名的风景点。现请根据学校的平面图，找出一些重要的场所，画出学校的平面图（场所可以根据其重要性适当减少），根据实际画出不同点间的路径，并估算每两个场所间的路径长。请设计数据结构并编程，当给出一个出发点和要到达另外一个场所的信息时，请给出最佳路径，并输出路径相关信息。
图的最短路径问题是指从指定的某一点v开始，求得从该地点到图中其它各地点的最短路径，并且给出求得的最短路径的长度及途径的地点。除了完成最短路径的求解外，还能对该图进行修改，如顶点以及边的增删、边上权值的修改等。 校园最短路径问题中的数据元素有：
带权无向图模块
typedef struct//图中顶点表示点，存放点名称 void Menu()//输出菜单 void PutOutVex(MGraph *G)//输出每个顶点的信息 void PutOutArc(MGraph *G)//输出每条边的信息 void Dijkstra(MGraph * G)//迪杰斯特拉算法求最短路径 void DeleteVex(MGraph *G)//删除某个顶点 void DeleteArc(MGraph *G)//删除某条边 void InsertArc(MGraph *G)//插入某条边 void main()//主函数
#include <stdio.h>
#include <iostream.h>
#include<stdlib.h>
#include<conio.h>
#include <malloc.h>
#include<string.h>
#define MAX 10000
#define MAXLEN 10
#define ADJTYPE int
typedef struct //图中顶点表示点，存放点名称
{
char name[30];
int num;
}VEXTYPE;
typedef struct
{
VEXTYPE vexs[MAXLEN]; //顶点的信息
ADJTYPE arcs[MAXLEN][MAXLEN]; //邻接矩阵
int vexnum,arcnum ; //顶点数和边数
}MGraph;
MGraph b;
MGraph InitGraph()
{ /*建立无向网的邻接矩阵结构*/
int i,j;
MGraph G;
G.vexnum =10; //存放顶点数
G.arcnum =24; //存放边点数
for(i=0;i<G.vexnum;i++)
G.vexs[i].num=i;
strcpy(G.vexs[0].name," 广东海洋大学正门");
strcpy(G.vexs[1].name," 商业中心");
strcpy(G.vexs[2].name," 主楼");
strcpy(G.vexs[3].name," 图书馆");
strcpy(G.vexs[4].name," 体育馆");
strcpy(G.vexs[5].name," 钟海楼");
strcpy(G.vexs[6].name," 第一饭堂");
strcpy(G.vexs[7].name," 第三饭堂");
strcpy(G.vexs[8].name," 第四饭堂");
strcpy(G.vexs[9].name," 校医院");
for(i=0;i<G.vexnum;i++)
for(j=0;j<G.vexnum;j++)
G.arcs[i][j]=MAX;
G.arcs[0][1]=395;
G.arcs[0][2]=380;
G.arcs[0][3]=504;
G.arcs[0][4]=415;
G.arcs[0][5]=703;
G.arcs[0][6]=436;
G.arcs[0][7]=840;
G.arcs[0][8]=1000;
G.arcs[0][9]=1100;
G.arcs[1][2]=264;
G.arcs[1][3]=170;
G.arcs[1][4]=86;
G.arcs[1][6]=81;
G.arcs[2][3]=230;
G.arcs[2][4]=209;
G.arcs[2][5]=328;
G.arcs[2][6]=310;
G.arcs[3][4]=87;
G.arcs[3][5]=295;
G.arcs[3][6]=146;
G.arcs[4][6]=102;
G.arcs[5][7]=153;
G.arcs[7][8]=393;
G.arcs[7][9]=359;
G.arcs[8][9]=645;
for(i=0;i<G.vexnum;i++)
for(j=0;j<G.vexnum;j++)
G.arcs[j][i]=G.arcs[i][j];
return G;
}
void Menu() //输出菜单
{
cout<<" ********** 欢迎来到广东海洋大学 ********** n";
cout<<" ┏━━━━━━━━━━━━━━━━━━━━┓n";
cout<<" ┃ 0. 输出顶点(地点)的信息 ┃n";
cout<<" ┃ 1. 输出边(路径)的信息 ┃n";
cout<<" ┃ 2. 修改 ┃n";
cout<<" ┃ 3. 求出最短路径 ┃n";
cout<<" ┃ 4. 删除某个顶点(地点) ┃n";
cout<<" ┃ 5. 删除某条边(路径) ┃n";
cout<<" ┃ 6. 需要插入某条边(路径) ┃n";
cout<<" ┃ 7. 退出系统 ┃n";
cout<<" ┗━━━━━━━━━━━━━━━━━━━━┛n";
}
void PutOutVex(MGraph *G) //输出每个顶点的信息
{
int v;
for(v=0;v<G->vexnum;v++)
cout<<G->vexs[v].num<<G->vexs[v].name<<endl;
}
void PutOutArc(MGraph *G) //输出每条边的信息
{
for(int i=0;i<G->vexnum;i++)
for(int j=0;j<G->vexnum;j++)
if(G->arcs[i][j]<MAX)
{cout<<" 从 " <<G->vexs[i].name<<" 到 "<<G->vexs[j].name<<"的距离是 "<<G->arcs[i][j]<<"米"<<endl;
cout<<" ━━━━━━━━━━━━━━━━━━━━━━━━━━"<<endl;
}
}
void Change(MGraph *G) //修改
{ int v0,v1,length;
cout<<"changen";
cin>>v0;
cin>>v1;
cout<<"length:";
cin>>length;
G->arcs[v0][v1]=G->arcs[v1][v0]=length;
}
void Dijkstra(MGraph * G) //迪杰斯特拉算法求最短路径
{
int v,w,i,min,t=0,x,v0,v1;
int final[40],D[40],p[40][40];
cout<<"请输入源顶点:n";
cin>>v0;
if(v0<0||v0>G->vexnum)
{
cout<<"此点编号不存在!请重新输入顶点编号:";
cin>>v0;
}
cout<<"请输入结束顶点:n";
cin>>v1;
if(v1<0||v1>G->vexnum)
{
cout<<"此点编号不存在!请重新输入顶点编号:";
cin>>v1;
}
for(v=0;v<G->vexnum;v++)
{// 初始化final[40],p[40][40],final[v]=1即已经求得v0到v的最短路径，
//p[v][w]=1则是w从v0到v当前求得最短路径上的顶点，D[v]带权长度
final[v]=0;
D[v]=G->arcs[v0][v];
for(w=0;w<G->vexnum;w++)
p[v][w]=0;
if(D[v]<MAX)
{
p[v][v0]=1;p[v][v]=1;
}
}
D[v0]=0;final[v0]=1;
for(i=1;i<G->vexnum;i++)
{
min=MAX;
for(w=0;w<G->vexnum;w++)
if(!final[w])
if(D[w]<min){v=w;min=D[w];}
final[v]=1;
for(w=0;w<G->vexnum;w++)
if(!final[w]&&(min+G->arcs[v][w]<D[w]))
{
D[w]=min+G->arcs[v][w];
for(x=0;x<G->vexnum;x++)
p[w][x]=p[v][x];
p[w][w]=1;
}
}
cout<<" 从 "<<G->vexs[v0].name<<" 到 "<<G->vexs[v1].name<<" 的最短路径长度为："<<D[v1]<<"米"<<endl;
cout<<" 路径为：";
for(int j=0;j<G->vexnum;j++)
{
if(p[v1][j]==1)
cout<<G->vexs[j].name<<endl;
}
}
void DeleteVex(MGraph *G) //删除某个顶点
{
int row,col;
int v0;
cout<<"请输入要删除的顶点";
cin>>v0;
for(int i=v0;i<G->vexnum;i++)
G->vexs[i]=G->vexs[i+1];
G->vexnum--;
for(row=0;row<G->vexnum;row++)
{
for(col=v0;col<G->vexnum;col++)
G->arcs[row][col]=G->arcs[row][col+1];
}
for(col=0;col<G->vexnum;col++)
{
for(row=v0;row<G->vexnum;row++)
G->arcs[col][row]=G->arcs[col][row+1];
}
}
void DeleteArc(MGraph *G) //删除某条边
{
int v0,v1;
cout<<"请输入两顶点:n";
cin>>v0>>v1;
G->arcs[v0][v1]=MAX;
G->arcs[v1][v0]=MAX;
}
void InsertArc(MGraph *G) //插入某条边
{
int v0,l=0;
cout<<"请输入两顶点:n";
cin>>v0>>v1;
cout<<"请输入路径长度:n";
cin>>l;
G->arcs[v0][v1]=l;
G->arcs[v1][v0]=l;
}
void main() //主函数
{ int a;
b=InitGraph();
Menu();
cin>>a;
while(a!=7)
{
switch(a)
{
case 0:PutOutVex(&b);Menu();break;
case 1:PutOutArc(&b);Menu();break;
case 2:Change(&b);Menu();break;
case 3:Dijkstra(&b);Menu();break;
case 4:DeleteVex(&b);Menu();break;
case 5:DeleteArc(&b);Menu();break;
case 6:InsertArc(&b);Menu();break;
case 7:exit(1);break;
default:break;
}
cin>>a;
}
}
输出顶点（地点）信息
输出边（路径）的信息
修改
求出最短路径
删除某个顶点（地点）
删除某条边（路径）
需要插入某条边（路径）
退出系统
课程设计是培养学生综合运用所学知识，发现、提出、分析和解决实际问题，锻炼实践能力的重要环节，是对学生实际工作能力的具体训练和考察过程。通过这次课程设计，使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，将结论用于实践，从而提高自己的实际动手能力和独立思考的能力。在设计的过程中遇到了很多问题，可以说得是困难重重，但这是不可避免的。在这次课程设计的过程中，我发现了自己的不足之处，对以前所学过的知识理解得不够深刻，掌握得不够牢固，知识面太窄。由于编程水平有限，其中迪杰斯特拉算法的C++程序是参考网上的资料，有关校园地图的输出也没有实现。我想在以后的学习中，我要更注重实践这一环节。
??
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |