交通图咨询查询系统数据结构(C语言) (2).docx

数据结构（C语言版）（第2版）课后习题答案李冬梅2015.3目录第1章绪论 (1)第2章线性表 (5)第3章栈和队列 (13)第4章串、数组和广义表 (26)第5章树和二叉树 (33)第6章图 (43)第7章查找 (54)第8章排序 (65)第1章绪论1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。

答案：数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。

如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。

数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。

在有些情况下，数据元素也称为元素、结点、记录等。

数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。

数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。

例如，学生基本信息表中的学号、姓名、性别等都是数据项。

数据对象：是性质相同的数据元素的集合，是数据的一个子集。

例如：整数数据对象是集合N={0，±1，±2，…}，字母字符数据对象是集合C={‘A’，‘B’，…，‘Z’，‘a’，‘b’，…，‘z’}，学生基本信息表也可是一个数据对象。

数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。

换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。

逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。

因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。

存储结构：数据对象在计算机中的存储表示，也称为物理结构。

抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。

具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。

数据结构（C语言版）（第2版）课后习题答案数据结构（C语言版）（第2版）课后习题答案目录第1章绪论1 第2章线性表5 第3章栈和队列13 第4章串、数组和广义表26 第5章树和二叉树33 第6章图43 第7章查找54 第8章排序65 第1章绪论1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。

答案：数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。

如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。

数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。

在有些情况下，数据元素也称为元素、结点、记录等。

数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。

数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。

例如，学生基本信息表中的学号、姓名、性别等都是数据项。

数据对象：是性质相同的数据元素的集合，是数据的一个子集。

例如：整数数据对象是集合N={0，±1，±2，。

}，字母字符数据对象是集合C={‘A’，‘B’，。

，‘Z’，‘a’，‘b’，。

，‘z’}，学生基本信息表也可是一个数据对象。

数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。

换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。

逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。

因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。

存储结构：数据对象在计算机中的存储表示，也称为物理结构。

抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。

具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。

2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。

数据结构课程设计-全国交通咨询模拟系统程序设计源代码一、程序界面A.关于程序1. 该程序以C语言为开发工具,运行该程序前请确保你的机器上已安装tc或turboc ,否则系统会提示:BGI Error: Graphics not initialized (use 'initgraph')而无法使用该程序。

遇到此情况请安装tc ,建议将其安装到C:目录下,以确保程序运行万无一失。

2. 该软件完全支持鼠标,请放心使用。

3. 该程序能将您输入的城市转换为象素坐标,显示在屏幕上,操作直观方便,选择城市时,用时标一点该城市即可,省去了输入的麻烦。

如果您选择的两个城市间有路径的话,程序除了给您信息输出外,还会在地图上将此路径以不同颜色画出,更加直观。

4. 该程序附带三个数据文件(num.txt,vex.t xt,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) ]此时程序等待用户输入选择.输入正确后程序会自动打开地图由用户进行下一步操作.3. 对于其他命令,用户可由显示于屏幕下面的提示进行相关操作.二.程序内部设计及数据结构A. 数据的存放格式1.火车信息数据结构定义:typedef struct inf{ int num;/*车次*/int stt1;int stt2;/*出发时间*/int endt1;int endt2;/*到达时间*/int waitt;/*等待时间*/int allt;/*两站之间总耗时*/int money;/*票价*/}inf2.车站信息数据结构定义:typedef struct ArcCell{int ff;/*ff=1 表示两点有信息*/int adj;/*路程长度*/inf two;/*火车信息* /}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; 3.图的数据结构定义typedef struct Mgraph{ char vexs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];/*顶点名*/AdjMatrix arcs;/* 车站信息*/int vexsx[MAX_VERTEX_NUM];/*该顶点的X坐标*/int vexsy[MAX_VERTEX_NUM]; /*该顶点的Y坐标*/int vexnum,arcnum; /* vexnum:顶点的数目,arcnum:路线数目*/}Mgraph;4.基于以上数据结构的数据存储举例:(以下为部分顶点信息)wulumuqi 49 59(表示城市wulumuqi 在640X480的屏幕中位于坐标49,59处,下同)xining 97 155lanzhou 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元。

CHINA交通咨询系统目录一、需求分析 (2)1、程序的功能及设计要求 (2)2、输入输出的要求 (2)二、环境说明 (2)三、详细设计 (3)1、模块设计 (3)2、画出各函数的调用关系图、主要函数的流程图。

(3)2、详细代码 (4)四、调试分析 (4)1、测试数据： (4)2、借鉴的资料 (5)五、课程总结 (6)六、附录 (6)一、需求分析1、程序的功能及设计要求在交通网络非常发达、交通工具和交通方式不断更新的今天，人们在出差、旅游或做其他出行时，不仅关心节省交通费用，而且对里程和所需时间等问题也感兴趣.对于这样一个人们关心的问题，通过建立交通网络图的存储结构图，提供用户查询的功能，功能一:通过输入城市名及任意两个城市的距离,查询任意两个城市之间的最短距离，从而达到最省目的；功能二：通过输入城市名以及任意两个程序的距离，查询中转路线最少。

程序所具有的功能特色本程序主要目的是为了给用户提供路径咨询，可以通过输入设置，延续程序的拓展性。

设计要求及分析设计一个交通咨询系统，能让旅客咨询从任一个城市顶点到另一城市顶点之间的中转次数最少问题或最低花费或最少时间(最短路径）问题。

该设计共分三个部分：一是建立交通网络图的存储结构；二是解决单源最短路径问题；最后再实现任意两个城市顶点之间的最短路径问题。

1。

建立交通网络图的存储结构要实现设计要求,首先要定义交通图的存储结构：邻接链表和邻接矩阵；2。

解决任意两个城市顶点之间的中转次数最少的问题;3. 解决任意两个城市顶点之间的最短路径(最低花费或最少时间）问题。

2、输入输出的要求定义变量类型应该保持类型一致，通过键盘输入，确保输入输出一致，使最短路径途径以及最短路径能够简单明了的输出，同时保持程序简洁美观，效果明显。

输入要求为输入界面直观、亲切；有利于快速输入；有利于准确输入;有利于输入、修改；方便操作。

输出要求：输出要求应简单、直观，一目了然，尽量符合用户的习惯，便于用户阅读、理解与使用.输出内容应尽量汉字化，从而使输出格式醒目；各种输出设计要长考虑以利于系统发展和输出项目扩充、变动的需要；输出操作方便二、环境说明系统：WINDOS7开发软件：vc6+三、详细设计1、模块设计交通咨询系统模块图如下由模块图可知，该设计共分三个部分：一是建立交通网络图的存储结构;二是解决单源最短路径问题；最后再实现任意两个城市顶点之间的最短路径问题。

目录第1章概述 (1)1.1 性能需求 (1)1.2 功能需求 (2)第2章概要设计 (3)2。

1功能模块设计 (3)2.2算法分析与设计 (3)第3章详细设计 (5)3.1 管理员功能模块设计 (5)3。

2计算最少费用功能模块设计 (11)第4章调试分析与测试结果 (18)4。

1调试分析 (18)4。

2测试结果 (19)第5章总结 (21)参考文献 (22)附录 (23)第1章概述数据结构作为一门学科主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。

因此,主要有三个方面的内容：数据的逻辑结构；数据的物理存储结构；对数据的操作（或算法）。

通常，算法的设计取决于数据的逻辑结构,算法的实现取决于数据的物理存储结构.数据结构是信息的一种组织方式，其目的是为了提高算法的效率，它通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。

在当今信息时代，信息技术己成为当代知识经济的核心技术。

我们时刻都在和数据打交道。

比如人们在外出工作时找最短路径,在银行查询存款、通过互联网查新闻、以及远程教育报名等,所有这些都在与数据发生关系。

实际上，现实世界中的实体经过抽象以后，就可以成为计算机上所处理的数据。

数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。

数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程,它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。

学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。

通过课程设计可以提高学生的思维能力,促进学生的综合应用能力和专业素质的提高。

通过此次课程设计主要达到以下目的:1。

了解并掌握数据结构与算法的设计方法,具备初步的独立分析和设计能力；2。

初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4。

头文件：（TrafficGraph.h）#ifndef TrafficGraph_h#define TrafficGraph_h#define dingdian 18#define NULL 0#define hu 100#define lujing 5#include"queue.h"#include"heap.h"#include<string.h>#include<conio.h>#include<fstream>char *ch[2]={"列车","航班"};template<class T>class Graph{struct EdgeNode{int dest;double cost;operator int(){return dest;}};typedef struct{char number[20];float expenditure;int begintime[2];int arrivetime[2];}qiche;typedef struct{qiche stata[lujing];int last;}infolist;typedef struct ArcNode{int adjvex;struct ArcNode *nextarc;infolist info;}ArcNode;typedef struct VNode{char cityname[10];ArcNode *planefirstarc,*trainfirstarc;}VNode,AdjList[dingdian];typedef struct{AdjList vertices;int vexnum,planearcnum,trainarcnum; }ALGraph;AdjList vertices;int vexnum,planearcnum,trainarcnum; typedef struct Node{int adjvex;int route;struct Node *next;}Node;typedef struct QNode{int adjvex;struct QNode *next;}QNode;typedef struct{QNode *front;QNode *rear;}LinkQueue;typedef struct TimeNode{int adjvex;int route;int begintime[2];int arrivetime[2];struct TimeNode *child[lujing];}TimeNode,*TimeTree;struct arc{char co[20];char vt[10];char vh[10];int bt[2];int at[2];float mo;}a[hu];char city[dingdian][10];int TTime[2],time[2],time1[2],time2[2];int c[dingdian],d[dingdian];public:Graph(){}~Graph(){}void guanliyuan();void cityedit();void CopyTimeTree(TimeTree p,TimeTree q);void createcityfile();void CreateGraph();void createplanefile();void CreateTimeTree(TimeTree p,int i,int j,LinkQueue *Q,infolist (*arcs)[dingdian]);void createtrainfile();void DeleteEdge(int j,T *code,ArcNode *E,char *ch);int DeleteplaneArc();void DeleteQueue(LinkQueue *Q,int *x);int DeletetrainArc();void DeleteVertex();void DemandDispose(int n);void DestoryTimeTree(TimeTree p);void EnterEdge(int j,int *bt,int *at,T *code,float money,ArcNode *E,int s);void EnterplaneArc();void EnterQueue(LinkQueue *Q,int x);void EntertrainArc();void EnterVertex();void ExpenditureDispose(int k,infolist (*arcs)[dingdian],int v0,int v1,float *M,int *final);void flightedit();//编辑航班void chushihua();//初始化系统void InitQueue(LinkQueue *Q);int IsEmpty(LinkQueue *Q);int LocateVertex(T *v);void MinExpenditure(infolist arcs,float *expenditure,int *route);void MinTime(infolist arcs,int *time,int *route);void PrintGraph();int save();void TimeDispose(int k,infolist (*arcs)[dingdian],int v0,int v1,int (*S)[2],int *final);void TimeTreeDispose(Node *head,infolist (*arcs)[dingdian]);void trainedit();void TransferDispose(int k,infolist (*arcs)[dingdian],int v0,int v1);void UserDemand();void VisitTimeTree(TimeTree p);};template<class T>void Graph<T>::guanliyuan(){int i=0;while(i!=5){system("cls");cout<<"\n\t\t\t【管理员管理】"<<endl;cout<<"\t\t*******************************"<<endl;cout<<"\t\t\t1=初始化交通系统"<<endl;cout<<"\t\t\t2=城市编辑"<<endl;cout<<"\t\t\t3=飞机航班编辑"<<endl;cout<<"\t\t\t4=列车车次编辑"<<endl;cout<<"\t\t\t5=返回上一级菜单"<<endl;cout<<"\t\t*******************************"<<endl;cout<<"\t\t请输入您的选择：";cin>>i;getchar();switch(i){case 1:chushihua();break;case 2:cityedit();break;case 3:flightedit();break;case 4:trainedit();break;}}}template<class T>void Graph<T>::chushihua(){system("cls");int i;cout<<"\n\t\t您想从哪儿初始化(键盘（1）或文档（2）):";cin>>i;getchar();switch(i){createcityfile();createplanefile();createtrainfile();CreateGraph();break;case 2:CreateGraph();break;}}template<class T>void Graph<T>::createcityfile()//新建“城市”文件{int i=0;int j;char flag='y';FILE *fp;cout<<"【请输入城市名称的信息】"<<endl;while(flag=='y'||flag=='Y'){cout<<"城市名称（小于10字符）：";gets(city[i]);i++;cout<<"继续输入?(Y/N)";cin>>flag;getchar();}if((fp=fopen("city.txt","wb"))==NULL){cout<<"无法打开文件!"<<endl;return;}for(j=0; j<i; j++)fprintf(fp,"%10s",city[j]);fclose(fp);}template<class T>void Graph<T>::createplanefile()//新建“航班”文件{T code[20];int bt[2],at[2];float money;int i;char vt[10],vh[10],flag;FILE *fp;flag='y';count=0;while(flag=='Y'||flag=='y'){cout<<"【请输入飞机航班的信息】"<<endl;cout<<"飞机航班编号:";cin>>code;getchar();cout<<"起始城市:";gets(vt);cout<<"目的城市:";gets(vh);cout<<"航班费用:";cin>>money;getchar();cout<<"起飞时间:(时:分)";scanf("%d:%d",&bt[0],&bt[1]);getchar();while(bt[0]<0||bt[0]>=24||bt[1]<0||bt[1]>=60) {cout<<"时间输入有误，请重新输入：";scanf("%d:%d",&bt[0],&bt[1]);getchar();}cout<<"到达时间:(时:分)";scanf("%d:%d",&at[0],&at[1]);getchar();while(at[0]<0||at[0]>=24||at[1]<0||at[1]>=60){cout<<"时间输入有误，请重新输入：";scanf("%d:%d",&at[0],&at[1]);getchar();}strcpy(a[count].co,code);strcpy(a[count].vt,vt);strcpy(a[count].vh,vh);a[count].bt[0]=bt[0];a[count].bt[1]=bt[1];a[count].at[0]=at[0];a[count].at[1]=at[1];a[count].mo=money;count++;cout<<"继续输入?(Y/N)";cin>>flag;getchar();}if((fp=fopen("plane.txt","wb"))==NULL)cout<<"无法打开文件!"<<endl;fprintf(fp,"%d",count);for(i=0; i<count; i++)if(fwrite(&a[i],sizeof(struct arc),1,fp)!=1)cout<<"文件写入错误!"<<endl;fclose(fp);}template<class T>void Graph<T>::createtrainfile(){T code[20];int bt[2],at[2];float money;int i;int count;char vt[10],vh[10],flag;FILE *fp;flag='y';count=0;while(flag=='y'||flag=='Y'){cout<<"【请输入列车车次的信息】"<<endl;cout<<"列车车次编号:";cin>>code;getchar();cout<<"起始城市:";gets(vt);cout<<"目的城市:";gets(vh);cout<<"车次费用:";cin>>money;getchar();cout<<"发车时间:(时:分)";scanf("%d:%d",&bt[0],&bt[1]);getchar();while(bt[0]<0||bt[0]>=24||bt[1]<0||bt[1]>=60){cout<<"时间输入有误，请重新输入：";scanf("%d:%d",&bt[0],&bt[1]);getchar();}cout<<"到达时间:(时:分)";scanf("%d:%d",&at[0],&at[1]);getchar();while(at[0]<0||at[0]>=24||at[1]<0||at[1]>=60){cout<<"时间输入有误，请重新输入：";scanf("%d:%d",&at[0],&at[1]);getchar();}strcpy(a[count].co,code);strcpy(a[count].vt,vt);strcpy(a[count].vh,vh);a[count].bt[0]=bt[0];a[count].bt[1]=bt[1];a[count].at[0]=at[0];a[count].at[1]=at[1];a[count].mo=money;count++;cout<<"继续输入?(Y/N)";cin>>flag;getchar();}if((fp=fopen("train.txt","wb"))==NULL)cout<<"无法打开文件!"<<endl;fprintf(fp,"%d",count);for(i=0; i<count; i++)if(fwrite(&a[i],sizeof(struct arc),1,fp)!=1)cout<<"文件写入错误!"<<endl;fclose(fp);}template<class T>int Graph<T>::LocateVertex(T *v){int j,k;j=-1;for(k=0; k<vexnum; k++)if(strcmp(vertices[k].cityname,v)==0){j=k;break;}return j;}template<class T>void Graph<T>::CreateGraph(){int i,j,k;int arc_num;int count1,count2;int m,t;ArcNode *p,*q;FILE *fp;i=0;if((fp=fopen("city.txt","rb"))==NULL){cout<<"无法打开文件!"<<endl;return;}while(!feof(fp)){fscanf(fp,"%10s",city[i]);i++;}fclose(fp);j=0;while(j<i){strcpy(vertices[j].cityname,city[j]);vertices[j].planefirstarc=NULL;vertices[j].trainfirstarc=NULL;j++;}vexnum=i;if((fp=fopen("plane.txt","rb"))==NULL)cout<<"无法打开文件!"<<endl;k=0;fscanf(fp,"%d",&count1);while(k<count1){if(fread(&a[k],sizeof(struct arc),1,fp)!=1)cout<<"文件读取错误!"<<endl;k++;}fclose(fp);k=0;arc_num=0;while(k<count1){i=LocateVertex(a[k].vt);j=LocateVertex(a[k].vh);q=vertices[i].planefirstarc;m=0;while(q!=NULL){if(q->adjvex==j){t=q->st+1;strcpy(q->info.stata[t].number,a[k].co);q->info.stata[t].expenditure=a[k].mo;q->info.stata[t].begintime[0]=a[k].bt[0];q->info.stata[t].begintime[1]=a[k].bt[1];q->info.stata[t].arrivetime[0]=a[k].at[0];q->info.stata[t].arrivetime[1]=a[k].at[1];q->st=t;m=1;break;}q=q->nextarc;}if(m==0){p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=j;strcpy(p->info.stata[0].number,a[k].co);p->info.stata[0].expenditure=a[k].mo;p->info.stata[0].begintime[0]=a[k].bt[0];p->info.stata[0].begintime[1]=a[k].bt[1];p->info.stata[0].arrivetime[0]=a[k].at[0];p->info.stata[0].arrivetime[1]=a[k].at[1];p->st=0;p->nextarc=vertices[i].planefirstarc;vertices[i].planefirstarc=p;arc_num++;}k++;}planearcnum=arc_num;if((fp=fopen("train.txt","rb"))==NULL){cout<<"无法打开文件!"<<endl;return;}k=0;fscanf(fp,"%d",&count2);while(k<count2){if(fread(&a[k],sizeof(struct arc),1,fp)!=1)cout<<"文件读取错误!"<<endl;k++;}fclose(fp);k=0;arc_num=0;while(k<count2){i=LocateVertex(a[k].vt);j=LocateVertex(a[k].vh);q=vertices[i].trainfirstarc;m=0;while(q!=NULL){if(q->adjvex==j){t=q->st+1;strcpy(q->info.stata[t].number,a[k].co);q->info.stata[t].expenditure=a[k].mo;q->info.stata[t].begintime[0]=a[k].bt[0];q->info.stata[t].begintime[1]=a[k].bt[1];q->info.stata[t].arrivetime[0]=a[k].at[0];q->info.stata[t].arrivetime[1]=a[k].at[1];q->st=t;m=1;break;}q=q->nextarc;}if(m==0){p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=j;strcpy(p->info.stata[0].number,a[k].co);p->info.stata[0].expenditure=a[k].mo;p->info.stata[0].begintime[0]=a[k].bt[0];p->info.stata[0].begintime[1]=a[k].bt[1];p->info.stata[0].arrivetime[0]=a[k].at[0];p->info.stata[0].arrivetime[1]=a[k].at[1];p->st=0;p->nextarc=vertices[i].trainfirstarc;vertices[i].trainfirstarc=p;arc_num++;}k++;}trainarcnum=arc_num;}template<class T>int Graph<T>::save(){int i,j,k,t;ArcNode *q;FILE *fp;j=0;while(j<vexnum){strcpy(city[j],vertices[j].cityname);j++;}i=0;if((fp=fopen("city.txt","wb"))==NULL)cout<<"无法打开文件!"<<endl;while(i<vexnum){fprintf(fp,"%10s",city[i]);i++;}fclose(fp);k=0;for(i=0; i<vexnum; i++){q=vertices[i].planefirstarc;while(q!=NULL){for(t=0; t<=q->st; t++){strcpy(a[k].vt,vertices[i].cityname);strcpy(a[k].vh,vertices[q->adjvex].cityname);strcpy(a[k].co,q->info.stata[t].number);a[k].mo=q->info.stata[t].expenditure;a[k].bt[0]=q->info.stata[t].begintime[0];a[k].bt[1]=q->info.stata[t].begintime[1];a[k].at[0]=q->info.stata[t].arrivetime[0];a[k].at[1]=q->info.stata[t].arrivetime[1];k++;}q=q->nextarc;}}if((fp=fopen("plane.txt","wb"))==NULL){cout<<"无法打开文件!"<<endl;return 0;}i=0;fprintf(fp,"%d",k);while(i<k){if(fwrite(&a[i],sizeof(struct arc),1,fp)!=1)cout<<"文件写入错误!"<<endl;i++;}fclose(fp);k=0;for(i=0; i<vexnum; i++){q=vertices[i].trainfirstarc;while(q!=NULL){for(t=0; t<=q->st; t++){strcpy(a[k].vt,vertices[i].cityname);strcpy(a[k].vh,vertices[q->adjvex].cityname);strcpy(a[k].co,q->info.stata[t].number);a[k].mo=q->info.stata[t].expenditure;a[k].bt[0]=q->info.stata[t].begintime[0];a[k].bt[1]=q->info.stata[t].begintime[1];a[k].at[0]=q->info.stata[t].arrivetime[0];a[k].at[1]=q->info.stata[t].arrivetime[1];k++;}q=q->nextarc;}if((fp=fopen("train.txt","wb"))==NULL){cout<<"无法打开文件!"<<endl;return 0;}i=0;fprintf(fp,"%d",k);while(i<k){if(fwrite(&a[i],sizeof(struct arc),1,fp)!=1)cout<<"文件写入错误!"<<endl;i++;}fclose(fp);return 1;}template<class T>void Graph<T>::cityedit(){system("cls");int i;cout<<"您想（1=增加城市，2=删除城市）:";cin>>i;getchar();if(i==1)EnterVertex();if(i==2)DeleteVertex();getchar();}template<class T>void Graph<T>::EnterVertex(){char v[10],c;int i;cout<<"请输入新增城市的名称:";gets(v);i=LocateVertex(v);if(i>=0&&i<vexnum){cout<<"此城市已存在，不能新增了。

【交通运输】交通图咨询查询系统数据结构C语言xxxx年xx月xx日xxxxxxxx集团企业有限公司Please enter your company's name and contentv信息科学与工程学院《结构数据》课程设计报告课程设计名称：交通咨询系统专业班级：计算机xxx学生姓名：xxx学号：2015xxxx指导教师：xx课程设计时间：2016.07.04—2016.07.08计算机应用技术专业课程设计任务书说明：本表由指导教师填写，由教研室主任审核后下达给选题学生，装订在设计（论文）首页填表说明1．“课题性质”一栏：A．工程设计；B．工程技术研究；C．软件工程（如CAI课题等）；D．文献型综述；E．其它。

2．“课题来源”一栏：A．自然科学基金与部、省、市级以上科研课题；B．企、事业单位委托课题；C．校、院（系、部）级基金课题；D．自拟课题。

目录1 需求分析 (1)1.1 添加交通图信息 (1)1.2 查询单源最短路径 (1)1.3 查询多源最短路径 (1)1.4 更新交通图信息 (2)1.6 读取、保存信息 (2)2 概要设计 (3)2.1 数据类型的定义 (3)2.2 功能模块结构图 (4)3 运行环境 (6)4 开发工具和编程语言 (6)5 详细设计 (7)5.1 图结构的基本操作 (7)5.1.1添加城市结点和路径结点 (8)5.1.2修改城市结点和路径结点 (8)5.1.3删除城市结点和路径结点 (8)5.1.4退出保存 (8)5.2 迪杰斯特拉算法的实现 (8)5.2.1 迪杰斯特拉算法函数 (8)5.2.2 提取迪杰斯特拉函数信息 (8)5.2.3 求多源最短路径 (8)6 程序编码 (9)7 运行结果 (41)8 心得体会 (46)9参考文献 (47)1需求分析本系统中的数据来源于标准输入设备（如键盘）和文件，可以实现对交通图城市、城市到其余城市的距离的操作，根据需要可查询某两个城市之间的最短距离、城市到各城市的最短距离，各个城市到各个城市的最短距离，以及路径。

数据结构课程设计交通咨询系统设计学生姓名：学号：指导教师：完成日期：目录1 设计任务书 (1)1.1 题目与要求 (1)1.2 知识点 (1)1.3 输入输出分析 (1)1.4 实现的功能 (1)2 概要设计 (2)2.1 结构体类型及函数声明 (2)2.2 主程序流程 (2)3 详细设计 (3)3.1 数据类型实现 (3)3.2 程序代码 (3)4 调试分析 (11)4.1 问题分析与回顾 (11)4.2 算法时空分析 (11)4.3 算法改进 (11)4.4 经验和体会 (12)5 测试结果 (12)参考文献 (13)1 设计任务书1.1 题目与要求题目：编写程序实现交通咨询系统设计的模拟。

要求：（1）建立交通网络网的存储结构；（2）总体设计要画流程图；（3）提供程序测试方案；（4）界面友好。

1.2 知识点本次课程设计应用到了图的创建、邻接矩阵、迪杰斯特拉算法、弗洛伊德算法、结构体、宏定义、自定义类型、函数的声明与调用等知识点。

1.3 输入输出分析（1）普通输入对于图的存储，我采用的是邻接矩阵的方法，借助于邻接矩阵容易判定任意两个顶点之间是否有弧相连，也容易求得各段弧的权值。

（2）对话式输入在用户选择系统功能时，我采用的是对话式输入，让用户输入系统功能的代号，利用switch语句判断用户输入的指令并调用相应的函数实现具体功能。

（3）程序输出对于用户查询结果的展示，考虑美观以及方便用户的因素，我写了一个pri()函数输出各个城市的代码城市名字对照表，用户可以更方便的使用。

对于用户查询一个城市到所有城市的最短路径时，考虑到显示结果较多，我采用表格的形式进行显示，使界面更美观。

1.4 实现的功能在交通网络越来越发达的今天，人们出去旅行、出差更多的会考虑选择最短路径或最小花费等问题，因此我设计了一个交通咨询系统。

这个系统可以根据用户的选择实现3种功能：求一个城市到所有城市的最短路径；求两个城市间的最短路径；求两个城市间的最小花费。

数据结构--交通咨询系统数据结构--交通咨询系统一、引言交通咨询系统是为了方便用户获取交通相关信息而设计的一种软件系统。

本文档旨在说明交通咨询系统的设计和实现细节，包括系统的功能需求、系统架构、核心算法以及数据结构的选择等方面内容。

二、功能需求1、用户注册与登录功能a：用户可以通过注册功能创建账户；b：用户可以通过登录功能进行身份验证。

2、交通信息查询功能a：用户可以根据起点和终点查询交通路线；b：用户可以查询公交、地铁、火车、飞机等交通工具的时刻表；c：用户可以查询附近交通站点或机场、车站的详细信息。

3、交通信息推荐功能a：根据用户的历史查询记录和个人偏好，系统可以推荐适合的交通方案；b：根据用户的位置信息，系统可以推荐附近的交通站点或机场、车站。

4、系统设置功能a：用户可以选择系统界面的主题风格；b：用户可以设置提醒功能，以接收相关交通信息的通知。

三、系统架构1、前端设计a：用户界面设计：包括登录、注册、查询、推荐、设置等功能的界面设计；b：用户交互设计：实现用户与系统之间的信息交互。

2、后端实现a：数据库设计：设计用户、交通路线、交通工具、交通站点等相关数据表；b：服务器端设计：负责处理用户请求、数据存储和计算等任务；c：算法设计：设计合适的算法用于交通信息查询和推荐。

四、核心算法1、最短路径算法a：使用Dijkstra算法计算起点到终点的最短路径；b：考虑交通工具的运行时间、换乘时间等因素。

2、推荐算法a：使用协同过滤算法根据用户的历史查询记录和个人偏好进行交通方案推荐；b：使用基于位置的推荐算法根据用户的位置信息推荐附近的交通站点或机场、车站。

五、数据结构选择1、图结构a：使用图结构来表示交通路线和交通站点之间的关系；b：利用图的搜索算法来实现最短路径算法。

2、队列和栈a：使用队列和栈来处理用户的查询请求和系统的任务调度。

六、附件本文档涉及的附件包括系统的界面原型设计图、数据库设计文档、算法设计文档等。

2数据结构——全国交通咨询模拟系统实验报告
实验目的：
实验环境：
本次实验的开发环境为Java编程语言，使用了面向对象的编程思想，采用了数据结构中的图和链表等数据结构。

实验内容：
1.设计交通工具类：
首先，根据系统需求，设计了交通工具类，该类用于表示交通工具的
基本信息，包括交通工具的名称、班次、票价等。

在该类中，使用了链表
数据结构来存储交通工具的班次信息。

2.设计城市类：
接下来，设计了城市类，用于表示各个城市的交通信息。

在该类中，
使用了图数据结构来表示城市之间的联通关系，每个城市作为图的一个节点，城市间的交通工具作为图的边。

实验结果：
经过测试，实验系统能够准确地输出起点城市到终点城市的最短路径
和最佳交通方案，用户可以根据输出信息来决定如何安排旅行计划。

实验总结：。