entry是什么意思

数据结构课程设计

—省会城市最短路径求解

一、类关系图

说明：Graph类继承Form类，同时嵌入了CityInf结构体和List类。

Graph类的几个重要函数、类、结构体

privatevoidInit()//初始化函数

privatevoidShowMap_Paint(objectnder,PaintEventArg)//绘制地图

privateboolGetMinDistanceFun(intentry)//采用迪杰斯特拉算法获得最短路径

privatevoidBFS(intStartPoint,int[]visited,stringname)//广度优先遍历函数

privatevoidDFS(intStartPoint,int[]visited,stringname)//深度优先遍历函数

privatevoidPrim()//求解最小生成树Prim算法

privateclassList//广度优先遍历用到的队列类

publicstructCityInf//存放城市信息：城市名称、城市坐标、状态值

二、流程图

主界面

路径增删应用设置

求

最

短

路

径

仅

显

示

最

短

路

径

显

示

或

隐

藏

距

离

数

据

显

示

全

部

城

市

到

起

点

城

市

的

最

短

路

径

随

机

产

生

路

径

最

小

生

成

树

删

除

两

个

城

市

之

间

的

路

增

加

两

个

城

市

之

间

的

路

深

度

优

先

遍

历

最

短

距

离

广

度

优

先

遍

历

寻

径

过

程

选

择

文

件

查

看

邻

接

矩

阵

(在

模

拟

数

据

中

)

模

拟

数

据

城

市

数

据

真

实

地

图

三、主要算法的实现

1．用迪杰斯特拉算法实现省会城市间最短路径的求解

privateboolGetMinDistanceFun(intentry)

{

intinputnodenum=m;

int[]Mark=newint[inputnodenum];//标志位数组标记数据在哪个集合

intmindis=0,nextnode=0;//最短路径，下一个城市结点

inti,j;

//第一轮距离数组记录从起始点到其他所有点的边权值

for(i=0;i

{

Distance[i]=GetCityWeight(entry,i);

//所有标志位清零

Mark[i]=0;

//如果起始结点可以抵达某个结点

if(i!=entry&&Distance[i]

{

RoutePath[i]=entry;//则把该结点首先放入路径数组

}

el

{

RoutePath[i]=-1;//表示该路径不通

}

}

//初始状态下集合存放找到最短路径顶点集合的中只包含源点entry所以把它在Mark

中标记出来

Mark[entry]=1;

//在还没有找到最短路径的结点集合中选取最短距离结点nextnode

for(i=1;i

{

//设定每轮的初始最小距离为无穷大

mindis=MaxWeight;

for(j=0;j

{

//保证每次循环mindis是到entry的最小值

if(Mark[j]==0&&Distance[j]

离小于最小距离

{

nextnode=j;

mindis=Distance[j];//记录本次循环的最短路径

}

}

if(mindis==MaxWeight)//不存在最短路径退出

{

returnfal;

}

//把nexinode在集合mark中标记成已在最短路径集合中

Mark[nextnode]=1;

//每加入一个元素都要修改entry到最短路径集合都要再修改entry到剩余顶点的

最短路径长度值

for(j=0;j

{

//找到新的最短路径

if(Mark[j]==0&&GetCityWeight(nextnode,j)

&&Distance[nextnode]+GetCityWeight(nextnode,j)

{

//新的最短路径

Distance[j]=Distance[nextnode]+GetCityWeight(nextnode,j);

//把该点加入路径

RoutePath[j]=nextnode;

}

}

}

returntrue;

}

算法实现全国公路网最小生成树的求解

privatevoidPrim()

{

inti=0,j=0,k=0;

//权值数组保存权值的数组

int[]WeightArrays=newint[m];

//顶点数组保存相应各个顶点的数组

int[]NodeArrays=newint[m];

//最小权值初始化时为gh

intmincost=ght;

eEdges=newint[m,m];

for(i=0;i

for(j=0;j

{

if(i!=j)

{

eEdges[i,j]=ght;

}

el

{

eEdges[i,j]=0;

}

}

//辅助数组初始化权值数组赋值

for(i=1;i

{

WeightArrays[i]=[0,i];

NodeArrays[i]=0;

}

//某个顶点加入集合U

WeightArrays[0]=0;

NodeArrays[0]=0;

//判断最小的权值通过的顶点的循环就此开始

for(i=0;i

{

k=1;

j=1;

mincost=ght;

//选取权值最小的边和相应的顶点

while(j

{

if(WeightArrays[j]

{

mincost=WeightArrays[j];

k=j;

}

j++;

}

//新顶点加入集合U

WeightArrays[k]=0;

eEdges[k,NodeArrays[k]]=[k,NodeArrays[k]];

eEdges[NodeArrays[k],k]=[k,NodeArrays[k]];

//重新计算该顶点到其余顶点的边的权值

for(j=1;j

{

if([k,j]

{

WeightArrays[j]=[k,j];

NodeArrays[j]=k;

}

}

}

t();

ntree=true;

h();

}

四、程序测试结果

求解两个城市最短路径

显示所有城市到“北京”的最短路径

求解全国省会城市的公路网的最小生成树

“增删”功能

“网络地图”功能

五、总结

本次课程设计收获很大，使用了多种算法：迪杰斯特拉算法、Prim

算法。多种数据结：线性表、栈、队列、二维数组。用到了递归程序

设计思想。用到了Windows程序设计中很重要的GID+绘图方法，采

用了巧妙的方法把经纬度转换成坐标，再把省会城市节点绘制到窗体

上，使得运行结果更具说服力（1：17经纬度1度对应17像素点）

首次引入网络地图功能，方便用户查看真实地图，更具有实用性。

这次的课程设计难度很大，做起来很不轻松，几个算法也是比较

巧妙的，代码写了1800左右，功能还是不完善，很多的代码都是为

绘图服务的。写Windows程序不同于命令提示符下的程序设计，

Windows程序靠事件驱动，用户在Windows系统下做出任何操作都是

会产生事件的，比如点击一个按钮，甚至仅仅移动一下鼠标。这就意

味着，在图形界面上，如果是GDI绘图的情况下就得考虑用户的各种

操作对数据的影响，因为我们不知道用户会选择哪个按钮，然后又会

按哪个按钮，所以要考虑大量的情况。

这次课设让我对解决程序设计中的困难有更大的信心，程序设计

的能力有了很大的提高，对数据结构的知识掌握的更加透彻，我认为

这得益于全部程序自己编写，而不是在网上下载一个程序修改一下，

不然就失去了的课设的意义，也就学不到什么东西，没有什么进步。

想着自己一步步从在窗口上画出一个圆，一条线，到做出这么一

个程序，感觉还是很高兴的，今后还是要多编程，多思考去提升编程

能力，多去实现一些算法。MFC，C++，C#……都是工具，随着科技

的发展都将会过时，唯有算法才是程序的灵魂。