1、第3章 栈和队列,北京师范大学 教育技术学院 杨开城,一、栈栈的定义,如果一个线性表的插入和删除操作只能在线性表的一端进行，而不能在其他位置上进行，那么这个线性表被称为栈(Stack)。 后进先出(Last In First Out)栈的操作包括： 初始化空栈 销毁栈 判断栈的空和满 入栈 出栈,一、栈顺序栈(1),顺序栈的数据类型定义如下： typedef struct stack_tag elemtype *elem; /*指向存放数据元素的内存块*/int top; /*栈顶标识，elemtop是栈顶元素*/int size; /*栈的容量*/SQSTACK;,一、栈顺序栈(2),1初始
2、化栈 int InitSqstack(SQSTACK *S, int n) /*初始化顺序栈，栈的容量是n。成功则返回1，否则返回0*/S-elem=(elemtype *)malloc(n*sizeof(elemtype); /*为数据元素分配内存*/if(S-elem=NULL)return 0; /*初始化失败*/S-size=n; /*设置栈的容量*/S-top=-1; /*设置栈为空栈*/return 1; 2销毁栈 void DestroySqstack(SQSTACK *S) /*释放栈所占有的内存*/free(S-elem); /*释放内存，并设置为NULL*/S-elem=N
3、ULL;S-top=-1;/*将其他成员设置成安全值*/S-size=0; ,一、栈顺序栈(3),3入栈 int Push(SQSTACK *S,elemtype e) /*在栈顶一端插入数据元素e，操作成功，则返回1，否则返回0*/if(IsSqstackFull(*S)return 0; /*栈满，操作失败*/S-top+;/*top增1*/S-elemS-top=e; /*将e赋值成新的栈顶*/return 1; 4出栈 int Pop(SQSTACK *S,elemtype *e) /*获取栈顶数据元素，并删除栈顶。操作成功，则返回1，否则返回0*/if(IsSqstackEmpty(
4、*S) return 0; /*如果栈空，操作失败*/*e=S-elemS-top; /*获取栈顶元素*/S-top-; /*删除栈顶*/return 1; ,一、栈顺序栈(4),5判断栈空、栈满 int IsSqstackEmpty(SQSTACK S) /*如果栈空，则返回1，否则返回0*/return S.top=-1; /*top是栈顶标识，是-1时表示空栈*/ int IsSqstackFull(SQSTACK S) /*如果栈满，则返回1，否则返回0*/return S.top=S.size-1; /*top作为elem的下标，其最大值是size-1 */ ,一、栈链式栈(1),链
5、式栈的数据类型定义： typedef struct node_tag elemtype data;struct node_tag *next;NODE, *NODEPTR, *LINKSTACK;链式栈的操作： 1入栈 int Push(LINKSTACK L,elemtype e) /*将数据元素e入栈*/NODEPTR p;p=(NODEPTR)malloc(sizeof(NODE);if(p=NULL)return 0;p-data=e;/*形成数据元素e的结点p*/p-next=L-next;/*将p插到头结点后面*/L-next=p;return 1; ,一、栈链式栈(2),2出栈
6、int Pop(LINKSTACK L, elemtype *e) /*获取栈顶数据，删除栈顶*/NODEPTR p;p=L-next; /*p指向栈顶*/if(p=NULL) return 0;L-next=p-next; /*摘除栈顶*/*e=p-data; /*获取原栈顶数据*/free(p); /*释放原栈顶结点*/return 1;,二、栈的应用括号匹配检查,while(stri!=0)ch=stri;if(ch=()Push(,【任务描述】要求设计算法，对于给定的表达式字符串，检查其中括号是否匹配。,typedef char elemtype;int CheckBracket(ch
7、ar *str) /*如果字符串str中括号配对，则返回1，否则返回0*/int i,len;SQSTACK s; /*定义一个栈*/elemtype ch;len=strlen(str); /*将栈s的最大容量设置为字符串的长度*/ InitSqstack(/*从左向右扫描字符串，遇到括号进行入栈和出栈处理*/,二、栈的应用算术表达式求值(1),与表达式求值有关的知识： 表达式中运算符具有优先级和结合性特征 中缀表达式中，双目运算符需要两个操作数，一个操作数在左边，另一个在右边。 表达式求值算法的基本思想： 从左向右扫描表达式，获取单词。 如果单词是操作数，则入操作数栈； 如果单词是常规运算
8、符或者左括号:如果单词的栈外优先级数高，则将运算符入栈；否则反复出栈处理，直到单词栈外优先级数高为止。 如果单词是右括号，则反复出栈处理，直到运算符栈顶是左括号为止。将左括号出栈。 如果单词是=，反复出栈处理，直到运算符栈空。这时操作数栈的栈顶就是表达式的值。,【任务描述】 已知str是某算术表达式字符串，编写算法求得这个算术表达式的值。比如，str的内容是”22*5+6*(10-5)”，那么算法求得的值应该是140。这个算法不考虑单目运算符。为了简便起见，只允许使用加(+)、减(-)、乘(*)、除(/)、乘方()这5个运算符，这5个运算符都是双目运算符。,二、栈的应用算术表达式求值(2),单
9、词的数据类型： typedef struct int type; /*标识word成员是运算符还是操作数*/union float X; char op; word;WORD; typedef WORD elemtype; #define ERROR 0 #define OPERAND 1 /*标识操作数*/ #define OPERATOR 2 /*标识运算符*/ 算法 int Evaluate(char *exp, float *result) /*计算表达式exp的值，*result存放计算结果。如果操作成功，返回1，否则返回0*/int k=0;WORD w,W1,W2,W3;SQST
10、ACK s1,s2;/*s1是操作数栈，s2是运算符栈*/*result=0;InitSqstack(/*事先在运算符栈放置一个左括号*/,二、栈的应用算术表达式求值(3),while(1) w=GetWord(exp,二、栈的应用算术表达式求值(4),case =:while(s2.elems2.top.word.op!=()/*反复出栈处理，直到遇到最开始放在栈里的左括号为止*/if(!Pop( ,二、栈的应用算术表达式求值(5),default:while(InPri(s2.elems2.top.word.op)OutPri(w.word.op)/*只要栈顶运算符的优先级数大于栈外运算符
11、的优先级数，则反复出栈处理*/if(!Pop(/*属于switch语句*/*属于while(1)语句*/,二、栈的应用迷宫路径求解(1),【任务描述】给定某个迷宫的布局及其入口和出口的坐标（如图3_9所示，注意横坐标是从左向右的，但是纵坐标是从上向下的），迷宫中空白的地方可以走，阴影的部分表示墙壁，走不通。设计算法找出从入口到出口的所有路径。需要解决2个问题： 迷宫在计算机中如何表示。 int maze 12= 1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,1,0,0,1,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,0,1,0,0,0,1,0,1,1,
12、1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1; 如何探索从入口到达出口的所有路径。 深度优先探索回溯：从当前位置出发，向四个方向探索，如果发现某方向的相邻位置可走，则走过去，将那个位置当作当前位置继续探索。这时需要将原当前位置保存在栈中。如果四个方向都走不通，则退回到出发点（栈顶中的位置）。走过的地方要打上“已走标记”，回退时要将“已走”标记清除。,二、栈的应用迷宫路径求解(2),typedef struct int x,y;/*位置坐标*/int v; /*探索方向*/elemtype;
13、int movex5=0,0,1,0,-1; int movey5=0,-1,0,1,0;#define M 27 #define N 25 #define MAXSIZE 200 算法： void go(int mazeMN ,int x0,int y0 ,int xx ,int yy) /*找出maze中从入口(x,y)到出口(xx,yy)的所有路径*/int x,y,x1,y1,v;SQSTACK s; /*存放探索路径的栈*/elemtype e;InitSqstack(/*初始化栈*/,二、栈的应用迷宫路径求解(3),e.x=x0; e.y=y0; e.v=0;Push(,二、栈的应
14、用迷宫路径求解(4),while(v0 /*(x1,y1)不通，换一个方向探索*/*while循环结束时，说明(x,y)的4个方向都探索过了，应该回退一步*/while stack ,三、递归问题的非递归算法斐波那契问题(1),【任务描述】斐波那契序列中第n项的递归定义如下，设计算法求得第n项斐波那契序列项的值。递归算法 int Fibo(int n) /*斐波那契序列项求解的递归算法*/int val;if(n=1|n=2)return 1;/*到达递归终点*/val=Fibo(n-1)+Fibo(n-2);/*递归调用*/return val;,三、递归问题的非递归算法斐波那契问题(2),
15、非递归算法 【算法思想】首先将问题Fibo(n)入栈。接着进入一个循环：弹出栈顶问题，如果是递归终点，则求值累加；否则将Fibo(n)递归分解为Fibo(n-1)和Fibo(n-2)，并将它们分别入栈，直到栈空为止。 【适用条件】由P(n)递归分解产生两个问题规模更小的问题P(n1)和P(n2)，它们的求解相互独立，相互之间不构成求解条件。,递归问题的非递归算法设计中栈的作用 保存暂时不能求解的问题，等待条件具备时，再将问题出栈进行求解。被保存的问题，通常是递归分解的结果。,三、递归问题的非递归算法斐波那契问题(3),int Fibonacci(int n) /*非递归算法*/SQSTACK
16、s;int val=0,k;InitSqstack( ,三、递归问题的非递归算法Ackerman函数(1),【任务描述】已知Ackerman函数A(n,x,y)的递归定义如下，设计算法求得Ackerman函数的值。递归算法 int Ackerman(int n,int x,int y) /*递归算法*/ if(n=0)return x+1; /*递归终点*/else if(y=0) /*递归终点*/switch(n)case 1:return x;case 2:return 0;case 3:return 1;default:return 2;/*n=4*/ else return Acker
17、man(n-1,Ackerman(n,x,y-1),x); /*递归调用*/,三、递归问题的非递归算法Ackerman函数(2),非递归算法(I) 【算法思想】 Ackerman函数的非递归算法包含两种基本操作： 递归分解，这是一个循环操作。即如果当前问题不是递归终点，就将当前问题不断递归分解，将产生的第二个子问题入栈，将产生的第一个问题作为当前问题，直到遇到递归终点为止；遇到递归终点时即可求值。 弹出栈顶问题，转去递归分解。 这两个操作构成一个循环。当栈为空时，循环结束，算法终止。 入栈信息是(n,x),三、递归问题的非递归算法Ackerman函数(3),typedef struct int
18、 n,x;elemtype;#define MAXSIZE 500 int Ackerman1(int n,int x,int y) SQSTACK s;elemtype e;int val; /*用来存放函数值*/InitSqstack(/*递归分解,y参数规模减1*/,/*此刻当前问题是A(n,x,0)或A(0,x,y) */ val=AkmValue(n,x); if(IsSqstackEmpty(s) /*求值完毕*/DestroySqstack( /*当前问题变为(n,val,x)*/while(1),int AkmValue(int n,int x) if(n=0)return x
19、+1;else /*属于y=0的情况*/switch(n)case 1:return x;case 2:return 0;case 3:return 1;default:return 2;/*n=4*/,三、递归问题的非递归算法Ackerman函数(4),非递归算法(II) 【算法思想】 首先将初始问题入栈，然后进入递归分解和出栈处理的循环。 先执行对栈顶问题的递归分解，一直分解到递归终点。求得递归终点的函数值val，并弹出栈顶。如果栈为空，则算法终止，返回val；否则出栈问题信息(n,x,y)，形成新的问题信息(n-1,val,x)后入栈。 这时栈顶问题可能不是递归终点，是需要继续递归分解的
20、问题。这时转到前面进行栈顶问题的递归分解操作。 入栈信息是(n,x,y),入栈的问题信息不同，算法细节也会不同,三、递归问题的非递归算法Ackerman函数(5),#define MAXSIZE 500 typedef struct int n,x,y;elemtype; int Ackerman2(int n,int x,int y) SQSTACK s; elemtype e; int val;InitSqstack( ,/*遇到递归终点，求值*/ val=AkmValue(n,x); /*弹出栈顶，因为是递归终点*/Pop(/while 1,三、递归问题的非递归算法汉诺塔问题(1),【任
21、务描述】假设有3根柱子，第1根柱子上套着n个半径大小不同的盘子（盘子中央有小孔），并且大盘子在下面，小盘子在上面，见图3_14。要求将第1根柱子上的盘子搬到第3根柱子上。在搬动过程中，可以使用第2根柱子暂时存放盘子，但无论何时都必须保证大盘子在下面，小盘子在上面，并且一次只能搬动一个盘子。,递归算法 void hanoi(int n,int A,int B,int C) /*汉诺塔的递归算法*/if(n=1)move(A,C);/*递归出口*/elsehanoi(n-1,A,C,B);move(A,C);hanoi(n-1,B,A,C);,三、递归问题的非递归算法汉诺塔问题(1),非递归算法：
22、 typedef struct int n,x,y,z;elemtype;void hanoi1(int n,int A,int B,int C) /*汉诺塔的非递归算法*/ SQSTACK s; elemtype e; int t;InitSqstack(/*将初始问题(n,A,B,C)入栈*/,三、递归问题的非递归算法汉诺塔问题(2),while(1) /*进入递归分解和出栈处理的循环*/ e=s.elems.top; /*取栈顶问题*/while(e.n1) /*递归分解的循环*/ e.n-; t=e.y; e.y=e.z; e.z=t;Push(/*(n-1,B,A,C)入栈，转到前面
23、，进行栈顶问题的递归分解*/,三、递归问题的非递归算法设计思路,四、队列队列的定义,队列(Queue)也是一种操作受限的线性表。与栈不同的是，队列只能在一端插入数据元素，在另一端删除数据元素。 先进先出(First In First Out) 队列的基本操作包括： 初始化空队销毁队列判断队空或队满 入队 出队 获得队列长度,四、队列顺序(循环)队列(1),数据类型定义： typedef struct elemtype *elem; /*指向存放队列数据元素的数组*/int front,rear; /*分别是队首和队尾下标，也称为队首指针和队尾指针*/int size; /*数组elem的容量*
24、/SQQUEUE; 基本操作 1初始化空队 int InitSqqueue(SQQUEUE *q,int n) /*初始化队列，将队列容量设为n。成功则返回1，否则返回0*/*容量为n的顺序队列，需要容量是n+1数组*/ q-elem=(elemtype *)malloc(n+1)*sizeof(elemtype);if(q-elem=NULL)return 0; /*操作失败*/q-front=q-rear=0; /*队首指针、队尾指针都归零*/q-size=n+1; /*设置容量*/return 1; ,四、队列顺序(循环)队列(2),2销毁队列 void DestroySqqueue(S
25、QQUEUE *q) /*销毁队列*/free(q-elem); /*释放队列所占内存*/q-elem=NULL; /*将其他成员设置成安全值*/q-front=q-rear=0;q-size=0; 3判断队空 int IsSqqueueEmpty(SQQUEUE q) /*如果队空，则返回1，否则返回0*/return q.front=q.rear;,四、队列顺序(循环)队列(3),4入队 int EnSqqueue(SQQUEUE *q, elemtype e) /*将数据元素e入队，操作成功返回1，否则返回0*/if(IsSqqueueFull(*q)return 0;q-elemq-r
26、ear=e; /*将e放置在队列中*/q-rear=(q-rear+1)%q-size; /*队尾指针向后移动*/return 1; 5判断队满 int IsSqqueueFull(SQQUEUE q) /*如果队满，则返回1，否则返回0*/return q.front=(q.rear+1)%q.size;,四、队列顺序(循环)队列(4),6出队 int DeSqqueue(SQQUEUE *q, elemtype *e) /*将队首元素复制给*e,操作成功返回1，否则返回0*/if(IsSqqueueEmpty(*q)return 0; /*如果队空，操作失败*/*e=q-elemq-fro
27、nt; /*复制队首元素*/q-front=(q-front+1)%q-size; /*队首指针向后移动*/return 1; 7获得队列长度 int SqqueueLen(SQQUEUE q) /*返回队列长度*/return (q.size+q.rear-q.front)%q.size; ,四、队列链式队列(1),数据类型定义： typedef struct node_tag elemtype data;struct node_tag *next;NODE, *NODEPTR; /*定义单链表结点和指针类型*/ typedef struct NODEPTR front,rear;/*队首队
28、尾指针*/ LKQUEUE;基本操作： 1初始化空队 void InitLkqueue(LKQUEUE *Q) Q-front=Q-rear=NULL;,四、队列链式队列(2),2销毁队列 void DestroyLkqueue(LKQUEUE *Q) NODEPTR p;while(Q-front!=NULL)p=Q-front;Q-front=p-next; /*摘除队首结点*/free(p);Q-rear=NULL;,四、队列链式队列(3),3入队 int EnLkqueue(LKQUEUE *Q,elemtype e) NODEPTR p;p=(NODEPTR)malloc(sizeo
29、f(NODE);if(p=NULL)return 0;p-data=e;p-next=NULL;if(Q-front=NULL) /*如果队空，则将队首队尾指针都指向结点p*/Q-front=Q-rear=p;else/*否则将结点p插入到队尾结点后面*/Q-rear-next=p;Q-rear=p;return 1;,四、队列链式队列(4),4出队 int DeLkqueue(LKQUEUE *Q,elemtype *e) NODEPTR p;if(Q-front=NULL)return 0;p=Q-front;Q-front=p-next;if(Q-front=NULL)Q-rear=NU
30、LL;/*如果队空，则将队尾指针置NULL*/*e=p-data;free(p);return 1;,五、队列的应用迷宫最短路径(1),【任务描述】给定某个迷宫的布局及其入口和出口的坐标，设计算法找出从入口到出口的最短路径。 思考方式：从入口出发，走1步可以到达哪里？走2步可以到达哪里？走3步可以到达哪里？ 算法需要一个辅助队列,五、队列的应用迷宫最短路径(2),typedef struct int x,y,pre;/*(x,y)是坐标，pre是前驱位置在队列数组中的下标*/ elemtype; int movex5=0,0,1,0,-1,movey5=0,-1,0,1,0;void go1(
31、int mazeMN ,int x,int y ,int xx ,int yy) /*求最短路径*/ elemtype e; SQQUEUE q; int x1,y1,i,k;if(!InitSqqueue(,五、队列的应用迷宫最短路径(3),for(i=1;i=4;i+) /*从四个方向探索相邻位置是否可走*/ e.x=x1+movexi;e.y=y1+moveyi;if(mazee.ye.x=0) /*某个相邻位置可走*/ EnSqqueue( /*属于for语句*/*属于while语句*/ ,导航图(1),导航图(2),导航图(3),导航图(4),导航图(5),导航图(6),导航图(7),导航图(8),导航图(9),
