《C语言程序设计与数据结构》课件第14章.ppt
《《C语言程序设计与数据结构》课件第14章.ppt》由会员分享,可在线阅读,更多相关《《C语言程序设计与数据结构》课件第14章.ppt(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-fron
17、t+; x=sq-datasq-front; /* 原队头元素送x中 */ 整个队列的数据区为sq-data0至sq-dataMaxSize -1。队中元素的个数m为队尾指针sq-rear减去队头指针sq-front的值。队满时,m= MaxSize;队空时,m=0。 置空队则为sq-front=sq-rear=-1; 如图14.4所示,是一个队列的操作示意图,它描述了队列的变化过程。 图14.4 队列操作示意图,C语言程序设计与数据结构,从图14.4中可以看出,在这样的顺序队列中,入队操作就是要在队尾增加元素,并将尾指针rear后移。出队时,则是头指针front后移。进行了一定数量的入队和出
18、队后,会使整个队列整体向后移动。这样就可能会出现图14.4(d)中的情况:队尾指针rear已指到数组的最后一个元素,即rear=MaxSize-1,此时若再执行入队操作,便会出现溢出。然而,由于在此操作之前可能也执行了若干次出队操作,因而数组的前面部分可能还有闲置的元素空间,即这种溢出并非是真的没有可用的存储空间,故称这种溢出现象为假溢出。显然,必须要解决假溢出问题,才能保证队列结构的正确应用。,C语言程序设计与数据结构,采用循环结构就可以解决假溢出的问题,具体方法是:将数组元素data0看作是dataMaxSize-1的下一个存储位置,也就是说,将数组看作是一个循环结构。这样,当执行入队或出
19、队操作时,如果原指针rear或front的值为MaxSize-1,即已经指向了数组的最后一个元素时,则执行入队或出队操作后,相应指针的值就要变为0。这样就可以使被删除的结点在被使用,称这种形式的队列为循环队列,如图14.5所示。 图14.5 循环队列示意图,C语言程序设计与数据结构,循环队列操作如图14.6所示。 图14.6 循环队列操作示意图,C语言程序设计与数据结构,队列的链式存储结构就是用一个线性链表来表示队列,队列中的每个元素对应链表中的一个结点,这样的队列简称链式队列。 在采用链式队列存储时,首先要确定链表的形式及队尾的位置。其讨论如下: (1) 一个链式队列显然需要两个分别指示队头
20、和队尾的指针(分别称为头指针和尾指针)才能唯一确定。由于队列的入队和出队操作分别是在队尾和队头进行,故将链表头作为队头、链表表尾作为队尾比较合适。出队时,只需要进行删除表头的操作,而入队时所要做的操作是在表尾添加结点。 (2) 和线性表的单链表一样,为了操作方便起见,也给链队列添加一个头结点,并令头指针指向头结点。 链式队列的结构如图14.7所示。 图14.7 链式队列示意图,C语言程序设计与数据结构,链式队列的结点类型描述如下: typedef struct queuenode /* 结点结构 */ Elemtype data; struct queuenode *next; QueueNo
21、de; 为了强调队头和队尾是队列的属性,将队列封装,引入链式队列类型: typedef struct QueueNode *front, *rear; /* 队头和队尾指针 */ LinkQueue; 按这种思想建立的带头结点的链式队列如图14.8所示。 图14.8 头尾指针封装在一起的链式队列,C语言程序设计与数据结构,14.3 树 14. 3 .1 什么是树 14.3.2 二叉树的概念及性质 14.3.3 二叉树的存储及遍历,C语言程序设计与数据结构,14. 3 .1 什么是树 1.树的定义 树(Tree)是n(n0)个结点的有限集合。当n0时,称这棵树为空树;当n0时,该集合需满足以下条
22、件: (1)有且仅有一个称为根(root)的结点,它没有直接前驱,但有零个或者多个直接后继。 (2)其余n-1个结点可以被划分成m(m0)个互不相交的有限集T1,T2,Tm,其中每一个集合Ti(1im)又是一棵树,称为根root的子树。每棵子树的根结点有且仅有一个直接前驱,但有零个或者多个直接后继。 可见树的定义是一个递归定义,它反映了树的固有特性,因为一棵树是由根和它的子树构成,而子树又由子树的根和更小的子树构成。树的表示形式如图14.9所示。 图14.9 树的一般形式,C语言程序设计与数据结构,2.树的常用术语 结点:包含一个数据元素及若干指向其他结点的分支信息。 结点的度:一个结点的子树
23、个数。图14.9中,A的度为3,B的度为1。 树的度:树中结点的最大度。图14.9中,树的度为3。 终端结点(叶子结点):度为0的结点,即无后继的结点。 分支结点:度不为0的结点,也称非终端结点。 孩子结点:一个结点的直接后继结点。 双亲结点:一个结点的直接前驱结点称为该结点的双亲结点。 结点的层次:根为第一层,根的直接后继所在的层为第二层,以此类推。 树的深(高)度:树中结点的最大层次称为树的深度(或高度)。 兄弟结点:同一双亲结点的孩子结点之间互称兄弟结点。 祖先结点:一个结点的祖先是从根到该结点所经分支上的所有结点。 子孙结点:以某结点为根的子树中的任一结点都称为该结点的子孙结点。 有序
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- C语言程序设计与数据结构 语言程序设计 数据结构 课件 14
链接地址:https://www.31doc.com/p-2152620.html