文档介绍：栈和队列
栈和队列是两种特殊的线性表,是操作受限的线性表,称限定性DS
栈(stack)
栈的定义和特点
定义:限定仅在表尾进行插入或删除操作的线性表,表尾—栈顶,表头—栈底,不含元素的空表称空栈
特点:先进后出(FILO)或后进先出(LIFO)
an
a1
a2
……...
栈底
栈顶
...
出栈
进栈
栈s=(a1,a2,……,an)
栈的存储结构
顺序栈
实现:一维数组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
栈空
创建栈判断栈空
0
M-1
栈1底
栈1顶
栈2底
栈2顶
入栈算法出栈算法
在一个程序中同时使用两个栈
定义顺序栈
链栈
栈顶
^
…...
top
data
link
栈底
结点定义
入栈算法
出栈算法
typedef struct node
{ int data;
struct node *link;
}JD;
^
…...
栈底
top
top
x
p
top
^
…...
栈底
top
q
栈的应用
过程的嵌套调用
r
主程序
s
r
r
r
s
子过程1
r
s
t
子过程2
r
s
t
子过程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
w
2
print(1);
(2)w=2
(1)w=3
top
w
1
print(0);
(3)w=1
(2)w=2
(1)w=3
top
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)
Tower of Hanoi问题
问题描述:有A,B,C三个塔座,A上套有n个直径不同的圆盘,按直径从小到大叠放,形如宝塔,编号1,2,3……n。要求将n个圆盘从A移到C,叠放顺序不变,移动过程中遵循下列原则:
每次只能移一个圆盘
圆盘可在三个塔座上任意移动
任何时刻,每个塔座上不能将大盘压到小盘上
解决方法:
n=1时,直接把圆盘从A移到C
n>1时,先把上面n-1个圆盘从A移到B,然后将n号盘从A移到C,再将n-1个盘从B移到C。即把求解n个圆盘的Hanoi问题转化为求解n-1个圆盘的Hanoi问题,依次类推,直至转化成只有一个圆盘的Hanoi问题
算法: