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

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

2、实型数据；输入列车或飞机开始时间和到达时间时均需输入两个整型数据(以hh：mm的形式)；在选择功能时，应输入与所选功能对应的一个整型数据。(2) 程序的输出信息主要是：最快需要多少时间才能到达，或最少需要多少旅费才能到达，或最少需要多少次中转到达，并详细说明依次于何时乘坐哪一趟列车或哪一次班机到何地。(3) 程序的功能包括：提供对城市信息的编辑，提供列车时刻表和飞机航班表 的编辑，提供三种最优决策：最快到达、最省钱到达、最少中转次数到达。四概要设计系统用到的抽象数据类型定义：1 ADT Graph数据对象V: 个集合，该集合中的所有元素具有相同的特性 数据关系R： R=VRVR=<x,y

3、>|P(x,y)A(x,y属于 V)基本操作：(1)in itgraph(&G)；(2)CreateGraph(&G)；(3)En terVertex(&G)；(4)DeleteVertex(&G)；(5)En terpla neArc(&G)；(6)Deletepla nArc(&G)；(7)En tertrai nArc(&G)；(8)DeletetrainArc(&G);ADT Graph2 . ADT LinkQueue数据元素：可以是任意类型的数据，但必须属于同一个数据对象 关系：队列中数据元素之间是线性关系。基本

4、操作：(1)Ini tQueue(&Q);(2)IsEmpty(&Q);(3)EnterQueue(&Q,x);(4)DeleteQueue(&Q,&y);ADT Lin kQueue3 . ADT TimeTree数据对象D: 个集合，该集合中的所有元素具有相同的特性数据关系R：若D为空，则为空树。若 D中仅含有一个数据元素，则R为空集，否则R=H, H为如下二元关系：(1) 在D中存在唯一的称为根的数据元素root ,它在关系H中没有前驱(2) 除root以外，D中每个结点在关系H下有且仅有一个前驱。基本操作：(1) CreateTimeTree(p

5、,i,j，&Q,i nfolist arcs);(2) CopyTimeTree(p,q);(3) VisitTimeTree(p);ADT TimeTree系统中子程序及功能要求: 1.Administer(ALGraph *G)2.3.4.5.6.:提供管理员管理城市交通系统的界面，通过该子程 序可调用其他管理交通系统的子程序。:初始化交通系统的子程序in itgraph(ALGraph *G):创建城市文件的子程序:创建航班文件的子程序:创建列车时刻表文件的子程序:提供城市名在城市交通系统中相应的编 号createcityfile() createpla nefile() cre

6、atetra in file() LocateVertex(ALGraph *G,char *v)9. EnterVertex(ALGraph *G):10. DeleteVertex(ALGraph *G)11. flightedit(ALGraph *G):12. EnterplaneArc(ALGraph *G)13. DeleteplaneArc(ALGraph *G)7. CreateGraph(ALGraph *G):创建城市交通系统8. cityedit(ALGraph *G):提供城市编辑功能 提供在城市交通系统中加入城市的功能:提供在城市交通系统中删除城市的功 能提供航班编辑

7、功能:提供在城市交通系统中加入航班的功 能:提供在城市交通系统中删除航班的功能14： trainedit(ALGraph *G):提供列车车次的编辑功能15. EntertrainArc(ALGraph *G):提供在城市交通系统中加入列车车次的功能16. DeletetrainArc(ALGraph *G):提供在城市交通系统中删除列车车次的功能17. UserDemand(ALGraph G):提供用户咨询的界面18. DemandDispose(int n,ALGraph G):通过该子程序调用其他咨询子程序19. InitQueue(LinkQueue 创建交通图算法的伪码描述如下：i

8、nt LocateVertex(ALGaph *G ,char *v)/* 找出城市名在图中对应结 点位置*/for(k=0;kv 图 G 中的结点个数 G->vexnum;k+)Q):初始化队列20. EnterQueue(LinkQueue *Q,int x) :入队操作21. DeleteQueue(LinkQueue *Q,int *x):出队操作22. IsEmpty(LinkQueue *Q):队列判空操作23. TransferDispose(int k,infolist(*arcs)MAX_VERTEX_NUM, (*arcs)MAX_VERTEX_NUM ,ALGrap

9、h G,ALGraph G,i nt v0,i nt v1) :提供最少中转次数决策的功能24 . MinExpenditure(infolist arcs,float *expenditure,float *route) :提供两个城市之间最少费用的功能25 . ExpenditureDispose(int k, infolist (*arcs)MAX_VERTEX_NUM,ALGraph G, i nt v0,i nt v1,float *D,i nt *fin al):提供最少费用决策的功能26 . MinTime(infolist arcs,float *time,float *rou

10、te):提供两个城市之间最短时间的功能27 . TimeTreeDispose(Node *head,infolist(*arcs)MAX_VERTEX_NUM):提供两个之间相隔一个以上城市的城市间的最短时间的功能28 . CreateTimeTree(TimeTree p,int i,int j,Lin kQueue *Q,i nfolist(*arcs)MAX_VERTEX_NUM):创建时间树29 . CopyTimeTree(TimeTree p,TimeTree q):复制时间树30 . VisitTimeTree(TimeTree p):访问时间树31 . DestoryTime

11、Tree(TimeTree p) :销毁时间树32 . TimeDispose(i nt k,i nfolist (*arcs)MAX_VERTEX_NUM,ALGraphG,i nt v0,i nt v1,float *D,i nt *fin al):提供最少时间决策的功能33 : PrintGraph(ALGraph *G):显示整个城市交通系统主函数可调用子程序 1,17,33子程序1可调用子程序2, 8,11,14子程序2可调用子程序3, 4,5,7子程序7, 12, 13, 15,16可调用子程序子程序8可调用子程序9, 10子程序11可调用子程序12,13子程序14可调用子程序15

12、,16子程序17可调用子程序18子程序18可调用子程序23,25,32子程序23可调用子程序19,29,21, 22子程序25可调用子程序24子程序32可调用子程序26,27子程序27可调用子程序28,30,31子程序28可调用子程序29* 各程序模块之间的调用关系(子程序编号见上)6五.详细设计if（第k个结点中的城市名与传过来的城市名相同）j=k;/* 记录位置 */break; 返回 k 的数值；int CreatGraph（ALGraph *G）if（打开城市文件，文件指针返回值为空）输出错误文件信息；程序返回值为 0；while（文件不为空）将文件指针所指的字符串读到城市名数组cit

13、yi中；i+;关闭文件；j=0;while（j< 城市个数）将 cityi 中的内容复制到图的结构体的结点数组中 ;图的结构体其他项负初值 ;j+;G->vexnum=i;打开航班信息文件 "plane.txt"将文件中的内容以块为单位读到缓冲区数组 a 中； 关闭文件； a 的计数变量 k=0;弧的计数变量 arc_num=0;while（k< 信息个数 ）调用函数 LocateVertex（G,ak.vt） 得到起始结点的位置i；调用函数 LocateVertex（G,ak.vt） 得到起始结点的位置j；q=G->verticesi.planfi

14、rstarc;m=0;while（q!=NULL）if（弧q中的邻接顶点与j相等）将数组 ai 中的内容都复制到弧 q 中；m=1;break;q=q->nextarc;if(m=O);开辟一个弧结点；将数组ai中的内容都复制到新的弧结点中；将弧结点连接到适当的位置中去；arc_num+; _k+;G->planarcnum=arc_num;打开列车信息文件"plane.txt"将文件中的内容以块为单位读到缓冲区数组a中；关闭文件；a的计数变量k=0;弧的计数变量 arc_num=0;while(kv信息个数)调用函数 LocateVertex(G,ak.vt)

15、得到起始结点的位置 i ； 调用函数 LocateVertex(G,ak.vt)得到起始结点的位置 j ； q=G->verticesi.trainfirstarc;m=0;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)/*f

16、lag 为标志位，初值为 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（航班文件不能以读写形式打开）提示“无法打开

17、文件”；将计数值count写入航班车文件；for（i=O;ivcount;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的存储城市名与 v不同） /*G表头结点总个数比实际大1*

18、/记数值n+1;if（n =图G表头结点总个数）提示“无法找到此城市“；elsei=LocateVertex（G ,v）;/*利用G函数找到此城市名所处在G中位置*/删除从此结点出发的所有航班弧；删除从此结点出发的所有列车弧；for（j=i;jv图G表头结点总个数-1 ； j+）将G第j个结点的信息依前移1位；将G第j个结点的信息制空；/*以下是删除所有指向此结点的航班弧*/for（k=O;kv图G表头记点总个数-1 ； k+）p指向图G中k结点的第一条飞机弧；while （ p ！ =NULL ） if （该弧指向的顶点位置（p-adjvex ）i）将该弧指向顶点位置-1 ；q=p ；p指向

19、下一条飞机弧;else if (该弧指向的顶点位置( p->adjvex ) = = i) if (p指向图G中k结点的第一条飞机弧) m=p ；将图 G 中 k 结点的第二条飞机弧改为第一弧； p 指向下一条飞机弧；释放( m)；else将p的下一条弧赋给 q的下一条弧； m=p；p 指向下一条飞机弧； 释放( q)；elseq=p；p 指向下一条飞机弧；/*以下是删除所有指向此结点的列车弧 */ for(k=0;k< 图 G 表头记点总个数 -1； k+)p指向图G中k结点的第一条列车弧；while( p！=NULL ) if (该弧指向的顶点位置(p->adjvex )

20、>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 )；elseq=p；p 指向下一条列车弧；图 G 表头结点总个数 -1； else return；求城市vO, v1之间的最少费用算法的伪码描述如下：Expe nditureDispose()for(v=0 ；

21、v<城市个数；v+) 城市v还未求得最少费用；*(D+v)= 城市vO到v的最少费用；将城市v的路径设置为空；if(最少中转次数算法的伪码描述如下：求城市V0到城市v1的最少中转次数TransferDispose()for(v=0 ； wG.vexnum ； v+)城市v设为未访问； 城市v的路径设为空；将城市V0设为已访问；将城市V0入队；(D+v)<INFINITY)将城市v0和v加入到城市v的路径中；城市v0到城市v0的最少费用为0；城市v0设为已求得最少费用；for(i=1； i< 城市个数；v+)m=INFINITY;for(w=0； w<城市个数；w+)if

22、(城市w未求得最少费用)if(*(D+w)<m)v=w;m=*(D+w);if(v 等于 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 ；while（队列不空）队首城市v出队

23、；w为与城市v相连的第一个城市；while（w 存在）if（城市w未访问）将城市w设为已访问； 将城市w的路径改为城市 v的路径并在最后加入城市w；if（w 等于 v1）根据城市w的路径输出从城市 v0到城市v1所需经过的城市及路线; 返回；将城市w入队；w等于城市v相连的下一个城市；输出没有列车或飞机从城市v0到v1 ； 求城市v0，v1之间的最少时间算法的伪码描述如下：TimeDispose（） for（v=0 ； v城市个数；v+）城市v还未求得最少时间； *（D+v）=城市v0到v的最少时间； 将城市v的路径设置为空； if（*（D+v）vlNFINITY）将城市v0和v加入到城市v的

24、路径中；城市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 等于 v1）根据城市v的路径输出从城市 v0到城市v1所需经过的城市及路线; 输出最少时间v1； 返回；else将城市v设为已求得最少时间；for（w=0 ； vG.vexnum ； w+）if（城市w未求得最少时间并且从城市v到w有路径）保存城市w原来的路径； 将城市w的路径设为城市 v的路径并在最后加入城市 w； 利用时间树求出从

25、城市 v0城市w的最少时间及路径； if（*（D+w）从城市v0到城市 w的最少时间）*(D+w)= 从城市 v0 到城市 w 的最少时间； else将城市 w 的路径还原；输出没有列车或飞机从城市 v0 到 v1；六测试分析按照附录中的测试数据，得出如下测试、分析结果：1. 操作员管理功能 .1>. 当我们从键盘输入有关图的顶点及弧的信息后 ,用显示图的函数验证 ,DOS 中显示的 图的信息与从键盘输入的信息相同 ,表明交通系统可以从键盘正确输入信息 .2>. 我们事先建立了有关图的 3 个文本文件 ( 包括 city.txt,plan.txt,train.txt), 在交通系统

26、 程序中 ,选择从文本文件输入图的信息后,用显示操作验证 , 表明文本文件的内容可以正确调入图的结构体中 ,说明交通系统可以从文本文件中读取信息.3>. 当从键盘或文本文件初始化交通图后,测试增加或删除城市结点 ,增加或删除航班或列车弧 ,以上各功能都正确 .2. 交通咨询功能 .1>. 火车情况 .1.1>.最少费用 .a. 两地间无中转且有多辆火车 .北京 郑州输出结果为 :旅行路线是 :乘坐 NO.27 列车车次在 13： 15 从 Beijing 到 zhengzhou. 最少旅行费用是 78 元 .而若选择 NO.41 则花费为 80 元 .结果正确 .b. 两地之

27、间无中转达且只有一辆火车 .西安 武汉输出结果为 :旅行路线是 :乘坐NO.218列车车次在 1: 34从xi ' a到 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

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

29、 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. 两地可直达且有中转 .昆明 - 广州 输出结果为 : 旅行路线是 :乘坐 NO.323 列车车次在

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

31、输出结果为 : 不存在飞机航班从 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>两地可中转 .广州

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

33、hou 到 xi ' an. 乘坐NO.210飞机航班在12: 35从xi ' a到beijing.最少旅行中转次数是 1 次. 结果正确 .3. 打印打印结果正确 ;4. 退出能正确退出七使用说明1 运行程序，首先出现主界面。主界面包括四个选项：选项一：管理员管理界面，选择该项可进行城市交通系统的管理，具体使用说明见说明2;选项二：用户咨询界面，选择该项可进行最少费用、最少时间、最少中转次数的决策咨询，具体 使用见说明7;选项三：显示城市交通系统程序，选择该项可显示城市交通系统 的所有信息，包括城市、航班和列车车次；选项四：退出程序，选择该项将退出 程序。2 管理员管理界面包

34、括 5个选项：选项一：初始化城市交通系统界面，可进行城市交通系统的初始化，具体使用见说明3;选项二：城市编辑界面，可进行城市的增加和删除，具体使用见说明4;选项三：航班编辑界面，可进行航班的增加和删除，具体使用见说明5;选项四：列车车次编辑界面，可进行列车车次的增加和删除，具体使用见说明 6;选项五：返回上一级菜单，可返回主界面。3 .初始化城市交通系统界面包括两个选项：选项一：通过键盘初始化城市交通系统，选择该项后程序将给出输入说明，按输入说明用户需逐 步输入城市、航班、列车车次的信息来对城市交通系统初始化。在输入航班和 列车信息时需注意两点：a.所输入的航班和列车的发车时间均在同一天。b.

35、若发车时间小于到达时间，则说明列车在同一天到达，若发车时间大于到达时间， 则说明列车在次日达到。飞机航班也是如此；选项二：通过文档初始化城市交 通系统，选择该项可用文档进行初始化，但文档必须存在于程序的同一目录下， 且必须包含 CITY, PLANE TRAIN三个文本文档，否则程序将提示出错。4 城市编辑界面包括两个选项：选项一：增加城市，可在城市交通系统中加入新的城市，若用户输入的是已有的城市名，程序将提示出错；选项二：删除城市，可 在城市交通系统中删除城市，用户必须输入一个已有的城市名，否则程序提示出 错。5 航班编辑界面包括两个选项：选项一：增加航班，可在两个城市之间新增航班，选择该项后用户需输入新增航班的编号，起始城市，到达城市及费用、时间等信息；选项二，删除航班，可删除两个城