C语言程序设计与数据结构第14章.pptx

栈
队列
树
栈


栈和队列是在软件设计中常用的两种数据结构，它们的逻辑结构和线性表相同。其特点在于运算受到了限制：栈按“后进先出”的规则进行操作，队按“先进先出”的规则进行操作，故称操作受限制的线性表。
树型结构是一种非常重要的非线性结构，它是具有分支关系的层次结构，可以用来描述较复杂的数据关系。树型结构应用非常广泛，特别是在数据处理方面，如在文件系统、编译系统、目录组织等方面，显得更加突出。
什么是栈
栈（Stack）是限定仅在表的一端进行插入和删除操作的线性表。通常将表中允许插入、删除操作的这一端称为栈顶（top），因此栈顶的当前位置是动态变化的，它由一个称为栈顶指针的位置指示器指示。同时表的另一端被称为栈底（bottom）。栈顶的第一个元素叫做栈顶元素。不含任何数据元素的栈称为空栈。栈的插入操作被形象的称为进栈或入栈，删除操作称为出栈或退栈。
假设有栈S=(a1,a2,…,an)，(a)所示，元素是以a1,a2,…,an的顺序进栈，因此栈底元素是a1，栈顶元素是an。退栈的第一个元素应为栈顶元素an。

(a) 栈
下面举例说明栈的结构特征。
假设有一个很窄的死胡同，胡同里能容纳若干人，但每次只能容许一个人进出。现有五个人，分别编号为①～⑤，按编号的顺序进入胡同，(b)所示。若④要出来，必须等⑤退出后才有可能。若①要退出，则必须等到⑤④③②依次都退出后才行。这里，人进出胡同的原则是后进去的先出来。换句话说，先进去的后出来。
栈可以比作这里的死胡同，栈顶相当于胡同口，栈底相当于胡同的另一端，进、出胡同可看作栈的插入、删除运算。插入、删除都在栈顶进行，进出都经过胡同口。这表明栈的原则是后进先出。因此，栈又称为后进先出(last in first out)线性表，简称 LIFO表。
栈的基本操作除了在进栈（栈顶插入）、出栈（删除栈顶元素）外，还有建立堆栈（栈的初始化）、判空和取栈顶元素等运算。
基本操作：
（1）INI_STACK(S)
（2）EMPTY_STACK (S)
（3）PUSH_STACK(S, x)
（4）POP_STACK(S)
（5）TOP_STACK(S)
顺序栈的实现
栈作为一种特殊的线性表，在计算机中也主要有两种基本的存储结构：顺序存储结构和链式存储结构。我们称顺序存储的栈为顺序栈，链式存储的栈为链栈。
顺序栈是用顺序存储结构实现的栈。顺序栈的存储结构可以用C语言中的一维数组来表示。栈的顺序存储结构定义如下：
#define MaxSize /* 线性表可能达到的最大长度 */
typedef struct /* 顺序栈类型定义 */
{ Elemtype data[MaxSize];
int top; /* 指示栈顶位置 */
}SeqStack;
这里把存放栈中元素的数组和指向栈顶的变量都作为结构体类型SeqStack的分量来定义。鉴于C语言中数组的下标值约定从0开始，则当以C语言作描述语言时，数组的0下标端设为栈底。这样，空栈时，栈顶指针top为-1；入栈时，栈顶指针top加1；出栈时，栈顶指针top减1。
假设用一维数组sq表示一个栈，。

(a)是空栈； (b)是只有一个元素时的状态； (c)是A、B、C、D、E、F这六个元素依次进入栈之后的状态；(d)是删除E、F两个元素后的状态，此时栈中还有四个元素，或许刚出栈的元素E、F仍然在原先的单元存储着，但top指针已经指向了新的栈顶，则元素E