《C语言程序设计与数据结构》第章栈、队列与树.ppt

C语言程序设计与数据结构 第十四章 栈、队列与树 总体要求： ?掌握栈、队列和树的概念、有关术语； ?掌握栈、队列的基本操作； ?掌握树的定义与二叉树的性质； ?掌握二叉树的存储结构及二叉树的先序、中序、后序遍历算法； ?学会栈、队列和树的灵活应用。 学习重点： ?栈和队列的基本操作； ?二叉树的存储和遍历。六种位运算的综合使用 14.1 栈 14.2 队列 14.3 树 14.1 栈 14.1.1什么是栈 14.1.2顺序栈的实现 栈和队列是在软件设计中常用的两种数据结构，它们的逻辑结构和线性表相同。其特点在于运算受到了限制：栈按“后进先出”的规则进行操作，队按“先进先出”的规则进行操作，故称操作受限制的线性表。 树型结构是一种非常重要的非线性结构，它是具有分支关系的层次结构，可以用来描述较复杂的数据关系。树型结构应用非常广泛，特别是在数据处理方面，如在文件系统、编译系统、目录组织等方面，显得更加突出。 14.1.1 什么是栈 栈（Stack）是限定仅在表的一端进行插入和删除操作的线性表。通常将表中允许插入、删除操作的这一端称为栈顶（top），因此栈顶的当前位置是动态变化的，它由一个称为栈顶指针的位置指示器指示。同时表的另一端被称为栈底（bottom）。栈顶的第一个元素叫做栈顶元素。不含任何数据元素的栈称为空栈。栈的插入操作被形象的称为进栈或入栈，删除操作称为出栈或退栈。 假设有栈S=(a1,a2,…,an)，如图14.1(a)所示，元素是以a1,a2,…,an的顺序进栈，因此栈底元素是a1，栈顶元素是an。退栈的第一个元素应为栈顶元素an。 图14.1(a) 栈 下面举例说明栈的结构特征。 假设有一个很窄的死胡同，胡同里能容纳若干人，但每次只能容许一个人进出。现有五个人，分别编号为①～⑤，按编号的顺序进入胡同，如图14.1(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) 14.1.2 顺序栈的实现 栈作为一种特殊的线性表，在计算机中也主要有两种基本的存储结构：顺序存储结构和链式存储结构。我们称顺序存储的栈为顺序栈，链式存储的栈为链栈。 顺序栈是用顺序存储结构实现的栈。顺序栈的存储结构可以用C语言中的一维数组来表示。栈的顺序存储结构定义如下： #define MaxSize /* 线性表可能达到的最大长度 */ typedef struct /* 顺序栈类型定义 */ { Elemtype data[MaxSize]; int top; /* 指示栈顶位置 */ }SeqStack; 这里把存放栈中元素的数组和指向栈顶的变量都作为结构体类型SeqStack的分量来定义。鉴于C语言中数组的下标值约定从0开始，则当以C语言作描述语言时，数组的0下标端设为栈底。这样，空栈时，栈顶指针top为-1；入栈时，栈顶指针top加1；出栈时，栈顶指针top减1。 假设用一维数组sq表示一个栈，图14.2说明了这个顺序栈的几种状态。