《太空漫游数据结构课程设计邵阳学院物联网工程陈汝涛》由会员分享，可在线阅读，更多相关《太空漫游数据结构课程设计邵阳学院物联网工程陈汝涛（44页珍藏版）》请在金锄头文库上搜索。
1、课程设计(论文)题 目 名 称 太空漫游 课 程 名 称 数据结构课程设计 学 生 姓 名 陈汝涛 学 号 1341306005 系 、 专 业 信息工程系、13 级物联网工程 指 导 教 师 黄同成 2014 年 12 月 22 日摘 要为了估计预算，现在需要知道终点星球的接待站应该设计多大容量，浏览并分析所需景点信息，选择相应选项即可了解相应方案详情。输出景点星图、各景点介绍及其空间站的容量大小，路径中包括到达各景点的最短路径、花费最小路径、深度优先遍历路径和广度优先遍历路径！才能使得每艘飞船在到达时都可以保证让全部旅客下船。关键词：循环队列；无向图；深度优先遍历、广度优先遍历、Prim
2、算法、Dijkstra 算法；最短路径目 录1 问题描述 .12 需求分析 .13 概要设计 .131 抽象数据类型定义 .132 模块划分 .34 详细设计 .641 数据类型的定义 .642 主要模块的算法描述 .75 测试分析 .146 课程设计总结 .18参考文献 .18附录（源程序清单） .19第 0 页1 问题描述在走遍了地球上的所有景点以后，旅游狂人开始了他的太空漫游计划。经过谨慎调查，他目前掌握了一张各卫星空间站可以临时容纳的旅客人数的列表。当旅客从一个星球飞往另一个星球时，需要在若干卫星空间站临时停靠中转，而这些空间站不能接待任何旅客驻留，旅客必须立刻转乘另一艘飞船离开，所以
3、空间站不能接待超过自己最大容量的旅客流。为了估计预算，现在旅游狂人需要知道终点星球的接待站应该设计多大容量，才能使得每艘飞船在到达时都可以保证让全部旅客下船。输入要求：浏览并分析所需景点信息，综合各方面因素选择所需最佳方案，选择相应选项即可了解相应方案详情。输出要求：输出景点星图、各景点介绍及其空间站的容量大小，在各种方案中输出旅行路径和方案简介。路径中包括到达各景点的最短路径、花费最小路径、深度优先遍历路径和广度优先遍历路径！2 需求分析（1）用结构体 EdgeNode 表示图的每一条边的信息，start 表示起点，end 表示终点，weight 表示路径长度。先定义变量 edge，再通过初
4、始化给无向图的每条边edgei的起点、终点、权的分行赋值，表示成一个无向图邻接矩阵，该无向图邻接矩阵代表旅游星图。（2）使用字符串指针数组 vert表示各景点名称，并将顶点信息初始化赋值，VC 中支持汉字字符串，所以需使用汉字表示各景点名称，这样更生动形象具体。（3）在循环队列中需要用 Q-rear=(Q-rear+1)%QueueSize 表示入队操作之后Q-rear 的变化，防止 “假溢出” ，便于有效利用队列空间。同样在出队操作中需使用 Q-front=(Q-front+1)%QueueSize 表示出队之后 Q-front 的变化，防止“假溢出”。（4）matMaxSizeMaxSiz
5、e表示旅行无向图的邻接矩阵，在CreateMGraph(char vert,MGraph *G,EdgeNode edge)中将 EdgeNode edge中各边的信息加入到图 G 中。（5）另外还需设计一个可视化选择界面，要求简单、方便、灵活、且美观，使用清屏函数 system(“cls”)清除上次操作界面，以免影响视觉错乱！3 概要设计第 1 页31 抽象数据类型定义（1）循环队列的抽象数据类型定义ADT Queue 数据对象：D=ai|aiElemSet,i=1,2,.,n, n0数据关系：R1=|ai-1,aiD，i=2,.,n约定 a1 端为队列头， an 端为队列尾。ADT Que
6、ue基本操作：void InitQueue(CirQueue *Q)：队列初始化初始条件：队列 Q 不存在。操作结果：构造一个空栈 S。int 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 成为新的队
7、尾元素，队长增长 1。int DeQueue(CirQueue *)：出队初始条件:队列 Q 存在且非空。操作结果：读取队头元素并用队头元素作为返回值，队长自减 1。（2）无向图的抽象数据类型定义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第 2 页基本操作：void InitGraph(MGraph *G)：初始化图的顶点集合和邻
8、接矩阵初始条件：图 G 不存在。操作结果：令图 G 的每个顶点为空格，令主对角线上的数据元素权值为 0，令非主对角线上的数据元素权值为无穷大，将当前顶点数置为 0，将当前边数置为0。void CreateMGraph(char vert,MGraph *G,EdgeNode edge)：构造图 G初始条件：图 G 不存在。操作结果：以顶点集合 vert和边集合 edge构造一个图，顶点和边的相应信息保存到图 G 中。void Unvisited(MGraph *G)：设置未访问标记 0初始条件：图 G 存在。操作结果：将图 G 中未访问的顶点标记为 0。（3）邻接矩阵的抽象数据类型定义ADT
9、EdgeNode数据对象：D=(vi,vj,wij)|vi,vjV,wij=0,0vertexi= ; /令图 G 的每个顶点为空格for(i=0;imatij=0;/令主对角线上的数据元素权值为 0elseG-matij=MaxCost; /令非主对角线上的数据元素权值为无穷大G-VertCount=0; /当前顶点数为 0G-EdgeCount=0; /当前边数为 0void CreateMGraph(char vert,MGraph *G,EdgeNode edge)/形参 vert表示顶点集合，形参 edge表示边集合第 20 页/以顶点集合和边集合构造一个图G-VertCount=N
10、; /图的顶点个数int i,j,k;for(i=0;ivertexi=verti;G-EdgeCount=EdgeSum; /图的边数for(k=0;kmatij=edgek.weight; /边的权值赋值给 matijvoid Unvisited(MGraph *G) /设置未访问标记 0for(int i=0;iVertCount;i+) /循环图 G 的每一个顶点，标记为 0G-visitedi=0;void InitQueue(CirQueue *Q) /队列初始化Q-front=Q-rear=0; /尾指针=头指针Q-size=0; /队长为 0int QueueEmpty(Cir
11、Queue *Q) /判断对空函数第 21 页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 DeQueue(CirQueue *Q) /出队算法int temp;if(QueueEmpty(Q) /判断队空printf(队列空！n);return NULL;else /队不为空temp=Q-dataQ-front; /提取队头元素第 22 页Q-size-; /队长-1Q-front=(Q-front+1)%QueueSize;/防止“假溢出”return temp; /返回值为队头元素元素/void BreadthFS(MGraph *G,int
