栈和队列 PPT课件.ppt

文档介绍：第三章栈和队列
栈和队列是两种特殊的线性表,是操作受限的线性表,称限定性DS
栈(stack)
栈的定义和特点
定义:限定仅在表尾进行插入或删除操作的线性表,表尾—栈顶,表头—栈底,不含元素的空表称空栈
特点:先进后出(FILO)或后进先出(LIFO)
an
a1
a2
……...
栈底
栈顶
...
出栈
进栈
栈s=(a1,a2,……,an)
线性表栈队列
Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x)
1≤i≤n+1
Delete(L, i) Delete(S, n) Delete(Q, 1)
1≤i≤n
栈的存储结构
顺序栈
实现:一维数组s[M]
top=0
1
2
3
4
5
0
栈空
栈顶指针top,指向实际栈顶
后的空位置,初值为0
top
1
2
3
4
5
0
进栈
A
top
出栈
栈满
B
C
D
E
F
设数组维数为M
top=0,栈空,此时出栈,则下溢(underflow)
top=M,栈满,此时入栈,则上溢(overflow)
top
top
top
top
top
1
2
3
4
5
0
A
B
C
D
E
F
top
top
top
top
top
top
栈空
base=0
base=0
base=0
//----- 栈的顺序存储表示-----
#define STACK_INIT_SIZE 100;
#define STACKINCREMENT 10;
typedef struct {
SElemType *base;
SElemType *top;
int stacksize;
} SqStack;
类似于线性表的顺序映象实现,指向表尾的指针可以作为栈顶指针。
入栈算法
0
M-1
栈1底
栈1顶
栈2底
栈2顶
出栈算法
在一个程序中同时使用两个栈
链栈
栈顶
^
…...
top
data
next
栈底
结点定义
入栈算法
出栈算法
typedef struct node
{ int data;
struct node *next;
}JD;
^
…...
栈底
top
top
x
p
top
^
…...
栈底
top
q
栈的应用
过程的嵌套调用
r
主程序
s
r
r
r
s
子过程1
r
s
t
子过程2
r
s
t
子过程3
例递归的执行情况分析
递归过程及其实现
递归:函数直接或间接的调用自身叫~
实现:建立递归工作栈
w=3;
void print( int w)
{ int i;
if ( w!=0)
{ print(w-1);
for(i=1;i<=w;++i)
printf(“%3d,”,w);
printf(“/n”);
}
}

运行结果:
1,
2,2,
3,3,3,
递归调用执行情况如下:
主程序
(1)
print(w)
w=3;
3
print(2);
(1)w=3
top
(2) 输出:3, 3, 3
w
2
print(1);
(2)w=2
(1)w=3
top
(3) 输出:2, 2
w
1
print(0);
(3)w=1
(2)w=2
(1)w=3
top
(4)输出:1
w
0
(4)w=0
(3)w=1
(2)w=2
(1)w=3
top
w
(3) 输出:2, 2
(2) 2
(1) 3
top
(4)输出:1
(3) 1
(2) 2
(1) 3
top
(2) 输出:3, 3, 3
(1 ) 3
top
返回
(3) 1
(2) 2
(1) 3
top
(4) 0
结束
(1)
A
B
C
汉诺塔问题
一块板上有三根柱子:A,B,C。A柱上套有64个大小不等的圆盘:大的在下,小的在上。要求把这64个圆盘从A移动到C上,每次只能移动一个圆盘,移动时可以借助B来进行。但在任何时候,任何柱上的圆盘都必须保持大盘在下,小盘在上。求移动的过程。
本题算法分析如下,设A上有n个盘子。
如果n=1,则将圆盘从A直接移动到C。
如果n>=2时,移动的过程可分解为三个步骤:
第一步:把A上的n-1个圆盘移到B上;
第二步:把A上的一个圆盘移到C上;
第三步:把B上的n-1个圆盘移到C上。