数据结构课程设计.docx
《数据结构课程设计.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计.docx（23页珍藏版）》请在冰点文库上搜索。
数据结构课程设计
目录
1.设计时间………………………………………………2
2.设计目的………………………………………………2
3.设计任务………………………………………………2
4.设计内容………………………………………………2
4.1需求分析…………………………………………………2
4.2总体设计…………………………………………………3
4.3详细设计…………………………………………………4
4.4测试与分析………………………………………………12
4.4.1测试…………………………………………………………12
4.4.2分析…………………………………………………………13
4.5附录………………………………………………………14
5总结与展望……………………………………………20
6.参考文献………………………………………………21
7.成绩评定………………………………………………21
1设计时间
2012/01/03至2012/01/06
2设计目的
1．加深对《数据结构》这一课程所学内容的进一步理解与巩固
2．通过完成课程设计，逐渐培养自己的编程能力；
3．培养给出题目后，构建框架，用计算机解决的能力；
4．通过调试程序积累调试C程序设计的经验；
3设计任务
给出校园各主要建筑的名称信息及有线路联通的建筑之间的距离，利用校园导航系统计算出给定的起点到终点之间的最近距离及线路。
4设计内容
4.1需求分析
1．程序所能达到的功能：
（1）map——输出辽宁工程技术大学平面图。
（2）init（）——按相应编号输入各个节点内容，对相应路径赋值的函数。
（3）menu（）——菜单函数
（4）information（）——输出简介的函数
（5）way（）——最短路径的输出函数
（6）shortestpath（）——调用弗洛伊德和最短路径输出的函数
（7）main（）——主函数
2．输入的形式和输入值的范围：
输入数字和字母：
字母：
以s查询最短路径；以i查询信息；以e退出程序。
数字：
从1到11输入。
3．输出的形式：
从A到B得最短路径为：
A-到-C-到-D-到-B
最短距离为：
xxx米。
4．测试数据包括在正确的输入及输出结果及含有错误的输入及输出结果：
当输入为：
s111
输出为：
从浴池到静远楼的最短路径为：
浴池-到-B寝室楼-到-一食堂-到-综合楼-到-静远楼
最短距离为：
180米。
数据均为测试数据，与实际有误差，敬请谅解。
当输入为：
i1
输出为：
名称：
浴池
简介：
洗澡，吃饭，超市，一应俱全
当输入为：
e
输出为：
谢谢使用！
当输入为：
i13
输出为：
输入有误！
请输入查询地点的编号：
4.2总体设计
1．抽象数据类型定义
有向网节点结构体类型
typedefstruct
{
charname[10];
intnumber;
charintroduce[100];
}vertex;
2．主程序模块的整体
流程
1、进入主函数，调用init，map和menu函数。
2、选择“s”，调用shortestpath函数，并同时调用floyd和way函数。
并返回调用menu函数。
3、选择“i”，调用information函数。
并返回调用menu函数。
4、选择“e”，退出。
3.各模块调用关系如下：
4.3详细设计
1.有向网节点结构体类型定义：
typedefstruct
{
charname[10];
intnumber;
charintroduce[100];
}vertex;
2.主程序和其它主要函数伪码算法
1）主程序
intmain（）/*主函数*/
{
chari;
printf（"\t\t\t欢迎使用辽宁工程技术大学导航系统\n\n"）;
init（）;
map（）;/*输出地图，提示使用者*/
while
（1）
{
i=menu（）;
switch（i）
{
case's':
shortestpath（）;break;
case'i':
information（）;break;
case'e':
printf（"\n\n\n\t\t\t\t谢谢使用!
\n"）;return（0）;
default:
printf（"输入错误！
\n"）;break;
}
}
}
2）赋值init函数
voidinit（）
{
inti,j;/*从41到73行，对平面图中的各个地点信息进行输入，运用strcpy函数*/
ver[1].number=1;
strcpy（ver[1].name,"浴池"）;
strcpy（ver[1].introduce,"洗澡，吃饭，超市，一应具全\n"）;
ver[2].number=2;
strcpy（ver[2].name,"老操场"）;
strcpy（ver[2].introduce,"怀念一下学长们的艰苦生活\n"）;
ver[3].number=3;
strcpy（ver[3].name,"新体育场"）;
strcpy（ver[3].introduce,"假草，球门，尽情施展脚法的好地方\n"）;
ver[4].number=4;
strcpy（ver[4].name,"B寝室楼"）;
strcpy（ver[4].introduce,"女寝，不解释\n"）;
ver[5].number=5;
strcpy（ver[5].name,"一食堂"）;
strcpy（ver[5].introduce,"饭呐，不好吃\n"）;
ver[6].number=6;
strcpy（ver[6].name,"综合楼"）;
strcpy（ver[6].introduce,"超市，有日用品，各种食品，还有各种营业厅，眼镜店，书店，水果店\n"）;
ver[7].number=7;
strcpy（ver[7].name,"南大门"）;
strcpy（ver[7].introduce,"学校最宏伟的建筑，校友捐赠\n"）;
ver[8].number=8;
strcpy（ver[8].name,"A寝室楼"）;
strcpy（ver[8].introduce,"男寝，我的家\n"）;
ver[9].number=9;
strcpy（ver[9].name,"尔雅"）;
strcpy（ver[9].introduce,"教学楼，有我最爱的411，是基础教学部老师大展身手的地方\n"）;
ver[10].number=10;
strcpy（ver[10].name,"耘慧楼"）;
strcpy（ver[10].introduce,"教学楼，各种上机实验的地方\n"）;
ver[11].number=11;
strcpy（ver[11].name,"静远楼"）;
strcpy（ver[11].introduce,"教学楼，内涵图书馆，足够惊喜\n"）;
for（i=1;i<=Num;i++）/*对存储距离的距离矩阵取值进行初始化，全定义为最大*/
{
for（j=1;j<=Num;j++）
{
edge[i][j]=Maxedge;
}
}
for（i=1;i<=Num;i++）/*对存储距离的矩阵的取值进行正确赋值，由于我校均来回可达，顾对路径正反同时赋值*/
{
edge[i][i]=0;
}
edge[1][2]=edge[2][1]=20;
edge[2][3]=edge[3][2]=50;
edge[2][5]=edge[5][2]=50;
edge[3][4]=edge[4][3]=100;
edge[3][6]=edge[6][3]=300;
edge[1][4]=edge[4][1]=20;
edge[4][5]=edge[5][4]=30;
edge[5][6]=edge[6][5]=10;
edge[6][7]=edge[7][6]=200;
edge[6][11]=edge[11][6]=120;
edge[4][8]=edge[8][4]=10;
edge[8][9]=edge[9][8]=250;
edge[9][10]=edge[10][9]=50;
edge[10][11]=edge[11][10]=50;
edge[7][11]=edge[11][7]=100;
}
3）输出辽宁工程技术大学平面图的map函数
voidmap（）/*辽宁工程技术大学平面图，给使用程序者以直观认识*/
{
printf（"\t\t辽宁工程技术大学大学平面图（括号内为相对应的数字编号）\n\n"）;
printf（"浴池
（1）——————老体育场
（2）————新体育场（3）————\n"）;
printf（"||||\n"）;
printf（"||||\n"）;
printf（"B寝室楼（4）————一食堂（5）——————综合楼（6）————————南大门（7）\n"）;
printf（"||\n"）;
printf（"A寝室楼（8）|\n"）;
printf（"||\n"）;
printf（"——尔雅楼（9）——————耘慧楼（10）——————静远楼（11）\n\n"）;
}
4）菜单menu函数
charmenu（）/*菜单函数*/
{
chari;
printf（"输入“s”以查询最短路径\n"）;
printf（"输入“i”以查询信息\n"）;
printf（"输入“e”以退出程序\n"）;
printf（"请输入对应的英文小写字母，谢谢：
\n\t"）;
scanf（"%s",&i）;
returni;
}
5）输出地点信息的information函数
voidinformation（）/*输出简介函数*/
{
inti;
while
（1）
{
printf（"请输入查询地点的编号：
\n\t"）;
scanf（"%d",&i）;
if（i<=Num&&i>=1）
{
printf（"\n@名称：
%s\n#简介：
%s\n",ver[i].name,ver[i].introduce）;
return;
}
else
{
printf（"输入有误！
"）;
}
}
}
6）最短路径floyd函数
voidfloyd（）/*弗洛伊德算法*/
{
inti=1,j=1,k=1,l=1;
for（i=1;i<=Num;i++）
{
for（j=1;j<=Num;j++）
{
shortest[i][j]=edge[i][j];
path[i][j]=0;
}
}
for（k=1;k<=Num;k++）
{
for（i=1;i<=Num;i++）
{
for（j=1;j<=Num;j++）
{
if（shortest[i][j]>（shortest[i][k]+shortest[k][j]））
{
shortest[i][j]=（shortest[i][k]+shortest[k][j]）;
path[i][j]=path[j][i]=k;
}
}
}
}
}
7）输出路径way算法
voidway（inti,intj）/*最短路径的输出*/
{
intk=0,a=i,b=j;
if（shortest[i][j]!
=Maxedge）
{
printf（"\n%从%s到%s的最短路径为:
\n",ver[i].name,ver[j].name）;
printf（"%s",ver[i].name）;
while（path[i][j]!
=0）
{
k=path[i][j];
while（path[i][k]!
=0）
{
k=path[i][k];
}
printf（"-到-%s",ver[k].name）;
i=k;
}
printf（"-到-%s;\n",ver[j].name）;
printf（"\n最短距离为：
%d米。
\n",shortest[a][b]）;
printf（"\n数据均为测试数据，与实际有误差，敬请谅解.\n\n"）;
}
else
printf（"从%s不能到达%s。
",ver[i].name,ver[j].name）;
}
8）调用floyd和way的最短路径shortestpath算法
voidshortestpath（）/*寻找最短路径*/
{
inti=0,j=0;
while
（1）
{
printf（"请输入要查询的两点的编号：
（以空格间隔）"）;
scanf（"%d%d",&i,&j）;
if（i<=Num&&i>0&&j<=Num&&j>0）
{
floyd（）;
way（i,j）;
return;
}
}
}
3.函数的调用关系
exit
exit
4.4测试与分析
4.4.1测试
1）打开程序后，出现我校平面图和菜单选项，如图所示
2）选“i”，查询对应地点的信息，如输入“3”，而后会继续输出菜单，如图所示
3）选“s”，查询两点之间的信息，如输入“111”，而后会继续输出菜单，如图所示
4）选“e”，推出程序，如图所示
4.4.2分析
1.本次作业的核心是利用弗洛伊德算法计算给定有向网中两点最短距离；给出有向网中所要求点的信息。
在调试过程中，除了简单语法错误外，就是对弗洛伊德算法的理解和实现，以及菜单的设置，这是我以前没有实现过的。
出于简单化，并没有对有向图中各个点进行输入，而是在程序中直接赋值。
2.在对各个功能操作的实现上，由于有弗洛伊德算法时间复杂度大多数是O（n3），空间上增加了二维数组，空间复杂度为O（n+s）。
4.5附录
源程序代码及必要注释。
#include
#include
#defineNum11/*测试使用十一个地点，直接定义*/
#defineMaxedge32760/*最大距离*/
typedefstruct/*定义对各个地点信息存储的结构体类型*/
{
charname[10];
intnumber;
charintroduce[100];
}vertex;
vertexver[Num];/*定义结构体数组*/
intedge[Num][Num];
intshortest[Num][Num];
intpath[Num][Num];
voidmap（）/*辽宁工程技术大学平面图，给使用程序者以直观认识*/
{
printf（"\t\t辽宁工程技术大学大学平面图（括号内为相对应的数字编号）\n\n"）;
printf（"浴池
（1）——————老体育场
（2）————新体育场（3）————\n"）;
printf（"||||\n"）;
printf（"||||\n"）;
printf（"B寝室楼（4）————一食堂（5）——————综合楼（6）————————南大门（7）\n"）;
printf（"||\n"）;
printf（"A寝室楼（8）|\n"）;
printf（"||\n"）;
printf（"——尔雅楼（9）——————耘慧楼（10）——————静远楼（11）\n\n"）;
}
voidinit（）
{
inti,j;/*从41到73行，对平面图中的各个地点信息进行输入，运用strcpy函数*/
ver[1].number=1;
strcpy（ver[1].name,"浴池"）;
strcpy（ver[1].introduce,"洗澡，吃饭，超市，一应具全\n"）;
ver[2].number=2;
strcpy（ver[2].name,"老操场"）;
strcpy（ver[2].introduce,"怀念一下学长们的艰苦生活\n"）;
ver[3].number=3;
strcpy（ver[3].name,"新体育场"）;
strcpy（ver[3].introduce,"假草，球门，尽情施展脚法的好地方\n"）;
ver[4].number=4;
strcpy（ver[4].name,"B寝室楼"）;
strcpy（ver[4].introduce,"女寝，不解释\n"）;
ver[5].number=5;
strcpy（ver[5].name,"一食堂"）;
strcpy（ver[5].introduce,"饭呐，不好吃\n"）;
ver[6].number=6;
strcpy（ver[6].name,"综合楼"）;
strcpy（ver[6].introduce,"超市，有日用品，各种食品，还有各种营业厅，眼镜店，书店，水果店\n"）;
ver[7].number=7;
strcpy（ver[7].name,"南大门"）;
strcpy（ver[7].introduce,"学校最宏伟的建筑，校友捐赠\n"）;
ver[8].number=8;
strcpy（ver[8].name,"A寝室楼"）;
strcpy（ver[8].introduce,"男寝，我的家\n"）;
ver[9].number=9;
strcpy（ver[9].name,"尔雅"）;
strcpy（ver[9].introduce,"教学楼，有我最爱的411，是基础教学部老师大展身手的地方\n"）;
ver[10].number=10;
strcpy（ver[10].name,"耘慧楼"）;
strcpy（ver[10].introduce,"教学楼，各种上机实验的地方\n"）;
ver[11].number=11;
strcpy（ver[11].name,"静远楼"）;
strcpy（ver[11].introduce,"教学楼，内涵图书馆，足够惊喜\n"）;
for（i=1;i<=Num;i++）/*对存储距离的距离矩阵取值进行初始化，全定义为最大*/
{
for（j=1;j<=Num;j++）
{
edge[i][j]=Maxedge;
}
}
for（i=1;i<=Num;i++）/*对存储距离的矩阵的取值进行正确赋值，由于我校均来回可达，顾对路径正反同时赋值*/
{
edge[i][i]=0;
}
edge[1][2]=edge[2][1]=20;
edge[2][3]=edge[3][2]=50;
edge[2][5]=edge[5][2]=50;
edge[3][4]=edge[4][3]=100;
edge[3][6]=edge[6][3]=300;
edge[1][4]=edge[4][1]=20;
edge[4][5]=edge[5][4]=30;
edge[5][6]=edge[6][5]=10;
edge[6][7]=edge[7][6]=200;
edge[6][11]=edge[11][6]=120;
edge[4][8]=edge[8][4]=10;
edge[8][9]=edge[9][8]=250;
edge[9][10]=edge[10][9]=50;
edge[10][11]=edge[11][10]=50;
edge[7][11]=edge[11][7]=100;
}
charmenu（）/*菜单函数*/
{
chari;
printf（"输入“s”以查询最短路径\n"）;
printf（"输入“i”以查询信息\n"）;
printf（"输入“e”以退出程序\n"）;
printf（"请输入对应的英文小写字母，谢谢：
\n\t"）;
scanf（"%s",&i）;
returni;
}
voidinformation（）/*输出简介函数*/
{
inti;
while
（1）
{
printf（"请输入查询地点的编号：
\n\t"）;
scanf（"%d",&i）;
if（i<=Num&&i>=1）
{
printf（"\n@名称：
%s\n#简介：
%s\n",ver[i].name,ver[i].introduce）;
return;
}
else
{
printf（"输入有误！
"）;
}
}
}
voidfloyd（）/*弗洛伊德算法*/
{
inti=1,j=1,k=1,l=1;
for（i=1;i<=Num;i++）
{
for（j=1;j<=Num;j++）
{
shortest[i][j]=edge[i][j];
path[i][j]=0;
}
}
for（k=1;k<=Num;k++）
{
for（i=1;i<=Num;i++）
{
for（j=1;j<=Num;j++）
{
if（shortest[i][j]>（shortest[i][k]+shortest[k][j]））
{
shortest[i][j]=（shortest[i][k]+shortest[k][j]）;
path[i][j]=path[j][i]=k;
}
}
}
}
}
voidway（inti,intj）/*最短路径的输出*/
{
intk=0,a=i,b=j;
if（shortest[i][j]!
=Maxedge）
{
printf（"\n%从%s到%s的最短路径为:
\n",ver[i].name,ver[j].name）;
printf（"%s",ver[i].name）;
while（path[i][j]!
=0）
{
k=path[i][j];
while（path[i][k]!
=0）
{
k=path[i][k];
}
printf（"-到-%s",ver[k].name）;
i=k;
}
printf（"-到-%s;\n",ver[j].name）;
printf（"\n最短距离为：
%d米。
\n",shortest[a][b]）;
printf（"\n数据均为测试数据，与实际有误差，敬请谅解.\n\n"
升级会员 