C语言迷宫求解(完结版)

发布时间:2017-6-27 18:37:42 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"C语言迷宫求解(完结版)",主要涉及到C语言迷宫求解(完结版)方面的内容,对于C语言迷宫求解(完结版)感兴趣的同学可以参考一下。

原文链接:http://hi.baidu.com/linfengtingyu1/item/9f588d9edf57facfb625317d //定义状态常量 #define OVERFLOW -2 #define ERROR 0 #define NULL 0 #define true 1 #define TRUE 1 #define false 0 #define FALSE 0 #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 #include <stdio.h> #include <stdlib.h> /* 初始化迷宫,1表示通道,0表示墙 */ int maze[8][8] = { 1,1,0,1,1,1,0,1, 1,1,0,1,1,1,0,1, 1,1,1,1,0,0,1,1, 1,0,0,0,1,1,1,1, 1,1,1,0,1,1,1,1, 1,0,1,1,1,0,1,1, 1,0,0,0,1,0,0,1, 0,1,1,1,1,1,1,1 }; //定义栈元素类型 typedef struct MStackElem { int x;//x坐标 int y;//y坐标 int val;//maze[x][y]的值 }MStackElem; //定义栈 typedef struct { MStackElem * base; MStackElem * top; int stackSize; }MStack; //=============Stack的实现======================== //初始化栈-------构造一个空栈 void initStack(MStack *s) { s->base = (MStackElem *)malloc(STACK_INIT_SIZE * sizeof(MStackElem)); if (!s->base) { printf("in initStack()...Failed to initalize the MStack ,no enough space! exit now. "); exit(OVERFLOW);//存储分配失败 } s->top = s->base; s->stackSize = STACK_INIT_SIZE; } //向栈中添加元素 void push(MStack *s,MStackElem e) { //向栈中添加元素前先判断栈是否还有空间容纳新元素 if (s->top - s->base >= s->stackSize) { //栈满,追加元素 s->base = (MStackElem *)realloc(s->base, (STACK_INIT_SIZE+STACKINCREMENT) * sizeof(MStackElem)); if (!s->base) { printf("in push()...Failed to realloc the MStack ,no enough space! exit now. "); exit(OVERFLOW);//存储分配失败 } s->top = s->base + s->stackSize; //重新分配空间,base的值其实已经改变,top的值也就相应的改变 s->stackSize += STACKINCREMENT; } //将新元素加到栈顶 *(s->top++) = e; } //获得栈顶元素 MStackElem getTop(MStack *s) { if (s->top == s->base) { printf("in getTop(),empty stack! exit now. "); exit(ERROR); } else { return *(s->top - 1); } } //删除栈顶元素 void pop(MStack *s) { //若栈不为空,则删除s的栈顶元素 if (s->top == s->base) { printf("in pop(),empty stack! exit now. "); exit(ERROR); } else { --(s->top); } } //=====================================求解迷宫的相关操作=====================// //构造两个栈,一个用来保存探索中的全部路径,一个用来保存有效路径 MStack realPath,path; //判断当前位置是否走过 int unPass(MStack path,MStackElem cur) {//这里不能传path的地址,否则在遍历过程中它的top值就真的被改了 !! int flag = 1; while(path.top != path.base) { MStackElem e = *(path.top - 1); if (e.x == cur.x&& e.y == cur.y) { flag = 0; } //每循环一次令头指针下移一个位置 (path.top)--; } return flag; } //获得东面相邻的位置 MStackElem getEast(MStackElem cur) { if(cur.y != 7) {//当y==7时已到了迷宫右边界,不能再向东(右)行了 cur.y += 1; cur.val = maze[cur.x][cur.y]; } return cur;// 当y==7时返回的是它本身 } //获得南面相邻的位置 MStackElem getSouth(MStackElem cur) { if(cur.x != 7) {//当x==7时已到了迷宫下边界,不能再向南(下)行了 cur.x += 1; cur.val = maze[cur.x][cur.y]; } return cur;// 当x==7时返回的是它本身 } //获得西面相邻的位置 MStackElem getWest(MStackElem cur) { if(cur.y != 0) {//当y==0时已到了迷宫左边界,不能再向西(左)行了 cur.y -= 1; cur.val = maze[cur.x][cur.y]; } return cur;// 当y==0时返回的是它本身 } //获得北面相邻的位置 MStackElem getNorth(MStackElem cur) { if(cur.x != 0) {//当cur.x==0时表示在迷宫的上边界,不能再向北(上)行了 cur.x -= 1; cur.val = maze[cur.x][cur.y]; } return cur;// 当cur.x==0时返回的还是它本身 } //获得下一个可通行的位置,按东南西北的方向试探 MStackElem getNext(MStackElem cur) { MStackElem next; next.x = next.y=next.val = -1; if(getEast(cur).val != 0 && unPass(path,getEast(cur))) { next = getEast(cur); } else if(getSouth(cur).val != 0 && unPass(path,getSouth(cur))) { next = getSouth(cur); } else if(getWest(cur).val != 0 && unPass(path,getWest(cur))) { next = getWest(cur); } else if(getNorth(cur).val != 0 && unPass(path,getNorth(cur))) { next = getNorth(cur); } //如果当前位置的四面或为墙或已走过,则返回的next的val值为-1 return next; } //获得迷宫路径的函数 int getMazePath(){ MStackElem start,end,cur; start.x = 0; start.y = 0; start.val = maze[start.x][start.y]; end.x = 7; end.y = 7; end.val = maze[end.x][end.y]; cur = start; //设定当前为位置为"入口位置" do { if (unPass(path,cur)) {//如果当前位置未曾走到过 push(&realPath,cur); push(&path,cur); cur = getNext(cur); if (cur.x == end.x && cur.y == end.y) { //到达出口了,则跳出循环,并返回true //把出口结点放入路径中 push(&realPath,cur); push(&path,cur); //直接跳出函数(而不只是跳出这个循环 ) return true; } else if(cur.val == -1) {//当前位置的四面或为墙或已走过 //删除真实路径的栈顶元素 pop(&realPath); cur = getTop(&realPath);//令cur指向栈顶元素 } } else {//如果当前位置已经走过,说明原来测试的方向不对,现在尝试其它方向 cur = getNext(cur); if (cur.val == -1) {//仍不通,删除真实路径的栈顶元素 pop(&realPath); cur = getTop(&realPath);//令cur指向栈顶元素 } } } while (cur.x != end.x || cur.y != end.y); } //打印迷宫路径 void printMazePath(MStack *s) {//这里不传MStack的地址,以防在遍历的过程中把它们的top或base的值也修改了 MStackElem e; while (s->base < (s->top-1)) { e = *(s->base);//先指向栈底元素,以后依次向上增1 printf("maze[%d][%d]----->",e.x,e.y); (s->base)++; } //最后一个结点没有后继,所以不再输出"------>" e = *(s->base); printf("maze[%d][%d]",e.x,e.y); } main(){ //初始化栈 initStack(&realPath); initStack(&path); getMazePath(); printf("The path of through the maze is:\n\n"); printMazePath(&realPath); getchar(); }

上一篇:使用动态数组结构的一个好处
下一篇:C语言知识点学习之联合体

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。