数据结构课程设计报告模板.doc

课程设计报告

设计名称： 数据结构课程设计
选题名称： 连云港市景点导游咨询
系 （院): 计算机工程学院
设计时间： 2012。12。24~2013。1.4
设计地点： 软件工程实验室、教室

成绩：
指导教师评语：

签名：
年 月 日

1．课程设计目的
1、训练学生灵活应用所学数据结构知识，独立完成问题分析，结合数据结构理论知识，编写程序求解指定问题.
2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；
3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力；
4。训练用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知识，提高编程水平，并在此过程中培养他们严谨的科学态度和良好的工作作风。

2．课程设计任务与要求：
任务
根据教材《数据结构—C语言描述》（耿国华主编）和参考书《数据结构题集(C语言版）》（严蔚敏、吴伟民主编）选择课程设计题目，要求通过设计，在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解和综合运用。
设计题目从任务书所列选题表中选取，每班每题不得超过2人.
学生自选课题
学生原则上可以结合个人爱好自选课题,要求课题有一定的深度与难度，有一定的算法复杂性，能够巩固数据结构课程所学的知识。学生自选课题需在18周前报课程设计指导教师批准方可生效.
要求：
1、在处理每个题目时，要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过设计实现抽象数据类型、编制上机程序和上机调试等若干步骤完成题目，最终写出完整的分析报告。前期准备工作完备与否直接影响到后序上机调试工作的效率.在程序设计阶段应尽量利用已有的标准函数,加大代码的重用率。
2、.设计的题目要求达到一定工作量(300行以上代码）,并具有一定的深度和难度。
3、程序设计语言推荐使用C/C++，程序书写规范，源程序需加必要的注释；
4、每位同学需提交可独立运行的程序;
5 、每位同学需独立提交设计报告书（每人一份），要求编排格式统一、规范、内容充实，不少于10页（代码不算）；
6、课程设计实践作为培养学生动手能力的一种手段，单独考核。

3．课程设计说明书
一 需求分析
连云港作为一个著名的旅游城市，每年都有大量的国内外游客来港城旅游，大多数外地游客对连云港的旅游景点的相关信息不是非常了解，所以我们可以为他们设计一个方便在连云港外出旅游的咨询程序，即连云港市景点导游咨询程序。
连云港市导游咨询程序需要把连云港市的主要景点,都包括在一个平面图内。
（1） 以图中各顶点存放连云港的各景点名称,代号，简介等相关信息
（2）程序中，以各个旅游景点名称为图的顶点，各个顶点的信息是景点的简要描述，权值就是任意两个景点间的路径长度。
(3) 以边存放路径及路径长度等相关信息，游客可根据图所提供的景点来查询各个景点的相关信息及各景点的路径查询。
(4) 提供两个景点间的所有路径并提示最短路径，为游客的旅游带来方便，游客可根据实际情况选择最佳的游览路线。

二 概要设计
1、抽象数据类型图的定义如下:
ADT Graph{
数据对象V：V是具有相同特性的数据元素的集合,称为顶点集。
数据关系R：
R={VR｝
VR=｛（v，w）|v，w∈V，(v，w）表示v和w之间存在路径｝
基本操作P：
path(MGraph g，int i,int j,int k）
初始条件：要查询的起点i与终点j，k初始值为0
操作结果：确定路径上第k+1个顶点的序号，找到从vi到vj的所有路径
disppath（MGraph g,int i,int j
初始条件：定义一个图与起点i终点j
操作结果：初始化访问标志与路径条数，并调用path（）函数
ppath（MGraph g,int path1［]，int i,int v0)
初始条件:定义一个图，path1[i］存放顶点i的当前最短路径上该点的前趋顶点，i为终点，v0为起点
操作结果：输出最短路径
dispath（MGraph g,int dist[］，int path1[］,int s［]，int n,int v0，int i）
初始条件：定义一个图,用dist[i]存放顶点i的当前最短路径长度，path1［i] 存放顶点i的当前最短路径上该点的前趋顶点，n为景点个数，v0与i分别为起点与终点
操作结果:由path1计算出从v0到i的最短路径
Dijkstra（MGraph g,int v0,int p)
初始条件：定义图与起点与终点
操作结果:采用迪杰斯特拉算法求从顶点v0到顶点p的最短路径
Searchname（MGraph g）
初始条件：定义一个图
操作结果：查询景点的信息
Searchpath1(MGraph g）
初始条件：定义一个图
操作结果:查询两个景点间的所有路径
Searchpath2(MGraph g）
初始条件:定义一个图
操作结果：查询两个景点间的最短路径
｝ADT Graph
2、系统中子程序及功能要求：
①path（MGraph g,int i,int j，int k)：确定路径上第k+1个顶点的序号，k初始值为0
②disppath(MGraph g，int i，int j）：初始化访问标志与路径条数,并调用path（）函数
③ppath(MGraph g，int path1［]，int i，int v0）：输出最短路径
④dispath（MGraph g,int dist[],int path1［],int s［］，int n，int v0，int i）：由path1计算从v0到i的最短路径
⑤Dijkstra(MGraph g，int v0,int p)：采用迪杰斯特拉算法求从顶点v0到顶点p的最短路径
⑥Searchname（MGraph g)：查询景点的信息
⑦Searchpath1(MGraph g)：查询两个景点间的所有路径
⑧Searchpath2(MGraph g):查询两个景点间的最短路径
⑨Searchpath3(MGraph g）：添加动态景点
3、 各程序模块之间的调用关系:
函数的调用关系图
main

Searchname ⑥ Searchpath1⑦ Searchpath2⑧ Searchpath2⑨

disppath ④ Dijkstra⑤

path ① dispath④

path ① ppath ③

Ppath③

主函数调用 ⑥⑦⑧⑨ ⑦可调用④ ⑧可调用⑤
①可调用① ④可调用③ ③可调用③
②可调用① ⑤可调用④
三 详细设计
⑴顶点、边和图的类型：
typedef struct
｛
int num；/＊顶点编号＊/
char name[MAXSIZE];/＊顶点名称＊/
char discription[MAXLEN］;/＊顶点信息描述＊/
}VertexType；
typedef struct
{
int edges[MAXV]［MAXV］；
int vexnum，arcnum;
VertexType vexs［MAXV]；
｝MGraph；
int visited［MAXV］;
int p[MAXV];

⑵创建连云港市景点地图：
int i，j
int b[11］={1，2，3，4,5，6,7,8，9,10,11};
char *c[11］={/＊各个景点名称＊/}；
char *d［11]=｛/*字符串指针数组,用来给每个顶点的简介信息进行赋值*/｝；
MGraph g；/*创建一个无向网＊/
int A［11］[11］=｛/＊景点的相关简介进行赋值＊/ ｝；
g。vexnum=顶点个数；
g。arcnum=顶点边数;
/＊建立无向网的邻接矩阵*/
for(i=0；i<图的顶点个数；i++）
{
/*给每个顶点一个编号*/
/＊通过字符串复制函数给每个顶点一个名称＊/
/＊通过字符串复制函数给每个顶点加上信息，即作为景点的简介信息＊/
}

⑶查询景点的信息:
int i；
char s;
while（1）
/＊可提供循环查询,当输入为’N’或'n'时,结束循环*/
｛
printf(”\t\t\t 请输入你要查询的景点：”）；
scanf（”％d"，＆i）；
for(int j=0；j〈图的顶点个数;j++)

{
/＊输出信息*/
}
printf（”继续查询?(y或n）:")；
scanf("％s”，＆s）；
if(s’N’|｜s=='n')
break；
｝

⑷查询景点间的游览路径：
void Searchpath1（MGraph g）
int i，j;
char s；
while(1）/*可提供循环查询，当输入为'N’或’n’时,结束循环*/
｛
/＊输入起点与终点*/;
disppath（g,i，j）;/＊调用disppath函数,用来输出两个景点间的所有路径*/
printf(”继续查询？（y或n）："）；
scanf（”%s",&s)；
if(s==’N’|｜s==’n'）
break；
｝

}

⑸查询最短路径：
int i，j；
char s；
while（1)
/*可提供循环查询,当输入为’N’或'n'时,结束循环＊/
｛
/*输入起点与终点＊/
Dijkstra（g,i,j)；/*调用Dijkstra函数,用来输出两个景点间的最短路径*/
printf（"继续查询？（y或n）:”）；
scanf（”％s"，&s）；
if（s==’N'｜|s==’n')
break；
｝
}

（6）添加动态景点:

(7）主函数:
int select;/*定义一个整型变量,用来输入不同的选择*/
do/＊可提供循环输入选择，当输入的选择为4时,退出循环*/
{
switch(select)/*判断select的值,根据其值跳转到相应的子模块继续执行＊/
｛
case 1：
/*查询景点的信息*/
break；
case 2:
；/*查询景点间的游览路径*/
break；
case 3：
/*查询景点间的最短游览路径*/
Case 4：
/＊添加动态景点＊/
break;
case 5:/*退出程序＊/
break;
｝
}while(select!=5)；/＊当select的值不为5时，继续循环*/
｝

四 设计与调试分析
1。菜单项
运行主函数时菜单项完整输出
结果正确
2. 查询景点
选出系统给出的景点名称如：1、锦屏山
系统输出信息如下：
名称：锦屏山
简介：因山色锦绣,美如画屏，而被康熙皇帝命名为锦屏山
票价: 10
结果正确。
3.查询最短路径
如:选择出发地：古城
目的地:玉女峰
系统输出如下：
古城--—->孔子忘角—--—〉玉女峰 路径长度：25公里
4.查询所有路径
如：选出出发地：孔望山
目的地：连岛
系统输出如下:
孔望山-—-—〉连岛
孔望山--——>前三岛—---〉枫树湾-———〉连岛
孔望山———-〉前三岛--——>枫树湾-——->桃花涧—-——〉连岛
孔望山--—->—--—〉前三岛----〉枫树湾---->桃花涧—-—->东海温泉—--—>连岛
结果正确
5. 动态添加景点
动态添加,目前只能添加进信息，方便查询,还未实现求路径的功能。
五 用户手册
本程序界面如下：

按序号进行操作！
六 测试成果
1、 查询景点

2、 查询所有路径

3、 查询最短路径

4、 添加景点

七 附录（源程序清单）
＃includeMAXLEN 500/*字符串成员content的最大长度＊/
#define INF 32768/*用32768表示∞＊/
int a=0；/*全局变量，用来记录每对顶点之间的所有路径的条数*/
static n=8；
typedef struct
｛
int num;
char name[MAXSIZE];
char discription［MAXLEN];
}VertexType；/*顶点的结构定义*/
typedef struct
{
int edges［MAXV]［MAXV］;
int vexnum,arcnum;
VertexType vexs[MAXV];
}MGraph;/*网的结构定义*/
int visited［MAXV］;/*全局数组，用来记录各顶点被访问的情况＊/
int p［MAXV］；/＊全局数组,用来存放路径上的各顶点＊/

void path(MGraph g,int i,int j,int k) /*i为要查询是起始点，j为要查询的终点,相当于深度优先遍历＊/
{
int s;
if（p[k］==j)
{
a++;
printf（"第%d条：”,a）；
for（s=0；s<=k-1;s++）
printf(”％s—>”,g.vexs［p［s]］.name）；
printf（"％s\n"，g。vexs[p[s]].name)；
｝
s=0；
while（s〈g。vexnum）
｛
if（s！=i)/*保证找到的是简单路径,保证没有回路＊/
｛
if(g.edges[p［k］］［s]!=INF&&visited［s]==0)
｛
visited［s］=1；
p［k+1］=s；
path(g，i,j,k+1);
visited[s]=0；
}
｝
s++;
｝
}

void disppath（MGraph g，int i，int j)
｛
int k；
p［0]=i；
for(k=0；k〈g.vexnum;k++)
visited[i］=0；
a=0;
path(g,i,j，0）;
｝

void ppath(MGraph g，int path1［］,int i,int v0)
{
int k；
k=path1[i]；
if（k==v0)
return；
ppath(g,path1,k，v0）;
printf（”％s—〉",g.vexs［k］。name)；
}/*输出最短路径＊/

void dispath(MGraph g,int dist［],int path1[],int s［］,int n，int v0,int i)

{
if（s[i］==1&＆i！=v0）
｛
printf(”从％s到％s的最短游览路径是：\n",g.vexs[v0］。name，g.vexs[i].name）;
printf（”％s->”，g.vexs［v0］。name)；
ppath(g,path1，i，v0）;
printf(”％s "，g.vexs[i］。name）；
printf(”路径长度：%d公里\n",dist[i］);
}
}/*由path1计算从v0到i的最短路径＊/

void Dijkstra(MGraph g,int v0，int p）/＊采用迪杰斯特拉算法求从顶点v0到顶点p的最短路径＊/
{
int dist［MAXV］，path1［MAXV]；
int s[MAXV]；
int mindis,i,j，u，n=g。vexnum;
for（i=0；ipath1[i］=—1;
}
s[v0］=1；path1[v0]=0;
for(i=0；i dist［j］=dist［u］+g。edges［u］[j]；
path1[j]=u；
}
}
dispath(g,dist，path1，s，n，v0，p）;/＊输出最短路径＊/
}

void Searchname(MGraph g)/*查询景点的信息＊/
｛
printf（"景点：\n"）；
printf(”--——--———————----—-—------—-----—-——---——-—-—---———---————-—-———-----—---—-———--\n"）；
printf(”\t\t1：锦屏山\n\t\t2：将军崖岩画\n”）;
printf（"\t\t3：古城\n\t\t4：孔子望角\n\t\t5：玉女峰\n\t\t6：江岭\n\t\t7：花果山\n"）；
printf(”\t\t8：猴嘴公园\n”)；
printf（”------—-————-——————-——-—-----—--——--————--———-—-——---—---—-—--—--—-—--—-—-—-————\n”);
int i；
char s;
while(1）
/＊可提供循环查询，当输入为’N'或’n’时，结束循环＊/
{
printf（"\t\t\t 请输入你要查询的景点："）；
scanf("％d”，＆i）；
for(int j=0；j〈g。vexnum；j++）
if（i==g.vexs[j].num）
{
printf（"%s简介：\n”,g.vexs[j].name）;
printf(”———----—-—---——----—-—-——--——-——-—-----—-—---—--—---—-——--—-—--——--—-———--—-—--—\n”);
printf（"％s”,g。vexs［j］.discription)；
printf("\n")；
}
printf（"---—-——---———————--—-————-—--——--———---——----———---—-——--—-—————--———————-—-——-—\n”)；
printf（"继续查询？(y或n):”)；
scanf("％s”，&s)；
if（s=='N’｜｜s==’n')
break；
｝
｝

void Searchpath1（MGraph g)
/*查询两个景点间的所有路径*/
{
printf（"景点：\n”）；
printf（”———-——-----—-—--—-—---—---——-—-—---———-——--—--————————-—————-———-————-—--—---—--\n"）；
printf(”\t\t1:锦屏山\n\t\t2：将军崖岩画\n”);
printf("\t\t3:古城\n\t\t4：孔子望角\n\t\t5:玉女峰\n\t\t6：江岭\n\t\t7:花果山\n”);
printf（”\t\t8：猴嘴公园\n"）;
printf("—-———-—------———--—-—-——--———--———-—————-———-—--——————-------—-—-———--——-—------\n"）;
int i,j;
char s；
while(1)
｛
printf（"\t\t\t 选择出发景点：”）;
fflush(stdin)；
scanf（”％d”,＆i）;
printf（”\t\t\t 选择目地景点："）;
fflush（stdin）;
scanf（”％d",＆j）;
for(int k=0;k if(j==g。vexs［l］.num） j=l；
printf（”从％s到%s的所有游览路径有:\n"，g。vexs［i］.name，g。vexs[j］.name)；
disppath（g，i,j);
printf（”—--———--------——-——---—-—------—----———-—-——-—-————--—--—-—--———-——---—————-———-\n"）；
printf（"继续查询？（y或n)：”）；
scanf("％s"，&s);
if（s==’N'||s=='n'）
break；
}
｝

void Searchpath2(MGraph g)
/＊查询两个景点间的最短路径＊/
｛
printf("景点：\n”）;
printf（”———————---——-——---—-----—---——————————-—-——-———----———-——---——--———-——--——---———\n”)；
printf（”\t\t1:锦屏山\n\t\t2:将军崖岩画\n”)；
printf（”\t\t3:古城\n\t\t4：孔子望角\n\t\t5:玉女峰\n\t\t6：江岭\n\t\t7:花果山\n")；
printf(”\t\t8:猴嘴公园\n”）;
printf（”——-——-——--—--—---—-—--—--—-—————-———-—---—————-—————-———-——----——————-—————--———\n"）;
int i,j;
char s;
while(1)
{
printf(”\t\t\t 选择出发景点：");
fflush(stdin）;
scanf（”％d”，＆i）；
printf(”\t\t\t 选择目地景点:"）;
fflush（stdin)；
scanf（"％d”，＆j)；
for（int k=0;k〈g.vexnum；k++)
if(i==g。vexs［k].num) i=k;
for（int l=0;l〈g。vexnum；l++)
if（j==g.vexs［l］。num) j=l;
Dijkstra(g,i，j）;
printf(”——---—-—-——---—-——-—--—-——-—-——-—--—---————————-—---—---—-----—-—-——-——--—-————-\n")；
printf（”继续查询?（y或n)："）；
scanf（”%s”,＆s）;
if（s==’N’｜|s==’n'）
break；
}
｝
void Searchpath3(MGraph g，char ＊c［]，char *d［]） // 动态添加景点
｛
printf("请输入你想添加的景点：\n"）;
printf(”——---—--—-——-——--—---———--——-————---———--—-——————————---—----—--—————-—-————-——-\n”）;
char s;
while（1）
{
printf（”景点名称：\n");
int i=0;
while（i〈n—1)
i++；
scanf(”%s”，&（g。vexs［i]。name）)；
c［i］=g.vexs[i].name;
printf（”景点简介：\n")；
scanf（”%s"，&(g.vexs［i］.discription)）；
d[i]=g。vexs[i].discription；

printf（"继续查询?(y或n）:”);;
scanf（”%s”，＆s）；
if（s=='N’||s==’n’)

break;
}
}

void main(）
//*主函数＊/
｛
int i，j；
int b［11］=｛1,2，3,4,5,6,7,8}；
char ＊c［11]={"锦屏山",”将军崖岩画”,"古城"，"孔子望角"，"玉女峰"，"江岭”，”花果山”，”猴嘴公园"｝；
char ＊d［11］={
"名称：锦屏山\n简介：因山色锦绣，美如画屏,而被康熙皇帝命名为锦屏山\n票价： 10”,
"名称：将军崖岩画\n简介:这是我国迄今发现的最古老时代岩画，是东南沿海地区首次发现的岩画\n票价：20",
"名称：古城\n简介：古城为黄土夯成，当年建筑时留下来的孔穴和层层夯印，现在仍历历在目\n票价:30",
"名称：孔子望角\n简介：这座由花岗岩、片麻岩构成的古老体，距今已有18亿年的历史\n票价：40",
"名称：玉女峰\n简介：岩壁秀润光洁，宛如玉石雕就,乘坐竹筏从水上望去，俨然是一位秀美绝伦的少女\n票价：50”,
"名称：江岭\n简介：河边聚集的三、四个村庄,四周围绕着青山,构成了一副极美的婺源农村风光画卷\n票价：60"，
"名称：花果山\n简介：景区内峭壁悬崖,层峦叠嶂，巍峨壮观，且植被丰富，景色秀丽，一年四季皆有特色\n票价:70"，
”名称：猴嘴公园\n简介：街道巷闾，纵横交错，高楼广厦，鳞次栉比，令人心旷神怡\n票价：80"};
MGraph g；
int A［11］［11］=｛
｛INF，13,INF，INF，INF,INF,INF,15}，
｛13,INF,5,INF,INF,15,12,INF}，
｛INF,5,INF，15，INF，INF,INF，5}，
{INF,INF，15，INF,10,INF,INF,INF}，
｛INF,INF,INF,10,INF，10，8，INF}，
{INF,15,INF,INF,10，INF，INF，12｝,
｛INF,INF，8,INF,INF，18，INF，INF｝,
{INF，INF，INF，18，INF,10，15，INF}};
g。vexnum=n;
g.arcnum=14;
for（i=0；ilect；

do
｛
system(”cls”）；
printf("—-—--—-—-—-—————----—-—-—---——连云港市导游咨询程序-----——-—-—-——————--—----—-——-\n”);
printf(”本程序能够：\n”)；
printf（"\n ┏━━━━━━━━━━━━━━━━━┓\n”）；
printf（" ┃ ┃\n"
printf(” ┃ 1、查询景点的信息 ┃\n”）；
printf（” ┃ 2、查询景点间的游览路径 ┃\n")；
printf(” ┃ 3、查询景点间的最短游览路径 ┃\n");
printf（” ┃ 4、输入您要添加的景点 ┃\n");
printf（" ┃ 5、退出 ┃\n"）;
printf(” ┃ ┃\n")；
printf（” ┗━━━━━━━━━━━━━━━━━┛\n"）;
printf（"—--——---——-—-—-—--—--——-—-—-—-—---—---——------——-———-——-—--—-——-------—-—--—--——\n”)；
printf(” 请输入您的选择：”);
scanf(”％d”,＆select）;
switch(select)
{
case 1：
Searchname（g）；/＊查询景点的信息＊/
break；
case 2:
Searchpath1（g）;/＊查询景点间的游览路径＊/
break；
case 3：
Searchpath2（g）;/＊查询景点间的最短游览路径*/
break；
case 4:
n=n+1;
Searchpath3(g,c，d）；/*查询动态添加的景点到各景点间的游览路径＊/
int w；
printf（”\n加了该新景点后的信息为:\n”）;
for(w=0;wect的值不为4时，继续循环＊/
}

4. 课程设计心得
这次课程设计运用到了大学c++语言和大二所学习到的数据结构知识点,课设题目要求不仅要求对课本知识有较深刻的了解，同时要求程序设计者有较强的思维和动手能力。刚开始拿到题目时，完全不知道如何下手，开始在网上找类似的，结果还真的找到了两份，这两份的思想是完全不一样的,起初想着参考一下，各取一半的思想，本来以为很简单就可以把程序调出来，可结果是没那么简单。
慢慢的按照老师计划书上的指示一步来一步来,首先，我必须先对我选的这个题目进行概要的分析、设计，分析出这个程序是干什么用的，应该实现什么功能,这些功能应该包含哪些函数，函数之间应该是怎样的调用关系.比如说我做的连云港市导游咨询，我就做的包括三方面：1、查询景点信息2、查询景点间的游览路径3、查询景点间的最短游览路径。4、添加动态景点。首先我必须知道景点的信息包括哪些，必须清楚的了解好信息才可以下手。
在主函数中主要调用了三个函数，分别是 Searchname（g）、Searchpath1(g)、Searchpath2（g），也就是通过这三个函数来实现我们要求的三个查询功能。比较难的是后两个，它们，调用的函数比较多，并且考虑的方面也要全面，在Searchpath1（g）调用的函数中，特别是path（MGraph g，int i，int j,int k