第三章栈和队列 栈 队列 递归

栈 ( Stack ) 定义:是限定仅在表尾进行插入或删除操作的线性表。 特点：后进先出 (LIFO) 允许插入和删除的一端 称为栈顶(top)，另一端 称为栈底(bottom) 特点：后进先出 (LIFO) 出栈 进栈 top an . a1 bottom

栈的主要操作 ADT Stack { int Push (stack *S, StackData x); //进栈 int Pop (stack *S, StackData &x); //出栈 int GetTop (stack *S, StackData &x); //取栈顶 void InitStack (stack *S); //置空栈 int StackEmpty (stack *S); //判栈空否 int StackFull (stack *S); //判栈满否 }

栈的表示和实现 顺序栈：栈的顺序存储结构，利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，指针top指向栈顶元素在顺序栈中的下一个位置， base为栈底指针，指向栈底的位置。 空栈 a 进栈 b 进栈 a b top base base

top a b c d e e 进栈 f 进栈溢出 e 出栈 base

顺序栈的类型表示: #define STACK_INIT_SIZE 100； #define STACKINCREMENT 10； typedef char StackData; typedef struct { //顺序栈定义 StackData *base; //栈底指针 StackData *top; //栈顶指针 int stacksize；//当前已分配的存储空间 } SeqStack；

顺序栈的基本运算: 判栈空 判栈满 int StackEmpty (SeqStack *S) { if( S->top == S->base ) return 1 //判栈空,空则返回1 else return 0; //否则返回0 } 判栈满 int StackFull (SeqStack *S) { if( S->top- S->base >= S-> StackSize ) return 1 //判栈满,满则返回1

初始化 void InitStack ( SeqStack *S) { //置空栈 S->base =( StackData *)malloc(STACK_INIT_SIZE * sizeof(StackData)); if (!S->base) exit(OVERFLOW); S->top = S->base ; S->stacksize= STACK_INIT_SIZE ; Return ok; }

入栈 int Push (SeqStack *S, StackData x) { //插入元素x为新的栈顶元素 if ( StackFull (S) ){ S->base =( StackData *)malloc(S->base , (S->stacksize+ STACKINCREMENT) * sizeof(StackData)); if(! S->base)exit(overflow); S->top= S->base + S->stacksize; S->stacksize+= STACKINCREMENT; //追加存储空间 } *(S->top)=x; （S->top）++; Return ok

int Gettop (SeqStack *S, StackData &x) { 取栈顶元素 int Gettop (SeqStack *S, StackData &x) { //若栈空返回0, 否则栈顶元素读到x并返回1 if ( StackEmpty(S) ) return 0; (S->top)--; x = *(S->top); return 1; }

int pop (SeqStack *S, StackData &x) { if ( StackEmpty(S) ) return 0; 出栈 int pop (SeqStack *S, StackData &x) { //若栈空返回0, 否则栈顶元素退出到x并返回1 if ( StackEmpty(S) ) return 0; --(S->top); x = *(S->top); return 1; }

链式栈:栈的链接表示 链式栈无栈满问题，空间可扩充 插入与删除仅在栈顶处执行 链式栈的栈顶在链头 适合于多栈操作 top

链式栈 (LinkStack)的定义 typedef int StackData; typedef struct node { StackData data; //结点 struct node *link; //链指针 } StackNode; typedef struct { StackNode *top; //栈顶指针 } LinkStack;

链式栈操作实现 初始化 void InitStack ( LinkStack *S ) { S->top = NULL; } 入栈 int Push ( LinkStack *S, StackData x ) { StackNode *p = ( StackNode * ) malloc ( sizeof ( StackNode ) ); p->data = x; p->link = S->top; S->top = p; return 1;

判栈空 int StackEmpty (LinkStack *S) { return S->top == NULL; } 出栈 int Pop ( LinkStack *S, StackData &x ) { if ( StackEmpty (S) ) return 0; StackNode * p = S->top; S->top = p->link; x = p->data; free (p); return 1;

取栈顶 置栈空 int GetTop ( LinkStack *S, StackData &x ) { if ( StackEmpty (S) ) return 0; x = S->top->data; return 1; } 置栈空 int MakeEmpty ( LinkStack *S) { While(S->top!=NULL){ StackNode * p = S->top; S->top = S->top ->link; free(p);

栈的应用举例 数制转换 行编辑程序 迷宫求解 表达式求值

数制转换 N = (N div d)×d + N mod d 例如：（1348)10 = (2504)8 ，其运算过程如下： 数制转换 N = (N div d)×d + N mod d 例如：（1348)10 = (2504)8 ，其运算过程如下： N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2 计算顺序 输出顺序

void conversion () { InitStack(S); scanf ("%d",N); while (N) { Push(S, N % 8); N = N/8; } while (!StackEmpty(S)) { Pop(S,e); printf ( "%d", e ); } // conversion

行编辑程序 在用户输入一行的过程中，允许 用户输入出差错，并在发现有误时可以及时更正。 在用户输入一行的过程中，允许 用户输入出差错，并在发现有误时可以及时更正。 设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区; 并假设“#”为退格符，“@”为退行符。 假设从终端接受两行字符： whli##ilr#e（s#*s) outcha@putchar(*s=#++); 实际有效行为： while (*s) putchar(*s++);

Void LineEdit(){ InitStack(s); ch=getchar(); while (ch != EOF) { //EOF为全文结束符 while (ch != EOF && ch != '\n') { switch (ch) { case '#' : Pop(S, c); break; case '@': ClearStack(S); break; // 重置S为空栈 default : Push(S, ch); break; } ch = getchar(); // 从终端接收下一个字符

将从栈底到栈顶的字符传送至调用过程的 数据区； ClearStack(S); // 重置S为空栈 if (ch != EOF) ch = getchar(); } DestroyStack(s);

迷宫求解 通常用的是“穷举求解”的方法

迷宫路径算法的基本思想 若当前位置“可通”，则纳入路径，继续前进; 若当前位置“不可通”，则后退，换方向继续探索; 若四周“均无通路”，则将当前位置从路径中删除出去。

设定当前位置的初值为入口位置； do｛ 若当前位置可通， 则｛将当前位置插入栈顶； 若该位置是出口位置，则算法结束； 否则切换当前位置的东邻方块为新的 当前位置； ｝ 否则 { ……….. ｝while (栈不空）；

若栈不空且栈顶位置尚有其他方向未被探索， 则设定新的当前位置为: 沿顺时针方向旋转 找到的栈顶位置的下一相邻块； 若栈不空但栈顶位置的四周均不可通， 则｛ 删去栈顶位置；// 从路径中删去该通道块 若栈不空，则重新测试新的栈顶位置， 直至找到一个可通的相邻块或出栈至栈空; ｝

表达式求值 限于二元运算符的表达式定义: 表达式 ::= (操作数) + (运算符) + (操作数) 操作数 ::= 简单变量 | 表达式 简单变量 :: = 标识符 | 无符号整数 Exp = S1 + OP + S2 前缀表示法OP + S1 + S2 中缀表示法 S1 + OP + S2 后缀表示法 S1 + S2 + OP

表达式标识方法 例如: Exp = a  b + (c  d / e)  f 前缀式: +  a b   c / d e f - c a / * d e f +

后缀表达式求值 先找运算符，再找操作数 例如： a b  c d e /  f  + ab d/e c-d/e (c-d/e)f

从原表达式求得后缀式方法 设立暂存运算符的栈; 设表达式的结束符为“#”, 予设运算符栈的栈底为“#” 若当前字符是操作数，则直接发送给后缀式; 若当前运算符的优先数高于栈顶运算符，则进栈; 否则，退出栈顶运算符发送给后缀式; “(” 对它之前后的运算符起隔离作用，“)”为自左括弧开始的表达式的结束符。

队列 定义:只允许在表的一端进行插入，而在另一端删除元素的线性表。 特点：先进先出 (FIFO) 在队列中，允许插入的一端叫队尾（rear） ，允许删除的一端称为对头(front)。 特点：先进先出 (FIFO) 出队列 入队列 a1 ，a2， a3，…，an 队 头 队 尾

链队列：队列的链式表示 链队列中，有两个分别指示队头和队尾的指针。 链式队列在进队时无队满问题，但有队空问题。 front rear data next front rear data next front rear

front front rear rear front rear front rear front rear NULL ^ 空队列 空队列 x ^ 元素x入队 front rear x ^ y 元素y入队 front rear x ^ y 元素x出队

链式队列的定义 typedef int QueueData; typedef struct node { QueueData data; //队列结点数据 struct node *link; //结点链指针 } QueueNode; typedef struct { QueueNode *rear, *front; } LinkQueue;

链队列的主要操作 初始化 队空 取队头元素 void InitQueue ( LinkQueue *Q ) { Q->rear = Q->front = NULL; } 队空 int QueueEmpty ( LinkQueue *Q ) { return Q->front == NULL; 取队头元素 int GetFront ( LinkQueue *Q, QueueData &x ) { if ( QueueEmpty (Q) ) return 0; x = Q->front->data; return 1;

入队 int EnQueue ( LinkQueue *Q, QueueData x ) { QueueNode *p = ( QueueNode * ) malloc ( sizeof ( QueueNode ) ); p->data = x; p->link = NULL; if ( Q->front == NULL ) //空,创建第一个结点 Q->front = Q->rear = p; else Q->rear->link = p; //入队 Q->rear =p; return 1; }

出队 int DeQueue ( LinkQueue *Q, QueueData &x) { //删去队头结点，并返回队头元素的值 if ( QueueEmpty (Q) ) return 0; //判队空 QueueNode *p = Q->front; x = p->data; //保存队头的值 Q->front= Q->front->link; //新队头 free (p); return 1; }

循环队列 (Circular Queue) 顺序队列—队列的顺序存储表示。用一组地址连续的存储单元依次存放从队列头到队列尾的元素，指针front和rear分别指示队头元素和队尾元素的位置。 插入新的队尾元素，尾指针增1，rear = rear + 1， 删除队头元素，头指针增1， front = front + 1， 因此，在非空队列中，头指针始终指向队列头元素，而尾指针始终指向队列尾元素的下一个位置。 队满时再进队将溢出 解决办法：将顺序队列臆造为一个环状的空间，形成循环(环形)队列

队列的进队和出队 A B C D C D C D E F G C D E F G rear front 空队列 front rear H进队,溢出

循环队列 (Circular Queue) 循环队列 队头、队尾指针加1，可用取模(余数)运算实现。 队头指针进1: front = (front+1) %maxsize; 队尾指针进1: rear = (rear+1) % maxsize; 队列初始化：front = rear = 0; 队空条件：front == rear; 队满条件：(rear+1) % maxsize == front; 6 7 Maxsize-1 5 rear 4 1 3 2 front 循环队列

1 2 3 4 5 6 7 front B C D rear 一般情况 A 1 2 3 4 5 6 7 rear 空队列 front C 1 2 3 4 5 6 7 队满(正确) front rear D E F G A B C 1 2 3 4 5 6 7 队满 front rear D E F G A B H

循环队列的类型定义 #define MAXSIZE 100 Typedef struct{ QueueData *data; int front; int rear; } SeqQueue

循环队列操作的实现 初始化队列 void InitQueue ( SeqQueue *Q ) { //构造空队列 Q->data=(QueueData *)malloc(MAXSIZE *sizeof(QueueData)); If(! Q->data)exit(OVERFLOW); Q->rear = Q->front = 0; Return ok }

判队空 int QueueEmpty ( SeqQueue *Q ) { return Q->rear == Q->front; } 判队满 int QueueFull ( SeqQueue *Q ) { return (Q->rear+1) % QueueSize == Q->front; 入队 int EnQueue ( SeqQueue *Q, QueueData x ) { if ( QueueFull (Q) ) return 0; Q->data[Q->rear] = x; Q->rear = ( Q->rear+1) % MAXSIZE; return 1;

出队 取队头 int DeQueue ( SeqQueue *Q, QueueData &x ) { if ( QueueEmpty (Q) ) return 0; x = Q->data[Q->front]; Q->front = ( Q->front+1) % MAXSIZE; return 1; } 取队头 int GetFront ( SeqQueue *Q, QueueData &x ) { x = Q->data[(Q->front+1) % MAXSIZE];

队列应用举例 —打印二项展开式 (a + b)i 的系数 杨辉三角形 (Pascal’s triangle)

分析第 i 行元素与第 i+1行元素的关系 目的是从前一行的数据可以计算下一行的数据

从第 i 行数据计算并存放第 i+1 行数据

void YANGVI ( int n ) { Queue q; //队列初始化 q.MakeEmpty ( ); q.EnQueue (1); q.EnQueue (1);//预放入第一行的两个系数 int s = 0; for ( int i=1; i<=n; i++ ) { //逐行处理 cout << endl; q.EnQueue (0); for ( int j=1; j<=i+2; j++ ) { //处理第i行的i+2个系数 int t = q.DeQueue ( );//读取系数 q.EnQueue ( s+t );//计算下一行系数，并进队列 s = t; if ( j != i+2 ) cout << s << ‘ ’;//打印一个系数，第 i+2个为0 }

优先级队列 (Priority Queue) 优先级队列 是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素 例如下表：任务的优先权及执行顺序的关系 数字越小，优先权越高

优先队列的类定义 #include <assert.h> #include <iostream.h> $include <stdlib.h> const int maxPQSize = 50; //缺省元素个数 template <class Type> class PQueue { public: PQueue ( ); ~PQueue ( ) { delete [ ] pqelements; } void PQInsert ( const Type & item ); Type PQRemove ( );

void makeEmpty ( ) { count = -1; } int IsEmpty ( ) const { return count == -1; } int IsFull ( ) const { return count == maxPQSize; } int Length ( ) const { return count; }/ /优先级队列元素个数 private: Type *pqelements; //存放数组（优先级队列数组） int count; //队列元素计数 }

优先级队列部分成员函数的实现 template <class Type> PQueue<Type>::PQueue ( ) : count (-1) { pqelements = new Type[maxPQSize]; assert ( pqelements != 0 ); //分配断言 } template <class Type> void PQueue<Type> :: PQInsert ( const Type & item ) { assert ( !IsFull ( ) ); //判队满断言 count ++； pqelements[count] = item;

template <class Type> Type PQueue<Type>::PQRemove ( ) { assert ( !IsEmpty ( ) ); //判队空断言 Type min = pqelements[0]; int minindex = 0; for ( int i=1; i<count; i++ ) //寻找最小元素 if ( pqelements[i] < min ) //存于min { min = pqelements[i]; minindex = i; } pqelements[minindex] = pqelements[count-1]; //用最后一个元素填补要取走的最小值元素 count-- ;//优先级队列中元素个数减一 return min; }

递 归 定义 若一个对象部分地包含它自己, 或用它自己给自己定义, 则称这个对象是递归的； 若一个过程直接地或间接地调用自己, 则称这个过程是递归的过程。 三种递归情况 定义是递归的 数据结构是递归的 问题的解法是递归的

定义是递归的 例1.阶乘函数 求解阶乘函数的递归算法 long Factorial ( long n ) { if ( n == 0 ) return 1; else return n * Factorial (n-1); }

求解阶乘 n! 的过程 主程序 main : fact(4) 参数 4 计算 4*fact(3) 返回 24 递归调用 参数传递 结果返回 回归求值 参数 3 计算 3*fact(2) 返回 6 参数 2 计算 2*fact(1) 返回 2 参数 1 计算 1*fact(0) 返回 1 参数 0 直接定值 = 1 返回 1

例2.计算斐波那契数列函数Fib(n)的定义 如 F0 = 0, F1 = 1, F2 = 1, F3 = 2, F4 = 3, F5 = 5 递归算法 long Fib ( long n ) { if ( n <= 1 ) return n; else return Fib (n-1) + Fib (n-2); }

数据结构是递归的 例如单链表结构 只有一个结点的单链表 f  有若干结点的单链表 f 

例1.搜索链表最后一个结点并打印其数值 递归找链尾 a1 a2 a3 a4 f a0 f f f f void Search ( ListNode *f ) { if ( f ->link == NULL ) printf (“%d\n”, f ->data ); else Search ( f ->link ); } 递归找链尾 a1 a2 a3 a4 f a0  f f f f

例2. 在链表中寻找等于给定值的结点,并打印其数值 void Search ( ListNode 例2.在链表中寻找等于给定值的结点,并打印其数值 void Search ( ListNode *f, ListData& x ) { if ( f != NULL ) if ( f -> data == x ) printf (“%d\n”, f ->data ); else Search ( f -> link, x ); } 递归找含x值的结点 f x  f f f

例如，汉诺塔(Tower of Hanoi)问题的解法： 问题的解法是递归的 例如，汉诺塔(Tower of Hanoi)问题的解法： 如果 n = 1，则将这一个盘子直接从 A 柱移到 C 柱上。否则，执行以下三步： ① 用 C 柱做过渡，将 A 柱上的 (n-1) 个盘子移到 B 柱上： ② 将 A 柱上最后一个盘子直接移到 C 柱上； ③ 用 A 柱做过渡，将 B 柱上的 (n-1) 个盘子移到 C 柱上。

算法 #include <iostream.h> #include "strclass.h” void Hanoi (int n, String A, String B, String C) { //解决汉诺塔问题的算法 if ( n == 1 ) printf (" move %s",A, " to %s,C); else { Hanoi ( n-1, A, C, B ); printf (" move %s",A, " to %s,C); Hanoi ( n-1, B, A, C ); }

递归过程与递归工作栈 递归过程在实现时，需要自己调用自己。 层层向下递归，退出时的次序正好相反： 递归调用 n! (n-1)! (n-2)! 1! 0!=1 返回次序 主程序第一次调用递归过程为外部调用； 递归过程每次递归调用自己为内部调用。

递归工作栈 每一次递归调用时，需要为过程中使用的参数、局部变量等另外分配存储空间。 每层递归调用需分配的空间形成递归工作记录，按后进先出的栈组织。 局部变量 返回地址 参 数 活动记录框架 递归 工作记录

函数递归时的活动记录 调用块 函数块 ………………. <下一条指令> Function(<参数表>) ………………. <return> 函数块 返回地址(下一条指令) 局部变量 参数

long Factorial ( long n ) { int temp; if ( n == 0 ) return 1; else temp = n * Factorial (n-1); RetLoc2 return temp; } void main ( ) { int n; n = Factorial (4); RetLoc1

计算Fact时活动记录的内容 参数 返回地址 返回时的指令 RetLoc1 return 4*6 //返回24 4 RetLoc1 参数 返回地址 返回时的指令 RetLoc1 return 4*6 //返回24 4 RetLoc1 递归调用序列 RetLoc2 return 3*2 //返回6 3 RetLoc2 2 RetLoc2 RetLoc2 return 2*1 //返回2 1 RetLoc2 RetLoc2 return 1*1 //返回1 0 RetLoc2 RetLoc2 return 1 //返回1

递归过程改为非递归过程 递归过程简洁、易编、易懂 递归过程效率低，重复计算多 改为非递归过程的目的是提高效率 单向递归和尾递归可直接用迭代实现其非递归过程 其他情形必须借助栈实现非递归过程

计算斐波那契数列的函数Fib(n)的定义 如 F0 = 0, F1 = 1, F2 = 1, F3 = 2, F4 = 3, F5 = 5 求解斐波那契数列的递归算法 long Fib ( long n ) { if ( n <= 1 ) return n; else return Fib (n-1) + Fib (n-2); }

斐波那契数列的递归调用树 Fib(5) Fib(4) Fib(3) Fib(3) Fib(2) Fib(2) Fib(1) Fib(2)

         栈结点 n tag tag = 1, 向左递归；tag = 2, 向右递归 Fib(4) Fib(3)

                           Fib(4) Fib(3) 2 1 3 1 4 1 2 2 3 1 4 1    3 1 4 1  3 2 4 1      4 1  4 2       n=1 sum=0+1 n=0 sum=1+0 n=1 sum=1+1 n=2-2 n=3-2 n=4-2

                 Fib(4) Fib(3) Fib(2) Fib(2) Fib(1) 2 1 4 2  2 2 4 2    4 2    n=1 sum=2+1 n=0 sum=3+0 n=2-2

long Fibnacci ( long n ) { Stack<Node> S; Node *w; long sum = 0; //反复执行直到所有终端结点数据累加完 do { while ( n > 1 ) { w->n = n; w->tag = 1; S.push ( w ); n--; } //向左递归到底, 边走边进栈 sum = sum + n; //执行求和

while ( !S.IsEmpty( ) ) { w = S.getTop( ); S.Pop( ); if ( w->tag == 1 ) { //改为向右递归 w->tag = 2; S.push ( w ); n = w->n – 2; //F(n)右侧为F(n-2) break; } } while ( !S.IsEmpty( ) ); return sum;

递归与回溯 n皇后问题 在 n 行 n 列的国际象棋棋盘上，若两个皇后位于同一行、同一列、同一对角线上，则称为它们为互相攻击。n皇后问题是指找到这 n 个皇后的互不攻击的布局。

    k = i+j k = n+i-j-1 0#次对角线 2#次对角线 1#次对角线 4#次对角线 3#次对角线 0 1 2 3 6#次对角线 k = i+j 1#次对角线 3#次对角线 5#次对角线 0 1 2 3 1 2 3    0#主对角线 2#主对角线 4#主对角线 6#主对角线 1#主对角线 3#主对角线 5#主对角线  k = n+i-j-1

解题思路 安放第 i 行皇后时，需要在列的方向从 0 到 n-1 试探 ( j = 0, …, n-1 ) 在第 j 列安放一个皇后： 如果没有出现攻击，在第 j 列安放的皇后不动，递归安放第 i+1行皇后。

设置 4 个数组 col [n] ：col[i] 标识第 i 列是否安放了皇后 md[2n-1] : md[k] 标识第 k 条主对角线是否安放了皇后 sd[2n-1] : sd[k] 标识第 k 条次对角线是否安放了皇后 q[n] : q[i] 记录第 i 行皇后在第几列

void Queen( int i ) { for ( int j = 0; j < n; j++ ) { if ( 第 i 行第 j 列没有攻击 ) { 在第 i 行第 j 列安放皇后； if ( i == n-1 ) 输出一个布局； else Queen ( i+1 ); 撤消第 i 行第 j 列的皇后； }

void Queen( int i ) { for ( int j = 0; j < n; j++ ) { if ( !col[j] && !md[n+i-j-1] && !sd[i+j] ) { /*第 i 行第 j 列没有攻击 */ col[j] = md[n+i-j-1] = sd[i+j] = 1; q[i] = j; /*在第 i 行第 j 列安放皇后*/ if ( i == n-1 ) { /*输出一个布局*/ for ( int k = 0; k < n; k++ ) cout << q[k] << ‘,’; cout << endl; } else Queen ( i+1 ); col[j] = md[n+i-j-1] = sd[i+j] = 0; q[i] = 0; /*撤消第 i 行第 j 列的皇后*/