迷宫求解和拓扑排序

迷宫求解和拓扑排序,程序能够完全运行。

《数据结构》课程设计报告

专班学

业：计算机科学与技术（软件工程方向）级：软件***班号：*******

2010年1月14日星期四

学生姓名：*锦超9817

迷宫求解和拓扑排序,程序能够完全运行。

目录

.3一、设计目的…………………………………………………………………………………………………………………….3.3二、设计要求…………………………………………………………………………………………………………………….3.3三、设计题目…………………………………………………………………………………………………………………….3

..3四、设计思路…………………………………………………………………………………………………………..3

.3………………………………………………….3题目一迷宫求解…………………………………………………16…………………………………………………16题目二拓扑排序…………………………………………………

.......24五、心得体会…………………………………………………………………………………………………………..............24

迷宫求解和拓扑排序,程序能够完全运行。

《数据结构》课程设计报告

一、设计目的

《数据结构》是一门实践性较强的软件基础课程，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。本课程设计的目的就是要达到理论与实际应用相结合，使同学们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能。

二、设计要求

1、通过这次设计，要求在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。2、学生必须仔细研读《数据结构》课程设计(实习)要求，以学生自学为主、指导教师指导为辅，认真、独立地完成课程设计的任务，有问题及时主动与指导教师沟通。

3、本次课程设计按照教学要求需要在一周半时间内独立完成，学生要发挥自主学习的能力，充分利用时间，安排好课设的时间计划，并在课设过程中不断检测自己的计划完成情况，及时地向指导教师汇报。

4、编程语言任选。

三、设计题目

１．迷宫求解２．拓扑排序

四．设计思路

一、二、

题目一迷宫求解

设计题目：迷宫求解问题需要分析：

任务：可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出

输入数据：输入开始界面的选项1-4，选择1初始化建立迷宫图，输入（0、1）建立正方形迷宫图；选择2输入迷宫入口坐标和出口坐标；选择3判断是否为通路并显示可通路径。选择4退出出程序。输出形式：输出迷宫图以及走出迷宫的路径；程序所能达到的功能输出迷宫图以及走出迷宫的路径“1”代表障碍物“0”代表路径，“#”代表外围迷宫墙，“*”显示迷宫可通时的路径；如果主函数选项错误显示“选项错误，请从新输入要选择项目”，选择迷宫尺寸超出范围显示“输入错误”；如果输入迷宫有路径时显示“找到通路”，如果迷宫有路径显示迷宫图以及走出路径和“找不到通路”。

迷宫求解和拓扑排序,程序能够完全运行。

三．概要设计

1.定义栈的抽象数据类型定义：ADTStack{

数据对象：

D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：

R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}

基本操作：

typedefstructSqStack//构造一个栈的结构体StatusInitStack(Stack&S)//建立一个空栈

StatusStackEmpty(StackS)//若s为空返回TRUE,否则返回FALSEStatusPush(Stack&S,SElemTypee)//插入元素e为新的栈顶元素

StatusPop(Stack&S,SElemType&e)//若栈不空删除栈顶元素用e返回并返回OK，2.定义迷宫的抽象数据类型ADTMaze{

数据对象：

D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：

R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}

基本操作：

voidInitmaze(intmaze[22][22],intsize)//初始化迷宫

voidPrintmaze(intmaze[22][22],intsize)//显示初始化迷宫图形voidPrintmaze(intmaze[22][22],intsize)//将标记路径信息的迷宫输出到终端(包括外墙)StatusPass(intmaze[22][22],PosTypeCurPos)//当前位置可通则返回TURE,否则返回FALSEvoidMarkfoot(intmaze[22][22],PosTypeCurPos)//标记当前位置可通

StatusMazePath(MazeType&maze,PostTypestart,PostTypeend)//若迷宫maze存在从入口start到end的通道则求得一条存放在栈中;并返回TRUE,否则返回FALSEPosTypeNextPos(PosTypeCurPos,intDir)//进入下一位置寻找可通路径

StatusMazePath(intmaze[22][22],SqStack&S,PosTypestart,PosTypeend)//若迷宫maze中从入口start到出口end的通道，则求得一条存放在栈中3.主程序包含三个模块：1）voidmain(){//主函数输出开始界面；

由switch()语句调用各函数；输出测试结果；}

2）栈模块---实现栈抽象数据类型

3）迷宫模块---实现迷宫抽象数据类型各模块调用关系如下：

主程序模块

迷宫模块栈模块

四．

…… 此处隐藏：10213字，全部文档内容请下载后查看。喜欢就下载吧 ……