校园导航问题数据结构设计.doc

1、数 据 结 构课程设计说明书题 目校园导航问题学 号1067111204姓 名范振辉指导教师周李涌日 期2012-6-17至2012-6-27内蒙古科技大学课程设计任务书课程名称数据结构课程设计设计题目校园导航问题指导教师 时间2012.62012.7一、教学要求1. 掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力2. 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能3. 提高综合运用所学的理论知识和方法独立分析和解决问题的能力4. 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风二、设计资料及参数每个学生在教师提

2、供的课程设计题目中任意选择一题，独立完成，题目选定后不可更换。校园导航问题自主选择存储结构表示校园平面图，在此基础上实现求校园任意两点的最短路径。要求设计类（或类模板）来描述图，包含必要的构造函数和析构函数，以及其他能够完成如下功能的成员函数：v 输入图、输出图v 查询给定建筑信息v 求校园平面图中任意两点的最短路径，并输出路径及路径长度v 任意输入两点，查询出该两点是否存在最短路径 并设计主函数测试该类（或类模板）。三、设计要求及成果1. 分析课程设计题目的要求2. 写出详细设计说明3. 编写程序代码，调试程序使其能正确运行4. 设计完成的软件要便于操作和使用5. 设计完成后提交课程设计报告

3、四、进度安排资料查阅与讨论（1天）系统分析（2天）系统的开发与测试（5天）编写课程设计说明书和验收（2天）五、评分标准1. 根据平时上机考勤、表现和进度，教师将每天点名和检查2. 根据课程设计完成情况，必须有可运行的软件。3. 根据课程设计报告的质量，如有雷同，则所有雷同的所有人均判为不及格。4. 根据答辩的情况，应能够以清晰的思路和准确、简练的语言叙述自己的设计和回答教师的提问六、建议参考资料1数据结构 （C语言版）严蔚敏、吴伟民 主编 清华大学出版社 2004.112数据结构课程设计案例精编（用C/C+描述），李建学 等 编著，清华大学出版社 2007.23.数据结构:用面向对象方法与C+

4、语言描述，殷人昆 主编，清华大学出版社 2007.6目录第1章 需求分析3第2章 总体设计3第3章 抽象数据类型定义33.1 抽象数据类型的设计33.2 抽象数据类型的设计4第4章 详细设计44.1 工程视图44.2 类图视图44.3 函数的调用关系44.4 主程序流程图54.5 主要算法的流程图5第5章 测试5第6章 总结5附录：程序代码5第1章 需求分析以邻接表的存储结构存储校园平面图，在此基础上实现求校园任意两点的最短路径。要求设计类（或类模板）来描述图，包含必要的构造函数和析构函数，以及其他能够完成如下功能的成员函数：v 输入图、输出图v 查询给定建筑信息v 求校园平面图中任意两点的最

5、短路径，并输出路径及路径长度v 任意输入两点，查询出该两点是否存在最短路径v 设计主函数测试该类（或类模板）。第2章 总体设计系统的功能结构：v 输入创建图、输出图v 查询给定建筑信息v 求校园平面图中任意两点的最短路径，并输出路径及路径长度v 任意输入两点，查询出该两点是否存在最短路径。输出平面图系统功能查询建筑信息输校园平面出图任意两点最短路径指定两点最短路径图的创建与修改创建查找离你最近的建筑小组分工：范振辉负责主函数菜单函数的控制，图的创建、修改，文件保存、读取等。李健主要负责查询建筑型，任意两点最短路径（具体由他本人详述），杨广振主要负责查找最近建筑，指定最短路径（具体由他本人详述）

6、。第3章 抽象数据类型定义3.1 ADT CampusGraph抽象数据类型的设计ADT CampusGraph数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。数据关系R：R=VRVR=|v,wV且p(v,w),表示从v到w的弧，谓词p(v,w)定义了弧的意义或信息 基本操作：int CreateGraph();初始条件：CampusGraph 的对象存在。操作结果：按V和VR的定义构造图G。int LocateVex(VertexType v)初始条件：顶点V存在操作结果：给一个正确的顶点 V ，输入成功返回V 的序号，否则 返回-1。int FirstAdjVex(VertexT

7、ype);初始条件：顶点V存在操作结果：给一个正确的顶点 V ，输入成功返回返回V的第一个邻接点，否则 返回-1。int NextAdjVex(VertexType ,VertexType);初始条件：顶点V存在操作结果：给一个正确的顶点 V ，输入成功返回V的继W后的下一个邻接点，否则 返回-1。VertexType GetVex( int N);初始条件：0N20操作结果：给一个正确的顶点序号N ，输入成功返回序号为N的顶点，否则 返回-1。void DestroyGraph();初始条件：图存在操作结果：销毁导航图。int PutVex(VertexType V1,VertexTypeV

8、2); 初始条件：顶点V存在；操作结果：对V1赋新值V2；输入成功返回1，否则 返回-1。void InsertVex(VertexType);初始条件：顶点V存在；操作结果：对V1赋新值V2；输入成功返回1，否则 返回-1。/增加新顶点int DeleteVex(VertexType v);初始条件：顶点V存在；操作结果：对V1赋新值V2；输入成功返回1，否则 返回-1。/ 删除图中顶点v及其相关的弧。int InsertArc(VertexType v, VertexType w);初始条件：顶点V存在；操作结果：在G中增添弧,对称弧；输入成功返回1，否则 返回-1。int DeleteA

9、rc(VertexType v,VertexType w);初始条件：顶点V,W存在；操作结果：在G中删除弧,对称弧;输入成功返回1，否则 返回-1。int SaveInfo();初始条件：文件“数据。txt”存在；操作结果：把图的信息保存到文件。void DFS(int v);初始条件：0N20；操作结果：从第v个顶点出发递归地深度优先遍历图G。void DFSTraverse();初始条件：图存在操作结果：对图G作深度优先遍历。void Shuchu();初始条件：图存在操作结果：以校园平面坐标形式输出图中信息。 ADT CampusGraph3.2 LinkQueue抽象数据类型的设计A

10、DT LinkQueue数据对象V：V是具有相同特性的数据元素的集合，称为结点集。数据关系R：基本操作：int InitQueue(L);初始条件：队列L存在；操作结果：初始化L构造一个空队列L;输入成功返回1，否则 返回-1。int EmptyQueue();初始条件：队列L存在；操作结果：判断队列是否为空 是返回1，否则 返回0。int EnQueue(QElemType );初始条件：队列L存在；操作结果：插入元素e为Q的新的队尾元素;输入成功返回1，否则 返回-1。int DeQueue( QElemType & );初始条件：队列L存在；操作结果：若队列不空,删除Q的队头元素,用p返

11、回其值;输入成功返回1，否则 返回-1 ADT LinkQueue3.3 Shuzu抽象数据类型的设计ADT Shuzu数据对象aij是具有相同特性的数据元素的字符数组。数据关系R：基本操作：void InitShuzu(int i,int j);初始条件：数组A存在，i j 不越界；操作结果：初始化A构造一个中间为空四周是#号的图，并产生第一个终点，输入成功返回1，否则 返回-1。int Drawxian(int,int);初始条件：数组A存在，i j 不越界；操作结果：从上一次终点开始沿线赋值画线的功能，并产生新的终点，输入成功返回1，否则 返回-1。int Drawxian(int,in

12、t,int,int);初始条件：数组A存在，i j k l不越界；操作结果：在（i，j）（k,l）两点之间画线，成功返回1，否则 返回-1。int Drawdian(int ,int );初始条件：数组A存在，i j 不越界；操作结果：产生第一个终点，输入成功返回1，否则 返回-1。void Display();初始条件：数组A存在， 不越界；操作结果：输出数组中的图，输入成功返回1，否则 返回-1。 ADT LinkQueue第4章 详细设计4.1 工程视图说明有几个源代码文件，可以截取工程文件视图表示图4.1 工程文件视图4.2 类图视图 图4.2文件包含的类和函数说明4.3 函数的调用关

13、系如下图：图4.3函数的调用关系4.4 主程序流程图图4.4修改函数的调用关系流程图4.5 主要算法的流程图图4.5创建图的主要算法第5章 测试程序的运行结果截图图5.1首次运行，录入信息图5.2再次进入系统 读取已有文件信息图5.3创建图后 显示平面图中建筑的位置图5.4创建图后 显示平面图中建筑的位置以及它们之间的路径图5.5创建图后 进入主菜单图5.6选择1 进入修改菜单图5.7选择1修改顶点信息，如果输入的顶点名称没有 提示重新输入，修改信息。图5.8选择2增加顶点，如果输入的顶点名称越界 提示重新输入，增加信息。图5.9选择3增加路径，输入已存在的顶点名称 如果错误提示重新输入，增加

14、路径。图5.10选择4删除顶点，如果输入的顶点名称没有 提示重新输入，删除顶点。图5.11选择5删除路径，如果输入的顶点名称没有 提示重新输入图5.12选择6输出平面位置图，路径图。图5.13选择7 深度优先输出图，并按图的路径信息，输出平面遍历的路径图图5.14选择8 销毁图，重新创建图。图5.15选择9 保存图的信息到文件，下一次可以不必手写输入信息图5.16选择9之后再选择8 从保存的文件中读取图的信息，不必手写输入信第6章 总结在这次的小组合作共同来做校园导航系统的过程中，我体会到了与人合作的重要意意和基本的方式方法，不仅锻炼了自己的编程实践的能力，也提升了自己的语言表达能力和与人合作

15、的能力。这次的校园导航系统的设计过程中，我同样遇到了不少的问题。对类的设计有了更为深刻的理解，自己也对C+编程更为熟悉了。在对图的设计过程中是我掌握了图的基本运算的函数的算法的理解和程序的有效吸收。包括图的深度和广度优先的遍历，对图的联通分量的求解，图的最小生成树。以及图的拓扑排序、图的关键路径和用地杰斯特拉算法的基础上计算任意；两点间的最短距离及其顺序路径问题。在这次的实践练习中，提升了自己的编程能力和个方面的技巧，也提高了自己的与人交际及合作的能力。附录：程序代码/*类的声明定义文件“head.h”#include #include#include #include #include /*

16、 图的邻接表存储表示*#define MAX_NAME 10/ 顶点字符串的最大长度#define MAX_JIANJIE 100/简介字符串最大长度#define MAX_VERTEX_NUM 20/最大顶点数typedef double InfoType;/ 存放网的权值 / * 顶点类型定义*typedef struct char nameMAX_NAME+1; /地点名称char jianjieMAX_JIANJIE+1; /地点简介int x,y;/地点坐标 VertexType; / * 边结点类型定义*typedef struct ArcNodeint adjvex; / 该弧所

17、指的邻接点域 struct ArcNode *nextarc; / 指向下一条弧的指针 InfoType info; / 网的权值 ArcNode;/ * 顶点向量类型定义*typedef struct VNodeVertexType data; / 顶点信息 ArcNode *firstarc; / 第一个表结点的地址,指向第一条依附该顶点的弧的指针 VNode,AdjListMAX_VERTEX_NUM; / 顶点结点，顶点向量 typedef VertexType QElemType; / 队列类型 / * 单链队列队列的链式存储结构*typedef struct QNodeQElemT

18、ype data; /数据域struct QNode *next; /指针域QNode,*QueuePtr;/队结点/*队列类的定义*class LinkQueueQueuePtr front,/队头指针，指针域指向队头元素rear;/队尾指针，指向队尾元素public:int InitQueue();/构造一个空队列Q。int EmptyQueue();int EnQueue(QElemType );/插入元素e为Q的新的队尾元素int DeQueue( QElemType & );/若队列不空,删除Q的队头元素,用p返回其值;class CampusGraphprivate:LinkQue

19、ue LQueue;AdjList vertices;int vexnum,arcnum;/ 图的当前顶点数和弧数 public:LinkQueue GetQueue();/返回队列void Shuchu();int CreateGraph();/ 采用邻接表存储结构,构造导航图int LocateVex(VertexType);/返回该顶点在图中存储位置编号int FirstAdjVex(VertexType);/返回V的第一个邻接点int NextAdjVex(VertexType ,VertexType);/返回V的继W后的下一个邻接点VertexType GetVex( int );/

20、返回序号为v的顶点int Getvexnum();int Getarcnum();void DestroyGraph();/销毁导航图int PutVex(VertexType ,VertexType);/ 对v赋新值evoid InsertVex(VertexType);/增加新顶点int DeleteVex(VertexType v);/ 删除图中顶点v及其相关的弧。int InsertArc(VertexType v, VertexType w);/ 在G中增添弧,对称弧int DeleteArc(VertexType v,VertexType w);/ 在G中删除弧,对称弧。int S

21、aveInfo();/保存信息到文件void DFS(int v);/从第v个顶点出发递归地深度优先遍历图Gvoid DFSTraverse();/对图G作深度优先遍历。/*广振void DFS1(int v, double x1, double y1);void ShortestBuilding();double ReturnInfo(VertexType k, VertexType j);void MiniSpanTree_PRIM();int SearchVex(char a5);void Shortestpath_DIJ();/*李健void Sightintroduce();char

22、 InqurieMenu();void Inquire(); / 查询景点信息int ReturnInfo(int k, int j);void ShortestPath(int PMAX_VERTEX_NUMMAX_VERTEX_NUMMAX_VERTEX_NUM,int DMAX_VERTEX_NUMMAX_VERTEX_NUM);/查询最短路径任意两点之间void ShortestPathdisplay();class Shuzuprivate:char a2380;public:void InitShuzu(int,int);/初始化数组，并产生第一个终点int Drawxian(in

23、t,int);/从上一次终点开始沿线赋值，并产生新的终点int Drawxian(int,int,int,int);int Drawdian(int ,int );void Display();/显示数组中的图;/*关震的typedef struct VertexType adjvex1;double lowcost;closedgeMAX_VERTEX_NUM;/*类成员函数的实现文件“class.cpp”#includehead.h#include #include #include int visitedMAX_VERTEX_NUM;/ 访问标志数组(全局量)/*广振的closedge

24、h;int finalMAX_VERTEX_NUM;/finalv为true当且仅当v属于S,即已将求得/从v0到v的最短路径double DMAX_VERTEX_NUM;/记录从v0到v的最短路径int pMAX_VERTEX_NUMMAX_VERTEX_NUM;/pvw为true,则w是从v0到v当前求/的最短路径上的顶点int min;/记录离你最近的建筑的序号double mlen;/记录离你最近的建筑物的距离/ 若G中存在顶点v,则返回该顶点在图中位置;否则返回-1。 int CampusGraph:LocateVex(VertexType v)int i;for(i=0;i=0)/

25、p = verticesi.firstarc;if(p)return p-adjvex;elsereturn -1;/这是孤立顶点 没有第一个邻接点return -2;/没有这个节点，无法找到邻接点/返回V的继W后的下一个邻接点序号int CampusGraph: NextAdjVex(VertexType v,VertexType w)ArcNode *p;int v1,w1;v1 = LocateVex(v);/ v1为顶点v在图G中的序号 w1 = LocateVex(w);/ w1为顶点w在图G中的序号 p = verticesv1.firstarc;while(p&p-adjvex

26、!= w1)/ 指针p不空，且所指表结点序号不是w，继续向下查找p = p-nextarc;if(!p|!p-nextarc) / 没找到w1，或w1是最后一个邻接点 return -1;else / 返回v的(相对于w的)下一个邻接顶点的序号 return p-nextarc-adjvex;/ 此时p-adjvex=w / 采用邻接表存储结构,构造导航图。int CampusGraph:CreateGraph()int i,j,k;int flag;VertexType va,vb;ArcNode *p;if ( fopen(数据.txt,r) )char ck;int ck1;ifstre

27、am file ( 数据.txt ,ios:in) ;cout已保存有校园图的信息，是否读取已存信息（Y/N）ck;do if (ck1=(ck!=Y & ck!=y&ck!=N & ck!=n)cout输入错误，请重新输入ck; while (ck1);if (ck=Y | ck=y)cout按任意键开始读取文件.vexnum;filearcnum;for(i = 0; i verticesi.data.name;fileverticesi.data.jianjie;fileverticesi.data.x;fileverticesi.data.y;verticesi.firstarc =

28、NULL; for(k = 0;k va.name;filevb.name;i = LocateVex(va);/ 尾 va=GetVex(i);j = LocateVex(vb);/ 头 vb=GetVex(j);p = (ArcNode*)malloc(sizeof(ArcNode);p-adjvex = j;p-info = abs(va.x-vb.x)+abs(va.y-vb.y); / 根据两点坐标自动计算权值 p-nextarc = verticesi.firstarc; / 插在表头 verticesi.firstarc = p;/ 无向图,产生第二个表结点 p = (ArcNo

29、de*)malloc(sizeof(ArcNode);p-adjvex = i;p-info = abs(va.x-vb.x)+abs(va.y-vb.y);p-nextarc = verticesj.firstarc; / 插在表头 verticesj.firstarc = p;file .close();cout读取完毕！endl;return 1;elsecoutttt请按回车键开始手工录入.endl;getchar();doflag=1;cout请输入图的顶点数和边数:（顶点数应小于20，顶点以空格作为间隔）vexnumarcnum;if(vexnum 0 & vexnum 20)fl

30、ag=0;else cout输入错误，请重新输入endl;while(flag);for(i = 0; i verticesi.data.name;printf(请输入第%d个顶点的简介(小于%d个字符):n,i+1,MAX_JIANJIE);cinverticesi.data.jianjie;doflag=1;printf(请输入第%d个顶点的坐标(x 80,yverticesi.data.xverticesi.data.y;if(verticesi.data.x 0 & verticesi.data.x0 & verticesi.data.y23)flag=0;else cout输入错误，

31、请重新输入;while(flag);verticesi.firstarc = NULL; for(k = 0;k va.name;cinvb.name;i = LocateVex(va);/ 尾 va=GetVex(i);j = LocateVex(vb);/ 头 vb=GetVex(j);p = (ArcNode*)malloc(sizeof(ArcNode);p-adjvex = j;p-info = abs(va.x-vb.x)+abs(va.y-vb.y); / 根据两点坐标自动计算权值 p-nextarc = verticesi.firstarc; / 插在表头 verticesi.

32、firstarc = p;/ 无向图,产生第二个表结点 p = (ArcNode*)malloc(sizeof(ArcNode);p-adjvex = i;p-info = abs(va.x-vb.x)+abs(va.y-vb.y);p-nextarc = verticesj.firstarc; / 插在表头 verticesj.firstarc = p;return 1;/if ( !fopen(数据.txt,r) )elsecout 本次可能是首次运行，尚未保存过信息,请您先录入信息 endlendl;coutttt请按回车键开始手工录入.endl;getchar();doflag=1;c

33、out请输入图的顶点数和边数:（顶点数应小于20，顶点以空格作为间隔）vexnumarcnum;if(vexnum 0 & vexnum 20)flag=0;else cout输入错误，请重新输入endl;while(flag);for(i = 0; i verticesi.data.name;printf(请输入第%d个顶点的简介(小于%d个字符):n,i+1,MAX_JIANJIE);cinverticesi.data.jianjie;doflag=1;printf(请输入第%d个顶点的坐标(x 80,yverticesi.data.xverticesi.data.y;if(vertice

34、si.data.x 0 & verticesi.data.x0 & verticesi.data.y23)flag=0;else cout输入错误，请重新输入;while(flag);verticesi.firstarc = NULL; for(k = 0;k va.name;cinvb.name;i = LocateVex(va);/ 尾 va=GetVex(i);j = LocateVex(vb);/ 头 va=GetVex(i);p = (ArcNode*)malloc(sizeof(ArcNode);p-adjvex = j;p-info = abs(va.x-vb.x)+abs(va.y-vb.y); / 根据两点坐标自动计算权值 p-nextarc = verticesi.firstarc; / 插在表头 verticesi.firstarc = p;/ 无向图,产生第二个表结点 p = (ArcNode*)malloc(sizeof(ArcNode);p-adjvex =