《数据结构》课程设计参考样例

1、数据结构课程设计参考样例源程序下载题目：全国交通咨询 一设计目的通过实习，了解并初步掌握设计、实现较大系统的完整过程，包括系统分析、编码设计、系统集成、以及调试分析，熟练掌握数据结构的选择、设计、实现以及操作方法，为进一步的应用开发打好基础。二问题描述设计、实现一个全国大城市间的交通咨询程序，为旅客提供三种最优决策方案：（1）时间最短（2）费用最小（3）中转次数最少。三需求分析 该程序所做的工作的是模拟全国交通咨询，为旅客提供三种最优决策的交通咨询。此程序规定：（1）       在程序中输入城市名称时，需输入10个字母以内的字母串；

2、输入列车或飞机编号时需输入一个整型数据；输入列车或飞机的费用时需输入一个实型数据；输入列车或飞机开始时间和到达时间时均需输入两个整型数据（以hh：mm的形式）；在选择功能时，应输入与所选功能对应的一个整型数据。（2）      程序的输出信息主要是：最快需要多少时间才能到达，或最少需要多少旅费才能到达，或最少需要多少次中转到达，并详细说明依次于何时乘坐哪一趟列车或哪一次班机到何地。（3）      程序的功能包括：提供对城市信息的编辑，提供列车时刻表和飞机航班表的编辑，提供三种最优决策：最快到达

3、、最省钱到达、最少中转次数到达。 四概要设计·         系统用到的抽象数据类型定义：1ADT Graph 数据对象V：一个集合，该集合中的所有元素具有相同的特性 数据关系R：R=VR VR=<x,y>|P(x,y)(x,y属于V) 基本操作：（1）       initgraph(&G)；（2）       CreateGraph(&G)；（3）

4、60;      EnterVertex(&G)；（4）       DeleteVertex(&G)；（5）       EnterplaneArc(&G)；（6）       DeleteplanArc(&G)；（7）       EntertrainArc(&G)

5、；（8）       DeletetrainArc(&G)；ADT Graph 2ADT LinkQueue 数据元素：可以是任意类型的数据，但必须属于同一个数据对象 关系：队列中数据元素之间是线性关系。 基本操作：（1）       InitQueue(&Q)；（2）       IsEmpty(&Q)；（3）       Ente

6、rQueue(&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）      

7、; CreateTimeTree(p,i,j,&Q,infolist arcs)；（2）       CopyTimeTree(p,q)；（3）       VisitTimeTree(p)；ADT TimeTree·         系统中子程序及功能要求：1Administer(ALGraph *G)：提供管理员管理城市交通系统的界面，通过该子程序可调用其他管理交通系统的子程

8、序。2initgraph(ALGraph *G)：初始化交通系统的子程序3createcityfile( )：创建城市文件的子程序4createplanefile( )：创建航班文件的子程序5createtrainfile( )：创建列车时刻表文件的子程序6LocateVertex(ALGraph *G,char *v)：提供城市名在城市交通系统中相应的编号7CreateGraph(ALGraph *G)：创建城市交通系统8cityedit(ALGraph *G)：提供城市编辑功能9EnterVertex(ALGraph *G)：提供在城市交通系统中加入城市的功能10DeleteVertex(

9、ALGraph *G)：提供在城市交通系统中删除城市的功 能11flightedit(ALGraph *G)：提供航班编辑功能12EnterplaneArc(ALGraph *G)：提供在城市交通系统中加入航班的功 能13DeleteplaneArc(ALGraph *G)：提供在城市交通系统中删除航班的 功能14：trainedit(ALGraph *G):提供列车车次的编辑功能15EntertrainArc(ALGraph *G)：提供在城市交通系统中加入列车车次 的功能16DeletetrainArc(ALGraph *G)：提供在城市交通系统中删除列车车 次的功能17UserDeman

10、d(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,ALGrap

11、h 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) ：提供两个城市之间最短时间的功能 27T

12、imeTreeDispose(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)：销毁时间树 32TimeDispo

13、se(int k,infolist (*arcs)MAX_VERTEX_NUM,ALGraphG,int v0,int v1,float *D,int *final) ：提供最少时间决策的功能 33：PrintGraph(ALGraph *G)：显示整个城市交通系统 ·         各程序模块之间的调用关系（子程序编号见上）： 主函数可调用子程序1，17，33 子程序1可调用子程序2，8，11，14 子程序2可调用子程序3，4，5，7 子程序7，12，13，15，16可调用子程序6 子程序8可调用子程

14、序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五详细设计·         创建交通图算法的伪码描述如下： int LocateVertex(ALGaph *G,char *v)/*找出城市名在图中对应结 点位置*/ for(k=0;

15、k<图G中的结点个数G->vexnum;k+) if(第k个结点中的城市名与传过来的城市名相同) j=k;/*记录位置*/ break; 返回k 的数值；int CreatGraph(ALGraph *G) if(打开城市文件，文件指针返回值为空） 输出错误文件信息； 程序返回值为0； while(文件不为空） 将文件指针所指的字符串读到城市名数组 cityi中； i+; 关闭文件； j=0; while(j<城市个数） 将 cityi 中的内容复制到图的结构体的结点数组中; 图的结构体其他项负初值; j+; G->vexnum=i; 打开航班信息文件"pla

16、ne.txt" 将文件中的内容以块为单位读到缓冲区数组a中； 关闭文件； a的计数变量k=0; 弧的计数变量 arc_num=0; while(k<信息个数) 调用函数 LocateVertex(G,ak.vt)得到起始结点的位置 i； 调用函数 LocateVertex(G,ak.vt)得到起始结点的位置 j； q=G->verticesi.planfirstarc; m=0; while(q!=NULL) if( 弧 q中的邻接顶点与j相等） 将数组ai 中的内容都复制到弧q中； m=1; break; q=q->nextarc; if(m=0); 开辟一个弧结

17、点； 将数组ai中的内容都复制到新的弧结点中； 将弧结点连接到适当的位置中去； arc_num+; k+; G->planarcnum=arc_num; 打开列车信息文件"plane.txt" 将文件中的内容以块为单位读到缓冲区数组a中； 关闭文件； a的计数变量k=0; 弧的计数变量 arc_num=0; while(k<信息个数) 调用函数 LocateVertex(G,ak.vt)得到起始结点的位置 i； 调用函数 LocateVertex(G,ak.vt)得到起始结点的位置 j； q=G->verticesi.trainfirstarc; m=0;

18、 while(q!=NULL) if( 弧 q中的邻接顶点与j相等） 将数组ai 中的内容都复制到弧q中； m=1; break; q=q->nextarc; if(m=0); 开辟一个弧结点； 将数组ai中的内容都复制到新的弧结点中； 将弧结点连接到适当的位置中去； arc_num+; k+; G->trainarcnum=arc_num;返回；·         创建航班算法的伪码描述如下： creatplanefile() while(flag) /*flag为标志位,初值为1*/ 提示

19、“输入航班信息”；输入航班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(航班文件不能以读写形式打开)提示“无法打开文件”；将计数值count写入航班车文件

20、；for(i=0;i<count;i+) if(无法将ai写入航班文件) 提示“文件无法写入”；关闭航班文件；·         删除城市结点算法的伪码描述如下： DeleteVertex(ALGraph *G) /* G是程序头部定义的结构体*/ 提示“输入删除城市名”； gets(城市名：v); 提示“是否确定要删除（Y/N）“； c=getchar(); if(c=Y|c=y) n=0; /*0是记数标志，控制循环次数*/while(n<图G表头接点总个数&&图G的存储城

21、市名与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;k<图G表头记点总个数-1；k+)p指向图G中k结点的第一条飞机弧； while（p！=NULL） if（该弧指向的顶点位置（p->a

22、djvex ）>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;k<图G表头记点总个数-1；k+)p指向图G中k结点的第一条列车弧； while（p！=NULL） if（该弧指

23、向的顶点位置（p->adjvex ）>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； ·       

24、60; 求城市v0，v1之间的最少费用算法的伪码描述如下： ExpenditureDispose( )for(v=0；v<城市个数；v+) 城市v还未求得最少费用； *(D+v)=城市v0到v的最少费用； 将城市v的路径设置为空； if(*(D+v)<INFINITY) 将城市v0和v加入到城市v的路径中； 城市v0到城市v0的最少费用为0； 城市v0设为已求得最少费用； for(i=1；i<城市个数；v+) m=INFINITY; for(w=0；w<城市个数；w+) if(城市w未求得最少费用) if(*(D+w)<m) v=w; m=*(D+w); if(v

25、等于v1)根据城市v的路径输出从城市v0到城市v1所需经过的城市及路线； 输出最少费用*(D+v1)； 返回；else将城市v设为已求得最少费用； for(w=0；<G.vexnum；w+) if(城市w未求得最少费用并且从城市v到w有路径) 求出从城市v到城市w的最少费用及路线； if(*(D+w)>m+城市v到w的最少费用) *(D+w)=m+城市v到w的最少费用； 将城市w的路径改成城市v的路径并在最后加入城市w； 输出没有列车或飞机从城市v0到v1； ·         最少中转次数算

26、法的伪码描述如下：求城市v0到城市v1的最少中转次数TransferDispose( )for(v=0；v<G.vexnum；v+) 城市v设为未访问； 城市v的路径设为空； 将城市v0设为已访问； 将城市v0入队； while(队列不空) 队首城市v出队； w为与城市v相连的第一个城市； while(w存在) if(城市w未访问)将城市w设为已访问； 将城市w的路径改为城市v的路径并在最后加入城市w； if(w等于v1) 根据城市w的路径输出从城市v0到城市v1所需经过的城市及路线； 返回； 将城市w入队； w等于城市v相连的下一个城市； 输出没有列车或飞机从城市v0到v1； 

27、3;         求城市v0，v1之间的最少时间算法的伪码描述如下： TimeDispose( )for(v=0；v<城市个数；v+) 城市v还未求得最少时间； *(D+v)=城市v0到v的最少时间； 将城市v的路径设置为空； if(*(D+v)<INFINITY) 将城市v0和v加入到城市v的路径中； 城市v0到城市v0的最少时间为0； 城市v0设为已求得最少时间； for(i=1；i<城市个数；v+) m=INFINITY; for(w=0；w<城市个数；w+) if(城市w未求得最

28、少时间) if(*(D+w)<m) v=w; m=*(D+w); if(v等于v1)根据城市v的路径输出从城市v0到城市v1所需经过的城市及路线； 输出最少时间v1； 返回；else将城市v设为已求得最少时间； for(w=0；<G.vexnum；w+) if(城市w未求得最少时间并且从城市v到w有路径) 保存城市w原来的路径；将城市w的路径设为城市v的路径并在最后加入城市w； 利用时间树求出从城市v0城市w的最少时间及路径； if(*(D+w)>从城市v0到城市w的最少时间) *(D+w)=从城市v0到城市w的最少时间； else 将城市w的路径还原； 输出没有列车或飞机从

29、城市v0到v1； 六测试分析 按照附录中的测试数据，得出如下测试、分析结果：1.       操作员管理功能.1>. 当我们从键盘输入有关图的顶点及弧的信息后,用显示图的函数验证,DOS中显示的图的信息与从键盘输入的信息相同,表明交通系统可以从键盘正确输入信息.2>. 我们事先建立了有关图的3 个文本文件(包括city.txt,plan.txt,train.txt),在交通系统程序中,选择从文本文件输入图的信息后,用显示操作验证,表明文本文件的内容可以正确调入图的结构体中,说明交通系统可以从文本文件中读取信息.3>.

30、 当从键盘或文本文件初始化交通图后,测试增加或删除城市结点,增加或删除航班或列车弧,以上各功能都正确.2. 交通咨询功能. 1>. 火车情况. 1.1>.最少费用.a.       两地间无中转且有多辆火车.北京-à郑州输出结果为:旅行路线是: 乘坐NO.27列车车次在13：15 从 Beijing 到zhengzhou.最少旅行费用是78元. 而若选择NO.41 则花费为80 元. 结果正确.b.       两地之间无中转达且只有一辆火车.西安-&#

31、224;武汉输出结果为:旅行路线是: 乘坐NO.218列车车次在1：34从xian到wuhan. 最少旅行费用是178.00 元. 结果正确.c.       两地之间有中转.昆明-à北京输出结果为:旅行路线是: 乘坐NO.323列车车次在16.：31从kunming到Guangzhou. 乘坐NO.59列车车次在3：39从Guangzhou 到shanghai.乘坐NO.41列车车次在0：35从shanghai 到zhengzhou.乘坐NO.27列车车次在13：42 从zhengzhou 到Beijing.最少旅行费用是

32、462 元. 而若选择 昆明-à武汉-à兰州-à北京 则花费为506 元. 若选择 昆明-à武汉-à西安-à郑州-à北京 则花费为472 元.结果正确. 1.2>最短时间. a. 两地间无中转且有多辆火车.北京-à郑州输出结果为:旅行路线是: 乘坐NO.41列车车次在13：15从Beijing 到zhengzhou.最少旅行时间是7：57. 结果正确.b.两地之间无中转达且只有一辆火车.乌鲁木齐-à兰州 输出结果为:旅行路线是: 乘坐No.371列车车次在0：35从wulumuqi 到la

33、nzhou. 最少旅行时间是10：48. 结果正确.c.       两地之间有中转.广州-à兰州 输出结果为:旅行路线是: 乘坐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.结果正确. 1.3>.最短周转次数.a. 两地可直达且有中转.昆明-à广州

34、输出结果为:旅行路线是: 乘坐NO.323列车车次在16：31从kunming到guangzhou.最少旅行中转次数是0次 .而若选择 昆明-à武汉-à长沙-à兰州 则 结果为3.结果正确.b.两地间有多条中转路径.昆明-à上海输出结果为:旅行路线是: 乘坐NO.323列车车次在16：31从kunming 到guangzhou.乘坐NO.59列车车次在3：39从guangzhou 到shanghai.最少旅行总转次数是1次 .而若选择 昆明-à武汉-à西安-à郑州-à上海 则 结果为4.结果正确.2.飞机情况.2.

35、1>.两地无直达. 兰州-à武汉输出结果为: 不存在飞机航班从lanzhou到wuhan.2.2>.两地无直达.拉萨-à昆明a.最少费用: 输出结果为:乘坐NO.173飞机航班在10：20 从lasa 到kunming.最少旅行费用是830 元.结果正确.b.最短时间:输出结果为:乘坐NO.173 飞机航班在10：20 从lasa 到kunming.最少旅行时间是1：25.结果正确.c.最短中转次数.输出结果为:乘坐NO.173 飞机航班在10：20 从lasa 到kunming.最少旅行中转次数是0次.结果正确.2.3>两地可中转.广州-à北京

36、a.最少费用:输出结果为:乘坐NO.2323飞机航班在10：15 从Guangzhou 到xian.乘坐NO.210 飞机航班在12：35 从xian 到beijing.最少旅行费用是2250 元.结果正确.b.最短时间:输出结果为: 乘坐NO.2323 飞机航班在10：15 从Guangzhou 到xian.乘坐NO.210 飞机航班在12：35 从xian 到beijing.最少旅行时间是4：00.结果正确.c.最短中转次数.输出结果为:乘坐NO.2323 飞机航班在10：15 从Guangzhou 到xian.乘坐NO.210 飞机航班在12：35从xian 到beijing.最少旅行中

37、转次数是1次.结果正确.3.打印 打印结果正确;4.退出能正确退出七使用说明 1运行程序，首先出现主界面。主界面包括四个选项：选项一：管理员管理界面，选择该项可进行城市交通系统的管理，具体使用说明见说明2；选项二：用户咨询界面，选择该项可进行最少费用、最少时间、最少中转次数的决策咨询，具体使用见说明7；选项三：显示城市交通系统程序，选择该项可显示城市交通系统的所有信息，包括城市、航班和列车车次；选项四：退出程序，选择该项将退出程序。 2管理员管理界面包括5个选项：选项一：初始化城市交通系统界面，可进行城市交通系统的初始化，具体使用见说明3；选项二：城市编辑界面，可进行城市的增加和删除，具体使用

38、见说明4；选项三：航班编辑界面，可进行航班的增加和删除，具体使用见说明5；选项四：列车车次编辑界面，可进行列车车次的增加和删除，具体使用见说明6；选项五：返回上一级菜单，可返回主界面。 3初始化城市交通系统界面包括两个选项：选项一：通过键盘初始化城 市交通系统，选择该项后程序将给出输入说明，按输入说明用户需逐步输入城市、航班、列车车次的信息来对城市交通系统初始化。在输入航班和列车信息时需注意两点：a.所输入的航班和列车的发车时间均在同一天。b.若发车时间小于到达时间，则说明列车在同一天到达，若发车时间大于到达时间，则说明列车在次日达到。飞机航班也是如此；选项二：通过文档初始化城市交通系统，选择该项可用文档进行初始化，但文档必须存在于程序的同一目录下，且必须包含CITY，PLANE，TRAIN三个文本文档，否则程序将提示出错。 4城市编辑界面包括两个选项：选项一：增加城市，可在城市交通系统中加入新的城市，若用户输入的是已有的城市名，程序将提示出错；选项二：删除城市，可在城市交通系统中删除城市，用户必须输入一个已有的城市名，否则程序提示出错。 5航班编辑界面包括两个选项：选项一：增加航班，可在两个城市之间 新增航班，选择该项后用户需输入新增航班的编号，起始城市，到达城市及费用、时间等信息；选项二，删除航