2022年数据结构课程设计-全国交通咨询模拟系统程序设计源代码.docx
精选学习资料 - - - - - - - - - 数据结构课程设计-全国交通询问模拟系统程序设计 源代码一、程序界面A关于程序1. 该程序以 C 语言为开发工具,运行该程序前请确保你地机器上已安装tc 或 turboc ,否就系统会提示：BGI Error: Graphics not initialized use 'initgraph'> 而无法使用该程序 .遇到此情形请安装 tc ,建议将其安装到 C:目录下 ,以确保程序运行万无一失 . 2. 该软件完全支持鼠标 ,请放心使用 . 3. 该程序能将您输入地城市转换为象素坐标 ,显示在屏幕上 ,操作直观便利 ,挑选城市时 ,用时标一点该城市即可,省去了输入地麻烦 .假如您挑选地两个城市间有路径地话 ,程序除了给您信息输出外 ,仍会在地图上将此路径以不同颜色画出 ,更加直观 . 4. 该程序附带三个数据文件 num.txt,vex.txt,len.txt - 此文件由系统默认 >以供用户调试 ,用户仍可自己创建文件,以备试验查询使用 . B. 程序地使用用户打开程序 ,会看到命令行 : FILE CHANGE SHORTWAY MAP HELP ABOUT QUIT CLRSCR 用户将鼠标放于某命令上会看到屏幕最下面有一行字在闪动,这是对命令地说明,如当鼠标访于FILE 上时其下说明 "press this button to open/creat a file" , 当鼠标闲暇时在下面显示: "Please Enter Your Choice With Mouse Or Keyboard" , 提示用户进行命令挑选从而进行某一操作2.用户运行程序时请先打开 FILE 菜单 ,该菜单有 4 个命令选项 : 信息提示 1. 调用已存信息库文件 由用户供应 > 2. 创建新地信息库文件3. 调用演示信息库文件4. 退出程序 请输入你地挑选 1/2/3/4> .单机鼠标就会将某一功能打开名师归纳总结 此时程序等待用户输入挑选.输入正确后程序会自动打开地图由用户进行下一步操作. 第 1 页,共 7 页- - - - - - -精选学习资料 - - - - - - - - - 3. 对于其他命令 ,用户可由显示于屏幕下面地提示进行相关操作 . 二程序内部设计及数据结构A. 数据地存放格式1火车信息数据结构定义：typedef struct inf int num ； /* 车次 */ int stt1 ；int stt2； /* 动身时间 */ int endt1； int endt2； /*到达时间 */ int waitt ；/* 等待时间 */ int allt ； /* 两站之间总耗时 */ int money ；/*票价 */ inf 2车站信息数据结构定义：typedef struct ArcCell int ff ；/*ff=1 表示两点有信息 */ int adj ；/*路程长度 */ inf two ； /* 火车信息 * / ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM；3图地数据结构定义typedef struct Mgraph char vexsMAX_VERTEX_NUMMAX_VERTEX_NUM； /* 顶点名 */ AdjMatrix arcs ； /* 车站信息 */ 名师归纳总结 - - - - - - -第 2 页,共 7 页精选学习资料 - - - - - - - - - int vexsxMAX_VERTEX_NUM；/* 该顶点地 X 坐标 */ int vexsyMAX_VERTEX_NUM； /* 该顶点地 Y 坐标 */ int vexnum,arcnum ； /* vexnum ：顶点地数目 ,arcnum：路线数目 */ Mgraph ；4基于以上数据结构地数据储备举例：<以下为部分顶点信息）wulumuqi 49 59< 表示城市 wulumuqi 在 640X480 地屏幕中位于坐标 49,59 处,下同）xining 97 155 lanzhou 121 174 <以下为部分路线信息）wulumuqi lanzhou 1 1892 1001 1 0 12 0 10 670 150 <表示从城市wulumuqi 到城市 lanzhou 有信息 1,路线长度为1892,车次为 1001,从城市 wulumuqi 开出时间为 1： 00,到 lanzhou 站时间为 12：00,在 lanzhou 停留 10 分钟 ,总耗时 670 分钟 <总耗时由系统自动运算出） ,车票报价 150 元 .下同）xining lanzhou 1 216 1002 9 0 12 5 5 190 50 xining xian 0 10000 10000 10000 10000 10000 10000 10000 10000 10000 <表示 xining 与 xian 两城市间无直达 <直接相连）路线）B. 求最优路径地算法求最优路径地算法可以说是本程序地核心.本程序使用地是弗洛伊德<floyd ）算法1、弗洛伊德算法地基本思想设求顶点 vi 到 vj 间地最短路径 ,如 vi 到 vj 有弧 ,就弧上地权值是一条路径 ,但未必是最短路径 ,要经过 n-1 次测试 .第一将顶点 v1 加入 ,即看 vi,v1>,v1,vj> 是否有路径 ,且比 vi,vj> 低,如是 ,就用后两段路径代替 ,并称这是vi 到 vj 中间顶点序号不大于 1地最短路径 .再将顶点 v2 加入 ,得到 vi 到 vj 中间顶点序号不大于 2 地最短路径.如此下去 ,直到 vn 加入 ,得到 vi 到 vj 中间顶点序号不大于 2、弗洛伊德 <floyd ）算法清单略述n 地最短路径 ,算法终止 . void ShortestPath_FLOYDMGraph G,PathMatrix &P,DistanceMatrix &D> 名师归纳总结 - - - - - - -第 3 页,共 7 页精选学习资料 - - - - - - - - - for v=0 ；v<G,vexnum ； +v> for w=0 ； w<G,vexnum ；+w> Dvw=G.arcsvw；for u=0 ； u<G,vexnum；+u> Pvw=FALSE；ifDvw<INFINITY>pvwv=TRUE； Pvww=TRUE； for u=0 ； u<G.vexnum； u+> /* 将顶点 u 从 0 到 n-1 逐个加入测试 */ for v=0 ； v<G.vexnum ；v+> /* 求 v 到 w 间地最短路径 */ for w=0 ； w<G.vexnum ；w+> if Dv+Dw<Dvw> /*；从 v 经 u 到 w 地一条路径更短 */ Dvw=Dv+Dwfor i=0 ； i<G,vexnum ；+i> Pvw=Pv|Pw； 在程序运算最短路线,最短时间 ,最少消费时使用地就是这个算法. C. 交通图地绘制问题1将 DOS 默认地字符模式改为图形模式由于 DOS 默认地显示形式为字符模式 ,因此要在 DOS 下画图必需将字符模式改为图形模式 .绘图程序地第一步就是初始化图形硬件 .这里地硬件指地是为显示图形所必备地显示适配器 .用于设置运算机图形方式地函数叫作 initgraph >, 它地原型如下：名师归纳总结 void far initgraphint far *gdriver, int far *gmode, char far *driver_path>；第 4 页,共 7 页initgraph > 地函数原型在graphics.h 头文件中 ,它必需包含在C 图形程序地开头处.该文件包括了全部绘图组成成分地数据结构、常量和函数原型定义. 其中 ,在 initgraph > 地函数原型中头两个参数是整型指针.它们分别存有视频适配器和模式地规律值.第三个参数指明 C 绘图驱动程序所储备地路径.指向驱动程序地路径名可以是全程路径名,如：- - - - - - -精选学习资料 - - - - - - - - - initgraph&driver, &mode, “ c: bgi ” >；假如 BGI 驱动程序就在当前目录下,您也可以这样调用initgraph > ：. initgraph > 以前initgraph&driver, &mode, ；“ ” >这里路径名为空字符串.本程序使用DETECT 宏来自动检测本机器最优地图形驱动方式在程序地末尾使用closegraph > 函数 ,以关闭 BGI 系统并把显示器地视频方式复原到调用地情形 . 本程序绘图部分主要程序：#include <graphics.h> / 包含绘图头文件void mainvoid> / 主函数 int gdriver = DETECT ； / 使用自检地方式int gmode；initgraph&gdriver, &gmode, “ c: bgi ” >； / 初始化图形系统/ 此处为绘图代码进行绘图 ,下面有具体介绍closegraph>； / 关闭图形系统 2本程序显示地交通图绘制方法详述A.读入信息后显示路线地主要程序段： fori=0 ；i<G.vexnum ；i+> forj=0 ；j<G.vexnum ；j+>/* 用此循环将全部城市画出 */ setcolorWHITE> ； circleG.vexsx,G.vexsy,4> ； /* 画出半径为 4 个像素地路线起始城市 A*/ circleG.vexsxj,G.vexsyj,4>； /* 画出半径为 4 个像素地路线终止城市 B,为白色 */ setcolorYELLOW> ；名师归纳总结 - - - - - - -第 5 页,共 7 页精选学习资料 - - - - - - - - - outtextxyG.vexsx+5,G.vexsy-3,G.vexs> ； /* 写出路线起始城市 A 城市名 */ outtextxyG.vexsxj+5,G.vexsyj-3,G.vexsj>；/* 写出路线终止城市 B 城市名 ,黄色 */ ifG.arcsj.ff=1>/* 假如两城市间有信息 */ setcolorWHITE> ； lineG.vexsx,G.vexsy,G.vexsxj,G.vexsyj>； /* 在两城市间画一条线,白色 */ B.求出最优路线后地路线绘制程序段ifDj<INFINITY>/* Dj<INFINITY 表示已找到最优路径*/ printf" 里程 :%d km",Dj> ；k=pathj ；ifk.=-1> printf"n 最短路线 :图中绿色 >"> ； printf"n%s",G.vexs> ；whilek.=j> printf"No.%d, 时间 :%02d:%02d>->%s",G.arcsk.two.num,G.arcsk.two.stt1, G.arcsk.two.stt2,G.vexsk> ； /* 在屏幕底部显示路线 */ setcolorGREEN> ； lineG.vexsx,G.vexsy,G.vexsxk,G.vexsyk>；/* 在路线图中将路线画出,为绿色 */ i=k ；k=pathkj ； printf"No.%d, 时间 :%02d:%02d>->%s",G.arcsj.two.num,G.arcsj.two.stt1, G.arcsj.two.stt2,G.vexsj> ；名师归纳总结 - - - - - - -第 6 页,共 7 页精选学习资料 - - - - - - - - - setcolorGREEN> ；lineG.vexsx,G.vexsy,G.vexsxj,G.vexsyj>； /* 将路线地最终一段画出 */ t=0； return OK ； C将屏幕坐标转化为城市坐标问题本程序利用函数 void put_mouse_positionint *x,int *y> 获得当前鼠标位置 X,Y>, 再将鼠标位置通过查城市信息<城市坐标）地方式转换为具体地城市 .具体函数如下：int whichvexint x,int y>/* 求模法判定顶点函数 whichvexx,y,G>*/ int i,pos,a,b,c,d ； pos=-1；/*pos=-1 表示点取位置置没有城市 */ fori=0 ；i<G.vexnum ；i+> c=G.vexsx-x ； d=G.vexsy-y ；/* 查找城市 */ a=absc>； b=absd>； if.a<=5&&b<=5>> continue； ifa<=5&&b<=5>pos=i； /* 假如点取坐标与该城市真实坐标相差小于5 个像素 ,就认为点取了该城市*/ return pos； 名师归纳总结 - - - - - - -第 7 页,共 7 页
