#include <stdio.h> #include <stdlib.h> #define MAXSIZE 20 #define ERROR -1 #define OK 1 #define FALSE 0 #define TRUE 1 typedef enum{RIGHT,DOWN,LEFT,UP}Direction; typedef enum{YES,NO}MarkTag; typedef struct position //迷宫中位置的坐标 { int x; int y; }Position; typedef struct { int order; //当前位置在路径中的序号 Position seat; //当前位置在迷宫中的坐标 Direction di; //从当前位置走到下一位置的方向 }SElemType; //栈元素的类型 typedef struct { SElemType *elem; int top; }Stack; char maze[MAXSIZE][MAXSIZE]={ {'1','1','1','1','1','1','1','1','1','1'}, {'1','0','0','1','0','0','0','1','0','1'}, {'1','0','0','1','0','0','0','1','0','1'}, {'1','0','0','0','0','1','1','0','0','1'}, {'1','0','1','1','1','0','0','0','0','1'}, {'1','0','0','0','1','0','0','0','0','1'}, {'1','0','1','0','0','0','1','0','0','1'}, {'1','0','1','1','1','0','1','1','0','1'}, {'1','1','0','0','0','0','0','0','0','1'}, {'1','1','1','1','1','1','1','1','1','1'} }; //用二维字符数组表示迷宫 int InitStack(Stack *S) //创建一个空栈 { S->elem=(SElemType*)malloc(MAXSIZE*MAXSIZE*sizeof(SElemType)); if(!S->elem) return ERROR; S->top=0; return OK; } int Push(Stack *S,SElemType e) //元素e入栈 { if(S->top>=MAXSIZE*MAXSIZE) return ERROR; S->elem[S->top++]=e;return OK; } int Pop(Stack *S,SElemType *e) //栈顶元素出栈,由e带回栈顶元素 { if(S->top<=0) return ERROR; *e=S->elem[--S->top]; return OK; } int Empty(Stack S) //判断栈是否为空 { if(S.top==0) return TRUE; else return FALSE; } int createMaze(Position *startpos,Position *endpos) { Position start,end; printf("请输入迷宫入口的位置:"); scanf("%d%d",&start.x,&start.y); printf("请输入迷宫出口的位置:"); scanf("%d%d",&end.x,&end.y); *startpos=start; *endpos=end; return OK; } //createMaze int canPass(Position curpos) { if(maze[curpos.x][curpos.y]=='0') return TRUE; return FALSE; } //canPass void markPos(Position curpos,MarkTag tag) //为已经探索过的位置加标记 { switch(tag) { case YES: maze[curpos.x][curpos.y]='.'; break; //路径标记 case NO: maze[curpos.x][curpos.y]='#'; break; //死胡同标记 } } //根据当前的位置坐标和下一步要探索的方向dir求下一步要走的位置坐标 Position nextPos(Position curpos,Direction dir) { Position nextpos; switch(dir) { case RIGHT:nextpos.x=curpos.x ;nextpos.y =curpos.y +1; break; case DOWN :nextpos.x=curpos.x+1 ;nextpos.y =curpos.y; break; case LEFT :nextpos.x=curpos.x ;nextpos.y =curpos.y -1; break; case UP :nextpos.x=curpos.x-1 ;nextpos.y =curpos.y; break; } return nextpos; } Direction nextDir(Direction dir) { switch(dir) { case RIGHT: return DOWN; case DOWN : return LEFT; case LEFT: return UP; } } int Solve(Stack *S,Position start,Position end) {//若迷宫中存在从入口start到出口end的通道,则求得一条存放在栈S中,并返回TRUE,若迷宫中不存在从入口start到出口end的通道,并返回FALSE Position curpos; SElemType e; int curstep=1; //共用的步数 if(InitStack(S)==ERROR) return FALSE; curpos=start; do{ if(canPass(curpos)){ //当前位置可以通过 markPos(curpos,YES); //留下足迹 e.order=curstep;e.seat=curpos;e.di=RIGHT; Push(S,e); //当前位置加入路径 if(curpos.x==end.x&&curpos.y==end.y) //当前位置是出口 return TRUE; curpos=nextPos(curpos,RIGHT); curstep++; } else{ //当前位置不能通过 if(!Empty(*S)){ if(Pop(S,&e)==ERROR) return FALSE; while(e.di==UP&&!Empty(*S)){ //四个方向都试探过,没有找到通路也不能继续探索,则回溯 curpos=e.seat;markPos(curpos,NO); if(Pop(S,&e)==ERROR) return FALSE; } if(e.di!=UP){ //四个方向还没有试探完 e.di=nextDir(e.di); Push(S,e); //换下一个方向探索 curpos=nextPos(e.seat,e.di); } } } }while(!Empty(*S)); return FALSE; } void main() { Position startPos,endPos; Stack path; int i,j; SElemType e; if(createMaze(&startPos,&endPos)==ERROR) return ; Solve(&path,startPos,endPos); while(!Empty(path)){ //输出出口到入口的路径 Pop(&path,&e); printf("(%d,%d)",e.seat.x,e.seat.y); } //输出迷宫的图形 printf("\n"); for(i=0;i<10;i++) {for(j=0;j<10;j++) printf("%c ",maze[i][j]); printf("\n"); } }
b
相关推荐
栈的应用-迷宫问题-数据结构(C语言版)-源代码(直接运行)[定义].pdf
数据结构中,关于迷宫问题的源代码(C语言)。课程作业是解决迷宫求解的问题,从入口出发,顺某一方向向前探索,若能走通,则继续往前走;否则沿原路退回,换一个方向再继续探索,直至所有可能的通路都探索到为止。...
03-002栈的应用、数制转换、括号匹配、行编辑问题、迷宫问题 03-003栈的应用:表达式求值、后缀表达式的表示 03-004队列的定义与存储、顺序队列、链式队列、循环队列 04-001串的定义、表示与实现 04-002串的模式...
· 《数据结构(C语言版) 严蔚敏主编》内容提要: 《数据结构》(C语言版)是为“数据结构”课程编写的教材,也可作为学习数据结构及其算法的C程序设计的参考教材。本书的前半部分从抽象数据类型的角度讨论各种基本类型...
基于C语言设计的迷宫问题与栈问题课程设计报告,应用数据结构栈的主要知识来实现。
数据结构3.txt 数组完全单元.txt 数组操作.txt 数组递归退出.txt 数组递归退出2.txt 文件加密.txt 文件复制.txt 文件连接.txt 无向图.txt 时间陷阱.txt 杨辉三角形.txt 栈单元加.txt 栈操作.txt 桃子...
基本要求:首先实现一个以链表作存储结构的栈类型,然后编写一个求解迷宫的非递归程序。求得的通路以三元组(i,j,d)的形式输出,其中:(i,j)指示迷宫中的一个坐标,d表示走到下一坐标的方向。如:对于下列数据的...
用C写的迷宫源代码,采用数据结构栈的记录实现,适合课程设计和算法应用研究之用 。
1、1 什么是数据结构 1、2 基本概念和术语 1、3 抽象数据类型的表示与实现 1、4 算法和算法分析 1、4、1 算法 1、4、2 算法设计的要求 1、4、3 算法效率的度量 1、4、4 算法的存储空间需求 2 线性表 2、1 线性表...
迷宫算法的c语言实现,数据结构中关于栈的应用。
求迷宫最优路径—栈和队列的应用,完整的可运行的程序,在学数据结构的朋友可以参考下,在TC下可以有步骤的演示.
1.1 数据结构的基本概念和术语 1.1.1 引言 1.1.2 数据结构有关概念及术语 1.1.3 数据结构和抽象数据类型(ADT) 1.2 算法描述与分析 1.2.1 什么是算法 1.2.2 算法描述工具——C语言 1.2.3 算法分析技术初步...
3.1 C语言的数据类型 32 3.2 常量与变量 33 23.2.1 常量和符号常量 33 3.2.2 变量 33 3.3 整型数据 34 3.3.1 整型常量的表示方法 34 3.3.2 整型变量 35 3.4 实型数据 37 3.4.1 实型常量的表示方法 37 3.4.2 实型...
3.1 C语言的数据类型 32 3.2 常量与变量 33 23.2.1 常量和符号常量 33 3.2.2 变量 33 3.3 整型数据 34 3.3.1 整型常量的表示方法 34 3.3.2 整型变量 35 3.4 实型数据 37 3.4.1 实型常量的表示方法 37 3.4.2 实型...
数据结构课程设计题目,课程设计,C语言!
全集内容结构如下: ├─图 │ ├─关键路径(有向无环图及其应用2) │ │ 1.txt │ │ ALGraph.cpp │ │ ALGraph.h │ │ CriticalPath.cpp │ │ CriticalPath.h │ │ InfoType.cpp │ │ InfoType.h │ │ ...
《数据结构》 (严蔚敏版) 源代码 C语言实现 教材:数据结构题集 高等教育出版社 严蔚敏 吴伟民 米宁编著 实验一 线性表的应用(4学时) 一、实验目的:掌握线性表的基本结构和操作方法,培养学生灵活使用...
第2部分 数值计算与数据结构篇 实例16 常用的几种排序方法 46 实例17 广度优先搜索及深度优先搜索 53 实例18 实现基本的串操作 59 实例19 计算各点到源点的最短距离 62 实例20 储油问题 65 实例21...