{ 若栈不空且栈顶位置尚有其他方向未被探索，
则设定新的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相邻块； 若栈不空但栈顶位置的四周均不可通，
则{ 删去栈顶位置； // 从路径中删去该通道块 若栈不空，则重新测试新的栈顶位置，
直至找到一个可通的相邻块或出栈至栈空； }}} void mgpath() /*路径为:(1,1)->(M-2,N-2)*/ { int i,j,di,find,k;
top++; /*初始方块进栈*/
Stack[top].i=1;Stack[top].j=1;Stack[top].di=-1;mg[1][1]=-1; while (top>-1) /*栈不空时循环*/
{ i=Stack[top].i;j=Stack[top].j;di=Stack[top].di; if (i==M-2 && j==N-2) /*找到了出口,输出路径*/ { printf(\迷宫路径如下:\\n\ for (k=0;k<=top;k++) { printf(\ if ((k+1)%5==0) printf(\ printf(\ return；} find=0; while (di<4 && find==0) /*找下一个可走方块*/ { di++; switch(di) {case 0:i=Stack[top].i-1;j=Stack[top].j;break; case 1:i=Stack[top].i;j=Stack[top].j+1;break; case 2:i=Stack[top].i+1;j=Stack[top].j;break; case 3:i=Stack[top].i,j=Stack[top].j-1;break;} if (mg[i][j]==0) find=1;
if (find==1) /*找到了下一个可走方块*/ { Stack[top].di=di; /*修改原栈顶元素的di值*/ top++; /*下一个可走方块进栈*/
Stack[top].i=i;Stack[top].j=j;Stack[top].di=-1; mg[i][j]=-1; /*避免重复走到该方块*/ } else /*没有路径可走,则退栈*/ { mg[Stack[top].i][Stack[top].j]=0;
/*让该位置变为其他路径可走方块*/ top--;}} printf(\没有可走路径!\\n\4、递归问题的优点
通过上面的例子可看出，递归既是强有力的数学方法， 也是程序设计中一个很有用的工具。其特点是对递归问题描述简捷，结构清晰，程序的正确性容易证明。 5、消除递归的原因
6
其一：有利于提高算法时空性能，因为递归执行时需要系统提供隐式栈实现递归，效率低且费时。
其二： 无应用递归语句的语言设施环境条件，有些计算机语言不支持递归功能，如FORTRAN语言中无递归机制 。
其三：递归算法是一次执行完，这在处理有些问题时不合适， 也存在一个把递归算法转化为非递归算法的需求。
1链队列
队列的链式存储，称为链队列。一个链队列显然需要两个分别指示队头（头指针）和队尾（尾指针）指针才能唯一确定。
队尾指针rear与前面介绍的单链表类似，但为了使头指针，尾指针统一起来， 队头指针front链队列可以定义如下：
typedef struct QNode
(a) 空的链队列{ rearfront QElemType data; /*数据域*/ a1?an struct QNode *next; /*指针域*/
(b) 非空的链队列 }Qnode,*QueuePtr;
front typedef struct front …… an ^ 头 ^ 头 a 1 a 2 {
QueuePtr front; rear rear QueuePtr rear;
(b) （ a ）空链队列 非空链队 }LinkQueue;
链队列的基本操作 （1） 初始化操作。
int InitQueue(LinkQueue &Q)
{ /* 将Q初始化为一个空的链队列 */
Q.front= Q.rear=(QueuePtr)malloc(sizeof(QNode)); if(!Q.front) exit(OVERFLOW); Q->front->next=NULL; return OK; }
（2） 入队操作。
Status EnQueue(LinkQueue &Q, QElemType e) { /* 将数据元素x插入到队列Q中 */ QueuePtr p;
p=(QueuePtr* )malloc(sizeof(QNode)); if(!p) exit(OVERFLOW); p->data=e;
p->next=NULL; Q->rear->next=p
7
Q->rear=p;?
return OK; }
（3） 出队操作。
int DeQueue(LinkQueue &Q, QElemType &e)
{ /* 将队列Q的队头元素出队， 并存放到x所指的存储空间中 */ QueuePtr p;
if(Q->front==Q->rear) return ERROR; p=Q->front->next; e=p->data;
Q->front->next=p->next; /* 队头元素p出队 */
if(Q->rear==p) /* 如果队中只有一个元素p， 则p出队后成为空队 */ Q->rear=Q->front; free(p); /* 释放存储空间 */ return OK; }
2. 循环队列:队列的顺序表示和实现
用一组连续的存储单元依次存放队列的元素，并设两个指针front、rear分别指示队头和队尾元素的位置。
front：指向实际的队头；rear：指向实际队尾的下一位置。 初态： front＝rear＝0；队空： front＝rear;队满： rear＝M; 入队： q[rear]=x; rear＝ rear+1; 出队：x=q[front];front=front+1;
Queue[6] rear5555f
rearrear4444e
33d3d3d frontfront22c22
11b11rearfront 00a00front
(1) 空队列(2) a、b、c、d依次入队(3) a、b、c出队(4) e、f入队
假溢出的解决方法：
（1）将队中元素向队头移动；（2）采用循环队列：q[0]接在Q[M-1]之后 初态： front＝rear＝0或M-1；队空： front＝rear; 入队： q[rear]=x； rear＝( rear+1)%M; 出队： x=q[front]; front=(front+1)%M; 队满： 留一个空间不用(rear+1)%M=front;
或另设一个标志以区分队空和队满。
rear
e5e5rear front5e45e4500e60444
313131 ee3322e2front7reare8front
(a) 空队列(b) 队列满(b) 一般情况8
循环队列的类型定义：
＃define MAXSIZE 100 /*队列的最大长度*/ typedef struct
{ QElemType element［MAXSIZE］; /* 队列的元素空间*/ int front; /*头指针指示器*/
int rear ; /*尾指针指示器*/}SeqQueue; 循环队列的基本操作： （1） 初始化操作。
void InitQueue（SeqQueue &Q）
{ /* 将*Q初始化为一个空的循环队列 */ Q->front=Q->rear=0;} （2） 入队操作。
int EnterQueue(SeqQueue *Q, QueueElementType x) { /*将元素x入队*/
if((Q->rear+1)%MAXSIZE==Q->front) /*队列已经满了*/ return ERROR;
Q->element［Q->rear］=x;
Q->rear=(Q->rear+1)%MAXSIZE; /* 重新设置队尾指针 */ return OK; /*操作成功*/} （3） 出队操作。
int DeQueue(SeqQueue &Q, QueueElementType &e) { /*删除队列的队头元素， 用x返回其值*/ if（Q->front==Q->rear） /*队列为空*/ return ERROR; e=Q->element［Q->front］;
Q->front=(Q->front+1)%MAXSIZE; /*重新设置队头指针*/ return OK; /*操作成功*/} 一、基础知识题 二、算法设计题
3.15，3.17，3.19，3.22， 3.27 ,3.28，3.30，3.31，3.32
9