迷宫问题数据结构实验报告

数据结构实验报告

实习1 栈和队列及其应用

题目：迷宫问题

班级：1403011班 姓名：付尧 学号：[1**********] 完成日期：2015.11.25

一．需求分析

1．以二维数组maze[m][n]表示迷宫，再为周围加一圈障碍。数组以元素值为0表示通路，1表示障碍。

2．用户以文件的形式输入迷宫的数据：文件中第一行的数据为迷宫的行数m和列数n；从第二行到第m+1行（每行n个数）为迷宫值。

3．迷宫的入口位置默认为（1，1），出口位置默认为（m，n）。

4．程序执行的命令包括：

（1）创建迷宫；（2）求解迷宫；（3）输出迷宫的解；（4）结束。

5．测试数据

测试数据见原题，已存储在maze.txt文件中。输出内容为：(1,1,1),(2,1,1),(3,1,1),(4,1,1),(5,1,1),(6,1,1),(5,1,2),(5,2,2),(5,3,1),(6,3,2),(6,4,2),(6,5,3),(5,5,2),(5,6,2),(5,7,1),(6,7,1),(7,7,1),(8,7,1),(9,7,2),(9,8,0)

二．概要设计

为了实现程序上述功能，应以队列为存储结构。

1. 基本操作：

void GoMaze( )

操作结果：求解迷宫，并输出一条通路。

2． 本程序包含三个模块：

（1）构建迷宫及主程序模块;

（3）执行迷宫求解模块；

三．详细设计

1.元素类型，结点类型和指针类型：

typedef struct {

int ord;

int x,y;

int di;

int pre;

}elem;

elem **maze;

int i,j,m,n,a,b;

int c=0;

queue s;

6．每个模块的分析：

（1）构建迷宫及主程序模块：

int main(){

FILE *mazefile;

mazefile = fopen("maze.txt","r");

fscanf(mazefile,"%d %d\n",&a,&b); //读入行数和列数

m=a+2;

n=b+2; //在周围添加一圈障碍后的行数和列数

maze = new elem*[m];

for (i=0;i

maze[i] = new elem [n];

for (i=0;i

for (int j=0;j

char ch;

maze[i][j].x=i;

maze[i][j].y=j;

maze[i][j].pre=0;

maze[i][j].di=0;

if(i==0||j==0||i==m-1||j==n-1)

maze[i][j].ord=1;

else{

fscanf(mazefile,"%c",&ch);

maze[i][j].ord=(ch-'0');

}

}

fscanf(mazefile,"\n");

}

GoMaze(1,1); //执行迷宫求解函数

printf("(%d,%d,0)",m-2,n-2); //输出终点（迷宫求解函数只输出除终点外的路径）

return 0;

}

（2）执行迷宫求解模块：

void GoMaze(int x,int y){

if(x==(m-2)&&y==(n-2)) //创建计数器，保证递归终止条件

c++;

if(x+1

if(maze[x][y].pre==3) //弹出遇到死路的元素

s.pop();

else{

maze[x+1][y].ord=1;

maze[x][y].di

=1; //设立方向标志

maze[x+1][y].pre=1; //为此元素做标记，防止再次访问

s.push(maze[x][y]); //元素入队列

GoMaze(x+1,y); //进入递归

maze[x+1][y].ord=0; //将元素恢复

}

}

if(y+1

if(maze[x][y].pre==4)

s.pop();

else{

maze[x][y+1].ord=1;

maze[x][y].di=2;

maze[x][y+1].pre=2;

s.push(maze[x][y]);

GoMaze(x,y+1);

maze[x][y+1].ord=0;

}

}

if(x-1>=0&&maze[x-1][y].ord==0&&c==0){

if(maze[x][y].pre==1)

s.pop();

else{

maze[x-1][y].ord=1;

maze[x][y].di=3;

maze[x-1][y].ord=3;

s.push(maze[x][y]);

GoMaze(x-1,y);

maze[x-1][y].ord=0;

}

}

if(y-1>=0&&maze[x][y-1].ord==0&&c==0){

if(maze[x][y].pre==2)

s.pop();

else{

maze[x][y-1].ord=1;

maze[x][y].di=4;

maze[x][y-1].pre=4;

s.push(maze[x][y]);

GoMaze(x,y-1);

maze[x][y-1].ord=0;

}

}

while(!s.empty()){ //输出队列内已储存的通路

elem t=s.front();

printf("(%d,%d,%d),",t.x,t.y,t.di);

s.pop(); //弹出元素

}

}

四．调试分析

（1）设计过程中对递归结束的条件感到疑惑，经过考虑，设立了一个计数器c，解决问题。

（2）程序采用c++中queue函数，减少了c语言中构建队列的冗长代码，方便快捷。

（3）这道题第一眼看觉得仅仅是个递归的简单应用，但实际操作还是有很多需要考虑的地方，比如如何终止递归，防止其他函数再次执行函数。

五．用户使用说明

（1）本程序的运行环境为VS2010。

（2）进入演示程序后即直接输出结果。

六．测试结果

当正确添加文件，就可以得出结果(1,1,1),(2,1,1),(3,1,1),(4,1,1),(5,1,1),(6,1,1),(5,1,2),(5,2,2),(5,3,1),(6,3,2),(6,4,2),(6,5,3),(5,5,2),(5,6,2),(5,7,1),(6,7,1),(7,7,1),(8,7,1),(9,7,2),(9,8,0)

七．附录

#include

#include

using namespace std;

typedef struct {

int ord;

int x,y;

int di;

}elem;

elem **maze;

int i,j,m,n;

int c=0;

queue s;

void GoMaze(int x,int y){

if(x==(m-2)&&y==(n-2))

c++;

if(x+1

maze[x+1][y].ord=1;

maze[x][y].di=1;

s.push(maze[x][y]);

GoMaze(x+1,y);

maze[x+1][y].ord=0;

}

if(y+1

maze[x][y+1].ord=1;

maze[x][y].di=2;

s.push(maze[x][y]);

GoMaze(x,y+1);

maze[x][y+1].ord=0;

}

if(x-1>=0&&maze[x-1][y].ord==0&&c==0){

maze[x-1][y].ord=1;

maze[x][y].di=3;

s.push(maze[x][y]);

GoMaze(x-1,y);

maze[x-1][y].ord=0;

}

if(y-1>=0&&maze[x][y-1].ord==0&&c==0){

maze[x][y-1].ord=1;

ma

ze[x][y].di=4;

s.push(maze[x][y]);

GoMaze(x,y-1);

maze[x][y-1].ord=0;

}

if(!s.empty()){

elem t=s.front();

printf("(%d,%d,%d)\n",t.x,t.y,t.di);

s.pop();

}

}

int main(){

FILE *mazefile;

mazefile = fopen("maze.txt","r");

fscanf(mazefile,"%d %d\n",&m,&n);

maze = new elem*[m];

for (i=0;i

maze[i] = new elem [n];

for (i=0;i

for (int j=0;j

char ch;

fscanf(mazefile,"%c",&ch);

maze[i][j].ord=(ch-'0');

maze[i][j].x=i;

maze[i][j].y=j;

}

fscanf(mazefile,"\n");

}

GoMaze(1,1);

printf("(%d,%d,0)",m-2,n-2);

return 0;

}

数据结构实验报告

实习1 栈和队列及其应用

题目：迷宫问题

班级：1403011班 姓名：付尧 学号：[1**********] 完成日期：2015.11.25

一．需求分析

1．以二维数组maze[m][n]表示迷宫，再为周围加一圈障碍。数组以元素值为0表示通路，1表示障碍。

2．用户以文件的形式输入迷宫的数据：文件中第一行的数据为迷宫的行数m和列数n；从第二行到第m+1行（每行n个数）为迷宫值。

3．迷宫的入口位置默认为（1，1），出口位置默认为（m，n）。

4．程序执行的命令包括：

（1）创建迷宫；（2）求解迷宫；（3）输出迷宫的解；（4）结束。

5．测试数据

测试数据见原题，已存储在maze.txt文件中。输出内容为：(1,1,1),(2,1,1),(3,1,1),(4,1,1),(5,1,1),(6,1,1),(5,1,2),(5,2,2),(5,3,1),(6,3,2),(6,4,2),(6,5,3),(5,5,2),(5,6,2),(5,7,1),(6,7,1),(7,7,1),(8,7,1),(9,7,2),(9,8,0)

二．概要设计

为了实现程序上述功能，应以队列为存储结构。

1. 基本操作：

void GoMaze( )

操作结果：求解迷宫，并输出一条通路。

2． 本程序包含三个模块：

（1）构建迷宫及主程序模块;

（3）执行迷宫求解模块；

三．详细设计

1.元素类型，结点类型和指针类型：

typedef struct {

int ord;

int x,y;

int di;

int pre;

}elem;

elem **maze;

int i,j,m,n,a,b;

int c=0;

queue s;

6．每个模块的分析：

（1）构建迷宫及主程序模块：

int main(){

FILE *mazefile;

mazefile = fopen("maze.txt","r");

fscanf(mazefile,"%d %d\n",&a,&b); //读入行数和列数

m=a+2;

n=b+2; //在周围添加一圈障碍后的行数和列数

maze = new elem*[m];

for (i=0;i

maze[i] = new elem [n];

for (i=0;i

for (int j=0;j

char ch;

maze[i][j].x=i;

maze[i][j].y=j;

maze[i][j].pre=0;

maze[i][j].di=0;

if(i==0||j==0||i==m-1||j==n-1)

maze[i][j].ord=1;

else{

fscanf(mazefile,"%c",&ch);

maze[i][j].ord=(ch-'0');

}

}

fscanf(mazefile,"\n");

}

GoMaze(1,1); //执行迷宫求解函数

printf("(%d,%d,0)",m-2,n-2); //输出终点（迷宫求解函数只输出除终点外的路径）

return 0;

}

（2）执行迷宫求解模块：

void GoMaze(int x,int y){

if(x==(m-2)&&y==(n-2)) //创建计数器，保证递归终止条件

c++;

if(x+1

if(maze[x][y].pre==3) //弹出遇到死路的元素

s.pop();

else{

maze[x+1][y].ord=1;

maze[x][y].di

=1; //设立方向标志

maze[x+1][y].pre=1; //为此元素做标记，防止再次访问

s.push(maze[x][y]); //元素入队列

GoMaze(x+1,y); //进入递归

maze[x+1][y].ord=0; //将元素恢复

}

}

if(y+1

if(maze[x][y].pre==4)

s.pop();

else{

maze[x][y+1].ord=1;

maze[x][y].di=2;

maze[x][y+1].pre=2;

s.push(maze[x][y]);

GoMaze(x,y+1);

maze[x][y+1].ord=0;

}

}

if(x-1>=0&&maze[x-1][y].ord==0&&c==0){

if(maze[x][y].pre==1)

s.pop();

else{

maze[x-1][y].ord=1;

maze[x][y].di=3;

maze[x-1][y].ord=3;

s.push(maze[x][y]);

GoMaze(x-1,y);

maze[x-1][y].ord=0;

}

}

if(y-1>=0&&maze[x][y-1].ord==0&&c==0){

if(maze[x][y].pre==2)

s.pop();

else{

maze[x][y-1].ord=1;

maze[x][y].di=4;

maze[x][y-1].pre=4;

s.push(maze[x][y]);

GoMaze(x,y-1);

maze[x][y-1].ord=0;

}

}

while(!s.empty()){ //输出队列内已储存的通路

elem t=s.front();

printf("(%d,%d,%d),",t.x,t.y,t.di);

s.pop(); //弹出元素

}

}

四．调试分析

（1）设计过程中对递归结束的条件感到疑惑，经过考虑，设立了一个计数器c，解决问题。

（2）程序采用c++中queue函数，减少了c语言中构建队列的冗长代码，方便快捷。

（3）这道题第一眼看觉得仅仅是个递归的简单应用，但实际操作还是有很多需要考虑的地方，比如如何终止递归，防止其他函数再次执行函数。

五．用户使用说明

（1）本程序的运行环境为VS2010。

（2）进入演示程序后即直接输出结果。

六．测试结果

当正确添加文件，就可以得出结果(1,1,1),(2,1,1),(3,1,1),(4,1,1),(5,1,1),(6,1,1),(5,1,2),(5,2,2),(5,3,1),(6,3,2),(6,4,2),(6,5,3),(5,5,2),(5,6,2),(5,7,1),(6,7,1),(7,7,1),(8,7,1),(9,7,2),(9,8,0)

七．附录

#include

#include

using namespace std;

typedef struct {

int ord;

int x,y;

int di;

}elem;

elem **maze;

int i,j,m,n;

int c=0;

queue s;

void GoMaze(int x,int y){

if(x==(m-2)&&y==(n-2))

c++;

if(x+1

maze[x+1][y].ord=1;

maze[x][y].di=1;

s.push(maze[x][y]);

GoMaze(x+1,y);

maze[x+1][y].ord=0;

}

if(y+1

maze[x][y+1].ord=1;

maze[x][y].di=2;

s.push(maze[x][y]);

GoMaze(x,y+1);

maze[x][y+1].ord=0;

}

if(x-1>=0&&maze[x-1][y].ord==0&&c==0){

maze[x-1][y].ord=1;

maze[x][y].di=3;

s.push(maze[x][y]);

GoMaze(x-1,y);

maze[x-1][y].ord=0;

}

if(y-1>=0&&maze[x][y-1].ord==0&&c==0){

maze[x][y-1].ord=1;

ma

ze[x][y].di=4;

s.push(maze[x][y]);

GoMaze(x,y-1);

maze[x][y-1].ord=0;

}

if(!s.empty()){

elem t=s.front();

printf("(%d,%d,%d)\n",t.x,t.y,t.di);

s.pop();

}

}

int main(){

FILE *mazefile;

mazefile = fopen("maze.txt","r");

fscanf(mazefile,"%d %d\n",&m,&n);

maze = new elem*[m];

for (i=0;i

maze[i] = new elem [n];

for (i=0;i

for (int j=0;j

char ch;

fscanf(mazefile,"%c",&ch);

maze[i][j].ord=(ch-'0');

maze[i][j].x=i;

maze[i][j].y=j;

}

fscanf(mazefile,"\n");

}

GoMaze(1,1);

printf("(%d,%d,0)",m-2,n-2);

return 0;

}


相关内容

  • 数据结构实验报告---迷宫问题--葛晨阳

    • 数据结构课程设计 设计题目: 迷宫问题 学 院: 信息技术学院 专 业: 网络工程 班 级: B1204 学 号: 0913120419 姓 名: 葛晨阳 指导老师: 戴玉洁 课程设计日期: 2013年 7月 20日- 2013年 8月日 1 实验题目 一.问题描述 输入一个任意大小的迷宫数据,用递 ...

  • 智能小车实验报告

    • 北京邮电大学实习报告 附1 实习总结 为期两周的电子工艺实习,我过得十分忙碌和充实.从茫然地走进实验室,到学习最基本的焊接,到组装小车,再到无数次地调试程序,最后获得全院比赛的二等奖,有很多的辛苦,但是有更多的收获. 焊接是电子工艺实习最基本的部分,也是我们小学期的第一课.最开始是焊接基本的元件,包 ...

  • 迷宫机器人设计开题报告

    • 滨 州 学 院 毕业设计(论文)开题报告 题 目 基于AVR 单片机的迷宫机器人设计 系 (院) 自动化系 年级 2009 专 业 电气工程与自动化 班级 1班 学生姓名 王征飞 学号 [1**********] 指导教师 王志勇 职称 助教 滨州学院教务处 二〇一三 年 三 月 开题报告填表说明 ...

  • 迷宫问题2

    • 题目:假设迷宫由m行n列构成,有一个入口和一个出口,入口坐标为(1,1),出口坐标为 (m,n),试找出一条从入口通往出口的最短路径.设计算法并编程输出一条通过迷宫的最短路径或报告一个"无法通过"的信息. 要求:用栈和队列实现,不允许使用递归算法. 一. 需求分析 1. 用户可以 ...

  • 高架迷宫和Y迷宫

    • 高架十字迷宫(Elevated plus maze): (1)高架十字迷宫(High plus maze)是利用动物对新异环境的探究特性和对高悬敞开臂的恐惧形成矛盾冲突行为来考察动物的焦虑状态.高架十字迷宫具有一对开臂和一对闭臂,啮齿类动物由于嗜暗性会倾向于在闭臂中活动,但出于好奇心和探究性又会在开 ...

  • 迷宫问题课程设计报告

    • 湖南文理学院课程设计报告 课程名称: 计算机技术基础 系 部: 电气与信息工程学院 专业班级: 学 号:学生姓名:指导教师: 完成时间: 报告成绩: 迷宫通路问题 一．设计要求 通过游戏程序设计,提高编程兴趣与编程思路,巩固C语言中所学的知识,合理的运用资料,实现理论与实际相结合. (1)．收集资料 ...

  • 人事测评理论与方法

    • 人事测评理论与方法 附:人力资源专业校园招 聘测评方案 一. 国内人事测评理论与实践 我国的人事测评经历了复苏阶段(1980-1988).初步应用阶段(1989-1992).繁荣发展阶段(1993-迄今). 20世纪90年代以来,随着政治体制改革的推进,国有企业改革的深化,尤其是国家公务员录用考试制 ...

  • 独活对AD模型大鼠定位航行行为学的影响_杜久钢

    • #144# 辽宁中医杂志2009年第36卷第1期 独活对AD 模型大鼠定位航行行为学的影响 杜久钢, 高嵩松, 王 辰, 杨雪山, 刘媛媛, 指导:王佰庆 (辽宁中医药大学, 辽宁沈阳110032) 摘 要:目的:观察独活改善老年性痴呆(AD ) 模型大鼠定位航行学习记忆功能的作用.方法:应用M o ...

  • 智能玩具机器人的工作原理

    • 智能玩具机器人的工作原理 人工智能(AI)可以说是最令人兴奋的在智能玩具机器人技术领域.这当然是最具争议的:每个人都同意,一个智能玩具机器人可以在装配线上工作,但是没有共识智能玩具机器人是否能够聪明. 像"智能玩具机器人"一词本身,人工智能是很难定义的.最终人工智能将是一个娱乐的 ...

热门内容

标签

教师演讲稿   财务工作计划范文   小学生书信范文   小班班会会议记录范文   公务员自我总结范文   病情说明范文   专业技术人员年度考核登记表范文   改名证明书范文   餐饮实习报告范文   年度降价联络函   资料员先进个人材料范文   迎新春晚会主持词   领导讲话后总结串词