2022年数据结构课程设计 3.pdf

i目录1 实习目的.12 问题描述.13 概要设计.14 详细设计.54.1 创建交通图伪码.54.2 建航班算法伪码.84.3 删除城市结点算法伪码.95 测试分析.12 5.1 操作员管理功能.12 5.2 交通咨询功能.12 6 使用说明.14 7 总结.15 8 参考文献.15 9 附录.15 名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 18 页 -德州学院信息管理学院计算机科学与技术专业 2014 数据结构课程设计1 交通咨询模拟1 实习目的通过实习，了解并初步掌握设计、实现较大系统的完整过程，包括系统分析、编码设计、系统集成、以及调试分析，熟练掌握数据结构的选择、设计、实现以及操作方法，为进一步的应用开发打好基础。2 问题描述设计、实现一个全国大城市间的交通咨询程序，为旅客提供三种最优决策方案：（1）时间最短（2）费用最小（3）中转次数最少。该程序所做的工作的是模拟全国交通咨询，为旅客提供三种最优决策的交通咨询。此程序规定：（1）在程序中输入城市名称时，需输入10个字母以内的字母串；输入列车或飞机编号时需输入一个整型数据；输入列车或飞机的费用时需输入一个实型数据；输入列车或飞机开始时间和到达时间时均需输入两个整型数据（以hh：mm 的形式）；在选择功能时，应输入与所选功能对应的一个整型数据。（2）程序的输出信息主要是：最快需要多少时间才能到达，或最少需要多少旅费才能到达，或最少需要多少次中转到达，并详细说明依次于何时乘坐哪一趟列车或哪一次班机到何地。（3）程序的功能包括：提供对城市信息的编辑，提供列车时刻表和飞机航班表的编辑，提供三种最优决策：最快到达、最省钱到达、最少中转次数到达。3 概要设计3.1 数据结构设计系统用到的抽象数据类型定义：1ADT Graph 数据对象 V：一个集合，该集合中的所有元素具有相同的特性数据关系 R：R=VR VR=|P(x,y)(x,y属于 V)基本操作：（1）Initgraph(&G)；（2）CreateGraph(&G)；名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 18 页 -德州学院信息管理学院计算机科学与技术专业 2014 数据结构课程设计2（3）EnterVertex(&G)；（4）DeleteVertex(&G)；（5）EnterplaneArc(&G)；（6）DeleteplanArc(&G)；（7）EntertrainArc(&G)；（8）DeletetrainArc(&G)；ADT Graph 2ADT LinkQueue 数据元素：可以是任意类型的数据，但必须属于同一个数据对象关系：队列中数据元素之间是线性关系。基本操作：（1）InitQueue(&Q)；（2）IsEmpty(&Q)；（3）EnterQueue(&Q,x)；（4）DeleteQueue(&Q,&y)；ADT LinkQueue 3ADT TimeTree 数据对象 D：一个集合，该集合中的所有元素具有相同的特性数据关系 R：若 D为空，则为空树。若D中仅含有一个数据元素，则R为空集，否则 R=H，H为如下二元关系：（1）在 D中存在唯一的称为根的数据元素root，它在关系 H中没有前驱（2）除 root 以外，D中每个结点在关系 H下有且仅有一个前驱。基本操作：（1）CreateTimeTree(p,i,j,&Q,infolist arcs)；（2）CopyTimeTree(p,q)；（3）VisitTimeTree(p)；ADT TimeTree 3.2 函数及功能要求1Administer(ALGraph*G)：提供管理员管理城市交通系统的界面，通过该子程序可调用其他管理交通系统的子程序。名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 18 页 -德州学院信息管理学院计算机科学与技术专业 2014 数据结构课程设计3 2initgraph(ALGraph*G)：初始化交通系统的子程序。3createcityfile()：创建城市文件的子程序。4createplanefile()：创建航班文件的子程序。5createtrainfile()：创建列车时刻表文件的子程序。6LocateVertex(ALGraph*G,char*v)：提供城市名在城市交通系统中相应的编号。7CreateGraph(ALGraph*G)：创建城市交通系统。8cityedit(ALGraph*G)：提供城市编辑功能。9EnterVertex(ALGraph*G)：提供在城市交通系统中加入城市的功能。10DeleteVertex(ALGraph*G)：提供在城市交通系统中删除城市的功能。11flightedit(ALGraph*G)：提供航班编辑功能。12EnterplaneArc(ALGraph*G)：提供在城市交通系统中加入航班的功能。13DeleteplaneArc(ALGraph*G)：提供在城市交通系统中删除航班的功能。14：trainedit(ALGraph*G)：提供列车车次的编辑功能。15EntertrainArc(ALGraph*G)：提供在城市交通系统中加入列车车次的功能。16DeletetrainArc(ALGraph*G)：提供在城市交通系统中删除列车车次的功能。17UserDemand(ALGraph G)：提供用户咨询的界面。18DemandDispose(int n,ALGraph G)：通过该子程序调用其他咨询子程序。19InitQueue(LinkQueue*Q)：初始化队列。20EnterQueue(LinkQueue*Q,int x)：入队操作。21DeleteQueue(LinkQueue*Q,int*x)：出队操作。22IsEmpty(LinkQueue*Q)：队列判空操作。23TransferDispose(int k,infolist(*arcs)MAX_VERTEX_NUM,(*arcs)MAX_VERTEX_NUM,ALGraph G,ALGraph G,int v0,int v1)：提供最少中转次数决策的功能。24MinExpenditure(infolist arcs,float*expenditure,float*route)：提供两个城市之间最少费用的功能。25ExpenditureDispose(int k,infolist(*arcs)MAX_VERTEX_NUM,ALGraph G,int v0,int v1,float*D,int*final)：提供最少费用决策的功能。26MinTime(infolist arcs,float*time,float*route)：提供两个城市之间最名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 18 页 -德州学院信息管理学院计算机科学与技术专业 2014 数据结构课程设计4 短时间的功能。27TimeTreeDispose(Node*head,infolist(*arcs)MAX_VERTEX_NUM)：提供两个之间相隔一个以上城市的城市间的最短时间的功能。28CreateTimeTree(TimeTree p,int i,int j,LinkQueue*Q,infolist(*arcs)MAX_VERTEX_NUM)：创建时间树。29CopyTimeTree(TimeTree p,TimeTree q)：复制时间树。30VisitTimeTree(TimeTree p)：访问时间树。31DestoryTimeTree(TimeTree p)：销毁时间树。32TimeDispose(int k,infolist(*arcs)MAX_VERTEX_NUM,ALGraphG,int v0,int v1,float*D,int*final)：提供最少时间决策的功能。33：PrintGraph(ALGraph*G)：显示整个城市交通系统。3.3 模块调用关系各程序模块之间的调用关系（子程序编号见上）：主函数可调用子程序1，17，33。子程序 1 可调用子程序 2，8，11，14。子程序 2 可调用子程序 3，4，5，7。子程序 7，12，13，15，16 可调用子程序 6。子程序 8 可调用子程序 9，10。子程序 11 可调用子程序 12，13。子程序 14 可调用子程序 15，16。子程序 17 可调用子程序 18。子程序 18 可调用子程序 23，25，32。子程序 23 可调用子程序 19，29，21，22。子程序 25 可调用子程序 24。子程序 32 可调用子程序 26，27。子程序 27 可调用子程序 28，30，31。子程序 28 可调用子程序 29。名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 18 页 -德州学院信息管理学院计算机科学与技术专业 2014 数据结构课程设计5 4 详细设计4.1 创建交通图伪码创建交通图算法的伪码描述如下：int LocateVertex(ALGaph*G,char*v)/*找出城市名在图中对应结点位置*/for(k=0;kvexnum;k+)if(第 k 个结点中的城市名与传过来的城市名相同)j=k;/*记录位置*/break;返回 k 的数值；int CreatGraph(ALGraph*G)if(打开城市文件，文件指针返回值为空）输出错误文件信息；程序返回值为 0；while(文件不为空）将文件指针所指的字符串读到城市名数组 cityi中；i+;关闭文件；j=0;while(jvexnum=i;打开航班信息文件 plane.txt;将文件中的内容以块为单位读到缓冲区数组a 中；关闭文件；a 的计数变量 k=0;弧的计数变量 arc_num=0;while(kverticesi.planfirstarc;m=0;while(q!=NULL)if(弧 q 中的邻接顶点与 j 相等）将数组 ai 中的内容都复制到弧q 中；m=1;break;q=q-nextarc;if(m=0);开辟一个弧结点；将数组 ai中的内容都复制到新的弧结点中；将弧结点连接到适当的位置中去；arc_num+;名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 18 页 -德州学院信息管理学院计算机科学与技术专业 2014 数据结构课程设计7 k+;G-planarcnum=arc_num;打开列车信息文件 plane.txt;将文件中的内容以块为单位读到缓冲区数组a 中；关闭文件；a 的计数变量 k=0;弧的计数变量 arc_num=0;while(kverticesi.trainfirstarc;m=0;while(q!=NULL)if(弧 q 中的邻接顶点与 j 相等）将数组 ai 中的内容都复制到弧q 中；m=1;break;q=q-nextarc;if(m=0);开辟一个弧结点；将数组 ai中的内容都复制到新的弧结点中；将弧结点连接到适当的位置中去；arc_num+;名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 18 页 -德州学院信息管理学院计算机科学与技术专业 2014 数据结构课程设计8 k+;G-trainarcnum=arc_num;返回；4.2 建航班算法伪码建航班算法的伪码描述如下：creatplanefile()while(flag)/*flag为标志位,初值为 1*/提示“输入航班信息”；输入航班 code;输入航班的出发城市vt;输入航班的到达城市vh;输入机票价格 money;输入航班的出发时间bt;输入航班的到达时间at;a.count.co=code;/*a 为程序头部定义的结构体*/strcpy(a.count.vt,vt);strcpy(a.count.vh,vh);a.count.bt=bt;a.count.at=at;a.count.mo=money;计数值 count+1;提示“是否要继续输入航班信息：”；scanf(“%d”,&flag);if(航班文件不能以读写形式打开)提示“无法打开文件”；名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 18 页 -德州学院信息管理学院计算机科学与技术专业 2014 数据结构课程设计9 将计数值 count 写入航班车文件；for(i=0;icount;i+)if(无法将 ai写入航班文件)提示“文件无法写入”；关闭航班文件；4.3 删除城市结点算法伪码删除城市结点算法的伪码描述如下：DeleteVertex(ALGraph*G)/*G是程序头部定义的结构体*/提示“输入删除城市名”；gets(城市名：v);提示“是否确定要删除（Y/N）“；c=getchar();if(c=Y|c=y)n=0;/*0是记数标志，控制循环次数*/while(n 图 G表头接点总个数&图 G的存储城市名与 v 不同)/*G 表头结点总个数比实际大1*/记数值 n+1;if(n=图 G表头结点总个数)提示“无法找到此城市“；else i=LocateVertex(G,v);/*利用 G函数找到此城市名所处在G中位置*/删除从此结点出发的所有航班弧；删除从此结点出发的所有列车弧；for(j=i;j图 G表头结点总个数-1；j+)将 G第 j 个结点的信息依前移1 位；将 G第 j 个结点的信息制空；/*以下是删除所有指向此结点的航班弧*/for(k=0;kadjvex）i）将该弧指向顶点位置-1；q=p；p 指向下一条飞机弧；else if（该弧指向的顶点位置（p-adjvex）=i）if（p 指向图 G中 k 结点的第一条飞机弧）m=p；将图 G中 k 结点的第二条飞机弧改为第一弧；p 指向下一条飞机弧；释放（m）；else 将 p 的下一条弧赋给q 的下一条弧；m=p；p 指向下一条飞机弧；释放（q）；else q=p；p 指向下一条飞机弧；/*以下是删除所有指向此结点的列车弧*/for(k=0;kadjvex）i）将该弧指向顶点位置-1；q=p；p 指向下一条列车弧；else if（该弧指向的顶点位置（p-adjvex）=i）if（p 指向图 G中 k 结点的第一条列车弧）m=p；将图 G中 k 结点的第二条列车弧改为第一弧；p 指向下一条列车弧；释放（m）；else 将 p 的下一条弧赋给q 的下一条弧；m=p；p 指向下一条列车弧；释放（q）；else q=p；p 指向下一条列车弧；图 G表头结点总个数-1；else return；名师资料总结-精品资料欢迎下载-名师精心整理-第 12 页，共 18 页 -德州学院信息管理学院计算机科学与技术专业 2014 数据结构课程设计12 5 调试与测试结果分析5.1 操作员管理功能1.当我们从键盘输入有关图的顶点及弧的信息后，用显示图的函数验证，DOS 中显示的图的信息与从键盘输入的信息相同，表明交通系统可以从键盘正确输入信息。2.我们事先建立了有关图的3 个文本文件(包 city.txt,plan.txt,train.txt)，在交通系统程序中,选择从文本文件输入图的信息后,用显示操作验证，表明文本文件的内容可以正确调入图的结构体中，说明交通系统可以从文本文件中读取信息。3.当从键盘或文本文件初始化交通图后，测试增加或删除城市结点，增加或删除航班或列车弧，以上各功能都正确。5.2 交通咨询功能1.火车情况.（1）最少费用.a.两地间无中转且有多辆火车。北京-郑州输出结果为:旅行路线是:乘坐 NO.27列车车次在 13：15 从 Beijing 到 zhengzhou。最少旅行费用是 78 元。而若选择 NO.41 则花费为 80 元。结果正确。b.两地之间无中转达且只有一辆火车。西安-武汉输出结果为:旅行路线是:乘坐 NO.218列车车次在 1：34 从 xi an 到 wuhan。最少旅行费用是 178.00 元。结果正确。c.两地之间有中转。名师资料总结-精品资料欢迎下载-名师精心整理-第 13 页，共 18 页 -德州学院信息管理学院计算机科学与技术专业 2014 数据结构课程设计13 昆明-北京输出结果为:旅行路线是:乘坐 NO.323列车车次在 16.：31 从 kunming到 Guangzhou。乘坐 NO.59列车车次在 3：39 从 Guangzhou 到 shanghai。乘坐 NO.41列车车次在 0：35 从 shanghai 到 zhengzhou。乘坐 NO.27列车车次在 13：42 从 zhengzhou 到 Beijing。最少旅行费用是 462 元。而若选择昆明-武汉-兰州-北京 则花费为 506 元。若选择 昆明-武汉-西安-郑州-北京 则花费为 472 元。结果正确。(2)最短时间。a.两地间无中转且有多辆火车。北京-郑州输出结果为:旅行路线是:乘坐 NO.41列车车次在 13：15 从 Beijing 到 zhengzhou。最少旅行时间是 7：57。结果正确。b.两地之间无中转达且只有一辆火车。乌鲁木齐-兰州输出结果为:旅行路线是:乘坐 No.371 列车车次在 0：35 从 wulumuqi 到 lanzhou。最少旅行时间是 10：48。结果正确。c.两地之间有中转。广州-兰州输出结果为:旅行路线是:名师资料总结-精品资料欢迎下载-名师精心整理-第 14 页，共 18 页 -德州学院信息管理学院计算机科学与技术专业 2014 数据结构课程设计14 乘坐 NO.59列车车次在 3：39 从 guangzhou到 shanghai。乘坐 NO.41列车车次在 0：35 从 shanghai 到 zhengzhou。乘坐 NO.41列车车次在 9.40 从 zhengzhou到 Beijing。乘坐 NO.134列车车次在 19.24 从 Beijing到 lanzhou。最少旅行时间是 54：49。结果正确。2.飞机情况.（1）两地无直达。兰州-武汉输出结果为:不存在飞机航班从lanzhou 到 wuhan。（2）两地无直达。拉萨-昆明3.打印打印结果正确;4.退出能正确退出。6 使用说明1运行程序，首先出现主界面。主界面包括四个选项：选项一：管理员管理界面，选择该项可进行城市交通系统的管理，具体使用说明见说明2；选项二：用户咨询界面，选择该项可进行最少费用、最少时间、最少中转次数的决策咨询，具体使用见说明7；选项三：显示城市交通系统程序，选择该项可显示城市交通系统的所有信息，包括城市、航班和列车车次；选项四：退出程序，选择该项将退出程序。2管理员管理界面包括5 个选项：选项一：初始化城市交通系统界面，可进行城市交通系统的初始化，具体使用见说明3；选项二：城市编辑界面，可进行城市的增加和删除，具体使用见说明4；选项三：航班编辑界面，可进行航班的增加和删除，具体使用见说明 5；选项四：列车车次编辑界面，可进行列车车次的增加和删除，具体使用见说明 6；选项五：返回上一级菜单，可返回主界面。3初始化城市交通系统界面包括两个选项：选项一：通过键盘初始化城市交通系统，选择该项后程序将给出输入说明，按输入说明用户需逐步输入城市、航班、列车车名师资料总结-精品资料欢迎下载-名师精心整理-第 15 页，共 18 页 -德州学院信息管理学院计算机科学与技术专业 2014 数据结构课程设计15 次的信息来对城市交通系统初始化。在输入航班和列车信息时需注意两点：a.所输入的航班和列车的发车时间均在同一天。b.若发车时间小于到达时间，则说明列车在同一天到达，若发车时间大于到达时间，则说明列车在次日达到。飞机航班也是如此；选项二：通过文档初始化城市交通系统，选择该项可用文档进行初始化，但文档必须存在于程序的同一目录下，且必须包含CITY，PLANE，TRAIN三个文本文档，否则程序将提示出错。4城市编辑界面包括两个选项：选项一：增加城市，可在城市交通系统中加入新的城市，若用户输入的是已有的城市名，程序将提示出错；选项二：删除城市，可在城市交通系统中删除城市，用户必须输入一个已有的城市名，否则程序提示出错。5航班编辑界面包括两个选项：选项一：增加航班，可在两个城市之间新增航班，选择该项后用户需输入新增航班的编号，起始城市，到达城市及费用、时间等信息；选项二，删除航班，可删除两个城市间的一条航班，选择该项后用户需输入要删除航班的编号，起始城市，到达城市的信息，若航班不存在或编号、城市输入有误，程序将提示错误。6列车车次编辑界面包括两个选项：选项一：增加列车车次，可在两个城市之间新增列车车次，选择该项后用户需输入新增列车的编号，起始城市，到达城市及费用、时间等信息；选项二，删除列车车次，可删除两个城市间的一条列车车次，选择该项后用户需输入要删除车次的编号，起始城市，到达城市的信息，若列车车次不存在或编号、城市输入有误，程序将提示错误。7用户咨询界面包括四个选项：选项一：最少费用咨询；选项二：最少时间咨询；选项三：最少中转次数咨询；选项三：返回上级菜单，可返回主界面。选择选项一、二、三都要求用户输入咨询信息，包括起始城市，到达城市和交通工具。输入完毕后城市提示用户是否确认，若不确认则要求用户重新输入咨询信息，若确认则给出用户所需的最优决策信息。7 总结8 参考文献1 魏善沛.Web 数据库技术使用教程M.北京:清华大学出版社，1999.9 附录文中若用到图表按如下格式：名师资料总结-精品资料欢迎下载-名师精心整理-第 16 页，共 18 页 -德州学院信息管理学院计算机科学与技术专业 2014 数据结构课程设计16 图 1 用户登陆流程图表 1 文章信息表字段类型整理是否是空G_ID mediumint(8)否G_Title varchar(50)gbk_chiese_ci 否G_UserName varchar(20)gbk_chiese_ci否G_Sex Char(1)gbk_chiese_ci否G_Face varchar(20)gbk_chiese_ci否G_Email varchar(40)gbk_chiese_ci否G_QQ varchar(20)gbk_chiese_ci否G_Url varchar(40)gbk_chiese_ci否G_Brow varchar(20)gbk_chiese_ci否G_Content text gbk_chiese_ci否G_Reld mediumint(8)否G_ReadContent Smallint(6)否G_CommentCount Smallint(6)否名师资料总结-精品资料欢迎下载-名师精心整理-第 17 页，共 18 页 -德州学院信息管理学院计算机科学与技术专业 2014 数据结构课程设计17 G-Date datetime 否名师资料总结-精品资料欢迎下载-名师精心整理-第 18 页，共 18 页 -