? 栈
队列
递归第三章栈和队列栈 ( Stack )
定义,是限定仅在表尾进行插入或删除操作的线性表。
允许插入和删除的一端称为栈顶 (top)，另一端称为栈底 (bottom)
特点,后进先出 (LIFO)
a1
top
bottom
an
.
.
.
.
进栈出栈栈的主要操作
ADT Stack {
//对象由数据类型为 StackData的元素构成
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为栈底指针，指向栈底的位置。
base
空栈 a 进栈 b 进栈
a a
btop basetop
base
top
top top
ab
c
d
e
e 进栈
ab
c
d
e
f 进栈溢出
ab
d
e 出 栈
c
base basebase
top
顺序栈的类型表示,
#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
else return 0; //否则返回 0
}
顺序栈的基本运算,
初始化
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) {
//若栈空返回 0,否则栈顶元素读到 x并返回 1
if ( StackEmpty(S) ) return 0;
(S->top)--;
x = *(S->top);
return 1;
}
出栈
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 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
中缀式,a? b + c? d / e? f
后缀式,a b? c d e /? f? +
表达式标识方法
b -
c
a
/
*
d e
f
*
+
后缀表达式求值先找运算符，再找操作数例如：
a b? c d e /? f? +
a?b d/e
c-d/e
(c-d/e)?f
从原表达式求得后缀式方法
1) 设立暂存 运算符 的 栈 ;
2) 设表达式的结束符为,#‖,予设 运算符栈的 栈底为,#‖
3) 若 当前字符 是操作数,则 直接发送给后缀式 ;
4) 若 当前 运算符的 优先数高 于栈顶运算符，
则 进栈 ;
5) 否则，退出栈顶运算符发送给后缀式 ;
6) ―(‖ 对它之前后的运算符 起隔离作用,
,)‖为自左括弧开始的表达式的结束符。
队列
定义,只允许在表的一端进行插入，而在另一端删除元素的线性表。
在队列中，允许插入的一端叫队尾 （ rear）
,允许删除的一端称为对头 (front)。
特点,先进先出 (FIFO)
a1,a2,a3,…,an
出队列 入队列队头队尾链队列,队列的链式表示
链队列中，有两个分别指示队头和队尾的指针。
链式队列在进队时无队满问题，但有队空问题。
data next
front
reardata next
front
rear
front
rear x ^
元素 x入队
front
rear
x ^ y ^ 元素 y入队
front
rear
x ^^ y 元素 x出队
front
rear ^
空队列^ frontrear NULL 空队列链式队列的定义
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，
因此，在非空队列中，头指针始终指向队列头元素，而尾指针始终指向队列尾元素的下一个位置。
队满时再进队将溢出
解决办法：将顺序队列臆造为一个环状的空间，
形成循环 (环形 )队列队列的进队和出队
front rear 空队列 front rear
A,B,C,D进队
A B C D
front rear
A,B出队
C D
front rear
E,F,G进队
C D E F G
C D E F G
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;
0
1
23
4
5
6 7
循环队列 front
rear
Maxsize-1
0
1
23
4
5
6 7 front
B
CDrear
一般情况
A
C
0
1
23
4
5
6 7
队满
front
rear
D
E
F
G
A
B
C
H
0
1
23
4
5
6 7 rear
空队列
front
C
0
1
23
4
5
6 7
队满 (正确 )
front
rear
D
E
F
G
A
B
C
#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 ) {
if ( QueueEmpty (Q) ) return 0;
x = Q->data[(Q->front+1) % MAXSIZE];
return 1;
}
1 1 i = 1
1 2 1 2
1 5 5 1 3
1 4 6 4 1 4
1 5 10 10 5 1 5
1 6 15 20 15 6 1 6
队列应用举例
—打印二项展开式 (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
}
}
}
任务编号 1 2 3 4 5
优先权 2 0 0 4 0 3 0 1 0
执行顺序 3 1 5 4 2
优先级队列 (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;
}
递 归
定义 若一个对象部分地包含它自己,或用它自己给自己定义,则称这个对象是递归的；
若一个过程直接地或间接地调用自己,
则称这个过程是递归的过程 。
三种递归情况
定义是递归的
数据结构是递归的
问题的解法是递归的定义是递归的求解阶乘函数的递归算法
long Factorial ( long n ) {
if ( n == 0 ) return 1;
else return n * Factorial (n-1);
}
例 1.阶乘函数
时当时当
1,)!1(
0,1
!
n
n
nn
n
求解阶乘 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)的定义递归算法
long Fib ( long n ) {
if ( n <= 1 ) return n;
else return Fib (n-1) + Fib (n-2);
}
1n2 ),F i b ( n1)F i b ( n
0,1nn,
)F i b ( n
如 F0 = 0,F1 = 1,F2 = 1,F3 = 2,F4 = 3,F5 = 5
数据结构是递归的有若干结点的单链表例如单链表结构
f?
f?
只有一个结点的单链表例 1.搜索链表最后一个结点并打印其数值
void Search ( ListNode *f ) {
if ( f ->link == NULL )
printf (―%d \n‖,f ->data );
else Search ( f ->link );
}
f
f f f f
a0 a1 a2 a3 a4
递归找链尾例 2.在链表中寻找等于给定值的结点,并打印其数值
void Search ( ListNode *f,ListData& x ) {
if ( f != NULL )
if ( f -> data == x )
printf (“%d\n”,f ->data );
else Search ( f -> link,x );
}
f
f f f
递归找含 x值的结点
x
例如，汉诺塔 (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时活动记录的内容递归调用序列
0 RetLoc2
1 RetLoc2
2 RetLoc2
3 RetLoc2
4 RetLoc1
参数 返回地址 返回时的指令
RetLoc1 return 4*6 //返回 24
RetLoc2 return 3*2 //返回 6
RetLoc2 return 1 //返回 1
RetLoc2 return 1*1 //返回 1
RetLoc2 return 2*1 //返回 2
递归过程改为非递归过程
递归过程简洁、易编、易懂
递归过程效率低，重复计算多
改为非递归过程的目的是提高效率
单向递归和尾递归可直接用迭代实现其非递归过程
其他情形必须借助栈实现非递归过程计算斐波那契数列的函数 Fib(n)的定义求解斐波那契数列的递归算法
long Fib ( long n ) {
if ( n <= 1 ) return n;
else return Fib (n-1) + Fib (n-2);
}
1n2 ),F i b ( n1)F i b ( n
0,1nn,
)F i b ( n
如 F0 = 0,F1 = 1,F2 = 1,F3 = 2,F4 = 3,F5 = 5
斐波那契数列的递归调用树
Fib(1) Fib(0)
Fib(1)Fib(2)
Fib(3)
Fib(4)
Fib(1) Fib(0)
Fib(2)
Fib(1) Fib(0)
Fib(1)Fib(2)
Fib(3)
Fib(5)
Fib(1) Fib(0)
Fib(2) Fib(1) Fib(0)
Fib(2)
Fib(1)
Fib(3)
Fib(4)
栈结点 n tag
tag = 1,向左递归； tag = 2,向右递归
Fib(1) Fib(0)
Fib(2) Fib(1) Fib(0)
Fib(2)
Fib(1)
Fib(3)
Fib(4)
2 1
3 1
4 1
n=1
sum=0+1
2 2
3 1
4 1
n=2-2
3 1
4 1
n=0
sum=1+0
3 2
4 1
n=3-2
4 1
n=1
sum=1+1
4 2
n=4-2
Fib(1) Fib(0)
Fib(2) Fib(1) Fib(0)
Fib(2)
Fib(1)
Fib(3)
Fib(4)
2 1
4 2
n=1
sum=2+1
2 2
4 2
n=2-2
4 2
n=0
sum=3+0
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 个皇后的互不攻击的布局 。
1#主对角线
3#主对角线
5#主对角线
0#次对角线
2#次对角线
4#次对角线
6#次对角线
1#次对角线
3#次对角线
5#次对角线
0#主对角线
2#主对角线
4#主对角线
6#主对角线
0 1 2 3
0
1
2
3
k = i+j
k = n+i-j-1
解题思路
安放 第 i 行 皇后时，需要在列的方向从 0 到 n-
1 试探 ( j = 0,…,n -1 )
在 第 j 列 安放一个皇后：
如果在 列,主对角线,次对角线 方向有其它皇后，则出现攻击，撤消在 第 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 列的皇后 */
}
}
}
队列
递归第三章栈和队列栈 ( Stack )
定义,是限定仅在表尾进行插入或删除操作的线性表。
允许插入和删除的一端称为栈顶 (top)，另一端称为栈底 (bottom)
特点,后进先出 (LIFO)
a1
top
bottom
an
.
.
.
.
进栈出栈栈的主要操作
ADT Stack {
//对象由数据类型为 StackData的元素构成
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为栈底指针，指向栈底的位置。
base
空栈 a 进栈 b 进栈
a a
btop basetop
base
top
top top
ab
c
d
e
e 进栈
ab
c
d
e
f 进栈溢出
ab
d
e 出 栈
c
base basebase
top
顺序栈的类型表示,
#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
else return 0; //否则返回 0
}
顺序栈的基本运算,
初始化
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) {
//若栈空返回 0,否则栈顶元素读到 x并返回 1
if ( StackEmpty(S) ) return 0;
(S->top)--;
x = *(S->top);
return 1;
}
出栈
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 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
中缀式,a? b + c? d / e? f
后缀式,a b? c d e /? f? +
表达式标识方法
b -
c
a
/
*
d e
f
*
+
后缀表达式求值先找运算符，再找操作数例如：
a b? c d e /? f? +
a?b d/e
c-d/e
(c-d/e)?f
从原表达式求得后缀式方法
1) 设立暂存 运算符 的 栈 ;
2) 设表达式的结束符为,#‖,予设 运算符栈的 栈底为,#‖
3) 若 当前字符 是操作数,则 直接发送给后缀式 ;
4) 若 当前 运算符的 优先数高 于栈顶运算符，
则 进栈 ;
5) 否则，退出栈顶运算符发送给后缀式 ;
6) ―(‖ 对它之前后的运算符 起隔离作用,
,)‖为自左括弧开始的表达式的结束符。
队列
定义,只允许在表的一端进行插入，而在另一端删除元素的线性表。
在队列中，允许插入的一端叫队尾 （ rear）
,允许删除的一端称为对头 (front)。
特点,先进先出 (FIFO)
a1,a2,a3,…,an
出队列 入队列队头队尾链队列,队列的链式表示
链队列中，有两个分别指示队头和队尾的指针。
链式队列在进队时无队满问题，但有队空问题。
data next
front
reardata next
front
rear
front
rear x ^
元素 x入队
front
rear
x ^ y ^ 元素 y入队
front
rear
x ^^ y 元素 x出队
front
rear ^
空队列^ frontrear NULL 空队列链式队列的定义
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，
因此，在非空队列中，头指针始终指向队列头元素，而尾指针始终指向队列尾元素的下一个位置。
队满时再进队将溢出
解决办法：将顺序队列臆造为一个环状的空间，
形成循环 (环形 )队列队列的进队和出队
front rear 空队列 front rear
A,B,C,D进队
A B C D
front rear
A,B出队
C D
front rear
E,F,G进队
C D E F G
C D E F G
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;
0
1
23
4
5
6 7
循环队列 front
rear
Maxsize-1
0
1
23
4
5
6 7 front
B
CDrear
一般情况
A
C
0
1
23
4
5
6 7
队满
front
rear
D
E
F
G
A
B
C
H
0
1
23
4
5
6 7 rear
空队列
front
C
0
1
23
4
5
6 7
队满 (正确 )
front
rear
D
E
F
G
A
B
C
#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 ) {
if ( QueueEmpty (Q) ) return 0;
x = Q->data[(Q->front+1) % MAXSIZE];
return 1;
}
1 1 i = 1
1 2 1 2
1 5 5 1 3
1 4 6 4 1 4
1 5 10 10 5 1 5
1 6 15 20 15 6 1 6
队列应用举例
—打印二项展开式 (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
}
}
}
任务编号 1 2 3 4 5
优先权 2 0 0 4 0 3 0 1 0
执行顺序 3 1 5 4 2
优先级队列 (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;
}
递 归
定义 若一个对象部分地包含它自己,或用它自己给自己定义,则称这个对象是递归的；
若一个过程直接地或间接地调用自己,
则称这个过程是递归的过程 。
三种递归情况
定义是递归的
数据结构是递归的
问题的解法是递归的定义是递归的求解阶乘函数的递归算法
long Factorial ( long n ) {
if ( n == 0 ) return 1;
else return n * Factorial (n-1);
}
例 1.阶乘函数
时当时当
1,)!1(
0,1
!
n
n
nn
n
求解阶乘 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)的定义递归算法
long Fib ( long n ) {
if ( n <= 1 ) return n;
else return Fib (n-1) + Fib (n-2);
}
1n2 ),F i b ( n1)F i b ( n
0,1nn,
)F i b ( n
如 F0 = 0,F1 = 1,F2 = 1,F3 = 2,F4 = 3,F5 = 5
数据结构是递归的有若干结点的单链表例如单链表结构
f?
f?
只有一个结点的单链表例 1.搜索链表最后一个结点并打印其数值
void Search ( ListNode *f ) {
if ( f ->link == NULL )
printf (―%d \n‖,f ->data );
else Search ( f ->link );
}
f
f f f f
a0 a1 a2 a3 a4
递归找链尾例 2.在链表中寻找等于给定值的结点,并打印其数值
void Search ( ListNode *f,ListData& x ) {
if ( f != NULL )
if ( f -> data == x )
printf (“%d\n”,f ->data );
else Search ( f -> link,x );
}
f
f f f
递归找含 x值的结点
x
例如，汉诺塔 (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时活动记录的内容递归调用序列
0 RetLoc2
1 RetLoc2
2 RetLoc2
3 RetLoc2
4 RetLoc1
参数 返回地址 返回时的指令
RetLoc1 return 4*6 //返回 24
RetLoc2 return 3*2 //返回 6
RetLoc2 return 1 //返回 1
RetLoc2 return 1*1 //返回 1
RetLoc2 return 2*1 //返回 2
递归过程改为非递归过程
递归过程简洁、易编、易懂
递归过程效率低，重复计算多
改为非递归过程的目的是提高效率
单向递归和尾递归可直接用迭代实现其非递归过程
其他情形必须借助栈实现非递归过程计算斐波那契数列的函数 Fib(n)的定义求解斐波那契数列的递归算法
long Fib ( long n ) {
if ( n <= 1 ) return n;
else return Fib (n-1) + Fib (n-2);
}
1n2 ),F i b ( n1)F i b ( n
0,1nn,
)F i b ( n
如 F0 = 0,F1 = 1,F2 = 1,F3 = 2,F4 = 3,F5 = 5
斐波那契数列的递归调用树
Fib(1) Fib(0)
Fib(1)Fib(2)
Fib(3)
Fib(4)
Fib(1) Fib(0)
Fib(2)
Fib(1) Fib(0)
Fib(1)Fib(2)
Fib(3)
Fib(5)
Fib(1) Fib(0)
Fib(2) Fib(1) Fib(0)
Fib(2)
Fib(1)
Fib(3)
Fib(4)
栈结点 n tag
tag = 1,向左递归； tag = 2,向右递归
Fib(1) Fib(0)
Fib(2) Fib(1) Fib(0)
Fib(2)
Fib(1)
Fib(3)
Fib(4)
2 1
3 1
4 1
n=1
sum=0+1
2 2
3 1
4 1
n=2-2
3 1
4 1
n=0
sum=1+0
3 2
4 1
n=3-2
4 1
n=1
sum=1+1
4 2
n=4-2
Fib(1) Fib(0)
Fib(2) Fib(1) Fib(0)
Fib(2)
Fib(1)
Fib(3)
Fib(4)
2 1
4 2
n=1
sum=2+1
2 2
4 2
n=2-2
4 2
n=0
sum=3+0
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 个皇后的互不攻击的布局 。
1#主对角线
3#主对角线
5#主对角线
0#次对角线
2#次对角线
4#次对角线
6#次对角线
1#次对角线
3#次对角线
5#次对角线
0#主对角线
2#主对角线
4#主对角线
6#主对角线
0 1 2 3
0
1
2
3
k = i+j
k = n+i-j-1
解题思路
安放 第 i 行 皇后时，需要在列的方向从 0 到 n-
1 试探 ( j = 0,…,n -1 )
在 第 j 列 安放一个皇后：
如果在 列,主对角线,次对角线 方向有其它皇后，则出现攻击，撤消在 第 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 列的皇后 */
}
}
}
