数据结构课程设计校园导游系统Word文档下载推荐.docx
《数据结构课程设计校园导游系统Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计校园导游系统Word文档下载推荐.docx（25页珍藏版）》请在冰点文库上搜索。
{
charname[30];
intnum;
charintroduction[100];
//简介
}infotype;
Prim算法：
voidprim（MGraph*G）
FILE*fp;
fp=fopen（"
D:
sight.txt"
"
at+"
）;
if（fp==NULL）
printf（"
failtoopen!
!
\n"
else
{
intv,u,i,w,k,j,flag=1,p[10][10][10],D[10][10];
for（v=0;
v<
G->
vexnum;
v++）
for（w=0;
w<
w++）
D[v][w]=G->
arcs[v][w].adj;
for（u=0;
u<
u++）
p[v][w][u]=0;
if（D[v][w]<
INFINITY）
p[v][w][v]=1;
p[v][w][w]=1;
}
if（D[v][u]+D[u][w]<
D[v][w]）
D[v][w]=D[v][u]+D[u][w];
for（i=0;
i<
i++）
p[v][w][i]=p[v][u][i]||p[u][w][i];
while（flag）
printf（"
请输入出发点和目的地的编号:
"
scanf（"
%d%d"
&
k,&
j）;
if（k<
0||k>
vexnum||j<
0||j>
vexnum）
景点编号不存在!
请重新输入出发点和目的地的编号:
if（k>
=0&
&
k<
vexnum&
j>
j<
flag=0;
fprintf（fp,"
%s"
G->
vexs[k].name）;
if（p[k][j][u]&
k!
=u&
j!
=u）
-->
vexs[u].name）;
vexs[j].name）;
总路线长%dm\n"
D[k][j]）;
fclose（fp）;
}
迪杰斯特拉算法：
voidShortestPath_DIJ（MGraph*G）
approach.txt"
Failtoopen\n"
intv,w,i,min,t=0,x,flag=1,v0;
intfinal[20],D[20],p[20][20];
请输入一个起始景点编号:
scanf（"
%d"
v0）;
if（v0<
0||v0>
{
printf（"
请重新输入景点编号:
scanf（"
}
if（v0>
v0<
flag=0;
}//endwhile
final[v]=0;
D[v]=G->
arcs[v0][v].adj;
for（w=0;
p[v][w]=0;
if（D[v]<
{
p[v][v0]=1;
p[v][v]=1;
}
D[v0]=0;
final[v0]=1;
for（i=1;
min=INFINITY;
if（!
final[w]）
if（D[w]<
min）{v=w;
min=D[w];
final[v]=1;
for（w=0;
if（!
final[w]&
（min+G->
arcs[v][w].adj<
D[w]））
{
D[w]=min+G->
for（x=0;
x<
x++）
p[w][x]=p[v][x];
p[w][w]=1;
}
if（v0!
=v）
fprintf（fp,"
vexs[v0].name）;
if（p[v][w]&
w!
=v0）
fprintf（fp,"
vexs[w].name）;
t++;
if（t>
vexnum-1&
v0!
总路线长%dm\n\n"
D[v]）;
}//endfor
}//endif
}//ShortestPath_DIJend
五．测试数据及运行结果
1．正常测试数据和运行结果
2．异常测试数据及运行结果
六．调试情况，设计技巧及体会
1．改进方案
对于我的设计，合理之处是对每一次查询都以文件的形式进行了存储，其次，校园的平面图比较好的展现了我们学校的风貌。
不足之处是使用prim算法的时候，若终点输入不合法，程序会陷入，死循环。
这是致命的错误，我的改进方法是若输入字符不合法，则跳出循环，再次输入，直到合法为止。
利用迪杰斯特拉算法在计算到剩下的顶点的最短距离时第一个for循环时时间复杂度是O（n），每进行一次第二个for循环的时间复杂度都是O（n），第三个for循环也就是存储途经顶点时用的循环而不是书中算法所用的只是个地址的赋值，所以时间复杂度也是O（n），这样总的时间复杂度就是O（n3）。
改进设想主要就是给用户一个浏览路线的推荐本来在程序设计初期是计划要实现这个功能的，但是由于时间和能力问题没有去实现，因为它涉及到汉密尔顿路的实现，目前感觉还比较复杂所以暂时放弃了，日后如果有机会一定将这个功能完善。
2．体会
调试过程中难免会遇见这样或者那样的问题，一个很低级的错误就是在字符串的赋值上居然还会出错，本来是不可以像int型数据那样直接用等于号赋值的，可是刚开始由于失误却犯了这样低级的错误结果导致出现102个错误，当时确实有点慌了，等冷静下来一想才把问题想明白，字符串的赋值必须用strcpy函数。
看来基本功还是相当的重要的。
此外，迪杰斯特拉算法其实放在这里多少有些不合适，因为不管在求任意两个景点之间的最短路径还是求某一景点到其它景点的最短路径时都要完全的执行一遍算法时间复杂度是很高的，当时在实现时也确实考虑到了这个问题只是后来感觉要是实现时间复杂度的降低不是很简单也就暂时放弃了，也就选择了将这个算法直接搬了过来，这里是一点败笔，尚需要改进。
七．参考文献
《数据结构》严蔚敏吴为民
《C语言程序设计（第三版）》谭浩强
八．附录：
源代码（电子版）
#defineINFINITY10000/*无穷大*/
#defineMAX_VERTEX_NUM40
#defineMAX40
#include<
stdlib.h>
stdio.h>
conio.h>
string.h>
typedefstructArCell
intadj;
//路径长度
}ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedefstruct
infotypevexs[MAX_VERTEX_NUM];
AdjMatrixarcs;
intvexnum,arcnum;
}MGraph;
MGraphb;
voidcmd（void）;
MGraphInitGraph（void）;
voidMenu（void）;
voidBrowser（MGraph*G）;
voidShortestPath_DIJ（MGraph*G）;
voidPrim（MGraph*G）;
voidSearch（MGraph*G）;
intLocateVex（MGraph*G,char*v）;
MGraph*CreatUDN（MGraph*G）;
voidprint（MGraph*G）;
voidmap（）;
/******************************************************/
voidmain（void）
system（"
modecon:
cols=100lines=30"
cmd（）;
voidcmd（void）
inti;
b=InitGraph（）;
Menu（）;
i）;
while（i!
=6）
switch（i）
case1:
Browser（&
b）;
Menu（）;
break;
case2:
map（）;
case3:
ShortestPath_DIJ（&
case4:
Floyd（&
case5:
Search（&
case6:
exit
（1）;
default:
MGraphInitGraph（void）
MGraphG;
inti,j;
G.vexnum=10;
G.arcnum=14;
G.vexnum;
G.vexs[i].num=i;
strcpy（G.vexs[0].name,"
旭日苑"
strcpy（G.vexs[0].introduction,"
难吃,洗过的筷子上面都是菜叶子"
strcpy（G.vexs[1].name,"
校医院"
strcpy（G.vexs[1].introduction,"
校医院，名副其实的校（shou）医（yi）院（yuan）"
strcpy（G.vexs[2].name,"
大学生活动中心"
strcpy（G.vexs[2].introduction,"
又名大活,举办一些没什么卵用的晚会"
strcpy（G.vexs[3].name,"
美食广场"
strcpy（G.vexs[3].introduction,"
吃货的天堂,完爆旭日苑"
strcpy（G.vexs[4].name,"
图书馆"
strcpy（G.vexs[4].introduction,"
Warning学霸出没"
strcpy（G.vexs[5].name,"
足球场"
strcpy（G.vexs[5].introduction,"
国足的未来......23333333"
strcpy（G.vexs[6].name,"
水煮鸽子"
strcpy（G.vexs[6].introduction,"
然而他并不能吃"
strcpy（G.vexs[7].name,"
东区教学楼"
strcpy（G.vexs[7].introduction,"
又名尼伯龙根,进去就不要想出来"
strcpy（G.vexs[8].name,"
狗男女湖"
strcpy（G.vexs[8].introduction,"
湖边时常回荡着单身狗的哀嚎"
strcpy（G.vexs[9].name,"
澡堂"
strcpy（G.vexs[9].introduction,"
洗个澡,压压惊"
for（j=0;
j++）
G.arcs[i][j].adj=INFINITY;
G.arcs[0][1].adj=100;
G.arcs[0][2].adj=200;
G.arcs[0][6].adj=400;
G.arcs[1][7].adj=300;
G.arcs[2][3].adj=120;
G.arcs[3][6].adj=220;
G.arcs[3][4].adj=100;
G.arcs[4][5].adj=300;
G.arcs[4][9].adj=250;
G.arcs[5][9].adj=350;
G.arcs[6][7].adj=60;
G.arcs[6][9].adj=200;
G.arcs[7][8].adj=50;
G.arcs[8][9].adj=20;
G.arcs[j][i].adj=G.arcs[i][j].adj;
returnG;
}//InitGraphend
voidMenu（）
{
\n西安邮（mei）电（dian）大学\n"
┏━━━━━━━━━━━━━━━━━━━━┓\n"
┃1.校园景点介绍┃\n"
┃2.校园平面图┃\n"
┃3.查看所有游览路线（jiandan）┃\n"
┃4.选择出发点和目的地（zuiduan）┃\n"
┃5.查看景点信息┃\n"
┃6.退出系统┃\n"
┗━━━━━━━━━━━━━━━━━━━━┛\n"
Option-:
voidBrowser（MGraph*G）
intv;
┏━━┳━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓\n"
┃编号┃景点名称┃简介┃\n"
┃%-4d┃%-16s┃%-56s┃\n"
vexs[v].num,G->
vexs[v].name,G->
vexs[v].introduction）;
┗━━┻━━━━━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛\n"
//迪杰斯特拉算法来计算出起点到各个顶点之间的最短路径,v0为起点
请稍候......\n"
文件已经成功地保存至D:
/approach.txt!
voidSearch（MGraph*G）
intk,flag=1;
请输入要查询的景点编号:
k）;
┏━━┳━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓\n"
vexs[k].num,G->
vexs[k].name,G->
vexs[k].introduction）;
┗━━┻━━━━━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛\n"
}//Searchend
intLocateVex（MGraph*G,char*v）
intc=-1,i;
if（strcmp（v,G->
vexs[i].name）==0）
{c=i;
returnc;
voidprint（MGraph*G）
intv,w,t=0;
for（v=0;
{if（G->
arcs[v][w].adj==INFINITY）
∞"
elseprintf（"
%-7d"
arcs[v][w].adj）;
if（t%G->
vexnum==0）
voidPrim（MGraph*G）
G
升级会员 