当前位置:首页 >> 数学 >>

迷宫求解

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

课题名称: 迷宫问题、八皇后问题 姓 学 专 班 名: 号: 业: 级: 杨帆 121842284 计算机科学与技术 计 1242 陈学进

指导教师:

迷宫求解
1. 问题描述

迷宫问题是实验心理学的一个经典问题。在该实验中,心理学家把一只老鼠从一个 无顶盖的大盒子的入口处赶进迷宫。迷宫中设置了很多隔壁,对前进方向形成了多 处障碍,心理学家在迷宫的唯一出口处放置了一块奶酪,吸引老鼠在迷宫中寻找通 路以到达出口。对同一只老鼠重复进行上述实验,一直到老鼠从入口走到出口,而 不走错一步。老鼠经过多次试验最终学会走通迷宫的路线。设计一个计算机程序对 任意设定的矩形迷宫,求出一条从入口到出口的通路,或得出没有通路的结论。

2. 设计思路
1)迷宫的建立 迷宫中存在通路和障碍,为了方便迷宫的建立,用 0 表示通路,用 1 表示障碍,这 样迷宫就可以用 0、1 矩阵来描述。建立一个大小为 m×n 的任意迷宫(迷宫数据可 由用户输入,也可由程序自动生成),并在屏幕上显示出来。 2)迷宫的储存 迷宫是一个矩形区域,可以使用二维数组表示迷宫,这样迷宫的每一个位置都可以 用唯一的行列号来指定,但是二维数组不能动态定义其大小,我们可以先定义一个 较大的二维数组 maze[m+2][n+2],然后用它的前 m 行 n 列来存放元素,即得到一个 m×n 的二维数组,这样(0,0)表示迷宫入口位置,(m-1,n-1)表示迷宫出口位置。 3)迷宫路径的搜索 首先从迷宫的入口开始,如果该位置就是迷宫出口,则已经找到了一条路径,搜索 工作结束。否则搜索其上、下、左、右位置是否为障碍,若不是障碍,就移动到该 位置,然后再从该位置开始搜索通往出口的路径;若是障碍就选择另一个相邻的位 置,并从它开始搜索路径。为防止搜索重复出现,则将已搜索过的位置标记为 2, 同时保留搜索的痕迹,在考虑进入下一个位置搜索之前,将当前位置保存在一个队 列中。如果该位置所有相邻的非障碍位置均被搜索过,且未找到通往出口的路径, 则表明不存在从入口到出口的路径。如果找到路径,则为最短路径。 以矩阵 0 0 1 0 1 为例 1 0 0 1 0 1 0 0 0 1 1 0 1 0 0 首先, 将位置(0,0)放入队列中, 其前节点为空, 从它开始搜索, 其标记由此变为 2, 由于其只有一个非障碍位置,所以接下来移动到(0,1),其前节点序号为 0,标记变 为 2,然后从(0,1)移动到(1,1),放入队列中,其前节点序号为 1,(1,1)存在(1, 2)、(2,1)两个可移动的位置,其前节点序号均为 2.对于每一个非障碍位置,它的 相邻非障碍节点均入队列,且它们的前节点序号均为该位置的序号,所以如果存在 路径,则从出口处节点的位置,逆序就可以找到其从入口到出口的通路。 由此得到最短路径:(0,0)(0,1)(1,1)(1,2)(2,2)(2,3)(3,3)(3,4)

3. 数据结构设计
在本程序中,迷宫的建立包括两个部分:系统自动生成迷宫和手动生成迷宫。迷宫 包括:行数(int m)、列数(int n),设置好后生成迷宫,按回车键等待系统求解迷 宫路径,若有解,则打印出迷宫的路径;无解,则没有通路,结束。 struct point /*建立迷宫节点*/ { int row,col,predecessor; }queue[512]; void shoudong_maze(int m,int n) int i,j; for(i=0;i<m;i++) for(j=0;j<n;j++) scanf("%d",&maze[i][j]); } /*手动生成迷宫*/

{

/*设置行、列数*/

void zidong_maze(int m,int n) { int i,j; for(i=0;i<m;i++) for(j=0;j<n;j++) maze[i][j]=rand()%2; }

/*自动生成迷宫*/

void result_maze(int m,int n) /*打印迷宫路径*/ { int i,j; for(i=0;i<m;i++) { for(j=0;j<n;j++) { if(maze[i][j]==0||maze[i][j]==2) if(maze[i][j]==1) if(maze[i][j]==3) } } }

4. 功能函数设计
1) 主函数 main() 2) 手动生成迷宫函数 void shoudong_maze(int m,int n) { int i,j; for(i=0;i<m;i++) for(j=0;j<n;j++) scanf("%d",&maze[i][j]); } 3) 自动生成迷宫函数

void zidong_maze(int m,int n) { for(i<=m) for(j<=n) maze[i][j]=rand()%2 } 4) 将迷宫打印成图形 void print_maze(int m,int n) 5) 打印迷宫路径 void result_maze(int m,int n) 6) 搜索迷宫路径 ①迷宫中队列入队操作 void enqueue(struct point p) { tail++ } ②迷宫中队列出队操作 struct point dequeue(struct point p) { head++; return que[head-1]; } ③判断队列是否为空 int is_empty() { return head==tail while(is_empty()) return 0; } ④访问迷宫矩阵中节点 void visit(int row,int col,int maze[102][102]) { struct point visit_point={row,col,head-1}; maze[row][col]=2; enqueue(visit_point); } ⑤路径求解 void mgpath(int maze[102][102],int m,int n) { X=1;

struct point p={0,0,-1}; if(maze[p.row][p.col]==1) { printf("\n====================================\n"); printf("此迷宫无解\n\n");X=0;return 0;} maze[p.row][p.col]=2; enqueue(p); /*先定义入口节点为 struct point p={0,0,-1},从 maze[0][0]开始访问。如果入口处即 为障碍,则此迷宫无解,返回 0 ,程序结束。否则访问入口节点,将入口节点标记为访问 过 maze[p.row][p.col]=2,调用函数 enqueue(p)将该节点入队。*/ while(!is_empty()) /*判断队列是否为空*/ { p=dequeue(); if((p.row==m-1)&&(p.col==n-1)) break;/*找到了路径,结束*/ if((p.col+1<n)&&(maze[p.row][p.col+1]==0)) visit(p.row,p.col+1,maze); /*没到迷宫的右边界, 并且该位置 的右方是通路,则将右边的节点入队标记为已访问*/ if((p.row+1<m)&&(maze[p.row+1][p.col]==0)) visit(p.row+1,p.col,maze); /*没到迷宫的下边界, 并且该位置 的下方是通路,则将下边的节点入队标记为已访问*/ if((p.col-1>=0)&&(maze[p.row][p.col-1]==0)) visit(p.row,p.col-1,maze); /*没到迷宫的左边界, 并且该位置 的左方是通路,则将左边的节点入队标记为已访问*/ if((p.row-1>=0)&&(maze[p.row-1][p.col]==0)) visit(p.row-1,p.col,maze); /*没到迷宫的上边界, 并且该位置 的上方是通路,则将上边的节点入队标记为已访问*/ } if(p.row==m-1&&p.col==n-1) { printf("\n============================================\n"); printf("迷宫路径为:\n"); printf("(%d,%d)\n",p.row,p.col); maze[p.row][p.col]=3; while(p.predecessor!=-1) { p=queue[p.predecessor]; printf("(%d,%d)\n",p.row,p.col); maze[p.row][p.col]=3; /*将迷宫路径打印出来*/ } } else { printf("\n======================================\n"); printf("此迷宫无解!\n\n");X=0;} return 0; }

5. 程序代码
#include"stdlib.h" #include"stdio.h"

#define N 100 #define M 100 int X; int maze[M+2][N+2]; struct point{ int row,col,predecessor; }queue[512]; int head=0,tail=0; void shoudong_maze(int m,int n) { int i,j; printf("\n\n"); printf("请按行输入迷宫,0 表示通路,1 表示障碍:\n\n"); for(i=0;i<m;i++) for(j=0;j<n;j++) scanf("%d",&maze[i][j]); } void zidong_maze(int m,int n) { int i,j; printf("\n 迷宫生成中……\n\n"); system("pause"); for(i=0;i<m;i++) for(j=0;j<n;j++) maze[i][j]=rand()%2; } void print_maze(int m,int n) { int i,j; printf("\n 迷宫生成如下:\n\n"); printf("迷宫入口\n"); printf("↓"); for(i=0;i<m;i++) { printf("\n"); for(j=0;j<n;j++) { if(maze[i][j]==0) printf("☆"); if(maze[i][j]==1) printf("★"); } } printf("→迷宫出口\n"); } void result_maze(int m,int n) { int i,j; printf("迷宫通路(用◇表示)如下所示:\n\t"); for(i=0;i<m;i++) { printf("\n"); for(j=0;j<n;j++)

{ if(maze[i][j]==0||maze[i][j]==2) printf("☆"); if(maze[i][j]==1) printf("★"); if(maze[i][j]==3) printf("◇"); } } } void enqueue(struct point p) { queue[tail]=p; tail++; } struct point dequeue() { head++; return queue[head-1]; } int is_empty() { return head==tail; } void visit(int row,int col,int maze[41][41]) { struct point visit_point={row,col,head-1}; maze[row][col]=2; enqueue(visit_point); } int mgpath(int maze[41][41],int m,int n) { X=1; struct point p={0,0,-1}; if(maze[p.row][p.col]==1) { printf("\n===============================================\n"); printf("此迷宫无解\n\n"); X=0; return 0; } maze[p.row][p.col]=2; enqueue(p); while(!is_empty()) { p=dequeue(); if((p.row==m-1)&&(p.col==n-1)) break; if((p.col+1<n)&&(maze[p.row][p.col+1]==0)) visit(p.row,p.col+1,maze); if((p.row+1<m)&&(maze[p.row+1][p.col]==0)) visit(p.row+1,p.col,maze); if((p.col-1>=0)&&(maze[p.row][p.col-1]==0)) visit(p.row,p.col-1,maze); if((p.row-1>=0)&&(maze[p.row-1][p.col]==0)) visit(p.row-1,p.col,maze); } if(p.row==m-1&&p.col==n-1) { printf("\n=================================================\n"); printf("迷宫的路径为:\n");

printf("(%d,%d)\n",p.row,p.col); maze[p.row][p.col]=3; while(p.predecessor!=-1) { p=queue[p.predecessor]; printf("(%d,%d)\n",p.row,p.col); maze[p.row][p.col]=3; } } else { printf("\n=================================================\n"); printf("此迷宫无解!\n\n"); X=0; } return 0; } void main() { int i,m,n,cycle=0; while(cycle!=(-1)) { printf(" 欢迎进入迷宫求解系统 \n"); printf(" 杨帆 121842284 \n"); printf("****************************************************\n"); printf(" ◆ 手动生成迷宫 请选择:1 \n"); printf(" ◆ 自动生成迷宫 请选择:2 \n"); printf(" ◆ 退出 请选择:3 \n\n"); printf("****************************************************\n"); printf("\n"); printf("请选择你的操作:\n"); scanf("%d",&i); switch(i) { case 1:printf("\n 请输入迷宫的行数:"); scanf("%d",&m); printf("\n"); printf("请输入迷宫的列数:"); scanf("%d",&n); while((m<=0||m>39)||(n<=0||n>39)) { printf("\n 对不起,你输入的迷宫行列数超出预设范围,请重新输入:\n\n"); printf("请输入迷宫的行数:"); scanf("%d",&m); printf("\n"); printf("请输入迷宫的列数:"); scanf("%d",&n); } shoudong_maze(m,n); print_maze(m,n);

mgpath(maze,m,n); if(X!=0) result_maze(m,n); printf("\n\nPress Enter Contiue!\n");getchar(); while(getchar()!='\n'); break; case 2: printf("\n 请输入迷宫的行数:"); scanf("%d",&m); printf("\n"); printf("请输入迷宫的列数:"); scanf("%d",&n); while((m<=0||m>100)||(n<=0||n>100)) {printf("\n 对不起,你输入的迷宫行列数超出预设范围,请重新输入:\n\n"); printf("请输入迷宫的行数:"); scanf("%d",&m); printf("\n"); printf("请输入迷宫的列数:"); scanf("%d",&n); } zidong_maze(m,n); print_maze(m,n); mgpath(maze,m,n); if(X!=0) result_maze(m,n); printf("\n\n Press Enter Contiue! \n"); getchar(); while(getchar()!='\n'); break; case 3: cycle=(-1); break; default:printf("\n"); printf("对不起,你的输入有误!\n"); printf("\n Press Enter Contiue! \n"); getchar(); while(getchar()!='\n'); break; } } }

6. 运行与测试
选择 1,则手动生成迷宫:

选择 2,则自动生成迷宫:

八皇后问题
1、 问题描述
八皇后问题是一个古老而著名的问题, 该问题是由十九世纪著名的数学家 高斯 1850 年提出的。在国际象棋中,皇后是最有权利的一个棋子,只要别的 棋子在它的同一行或同一列或同一斜线(正斜线或反斜线)上时,它就能把对 方棋子吃掉。 所以高斯提出了一个问题: 在 8*8 格的国际象棋上摆放八个皇后, 使其不能相互攻击,即任意两个皇后都不能处于同一列、同一行、同一条斜线 上面,问共有多少种解法。

2、 设计思路
1)解决行、列、斜线的冲突 行: 当第 i 行被某个皇后占领后, 则同一行上的所有空格都不能再放皇后, 还要把以 i 为下标的位置标记为已占领 列:规定每一列放置一个皇后,保证不会造成列上的冲突 对角线:对角线有正对角线和反对角线两个方向。当第 i 个皇后占领了第 j 列后,要同时把以(i+j)、(i-j)为下标的位置标记为已占领 2)数据结构的实现 数组 a[i]:a[i]表示第 i 个皇后放置的列 (1<=i<=8) 对角线数组:b[j](正对角线),c[j](反对角线),根据程序决定正反对角 线是否放入皇后

3、 数据结构设计
int Count=0; int Site[QUEENS]; void Queen(int n); { int i; if(n==QUEENS) { Output(); return;
/*记录解的序号*/ /*记录皇后放置在各行的位置*/ /*递归求解函数*/

} } void Output(); /*输出一个解法*/ { int i; for(i=0;i<QUEENS;i++) /*依次输出各行上皇后的位置*/ } int IsValid(int n); /*判断第 n 个皇后放后,是否有冲突*/ { int i; for(i=0;i<n;i++) /*将第 n 个皇后和前面 n-1 个皇后比较*/ { if(Site[i]==Site[n])/*两个皇后在同一列上,返回 0*/ return 0; if(abs(Site[i]-Site[n])==(n-i))/*两个皇后在同一对角线上,返回 0*/ return 0; } return 1; /*没有冲突,返回 1*/ }

4、 功能函数设计
1)求解函数 void Queen(int n):递归放置第 n 个皇后,判断第 n 个皇后放上去之 后,是否无冲突。 2)解法的输出 void Output():输出一种解法,先输出解的序号,再依次输出各行上 皇后的位置,即皇后所在的列数。

5、 程序代码
#include <stdio.h> #include <stdlib.h> #include <conio.h> #include <math.h> #define QUEENS 8 int Count=0; int Site[QUEENS]; void Queen(int n); void Output(); int IsValid(int n); void main() { printf(" 欢迎进入八皇后问题求解系统 \n");

printf(" 杨帆 121842284 \n"); printf("******************************************\n"); printf("每一行皇后放置的列数:\n"); printf("\n\n"); Queen(0); } void Queen(int n) { int i; if(n==QUEENS) { Output(); return; } for(i=1;i<=QUEENS;i++) { Site[n]=i; if(IsValid(n)) Queen(n+1); } } int IsValid(int n) { int i; for(i=0;i<n;i++) { if(Site[i]==Site[n]) return 0; if(abs(Site[i]-Site[n])==(n-i)) return 0; } return 1; } void Output() { int i; printf("第%-2d 组: ",++Count); for(i=0;i<QUEENS;i++) printf("%3d",Site[i]); printf("\n\n"); }

6、 运行与测试


相关文章:
数据结构 迷宫求解.doc
数据结构 迷宫求解_调查/报告_表格/模板_实用文档。数据结构实验报告 迷宫求解C++ 【完成题目 3】迷宫求解 【问题描述】以一个 m*n 的长方阵表示迷宫,0 ...
迷宫问题求解.doc
迷宫问题求解 - 课程设计报告 课题名称: 姓学专班名: 号: 业: 级: 迷宫问题的求解及演示 计算机与信息学院 指导教师: 第 1 页共 17 页 数据结构课程设计...
迷宫求解细节.doc
迷宫求解细节 - 数据结构课程设计 一、 需求分析 1.选题理由 本次课设我选择了迷宫问题, 迷宫求解是数据结构课程的一个经典问题, 迷宫问题要求寻找一条从入口到...
迷宫求解参考答案.txt
迷宫求解参考答案 - #include<stdio.h> #include&l...... (%d,%d)\n",e.ord,e.seat.x,e.seat.y); return OK; } //---迷宫求解的具体...
迷宫的求解.doc
迷宫求解 - 课程设计的名称:迷宫求解问题 1. 问题描述:迷宫只有两个门,一个叫做入口,另一个叫做出口。把一只老鼠从一个无 顶盖的大盒子的入口处赶进迷宫...
迷宫求解.doc
迷宫求解 - 数据结构课程设计(详细步骤)... 迷宫求解_数学_高中教育_教育
迷宫求解 数据结构 课业设计.doc
迷宫求解 数据结构 课业设计 - 设计题目: 迷宫问题求解 问题描述 迷宫问题是
迷宫求解实验报告.doc
\n"); continue; } } while(end.r>maze.r || end.c>maze.c); if(!MazePath(maze,start,end))//迷宫求解 printf("\n 没有路径!\n"); else ...
数据结构迷宫求解_图文.ppt
数据结构迷宫求解 - 迷宫求解问题 迷宫【问题描述】 ? ? 以一个 m*n的长
迷宫问题的求解.doc
迷宫问题的求解_计算机软件及应用_IT/计算机_专业资料。数据结构实验 程序设计
数据结构-迷宫求解算法.doc
数据结构-迷宫求解算法 - #include <stdio.h> #
数据结构 迷宫问题求解.doc
数据结构 迷宫问题求解 - 安徽大学计算机实验教学中心 1 学号 实验日期 专业
编程题迷宫求解.doc
编程题迷宫求解 - 迷宫求解问题 摘要:用矩阵表示迷宫,将矩阵表示的迷宫转换成无
数据结构课程设计迷宫问题求解.doc
数据结构课程设计迷宫问题求解 - 扬州大学信息工程学院 《数据结构》 ---课程设计报告 题目: 班级: 学号: 姓名: 迷宫问题 计科 1301 131404126 张艳 指导教师:...
迷宫求解:求任意迷宫所有路径.doc
迷宫求解:求任意迷宫所有路径 - #include <stdio.h>
求解迷宫问题 (c语言,很详细哦).doc
求解迷宫问题 (c语言,很详细哦) - 求迷宫问题就是求出从入口到出口的路径。在求解时,通常用的是 “穷举求解”的方法,即从入口出发,顺某一方向向前试探,若能...
迷宫求解参考答案.txt
迷宫求解参考答案 - 迷宫问题(栈) 问题描述: 以一个m*n的长方阵表示迷宫,
迷宫问题的求解.doc
迷宫问题的求解 - 【数据结构课程设计】C++环境下利用栈实现迷宫求解问题。... 【数据结构课程设计】C++环境下利用栈实现迷宫求解问题。 迷宫问题求解一.问题描述:请...
迷宫问题算法实现.doc
迷宫问题算法实现 - 一、需求分析 本课程设计是解决迷宫求解的问题,从入口出发,
迷宫问题的C,C++算法实现.doc
迷宫问题的C,C++算法实现 - 基于栈的 C 语言迷宫问题与实现 一. 问题描述 多年以来, 迷宫问题一直是令人感兴趣的题目。 实验心理学家训练老鼠在迷宫中寻找食物...