1 / 51
文档名称:

数据结构栈和队列.ppt

格式:ppt   大小:1,459KB   页数:51页
下载后只包含 1 个 PPT 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

数据结构栈和队列.ppt

上传人:q1188830 2017/7/21 文件大小:1.42 MB

下载得到文件列表

数据结构栈和队列.ppt

相关文档

文档介绍

文档介绍:数据结构与算法
第三章栈和队列
栈和队列是两种特殊的线性表,是操作受限的线性表,称限定性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
(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)
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问题
算法:
执行情况:
递归工作栈保存内容:形参n,x,y,z和返回地址
返回地址用行编号表示
n x y z 返回地址
main()
{ int m;
printf("Input number of disks”);
scanf("%d",&m);
printf(”Steps : %3d disks”,m);
hanoi(m,'A','B','C');
(0) }
void hanoi(int n,char x,char y,char z)
(1) {
(2) if(n==1)
(3) move(1,x,z);
(4) else{
(5) hanoi(n-1,x,z,y);
(6) move(n,x,z);
(7) hanoi(n-1,y,x,z);

最近更新

智能温室大棚转让与运营管理协议 3页

智能电网建设与运营合同范本 18页

装饰工程技术交底样本 10页

生物旅游资源的开发利用策略研究 33页

公司春晚文艺节目演出串词 6页

公民私有财产的继承受法律保护的教学设计 3页

智能音响设备采购及安装合同 3页

服装代理居间销售管理标准合同 3页

内蒙古自治区呼和浩特市方圆中学高三英语联考.. 5页

内蒙古自治区赤峰市市克旗经棚第一中学高三数.. 6页

区块链技术在生物信息领域的创新应用案例 33页

内蒙古自治区赤峰市松山区五三地区中学2021年.. 7页

内蒙古自治区赤峰市艺术高中2021-2022学年高一.. 6页

内蒙古自治区赤峰市马蹄营子职业高中高二化学.. 4页

农场里的悄悄话大班教案 3页

出版光盘合同 3页

初二学生操行鉴定评语 3页

办公大楼清洁开荒管理作业规程 1 3页

匆匆读后感400字读后感 3页

2021年市场营销题库 33页

北京下滩中学高二生物下学期期末试卷含解析 10页

农产品国际贸易:国际市场对农产品重金属含量.. 21页

采棉机驾驶员职业技能鉴定与劳动合同 3页

中国急性期缺血性脑卒中诊治指南2025 12页

汽车刹车抱死的利与弊 5页

汇总 - 39种行业废水处理工艺流程图 4页

书包质检报告 22页

风力发电施工安全培训课件 35页

发电厂电气主接线及厂用电 120页

JT∕T 1375.1-2022 公路水运工程施工安全风险.. 18页