《《C语言程序设计与数据结构》-刘信杰-电子教案 C语言程序设计与数据结构 课件第14章》由会员分享，可在线阅读，更多相关《《C语言程序设计与数据结构》-刘信杰-电子教案 C语言程序设计与数据结构 课件第14章（42页珍藏版）》请在金锄头文库上搜索。
1、C语言程序设计与数据结构,第十四章 栈、队列与树,C语言程序设计与数据结构,总体要求： 掌握栈、队列和树的概念、有关术语； 掌握栈、队列的基本操作； 掌握树的定义与二叉树的性质； 掌握二叉树的存储结构及二叉树的先序、中序、后序遍历算法； 学会栈、队列和树的灵活应用。 学习重点： 栈和队列的基本操作； 二叉树的存储和遍历。六种位运算的综合使用,C语言程序设计与数据结构,14.1 栈 14.2 队列 14.3 树,C语言程序设计与数据结构,14.1 栈 14.1.1什么是栈 14.1.2顺序栈的实现,C语言程序设计与数据结构,栈和队列是在软件设计中常用的两种数据结构，它们的逻辑结构和线性表相同。其
2、特点在于运算受到了限制：栈按“后进先出”的规则进行操作，队按“先进先出”的规则进行操作，故称操作受限制的线性表。 树型结构是一种非常重要的非线性结构，它是具有分支关系的层次结构，可以用来描述较复杂的数据关系。树型结构应用非常广泛，特别是在数据处理方面，如在文件系统、编译系统、目录组织等方面，显得更加突出。,C语言程序设计与数据结构,14.1.1 什么是栈 栈（Stack）是限定仅在表的一端进行插入和删除操作的线性表。通常将表中允许插入、删除操作的这一端称为栈顶（top），因此栈顶的当前位置是动态变化的，它由一个称为栈顶指针的位置指示器指示。同时表的另一端被称为栈底（bottom）。栈顶的第一个
3、元素叫做栈顶元素。不含任何数据元素的栈称为空栈。栈的插入操作被形象的称为进栈或入栈，删除操作称为出栈或退栈。 假设有栈S=(a1,a2,an)，如图14.1(a)所示，元素是以a1,a2,an的顺序进栈，因此栈底元素是a1，栈顶元素是an。退栈的第一个元素应为栈顶元素an。 图14.1(a) 栈,C语言程序设计与数据结构,下面举例说明栈的结构特征。 假设有一个很窄的死胡同，胡同里能容纳若干人，但每次只能容许一个人进出。现有五个人，分别编号为，按编号的顺序进入胡同，如图14.1(b)所示。若要出来，必须等退出后才有可能。若要退出，则必须等到依次都退出后才行。这里，人进出胡同的原则是后进去的先出来
4、。换句话说，先进去的后出来。 栈可以比作这里的死胡同，栈顶相当于胡同口，栈底相当于胡同的另一端，进、出胡同可看作栈的插入、删除运算。插入、删除都在栈顶进行，进出都经过胡同口。这表明栈的原则是后进先出。因此，栈又称为后进先出(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语言程序设
5、计与数据结构,14.1.2 顺序栈的实现 栈作为一种特殊的线性表，在计算机中也主要有两种基本的存储结构：顺序存储结构和链式存储结构。我们称顺序存储的栈为顺序栈，链式存储的栈为链栈。 顺序栈是用顺序存储结构实现的栈。顺序栈的存储结构可以用C语言中的一维数组来表示。栈的顺序存储结构定义如下： #define MaxSize /* 线性表可能达到的最大长度 */ typedef struct /* 顺序栈类型定义 */ Elemtype dataMaxSize; int top; /* 指示栈顶位置 */ SeqStack; 这里把存放栈中元素的数组和指向栈顶的变量都作为结构体类型SeqStack的
6、分量来定义。鉴于C语言中数组的下标值约定从0开始，则当以C语言作描述语言时，数组的0下标端设为栈底。这样，空栈时，栈顶指针top为-1；入栈时，栈顶指针top加1；出栈时，栈顶指针top减1。,C语言程序设计与数据结构,假设用一维数组sq表示一个栈，图14.2说明了这个顺序栈的几种状态。 图14.2栈顶指针和栈中元素之间的关系 图14.2(a)是空栈；图14.2 (b)是只有一个元素时的状态；图14.2 (c)是A、B、C、D、E、F这六个元素依次进入栈之后的状态；图14.2(d)是删除E、F两个元素后的状态，此时栈中还有四个元素，或许刚出栈的元素E、F仍然在原先的单元存储着，但top指针已经
7、指向了新的栈顶，则元素E、F已不在栈中了，通过这个示意图要深刻理解栈顶指针的作用。 由于栈是一个动态结构，而数组是静态结构，因此会出现所谓的溢出问题。当栈中已经有MaxSize个元素时，如果再进行进栈操作，则会产生溢出，通常称为上溢(overflow)；而对空栈进行出栈操作时，也会产生溢出，通常称为下溢(underflow)。为了避免溢出，在对栈进行进栈操作和出栈操作前，应分别检查栈是否已满或者是否已空。,C语言程序设计与数据结构,顺序栈的基本操作的实现如下： （1）初始化 顺序栈的初始化即构造一个空的顺序栈。为栈结构申请空间，并将栈顶指针赋值为-1。具体算法描述如下： 【算法14.1】构造一
8、个空栈 SeqStack *Init_SeqStack( ) SeqStack *s; s = (SeqStack *) malloc ( sizeof (SeqStack ) ); if (s = = NULL) printf ( “ Out of space!n“ ); else s-top=-1; return (s); （2）判栈空 判栈空运算，即判断一个栈是否为空栈，为空时，返回TRUE，否则返回FALSE。具体算法描述如下： 【算法14.2】 int Empty_SeqStack(SeqStack *s) /* 判断栈s是否为空 */ if (s-top = =-1) return
9、 (TRUE); else return (FALSE); ,C语言程序设计与数据结构,（3）进栈 入栈运算，即往栈中插入(或称为压入或推入)一个值为x的新元素。 完成这一操作的基本步骤： (1) 首先判断栈是否已满； (2) 当栈不满时，先修改栈顶指针，将其值加1； (3) 然后把元素x放入栈顶指针指向的位置中。 具体算法描述如下： 【算法14.3】 int Push_SeqStack ( SeqStack *s, Elemtype x ) /* 向栈s中压入一个新元素x为栈顶元素，并返回成功与否的标志 */ if ( s-top = = MaxSize-1) printf ( “Overf
10、low! n“ ); return ( FALSE ); /* 栈满不能入栈，返回FALSE */ else s - top +; s - datas-top = x ; return ( TRUE ); /* 操作成功，返回TRUE */ ,C语言程序设计与数据结构,（4）出栈 出栈运算，即从栈中删除(或称为弹出)一个元素。当栈不空时，可通过将栈顶指针减1，达到元素删除的目的。这里需要说明的是，所谓的删除，只是将栈顶位置下移一位，这样原来的栈顶元素就认为不包括在栈中了。实际上，该元素还存在于原来的存储单元中，只是当新的元素入栈时，会将其覆盖。具体算法描述如下： 【算法14.4】 int Po
11、p_SeqStack ( SeqStack *s , Elemtype *x ) /* 若栈s不为空，则删除栈顶元素，并返回栈顶元素值和删除成功与否的标志 */ if (s-top = =-1) printf ( “Underflow!n“ ); return (FALSE); /* 栈空不能出栈，返回FALSE */ else *x= s-datas-top; s-top - - ; /*修改栈顶指针*/ return (TRUE ); / * 栈顶元素存入*x，返回TRUE */ ,C语言程序设计与数据结构,（5）取栈顶元素 取栈顶元素运算，即当栈不为空时，将栈顶元素取出，而栈本身没有发生
12、任何变化。具体算法描述如下： 【算法14.5】 Elemtype Top_SeqStack ( SeqStack *s ) /* 当栈s不为空时，求栈顶元素 */ if s-top != = -1 return ( s-datas-top ); else return ( SPECIAL); /* 栈为空，返回一个栈中没有的特殊值 */ 说明： (1) 对于顺序栈，入栈时，应首先判栈是否已满，栈满的条件为s-top = = MaxSize-1，栈满时，不能入栈；否则出现空间溢出，引起上溢错误。 (2) 出栈和读栈顶元素操作，应先判栈是否为空，为空时不能操作，否则产生下溢错误。通常栈空时常作为一
13、种控制转移的条件。,C语言程序设计与数据结构,14.2 队列 14.2.1 什么是队列 14.2.2 队列的基本操作,C语言程序设计与数据结构,14.2.1 什么是队列 队列（Queue）是另一种操作受限的线性表，它是只允许在表的一端进行插入，而在另一端进行删除的线性表。能进行插入的一端称为队列的尾（rear），能进行删除的一端称为队列的头（front）。先进入队列的元素称为队列的头元素（队列的头），最后进入队列中的元素称为队列的尾元素（队列的尾）。队列称为先进先出的线性表（First In First Out），简称FIFO表。 例如，一个有六个元素的队列q = (a1、a2、a3、a4、a
14、5、a6)，那么a1 就是队头元素，a6则是队尾元素。入队的顺序依次为a1、a2、a3、a4、a5、a6，那么出队时的顺序将依然是a1、a2、a3、a4、a5、a6，也就是说，a1离开队列后，a2才能退出队列，a1、a2、a3、a4、a5都离开后，a6才能退出队列。队列q的示意图如图14.3所示。 图14.3 队列q的示意图,C语言程序设计与数据结构,14.2.2 队列的基本操作 队列的基本操作： （1）Init_Queue(q) （2）IsEmpty_ Queue(q) （3）En_Queue(q,x) （4）Out_ Queue(q,x) （5）GetHead_ Queue (q,x),C
15、语言程序设计与数据结构,与栈类似，队列通常有两种实现方法，即顺序队列实现和链式队列实现。队列的顺序存储结构称为顺序队，它由一个一维数组(用于存储队列中元素)及两个分别指示队头和队尾的变量组成，这两个变量分别称为队头指针和队尾指针(注意它们并非指针型变量)。因为在操作过程中，队头位置和队尾位置经常变化，所以设置了头、尾两个指针。通常约定队尾指针指示队尾元素在一维数组中的当前位置，队头指针指示队头元素在一维数组中的当前位置的前一个位置(这样设置是为了某些操作的方便，并不是唯一的方法)。由此可见顺序队列实际上就是运算受限制的顺序表。顺序队列的类型定义如下： #define MaxSize 线性表可能
16、达到的最大长度 typedef struct Elemtype dataMaxSize; /* 队员的存储空间 */ int front,rear; /* 队头，队尾指针 */ SeqQueue; 定义一个指向队的指针变量为 SeqQueue *sq,C语言程序设计与数据结构,队列的数据区为：sq-data0sq-dataMaxSize -1。 每当插入新的队尾元素时，在不考虑溢出的情况下，队尾指针加1，指向新位置后，元素入队。操作如下： sq-rear+; sq-datasq-rear=x; 每当删除队头元素时，在不考虑队空的情况下，队头指针加1，表明队头元素出队。操作如下： sq-front+; x=sq-datasq-front; /* 原队头元素送x中
