数据结构课程设计报告.docx
《数据结构课程设计报告.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计报告.docx（19页珍藏版）》请在冰点文库上搜索。
数据结构课程设计报告
数据结构课程设计报告撰写要求
（一）纸张与页面要求
1．采用国际标准A4型打印纸或复印纸，纵向打印。
2．封页和页面按照下面模板书写（正文为：
小四宋体1.5倍行距）。
3．图表及图表标题按照模板中的表示书写。
（二）课设报告书的内容应包括以下各个部分：
（按照以下顺序装订）
1.封页（见课设模版）
2.任务书（学生教师均要签字,信息填写完整）
3.目录
4.正文一般应包括以下内容:
（1）题目介绍和功能要求（或描述）
课程设计任务的详细描述（注意不能直接抄任务书）,将内容做更详细的具体的分析与描述；
（2）系统功能模块结构图
绘制系统功能结构框图及主要模块的功能说明；
（3）使用的数据结构的描述:
数据结构设计及用法说明;
（4）涉及到的函数的描述;
（5）主要算法描述（程序流程图）
（6）给出程序测试/运行的结果
设计多组数据加以描述（包括输入数据和输出结果）
（7）课程设计的总结及体会
（8）参考文献
格式要求：
[1]作者，等.书名.出版地：
出版社，出版年
5.附录：
程序清单（应带有必要的注释）
沈阳航空航天大学
课程设计报告
课程设计名称：
数据结构课程设计
课程设计题目：
城市旅游点导航问题
院（系）：
xxx学院
专业：
xxx
班级：
xxx
学号：
xxx
姓名：
xxx
指导教师：
xxx
此页为任务书
目录
1旅游点导航程序介绍和分析1
1.1程序的题目介绍及功能要求1
1.2运用的数据结构模型1
2系统功能模块2
2.1录入景点及路径长度模块2
2.1.1查询页面模块2
2.1.2初始景点模块2
2.2两景点间最短路径计算模块3
3运行结果5
3.1初始查询页面5
3.2输入查询的始终点5
4调试、总结和体会7
4.1调试7
4.2算法总结7
参考文献9
附录（关键部分程序清单）10
1旅游点导航程序介绍和分析
1.1程序的题目介绍及功能要求
程序要求至少包括10个以上的旅游点，每两个旅游点可以有不同的路径，并且路长可能不同，要求找出从任意旅游点到达另一旅游点的最短路径。
先从文件中读取城市的各个旅游点以及相互之间的路径和路长，构造城市的旅游图。
其次，根据用户输入的两个旅游点，给出两个旅游点之间的最短路径。
1.2运用的数据结构模型
此程序运用了结构体用来存储景点的编号和景点的名称，另用一结构体存储景点间的权值；
计算任意两景点间路径长度用到的是弗洛伊德算法，通过判断两景点间是否路径，然后计算两景点间的最短路径。
由于是有向图，所以输入路径需注意此问题。
2系统功能模块
2.1录入景点及路径长度模块
录入景点是用到一个结构体，typedefstructview{intno;//景点编号
charname[100];//景点名称}view;结构体中包括景点编号和景点名称，录入路经长度另用一结构体，typedefstructedge{intlength;}edge;只包括长度即可。
共用到查询页面模块、初始景点内容模块、景点权值模块，如图2.1。
录入景点及路径长度模块图：
录入景点及路径长度模块
查询页面模块
初始景点模块
景点权值模块
图2.1录入景点及路径长度模块
如图2.1所示，查询页面模块列出各个景点以及功能选项，按1则进行查询，按0则表示操作完成退出。
用showmenu函数实现。
初始景点模块此模块将景点名称复制到景点编号中，可实现景点名称的数字表示，该模块用Initview函数实现。
例如市政府编号为0，程序示例为strcpy（TD[0].name,"市政府"）;景点权值模块此模块式以二维数组的形式将景点间的路径长度保存下来，但要注意路径的方向性。
例如景点市政府（编号0）的景点沈阳故宫（编号1）之间的路径长度为10，程序示例为path[0][1].length=10;
2.2两景点间最短路径计算模块
此模块运用的是弗洛伊德算法，用函数onetoone实现。
算法逻辑图如下：
图2.2弗洛伊德算法逻辑图
如图2.2所示，弗洛伊德算法逻辑图原理为先判断两点间有无路径，再判断有无更短路径，若有则更新原有数值，否则其为最短路径。
算法流程图大致如下：
开始
输入起始地点
判断是否合理否
是
输入终点站
判断是否合理否
是
IfD[v]是（证明有路径）
否
!
final[w]&&（min+path[v][w].length是
D[w]=min+path[v][w].length
输出
图2.3算法流程图
算法流程大致为输入起始点和终点，判断两点是否是列表中的点，如果均符合就判断是否有路径，如果有路径再判断是否有其他路径并且路径长度更小，一直到照完所有的点。
3运行结果
3.1初始查询页面
图3.1初始查询页面
如图3.1所示，选择是查询还是退出。
例如选择1。
3.2输入查询的始终点
图3.2查询结果
如图3.2所示，例如查询的起始点是沈阳故宫（编号为1），终点是棋盘山（编号为3），则查询结果为最短路径是8。
路线为沈阳故宫棋盘山。
3.3是否继续查询
查询完毕后提示按任意键继续，然后选择是按1继续查询还是按0退出。
如果选择按1，则回到3.1初始页面阶段，如此循环。
4调试、总结和体会
4.1调试
调试过程中出现了许多问题一个很低级的错误就是在字符串的赋值上居然还会出错，本来是不可以像int型数据那样直接用等于号赋值的，可是刚开始由于失误却犯了这样低级的错误结果导致出现102个错误，当时确实有点慌了，等冷静下来一想才把问题想明白，字符串的赋值必须用strcpy函数。
看来基本功还是相当的重要的。
剩下的就是最主要的问题也可以说是99%的问题，都在弗洛伊德算法上了，弗洛伊德算法是我们重点学习的一个算法，当时学习时就感觉很吃力，不过当时也确实弄明白了，只可惜都过去好长一段时间了所以有所遗忘，算法确实是按照书上所写的抄到了程序中。
最短路径确实也存到了数组P[v0][v]中，可是在输出相应的景点名称时总不能输出正确，感觉是很不可思议的问题，后来才明白数组P中的存储是按照一定的顺序存储的但是并不一定是路径中所途经的景点的顺序，所以最后选择在求最短路径过程中将其输出。
还有一个就是确定两景点之间的权值的时候，刚开始没注意方向性，所以导致一个景点到另一个景点能过去，回来不行，后来经过查资料弄明白了。
4.2算法总结
弗洛伊德算法其实放在这里多少有些不合适，因为不管在求任意两个景点之间的最短路径还是求某一景点到其它景点的最短路径时都要完全的执行一遍算法时间复杂度是很高的，当时在实现时也确实考虑到了这个问题只是后来感觉要是实现时间复杂度的降低不是很简单也就暂时放弃了，也就选择了将这个算法直接搬了过来，这里是一点败笔，尚需要改进。
算法的时空分析和改进设想：
主要还是弗洛伊德算法的时空分析：
在计算到剩下的MAX-1个顶点的最短距离时第一个for循环时时间复杂度是O（n），每进行一次第二个for循环的时间复杂度都是O（n），第三个for循环也就是存储途经顶点时用的循环而不是书中算法所用的只是个地址的赋值，所以时间复杂度也是O（n），这样总的时间复杂度就是O（n3）。
改进设想主要就是给用户一个浏览路线的推荐本来在程序设计初期是计划要实现这个功能的，但是由于时间和能力问题没有去实现，因为它涉及到汉密尔顿路的实现，日后如果有机会一定将这个功能完善。
4.3体会
体会就是一个看似不起眼的小问题可能要花费很长的时间来找到并修改它，所以不要轻视小问题。
还有基础知识很重要，要把基础打好，否则只能吃哑巴亏了。
最后一句：
细心加耐心再加细节就等于成功。
参考文献
[1][美]S巴斯.计算机算法：
设计和分析引论[M].朱洪等译.s上海：
复旦大学出版社，1985
[2]（美）维斯.数据结构与算法分析[M].北京：
人民邮电出版社，2007.
[3]苏小红等.C语言大学实用教程.（第二版）[M].北京：
北京工业出版社，2008.
[4]吴文虎.程序设计基础（第二版）[M].北京：
清华大学出版社，2004.
[5]谭浩强.C程序设计教程[M].北京：
清华大学出版社，2008.
附录（关键部分程序清单）
#include
#include
#include
#defineMAX10
#defineINFINITY10000
typedefint**PathMatrix;
typedefint*DistancMatrix;
typedefstructview
{
intno;//景点编号
charname[100];//景点名称
}view;
typedefstructedge
{intlength;
}edge;
view*Initview（view*TD）//初始化景点内容
{
inti;
for（i=0;istrcpy（TD[0].name,"市政府"）;strcpy（TD[1].name,"沈阳故宫"）;strcpy（TD[2].name,"北陵公园"）;
strcpy（TD[3].name,"棋盘山"）;strcpy（TD[4].name,"中街"）;strcpy（TD[5].name,"沈阳大学"）;
strcpy（TD[6].name,"大帅府"）;strcpy（TD[7].name,"9.18纪念馆"）;strcpy（TD[8].name,"博物馆"）;
strcpy（TD[9].name,"市法院"）;returnTD;}
voidonetoone（PathMatrixP,DistancMatrixD,view*TD,edge**path）//计算最短路径
{
intv,w,w1,i,j,v1,min,t=0,x,flag=1,v0;
intfinal[MAX];
while（flag）
{
printf（"请输入一个起始景点编号:
"）;
scanf（"%d",&v0）;
if（v0<0||v0>MAX）
{
printf（"景点编号不存在!
请重新输入景点编号:
"）;
scanf（"%d",&v0）;
}
if（v0>=0&&v0flag=0;
}
flag=1;
while（flag）
{
printf（"请输入一个目的地景点编号:
"）;
scanf（"%d",&v1）;
if（v1<0||v1>MAX）
{
printf（"景点编号不存在!
请重新输入景点编号:
"）;
scanf（"%d",&v1）;
}
if（v1>=0&&v1flag=0;
}
for（v=0;v{
final[v]=0;
D[v]=path[v0][v].length;
for（w=0;wP[v][w]=0;
if（D[v]{
P[v][v0]=1;
P[v][v]=1;
}
}
D[v0]=0;
final[v0]=1;
for（i=1;i{
min=INFINITY;
for（w=0;wif（!
final[w]）
if（D[w]{
v=w;
min=D[w];
}
final[v]=1;
for（w=0;wif（!
final[w]&&（min+path[v][w].length{
D[w]=min+path[v][w].length;
for（x=0;xP[w][x]=P[v][x];
P[w][w]=1;
}
}
v=v1;
w1=v0;
printf（"%s",TD[v0].name）;
do{
flag=0;
min=INFINITY;
for（w=0;w{
if（P[v][w]&&w!
=v0）
{
flag=1;
if（D[w]{
j=w;min=D[w];
}
}
}
if（flag）
{
printf（"-->%s",TD[j].name）;w1=j;P[v][j]=0;
}
elsebreak;
}while
（1）;
printf（"\n总路线长%d\n\n",D[v]）;
printf（"完毕，按任意键继续!
\n"）;
getch（）;}
voidmain（）{
intk,v;
view*TD;
edge**path;
PathMatrixP;
DistancMatrixD;
path=（edge**）malloc（MAX*sizeof（edge））;
for（v=0;vpath[v]=（edge*）malloc（1000*sizeof（edge））;
TD=（view*）malloc（MAX*sizeof（view））;
D=（DistancMatrix）malloc（MAX*sizeof（DistancMatrix））;
P=（PathMatrix）malloc（MAX*sizeof（PathMatrix））;
for（v=0;vP[v]=（int*）malloc（MAX*sizeof（int*））;
Initview（TD）;
InitLength（path）;
while
（1）{
showmenu（）;
printf（"请选择：
\n"）;
scanf（"%d",&k）;
switch（k）{
case1:
onetoone（P,D,TD,path）;break;
case0:
exit（0）;}}}
课程设计总结：
通过这次数据结构课程设计，我清楚地认识到了自己的不足，所以开始的时候无从下手，但在老师的辛勤指导和同学的细心帮助下，使我明白了许多。
在一周的设计中，我不仅学到了许多知识，同时体会到了完成一项工作的快乐，我想，这也许就叫成就感吧，语言设计要求我们注意很多细节问题，我们必须仔仔细细，一丝不苟，才能保证程序的正确性，使我们办事做人都更加的认真，因为我知道了，只有这样才是对别人负责，也是对自己负责，同时，也会在这种负责的过程中得到他人的尊敬。
总之，我受益匪浅。
指导教师评语：
指导教师（签字）：
年月日
课程设计成绩
升级会员 