胡鹏《数据结构》课程设计报告2013-2014.doc

数据结构课程设计报告 38数据结构课程设计报告（2013 -2014学年 第 1 学期）题目：校园导航系统学号：111608020116 姓名： 胡鹏 指导教师: 方瑞英 信息科学与工程系目录1 需求分析21.1问题分析21.2基本要求32概要设计32.1主界面设计，32.2 存储结构设计42.3系统功能模块设计43模块设计53.1 模块设计53.2 系统子程序及功能设计54详细设计64.1数据类型定义64.2各个模块的程序流程图74.3关键代码分析说明95调试分析和测试结果116心得体会171 需求分析河南理工大学万方科技学院紧跟龙子湖校园开发工程的历史机遇，践行“厚德、博学、笃行、创新”校训，建设出一座美丽的校园。对河南理工大学万方科技学院校园导航系统的模拟，设计一个校园导航程序，为来访的客人提供各种信心查询服务网。1.1问题分析 为此通过对数据结构这一课程的应用，用图的模型对学校景点抽象。用邻接矩阵存储方法和狄克斯特拉算法及图的遍历实现对校园导游系统的模拟。此系统七个功能：浏览学校景点、查看单个景点信息、查看校园地图、导游推荐、查两景点最短路线、查两景点所有景点、退出系统。1.2基本要求首先是对校园整个的平面图输出；存储景点信息采用结构体；对各个景点用字母代替，字母组成图，通过对图的操作，求出制定最短路径，并且对图的整个遍历的操作。2概要设计2.1主界面设计， 图2-1 主控界面2.2 存储结构设计 图2-2 邻接矩阵 图2-3 校园平面图首先，由LOC-VERTEX(G,v)找到v在图G中的位置，即v在一维数组vexs中的序号i，则二维数组arcs中第i行上第一个adj域的值为“1”的分量所在列号j，便为v的第一个临界点在图G中的位置。通知，下一个邻接点在图G中的位置便为j列之后第一个adj的值为“1”的分量所在列号。2.3系统功能模块设计我设计有以下几个模块：（1） 身份验证（用户名和密码验证）（2） 校园导航系统的主界面输出；（3） 构造无向图采用数组表示法（邻接矩阵）存储；（4） 学校景点查询模块；（5） 学校景点平面图输出模块；（6） 计算最短路径算法的实现模块；3模块设计3.1 模块设计登陆界面是否正确导航主界面查询景点景点列表学校简介最短路径 图3-1 校园导航系统流程图3.2 系统子程序及功能设计(1) char Menu() / 主菜单 (2) char SearchMenu() / 查询子菜单(3) void search() / 查询景点信息(4) void CreateUDN / 采用数组（邻接矩阵）表示法，构造无向图G(5) void introduce() / 介绍函数(6) void pingmu() / 屏幕输出函数(7) void ShortestPath / 迪杰斯特拉算法最短路径函数 (8) void output / 输出函数3.3 函数主要调用关系图MenuintroduceSearchMenusearchpingmuCreateUDNShortestPathoutput 图3-2 主要函数调用关系图4详细设计4.1数据类型定义(1) 整型类型： adj; n; PNUMNUM; DNUM; i=0,a,j; i; v0,v1,i;flag; i,j; v,w,i,t; a,b,c,d,q=0; finalNUM;(2) 字符串类型：name20; c; ck; secret20; sight; description; info;4.2各个模块的程序流程图查询search1-15是否查询编号查询名称是否 图4-1 查询模块流程图开始数组edegesMAXEDGE边集数组；数组parentMAXVEX顶点数组；遍历顶点设置所有顶点parenti=0Int 1=0 1edges。Count设置n为edgesi.higen顶点的尾部下表Nm?结束Parentn = m设置m为edgesi.end顶点尾部下表I+;输出开始顶点Edgesi.start,结束顶点Edgesi.end，边为Edgesi图4-2 迪杰斯特拉算法流程4.3关键代码分析说明void CreateUDN(int v,int a) / 采用数组（邻接矩阵）表示法，构造无向图G。 int i,j; G.vexnum=v; / 初始化结构中的景点数！ ! G.arcnum=a;/ 初始化结构中的边数！ for(i=1;iG.vexnum;+i) G.vexi.number=i; / 初始化每一个景点的编号 / 初始化每一个景点名及其景点描述 G.vex0.sight=学校简介; G.vex1.sight=校大门; G.vex2.sight=三号楼学楼; G.vex3.sight=一号教学楼; G.vex4.sight=行政楼; G.vex5.sight=实验楼; G.vex6.sight=伯苓广场; G.vex7.sight=秀英图书馆; G.vex8.sight=艺术楼; G.vex9.sight=一号食堂; G.vex10.sight=操场; G.vex11.sight=西区宿舍楼; G.vex12.sight=二号食堂; G.vex13.sight=篮球场; G.vex14.sight=力功体育馆; G.vex15.sight=东区宿舍楼; / 这里把所有的边假定为32767(232次方)，含义是这两个景点之间是不可到达 。 for(i=1;iG.vexnum;+i) for(j=1;jG.vexnum;+j) G.arcsij.adj=Max;G.=NULL; /下边是可直接到达的景点间的距离，由于两个景点间距离是互相的/ ，所以要对图中对称的边同时赋值。 G.arcs12.adj=G.arcs21.adj=200; G.arcs13.adj=G.arcs31.adj=200; G.arcs110.adj=G.arcs101.adj=1000; G.arcs113.adj=G.arcs131.adj=1600; G.arcs23.adj=G.arcs32.adj=400; G.arcs26.adj=G.arcs62.adj=100; G.arcs34.adj=G.arcs43.adj=100; G.arcs37.adj=G.arcs73.adj=200; G.arcs47.adj=G.arcs74.adj=300; G.arcs56.adj=G.arcs65.adj=60; G.arcs67.adj=G.arcs76.adj=200; G.arcs68.adj=G.arcs86.adj=100; G.arcs710.adj=G.arcs107.adj=300; G.arcs711.adj=G.arcs117.adj=200; G.arcs810.adj=G.arcs108.adj=200; G.arcs910.adj=G.arcs109.adj=100; G.arcs912.adj=G.arcs129.adj=200; G.arcs1011.adj=G.arcs1110.adj=100; G.arcs1013.adj=G.arcs1310.adj=600; G.arcs1114.adj=G.arcs1411.adj=200; G.arcs1213.adj=G.arcs1312.adj=100; G.arcs1314.adj=G.arcs1413.adj=100; G.arcs1415.adj=G.arcs1514.adj=100;该模块是对图的建立及使用邻接矩阵存储顶点信息以及权值，而邻接矩阵特点是：邻接矩阵来表示一个具有n个顶点的有向图时需要n2个单元来存储邻接矩阵；对有n个顶点的无向图则只存入上（下）三角阵中剔除了左上右下对角线上的0元素后剩余的元素，故只需1+2+.+(n-1)=n(n-1)/2个单元。5调试分析和测试结果（1） 先是进入身份验证界面，如图所示5-1图5-1 身份验证界面（2） 验证成功后进入副界面，如图所示5-2图5-2 身份验证成功界面（3） 输入数字2，进入万科大导航系统主界面，如图所示5-3图5-3 万科大导航系统主界面（4） 输入数字1，进入万科大学校简介，如图所示5-4图5-4 万科大学校简介界面（5） 退出（ENTER），输入数字2，进入学校平面展示，如图所示5-5图5-5 学校平面展示界面（6） 退出（ENTER），输入数字3，进入景点展示界面，如图所示5-6图5-6 景点展示界面（7） 退出（ENTER），输入数字4，进入景点查询界面，如图所示5-7图5-7 景点查询界面（8） 输入数字1，进入按景点编号查询，如图所示5-8图5-8 景点编号查询（9） 输入1-15任何数字查看景点介绍，如图所示5-9图5-9 查看景点介绍界面（数字）（10） 按回车键返回，输入数字2进入按景点名称进行查询，如图所示5-10图5-10 景点名称进行查询界面（11） 按回车键返回到主界面，输入数字5进入计算最短路径算法查询，如图所示5-11图5-11 最短路径算法查询界面6心得体会 通过此次设计，明白了很多。首先要从设计的思路入手，思路决定出路，一个好的算法可以使工作量简化达到事半功倍的目的。平时生活更应该留心观察，多去想，多去做，好的程序是从历练中做出来的。其次，应该多去交流，去查阅资料，一个程序的产生不是那么容易的，更应该知难而进，积极进取。参考文献（至少两个）1数据结构（C语言版）严蔚敏 吴伟民 编2C语言程序设计教程杨路明 编3java开发实战经典李兴华 编4c语言程序设计（第四版）谭浩强 编附：源程序（可运行无误的代码）/-/校园导航系统/校园导航系统包括：学校简介，场所信息，计算路径/所使用的文件：Campus Navigation.cpp , 用户信息.text/程序编写人员：胡 鹏/编写程序时间：2013年10月30日 20:56:51/修改程序时间：2013年11月30日 14:38:32/代码规范时间：2013年12月10日 16:38:55/-/预处理命令#include#include /使用system函数#include#includevoid insert();#define N 10int n;#define Max 32767#define NUM 16typedef struct ArcCell int adj; / 相邻接的景点之间的路程 char *info;ArcCell; / 定义边的类型 typedef struct VertexType int number; / 景点编号 char *sight; / 景点名称 char *description; / 景点描述 VertexType; / 定义顶点的类型 typedef struct VertexType vexNUM; / 图中的顶点，即为景点 ArcCell arcsNUMNUM; / 图中的边，即为景点间的距离 int vexnum,arcnum; / 顶点数，边数 MGraph; / 定义图的类型 MGraph G; / 把图定义为全局变量 int PNUMNUM; /long int DNUM; / 辅助变量存储最短路径长度 void CreateUDN(int v,int a); / 创建图的函数 void pingmu(); /屏幕输出函数void introduce();/输入介绍内容，但不输出void ShortestPath(int num); /最短路径函数void output(int sight1,int sight2); /输出函数char Menu(); / 主菜单 void search(); / 查询景点信息 char SearchMenu(); / 查询子菜单 void NextValue(int); void display(); / 显示遍历结果 void show();/显示校园平面图void mainn();/-初始系统-struct student char name20; char secret20; ;struct student stuN;void pf()printf(nntt*信息工程与科学系数据结构课程设计*);printf(nnntt -);printf(n tt |t 名称： 万科大校园导航系统t|); printf(n tt |t 姓名： 胡鹏 t|); printf(n tt |t 班级： 1101网工 t|); printf(n tt |t 指导老师： 方瑞英 t|); printf(n tt |t 作者： 万科大校园 t|); printf(n tt -);/t表示的是向后空出8个空格,可以使自己输出字符更规范。/-身份验证-void main()/主函数char s210,s310,s410,s510,s610,s110,s710=0;int i=0,a,j; FILE *fp; /定义的fp是指向FILE类型结构体的指针。 可以使他指向某个文件的结构体变量/,从而通过该结构体变量中的文件信息能够访问该文件。if(fp=fopen(用户信息.txt,r)=NULL)/“r”为输出打开一个文本文档 printf(找不到 用户信息.txt文件!n); system(pause); /从程序里调用“pause”命令。 exit(0); else fscanf(fp,t%dn,&n);/fscanf(文件指针,格式字符串,输入文件表列) for(i=0;iN;i+) fscanf(fp,t%st%sn,,stui.secret); / 从一个流中执行格式化输入,fscanf遇到空格和换行时结束，注意空格时也结束。 /fscanf(文件指针，格式字符串，输入列表); fclose(fp); printf(nnnnnnnntt保存在用户信息.txt文件中的所有信息已经读入程序中!nnttt); system(pause); system(cls); for(i=0;i3;i+) pf();printf(nntt 用户登陆);printf(请输入用户名，你还有%d次机会。nttt,3-i);gets(s3); if(!strcmp(s3,s7) /strcmp比较两个字符串的大小 printf(用户名不能空格，谢谢！); printf(用户名不正确，请从新输入。n); system(pause);/从程序里调用“pause”命令。 system(cls);/从程序里调用“clear”命令。 if(i=2) printf(nnttt用户名不正确，按任意键退出。nnnttt); exit(0); continue; for(j=0;jN;j+) if(!strcmp(,s3) printf(用户名正确n); strcpy(s1,); strcpy(s2,stuj.secret); system(cls);/从程序里调用“clear”命令。 break; if(!strcmp(s1,s3)break;printf(用户名不正确，请从新输入。n);system(pause);/从程序里调用“pause”命令。 if(i=2) printf(用户名和密码不匹配，按任意键退出。n); system(pause);/从程序里调用“pause”命令。 exit(0); system(cls);/从程序里调用“clear”命令。 for(i=0;i3;i+) pf(); printf(nnt 用户登陆); printf(nn用户名正确n); printf(n请输入用户密码，你还有%d次机会。n,3-i); printf(密码正确，登陆成功时，系统将自动跳转n); gets(s4); if(!strcmp(s2,s4) system(cls);/从程序里调用“clear”命令。 break; Elseif(i=2) system(cls);/从程序里调用“clear”命令。 printf(nnnttt用户名和密码不匹配，按任意键退出。nnnttt);exit(0);elsesystem(cls);/从程序里调用“clear”命令。printf(输入错误，请从新输入:n);for(i=0;i+)pf();printf(ntt*n);printf(tt * 1.退出系统 * n); printf(tt * * n);printf(tt * 2.进入万科大导航系统 * n);printf(tt * * n);printf(tt * 3.新增用户信息 * n);printf(tt * * n); printf(tt * 0.修改密码 * n); printf(tt *n); printf(请选择功能n);scanf(%d,&a);if(a=1)printf(按任意键退出n);break;getchar(); if(a=2) mainn(); if(a=3) insert();if(a=0) for(i=0;i3;i+) system(cls);/从程序里调用“clear”命令。 pf(); printf(nn请输入原密码n); printf(两次不正确，系统将自动返回，你还有%d次机会。n,3-i-1); gets(s3); if(!strcmp(s2,s3) for(i=0;i+)printf(n请输入新密码n); gets(s6); printf(n请在此输入新密码n); gets(s5); if(!strcmp(s5,s6) system(cls);/从程序里调用“clear”命令。printf(新密码为: %sn,s5);strcpy(s2,s5);strcpy(stuj.secret, s2); if(fp=fopen(用户信息.txt,w)=NULL) printf(n保存失败!); exit(0); else for(i=0;iN;i+) fprintf(fp,t%st%sn,,stui.secret); fclose(fp); printf(新用户信息已保存在用户信息.txt中!n); system(pause); /从程序里调用“pause”命令。 system(cls); /从程序里调用“clear”命令。break; elsesystem(cls);/从程序里调用“clear”命令。printf(nn两次输入密码不一样，密码修改失败n);break; break; else printf(原密码输入错误n); printf(请珍惜机会，从新输入。); system(pause);/从程序里调用“pause”命令。 system(cls);/从程序里调用“clear”命令。 if(i=2) exit(0); /已经是第三次了，哈哈！ void insert() int i; FILE *fp; n+; printf(ntt输入新插入用户信息n); printf(n输入新用户名:); scanf(%s,); fflush(stdin); /清空输入缓冲区，通常是为了确保不影响后面的数据读取 printf(n输入新用户密码:); scanf(%s,stun.secret); if(fp=fopen(用户信息.txt,w)=NULL)/“w”为输出打开一个文本文档 printf(n保存失败!); exit(0); else fprintf(fp,t%dn,n);/fprintf(文件指针,格式字符串,输出文件表列) for(i=0;iN;i+) fprintf(fp,t%st%sn,,stui.secret); fclose(fp); printf(新用户信息已保存在用户信息.txt中!n); system(pause); system(cls);void mainn() / 万科大导航系统的主函数 int v0,v1,i; char ck; system(color 1b);/修改控制台的颜色信息 CreateUDN(NUM,16); do ck=Menu(); switch(ck) case1: system(cls); introduce(); printf(nntt%-25snn,G.vex0.description);/进入学校简介 getchar(); getchar(); break; case 2: show();/学校平面图 getchar(); getchar(); break; case 3: for(i=1;iNUM;i+) printf(%ctt(%2d)%s%cn,1,i,G.vexi.sight,1); / 输出景点列表 printf(nntttt请按回车键继续.n); getchar(); getchar(); break; case 4:search(); break; case 5: system(cls); for(i=1;iNUM;i+) printf(tt%ctt(%2d)%-20s%cttt,1,i,G.vexi.sight,1); / 输出景点列表 printf(nnttt请选择起点景点（115）：); scanf(%d,&v0); printf(ttt请选择终点景点（115）：); scanf(%d,&v1); ShortestPath(v0); / 计算两个景点之间的最短路径 output(v0,v1); / 输出结果 printf(nntttt请按回车键继续.n); getchar(); getchar(); break; while(ck!=6); system(cls);void show() printf(*万科大大学平面图*n);printf( 实验楼 n);printf( n);printf( n);printf( 三号教学楼 伯苓广场艺术楼 一号食堂 二号食堂 n);printf( n);printf( n);printf( 校大门 西区宿舍楼东区宿舍楼n);printf( n);printf( 一号教学楼 秀英图书馆 n);printf( n);printf( 操场 篮球场 n);printf( n);printf( 行政楼 力功体育馆 n); char Menu() / 主菜单 / char c; int flag; system(cls); do flag=1; pingmu(); introduce(); printf(tt * 1.学校简介 nn); printf(tt * 2.万科大校园平面简图 nn); printf(tt * 3.显示场所的编号 nn); printf(tt * 4.查看场所的具体信息 nn); printf(tt * 5.计算路径长度及找出最短路径nn); printf(tt * 6.退出 nn); printf(tt*n); printf(tttt请输入您的选择：); scanf(%c,&c); if(c=1|c=2|c=3|c=4|c=5|c=6) flag=0; while(flag); return c;/-查询-char SearchMenu() / 查询子菜单 char c; int flag; do flag=1; system(cls); pingmu(); introduce(); printf(ntt*n); printf(tt * n); printf(tt * 1、按照景点编号查询 n); printf(tt * 2、按照景点名称查询 n); printf(tt * 0、返回 n); printf(tt * n); printf(tt *n); printf(ttt请输入您的选择：); scanf(%c,&c); if(c=1|c=2|c=0) flag=0; while(flag); return c;void search() / 查询景点信息 int num; int i; char c; char name20; do system(cls); c=SearchMenu(); switch (c) case 1: system(cls); introduce(); for(i=1;iNUM;i+) printf(tt%ctt(%2d)%-20s%cttt,1,i,G.vexi.sight,1); / 输出景点列表 printf(nntt请输入您要查找的景点编号：); scanf(%d,&num); for(i=0;iNUM;i+) if(num=G.vexi.number) printf(nnttt您要查找景点信息如下:); printf(nnttt%-25snn,G.vexi.description); printf(nttt按任回车返回.); getchar(); getchar(); break; if(i=NUM)/只要上面FOR循环执行完毕，则i就是NUM printf(nnttt没有找到！); printf(nnttt按回车键返回.); getchar(); getchar(); break; case 2: system(cls); introduce(); printf(nntt请输入您要查找的景点名称：); scanf(%s,name); for(i=1;iNUM;i+) if(!strcmp(name,G.vexi.sight) printf(nnttt您要查找景点信息如下:); printf(nnttt%-25snn,G.vexi.description); printf(nttt按回车键返回.); getchar(); getchar(); break; if(i=NUM)/只要上面FOR循环执行完毕，则i就是NUM printf(nnttt没有找到！); printf(nnttt按回车键返回.); getchar(); getchar(); break; while(c!=0); getchar();/-构造无向图G-void CreateUDN(int v,int a) / 采用数组（邻接矩阵）表示法，构造无向图G。 int i,j; G.vexnum=v; / 初始化结构中的景点数！ ! G.arcnum=a;/ 初始化结构中的边数！ for(i=1;iG.vexnum;+i) G.vexi.number=i; / 初始化每一个景点的编号 / 初始化每一个景点名及其景点描述 G.vex0.sigh