（第五讲）.ppt

文档介绍：(第五讲)
绍兴文理学院
计算机系计算机应用教研室
数据结构
TKS
2
为什么在算术表达式中能先乘除后加减运算?
21:54
第3章栈和队列(1)
一、教学目的:明确栈的有关概念;掌握栈的逻辑结构和存储结构,掌握顺序和链式栈的基本操作;掌握栈的初步应用。
二、教学重点:栈的LIFO的结构和操作特点;栈的逻辑结构和存储结构,顺序和链式栈的基本操作;栈的初步应用;算法设计训练。
三、教学难点:栈的LIFO的有关概念和操作;栈的初步应用。算法实现能力的训练。
四、教学过程:
§ 栈(stack)
§ 栈的类型定义
1、定义:栈是限定仅在表尾进行插入或删除操作的线性表。
表尾端称为栈顶(top),表头端称为栈底(bottom),不含元素的空表称为空栈。
2、栈的逻辑结构及进出栈
S=(a1,a2,...,ai-1,ai,ai+1,…,an )
删除
插入
出栈
进栈
栈顶
栈底
an
a2
a1
第一个进栈的元素在栈底,
最后一个进栈的元素在栈顶,
第一个出栈的元素为栈顶元素,
最后一个出栈的元素为栈底元素
栈的特点后进先出
LIFO
TKS
4
21:54
3、栈的抽象数据类型定义(简讲)
ADT Stack
{ 数据对象:D={ai|ai ∈ElemSet, i=1,2,...,n, n≥0}
数据关系:R1={<ai-1, ai >| ai-1, ai∈D, i=2,...,n}
约定an 端为栈顶,a1 端为栈底。
基本操作:
InitStack(&S)
操作结果:构造一个空栈 S。
DestroyStack(&S)
初始条件:栈 S 已存在。
操作结果:栈 S 被销毁。
ClearStack(&S)
初始条件:栈 S 已存在。
操作结果:将 S 清为空栈。
TKS
5
21:54
StackEmpty(S)
初始条件:栈 S 已存在。
操作结果:若栈 S 为空栈,则返回 TRUE,否则 FALE。
StackLength(S)
初始条件:栈 S 已存在。
操作结果:返回 S 的元素个数,即栈的长度。
GetTop(S, &e)
初始条件:栈 S 已存在且非空。
操作结果:用 e 返回 S 的栈顶元素。
a1
a2
……
an
TKS
6
21:54
a
Push(&S,e)
初始条件:栈 S 已存在。
操作结果:插入元素 e 为新的栈顶元素。
e
a1
a2
an
……
Pop(&S, &e)
初始条件:栈 S 已存在且非空。
操作结果:删除 S 的栈顶元素,并用 e 返回其值。
a1
a2
an-1
……
}ADT Stack
TKS
7
21:54
1、结构定义
#define size 256
struct sqstack
{ selemtype *base;
int top;
int stacksize;
};
§ 顺序栈的表示和实现
top=-1
空栈
2、栈顶指针top与栈中数据元素的关系
top=-1
空栈
top=0
1个元素
top=4
5个元素
top=2
3个元素
TKS
8
21:54
3、初始化
构造一个空栈:首先建立栈空间,然后初始化栈顶指针。
int InitSqStack(sqstack &s)
{ =new selemtype[size];
=-1; =size;
return 1;
}
4、入栈
int push(sqstack
&s,selemtype e)
{ if(==SIZE-1) return 0;
// 栈满不能入栈
++;
[]=e;
return 1;
}
5、出栈
int pop(sqstack &s,
selemtype &e)
{ if(==-1) return 0;
// 栈空不能出栈
e=[]
--;
return 1;
}
TKS
9
21:54
6、取栈顶元素
int gettop(sqstack s,selemtype &e)
{ if(==-1) return 0; // 栈空
e=[];
}
顺序栈的基本操作 S5_1
§ 链栈的表示和实现
Data next
top
栈顶
栈底
an-1
a1
an
TKS
10
21:54
1、链栈概述
(1) 概念
用链式