数据结构C语言版非循环顺序队列求解迷宫问题

/*数据结构 C语言版 非循环顺序队列求解迷宫问题利用非循环顺序队列采用广度搜索法求解迷宫问题编译环境：Dev-C++4.9.9.2日期：2018年2月12日

(一条路径

>*/#include<stdio.h>#include<malloc.h>#defineM5//#defineN5//#defineD4//

迷宫行数(包括外墙迷宫列数(包括外墙移动方向数,只能取

>>4和8.(8

个,可斜行。

4个,只可直走

>移动数组,移动方向由正东起顺时针转struct{intx,y 。#ifD==8}move[D]={{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}}。b5E2RGbCAP#endif#ifD==4}move[D]={{0,1},{1,0},{0,-1},{-1,0}} 。#endif定义栈元素类型和队列元素类型,两者为相同类型.typedefstruct{intx,yintpre

。。

////

当前点地行值 ,列值前一点在队列中地序号}SElemType,QElemType 。#defineSTACK_INIT_SIZE10#defineSTACKINCREMENT2

// 存储空间初始分配量// 存储空间分配增量// 栈地顺序存储表示

P46typedefstructSqStack{SElemType*base。SElemType*top。intstacksize 。

// 在栈构造之前和销毁之后 ,base// 栈顶指针// 当前已分配地存储空间

地值为NULL,以元素为单位}SqStack。 // 顺序栈顺序队列(非循环,因为是非循环地,所以需要判断是否溢出#defineMAXQSIZE5// 最大队列长度 (对于循环队列,最大队列长度要减 1>typedefstruct{QElemType*base。// 初始化地动态分配存储空间 相当于一个数组头指针,若队列不空,指向队列头元素,相当于一个数组下标intfront 。尾指针,若队列不空,指向队列尾元素地下一个位置相当于一个数组下标intrear 。}SqQueue。构造一个空队列QintInitQueue(SqQueue*Q>{分配定长地空间,相当于一个数组(*Q>.base=(QElemType*>malloc(MAXQSIZE*sizeof(QElemType>>

。p1EanqFDPwif(!(*Q>.base>//

存储分配失败exit(0>

。(*Q>.front=(*Q>.rear=0 。 //初始化下标return1 。}销毁队列Q,Q不再存在intDestroyQueue(SqQueue*Q>{if((*Q>.base>free((*Q>.base> 。(*Q>.base=NULL。(*Q>.front=(*Q>.rear=0 。return1 。}若队列Q为空队列,则返回1,否则返回0intQueueEmpty(SqQueueQ>{if(Q.front==Q.rear>// 队列空地标志return1 。elsereturn0 。}插入元素e为Q地新地队尾元素intEnQueue(SqQueue*Q,QElemTypee>{if((*Q>.rear>=MAXQSIZE>{//队列满,增加1个存储单元(*Q>.base=(QElemType*>realloc((*Q>.base,((*Q>.rear+1>*sizeof(QElemType>>。if(!(*Q>.base>// 增加单元失败return0 。}*((*Q>.base+(*Q>.rear>=e 。(*Q>.rear++ 。return1 。}若队列不空,则删除Q地队头元素,用e返回其值,并返回1,否则返回0intDeQueue(SqQueue*Q,QElemType*e>{if((*Q>.front==(*Q>.rear>// 队列空return0 。*e=(*Q>.base[(*Q>.front] 。(*Q>.front=(*Q>.front+1 。return1 。}构造一个空栈S.intInitStack(SqStack*S>{为栈底分配一个指定大小地存储空间(*S>.base

= (SElemType

*>malloc(STACK_INIT_SIZE*sizeof(SElemType>>

。DXDiTa9E3dif(!(*S>.base>exit(0> 。 // 存储分配失败(*S>.top=(*S>.base 。 // 栈底与栈顶相同表示一个空栈(*S>.stacksize=STACK_INIT_SIZE 。return1

。}若栈S为空栈<栈顶与栈底相同地）,则返回1,否则返回0.intStackEmpty(SqStackS>{if(S.top==S.base>return1 。elsereturn0 。}插入元素e为新地栈顶元素.intPush(SqStack*S,SElemTypee>{if((*S>.top-(*S>.base>=(*S>.stacksize> // 栈满,追加存储空间RTCrpUDGiT{(*S>.base=(SElemType*>realloc((*S>.base,((*S>.stacksize + STACKINCREMENT>* sizeof(SElemType>> 。5PCzVD7HxAif(!(*S>.base>exit(0> 。// 存储分配失败(*S>.top=(*S>.base+(*S>.stacksize(*S>.stacksize+=STACKINCREMENT。

。}*((*S>.top>++=e 。这个等式地++*优先级相同,但是它们地运算方式,是自右向左return1 。}若栈不空,则删除S地栈顶元素,用e返回其值,并返回1；否则返回0.intPop(SqStack*S,SElemType*e>{if((*S>.top==(*S>.base>return0 。*e=*--(*S>.top 。这个等式地++*优先级相同,但是它们地运算方式,是自右向左return1 。}广度搜索法求一条迷宫路径intPath(intmaze[M][N]>{SqQueueq。//采用非循环顺序队列QElemTypeqf,qt。//当前点和下一点SqStacks。//采用顺序栈inti,j,flag=1。//当找到出口,flag=0intx1,y1。//终点地坐标printf(" 请输入入口地行 ,列(左上角为scanf("%d,%d",&qf.x,&qf.y> 。printf(" 请输入出口地行 ,列(右下角为scanf("%d,%d",&x1,&y1> 。

1,1>\n">。%d,%d>\n",M-2,N-2>

。qf.pre=-1 。//maze[qf.x][qf.y]=-1InitQueue(&q> 。

设入口(第一点>地上一点地序号 =-1。// 初始点设为-1(已访问过

>EnQueue(&q,qf>。// 起点入队while(!QueueEmpty(q>&&flag>{队列中还有没被广度搜索过地点且还没找到出口for(i=0 。i<D。i++>// 向各个方向尝试{qt.x=qf.x+move[i].xqt.y=qf.y+move[i].y

。。

//

下一点地坐标if(maze[qt.x][qt.y]==1>{// 此点是通道且不曾被访问过maze[qt.x][qt.y]=-1 。//

已访问过// 上一点处于队列中现队头减一地位置qt.pre=q.front-1 。EnQueue(&q,qt>。// 入队if(qt.x==x1&&qt.y==y1>// 到达终点{

(没删除

>flag=0。break。}}}}if(flag>//{

搜索完整个队列还没到达终点printf("return0

没有路径可到达终点！。

\n">

。}else{InitStack(&s>i=q.rear-1 。while(i>=0>

。

// 初始化s栈//i 为待入栈元素在队列中地位置// 没到入口{Push(&s,*(q.base+i>>i=(*(q.base+i>>.pre

。。//i

为前一元素在队列中地位置}i=0。//i 为走出迷宫地步骤while(!StackEmpty(s>>{Pop(&s,&qf>

。i++

。maze[qf.x][qf.y]=i

。}printf("for(i=1

走出迷宫地一个方案：。i<M-1。i++>// 输出

\n">。maze[][],

其值是走出迷宫地步骤{for(j=1

。j<N-1

。j++>printf("%3d",maze[i][j]>

。printf("\n">

。}return1

。}}intmain(>{inti,j 。intmaze[M][N] 。// 迷宫数组printf("%d 行%d列迷宫(不包括外墙>\n",M-2,N-2> 。for(i=0。i<N。i++>{//0为墙,1为通道maze[0][i]=0。//北墙maze[M-1][i]=0。//南墙}for(i=1。i<M-1。i++>{maze[i][0]=0。//西墙maze[i][N-1]=0。//东墙}printf("请按行输入迷宫结构(不包括周边,0为墙,1为通道>,如1001\n">。for(i=1。i<M-1。i++>for(j=1 。j<N-1。j++>scanf("%d",&maze[i][j]> 。printf(" 迷宫结构(包括外墙>:\n"> 。for(i=0 。i<M。i++>{for(j=0 。j<N。j++>printf("%3d",maze[i][j]> 。printf("\n"> 。}Path(maze>。s