数据结构学年论文.docx

学号：20105101244学年论文（设计）（本科）学 院 专业计算机科学与技术（网络工程）年级2010级计科二班姓名杨丽萍论文（设计）题目迷宫求解指导教师孙艳歌职称 讲师成绩2012年6月数据结构课程设计(论文)任务书计算机与信息技术 学院 计算机科学与技术 专业 2010 级二 班课程设计(论文)题目 1 •本课程设计的目的~~(1)巩固和加深对数据结构基本知识的理解，提高综合运用课程知识的能力~~(2)使学生掌握软件设计的基本内容和设计方法，并培养学生进行规范化软 件设计的能力"""(3)使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设 计的基本能力2 •课程设计的任务及要求1) 基本要求:~~(1)系统设计要能完成题目所要求的功能;~~(2)编程简练，可用，尽可能的使系统的功能更加完善和全面;~~(3)说明书、流程图要清楚;(4) 提高学生的论文写作能力；(5) 特别要求自己独立完成;~~(6)要同时上交纸质论文和源程序2) 创新要求:~~在基本要求达到后，可进行创新设计，如改善算法性能、友好的人机界面3) 课程设计论文编写要求~~(1)要按照学年论文的规范写作课程设计论文;"""(2)论文包括需求分析、概要设计、详细设计(源代码)、调试分析及测试、 总结、参考文献、附录等。

学生签名： 2012年6月目录一、 需求分析 1二、 概要设计 3三、 详细设计 5四、 调试分析及测试 13五、 总结 14参考文献 15附录 15一•需求分析人类建造迷宫已有5000多年的历史在世界的不同文化发展时期，这些奇特 的建筑物始终吸引人们沿着弯弯曲曲、困难重重的小路吃力地走，寻找真相因 此，求迷宫从入口到出口的所有路径（即迷宫求解问题）也成了一个经典的程序 设计问题1・1、选题理由：根据自己的知识功底和能力水平择选了迷宫求解问题•而且随着计算机技术 的飞速发展，这一古老而有趣的数学游戏问题也自然而然的被搬到了计算机上运 用所学计算机知识来试着解决这个问题是个锻炼和提高我自己编程能力和独立解 决问题能力的好机会，可以使我增强信心，为我以后的编程开个好头，故我选择了 这个有趣的课题1.2、求解方法：计算机解迷宫问题时，通常用的方法就是“穷举求解”的方法，即从入口 出发，顺某一方向向前搜索，若能走通，则继续往前走；否则沿原路退回，换一 个方向继续搜索，直至所有的可能通路都搜索到为止为了保证在任何位置上都 能沿原路退回，显然需要一个后进先出的结构来保存从入口到当前位置的路径， 因此，在求迷宫通路的算法中应用“栈”也就是自然而然的事了。

1. 3、求解思路：在计算机中可以用如图所示的方块图表示迷宫图中的每个方块或为通道 （以空白方块表示），或为墙（以带阴影的方块表示）所求的路径必须是简单路 径，即在求得的路径上不能重复出现同一通道快假设“当前位置”指的是“在搜索过程中某一时刻所在图中某个方块位置”， 则求迷宫中一条路径的算法的基本思想是：若当前位置的东南西北四个方向均是 可通的，则根据以下程序的算法思想，先按照方向东进行前进，如果走到下一位 置走不通了，则返回到刚才的位置，继续选择往南或西或北的方向继续进行查找，直到找到了指定的出口的位置，则此时查找成功，此时所走过的路径即是从入口 到出口的一条路径，就是迷宫的一组解1・4、涉及到的知识点本次课程设计中用到的主要知识点有:递归法的应用，数组的灵活运用, 栈的基本操作的应用，全局变量与局部变量的应用等1・5、功能要求当运行程序时首先在界面上显示的是迷宫的布局，其中0代表的是墙，-1 代表的是通路，并人为的确定入口位置和出口位置(注意每一个位置都是由行列 坐标共同确定的)，最后在屏幕上显示出从入口到出口的路径(其中1表示第一 步，2表示第二步，以此类推)二•概要设计2. 1、数据结构设定迷宫的布局，墙为0,通道为-1，不能通过的位置记录为-2，首先定义 除了周边的元素以外其他的都是通道，然后再在矩阵的中间位置确定其他的墙的 位置。

2.2、抽象数据类型定义① Print() //打印迷宫当前的状态② Init ()//设定迷宫布局③ Pass()〃判定当前位置是否可以通过④ FootPrint()〃记录走过的足迹⑤ NextPos()〃寻找当前位置的下一个位置⑥ MarkPrint()〃记录不能通过的足迹⑦ MazePath()〃利用栈来寻找出口⑧ Void main()//主函数调用2.3算法流程⑴初始化矩阵(即设定迷宫)⑵首先从当前的位置(cur )向东进行试探，看是否为通路(即看 m[next.x][next.y]==-l是否成立)，如果成立把当前的位置压入堆栈，如果不 成立，继续向南、西、北方向进行探索哪个方向可以走通，就把当前的位置压 入堆栈，把刚搜索到的位置作为下一个当前位置，并记下方向；如果各个方向均 走不通，若栈为空，则表明此迷宫无解，若栈不为空，则从栈中弹出当前的栈顶 元素，并把此元素记为不可通过的位置以此类推直至到达迷宫的出口⑶如果从入口找到了出口，则证明此迷宫有解，利用Print()函数，输出迷 宫的一条通路即可输入迷宫 选取起点向东寻找可以 经过的路径 以当前位置的下 一个位置为起点YYES进行递归以以当 前位置的下下一一 个位置为起点向南、西、北各个 方向继续寻找探索输出迷宫的解（即路 径）或输出的为空（迷宫没有解）三•详细设计#include vstdlib.h>#include vstdio.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -2typedef int Status;typedef struct{int x; 〃行值int y; // 列值}PosType; //迷宫坐标位置类型#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define MAXLENGTH 25 //设迷宫的最大行列为25typedef int MazeType[MAXLENGTH][MAXLENGTH]; // 迷宫数组类型[行][列]MazeType m; //迷宫数组int x,y; //全局变量PosType start,end; //迷宫的入口坐标，出口坐标int curstep;//注意：一定要设置成全局变量typedef struct{int ord; //通道块在路径上的"序号"PosType seat; //通道块在迷宫中的"坐标位置"int di; //从此通道块走向下一通道块的"方向"typedef struct{SElemType *base;SElemType *top; int stacksize;}SqStack;Status InitStack(SqStack &S){S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base) exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;}Status StackEmpty(SqStack S){if(S.top==S.base)return TRUE;elsereturn FALSE;}Status Push(SqStack & S,SElemType e){if(S.top-S.base>=S.stacksize){S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));if(!S.base) exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;return OK;}Status Pop(SqStack & S,SElemType &e){if(S.top==S.base) return ERROR;e=*__S.top;return OK;}void Print(){ //输出迷宫的解(m数组)int i,j;for(i=0;i