《太空漫游数据结构课程设计邵阳学院物联网工程陈汝涛.doc》由会员分享，可在线阅读，更多相关《太空漫游数据结构课程设计邵阳学院物联网工程陈汝涛.doc（44页珍藏版）》请在三一文库上搜索。
1、课程设计(论文)题 目 名 称 太空漫游 课 程 名 称 数据结构课程设计 学 生 姓 名 陈汝涛 学 号 1341306005 系 、专 业 信息工程系、13级物联网工程 指 导 教 师 黄同成 2014年 12 月 22 日摘 要为了估计预算，现在需要知道终点星球的接待站应该设计多大容量，浏览并分析所需景点信息，选择相应选项即可了解相应方案详情。输出景点星图、各景点介绍及其空间站的容量大小，路径中包括到达各景点的最短路径、花费最小路径、深度优先遍历路径和广度优先遍历路径！才能使得每艘飞船在到达时都可以保证让全部旅客下船。关键词：循环队列；无向图；深度优先遍历、广度优先遍历、Prim算法、D
2、ijkstra算法；最短路径目 录1 问题描述12 需求分析13 概要设计131抽象数据类型定义132模块划分34 详细设计641数据类型的定义642主要模块的算法描述75 测试分析146 课程设计总结18参考文献18附录（源程序清单）191 问题描述在走遍了地球上的所有景点以后，旅游狂人开始了他的太空漫游计划。经过谨慎调查，他目前掌握了一张各卫星空间站可以临时容纳的旅客人数的列表。当旅客从一个星球飞往另一个星球时，需要在若干卫星空间站临时停靠中转，而这些空间站不能接待任何旅客驻留，旅客必须立刻转乘另一艘飞船离开，所以空间站不能接待超过自己最大容量的旅客流。为了估计预算，现在旅游狂人需要知道终
3、点星球的接待站应该设计多大容量，才能使得每艘飞船在到达时都可以保证让全部旅客下船。输入要求：浏览并分析所需景点信息，综合各方面因素选择所需最佳方案，选择相应选项即可了解相应方案详情。输出要求：输出景点星图、各景点介绍及其空间站的容量大小，在各种方案中输出旅行路径和方案简介。路径中包括到达各景点的最短路径、花费最小路径、深度优先遍历路径和广度优先遍历路径！2 需求分析（1）用结构体EdgeNode 表示图的每一条边的信息，start表示起点，end表示终点，weight表示路径长度。先定义变量edge，再通过初始化给无向图的每条边edgei的起点、终点、权的分行赋值，表示成一个无向图邻接矩阵，该
4、无向图邻接矩阵代表旅游星图。（2）使用字符串指针数组vert表示各景点名称，并将顶点信息初始化赋值，VC中支持汉字字符串，所以需使用汉字表示各景点名称，这样更生动形象具体。（3）在循环队列中需要用Q-rear=(Q-rear+1)%QueueSize表示入队操作之后Q-rear的变化，防止“假溢出”，便于有效利用队列空间。同样在出队操作中需使用Q-front=(Q-front+1)%QueueSize表示出队之后Q-front的变化，防止“假溢出”。（4）matMaxSizeMaxSize表示旅行无向图的邻接矩阵，在CreateMGraph(char vert,MGraph *G,EdgeNo
5、de edge)中将EdgeNode edge中各边的信息加入到图G中。（5）另外还需设计一个可视化选择界面，要求简单、方便、灵活、且美观，使用清屏函数system(“cls”)清除上次操作界面，以免影响视觉错乱！3 概要设计31抽象数据类型定义（1）循环队列的抽象数据类型定义ADT Queue 数据对象：D=ai|aiElemSet,i=1,2,.,n, n0数据关系：R1=|ai-1,aiD，i=2,.,n约定a1端为队列头，an端为队列尾。ADT Queue基本操作：void InitQueue(CirQueue *Q)：队列初始化初始条件：队列Q不存在。操作结果：构造一个空栈S。int
6、 QueueEmpty(CirQueue *Q)：判断队列空初始条件：队列Q已存在。操作结果：若Q为空队列则返回1，否则返回0。int QueueFull(CirQueue *Q)：判断队满初始条件:队列Q已存在。操作结果：若队长达到最大值QueueSize，则返回1，否则返回0。void EnQueue(CirQueue *Q,int x)：入队初始条件:队列Q已存在。操作结果：在Q的队尾插入一个新元素x，x成为新的队尾元素，队长增长1。int DeQueue(CirQueue *)：出队初始条件:队列Q存在且非空。操作结果：读取队头元素并用队头元素作为返回值，队长自减1。（2）无向图的抽象
7、数据类型定义ADT Graph数据对象：由一个顶点集合V和边的集合E组成，顶点的偶对（x，y）表示无向边，（y，x）等价于（x，y），wij表示边的权值。数据关系：R=R2，WW=wij | i=1,2,M,j=0,1,NR2=（vi，vj）| vi，vjV，i=1,2,M,j=0,1,NADT Graph基本操作：void InitGraph(MGraph *G)：初始化图的顶点集合和邻接矩阵初始条件：图G不存在。操作结果：令图G的每个顶点为空格，令主对角线上的数据元素权值为0，令非主对角线上的数据元素权值为无穷大，将当前顶点数置为0，将当前边数置为0。void CreateMGraph(c
8、har vert,MGraph *G,EdgeNode edge)：构造图G初始条件：图G不存在。操作结果：以顶点集合vert和边集合edge构造一个图，顶点和边的相应信息保存到图G中。void Unvisited(MGraph *G)：设置未访问标记0初始条件：图G存在。操作结果：将图G中未访问的顶点标记为0。（3）邻接矩阵的抽象数据类型定义ADT EdgeNode数据对象：D=(vi,vj,wij)|vi,vjV,wij=0,0=i=M,0=j=N。数据关系：vi表示始点，vj表示终点，wij表示边（vi，vj）的权值。基本操作：EdgeNode edge：定义结构体数组。初始条件：已经定
9、义edge。操作结果：边edgen的起点、终点、权的分行赋值。32模块划分本程序包括12个模块：（1）主程序模块void main()调用温馨提示；延时再清屏；选择进入或退出；（2） Welcome（）函数模块先利用字符串指针数组*vertN，给顶点信息初始化赋值；再定义邻接矩阵并初始化赋值；其次定义图G1，初始化图G1，并以顶点集合vertN和邻接矩阵edge构造图G1，形成正式的无向图G1；然后用while循环反复展示主功能界面，根据所输入的选项调用相应的子函数；最后根据选项来选择循环或者退出。（3）StarMap()模块打印输出太空漫游星图，供用户参考。（4）循环队列模块实现循环队列的抽
10、象数据类型。（5）图模块实现无向图的抽象数据类型。（6）广度优先遍历模块BreadthFS(MGraph *G,int k)设置空队列；顶点信息初始化赋值；打印起始顶点访问过则标记1且入队；用while循环通过队列的入队和出队操作打印输出广度优先遍历路径；while循环中若每个访问过则标记为1，若已经打印输出则入队，循环之后再出队；BreadthFirstSearch(MGraph *G)设置出发点k；将所有景点设置为未访问标记0；嵌套调用BreadthFS(G,k)函数打印路径； （7） 深度优先遍历模块void DepthFS(MGraph *G,int k)顶点信息初始化赋值；打印输出上
11、一个出发点k；设置访问标记1；While循环查找与k相邻的其他顶点并递归调用DepthFS(G,j)；void DepthFirstSearch(MGraph *G) 设置出发点k；将所有景点设置为未访问标记0；嵌套调用DepthFS(G,k)函数打印路径（8）迪杰斯特拉算法模块void ShortestPath_DIJ(MGraph *G) for循环每一个顶点，初始化赋值，并设置空路径；for循环将每一个顶点初始化为未加入集合S；开始主循环，每次求得v0到某个v顶点的最短路径，并加v到集合S；更新当前最短路径和距离；For循环打印到达各景点的最短路径（线路）；（9） Prim算法模块voi
12、d Prim(MGraph *G) 顶点信息初始化赋值;循环比较，筛选最小代价时的代价和顶点序号,并打印输出；计算最小代价之和并打印输出；（10） 景点信息Search()模块选择所需景点序号；switch(m)相应景点信息；（11） 最短路径模块void PerfictPath(MGraph *G)调用Prim(G);（12） 路径探索模块void NovelPath(MGraph *G)选择所需景点序号；switch（x）调用深度优先遍历；调用广度优先遍历；4 详细设计41数据类型的定义（1）队列类型typedef struct /顺序循环队列 dataType dataQueueSize
13、;/定义一个一维数组存放队列中各元素 int size; /队列存放元素的个数，即队列的实际长度 int front,rear; /front、rear为队列首尾指针CirQueue;（2）邻接矩阵类型typedef struct /带权值的边 int start; /边的起点 int end; /边的终点 int weight; /边的权值EdgeNode; （3）无向图类型typedef struct /邻接矩阵图 int visitedMaxSize; /访问标记数组 char vertexMaxSize; /图的顶点集合，MaxSize为最大顶点数 int matMaxSizeMaxS
14、ize;/图的邻接矩阵，Adjacency matrix表示邻接矩阵 int VertCount; /图的顶点数 int EdgeCount; /图的边数MGraph;42主要模块的算法描述该题主要分为三步：（1）用邻接矩阵实现向无向图的各种信息的转接；（2）利用队列和无向图实现广度优先遍历，用无向图实现深度优先遍历，并打印相应路径及其他信息；（3）利用Prim算法、迪杰斯特拉算法输出相应路径。该题由我和刘熔同学合作完成，我主要负责：（3）各种算法设计及其修改优化。（1） 主调用函数void Welcome()/字符串指针数组，顶点信息初始化赋值char *vertN=地球,火星,月球,金星,
15、水星,木星,土星,天王星,海王星,冥王星;EdgeNode edge= /无向图的邻接矩阵 /边edge的起点、终点、权的分行赋值0,1,2,0,2,1,0,3,3,1,0,2,/0,1,2表示顶点地球到顶点火星的距离为21,7,5,2,0,1,2,5,4,2,6,6,3,0,3,3,4,3,3,5,5,4,3,3,4,8,7,5,2,4,5,3,5,5,8,2,6,2,6,6,7,4,6,8,1,7,1,5,7,6,4,7,9,8,8,4,7,8,5,2,8,6,1,8,9,4,9,7,8,9,8,4;int n;MGraph G1;/定义结构体变量图G1InitGraph(&G1);Cre
16、ateMGraph(*vert,&G1,edge);/以顶点集合*vert和边集合edge构造一个图StarMap();while(1)/printf输出选择界面n=getch();printf(%cn,n);if(n=6)printf(谢谢您的使用，欢迎您再次光临，再见!n);break;elseswitch(n)case 1:Search();system(pause);system(cls);break;case 2:ShortestPath_DIJ(&G1);system(pause);system(cls); break;case 3:PerfictPath(&G1);system(
17、pause);system(cls); break;case 4:NovelPath(&G1);system(pause);system(cls); break;case 5:system(cls);StarMap();system(pause);system(cls);default: break;（2） 主要函数算法流程图输出主功能界面n=getch()输入所需选项退出循环main函数if(n=6）While循环主功能界面Yswitch（n）Ncase n：调用子函数system（“cls”）清屏图4.1 主功能函数BFS广度优先遍历设置空队列访问起始顶点并标记，再入队while(判队空)
18、i=DeQueue(&Q)出队while()查找相邻的其他顶点访问顶点vertj，并标记，再入队if（非主对角线且未访问）else j+YN图4.2 广度优先遍历DFS深度优先遍历访问当前顶点并标记1while 查找与其相邻的其他顶点递归调用DepthFS(G,j)if（非0且非主对角线且未访问）j+NY图4.3 深度优先遍历迪杰斯特拉最短路径算法所有顶点的最短路径是否都求出选取不在S中且具有最短距离的顶点u源点编号v放入S中是否找到最短距离的顶点u修改不在S中的顶点的距离顶点u加入S中结束YNYN图5.4 迪杰斯特拉最短路径算法Prim算法初始化顶点集合V=v0,边集合E 为空for循环比较
19、，筛选最小代价时的代价和顶点序号将最小代价对应的顶点vj加入到V打印输出最小代价所对应的顶点及其距离E=E-EvV-V将最小代价对应的边从E中退出结束图4.5 Prim算法5 测试分析测试数据及结果如下：图5.1 迪杰斯特拉最短路径算法分析：Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。图5.2 Prim算法分析：此算法的精妙之处在于对求权值最小的边这一问题的分解（也正是由于这种分解，而导致了算法理
20、解上的困难）。按照常规的思路，这一问题应该这样解决：分别从集合VU和U中取一顶点，从邻接矩阵中找到这两个顶点行成的边的权值，设VU中有m个顶点，U中有n个顶点，则需要找到m*n个权值，在这m*n个权值中，再查找权最小的边。循环每执行一次，这一过程都应重复一次，相对来说计算量比较大。而本算法则利用了变量tree中第k+1到第n1号元素来存放到上一循环为止的一些比较结果，如以第k+1号元素为例，其存放的是集合U中某一顶点到顶点tree.en的边，这条边是到该点的所有边中权值最小的边，所以，求权最小的边这一问题，通过比较第k+1号到第n1号元素的权的大小就可以解决，每次循环只用比较nk2次即可，从而
21、大大减小了计算量。图5.3 深度优先遍历分析：深度优先遍历从某个顶点出发，首先访问这个顶点，然后找出刚访问这个结点的第一个未被访问的邻结点，然后再以此邻结点为顶点，继续找它的下一个新的顶点进行访问，重复此步骤，直到所有结点都被访问完为止。其无向图有10个顶点和14条边，此无向图采用邻接矩阵存储，那么决定某个顶点v所有邻接点所需的执行时间为O(10)，因为有n个顶点需要访问，则全部时间为O(102)=O(100)。图5.4 广度优先遍历分析：广度优先遍历从某个顶点出发，首先访问这个顶点，然后找出这个结点的所有未被访问的邻接点，访问完后再访问这些结点中第一个邻接点的所有结点，重复此方法，直到所有结
22、点都被访问完为止。广度优先搜索与深度优先搜索在执行时间上是同数量级的，亦为O(102)=O(100)。深度与广度比较：广度优先遍历与深度优先遍历的区别在于：广度优先遍历是以层为顺序，将某一层上的所有节点都搜索到了之后才向下一层搜索；而深度优先遍历是将某一条枝桠上的所有节点都搜索到了之后，才转向搜索另一条枝桠上的所有节点。6 课程设计总结通过此次课程设计使我充分地理解了用无向图和循环队列实现路径搜索问题，知道了深度和广度优先搜索的基本原理，还深刻地认识了Prim算法和迪杰斯特拉最短路径算法，也学会了简单的程序优化，另外最重要的是学会了将C+改编成C语言，初略地了解了C+语言，认识到了C+与C语言
23、的不同之处，C+是面向对象，而C是面向过程。虽然此次的程序不是很完备，但是总体还是一个比较能体现数据结构知识点能力的程序了，当然只是相对于我这个笨蛋来说。在刚开始面对C+的时候，我一脸茫然、感到万分恐惧，如今还是对他有点面熟了，也不那么害怕他了！在此我非常要感谢的是我们伟大的指导老师黄同成老师，感谢老师的细心认真的辅导和无微不至的关怀，让我对数据结构这门课程充满无限向往与希望！最后深深地祝福黄同成老师身体健康、万事如意、阖家欢乐！参考文献1 黄同成，黄俊民，董建寅数据结构M北京：中国电力出版社，20082 董建寅，黄俊民，黄同成数据结构实验指导与题解M北京：中国电力出版社，20083 严蔚敏，
24、吴伟民. 数据结构（C语言版）M. 北京：清华大学出版社，20024 刘振鹏，张晓莉，郝杰数据结构M北京：中国铁道出版社，2003附录（源程序清单）#includestdio.h#includestdlib.h#includeconio.h#includeiostream.h#includefstream.h#includewindows.h#define N 10#define MaxSize 10/顶点数#define EdgeSum 28/边数#define QueueSize 10/队长#define MaxCost 9999/最大代价typedef char dataType;voi
25、d Search(); /声明后面定义的Search()函数int ShortestPath_DIJ(); /声明后面定义的ShortestPath_DIJ()函数int PerfictPath(); /声明后面定义的PerfictPath()函数int NovelPath(); /声明后面定义的NovelPath()函数typedef struct /顺序循环队列 dataType dataQueueSize;/定义一个一维数组存放队列中各元素 int size; /队列存放元素的个数，即队列的实际长度 int front,rear; /front、rear为队列首尾指针CirQueue;t
26、ypedef struct /带权值的边 int start;/边的起点 int end; /边的终点 int weight; /边的权值EdgeNode; typedef struct /邻接矩阵图 int visitedMaxSize; /访问标记数组 char vertexMaxSize; /图的顶点集合，MaxSize为最大顶点数 int matMaxSizeMaxSize;/图的邻接矩阵，Adjacency matrix表示邻接矩阵 int VertCount; /图的顶点数 int EdgeCount; /图的边数MGraph;void InitGraph(MGraph *G) /
27、初始化图的顶点集合和邻接矩阵 int i,j; for(i=0;ivertexi= ; /令图G的每个顶点为空格 for(i=0;iMaxSize;i+) /循环每一行，初始化图的邻接矩阵 for(j=0;jmatij=0;/令主对角线上的数据元素权值为0 else G-matij=MaxCost;/令非主对角线上的数据元素权值为无穷大G-VertCount=0;/当前顶点数为0G-EdgeCount=0;/当前边数为0void CreateMGraph(char vert,MGraph *G,EdgeNode edge)/形参vert表示顶点集合，形参edge表示边集合 /以顶点集合和边集合
28、构造一个图 G-VertCount=N; /图的顶点个数 int i,j,k; for(i=0;ivertexi=verti; G-EdgeCount=EdgeSum;/图的边数 for(k=0;kmatij=edgek.weight; /边的权值赋值给matij void Unvisited(MGraph *G)/设置未访问标记0for(int i=0;iVertCount;i+)/循环图G的每一个顶点，标记为0 G-visitedi=0;void InitQueue(CirQueue *Q)/队列初始化Q-front=Q-rear=0;/尾指针=头指针Q-size=0;/队长为0int Q
29、ueueEmpty(CirQueue *Q) /判断对空函数return Q-front=Q-rear;/尾指针与头指针相等为真int QueueFull(CirQueue *Q)/判断对满函数return Q-size=QueueSize;/队长达到初始设置的最大值void EnQueue(CirQueue *Q,int x)/入队算法if(QueueFull(Q) /判断队满printf(队列满！n);elseQ-size+;/队长+1Q-dataQ-rear=x;/x赋值给队尾指针所对应的dataQ-rear=(Q-rear+1)%QueueSize;/防止“假溢出”int DeQueu
30、e(CirQueue *Q) /出队算法int temp; if(QueueEmpty(Q) /判断队空printf(队列空！n); return NULL;else /队不为空temp=Q-dataQ-front;/提取队头元素Q-size-; /队长-1Q-front=(Q-front+1)%QueueSize;/防止“假溢出”return temp; /返回值为队头元素元素/void BreadthFS(MGraph *G,int k) /从顶点k开始的广度优先遍历 /k为起始顶点下标 CirQueue Q;InitQueue(&Q); /设置空队列int i=k;/字符串指针数组，顶点
31、信息初始化赋值char *vertN=地球,火星,月球,金星,水星,木星,土星,天王星,海王星,冥王星; printf(%s ,verti); /访问起始顶点 G-visitedi=1; /设置访问标记 EnQueue(&Q,i);/访问过的顶点k入队 while(!QueueEmpty(&Q) /队列不空时 i=DeQueue(&Q); /出队,i是顶点k的数组下标 int j=0; while(jVertCount) /查找与k相邻的其他顶点if(i!=j & G-matij0 & G-matijvisitedj=0)/非主对角线上，且图G的邻接矩阵元素大于0，且其元素小于无穷大，且未被访
32、问 printf(%s ,vertj);/访问顶点vertjG-visitedj=1;/标记已经被访问的 EnQueue(&Q,j); /已访问则入队else j+; printf(感觉真浪漫！);void BreadthFirstSearch(MGraph *G)/图的广度优先遍历 /k为起始顶点下标printf(请参照以下路线:nn);int k=0;/从地球0开始Unvisited(G);/设置未访问标记BreadthFS(G,k);/嵌套调用BreadthFS(G,k)函数printf(n); void DepthFS(MGraph *G,int k) /从顶点k开始的深度优先遍历in
33、t i=k,j=0;/i下标从0开始/字符串指针数组，顶点信息初始化赋值char *vertN=地球,火星,月球,金星,水星,木星,土星,天王星,海王星,冥王星;printf(%s ,verti); /访问顶点G-visitedi=1; /设置访问标记while(jVertCount) /查找与k相邻的其他顶点if(i!=j & G-matij0 & G-matijvisitedj=0)DepthFS(G,j); /递归调用DepthFS(G,j)elsej+;void DepthFirstSearch(MGraph *G) /图的深度优先遍历printf(请请参照以下路线:nn);int k=0;Unvisited(G);/设置未访问标记 DepthFS(G,k);/嵌套调用DepthFS(G,k)函数printf(好奇特啊！);printf(n);/迪杰斯特拉最短路径算法void ShortestPath_DIJ(MGraph *G)