数据结构程序设计课题

数据结构程序设计课题12页)

-CAL-FENGHAI.-(YICAI)-Company One1

-CAL-本页仅作为文档封面，使用请直接删除

总

(

衡阳师范学院

工科课程设计 -《数据结构》

课程设计报告

题 目：迷宫问题（栈） 学 号：

姓 名：鲁向阳 肖吟月 班 级：物联网班（1405） 指导教师：王杰老师 日 期： 2016年 6月

目录

1概述 ................................... 错误!未定义书签。

课程设计目的...................... 错误!未定义书签。 开发环境 ......................... 错误!未定义书签。 任务分配 ......................... 错误!未定义书签。

2需求分析 ............................... 题目内容 ......................... 设计思想说明......................

数据结构设计...................... 3算法的设计 ............................. 定义坐标（X，Y）: ................. 定义方向： ....................... 定义/链表结点： ................... 定义栈： .........................

定义迷宫定义移动的4个方向： ...... 4各模块的伪码算法 ....................... 根据输入产生一个8*8的迷宫： ...... 探索路径函数： ....................

输出迷宫 ......................... 5函数的调用关系图 .......................

自动生成迷宫运行情况 .............. 7心得体会 ............................... - 3 -

错误!未定义书签。

错误!未定义书签。 错误!未定义书签。 错误!未定义书签。

错误!未定义书签。

错误!未定义书签。 错误!未定义书签。 错误!未定义书签。 错误!未定义书签。 错误!未定义书签。

错误!未定义书签。

错误!未定义书签。 错误!未定义书签。 错误!未定义书签。

错误!未定义书签。

错误!未定义书签。

错误!未定义书签。

参考文献 ................................. 错误!未定义书签。 附 录 ................................... 错误!未定义书签。

- 4 -

1概述

1.1 课程设计目的

本次课程设计是迷宫求解问题，主要是模拟从入口到出口的通路。程序中的数据采取的是“栈”作为数据的逻辑结构，并且使用链式存储结构，即是实现一个以链表作存储结构的栈类型。本课程设计实现了链栈的建立，入栈，出栈，判断栈是否为空的方法，关键的是迷宫通路路径的“穷举求解”和递归求解的方法。 1.2 开发环境

具有Intel酷睿i3处理器且满足以下要求的计算机：4GB 内存，500GB 硬盘；安装Visual C++ 。 1.3 任务分配

两人一起查找相关资料，整合并进行探讨。其中一人通过查找的资料先行拟定文件的大纲，初步定稿后，然后再由另一个人进行进一步加工，细化，最后两人一起核实文件，进行进一步的升华，最终完成该任务。

5

2需求分析

2.1 题目内容

以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 2.2 设计思想说明

计算机解迷宫通常用的是“穷举求解”方法，首先从迷宫的入口开始，如果该位置就是迷宫出口，则已经找到了一条路径，搜索工作结束。否则从入口出发，顺着某个方向进行探索，若能走通，则继续往前进，否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设的迷宫没有通路。

可以用二维数组存储迷宫数据，通常设定入口点的下标为（1，1），出口点的下标为（n,n）。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫中任一位置均可约定有东、南、西、北四个方向可通。

要实现上述算法，需要用到栈的思想。栈里面压的是走过的路径，若遇到死路，则将该位置在栈的顶层）弹出，再进行下一次判断；若遇到通路，则将该位置压栈并进行下一次判断。如此反复循环，直到程序结束。此时，若迷宫有通路，则栈中存储的是迷宫通

6

路坐标的倒序排列，再把所有坐标顺序排列好后，即可得到正确的迷宫通路。 2.3 数据结构设计

（1）以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。迷宫的四周有一圈障碍。

（2）程序输出的结果以三元组（i,j,di）的形式输出，其中：（i,j）指示迷宫中的一个坐标，di表示走到下一坐标的方向，di的取值为0、1、2、3分别表示北、东、南、西。

（3）若设定的迷宫存在通路，则以方阵形式将迷宫及其通路输出到标准输出文件上，对于迷宫中的每个方块，有上下左右4个方块相邻，第i行第j列的当前方块的位置记为（i,j）,规定上方方块为方位0，并按顺时针方向递增编号。在试探过程中，假设按从方位0到方位3的顺序查找下一个可走的方块。

（4）先将入口进栈（其初始方位设置为-1），在栈不空时循环：取栈顶方块（不退栈），若该方块是出口，则输出栈中所有方块即为路径，否则，找下一个可走的相邻方块，若不存在这样的方块，说明当前路径不可能走通，则回溯。也就是恢复当前方块为0后退栈；若存在这样的方块，则将这个可走的相邻方块进栈（其初始方位设置为-1）。

7

3算法的设计

3.1 定义坐标（X，Y）

#include #include using namespace std; struct Coor {

int row; int column; int direction; }; 3.2 定义方向

struct Move {

int row; int column;

8

};

3.3 定义/链表结点

struct LinkNode {

Coor data; LinkNode *next; }; 3.4 定义栈

class stack { private:

LinkNode *top; public:

stack(); ~stack(); void Push(Coor data); Coor Pop(); Coor GetPop(); void Clear(); bool IsEmpty(); 9

};

3.5 定义迷宫定义移动的4个方向

Move move[4]={{0,1},{1,0},{0,-1},{-1,0}}; 6、几个函数功能的描述: stack();

ow==().row&&().column==().column))

(Temp2);

ow; olumn;

ow==().row&&().column==().column)

10

ow-temp->; olumn-temp->;

11

ow==().row&&().column==().column))

(Temp2);

ow; olumn; ow==().row&&().column==().column) ow-temp->; olumn-temp->; //列坐标方向

if(a==1) temp->=1; //方向向下，用1表示 else if(b==1) temp->=2; //方向向右，用2表示 else if(a==-1) temp->=3; //方向向上，用3表示 else if(b==-1) temp->=4; //方向向左，用4表示

12

}

(temp->data); //把新位置入栈 delete temp;

cout<<\"坐标（row,column,direction）中x在指向当前位置

所在的行数，y指向当前位置所在的列数，\";

cout<<\"direction表示下一位置走向。\"<//输出路径，包括行坐标，列坐标，下一个位置方向 while(!()) //栈非空，继续输出 { data=();

cout<<'('<<<<','<<<<','<<<<\输出行坐标，列

坐标 switch //输出相应的方向 { case 1:cout<<\"↓)\\n\";break; case 2:cout<<\"→)\\n\";break; case 3:cout<<\"↑)\\n\";break; case 4:cout<<\"←)\\n\";break; case 0:cout<<\")\\n\";break;

}

}

}

13

void PrintPath2(int m,int n,stack p,int **maze) //输出路径 { }

void Restore(int **maze,int m,int n) //恢复迷宫 {

int i,j;

for(i=0;ifor(j=0;jif(maze[i][j]==8) //恢复探索过位

cout<<\"迷宫的路径为\\n\"; for (int i = 0; i < m+2; ++i ) { }

for (int j = 0; j < n+2; ++j)

cout << maze[i][j]<<\" \";

cout << endl;

置，即把-1恢复为0 }

14

}

maze[i][j]=0;

15