C语言 栈 迷宫 的一个疑问

Python09

C语言 栈 迷宫 的一个疑问,第1张

全部程序分几个文件，看清楚了，每段程序放入一个文件，每段程序前面都有文件名： //stackoperation.cpp Status InitStack(SqStack &S) { //构造一个空栈S S.base = (SElemType *)malloc(RANGE*sizeof(SElemType))if(!S.base) exit(OVERFLOW)//存储分配失败 S.top = S.baseS.stacksize = RANGEreturn OK}//Initstack Status Push(SqStack &S,SElemType e) { //插入元素e为新的栈顶元素 if(S.top - S.base >= S.stacksize){//栈满，追加存储空间 S.base = (SElemType*)realloc(S.base,(S.stacksize + STACKINCREMENT) * sizeof(SElemType))if(!S.base) exit(OVERFLOW)//存储分配失败 S.top = S.base + S.stacksizeS.stacksize += STACKINCREMENT} *S.top++ = ereturn OK}//Push Status Pop(SqStack &S,SElemType &e){ /*若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK； 否则返回ERROR*/ if(S.top == S.base) return ERRORe = * --S.topreturn OK}//Pop bool StackEmpty(SqStack S) { //判断栈是否为空并返回TURN或FALSE if(S.top == S.base) return TUREreturn FALSE}//StackEmpty void PrintStack() { SqStack STSElemType eInitStack(ST)do{ Pop(SqS,e)Push(ST,e)}while(!StackEmpty(SqS))do{ Pop(ST,e)printf("(%d,%d,%d)",e.seat.i,e.seat.j,e.di)}while(!StackEmpty(ST))} //migong.cpp #include "Basetype.h" #include "stackoperation.cpp" #include "Mazeoperation.cpp" void main() { char filename[15]FILE *fpprintf("请输入迷宫数据文件名（长度不超过15个字符）：")scanf("%s",&filename)//如找不到文件，则要求重新输入（最多三次机会） for(int i=0i<3i++){ if((fp = fopen(filename,"r")) == NULL) {printf("不能打开文件,请重新输入文件名（长度不超过15个字符）：\n")scanf("%s",filename)}//if break}//for //读取迷宫的行数和列数 int rnum,cnumfscanf(fp,"%d,%d",&rnum,&cnum)printf("这个迷宫有%d行，%d列\n",rnum,cnum)if(rnum>RANGE-2 || cnum>RANGE-2) { printf("迷宫太大，无法求解\n")return}//判断迷宫的大小是否符合要求 //初始化一个迷宫变量 MazeType mazefor(i=0i<=rnum+1i++) for(int j=0j<=cnum+1j++) maze.arr[i][j] = '#'CreatMaze(maze,rnum,cnum,fp)//创建迷宫 fclose(fp)//关闭迷宫文件 //打印当前迷宫 printf("当前迷宫为：\n")for(i=0i<=rnum+1i++) { for(int j=0j<=cnum+1j++) printf("%c",maze.arr[i][j])printf("\n")} printf("其中'#'表示障碍,外围一圈'#'为围墙\n")//读取入口及出口位置 PosType startp,endpprintf("请输入入口位置（两数中间以逗号相隔）：")scanf("%d,%d",&startp.i,&startp.j)printf("请输入出口位置（两数中间以逗号相隔）：")scanf("%d,%d",&endp.i,&endp.j)if(MazePath(maze,startp,endp)) { PrintMaze(maze,rnum,cnum)//将求解的迷宫输出到文件保存，并打印到屏幕 PrintStack()//如果存在路径则打印之 } else printf("此迷宫不存在路径\n")}//main //Mazeoperation.cpp bool Pass(MazeType maze,PosType curpos) { //判断当前位置是否可通，并返回值 switch(char ch = maze.arr[curpos.i][curpos.j]) { case' ': return(FALSE)case'#': case'@': case'*': return(TURE)default: { printf("迷宫中第%d行,第%d列出现不明字符%c\n", curpos.i,curpos.j,ch)exit(0)} }//switch }//pass void FootPrint(MazeType &maze,PosType curpos) { maze.arr[curpos.i][curpos.j] = '*'}//FootPrint void MarkPrint(MazeType &maze,PosType curpos) { maze.arr[curpos.i][curpos.j] = '@'}//MarkPrint void NextPos(PosType &curpos,int di) { switch(di) { case 1: curpos.j++breakcase 2: curpos.i++breakcase 3: curpos.j--breakcase 4: curpos.i--breakdefault: printf("当前方向%d无效\n",di)exit(0)}//switch }//NextPos bool MazePath(MazeType &maze,PosType start,PosType end){ SElemType eInitStack(SqS)PosType curpos = startint curstep = 1do{ if(!Pass(maze,curpos)){ FootPrint(maze,curpos)e.order = curstepe.seat.i = curpos.ie.seat.j = curpos.je.di = 1Push(SqS,e)if(curpos.i == end.i &&curpos.j == end.j) return(TURE)NextPos(curpos,1)curstep++}//if else{ if(!StackEmpty(SqS)){ Pop(SqS,e)while(e.di == 4 &&!StackEmpty(SqS)){ MarkPrint(maze,e.seat)Pop(SqS,e)}//while if(e.di<4){ e.di++Push(SqS,e)NextPos(e.seat,e.di)curpos.i = e.seat.icurpos.j = e.seat.j}//if }//if }//else }while(!StackEmpty(SqS))return(FALSE)}//Mazepath void CreatMaze(MazeType &maze,int row,int col,FILE *fp){ //建立迷宫 char ch = fgetc(fp)for(int i=1i<=rowi++) { for(int j=1j<=colj++) {switch( ch = fgetc(fp)) { case'0': maze.arr[i][j]=' 'breakcase'1': maze.arr[i][j]='#'breakdefault: printf("迷宫第%d行第%d列数据为%c有错误",i,j,ch)exit(0)}//switch }//for fseek(fp,2,1)}//for fclose(fp)}//CreatMaze void PrintMaze(MazeType maze,int row,int col) { //打印结果并输出到文件保存 FILE *outif((out = fopen("outfile","w"))==NULL) { printf("不能打开文件\n")exit(0)}//if for(int i=0i<=row+1i++) {for(int j=0j<=col+1j++) { fputc(maze.arr[i][j],out)printf("%c",maze.arr[i][j])} printf("\n")} printf("其中'*'号代表路径，'#'代表障碍,'@'代表死胡同\n")fclose(out)//关闭文件 } //Basetype.h #include <stdio.h>#include "stdlib.h" #define RANGE 30 //栈的存储空间初始分配量， //以及用来存放迷宫的字符数组的最大维数 #define TURE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -1 #define STACKINCREMENT 5 //栈的存储空间分配增量 typedef struct{ int i//行坐标 int j//列坐标 }PosType//迷宫中坐标位置类型 //栈的定义 typedef struct{ int order//通道块在路径上的“方向” PosType seat//通道块在迷宫中的“坐标位置” int di//从此通道块走向下一通道块的“方向” }SElemType//栈的元素类型 typedef struct{ SElemType *base//栈底指针 SElemType *top//栈顶指针 int stacksize//当前已分配的存储空间，以元素为单位 }SqStack//迷宫的定义 typedef struct{ int m,nchar arr[RANGE][RANGE]}MazeTypetypedef int StatusSqStack SqS//定义一个栈~

#include<stdio.h>

#include<stdlib.h>

#define M 15

#define N 15

struct mark //定义迷宫内点的坐标类型

{

int x

int y

}

struct Element //"恋"栈元素，嘿嘿。。

{

int x,y//x行,y列

int d//d下一步的方向

}

typedef struct LStack //链栈

{

Element elem

struct LStack *next

}*PLStack

/*************栈函数****************/

int InitStack(PLStack &S)//构造空栈

{

S=NULL

return 1

}

int StackEmpty(PLStack S)//判断栈是否为空

{

if(S==NULL)

return 1

else

return 0

}

int Push(PLStack &S, Element e)//压入新数据元素

{

PLStack p

p=(PLStack)malloc(sizeof(LStack))

p->elem=e

p->next=S

S=p

return 1

}

int Pop(PLStack &S,Element &e) //栈顶元素出栈

{

PLStack p

if(!StackEmpty(S))

{

e=S->elem

p=S

S=S->next

free(p)

return 1

}

else

return 0

}

/***************求迷宫路径函数***********************/

void MazePath(struct mark start,struct mark end,int maze

­[N],int diradd[4][2])

{

int i,j,dint a,b

Element elem,e

PLStack S1, S2

InitStack(S1)

InitStack(S2)

maze[start.x][start.y]=2//入口点作上标记

elem.x=start.x

elem.y=start.y

elem.d=-1//开始为-1

Push(S1,elem)

while(!StackEmpty(S1)) //栈不为空 有路径可走

{

Pop(S1,elem)

i=elem.x

j=elem.y

d=elem.d+1//下一个方向

while(d<4) //试探东南西北各个方向

{

a=i+diradd[d][0]

b=j+diradd[d][1]

if(a==end.x &&b==end.y &&maze[a][b]==0) //如果到了出口

{

elem.x=i

elem.y=j

elem.d=d

Push(S1,elem)

elem.x=a

elem.y=b

elem.d=886//方向输出为-1 判断是否到了出口

Push(S1,elem)

printf("\n0=东 1=南 2=西 3=北 886为则走出迷宫\n\n通路为:(行坐标,列坐标,方向)\n")

while(S1) //逆置序列 并输出迷宫路径序列

{

Pop(S1,e)

Push(S2,e)

}

while(S2)

{

Pop(S2,e)

printf("-->(%d,%d,%d)",e.x,e.y,e.d)

}

return//跳出两层循环，本来用break,但发现出错，exit又会结束程序，选用return还是不错滴o(∩_∩)o...

}

if(maze[a][b]==0) //找到可以前进的非出口的点

{

maze[a][b]=2//标记走过此点

elem.x=i

elem.y=j

elem.d=d

Push(S1,elem)//当前位置入栈

i=a//下一点转化为当前点

j=b

d=-1

}

d++

}

}

printf("没有找到可以走出此迷宫的路径\n")

}

/*************建立迷宫*******************/

void initmaze(int maze

­[N])

{

int i,j

int m,n//迷宫行,列

printf("请输入迷宫的行数 m=")

scanf("%d",&m)

printf("请输入迷宫的列数 n=")

scanf("%d",&n)

printf("\n请输入迷宫的各行各列:\n用空格隔开,0代表路,1代表墙\n",m,n)

for(i=1i<=mi++)

for(j=1j<=nj++)

scanf("%d",&maze[i][j])

printf("你建立的迷宫为o(∩_∩)o...\n")

for(i=0i<=m+1i++) //加一圈围墙

{

maze[i][0]=1

maze[i][n+1]=1

}

for(j=0j<=n+1j++)

{

maze[0][j]=1

maze[m+1][j]=1

}

for(i=0i<=m+1i++) //输出迷宫

{

for(j=0j<=n+1j++)

printf("%d ",maze[i][j])

printf("\n")

}

}

void main()

{

int sto

­[N]

struct mark start,end//start,end入口和出口的坐标

int add[4][2]={{0,1},{1,0},{0,-1},{-1,0}}//行增量和列增量 方向依次为东西南北

initmaze(sto)//建立迷宫

printf("输入入口的横坐标,纵坐标[逗号隔开]\n")

scanf("%d,%d",&start.x,&start.y)

printf("输入出口的横坐标,纵坐标[逗号隔开]\n")

scanf("%d,%d",&end.x,&end.y)

MazePath(start,end,sto,add)//find path

system("PAUSE")

}

#include <graphics.h>

#include <stdlib.h>

#include <stdio.h>

#include <conio.h>

#include <dos.h>

#define N 20/*

迷宫的大小，可改变

*/

int oldmap[N][N]/*

递归用的数组

,

用全局变量节约时间

*/

int yes=0/*yes

是判断是否找到路的标志

,1

找到，

0

没找到

*/

int way[100][2],wayn=0/*way

数组是显示路线用的

,wayn

是统计走了几个格

子

*/

void Init(void)/*

图形初始化

*/

void Close(void)/*

图形关闭

*/

void DrawPeople(int *x,int *y,int n)/*

画人工探索物图

*/

void PeopleFind(int (*x)[N])/*

人工探索

*/

void

WayCopy(int

(*x)[N],int

(*y)[N])/*

为了

8

个方向的递归，把旧迷宫图

拷贝给新数组

*/

int FindWay(int (*x)[N],int i,int j)/*

自动探索函数

*/

void MapRand(int (*x)[N])/*

随机生成迷宫函数

*/

void PrMap(int (*x)[N])/*

输出迷宫图函数

*/

void Result(void)/*

输出结果处理

*/

void Find(void)/*

成功处理

*/

void NotFind(void)/*

失败处理

*/

void main(void)/*

主函数

*/

{

int map[N][N]/*

迷宫数组

*/

char ch

clrscr()

printf("\n Please select hand(1) else auto\n")/*

选择探索方式

*/

scanf("%c",&ch)

Init() /*

初始化

*/

MapRand(map)/*

生成迷宫

*/

PrMap(map)/*

显示迷宫图

*/

if(ch=='1')

PeopleFind(map)/*

人工探索

*/

else

FindWay(map,1,1)/*

系统自动从下标

1,1

的地方开始探索

*/

Result()/*

输出结果

*/

Close()

}

void Init(void)/*

图形初始化

*/

{

int gd=DETECT,gm

initgraph(&gd,&gm,"c:\\tc")}

void DrawPeople(int *x,int *y,int n)/*画人工控制图*/ {/*如果将以下两句注释掉，则显示人工走过的路径，*/

setfillstyle(SOLID_FILL,WHITE) /*设置白色实体填充样式*/bar(100+(*y)*15-6,50+(*x)*15-6,100+(*y)*15+6,50+(*x)*15+6)/*恢复原通路*/

switch(n)/*判断x,y的变化，8个方向的变化*/{

case 1: (*x)--break/*上*/

case 2: (*x)--(*y)++break /*右上*/ case 3: (*y)++break /*右*/

case 4: (*x)++(*y)++break/*右下*/ case 5: (*x)++break /*下*/

case 6: (*x)++(*y)--break/*左下*/ case 7: (*y)--break /*左*/

case 8: (*x)--(*y)--break/*左上*/}

setfillstyle(SOLID_FILL,RED)/*新位置显示探索物*/

bar(100+(*y)*15-6,50+(*x)*15-6,100+(*y)*15+6,50+(*x)*15+6)}

void PeopleFind(int (*map)[N])/*人工手动查找*/ {

int x,y

char c=0/*接收按键的变量*/x=y=1/*人工查找的初始位置*/setcolor(11)

line(500,200,550,200) outtextxy(570,197,"d") line(500,200,450,200) outtextxy(430,197,"a") line(500,200,500,150) outtextxy(497,130,"w") line(500,200,500,250) outtextxy(497,270,"x") line(500,200,450,150) outtextxy(445,130,"q") line(500,200,550,150) outtextxy(550,130,"e") line(500,200,450,250) outtextxy(445,270,"z") line(500,200,550,250)

outtextxy(550,270,"c")/*以上是画8个方向的控制介绍*/

setcolor(YELLOW)

outtextxy(420,290,"Press 'Enter' to end")/*压回车键结束*/setfillstyle(SOLID_FILL,RED)

bar(100+y*15-6,50+x*15-6,100+y*15+6,50+x*15+6)/*入口位置显示*/while(c!=13)/*如果按下的不是回车键*/{

c=getch()/*接收字符后开始各个方向的探索*/ if(c=='w'&&map[x-1][y]!=1) DrawPeople(&x,&y,1)/*上*/ else if(c=='e'&&map[x-1][y+1]!=1) DrawPeople(&x,&y,2)/*右上*/ else if(c=='d'&&map[x][y+1]!=1) DrawPeople(&x,&y,3)/*右*/ else if(c=='c'&&map[x+1][y+1]!=1) DrawPeople(&x,&y,4)/*右下*/ else if(c=='x'&&map[x+1][y]!=1)DrawPeople(&x,&y,5)/*下*/ elseif(c=='z'&&map[x+1][y-1]!=1)DrawPeople(&x,&y,6)/*左下*/elseif(c=='a'&&map[x][y-1]!=1) DrawPeople(&x,&y,7)/*左*/else if(c=='q'&&map[x-1][y-1]!=1) DrawPeople(&x,&y,8)/*左上*/}

setfillstyle(SOLID_FILL,WHITE)/*消去红色探索物，恢复原迷宫图*/bar(100+y*15-6,50+x*15-6,100+y*15+6,50+x*15+6) if(x==N-2&&y==N-2)/*人工控制找成功的话*/ yes=1/*如果成功标志为1*/ }

void WayCopy(int (*oldmap)[N],int (*map)[N])/*拷贝迷宫数组 */ {

int i,j

for(i=0i<Ni++) for(j=0j<Nj++) oldmap[i][j]=map[i][j]}

int FindWay(int (*map)[N],int i,int j)/*递归找路*/ {

if(i==N-2&&j==N-2)/*走到出口*/{

yes=1/*标志为1,表示成功*/ return }

map[i][j]=1/*走过的地方变为1*/WayCopy(oldmap,map)/*拷贝迷宫图*/

if(oldmap[i+1][j+1]==0&&!yes)/*判断右下方是否可走*/{

FindWay(oldmap,i+1,j+1) if(yes)/*如果到达出口了，再把值赋给显示路线的way数组,也正是这个原因,所以具体路线是从最后开始保存*/ { way[wayn][0]=i way[wayn++][1]=j return }}

WayCopy(oldmap,map)

if(oldmap[i+1][j]==0&&!yes)/*判断下方是否可以走,如果标志yes已经是1也不用找下去了*/{

FindWay(oldmap,i+1,j) if(yes) { way[wayn][0]=i way[wayn++][1]=j return }}

WayCopy(oldmap,map)

if(oldmap[i][j+1]==0&&!yes)/*判断右方是否可以走*/{

FindWay(oldmap,i,j+1) if(yes) { way[wayn][0]=i way[wayn++][1]=j return }}

WayCopy(oldmap,map)

if(oldmap[i-1][j]==0&&!yes)/*判断上方是否可以走*/{

FindWay(oldmap,i-1,j) if(yes) { way[wayn][0]=i way[wayn++][1]=j return }}

WayCopy(oldmap,map)

if(oldmap[i-1][j+1]==0&&!yes)/*判断右上方是否可以走*/{

FindWay(oldmap,i-1,j+1) if(yes) { way[wayn][0]=i way[wayn++][1]=j return }}

WayCopy(oldmap,map)

if(oldmap[i+1][j-1]==0&&!yes)/*判断左下方是否可以走*/{

FindWay(oldmap,i+1,j-1) if(yes) { way[wayn][0]=i way[wayn++][1]=j return }}

WayCopy(oldmap,map)

if(oldmap[i][j-1]==0&&!yes)/*判断左方是否可以走*/{

FindWay(oldmap,i,j-1) if(yes) { way[wayn][0]=i way[wayn++][1]=j return }}

WayCopy(oldmap,map)

if(oldmap[i-1][j-1]==0&&!yes)/*判断左上方是否可以走*/{

FindWay(oldmap,i-1,j-1) if(yes) { way[wayn][0]=i way[wayn++][1]=j return }}

return}

void MapRand(int (*map)[N])/*开始的随机迷宫图*/ {

int i,j

cleardevice()/*清屏*/

randomize()/*随机数发生器*/for(i=0i<Ni++){

for(j=0j<Nj++) { if(i==0||i==N-1||j==0||j==N-1)/*最外面一圈为墙壁*/ map[i][j]=1 else if(i==1&&j==1||i==N-2&&j==N-2)/*出发点与终点表示为可走的*/ map[i][j]=0 else map[i][j]=random(2)/*其它的随机生成0或1*/ }} }

void PrMap(int (*map)[N])/*输出迷宫图*/ {

int i,j

for(i=0i<Ni++) for(j=0j<Nj++) if(map[i][j]==0) { setfillstyle(SOLID_FILL,WHITE)/*白色为可走的路*/ bar(100+j*15-6,50+i*15-6,100+j*15+6,50+i*15+6) } else { setfillstyle(SOLID_FILL,BLUE)/*蓝色为墙壁*/ bar(100+j*15-6,50+i*15-6,100+j*15+6,50+i*15+6)

} }

void Find(void)/*找到通路*/ {

int i

setfillstyle(SOLID_FILL,RED)/*红色输出走的具体路线*/wayn--

for(i=wayni>=0i--){

bar(100+way[i][1]*15-6,50+way[i][0]*15-6,100+ way[i][1]*15+6,50+way[i][0]*15+6) sleep(1)/*控制显示时间*/}

bar(100+(N-2)*15-6,50+(N-2)*15-6,100+ (N-2)*15+6,50+(N-2)*15+6)/*在目标点标红色*/setcolor(GREEN)

settextstyle(0,0,2)/*设置字体大小*/outtextxy(130,400,"Find a way!")}

void NotFind(void)/*没找到通路*/ {

setcolor(GREEN)

settextstyle(0,0,2)/*设置字体大小*/outtextxy(130,400,"Not find a way!")}

void Result(void)/*结果处理*/ {

if(yes)/*如果找到*/ Find()

else/*没找到路*/ NotFind() getch()}

void Close(void)/*图形关闭*/ {

closegraph()}