数据结构课程设计报告(doc 64页).docx

n数据结构课程设计报告 题目：全国交通咨询模拟 学 院 信息 专 业 计算机科学与技术 年级班别 计科0902 学 号 0912300213 学生姓名 陈佳丽 指导教师 章志勇 一需求分析1程序设计任务： 从中国地图平面图中选取部分城市，抽象为程序所需要图的结点，并以城市间的列车路线和飞机路线，作为图结点中的弧信息，设计一个全国交通咨询模拟系统。利用该系统实现两种最优决策：最快到达或最省钱到达。2. 明确规定：(1)输入形式和输入值的范围： 每条飞机弧或者火车弧涉及的信息量很多，包括：起始城市、目的城市、出发时间、到达时间、班次以及费用。作为管理员要输入的信息包括以上信息，而作为用户或者客户，要输入的信息有起始城市和目的城市，并选择何种最优决策。 (2)输出形式：按用户提供的最优决策的不同而输出不同的信息，其中输出的所搭飞机或火车的班次及其起始地点和终点、起始时间和出发时间还有相关的最优信息，比如最快经多少时间到达、最省钱多少钱到达和最少经多少中转站到达。(3)程序所能达到的功能a.该系统有供用户选择的菜单和交互性。可以对城市、列车车次和飞机航班进行编辑，添加或删除。b.建立一个全国交通咨询系统，该系统具备自动查找任意两城市间铁路、飞机交通的最短路径和最少花费及中转次数最少等功能。c.初始化交通系统有两种方式，键盘和文档。二设计概要1.抽象数据类型本程序运用了关于图这种数据结构。ADT Graph 数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。 数据关系R： R=VR VR=<v,w>|v,wV且P(v,w),<v,w>表示从v到w的弧。 谓词P(v,w)定义了弧<v,w>的意义或信息 基本操作P： CreateGraph(&G,V,VR); 初始条件：V是图的顶点集，VR是图中弧的集合。 操作结果：按V和VR的定义构造图G。 DestroyGraph(&G); 初始条件：图G存在。 操作结果：销毁图G。 LocateVet(G,u); 初始条件：图G存在，u和G中顶点有相同的特征。 操作结果：若G中存在顶点u，则返回该顶点在图中的位置， 否则返回其他信息。 GetVex(G,v); 初始条件：图G存在，v是G中某个顶点。 操作结果：返回v的值。PutVex(&G,v,value); 初始条件：图G存在，v是G中某个顶点。 操作结果：对v赋值value。FirstAdjVex(G,v); 初始条件：图G存在，v是G中某个顶点。 操作结果：返回v的第一个邻接顶点。若顶点在G中没有邻接 顶点，则返回“空”。NextAdjVex(G,v,w); 初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点， 操作结果：返回v的(相对于w的)下一个邻接顶点。若w是v 的最后一个邻接点，则返回“空”。InsertVex(&G,v); 初始条件：图G存在，v和图中顶点有相同特征。 操作结果：在图G中添加新顶点v。DeleteVex(&G,v); 初始条件：图G存在，v是G中某个顶点。 操作结果：删除G中顶点v及相关弧。InsertArc(&G,v,w); 初始条件：图G存在，v和w是G中两个顶点。 操作结果：在G中增添弧<v,w>，若G是无向的则还增加对称弧 <w,w>。DeleteArc(&G,v,w); 初始条件：图G存在，v和w是G中两个顶点。 操作结果：在G中删除弧<v,w>，若G是无向的，则还删除对称 弧<w,v>。DFSTraverse(G,Visit(); 初始条件：图G存在，Visit是顶点的应用函数。 操作结果：对图进行深度优先遍历。在遍历过程中对每个顶点调用函数Visit一次且仅一次。一旦visit()失败，则操作失败。BFSTraverse(G,Visit(); 初始条件：图G存在，Visit是顶点的应用函数。 操作结果：对图进行广度优先遍历。在遍历过程中对每个顶点调用函数Visit一次且仅一次。一旦visit()失败，则操作失败。 ADT Graph其他的抽象数据类型定义如下：typedef structint number; float expenditure; int begintime2; int arrivetime2;Vehide;typedef structVehide stataMAX_ROUTE_NUM; int last;infolist;typedef struct ArcNodeint adjvex; struct ArcNode *nextarc; infolist info;ArcNode;typedef struct VNodechar cityname10; ArcNode *planefirstarc,*trainfirstarc;VNode,AdjListMAX_VERTEX_NUM;typedef structAdjList vertices; int vexnum,planearcnum,trainarcnum;ALGraph;typedef struct Nodeint adjvex; int route; struct Node *next;Node;typedef struct QNodeint adjvex; struct QNode *next;QNode;typedef structQNode *front; QNode *rear;LinkQueue;typedef struct TimeNodeint adjvex; int route; int begintime2; int arrivetime2; struct TimeNode *childMAX_ROUTE_NUM;TimeNode,*TimeTree;struct arcint co; char vt10; char vh10; int bt2; int at2; float mo;aMAX_ARC_SIZE;基本操作：void Administer(ALGraph *G);void cityedit(ALGraph *G);void CopyTimeTree(TimeTree p,TimeTree q);void createcityfile();void CreateGraph(ALGraph *G);void createplanefile();void CreateTimeTree(TimeTree p,int i,int j,LinkQueue *Q,infolist (*arcs)MAX_VERTEX_NUM);void createtrainfile();int DeleteplaneArc(ALGraph *G);void DeleteQueue(LinkQueue *Q,int *x);int DeletetrainArc(ALGraph *G);void DeleteVertex(ALGraph *G);void DemandDispose(int n,ALGraph G);void DestoryTimeTree(TimeTree p);void EnterplaneArc(ALGraph *G);void EnterQueue(LinkQueue *Q,int x);void EntertrainArc(ALGraph *G);void EnterVertex(ALGraph *G);void ExpenditureDispose(int k,infolist (*arcs)MAX_VERTEX_NUM,ALGraph G,int v0,int v1,float *M,int *final);void flightedit(ALGraph *G);void initgraph(ALGraph *G);void InitQueue(LinkQueue *Q);int IsEmpty(LinkQueue *Q);int LocateVertex(ALGraph *G,char *v);void MinExpenditure(infolist arcs,float *expenditure,int *route);void MinTime(infolist arcs,int *time,int *route);void PrintGraph(ALGraph *G);int save(ALGraph *G);void TimeDispose(int k,infolist (*arcs)MAX_VERTEX_NUM,ALGraph G,int v0,int v1,int (*T)2,int *final);void TimeTreeDispose(Node *head,infolist (*arcs)MAX_VERTEX_NUM);void trainedit(ALGraph *G);void TransferDispose(int k,infolist (*arcs)MAX_VERTEX_NUM,ALGraph G,int v0,int v1);void UserDemand(ALGraph G);void VisitTimeTree(TimeTree p);主程序的流程以及各程序模块之间的调用关系退出显示交通系统PrintGraph用户咨询UserDemand管理员管理Administer主函数main（） 返回上一级菜单列车车次编辑Administer飞机航班编辑Administer城市编辑cityedit管理员管理Administer初始化交通系统initgraph返回上一级菜单最少中转次数TransferDispose最少旅行时间TimeDispose用户咨询UserDemand最少旅行费用ExpenditureDisposeUserDemand显示城市显示飞机航班显示列车车次返回上一级菜单显示交通系统PrintGraph文档键盘初始化交通系统initgraph删除城市新增城市城市编辑cityedit删除航班新增航班飞机航班编辑planeedit删除车次新增车次火车列次编辑trainedit三详细设计1.主程序伪代码 int main() 界面初始化； 输入操作命令； While（“命令” ！= “退出”） 接受命令（用户输入要实现功能）； 进入各个处理命令函数；2. 函数和过程的调用关系图DeleteQueueEnterQueueInitQueueMinTimeTimeTreeDisposeEnterplaneArcDeleteplaneArcEntertrainArcDeletetrainArcTransferDisposeTimeDisposeMinExpenditureExpenditureDisposecreateplanefilecreatetrainfileCreateGraphinitgraphcityeditAdministerPrintGraphEnterVertextraineditDeleteVertexcreatecityfileflighteditUserDemandMain()InitQueueEnterQueueDeleteQueueCreateTimeTreeCopyTimeTreeTimeTreeDisposeVisitTimeTreeDestoryTimeTree四调试分析： 调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析： 在调试的过程中碰到了一下问题：a. 引用形参应用不当；b. 文件操作中遇到读入错误或找不到文件；解决方案：a. 对引用形参了解的不是很透彻，导致错误，通过查阅相关书籍如C+ Primer和请教编程能力较高的人，最终解决问题。b. 通过参考谭浩强编著的C程序设计中的文件操作，文件格式和相关文件路径的设置，最终解决问题。 算法的时空分析（包括基本操作和其他算法的时间复杂度和空间复杂度的分析）和改进设想：基本操作时间复杂度空间复杂度void Administer(ALGraph *G)O(1)O(1)void cityedit(ALGraph *G)O(n)O(n)void CopyTimeTree(TimeTree p,TimeTree q)O(n)O(1)void createcityfile()O(n)O(n)void CreateGraph(ALGraph *G)O(n)O(n)void createplanefile()O(1)O(1)void CreateTimeTree(TimeTree p,int i,int j,LinkQueue *Q,infolist (*arcs)MAX_VERTEX_NUM)O(n)O(n)void createtrainfile()O(1)O(1)int DeleteplaneArc(ALGraph *G)O(n)O(n)void DeleteQueue(LinkQueue *Q,int *x)O(1)O(1)int DeletetrainArc(ALGraph *G)O(n)O(n)void DeleteVertex(ALGraph *G)O(n)O(n)void DemandDispose(int n,ALGraph G)O(1)O(1)void DestoryTimeTree(TimeTree p)O(n)O(1)void EnterplaneArc(ALGraph *G)O(n)O(n)void EnterQueue(LinkQueue *Q,int x)O(1)O(1)void EntertrainArc(ALGraph *G)O(1)O(1)void EnterVertex(ALGraph *G)O(n)O(n)void ExpenditureDispose(int k,infolist (*arcs)MAX_VERTEX_NUM,ALGraph G,int v0,int v1,float *M,int *final)O(n)O(1)void flightedit(ALGraph *G)O(1)O(1)void initgraph(ALGraph *G)O(1)O(n)void InitQueue(LinkQueue *Q)O(1)O(1)int IsEmpty(LinkQueue *Q)O(1)O(1)int LocateVertex(ALGraph *G,char *v)O(n)O(1)void MinExpenditure(infolist arcs,float *expenditure,int *route)O(n)O(n)void MinTime(infolist arcs,int *time,int *route)O(n)O(n)void PrintGraph(ALGraph *G)O(1)O(n)int save(ALGraph *G)O(1)O(1)void TimeDispose(int k,infolist (*arcs)MAX_VERTEX_NUM,ALGraph G,int v0,int v1,int (*T)2,int *final)O(n)O(n)void TimeTreeDispose(Node *head,infolist (*arcs)MAX_VERTEX_NUM)O(n)O(n)void trainedit(ALGraph *G)O(1)O(1)void TransferDispose(int k,infolist (*arcs)MAX_VERTEX_NUM,ALGraph G,int v0,int v1)O(n)O(n)void UserDemand(ALGraph G)O(1)O(1)void VisitTimeTree(TimeTree p)O(n)O(n) 经验和体会： 通过本次课程设计，我学到了一种程序设计方法，就是结构化程序设计方法，在程序设计过程中，我尝试按如下方法进行结构化程序设计：(1)自顶向下；(2)逐步细化；(3)模块化设计(4)结构化编码。这种设计方法的过程是将问题求解由抽象逐步具体化的过程，而且，用这种方法便于验证算法的正确性。 本次课程设计所使用的是较为复杂的抽象数据类型图，而且在弧的基础上增加了许多信息，如添加了时间，费用等等，这无疑给编程加大了难度，同时也是相当的具有挑战性。在编程的过程中，我用到了全局数组，我将数组放在工程的头文件里面，编译的时候报错，说是多重定义。最终放弃了创建工程，而选择了单个文件进行编译和运行，结果顺利通过。同时，在文件操作方面我也曾遇到问题，就是在程序对文件进行读取的时候报错，无法读取文件，最后查询有关C的工具书，原来是文件路径问题，借助工具书最终解决了文件操作方面的问题。总之，这次课程设计是对这一个学期以来对数据结构学习成果的一个验证，同时也是理论与实践很好的结合，既对学过的数据结构进行了巩固，也对我的编程能力奠定了坚实的基础。五用户使用说明：1) 打开并运行程序，按任意键进入操作主界面，按提示进行相关操作；2) 按“1”进入管理员界面，按“2”进入用户咨询界面，按“3”显示交通系统，按“4”则退出。3) 进入管理员界面可键入“1”初始化交通系统，并选择文档初始化方式(如果是第一次使用该系统建议使用文档初始化交通系统，免得自己进行繁冗的初始化操作)。其余可按提示进行相关操作，不难掌握。4) 进入用户咨询界面，可根据用户需要进行相关的选择，或是选择“1”(最少旅行费用)；或是选择“2”(最少旅行时间)，又或者是选择“3”(最少旅行中转次数)等。5) 进入显示交通系统界面，根据用户选择则可显示城市、飞机航班、列车车次等信息。或者返回上一级菜单。六测试结果：1. 个人信息界面：2. 操作主界面：3. 管理员界面：4. 交通系统初始化方式选择界面：5. 城市编辑界面：6. 飞机航班编辑：7. 列车车次编辑：8. 显示交通系统主界面：9. 显示城市：10. 显示飞机航班：11. 显示列车车次：12 用户咨询：13. 选择旅行起始城市：14. 选择旅行到达城市：15. 选择旅行的交通工具：16. 最少旅行费用：17最少旅行时间：18. 最少中转次数：七附录源程序#define MAX_VERTEX_NUM 18#define NULL 0#define MAX_ARC_SIZE 100#define MAX_ROUTE_NUM 5#include<stdio.h>#include<stdlib.h>#include<string.h>#include<conio.h>#define False 0#define True 1#define INFINITY 10000typedef structint number;float expenditure; int begintime2; int arrivetime2;Vehide;typedef structVehide stataMAX_ROUTE_NUM; int last;infolist;typedef struct ArcNodeint adjvex;struct ArcNode *nextarc; infolist info;ArcNode;typedef struct VNodechar cityname10;ArcNode *planefirstarc,*trainfirstarc;VNode,AdjListMAX_VERTEX_NUM;typedef structAdjList vertices; int vexnum,planearcnum,trainarcnum;ALGraph;typedef struct Nodeint adjvex; int route; struct Node *next;Node;typedef struct QNodeint adjvex; struct QNode *next;QNode;typedef structQNode *front; QNode *rear;LinkQueue;typedef struct TimeNodeint adjvex; int route; int begintime2; int arrivetime2; struct TimeNode *childMAX_ROUTE_NUM;TimeNode,*TimeTree; struct arcint co; char vt10; char vh10; int bt2; int at2; float mo;aMAX_ARC_SIZE;char cityMAX_VERTEX_NUM10;int TTime2;int time2;int time12;int time22;int cMAX_VERTEX_NUM;int dMAX_VERTEX_NUM;void Administer(ALGraph *G);void cityedit(ALGraph *G);void CopyTimeTree(TimeTree p,TimeTree q);void createcityfile();void CreateGraph(ALGraph *G);void createplanefile();void CreateTimeTree(TimeTree p,int i,int j,LinkQueue *Q,infolist (*arcs)MAX_VERTEX_NUM);void createtrainfile();int DeleteplaneArc(ALGraph *G);void DeleteQueue(LinkQueue *Q,int *x);int DeletetrainArc(ALGraph *G);void DeleteVertex(ALGraph *G);void DemandDispose(int n,ALGraph G);void DestoryTimeTree(TimeTree p);void EnterplaneArc(ALGraph *G);void EnterQueue(LinkQueue *Q,int x);void EntertrainArc(ALGraph *G);void EnterVertex(ALGraph *G);void ExpenditureDispose(int k,infolist (*arcs)MAX_VERTEX_NUM,ALGraph G,int v0,int v1,float *M,int *final);void flightedit(ALGraph *G);void initgraph(ALGraph *G);void InitQueue(LinkQueue *Q);int IsEmpty(LinkQueue *Q);int LocateVertex(ALGraph *G,char *v);void MinExpenditure(infolist arcs,float *expenditure,int *route);void MinTime(infolist arcs,int *time,int *route);void PrintGraph(ALGraph *G);int save(ALGraph *G);void TimeDispose(int k,infolist (*arcs)MAX_VERTEX_NUM,ALGraph G,int v0,int v1,int (*T)2,int *final);void TimeTreeDispose(Node *head,infolist (*arcs)MAX_VERTEX_NUM);void trainedit(ALGraph *G);void TransferDispose(int k,infolist (*arcs)MAX_VERTEX_NUM,ALGraph G,int v0,int v1);void UserDemand(ALGraph G);void VisitTimeTree(TimeTree p);int main()ALGraph G; int i; printf("nnnnnnn*"); printf("*"); printf("* 学院：计算机学院 *"); printf("* 专业：计算机科学与技术 *"); printf("* 班级：计科0902 *"); printf("* 姓名：陈佳丽 *"); printf("* 学号：0912300213 *"); printf("*"); printf("*"); printf("请按任何键以继续"); getchar(); system("cls"); printf("nnnnnnn 请选择程序功能:n"); printf(" *n"); printf(" * 1=管理员管理 *n"); printf(" * 2=用户咨询 *n"); printf(" * 3=显示交通系统 *n"); printf(" * 4=退出 *n"); printf(" *n"); printf(" 选择?"); scanf("%d",&i); getchar(); while(i!=4) switch(i) case 1:Administer(&G); break; case 2:UserDemand(G); break; case 3:PrintGraph(&G); break; system("cls"); printf("nnnnnnnn 请选择程序功能:n" ); printf(" *n"); printf(" * 1=管理员管理 *n"); printf(" * 2=用户咨询 *n"); printf(" * 3=显示交通系统 *n"); printf(" * 4=退出 *n"); printf(" *n"); printf(" 选择?"); scanf("%d",&i); getchar(); return 1; void Administer(ALGraph *G)int i;system("cls");printf("nnnnnnnn 请选择管理项目:n"); printf(" *n"); printf(" * 1=初始化交通系统 *n"); printf(" * 2=城市编辑 *n"); printf(" * 3=飞机航班编辑 *n"); printf(" * 4=列车车次编辑 *n"); printf(" * 5=返回上一级菜单 *n"); printf(" *n"); printf(" 选择?"); scanf("%d",&i); getchar();while(i!=5)switch(i)case 1:initgraph(G); break; case 2:cityedit(