课程设计报告示例：迷宫求解.doc

《课程设计报告示例：迷宫求解.doc》由会员分享，可在线阅读，更多相关《课程设计报告示例：迷宫求解.doc（16页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 安徽建筑大学课 程 设 计 报 告 课程名称： 数据结构与算法课程设计 题 目： 迷宫求解 院 系： 数理系 专 业： 信息与计算数学 班 级： 学 号： 姓 名： 时 间： 目 录一 、需求分析21. 问题描述：22. 基本要求2二、 概要设计31. 数据结构32. 程序模块33. 算法设计5三、详细设计71. 数据类型定义72. 函数实现代码73. 函数之间的调用关系7四、调试分析7五、用户手册8六、测试结果8七、参考文献9八、附录10迷宫求解题目：以一个mn长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍，设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论

2、。(1)以二维数组存储迷宫数据；(2)求得的通路以二元组( i , j )的形式输出，其中（i, j）指示迷宫中的一个坐标。一 、需求分析1. 问题描述：在迷宫中求出从入口到出口的路径。经分析，一个简单的求解方法是：从入口出发，沿某一方向进行探索，若能走通，则继续向前走；否则沿原路返回，换一方向再进行搜索，直到所有可能的通路都探索到为止。即所谓的回溯法。求迷宫中从入口到出口的所有路径是一个经典的程序设计问题。由于计算机解迷宫时，通常用的是“穷举求解”的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止。为了保证在

3、任何位置上都能沿原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此，在求迷宫通路的算法中应用“栈”也就是自然而然的事了。 假设“当前位置”指的是“在搜索过程中某一时刻所在图中某个方块位置”，则求迷宫中一条路径的算法的基本思想是：若当前位置可通，则纳入当前路径，并继续朝“下一位置”探索，即切换“下一位置”为“当前位置”，如此重复直至到达出口；若当前位置“不可通”，则应顺着“来向”退回到“前一通道块”，然后朝着除“来向”之外的其他方向继续探索；若该通道块的四周四个方块均“不可通”，则应从“当前路径”上删除该通道块。所谓“下一位置”指的是“当前位置”四周四个方向（东、南、西、北

4、）上相邻的方块。2. 基本要求（1）以二维数组maze.adrm+1n+1表示迷宫，其中mg0j和mgm+1j(0 j n)及mgi0和mgin(0 i m)为添加的一圈障碍，数组中以元素值为0表示通路，1表示障碍，限定迷宫大小m,n 10。（2）用户以文件的形式输入迷宫的数据：文件中第一行的数据为迷宫的行数m和列数n;从第2行至第m+1行（每行n个数）为迷宫值，同一行的两个数之间用空白字符相隔。（3）迷宫入口为（1，1），出口为（m,n）。（4）每次移动只能从一个无障碍的单元到周围8个方向上任意无障碍的单元，编制程序给出一条通过迷宫的路径或报告一个“无法通过”的信息。（5）本程序只求出一条成

5、功的通路。3 测试数据见下表，当入口为（1，1）时，出口为（8，8）用一个字符类型的二微数组表示迷宫，数组中的每个元素表示一个小方格，取值“0”（表示可以进出）或“1”（表示不可以进出）随机产生一个8*8的迷宫，其中使用迷宫障碍坐标如下：（1，3），（1，7），（2，3），（2，7），（3，5），（3，6），（4，3），（4，4），（5，4），（6，2），（6，6），（7，2），（7，3），（7，4），（7，6），（7，7），（8，1）。二、 概要设计1. 数据结构栈（stack）是限定仅在表尾进行插入或删除操作的线性表。因此，对栈来说，表尾端有特殊含义，称为栈顶（top）,相应的，表头端称为

6、栈底（bottom）。不含元素的空表称为空栈。假设栈S=（a1,a2,，an），则称a1为栈底元素，an为栈顶元素。栈的修改是按后进先出的原则进行的。因此，栈又称为后进先出（List In First Out）的线性表。在迷宫问题中，假设以栈S记录“当前路径”，则栈顶中存放的是“当前路径上最后一个通道块”。由此，“纳入路径”的操作即为“当前位置入栈”；“从当前路径上删除前一通道块”的操作即为“出栈”。基本操作的函数原型说明。2. 程序模块栈的顺序存储表示#define StackSize 100 /假定预分配的栈空间最多为100个元素 typedef char DataType;/假定栈元素的

7、数据类型为字符 typedef struct DataType dataStackSize; int top; SeqStack;基本操作的算法描述（1） 置栈空 void InitStack（SeqStack *S） /将顺序栈置空 S-top=-1; （2） 判栈空 int StackEmpty（SeqStack *S） return S-top=-1; （3） 判栈满 int StackFull（SeqStack *SS） return S-top=StackSize-1; （4） 进栈 void Push（S，x） if (StackFull(S) Error(Stack overfl

8、ow); /上溢，退出运行 S-data+S-top=x;/栈顶指针加1后将x入栈 （5） 退栈 DataType Pop（S） if(StackEmpty(S) Error(Stack underflow); /下溢，退出运行 return S-dataS-top-;/栈顶元素返回后将栈顶指针减1 （6） 取栈顶元素 DataType StackTop（S） if(StackEmpty(S) Error(Stack is empty); return S-dataS-top; 3各模块之间的调用关系以及算法设计（1）Stack.h中调用的base.h#include #include #in

9、clude #define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -2typedef int Status;（2）主程序maze.c中调用的stack.h#include base.h#define INIT_SIZE 100 /存储空间初始分配量#define INCREMENT 10 /存储空间分配增量typedef struct /迷宫中r行c列的位置 int r; int c;PostType;typedef struct int ord; /当前位置在路径上的序号 PostType seat;

10、/当前坐标 int di; /往下一坐标的方向SElemType; /栈元素类型typedef struct SElemType* base;/栈基址,构造前销毁后为空 SElemType* top;/栈顶 int stackSize; /栈容量Stack; /栈类型Status InitStack(Stack &S) /构造空栈s S.base=(SElemType*)malloc(INIT_SIZE *sizeof(SElemType); if(!S.base) exit(OVERFLOW);/存储分配失败 S.top=S.base; S.stackSize=INIT_SIZE; retu

11、rn OK;/InitStackStatus StackEmpty(Stack S) /若s为空返回TRUE,否则返回FALSE if(S.top=S.base) return TRUE; return FALSE;/StackEmptyStatus Push(Stack &S,SElemType e) /插入元素e为新的栈顶元素 if(S.top-S.base =S.stackSize)/栈满，加空间 S.base=(SElemType *)realloc(S.base,(S.stackSize+INCREMENT)*sizeof(SElemType); if(!S.base) exit(O

12、VERFLOW); /存储分配失败 S.top=S.base+S.stackSize; S.stackSize+=INCREMENT; *S.top+=e; return OK;/pushStatus Pop(Stack &S,SElemType &e)/若栈不空删除栈/顶元素用e返回并返回OK，否则返回ERROR if(S.top=S.base) return ERROR; e=*-S.top; return OK;/PopStatus DestroyStack(Stack &S)/销毁栈S, free(S.base); S.top=S.base; return OK;/DestroySta

13、ck3. 算法设计求迷宫中一条从入口到出口的路径的算法可简单描述如下： 设定当前位置的初值为入口位置； do 若当前位置可通， 则将当前位置插入栈顶； / 纳入路径 若该位置是出口位置，则结束；/ 求得路径存放在栈中 否则切换当前位置的东邻方块为新的当前位置； 否则 若栈不空且栈顶位置尚有其他方向未被探索， 则设定新的当前位置为: 沿顺时针方向旋转 找到的栈顶位置的下一相邻块； 若栈不空但栈顶位置的四周均不可通， 则 删去栈顶位置； / 从路径中删去该通道块 若栈不空，则重新测试新的栈顶位置， 直至找到一个可通的相邻块或出栈至栈空； while (栈不空）； 在此，尚需说明一点的是，所谓当前位

14、置可通，指的是未曾走到过的通道块，即要求该方块位置不仅是通道块，而且既不在当前路径上（否则所求路径就不是简单路径），也不是曾经纳入过路径后又从路径上删除的通道块（否则只能在死胡同内转圈）。 typedef struct int ord; / 通道块在路径上的“序号” PosType seat; / 通道块在迷宫中的“坐标位置” int di; / 从此通道块走向下一通道块的“方向” SElemType; / 栈的元素类型 Status MazePath ( MazeType maze, PosType start, PosType end ) / 若迷宫maze中从入口 start到出口 en

15、d的通道， / 则求得一条存放在栈中（从栈底到栈顶），并返回 / TRUE；否则返回FALSE InitStack(S); curpos = start;/ 设定“当前位置”为“入口位置” curstep = 1; / 探索第一步 do if (Pass (curpos) / 当前位置可以通过，即是未曾走到过的通道块 FootPrint (curpos); / 留下足迹 e = ( curstep, curpos, 1 ); Push (S,e); / 加入路径 if ( curpos = end ) return (TRUE);/ 到达终点（出口） curpos = NextPos ( cu

16、rpos, 1 );/ 下一位置是当前位置的东邻 curstep+; / 探索下一步 else / 当前位置不能通过 if (!StackEmpty(S) Pop (S,e); while (e.di=4 & !StackEmpty(S) MarkPrint (e.seat); Pop (S,e); / 留下不能通过的标记，并退回一步 / while if (e.di4) e.di+; Push ( S, e);/ 换下一个方向探索 curpos = NextPos (curpos, e.di );/ 设定当前位置是该新方向上的相邻块 / if / if / else while ( !Sta

17、ckEmpty(S) ); return (FALSE); / MazePath三、详细设计1. 数据类型定义typedef struct int r; int c; char adrMAXLENMAXLEN; MazeType; /迷宫类型2. 函数实现代码l 初始化迷宫Status InitMaze(MazeType &maze)l 可通位置Status Pass(MazeType maze,PostType curpos)l 标记非通路Status MarkPrint(MazeType &maze,PostType curpos)l 迷宫maze从入口start到end的通道Status

18、 MazePath(MazeType &maze,PostType start,PostType end)l 标记路径信息void PrintMaze(MazeType &maze)3. 函数之间的调用关系首先调用InitMaze(maze)，创建和初始化迷宫，初始化成功后输入迷宫的入口和出口坐标。接着迷宫求解调用MazePath(maze)并在其中调用可通位置的Pass(maze) 程序，并用FootPrint(maze,curpos)打印出足迹。如果非通，用MarkPrint(Maze)标记，直到最后，标记路径信息void PrintMaze(Maze)。四、调试分析 经过对程序的编制，调

19、试和运行，使我更好的掌握了栈基本性质和有关迷宫问题的解决方法，熟悉了各种调用的数据类型，在调试和运行过程中使我更加的了解和熟悉程序运行的环境，提高了我对程序调试分析的能力和对错误的纠正能力五、用户手册1.运行环境，执行文件1编制，调试和运行程序总是依赖所使用的语言环境，当然也令支持语言的系统程序的基础环境即操作系统环境的影响，此课程设计以Turbo C为依据，作为运行环境。2.用户界面Turbo C 3.操作过程 点击Turbo C的快捷图标，进入Turbo C的开发环境，进入“File”子菜单，选取“New”，开始输入一个新文件，编写新的程序。判断改错之后，按存盘。 对文件进行编译和链接在程

20、序编写后，需要将其编译成可执行文件，需要用“compile”中的F9进行编译和链接。然后看文件中是否存在错误，存在错误改正，直到没有错误。 运行 采用相关功能“compile”菜单，运行已形成好的可执行文件。如果源程序文件尚未编译或链接，选择此项目时系统也会进行编译和链接，如果程序中没有错误，再进行处理后的可执行文件。与此功能对应的快捷键为+六、测试结果输入数据：当入口为（1，1）时，出口为（8，8）用一个字符类型的二微数组表示迷宫，数组中的每个元素表示一个小方格，取值“0”（表示可以进出）或“1”（表示不可以进出）随机产生一个8*8的迷宫，其中使用迷宫障碍坐标如下：（1，3），（1，7），（

21、2，3），（2，7），（3，5），（3，6），（4，3），（4，4），（5，4），（6，2），（6，6），（7，2），（7，3），（7，4），（7，6），（7，7），（8，1），（-1，-1）输入过程如下图所示：输入时(-1，-1）结束，接着输入入口参数（1，1）然后输入出口参数（8，8），运行： 运行结果如下图所示：上图中”1”表示围墙和障碍物。”表示走过但不是通路.而”0”就是所要求的老鼠走过的最小路径.七、参考文献1 Richard F. Gilberg, Behrouz A. Forouzan. Data Structure. Brooks/Cole, Thomson Asia Pte

22、 Ltd, USA, 2000.2 严蔚敏, 吴伟民. 数据结构（第二版）. 北京：清华大学出版社, 1992.3 数据结构（C语言版） 李云清 杨庆红 揭安全 编著 人民邮电出版社4 C语言程序设计（第二版） 谭浩强 著 清华大学出版社5 数据结构课程设计 苏仕华 等编著 机械工业出版社八、附录原程序文件名清单:/base.h#include #include #include #define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -2typedef int Status;/stack.h#inclu

23、de base.h#define INIT_SIZE 100 /存储空间初始分配量#define INCREMENT 10 /存储空间分配增量typedef struct /迷宫中r行c列的位置 int r; int c;PostType;typedef struct int ord; /当前位置在路径上的序号 PostType seat;/当前坐标 int di; /往下一坐标的方向SElemType; /栈元素类型typedef struct SElemType* base;/栈基址,构造前销毁后为空 SElemType* top;/栈顶 int stackSize; /栈容量Stack;

24、 /栈类型Status InitStack(Stack &S) /构造空栈s S.base=(SElemType*)malloc(INIT_SIZE *sizeof(SElemType); if(!S.base) exit(OVERFLOW);/存储分配失败 S.top=S.base; S.stackSize=INIT_SIZE; return OK;/InitStackStatus StackEmpty(Stack S) /若s为空返回TRUE,否则返回FALSE if(S.top=S.base) return TRUE; return FALSE;/StackEmptyStatus Pus

25、h(Stack &S,SElemType e) /插入元素e为新的栈顶元素 if(S.top-S.base =S.stackSize)/栈满，加空间 S.base=(SElemType *)realloc(S.base,(S.stackSize+INCREMENT)*sizeof(SElemType); if(!S.base) exit(OVERFLOW); /存储分配失败 S.top=S.base+S.stackSize; S.stackSize+=INCREMENT; *S.top+=e; return OK;/pushStatus Pop(Stack &S,SElemType &e)/若

26、栈不空删除栈/顶元素用e返回并返回OK，否则返回ERROR if(S.top=S.base) return ERROR; e=*-S.top; return OK;/PopStatus DestroyStack(Stack &S)/销毁栈S, free(S.base); S.top=S.base; return OK;/DestroyStack/maze.c#include stack.h#define MAXLEN 10/迷宫包括外墙最大行列数目typedef struct int r; int c; char adrMAXLENMAXLEN;/可取 * #MazeType; /迷宫类型St

27、atus InitMaze(MazeType &maze)/初始化迷宫若成功返回TRUE,否则返回FALSE int m,n,i,j; printf(Enter row and column numbers: ); scanf(%d%d,&maze.r,&maze.c); /迷宫行和列数 for(i=0;i=maze.c+1;i+)/迷宫行外墙 maze.adr0i=1; maze.adrmaze.r+1i=1; /for for(i=0;i=maze.r+1;i+)/迷宫列外墙 maze.adri0=1; maze.adrimaze.c+1=1; for(i=1;i=maze.r;i+) f

28、or(j=1;jmaze.r | nmaze.c)/越界 exit(ERROR); maze.adrmn=1;/迷宫障碍用#标记 printf(Enter blocks coordinate(-1,-1) to end): ); scanf(%d%d,&m,&n); /while return OK;/InitMaze Status Pass(MazeType maze,PostType curpos)/当前位置可通则返回TURE,否则返回FALSE if(maze.adrcurpos.rcurpos.c= )/可通 return TRUE; else return FALSE;/PassSt

29、atus FootPrint(MazeType &maze,PostType curpos)/若走过并且可通返回TRUE,否则返回FALSE/在返回之前销毁栈S maze.adrcurpos.rcurpos.c=0;/*表示可通 return OK;/FootPrintPostType NextPos(PostType &curpos,int i)/指示并返回下一位置的坐标 PostType cpos; cpos=curpos; switch(i) /1.2.3.4分别表示东,南,西,北方向 case 1 : cpos.c+=1; break; case 2 : cpos.r+=1; brea

30、k; case 3 : cpos.c-=1; break; case 4 : cpos.r-=1; break; default: exit(ERROR); return cpos;/NextposStatus MarkPrint(MazeType &maze,PostType curpos)/曾走过但不是通路标记并返回OK maze.adrcurpos.rcurpos.c=;/表示曾走过但不通 return OK;/MarkPrintStatus MazePath(MazeType &maze,PostType start,PostType end) /若迷宫maze存在从入口start到e

31、nd的通道则求得一条存放在栈中 /并返回TRUE,否则返回FALSE Stack S; PostType curpos; int curstep;/当前序号,1.2.3.4分别表示东,南,西,北方向 SElemType e; InitStack(S); curpos=start; /设置当前位置为入口位置 curstep=1; /探索第一步 do if(Pass(maze,curpos)/当前位置可以通过,/即是未曾走到过的通道 FootPrint(maze,curpos);/留下足迹 e.ord=curstep; e.seat=curpos; e.di=1; Push(S,e); /加入路径

32、 if(curpos.r=end.r& curpos.c=end.c)if(!DestroyStack(S)/销毁失败exit(OVERFLOW);else return TRUE; /到达出口 else curpos=NextPos(curpos,1); /下一位置是当前位置的东邻 curstep+; /探索下一步 /else /if else /当前位置不通 if(!StackEmpty(S) Pop(S,e); while(e.di=4 & !StackEmpty(S) MarkPrint(maze,e.seat); Pop(S,e); /留下不能通过的标记,并退一步 /while if

33、(e.di 4) e.di+;/换下一个方向探索 Push(S,e); curpos=NextPos(e.seat,e.di);/设定当前位置是该/新方向上的相邻 /if /if /else while(!StackEmpty(S); if(!DestroyStack(S)/销毁失败 exit(OVERFLOW); else return FALSE;/MazePathvoid PrintMaze(MazeType &maze) /将标记路径信息的迷宫输出到终端(包括外墙) int i,j; printf(nShow maze path(*-pathway):nn); printf( ); for(i=0;i=maze.r+1;i+)/打印列数名 printf(%4d,i); printf(nn); for(i=0;i=maze.r+1;i+) printf(%2d,i);/打印行名 for(j=0;j=maze.c+1;j+) printf(%4c,maze.adrij);/输出迷宫/当前位置的标记 printf(nn); /PrintM