资源描述：
《数据结构C语言版 非循环顺序队列求解迷宫问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、/*数据结构C语言版非循环顺序队列求解迷宫问题利用非循环顺序队列采用广度搜索法求解迷宫问题(一条路径)编译环境：Dev-C++4.9.9.2日期：2011年2月12日*/#include#include#defineM5//迷宫行数(包括外墙)#defineN5//迷宫列数(包括外墙)#defineD4//移动方向数,只能取4和8。(8个,可斜行;4个,只可直走)//移动数组,移动方向由正东起顺时针转struct{intx,y;#ifD==8}move[D]={{0,1},{1,
2、1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}};#endif#ifD==4}move[D]={{0,1},{1,0},{0,-1},{-1,0}};#endif//定义栈元素类型和队列元素类型，两者为相同类型。typedefstruct{intx,y;//当前点的行值，列值intpre;//前一点在队列中的序号}SElemType,QElemType;#defineSTACK_INIT_SIZE10//存储空间初始分配量#defineSTACKINCREMENT2//存储空
3、间分配增量//栈的顺序存储表示P46typedefstructSqStack{SElemType*base;//在栈构造之前和销毁之后，base的值为NULLSElemType*top;//栈顶指针intstacksize;//当前已分配的存储空间，以元素为单位}SqStack;//顺序栈//顺序队列(非循环，因为是非循环的，所以需要判断是否溢出#defineMAXQSIZE5//最大队列长度(对于循环队列，最大队列长度要减1)typedefstruct{QElemType*base;//初始化的动态分配存储空间相当
4、于一个数组//头指针,若队列不空,指向队列头元素，相当于一个数组下标intfront;//尾指针,若队列不空,指向队列尾元素的下一个位置相当于一个数组下标intrear;}SqQueue;//构造一个空队列QintInitQueue(SqQueue*Q){//分配定长的空间，相当于一个数组(*Q).base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType));if(!(*Q).base)//存储分配失败exit(0);(*Q).front=(*Q).rear=0;//初始化下
5、标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,QElem
6、Typee){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*
7、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));if(!(*S).base)exit(0);//存储分配失败(*S).top=(*S).ba
8、se;//栈底与栈顶相同表示一个空栈(*S).stacksize=STACK_INIT_SIZE;return1;}//若栈S为空栈（栈顶与栈底相同的），则返回1，否则返回0。intStackEmpty(SqStackS){if(S.top==S.base)return1;elsereturn0;}//插入元素e为新的栈顶元素。intPush(
