《数据结构课程设计》
课程题目
Floyd算法求最佳路径
课程编号
j1620102
学生姓名
易玉环
所在专业
信息管理与信息系统
所在班级
信管1133班
任课老师
易学明
实习时间
2015年1月1日—1月11日
一、课程设计目的
通过课程设计，学会运用数据结构知识，针对具体应用，自己设计合理数据结构，确定存储结构，并能设计具体操作算法，选择使用具体语言进行实现。掌握C++较复杂程序的组织和设计过程，调试技巧。学习解决实际问题的能力。
二、实习环境
计算机windows 7，开发软件VC6.0，C++语言环境。
三、课程设计题目
题目0.GDOU是真是一个好地方，校园如一座大花园，美丽而宽广。校园有许多建筑如教学楼、饭堂、宿舍楼、图书馆、体育馆、运动场、商业街、医院等，还有一些著名的风景点。现请根据学校的平面图，找出一些重要的场所，画出学校的平面图（场所可以根据其重要性适当减少），根据实际画出不同点间的路径，并估算每两个场所间的路径长。请设计数据结构并编程，当给出一个出发点和要到达另外一个场所的信息时，请给出最佳路径，并输出路径相关信息。
四、总体要求和说明
使用数据结构相关知识来做。这里，我主要采用Floyd算法相关的知识来求最佳距离，完成本系统。
1、独立完成，设计算法并编写代码，调试通过。
2、写设计说明书。
内容：题目、功能、要求、分析、代码，收获和体会及不足等。
3、以个人独立完成。每一个选择一个题目。选题方式是：自己学号整除5所得的余数是几就做几号题。如学号为12做2号题，学号为5的做0号题。
五、需求分析
从实习题目和要求来看，本次的课程设计其依据的主要相关知识是Floyd算法相关的知识，函数模版等以及一些基础的C++编程语言知识。
六、代码如下：
#include <iostream> #include <string> // 字符串头文件#include<iomanip> //引入输入输出格式头文件 #include<windows.h>using namespace std; const int Maxsize = 100; class MGraph { public: MGraph(char a[],int H[6][6]); void Floyd(); void print(); private: string vertex[Maxsize]; int arc[Maxsize][Maxsize]; int vertexNum,arcNum; int dist[Maxsize][Maxsize]; string path[Maxsize][Maxsize]; }; MGraph::MGraph(char a[],int H[6][6]) { int i,j; vertexNum = 6; arcNum = 6; for(i=0;i<vertexNum;i++) vertex[i]=a[i]; for(i=0;i<vertexNum;i++) //使用邻接矩阵来存储，用数组l初始化,将不到达边初始值为最大值，这里使用10000 for(j=0;j<vertexNum;j++) arc[i][j]=H[i][j]; } void MGraph::Floyd() //使用floyd算法，求两点之间最短路径 { int i,j,k; for(i=0;i<vertexNum;i++) //初始化矩阵dist和path for(j=0;j<vertexNum;j++) { dist[i][j] = arc[i][j]; if(dist[i][j] != 10000) path[i][j]=vertex[i]+vertex[j]; else path[i][j] =" "; } for(k=0;k<vertexNum;k++) //进行n次迭代 for(i=0;i<vertexNum;i++) //判定顶点i和顶点j之间是否经过顶点k for(j=0;j<vertexNum;j++) if(dist[i][k]+dist[k][j]<dist[i][j]) { dist[i][j]=dist[i][k]+dist[k][j]; path[i][j]=path[i][k]+"-"+path[k][j]; } }void MGraph::print() //输出所求两点之间的最短路径(作用域 属于类) { int a,b,i; cout<<"您想了解哪两个点的最佳路径？（注：只能输入所给小写字母 如：a c）"<<endl; string ch1,ch2; cin>>ch1>>ch2; //输入要判定是的顶点，请输入顶点字符。 for(i=0;i<vertexNum;i++) if(vertex[i] == ch1) a=i; for(i=0;i<vertexNum;i++) if(vertex[i] == ch2) b=i; cout<<ch1<<"到"<<ch2<<"的最短路径为:"<<path[a][b]<<endl;cout<<"长度为"<<dist[a][b]<<endl; system("pause"); } int main() { char ch[]={‘a’,’b’,’c’,’d’,’e’,’f’}; //顶点信息，用于初始化顶点数组 int H[6][6]={{10000,200,400,10000,10000,10000},{200,10000,100,100,10000,200},{400,100,10000,10000,250,10000},{10000,100,10000,10000,100,150},{10000,10000,250,100,10000,300},{10000,200,10000,150,300,10000}}; //路径长度，用于初始化arc数组 cout <<"┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓"<<endl;cout <<"┃ →→→→niki ><(((:> 欢迎使用 <:)))>< niki ←←←← ┃"<<endl;cout <<"┃ 参考：易老师博客以及书本相关知识 ┃"<<endl;cout <<"┃ ┃"<<endl;cout <<"┃◇◇◇◇◇ Flord 算法求校园两点的最佳路径 ◇◇◇◇◇┃"<<endl;cout <<"┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛"<<endl;Sleep(3000); cout <<"┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓"<<endl;cout <<"┃ a—校门口┃ b—主教学楼┃ c—体育馆 ┃d—钟海楼 ┃e—科技楼 ┃f—医 院 ┃"<<endl; cout <<"┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛"<<endl; MGraph m(ch,H); m.Floyd(); m.print(); return 0; }
七、收获和体会及不足：
要做一个积极勇敢乐观的追梦人，永远不说消极的话，
