数据结构课程设计报告(含代码)

西安郵電學院

数据结构课程设计报告

题 目： 校园导航系统

院系名称： 计算机学院 专业名称： 计算机科学与技术

班 级： 学生姓名： 学号（8位）： 指导教师：

设计起止时间：2011年12月11日~2011年12月15日

一. 设计目的

1.通过本次课程设计巩固《数据结构》中所学的内容； 2.提高自己上机编程以及调试能力。

二. 设计内容

1.设计所在学校的校园平面图，所含景点不少于10个。以图中顶点表示校园内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。 2.为来访客人提供图中任意景点相关信息的查询。 3.为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。

三．概要设计 1．功能模块图；

图的建立与修改 景点信息介绍输入 各个景点的遍历 主程序 密码 校园平面图显示 景点信息路径查询 文件的读取与保存 退出程序

2．各个模块详细的功能描述。

1. 可以手动创建一个校园图。

2. 可以直接从文件读取校园各个景点的信息。 3. 可选择从任意个景点作为起点进行遍历。 4. 输入景点序号查询该景点相关信息。

5. 输入两个景点查询两个景点的最短，最佳及其所有的路径。 6. 将校园图信息保存入文件。

四．详细设计

1．功能函数的调用关系图

开始管理系统程序 输入密码 密码3次错误 判断密码 密码正确 显示menu 返 回 主菜 单 具体分函数 调用相应函数 执行函数相应的操作 是否退出？ 退出程序

main() arcnumfile() readvernum() vernumfile() readarcnum() creatdn() findvernum() search() shortload() locatevertex() creatvisited() depthfirstsearch() floyd() 2．各功能函数的数据流程图

1. Adjmatrix *g即结构体对象在main()中被创建在其他子函数中进行参数传递。 2. 全局变量visited数组 visited[] creatvisited() depthfirstsearch()

visited数组在creatvisited()中被初始化，然后再在depthfirstsearch()中用。 3. 全局变量shorest[][],path[][]

在floyd()中被赋值来分别记录v[i]-v[j]最短路径和 v[i]-v[j]所经过景点。

3．重点设计及编码

两景点最短距离 弗洛伊德算法

void floyd(adjmatrix *g) {

int i,j,k;

for(i=0;ivexnum;i++) for(j=0;jvexnum;j++) shortest[i][j]=0; for(i=0;ivexnum;i++) for(j=0;jvexnum;j++) { shortest[i][j]=g->arcs[i][j].adj; path[i][j]=0;

}

}

for(i=0;ivexnum;i++) for(j=0;jvexnum;j++) for(k=0;kvexnum;k++) if(shortest[i][j]>(shortest[i][k]+shortest[k][j])) { shortest[i][j]=shortest[i][k]+shortest[k][j]; path[i][j]=k; path[j][i]=k; }

五．测试数据及运行结果

1．正常测试数据和运行结果

要求提供3组正常测试数据和运行结果

2(遍历功能) 1(起始景点序号)

1 校门 呈长方形,校训:爱国、求实、奋进 2 喷泉 呈鸽子形状,喷射出水花 3 教学楼 传授知识和学习知识

4 实验楼 供学生进行课程实验和教师办公 5 洗浴中心 供学生洗澡,内设单人间和双人间 6 美食广场 仅一层,快餐味道不错

7 图书馆 共七层,存储大量书籍供学生查阅和学习 8 旭日苑 共三层,主要的就餐场所

9 体育馆 内设篮球场,羽毛球场和观看席 10 宿舍 休息的场所

5(查询景点信息) 2(景点序号)

2 喷泉 呈鸽子形状,喷射出水花

6(查询两景点最短路径) 1 9(两景点序号) 1->2->7->9

1->9 最短距离:570米

2．异常测试数据及运行结果

要求提供2组异常测试数据和运行结果

9

无此功能模块请重新输入

5(功能模块) 11(景点序号)

无此景点请重新输入

六．调试情况，设计技巧及体会

1．改进方案

1. 可将景点文件，边文件及账户密码合并为一个文件。

2. 可设管理员，是管理员才能进行创建和修改，而客户只能进行查询。 3. 可选用更好的算法，提升查询路径的速度。

2．体会

回顾起此课程设计，至今我仍感慨颇多，从理论到实践，在这段日子里，可以说得是苦多于甜，但是可以学到很多很多的东西，同时不仅可以巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的知识。通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能真正为社会服务，从而提高自己的实际动手能力和思考的能力。

七．参考文献

《数据结构》 杨剑 主编 清华大学出版社

《数据结构(C语言版)》 .严蔚敏_吴伟民.主编 清华大学出版社

八．附录：

源代码（电子版） #include #include

#include #include

#define maxsize 40 //最大景点数

#define infinity 32768 //两景点不可到距离长度 int visited[maxsize]; int path[maxsize][maxsize]; int shortest[maxsize][maxsize]; typedef struct { int top; char info[maxsize]; char introduce[maxsize]; }data;

typedef struct node { int adj; }node;

typedef struct { data vertex[maxsize]; node arcs[maxsize][maxsize]; int vexnum,arcnum;

}adjmatrix; void Cipher () { FILE *fp; char user0[20], user1[20], cipher0[10], cipher1[10], ch; int i; fp = fopen(\"Cipher.txt\ if((fp=fopen(\"Cipher.txt\ { printf(\"no user message!\\n\"); exit(1); } fscanf(fp, \"%s %s\ fclose(fp); printf(\"\\n\\┏━━━━━━━━━━━━━━━━━━━━━━━━┓\\n\"); printf(\"\\┃ XI'AN UNIVERSITY OF POSTS & TELLCOMUNICATIONS ┃\\n\"); printf(\"\\┃ ********* School Yard Guidebook ********* ┃\\n\"); printf(\"\\┗━━━━━━━━━━━━━━━━━━━━━━━━┛\\n\"); printf(\"\\ input user's name:\\"); scanf(\"%s\ printf(\"\\ intput cipher:\\"); for (i = 0; i<10; i++) { ch = getch(); if (ch == 13) break; printf(\"*\"); cipher1[i] = ch; } cipher1[i] = 0; printf(\"\\n\"); if(strcmp(user0, user1) != 0)

{ system(\"cls\");/*清屏*/ printf(\"error user's name!\\n\"); main(); } if(strcmp(cipher0, cipher1) != 0) { system(\"cls\");/*清屏*/ printf(\"error cipher!\\n\"); main(); } else { system(\"cls\");/*清屏*/ printf(\"\\n\\n\\ Welcome to The School Yard Guidebook! %s.....\\n\\n\ } }

void Browser() { system (\"color 0F\"); printf(\" 西安邮电学院平面图图 \"); printf(\"\\n\"); printf(\" 正门 \"); printf(\"\\n\"); printf(\" // || \\\\ \\\\ \"); printf(\"\\n\"); printf(\" // || \\\\ 行政楼 ===========\"); printf(\"\\n\"); printf(\" // 喷泉 \\\\ || || \"); printf(\"\\n\"); printf(\" 基础教学楼 || \\\\ || || \"); printf(\"\\n\"); printf(\" || || \\\\ || || \"); printf(\"\\n\"); printf(\" || || \\\\ || || \"); printf(\"\\n\"); printf(\" || || \\\\ || || \"); printf(\"\\n\"); printf(\" 实验楼 || 大学生活动中心 || \"); printf(\"\\n\"); printf(\" || || || \\\\ || \"); printf(\"\\n\"); printf(\" || || || \\\\ || \"); printf(\"\\n\"); printf(\" || == == 图书馆 == 人工湖 \\\\ || \"); printf(\"\\n\"); printf(\" || || \\\\ || \"); printf(\"\\n\"); printf(\" || || \\\\ || \"); printf(\"\\n\"); printf(\" || || \\\\ || \"); printf(\"\\n\"); printf(\" || ||=============东门 \"); printf(\"\\n\"); printf(\" || \");

printf(\"\\n\"); printf(\" || \"); printf(\"\\n\"); printf(\" 操场 ======================体育馆 \"); printf(\"\\n\"); printf(\" \\\\ || \"); printf(\"\\n\"); printf(\" \\\\ || \"); printf(\"\\n\"); printf(\" \\\\ || \"); printf(\"\\n\"); printf(\" \\\\ || \"); printf(\"\\n\"); printf(\" \\\\ || \"); printf(\"\\n\"); printf(\" \\\\ || \"); printf(\"\\n\"); printf(\" \\\\ || \"); printf(\"\\n\"); printf(\" =========食 堂 \"); printf(\"\\n\"); printf(\" || \"); printf(\"\\n\"); printf(\" || \"); printf(\"\\n\"); printf(\" ||===================宿舍 \"); printf(\"\\n\"); }

void PlaceList() { system (\"color 0A\"); printf(\"\\┏━━━━━━━━━━━━━━━━━━━━━━━━━┓\\n\"); printf(\"\\┃ 已存文件景点一览表 ┃\\n\"); printf(\"\\┣━━━━━━━━━━━━┳━━━━━━━━━━━━┫\\n\"); printf(\"\\┃1.学校正门 ┃2.喷泉 ┃\\n\"); printf(\"\\┣━━━━━━━━━━━━╋━━━━━━━━━━━━┫\\n\"); printf(\"\\┃3.教学楼 ┃4.实验楼 ┃\\n\"); printf(\"\\┣━━━━━━━━━━━━╋━━━━━━━━━━━━┫\\n\"); printf(\"\\┃5.洗浴中心 ┃6.美食广场 ┃\\n\"); printf(\"\\┣━━━━━━━━━━━━╋━━━━━━━━━━━━┫\\n\"); printf(\"\\┃7.图书馆 ┃8.旭日苑 ┃\\n\"); printf(\"\\┣━━━━━━━━━━━━╋━━━━━━━━━━━━┫\\n\"); printf(\"\\┃9.体育馆 ┃10.宿舍 ┃\\n\"); printf(\"\\┗━━━━━━━━━━━━┻━━━━━━━━━━━━┛\\n\"); }

int locatevertex(adjmatrix *g,int v) { int j,k; for(k=0;kvexnum;k++) if(g->vertex[k].top==v) { j=k; break; }

return(j); }

void creatdn(adjmatrix *g) { int i,j,k,weight; data v1,v2; printf(\"请输入景点数和边数:\\n\"); scanf(\"%d %d\ for(i=0;ivexnum;i++) for(j=0;jvexnum;j++) g->arcs[i][j].adj=infinity; for(i=0;ivexnum;i++) { printf(\"请输入该景点的序号,名称:\\n\"); scanf(\"%d\ gets(g->vertex[i].info); printf(\"请输入景点的信息:\\n\"); gets(g->vertex[i].introduce); } for(k=0;karcnum;k++) { printf(\"请输入第%d条边关联的两个景点:\\n\ scanf(\"%d %d\ printf(\"请输入距离:\\n\"); scanf(\"%d\ i=locatevertex(g,v1.top); j=locatevertex(g,v2.top); g->arcs[i][j].adj=weight; g->arcs[j][i].adj=weight; } }

void creatvisited(adjmatrix *g) { int i; for(i=0;ivexnum;i++) visited[i]=0; }

void depthfirstsearch(adjmatrix *g,int v) { int k; visited[v]=1; printf(\"景点序号:%d 名称:%s\\n\ for(k=0;kvexnum;k++) if(!visited[k]&&g->arcs[v][k].adj!=infinity) depthfirstsearch(g,k); }

int pat[maxsize],visited[maxsize]; int top=0;

void Depsearch(adjmatrix *G,int num1,int num2) {

int v,i;

top++; pat[top]=num1; visited[num1]=1; if(num1==num2){ for(i=0;i<=top;i++) printf(\"%s->\ printf(\"\\b\\b \\n\"); visited[num1]=0; top--; return ; } for(v=0;vvexnum;v++){ if(G->arcs[num1][v].adjvoid allways(adjmatrix *G) { int num1,num2,i; char c='y'; while(c=='y') { printf(\"请输入起始和终点的景点编号:\"); scanf(\"%d,%d\ top=-1; for(i=0;ivoid search(adjmatrix *g) { int i,n; creatvisited(g); for(i=0;ivexnum;i++) printf(\"%d\%s\\n\ printf(\"请输入遍历的起点序号:(1-%d)\\n\ scanf(\"%d\ depthfirstsearch(g,n-1); }

void vernumfile(adjmatrix *g) { FILE *fp; int i; fp=fopen(\"vernum.txt\ for(i=0;ivexnum;i++) fprintf(fp,\"%d %s %s\\n\ fclose(fp);

}

void arcnumfile(adjmatrix *g) { FILE *fp; int i,j; fp=fopen(\"arcnum.txt\ for(i=0;iarcnum;i++) for(j=0;jarcnum;j++) if(g->arcs[i][j].adj!=infinity) { fprintf(fp,\"%d %d %d\\n\ } fclose(fp); }

void readvernum(adjmatrix *g) { FILE *fp; int i=0; fp=fopen(\"vernum.txt\ while(fscanf(fp,\"%d %s %s\F) { printf(\"景点序号:%d 名称:%s\\n\ printf(\"景点信息:%s\\n\ printf(\"\\n\"); i++; } g->vexnum=i; fclose(fp); }

void readarcnum(adjmatrix *g) { FILE *fp; int i=0,j=0,k=0; for(i = 0 ; i < g->vexnum ; i++) for(j = 0 ; j < g->vexnum ; j++) g->arcs[i][j].adj = infinity; fp=fopen(\"arcnum.txt\ while(fscanf(fp,\"%d %d %d\ { g->arcs[i-1][j-1].adj=k; } fclose(fp); }

void findvernum(adjmatrix *g) { int i,n,a; char choice; for(i=0;ivexnum;i++) printf(\"%d\%s\\n\ printf(\"请选择查询方式的种类:\\n\"); printf(\"1.按序号\\n\"); printf(\"2.按名称\\n\"); scanf(\"%d\

do { printf(\"请输入要查询的景点序号(1-%d):\\n\ scanf(\"%d\ printf(\"景点名称:%s\\n\ printf(\"景点信息:%s\\n\ printf(\"\\n\"); printf(\"是否继续查询:(y/n):\\n\"); flushall(); scanf(\"%c\ }while(choice=='Y'||choice=='y'); }

void floyd1(adjmatrix *g) { int i,j,k; for(i=0;ivexnum;i++) for(j=0;jvexnum;j++) shortest[i][j]=0; for(i=0;ivexnum;i++) for(j=0;jvexnum;j++) { shortest[i][j]=g->arcs[i][j].adj; path[i][j]=0; } for(i=0;ivexnum;i++) for(j=0;jvexnum;j++) for(k=0;kvexnum;k++) if(shortest[i][j]>(shortest[i][k]+shortest[k][j])) { shortest[i][j]=shortest[i][k]+shortest[k][j]; path[i][j]=k; path[j][i]=k; } }

void shortload(adjmatrix *g) { int i,j,a,b; PlaceList(); floyd1(g); printf(\"请输入起始景点和终止景点(1-%d):\\n\ scanf(\"%d%d\ a=i; b=j; i=i-1; j=j-1; if(ii=path[j][i]; } printf(\"<-%d\ printf(\"\\n\\n\"); printf(\"%d->%d 距离是:%d米\\n\\n\ } else { printf(\"%d\ ///////////////////////// while(path[i][j]!=0) { printf(\"<-%d,path[i][j]+1\"); if(i%d\ printf(\"\\n\\n\"); printf(\"%d->%d 最短距离是:%d米\\n\\n\ } }

void suoyou(adjmatrix *g) { int i,j,a; printf(\"请输入起始景点和终止景点(1-%d):\\n\ scanf(\"%d%d\ a=j-i; for(;a>0;a--) printf(\"->%d\ }

meun() { char choice; adjmatrix *g; g=(adjmatrix *)malloc(sizeof(adjmatrix)); system (\"color 0C\"); while(1) { printf(\"\\n\"); printf(\"\\************************************************\\n\"); printf(\"\\***************校园景点导游系统 ***************\\n\"); printf(\"\\*****************欢迎您的使用 *****************\\n\"); printf(\"\\************************************************\\n\"); printf(\"\\**\ 1:创建景点信息 **\\n\"); printf(\"\\**\ 2:遍历景点信息 **\\n\"); printf(\"\\**\ 3:信息存入文件 **\\n\");

printf(\"\\**\ 4:读取文件信息 **\\n\"); printf(\"\\**\ 5:查询景点信息 **\\n\"); printf(\"\\**\ 6:查询最短路径 **\\n\"); printf(\"\\**\ 7:查询最佳路径 **\\n\"); printf(\"\\**\ 8:查询所有路径 **\\n\"); printf(\"\\**\ 9:查看景点地图 **\\n\"); printf(\"\\**\ 10:修改景点信息 **\\n\"); printf(\"\\**\ 0:退出查询系统 **\\n\");

printf(\"\\************************************************\\n\"); printf(\"\\************************************************\\n\"); printf(\"\\n\");

printf(\"请选择需要的服务:\\n\"); choice=getchar(); switch(choice) {

case '1': { creatdn(g); break; } case '2': { search(g); break; } case '3': { vernumfile(g); arcnumfile(g); break; } case '4': { readvernum(g); readarcnum(g); break; } case '5':{ findvernum(g); break; } case '6':{ shortload(g); break; } case '7':{ shortload(g); break; } case '8':{ allways(g); break; } case '9':{ Browser(g); break; }

case '0': {

printf(\"谢谢使用再见\\n\"); exit(0); } } printf(\"请按任意键继续.....\"); getch(); flushall(); system(\"cls\"); } }

main() { Cipher (); meun(); }