西安交通大学：《计算机软件基础》线性数据结构（二）（仇国巍）

软件技术基础 线性数据结构(二) 主讲:仇国巍 西安交通大学计算机教学实验中心

线性数据结构（二） 软件技术基础 主讲：仇国巍 西安交通大学计算机教学实验中心

教学内廖及要求 内容:栈、队列、数组、串的 有关概念 逻辑结构及特点 存储结构 有关操作 要求:熟练掌握上述内容及有关操作的算法 实现。 2021年2月24日 2

2021年2月24日 2 教学内容及要求 内容：栈、队列、数组、串的 ◼ 有关概念 ◼ 逻辑结构及特点 ◼ 存储结构 ◼ 有关操作 要求：熟练掌握上述内容及有关操作的算法 实现

本讲涉误本内容 第1章的 1.3栈和队列(P32-P46) 1.4串和数组(P47-P55) 2021年2月24日 3

2021年2月24日 3 第1章的 ◼ 1.3 栈和队列 (P32 - P46) ◼ 1.4 串和数组 (P47 - P55) 本讲涉及课本内容

栈结构 栈的定义 ■栈的顺序存储结构 栈的基本运算 多栈共享问题 ■栈的链式存储结构 栈的应用 2021年2月24日

2021年2月24日 4 ◼ 栈的定义 ◼ 栈的顺序存储结构 ◼ 栈的基本运算 ◼ 多栈共享问题 ◼ 栈的链式存储结构 ◼ 栈的应用 一、栈结构

1.1的定义 栈是只允许在同一端进行插入和删除操作 的特殊线性表。允许进行插入和删除操作的 端称为栈页(top),另一端为栈底( bottom); 栈底固定,而栈顶浮动;栈结构也称为后进先 出表(LIF0)。 栈中元素个数为零时称为空栈 2021年2月24日

2021年2月24日 5 栈是只允许在同一端进行插入和删除操作 的特殊线性表。允许进行插入和删除操作的一 端称为栈顶(top)，另一端为栈底(bottom)； 栈底固定，而栈顶浮动；栈结构也称为后进先 出表（LIFO）。 栈中元素个数为零时称为空栈。 1.1 栈的定义

1.2花的颁序存储结构 ■栈的顺序存储结构实际上是一维数组结构。 这种栈又称为—顺序栈。 ■栈的操作只能在一端进行;即栈顶位置随进 栈和出栈而变化。 顺序栈的C语言描述为: #define maXsize 200 int stackMAXSIZE: int top =-1 2021年2月24日

2021年2月24日 6 1.2 栈的顺序存储结构 ◼ 栈的顺序存储结构实际上是一维数组结构。 ◼ 这种栈又称为——顺序栈。 ◼ 栈的操作只能在一端进行；即栈顶位置随进 栈和出栈而变化。 ◼ 顺序栈的C语言描述为： #define MAXSIZE 200 int stack[MAXSIZE]; int top = -1;

栈顶指针 ■栈顶指针:在栈操作过程中,有一个专 门的栈指针(习惯上称它为TOP),指出 栈顶元素所在的位置 ■栈空的条件:top=-1 ■栈满的条件:top=MAXS|ZE-1 2021年2月24日

2021年2月24日 7 栈顶指针 ◼ 栈顶指针：在栈操作过程中，有一个专 门的栈指针（习惯上称它为TOP），指出 栈顶元素所在的位置。 ◼ 栈空的条件： top = -1 ◼ 栈满的条件： top = MAXSIZE-1

1.3栈操作举例 TOP a1 a 2 a MAXSIZE 栈底 栈顶 2.AB C top=-1(空栈) top-3(A、B、C进栈) 3.AB 4.AIBICIDEF top=2 (C出栈) top= MAXSIZE-1/(钱满) 2021年2月24日

2021年2月24日 8 a1 a2 …… an 栈底 栈顶 MAXSIZE TOP 1. top = -1 2. A B C (空栈) top=3 (A、B、C进栈） 3. A B top=2 (C出栈） 4. A B C D E F top=MAXSIZE-1 (栈满） 1.3 栈操作举例

栈溢出 栈上溢:栈空间是有限的,若栈已满, 在进行入栈操作时,就要产生上溢。 栈下溢:若栈空,再要执行出栈操作, 则会发生下溢。 2021年2月24日

2021年2月24日 9 栈上溢：栈空间是有限的，若栈已满， 在进行入栈操作时，就要产生上溢。 栈下溢：若栈空，再要执行出栈操作， 则会发生下溢。 栈溢出

1.4花的基本运募 ■进栈操作(插入)Push( Stack,x) 出栈操作(删除)Pop( Stack) 取栈顶元素Getp( Stack) 置栈为空 Setnull( stack 判定栈是否为空 Empty( Stack) 2021年2月24日

2021年2月24日 10 ◼ 进栈操作(插入) Push（Stack，x） ◼ 出栈操作(删除）Pop（Stack） ◼ 取栈顶元素 Gettop（Stack） ◼ 置栈为空 Setnull（Stack） ◼ 判定栈是否为空 Empty（Stack） 1.4 栈的基本运算