资源描述：
《太空漫游数据结构课程设计邵阳学院物联网工程陈汝涛》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、课程设计(论文)题目名称太空漫游课程名称数据结构课程设计学生姓名陈汝涛学号1341306005系、专业信息工程系、13级物联网工程指导教师黄同成2014年12月22日摘要为了估计预算，现在需要知道终点星球的接待站应该设计多大容量，浏览并分析所需景点信息，选择相应选项即可了解相应方案详情。输出景点星图、各景点介绍及其空间站的容量大小，路径中包括到达各景点的最短路径、花费最小路径、深度优先遍历路径和广度优先遍历路径！才能使得每艘飞船在到达时都可以保证让全部旅客下船。关键词：循环队列；无向图；深度优先遍历、广度优先遍历、Prim算法、Dijk
2、stra算法；最短路径目录1问题描述12需求分析13概要设计13．1抽象数据类型定义13．2模块划分34详细设计64．1数据类型的定义64．2主要模块的算法描述75测试分析146课程设计总结18参考文献18附录（源程序清单）191问题描述在走遍了地球上的所有景点以后，旅游狂人开始了他的太空漫游计划。经过谨慎调查，他目前掌握了一张各卫星空间站可以临时容纳的旅客人数的列表。当旅客从一个星球飞往另一个星球时，需要在若干卫星空间站临时停靠中转，而这些空间站不能接待任何旅客驻留，旅客必须立刻转乘另一艘飞船离开，所以空间站不能接待超过自己最大容量的
3、旅客流。为了估计预算，现在旅游狂人需要知道终点星球的接待站应该设计多大容量，才能使得每艘飞船在到达时都可以保证让全部旅客下船。输入要求：浏览并分析所需景点信息，综合各方面因素选择所需最佳方案，选择相应选项即可了解相应方案详情。输出要求：输出景点星图、各景点介绍及其空间站的容量大小，在各种方案中输出旅行路径和方案简介。路径中包括到达各景点的最短路径、花费最小路径、深度优先遍历路径和广度优先遍历路径！2需求分析（1）用结构体EdgeNode表示图的每一条边的信息，start表示起点，end表示终点，weight表示路径长度。先定义变量edg
4、e[]，再通过初始化给无向图的每条边edge[i]的起点、终点、权的分行赋值，表示成一个无向图邻接矩阵，该无向图邻接矩阵代表旅游星图。（2）使用字符串指针数组vert[]表示各景点名称，并将顶点信息初始化赋值，VC中支持汉字字符串，所以需使用汉字表示各景点名称，这样更生动形象具体。（3）在循环队列中需要用Q->rear=(Q->rear+1)%QueueSize表示入队操作之后Q->rear的变化，防止“假溢出”，便于有效利用队列空间。同样在出队操作中需使用Q->front=(Q->front+1)%QueueSize表示出队之后Q->
5、front的变化，防止“假溢出”。（4）mat[MaxSize][MaxSize]表示旅行无向图的邻接矩阵，在CreateMGraph(charvert[],MGraph*G,EdgeNodeedge[])中将EdgeNodeedge[]中各边的信息加入到图G中。（5）另外还需设计一个可视化选择界面，要求简单、方便、灵活、且美观，使用清屏函数system(“cls”)清除上次操作界面，以免影响视觉错乱！3概要设计3．1抽象数据类型定义第40页（1）循环队列的抽象数据类型定义ADTQueue{数据对象：D={ai
6、ai∈ElemSet,i
7、=1,2,...,n,n≥0}数据关系：R1={
8、ai-1,ai∈D，i=2,...,n}约定a1端为队列头，an端为队列尾。}ADTQueue基本操作：voidInitQueue(CirQueue*Q)：队列初始化初始条件：队列Q不存在。操作结果：构造一个空栈S。intQueueEmpty(CirQueue*Q)：判断队列空初始条件：队列Q已存在。操作结果：若Q为空队列则返回1，否则返回0。intQueueFull(CirQueue*Q)：判断队满初始条件:队列Q已存在。操作结果：若队长达到最大值QueueSize，
9、则返回1，否则返回0。voidEnQueue(CirQueue*Q,intx)：入队初始条件:队列Q已存在。操作结果：在Q的队尾插入一个新元素x，x成为新的队尾元素，队长增长1。intDeQueue(CirQueue*)：出队初始条件:队列Q存在且非空。操作结果：读取队头元素并用队头元素作为返回值，队长自减1。（2）无向图的抽象数据类型定义ADTGraph{数据对象：由一个顶点集合V和边的集合E组成，顶点的偶对（x，y）表示无向边，（y，x）等价于（x，y），wij表示边的权值。数据关系：R={R2，W}W={wij
10、i=1,2,…M,
11、j=0,1,…N}R2={（vi，vj）
12、vi，vj∈V，i=1,2,…M,j=0,1,…N}}ADTGraph基本操作：第40页voidInitGraph(MGraph*G)：初始化图的顶点集合和邻接矩阵
