平顶山工学院
《数据结构》课程设计任务书
班 级 0814091/2
专 业计算机科学与技术
课程名称 数据结构
指导教师张延红、魏新红、杨斌
计算机科学与工程系
20##年2月
《数据结构》课程设计任务书
编写： 审核：
一、设计时间及地点
1、设计时间：第1周
2、设计地点：计算机系机房205、206
二、设计目的和要求
数据结构课程设计是在学完数据结构课程之后的实践教学环节。该实践教学是软件设计的综合训练，包括问题分析、总体结构设计、用户界面设计、程序设计基本技能和技巧。要求学生在设计中逐步提高程序设计能力，培养科学的软件工作方法。学生通过数据结构课程设计在下述各方面得到锻炼：
1、能根据实际问题的具体情况，结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法。
2、提高程序设计和调试能力。学生通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。
3、培养算法分析能力。分析所设计算法的时间复杂度和空间复杂度，进一步提高程序设计水平。
学生认真主动完成课程设计的要求，发挥自主学习的能力，充分利用时间，安排好课程设计，并在课程设计过程中不断检测自己的计划完成情况，及时向教师汇报。
三、设计题目和内容
1、运动会分数统计
任务：参加运动会有n个学校，学校编号为1……n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1……m，女子m+1……m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m<=20,n<=20）
功能要求：
（1）可以输入各个项目的前三名或前五名的成绩；
（2）能统计各学校总分；
（3）可以按学校编号或名称、学校总分、男女团体总分排序输出；
（4）可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。
（5）数据存入文件并能随时查询
输入数据形式和范围：可以输入学校的名称，运动项目的名称；输出形式有提示，各学校分数为整形；界面要求有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。
存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。
测试数据：要求使用全部合法数据、整体非法数据、局部非法数据。进行程序测试，以保证程序的稳定。
2、飞机订票系统
通过此系统可以实现如下功能：
（1）录入：可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）
（2）查询：可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；可以输入起飞抵达城市，查询飞机航班情况；
（3）订票：（订票情况可以存在一个数据文件中，结构自己设定）可以订票，如果该航班已经无票，可以提供相关可选择航班；
（4）退票： 可退票，退票后修改相关数据文件；
根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能。
3、文章编辑
功能：输入一页文字，程序可以统计出文字、数字、空格的个数。
静态存储一页文章，每行最多不超过80个字符，共N行；要求
（1）分别统计出其中英文字母数和空格数及整篇文章总字数；
（2）统计某一字符串在文章中出现的次数，并输出该次数；
（3）删除某一子串，并将后面的字符前移。
存储结构使用线性表，分别用几个子函数实现相应的功能；输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。
输出形式：（1）分行输出用户输入的各行字符；
（2）分4行输出"全部字母数"、"数字个数"、"空格个数"、"文章总字数"
（3）输出删除某一字符串后的文章。
4、宿舍管理查询软件
任务：为宿舍管理人员编写一个宿舍管理查询软件, 程序设计要求：
（1）采用交互工作方式
（2）建立数据文件 ，数据文件按关键字（姓名、学号、房号）进行排序(冒泡、选择、插入排序等任选一种)
查询菜单: (用二分查找实现以下操作)
（3）按姓名查询
（4）按学号查询
（5）按房号查询
（6）打印任一查询结果（可以连续操作）
5、地图着色问题
设计要求：已知中国地图，对各省进行着色，要求相邻省所使用的颜色不同，并保证使用的颜色总数最少。
6、校园导航问题
设计要求：设计你的学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。
7、图书借阅管理系统
主要分为两大功能：
（1）图书管理(增加图书、查询图书、删除图书、图书借阅、还书)；
（2）会员管理(增加会员、查询会员、删除会员、借书信息)。
8、学生成绩管理
实现功能：输入、输出、插入、删除、查找、追加、读入、显示、保存、拷贝、排序、索引、分类合计、退出。
9、二叉排序树的实现
用顺序和二叉链表作存储结构
（1）以回车('\n')为输入结束标志,输入数列L，生成一棵二叉排序树T；
（2）对二叉排序树T作中序遍历，输出结果；
（3）输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2)；否则输出信息“无x”。
10、最小生成树问题
设计要求：在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。
11、通讯录的制作
设计目的：用〈〈数据结构〉〉中的双向链表作数据结构，结合C语言基本知识。编写一个通讯录管理系统。以把所学数据结构知识应用到实际软件开发中去。
设计内容：本系统应完成一下几方面的功能：输入信息——enter();显示信息———display( );查找以姓名作为关键字 ———search( );删除信息———delete( );
设计要求：
（1）每条信息至包含 ：姓名（NAME ）街道（STREET）城市（CITY）邮编（EIP）国家（STATE）几项
（2）作为一个完整的系统，应具有友好的界面和较强的容错能力
（3）上机能正常运行，并写出课程设计报告
12、哈夫曼编码/译码器
设计一个利用哈夫曼算法的编码和译码系统，重复地显示并处理以下项目，直到选择退出为止。
基本要求：
（1）将权值数据存放在数据文件(文件名为data.txt，位于执行程序的当前目录中)
（2）分别采用动态和静态存储结构
（3）初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树；
（4）编码：利用建好的哈夫曼树生成哈夫曼编码；
（5）输出编码；
进一步完成内容：
（1）译码功能；
（2）显示哈夫曼树；
（3）界面设计的优化。
13、图书管理系统
设计一个计算机管理系统完成图书管理基本业务。
基本要求：
（1）每种书的登记内容包括书号、书名、著作者、现存量和库存量；
（2）对书号建立索引表（线性表）以提高查找效率；
（3）系统主要功能如下：
采编入库：新购一种书，确定书号后，登记到图书帐目表中，如果表中已有，则只将库存量增加；
借阅：如果一种书的现存量大于0，则借出一本，登记借阅者的书证号和归还期限，改变现存量；
归还：注销对借阅者的登记，改变该书的现存量。
14、散列表的设计与实现
设计散列表实现电话号码查找系统。
基本要求：
（1）设每个记录有下列数据项：电话号码、用户名、地址；
（2）从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表；
（3）采用一定的方法解决冲突；
（4）查找并显示给定电话号码的记录；
（5）查找并显示给定用户名的记录。
15、二叉树的中序、前序、后序的递归、非递归遍历算法，层次序的非递归遍历算法的实现，应包含建树的实现。
要求：遍历的内容应是千姿百态的。
16、敢死队问题
有M个敢死队员要炸掉敌人的一碉堡，谁都不想去，排长决定用轮回数数的办法来决定哪个战士去执行任务。如果前一个战士没完成任务，则要再派一个战士上去。现给每个战士编一个号，大家围坐成一圈，随便从某一个战士开始计数，当数到5时，对应的战士就去执行任务，且此战士不再参加下一轮计数。如果此战士没完成任务，再从下一个战士开始数数，被数到第5时，此战士接着去执行任务。以此类推，直到任务完成为止。
排长是不愿意去的，假设排长为1号，请你设计一程序，求出从第几号战士开始计数才能让排长最后一个留下来而不去执行任务。
要求：至少采用两种不同的数据结构的方法实现。如果采用三种以上的方法者，可加分。
17、图的遍历和生成树求解实现
要求：
（1）先任意创建一个图；
（2）图的DFS,BFS的递归和非递归算法的实现
（3）最小生成树（两个算法）的实现，求连通分量的实现
（4）要求用邻接矩阵、邻接表多种结构存储实现
18、线索二叉树的应用
要求：实现线索树建立、插入、删除、恢复线索的实现。
19、树的应用
要求：实现树与二叉树的转换的实现。以及树的前序、后序的递归、非递归算法，层次序的非递归算法的实现，应包含建树的实现。
20、链表操作
要求：利用链表的插入运算建立线性链表，然后利用链表的查找、删除、计数、输出等运算反复实现链表的这些操作（插入、删除、查找、计数、输出单独写成函数的形式），并能在屏幕上输出操作前后的结果。
四、设计方法和步骤
在处理每个题目时，要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过设计实现抽象数据类型、编制上机程序和上机调试等若干步骤完成题目，最终写出完整的分析报告。具体为：
1、分析问题，给出数学模型，设计相应的抽象数据结构。
（1）分析问题的特点，用数学表达式或其它形式描述其数学模型。
（2）选择能够体现问题本身特点的逻辑结构。
（3）在逻辑结构确定的情况下，为算法的设计选择相应的存储结构，不同存储方式，其对应的算法也不相同。
2、算法设计
在已经选择好数据结构的前提下，为解决问题设计算法。
（1）确定所需模块
对于稍复杂的程序设计，要充分利用模块化程序设计方法，自顶向下，逐步细化，在整体思路确定的情况下，考虑所需模块数，各模块完成功能以及模块之间的数据联系和调用关系。
（2）各子模块功能描述
给出主要模块的算法描述，用流程图或伪代码表示。
（3）模块之间的调用关系
给出算法各模块之间的关系图示
3、源程序清单
为了提高工作效率，充分利用上机调试程序的时间，要求学生在上机之前给出源程序清单。
4、算法分析
经过上机调试，源程序运行正确，并且实现算法要求的功能，解决课程设计题目中给出的问题后，分析各模块算法的时间复杂度和空间复杂度。
5、撰写设计报告
说明：在设计的过程中，步骤1---步骤4往往是反复进行，在后续步骤中发现问题，往往需要从头重新分析、设计。。
五、设计成果的编制
1、设计的题目要求达到一定工作量（300行以上代码），并具有一定的深度和难度。
2、程序设计语言推荐使用C/C++，程序书写规范，源程序需加必要的注释;
3、每位同学需提交可独立运行的程序；
4 、每位同学需独立提交设计报告书（每人一份），要求编排格式统一、规范、内容充实，不少于10页（代码不算），内容包括：
（1）设计题目
（2）设计内容
（3）概要设计：确定所需模块及模块间调用关系
（4）算法描述：给出各模块流程图及代码
（5）算法分析
（6）心得体会和参考资料
5、课程设计实践作为培养学生动手能力的一种手段，单独考核
六、评分标准及成绩评定
1、有以下情况的学生不能参加答辩：
·设计报告未经指导教师审阅。
·或设计内容不全（有设计报告而无设计程序、有设计程序而无设计报告）。
·未经指导教师许可或无故不到者，缺勤率达50%的学生。
答辩时，设计者在5分钟内阐述自己的设计过程和最终结果，突出设计中遇到的主要问题和解决方法，然后回答教师提问。每位学生答辩总时间一般不超过10分钟。
2、课程设计成绩的评定：根据设计的完成情况、程序的编制质量、独立设计能力以及答辩情况综合衡量，由答辩小组讨论决定。原则上按以下公式计算：
课程设计成绩＝考勤×10%＋报告×20%＋答辩×20%＋程序×50%
七、设计指导教师及分组情况
1、设计指导教师
魏新红、杨斌、张延红
2、学生每2人一组。
八、设计时间及指导老师安排
地点：计算机系机房205、206
第二篇：3-交通咨询系统设计-数据结构-课程设计任务书
交通资讯系统
1.系统需求分析
1.1问题描述
在交通网络非常发达的今天，人们出差、旅游或做其他出行时，不仅关心节省交通费用，而且对里程和所需时间等问题也很感兴趣。对于这样一个人们关心的问题，可用一个图结构来表示交通网络系统，利用计算机建立一个交通咨询系统。图中顶点表示城市，边表示城市之间的交通关系。设计一个交通咨询系统，能让旅客咨询从任一个城市顶点到达另外一个城市顶点之间的最短路径（里程）的问题。
1.2功能要求
1.交通资讯系统提供用户三种决策方案：一是建立交通网络图的存储结构。二是 某个城市到达其余各城市的最短路径。三是实现两个城市之间最短路径的问题。主 要目的是给用户提供路径咨询。
2.本系统规定：
(1)在程序中输入城市名称时，需输入0到5的城市代号
(2)在选择功 能是，应输入与所选功能对应的一个整形数据。
(3)程序的输出信息主要是：城市代号，某城市到达其余各城市的最短路径，
两城市之间最短路径
1
2.概要设计
2.1系统总体设计
图2.1系统总体设计
2.2各模块的功能
void main() 主函数
void Dijkstr() 采用狄克斯特拉算法求从顶点v到其余个顶点的最短路径void DisPath() 由path计算最短路径
void Ppath() 输出各条最短路径
void Floyd() 采用弗洛伊德算法求所有顶点之间的最短路径
void DisPath2() 由path计算最短路径
void Ppath2() 输出各条最短路径
2
2.3相关数据结构设计
1.数据结构
typedef int InfoType;
typedef struct
{char cityname;
int no;
InfoType info;
}VertexType;
typedef struct
{
int edges[MAXV][MAXV]; int n,e; VertexType vxs[MAXV];
}MGraph;
2.数据库结构：下表构成该系统的基本数据库
3.详细设计
3.1采用c语言定义相关的数据结构
本系统定义了整形int,字符型char,还有结构体定义，建立图的存储结构
首先定义交通图的存储结构，邻接矩阵是表示图形中顶点之间相邻关系的矩阵.设G=（V，E）是具有n(n>0)个顶点的图，则邻接矩阵具有如下定义的n阶方阵
A[i][j]=
∞ 其他 Wij 若vi≠vj 且<vi,vj>∈E(G)
一个图的邻接矩阵表示是唯一的,除了许用一个二维数组存储顶点之间相邻关系的邻接矩阵外，通常还需要使用一个具有n个元素的一维数组来存储顶点信息 3
3.2函数调用关系图
3.2.1主函数
void main()
{
int i,j,z,x; MGraph g; int
A[][MAXV]={{INF,5,INF,7,INF,INF},{INF,INF,4,INF,INF,INF},
{8,INF,INF,INF,INF,9},{INF,INF,5,INF,INF,6},{INF,INF,INF,5,INF,INF}, {3,INF,INF,INF,1,INF}};
g.n=6; g.e=10;
for(i=0;i<g.n;i++)
for(j=0;j<g.n;j++)
g.edges[i][j]=A[i][j];
交
通
咨
询
系
统
printf("*******************
**********************\n");
4
printf("************* 1-查看系统中的城市代号 **********\n");
printf("************* 2-一个城市到所有城市的最短路径
**********\n");
printf("************* 3-任意的两个城市之间的最短路径
**********\n");
printf("*************
**********\n");
printf("\n");
printf("请选择：");scanf("%d",&z); 0-退出 while(z!=0) { switch(z) { case 1: printf("0——北京,1——天津,2——上海,3——广州,4——南
京,5——厦门\n");
printf("\n");
main();
scanf("%d",&z);
break; case 2: printf("请输入城市代号:"); scanf("%d",&x); switch(x) { case 0: printf("以下是最短路径：\n");Dijkstra(g,x);break; case 1: printf("以下是最短路径：\n");Dijkstra(g,x);break; case 2:
5
printf("以下是最短路径：\n");Dijkstra(g,x);break; case 3:
scanf("%d",&z);break;
case 0:
}
}
printf("以下是最短路径：\n");Dijkstra(g,x);break; case 4: printf("以下是最短路径：\n");Dijkstra(g,x);break; case 5: printf("以下是最短路径：\n");Dijkstra(g,x);break; default : printf("输入有误，请重新输入\n"); printf("\n"); main(); } printf("\n"); main(); case 3: Floyd(g); printf("请选择："); printf("\n"); main(); scanf("%d",&z);break; exit(-1);break; default: printf("输入有误，请重新输入\n"); printf("\n"); main(); } 6
3.2.2狄克斯特拉函数
初始化距离和路径，将s[]置为空。将远点编号v放入s中,循环直到所有顶点的最短路径都求出，将mindis置最小长度初值，选取不在s中且具有最小距离的顶点u将顶点u加入s中，修改不在s中的顶点的距离，输出最短路径
void Dijkstra(MGraph g,int v)
{ int dist[MAXV],path[MAXV];
int s[MAXV];
int mindis,i,j,u;
for(i=0;i<g.n;i++)
{ dist[i]=g.edges[v][i];
s[i]=0;
if(g.edges[v][i]<INF)
path[i]=v;
else
path[i]=-1;
}
s[v]=1;path[v]=0;
for(i=0;i<g.n;i++)
{
mindis=INF;
for(j=0;j<g.n;j++)
if(s[j]==0&&dist[j]<mindis)
{
u=j;
mindis=dist[j];
}
s[u]=1;
for(j=0;j<g.n;j++)
if(s[j]==0)
if(g.edges[u][j]<INF&&dist[u]+g.edges[u][j]<dist[j]) {
7
}
} } dist[j]=dist[u]+g.edges[u][j]; path[j]=u; Dispath(dist,path,s,g.n,v);
3.2.3 Ppath函数
前向递归查找路径上的顶点，找到起点则返回，找顶点k的前一个顶点，输出顶点k。
void Ppath(int path[],int i,int v)
{
}
3.2.4 Dispath函数
有path函数计算最短路径，搜索最短路径的所有边，输出路径上的起点，输出路径上的中间点，输出路径上的终点。
void Dispath(int dist[],int path[],int s[],int n,int v)
{
int i; for(i=0;i<n;i++) { if(s[i]==1&&dist[i]!=INF) { int k; k=path[i]; if(k==v) return; Ppath(path,k,v); printf("%d,",k); printf("从%d到%d的最短路径长度为：%d\t路径为：",v,i,dist[i]); 8
}
} printf("%d,",v); Ppath(path,i,v); printf("%d\n",i); } else printf("从%d到%d不存在路径\n",v,i);
3.2.5弗洛伊德函数
设置路径长度A和路径path初值。做k次迭代，每次均试图将顶点K扩充到点钱球得的从i到j的最短路径Pij上，修开路径长度，输出最短路径。
void Floyd(MGraph g)
{ int path[MAXV][MAXV],A[MAXV][MAXV];
int i,j,k;
for(i=0;i<g.n;i++)
for(j=0;j<g.n;j++) {A[i][j]=g.edges[i][j]; path[i][j]=-1; }
for(k=0;k<g.n;k++)
{ for(i=0;i<g.n;i++)
for(j=0;j<g.n;j++)
if(A[i][j]>A[i][k]+A[k][j]) { A[i][j]=A[i][k]+A[k][j]; path[i][j]=k; }
}
3.2.6 Ppath2函数
向前递归查找路径上的顶点，找到了起点则返回，，找顶点i的前一个顶点k，找顶点k的前一个顶点j。在path中递归输出从顶点i到顶点j的最短路径 9
void Ppath2(int path[][MAXV],int i,int j)
{
int k; k=path[i][j];
if(k==-1)return;
}
3.2.7 DisPath2函数
由path计算最短路径，若顶点i和顶点j之间没有边，则输出i到j没有路径，若有边则输出路劲上的起点、中间点和终点。
void Dispath2(int A[][MAXV],int path[][MAXV],int n)
{ int i,j;
printf("请输入起点和终点(i,j)：");
scanf("%d,%d",&i,&j);
if(A[i][j]==INF) { if(i!=j) printf("从%d到%d没有路径\n",i,j); } else { printf("从%d到%d路径为：",i,j); Ppath2(path,i,k); printf("%d,",k); Ppath2(path,k,j); printf("%d,",i); Ppath2(path,i,j); printf("%d",j); printf("\t路径长度为：%d\n",A[i][j]); }
10
}
4.系统调试
4.1系统调试中的问题
（1）只考虑函数而忽视数据库和标点：在存储文件时，没有<stdlib.h>头文件；在程序中，有部分；和}遗漏。
（2）控制程序功能，只能使用一次，导致整个程序无实际作用；对图的存储结构不太熟悉;没有初始化路径，致使出现了乱码；使用单个字符输入一个字符串，导致字符串输入异常；
5.运行结果
5.1输入界面
输入界面如图 5.1所示
图5.1 输入界面
11
5.2显示界面
显示界面如图5.2所示
图5.2 显示界面
5.3查询界面
查询一个城市到其余各城市最短路径界面如图5.3所示
图5.3查询一个城市到其余各城市最短路径界面
12
查询两城市之间最短路径界面如图5.4所示
图5.4查询两城市之间最短路径界面
5.4退出界面
退出界面如图5.5所示
图5.5退出界面
13
6.心得体会
这次的任务分配，从难度上来说，我这个交通资讯系统并不复杂，在书本上基本上能找到一摸一样的程序，但关键是理解。平时不听课，现在要把这些整体连接起来就跟困难，虽然书上的程序能看懂，但实践设计不比理解，要是练得少，往往捉襟见肘，要学会融会贯通，就是难上加难，所以我这次就不断演练，不断打击信心，结果程序不是自己的，有时候觉得计算机语言真的好难学，我想还是练少了，酱油打多了。尽管这学期课听了很多，但效果还是不好。
总的来说，这次编程还是学到了一些东西，尽管微乎其微，算法逼近是死的，但人的大脑是活的，只有不断地实践，才能找到信心，也才能学到东西，尽管这次编程是借鉴网络上的，但还是可以学到很多东西，怎样的思考方法，怎样连接是逻辑语句更加完善。所以在编程中和调试过程中要认真分析和善于发现问题并及时解决的习惯，不懂得及时问老师或其他同学通过本次实验，掌握了最短路径的问题，并结合图的存储结构，狄克斯特拉算法、弗洛伊德算法等解决交通资讯系统的设计问题，源程序打出来后有多处错误，大小写错误、符号错误、遗漏错误。
7.附录
7.1源代码
#include<stdio.h>
#include<stdlib.h>
#include "string.h"
#define INF 32767
#define MAXV 10
typedef int InfoType;
typedef struct
{char cityname;
int no;
InfoType info;
}VertexType;
typedef struct
{
14
int edges[MAXV][MAXV]; int n,e; VertexType vxs[MAXV];
}MGraph;
void Ppath(int path[],int i,int v)
{
}
void Dispath(int dist[],int path[],int s[],int n,int v) {
}
void Dijkstra(MGraph g,int v)
{ int dist[MAXV],path[MAXV];
int s[MAXV]; int mindis,i,j,u; int i; for(i=0;i<n;i++) { if(s[i]==1&&dist[i]!=INF) { int k; k=path[i]; if(k==v) return; Ppath(path,k,v); printf("%d,",k); printf("从%d到%d的最短路径长度为：%d\t路径为：",v,i,dist[i]); } printf("%d,",v); Ppath(path,i,v); printf("%d\n",i); } else printf("从%d到%d不存在路径\n",v,i);
15
for(i=0;i<g.n;i++)
{ dist[i]=g.edges[v][i];
s[i]=0;
if(g.edges[v][i]<INF)
path[i]=v;
else
path[i]=-1;
}
s[v]=1;path[v]=0;
for(i=0;i<g.n;i++)
{
mindis=INF;
for(j=0;j<g.n;j++)
if(s[j]==0&&dist[j]<mindis)
{
u=j;
mindis=dist[j];
}
s[u]=1;
for(j=0;j<g.n;j++)
if(s[j]==0)
if(g.edges[u][j]<INF&&dist[u]+g.edges[u][j]<dist[j]) {
dist[j]=dist[u]+g.edges[u][j];
path[j]=u;
}
}
Dispath(dist,path,s,g.n,v);
}
void Ppath2(int path[][MAXV],int i,int j)
16
{
int k;
k=path[i][j];
if(k==-1)return;
Ppath2(path,i,k);
printf("%d,",k);
Ppath2(path,k,j);
}
void Dispath2(int A[][MAXV],int path[][MAXV],int n) { int i,j;
printf("请输入起点和终点(i,j)：");
scanf("%d,%d",&i,&j);
if(A[i][j]==INF)
{
if(i!=j)
printf("从%d到%d没有路径\n",i,j); }
else
{
printf("从%d到%d路径为：",i,j); printf("%d,",i);
Ppath2(path,i,j);
printf("%d",j);
printf("\t路径长度为：%d\n",A[i][j]); }
}
void Floyd(MGraph g)
{ int path[MAXV][MAXV],A[MAXV][MAXV];
int i,j,k;
for(i=0;i<g.n;i++)
17
for(j=0;j<g.n;j++) {A[i][j]=g.edges[i][j]; path[i][j]=-1; }
for(k=0;k<g.n;k++)
{ for(i=0;i<g.n;i++)
for(j=0;j<g.n;j++)
if(A[i][j]>A[i][k]+A[k][j]) { A[i][j]=A[i][k]+A[k][j]; path[i][j]=k; }
}
Dispath2(A,path,g.n);
}
void main()
{
int i,j,z,x; MGraph g; int A[][MAXV]={{INF,5,INF,7,INF,INF},{INF,INF,4,INF,INF,INF},
{8,INF,INF,INF,INF,9},{INF,INF,5,INF,INF,6},{INF,INF,INF,5,INF,INF},
{3,INF,INF,INF,1,INF}}; g.n=6;g.e=10; for(i=0;i<g.n;i++) for(j=0;j<g.n;j++) g.edges[i][j]=A[i][j]; 交通咨询系统 printf("*******************
**********************\n");
printf("************* 1-查看系统中的城市代号 **********\n");
printf("************* 2-一个城市到所有城市的最短路径
**********\n");
18
printf("************* 3-任意的两个城市之间的最短路径 **********\n");
printf("*************
**********\n");
printf("\n");
printf("请选择：");scanf("%d",&z); 0-退出 while(z!=0) { switch(z) { case 1: printf("0——北京,1——天津,2——上海,3——广州,4——南京,5——厦门\n");
printf("\n");
main();
scanf("%d",&z);
break; case 2: printf("请输入城市代号:"); scanf("%d",&x); switch(x) { case 0: printf("以下是最短路径：\n");Dijkstra(g,x);break; case 1: printf("以下是最短路径：\n");Dijkstra(g,x);break; case 2: printf("以下是最短路径：\n");Dijkstra(g,x);break; case 3:
printf("以下是最短路径：\n");Dijkstra(g,x);break; case 4:
19
printf("以下是最短路径：\n");Dijkstra(g,x);break; case 5: printf("以下是最短路径：\n");Dijkstra(g,x);break; default : printf("输入有误，请重新输入\n"); printf("\n"); main(); }
printf("\n");
} main(); scanf("%d",&z);break; case 3: Floyd(g); printf("请选择："); printf("\n"); main(); scanf("%d",&z);break; case 0: } exit(-1);break; default: printf("输入有误，请重新输入\n"); printf("\n"); main(); }
7.2参考文献
《数据库教程（第三版）》 李春葆 尹为民 李蓉蓉 蒋晶珏 喻丹丹 编著
[M]清华大学出版社
《数据库教程上机实验指导（第三版）》 李春葆 尹为民 李蓉蓉 蒋晶珏 喻丹丹 编著[M]清华大学出版社
20
8. 评分表
计算机与通信学院课程设计评分表
课程名称： 数据结构
教师签名： 日 期：
21