c++学生成绩管理系统.doc

1、学 号 09710107数据结构课程设计设计说明书医院选址问题起止日期： 2012年 1月 2 日 至 2012 年 1月6日学生姓名杨军刚班级09计算机1班成绩指导教师(签字) 电子与信息工程系2012年 1月6日天津城市建设学院课程设计任务书20112012学年第1学期 电子与信息工程 系 计算机科学与技术 专业 09级 1 班级课程设计名称： 数据结构课程设计 设计题目： 医院选址问题 完成期限：自 2012 年 1 月 2 日至 2012 年 1 月 6 日共 1 周设计依据、要求及主要内容（可另加附页）：一、设计目的熟悉各种数据结构和运算，会使用数据结构的基本操作解决一些实际问题。二

2、、设计要求 （1）重视课程设计环节，用严谨、科学和踏实的工作态度对待课程设计的每一项任务；（2）按照课程设计的题目要求，独立地完成各项任务，严禁抄袭；凡发现抄袭，抄袭者与被抄袭者皆以零分计入本课程设计成绩。凡发现实验报告或源程序雷同，涉及的全部人员皆以零分计入本课程设计成绩；（3）学生在接受设计任务后，首先要按设计任务书的要求编写设计进程表；（4）认真编写课程设计报告。三、设计内容医院选址问题1)问题描述n个村庄之间的交通图可以用有向网图来表示，图中边上的权值表示从村庄i到村庄j的道路长度。现在要从这n个村庄中选择一个村庄新建一所医院，问这所医院应建在哪个村庄，才能使所有的村庄离医院都比较近？

3、2) 基本要求(1) 建立模型，设计存储结构；(2) 设计算法完成问题求解；(3) 分析算法的时间复杂度。3) 设计思想医院选址问题实际是求有向图中心点的问题。首先定义顶点的偏心度。设图G=（V，E），对任一顶点k，称E(k)=maxd(i, k)（iV）为顶点k的偏心度。显然，偏心度最小的顶点即为图G的中心点。如图7(a)所示是一个带权有向图，其各顶点的偏心度如图(b)所示。abcde1253214顶点偏心度a b 6b 8d 5e 7 (a) (b) 图7 带权有向图及各顶点的偏心度医院选址问题的算法用伪代码描述如下：1对加权有向图，调用Floyd算法，求每对顶点间最短路径长度的矩阵；2对

4、最短路径长度矩阵的每列求大值，即得到各顶点的偏心度；3具有最小偏心度的顶点即为所求。目录一、需求分析4二、问题求解5三、总体设计5四、详细设计61.输入函数2.建立邻接矩阵图63.求最短路径74.输出函数7五、调试与测试7六 .关键源程序清单和执行结果8七、参考文献12一、 需求分析输入村庄的个数、名称，输入村庄间路的个数以及每条路的长度（权值）；程序根据权值以及路来求解得出医院的地址。医院的地址要求：每个村庄到医院的路径最长的值要最小。二、问题求解在现实中我会以其中为终点以同样的速度在每个村庄走到终点的时间记录下最长的时间为该点为终点时的一个值。难后比较那个点为终点时所用的时间值是最小的。

5、a b c d ea 1 3 5 7b 2 4 6c 3 2 4d 1 3 7e 6 8 5三、总体设计医院选址输入函数输出函数建立邻接矩阵图求最短路径四、详细设计.输入函数：templateclass Graph public: virtual void Insert(int u,int v,T& w)=0; virtual void Remove(int u,int v)=0; virtual bool Exist(int u,int v)=0; protected: int n,e; ;2.建立邻接矩阵图template class MGraph:public Graph/邻接矩阵存储图

6、 public: MGraph(); MGraph(); void Build_Graph(); void Insert(int u,int v,T& w); void Remove(int u,int v); bool Exist(int u,int v); void Floyd(T*&d,int*&path); int num; protected: T*a; T noEdge;3.求最短路径template void MGraph:Floyd(T*&d,int*&path)/所有顶点之间的最短路径 int i,j,k; d=new T*n;path=new int*n; for(i=0;

7、in;i+) di=new Tn;pathi=new intn; for(j=0;jn;j+) dij=aij; if(i!=j& aijINFTY)pathij=i; else pathij=-1; for(k=0;kn;k+) for(i=0;in;i+) for(j=0;jn;j+) if(dik+dkjaij) dij=dik+dkj; pathij=pathkj; 4.输出函数： for(i=0;i!=n;i+)/输出矩阵 couti+1tt; sumi=0; for(j=0;j!=n;j+) sumi+=dij; coutdijt; coutendl; 五、调试与测试在测试中权值的

8、初始化以及最短路径的计算时出现赋值出错等问题。用if(u0|vn-1|vn-1|u=v|auv=noEdge) return false;来解决此问题！六 .关键源程序清单和执行结果#include using namespace std;int INFTY=9999;templateclass Graph public: virtual void Insert(int u,int v,T& w)=0; virtual void Remove(int u,int v)=0; virtual bool Exist(int u,int v)=0; protected: int n,e; ;temp

9、late class MGraph:public Graph/邻接矩阵存储图 public: MGraph(); MGraph(); void Build_Graph(); void Insert(int u,int v,T& w); void Remove(int u,int v); bool Exist(int u,int v); void Floyd(T*&d,int*&path); int num; protected: T*a; T noEdge;template void MGraph:Build_Graph()/建图 cout请输入顶点的个数：C_num; num=n=C_num

10、;e=0;noEdge=INFTY; a=new T*n; for(int k=0;kn;k+) ak=new T n; for(int j=0;jn;j+)akj=noEdge; akk=0; cout建立村庄编号为1-C_num的图endl; for(int i=0;i!=C_num;i+) for(int j=i+1;j!=C_num;j+) int w; cout请输入村庄i+1与村庄j+1w; Insert(i,j,w); /向图中添加权值为W的边 cout*endl; cout已建立村庄编号为1-C_num的图:endl; cout*endl; cout tt; for(int b

11、=1;b=C_num;b+) coutbt; coutendl;template MGraph:MGraph() Build_Graph();template MGraph:MGraph() for(int i=0;in;i+)deleteai; deletea;template bool MGraph:Exist(int u,int v) if(u0|vn-1|vn-1|u=v|auv=noEdge) return false; return true;template void MGraph:Insert(int u,int v,T &w) auv=w;avu=w;e+;template

12、void MGraph:Remove(int u,int v) auv=noEdge;e-;template void MGraph:Floyd(T*&d,int*&path)/所有顶点之间的最短路径 int i,j,k; d=new T*n;path=new int*n; for(i=0;in;i+) di=new Tn;pathi=new intn; for(j=0;jn;j+) dij=aij; if(i!=j& aijINFTY)pathij=i; else pathij=-1; for(k=0;kn;k+) for(i=0;in;i+) for(j=0;jn;j+) if(dik+d

13、kjaij) dij=dik+dkj; pathij=pathkj; int main() MGraph Hospital; int *d,*path; int i,j,n; n=Hospital.num; Hospital.Floyd(d,path); int *sum=new intn; coutendl; for(i=0;i!=n;i+)/输出矩阵 couti+1tt; sumi=0; for(j=0;j!=n;j+) sumi+=dij; coutdijt; coutendl; cout*endl; int min=0; for(i=0;i!=n;i+) couti+1村庄：sumisumi)/判断最短路径 min=i; cout医院应在编号为min+1的村庄endl; 测试所用数据：u=4 w=5,4,6,3,7,2七、参考文献1王红梅数据结构清华大学出版社2王红梅数据结构学习辅导与实验指导清华大学出版社3.严蔚敏，吴伟民数据结构（C语言版）121