资源描述：
《数据结构课程实验报告实验11》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、题目最短路径问题班级计算机科学与技术三班姓名康小雪学号20090810310完成日期2010-12-25需求分析(1)程序所能达到的功能：木程序可以通过用八从键盘中输入有向网中主要场所的数量及场所之间的票价的矩阵，并根据用户指定的起点和终点，输出从起点到终点的花费。(2)输入的形式和输入值的范围：输入从文件读取，定顶点个数应为小于或等于30的止整数，票价大于0,若两场所之间无直接路径，则票价为・1.(3)输出的形式：程序输出这从起点到终点最少的花费。(4)测试数据：输入：5-110320-1-1-1-15-1-12-1-115-1-1-1-111-1
2、-1-1-1-1(用户)起点0终点4输出18概要设计抽象数据类型为实现各个场所及票价的存储功能，每个场所即代表一个节点。为了实现输出最短路径，应选择川队列的先进先岀来实现，队列定义如下:ADTQueue}数据对象：D={ailai丘ElemSet,i=1,2,…,n,n20}数据关系：Rl={lai-l,ai^D,i=2,-*-,n}约定其中ai端为队列头，an端为队列尾。基本操作/*顺序栈的基本操作*/基本操作：voidinit(disList*PL)//初始化队列voidcnqucuc(disList*PL,disd)〃入队列v
3、oidtop(disList*PL,dis*p)〃取队首元素voiddequeue(disList*PL)//'l!队列intempty(disList*PL)〃判断队列是否为空intshortestpath(intcost[Max][Max],intn,intsrc,intdes)//最小路径}ADTQueue算法的基本思想弗洛伊徳算法，从图的带权邻接矩阵cos(出发，其基本思想是：假设求从顶点Vi到Vj的最短路径。如果从Vi到Vj有弧，则从Vi到vj存在一条长度为arcsliJUl的路径，该路径不一定是最短路径,尚需进行n次试探。首先考虑路径(v
4、i,vO,vj)是否存在(即判别弧(vi,vO)和(vO,vj)是否存在)。如果存在，贝吐匕较(vi,vj)秋vi,vO,vj)的路径长度収长度较短者为从vi到vj中间顶点的序号不大于0的最短路径。加入在路径上再增加一个顶点vl,也就是说，如果(vi,...,vl)和(vl,…,vj)分别是当前找到的中间顶点的序号不大于0的最短路径，那么(vi,....,vl,...,vj)就有可能是从vi到vj的中间顶点的序号不大于1的最短路径。将它和己经得到的从vi到vj中间顶点粗豪不人于0的最短路径相比较，从中选出中间顶点的序号不大于1的故短路径Z后，再增加一
5、个顶点v2,继续进行试探。以此类推。在一般情况下,若(vi,...vk)和(vk,...,vj)分别是从vi到vk和从vk到vj且中间顶点序号不大于k-1的最短路径相比较，其长度较短者便是从vi到vj的中间定点的序号不人于k的最短路径。这样，在经过n次比较后，最后求得的必是从vi到vj的瑕短路径。按此方法，可以同时求得各对顶点间的最短路径。程序的流程程序山三个模块纽成：(1)输入模块：完成场所的数量和各个场所之间的票价的输入，将各个场所之间的票价保存在相应的二维矩阵屮，并完成起点和终点的输入。(2)查找最短路径模块：利川弗洛伊徳算法查找最短路径，并计
6、算最短路径的长度。(3)输出模块：输出最小路径的长度，并显示在屏幕上。详细设计物理数据类型〃节点存储结构typedefstruct{intID;intPathcost;}dis;〃队列typedefstruct{disL[Max];intsize;}disList;算法的具体步骤第一步获取场所数目，以及各场所之间的票价，创建有向图矩阵第二步创建一个空的队列第三步利川弗洛伊德算法找最短路径，并计算最短路径第四步打卬出最短路径的长度voidinit(disList*PL)PL->size=0;voidenqueue(disList*PL,disd)int
7、curr;distemp;curr=PLosize;PL->L[curr]=d;〃上拉while((cuit!=0)&&(PL->L[curr].PathcostL[(curr-1)/2].Pathcost)){temp=PL->L[currJ;PL->L[curr]=PL->L[(curr-l)/2];PL->L[(curr-1)/2]=temp;curr=(curr-1)/2;}PL・>size++;}voidtop(disList*PL,dis*p){if(PL->size!=O)*p=PL->L[0];voiddequeue(dis
8、List*PL){distemp;intcurr=0,j;if(PL->size==0)return;〃头尾
