《第5章数据结构.pptx》由会员分享，可在线阅读，更多相关《第5章数据结构.pptx（59页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1链栈用单链表表示25.2.1 线性表的基本线性表的基本概念概念5.2.2 线性表的存储与处理线性表的存储与处理5.2.3 栈的存储与处理栈的存储与处理5.2.4 队列的存储与队列的存储与处理处理5.2 线性表线性表5.1 基本概念基本概念5.3.1 树的基本树的基本概念概念5.3.2 二叉树的基本概念二叉树的基本概念5.3.3 二叉树的遍历二叉树的遍历5.3 树树5.4.1 图的图的概念概念5.4.2 图的图的遍历遍历5.4 图图3p 数据数据：所有能：所有能输入输入到计算机中并能被计算机程序到计算机中并能被计算机程序识别和处理识别和处理的符的符号集合。号集合。 数值数据：整数、实数等数值数
2、据：整数、实数等 非数值数据：图形、图象、声音、文字等非数值数据：图形、图象、声音、文字等 p 数据元素数据元素：数据的：数据的基本基本单位，在计算机程序中通常作为一个单位，在计算机程序中通常作为一个整体整体进行考虑和处理。进行考虑和处理。p 数据对象数据对象：数据对象是性质相同的数据元素构成的集合，是数据：数据对象是性质相同的数据元素构成的集合，是数据的一个子集。的一个子集。学号姓名性别出生日期班级20190001鹿鸣男1978/10/151班20190002王强男1972/09/141班20190003林淼淼女1575/02/092班数据元素数据项4p 数据结构数据结构：是一个二元组：是一
3、个二元组Data Structure=（D，S），其中），其中D是一个是一个数据元素的有限集合，数据元素的有限集合，S是是D上的关系的有限集合。按照视点的不同，上的关系的有限集合。按照视点的不同，数据结构分为逻辑结构和存储结构。数据结构分为逻辑结构和存储结构。p集合结构集合结构p线性结构线性结构p树结构树结构p图结构图结构 （a）集合 （b）线性结构 （c）树结构 （d）图结构图5-2 数据的逻辑结构51. 顺序存储结构：顺序存储结构：用一组用一组连续连续的存储单元的存储单元依次依次存储数据元素，存储数据元素，数据元素之间的逻辑关系由元数据元素之间的逻辑关系由元素的素的存储位置存储位置来表示。
4、来表示。2. 链接存储结构：链接存储结构：用一组用一组任意任意的存储单元存储数据元素，数的存储单元存储数据元素，数据元素之间的逻辑关系用据元素之间的逻辑关系用指针指针来表示来表示 。 图5-3 数据的顺序存储结构 图5-4 数据的链式存储结构p 线性表：线性表：它是由它是由n n（n0n0）个具有相同类型的数据元素组成的有限序）个具有相同类型的数据元素组成的有限序列，如图列，如图5-55-5所示。线性表的一般表示如下：所示。线性表的一般表示如下： L= L=（a a1 1,a,a2 2,a,ai i,a,ai+1i+1,a,an n）p n n：为线性表的长度。为线性表的长度。p L L: :
5、 表示线性表名称表示线性表名称p a ai i: : (1in)(1in)称为数据元素，称为数据元素，下角标下角标 i 表示该元素在线性表中的位表示该元素在线性表中的位置或置或序号序号。 图5-5 线性表结构示意图 7p1. 顺序存储结构及操作顺序存储结构及操作p线性表的顺序存储结构称为顺序表。线性表的顺序存储结构称为顺序表。p顺序表是用一段地址连续的存储单元依次存储线性表的数据元素。顺序表是用一段地址连续的存储单元依次存储线性表的数据元素。用数组存储顺序表，用用数组存储顺序表，用MaxSize表示数组的长度，用表示数组的长度，用length表示线性表示线性表的长度，顺序表的存储示意图如图表的
6、长度，顺序表的存储示意图如图5-6所示。所示。 图5-6 数组的长度与线性表的长度具有不同的含义意图 插入前：插入前：( (a a1 1, , , , a ai i-1-1, , a ai i, , , , a an n) )插入后：插入后：( (a a1 1, , , , a ai i-1-1, , x x , , a ai i, , , , a an n) )ai-1和和ai之间的逻辑关系发生了变化之间的逻辑关系发生了变化顺序存储要求存储位置反映逻辑关系顺序存储要求存储位置反映逻辑关系存储位置要反映这个变化存储位置要反映这个变化p1. 顺序存储结构及操作顺序存储结构及操作p顺序表的操作插入
7、 9p1. 顺序存储结构及操作顺序存储结构及操作p顺序表的操作插入 图5-7 将元素21插入位置3，顺序表前后状态的对比 表满：表满：length=MaxSize合理的插入位置：合理的插入位置：1ilength+1（i指的是元素的序号）指的是元素的序号）什么时候不能插入什么时候不能插入？注意边界条件注意边界条件p1. 顺序存储结构及操作顺序存储结构及操作p顺序表的操作插入 删除前：删除前：( (a a1 1, , , , a ai i-1-1, , a ai i ，a ai+1i+1, , , , a an n) )删除后：删除后：( (a a1 1, , , , a ai i-1-1, ,
8、a ai i, , , , a an n) )ai-1和和ai之间的逻辑关系发生了变化之间的逻辑关系发生了变化顺序存储要求存储位置反映逻辑关系顺序存储要求存储位置反映逻辑关系存储位置要反映这个变化存储位置要反映这个变化p1. 顺序存储结构及操作顺序存储结构及操作p顺序表的操作删除 12p1. 顺序存储结构及操作顺序存储结构及操作p顺序表的操作删除 图5-8 将位置3上元素21删除，顺序表前后状态的对比 13p2. 链式存储结构及操作链式存储结构及操作p线性表的链式存储结构称为链表。线性表的链式存储结构称为链表。p单链表是单链表是由若干结点构成的由若干结点构成的 data：存储数据元素存储数据元
9、素next：存储指向后继结点的地址存储指向后继结点的地址 data next单链表的结点结构：单链表的结点结构：数据域数据域指针域指针域0300030804000425 r0300 p0425 b0400 o 结点结点数据域数据域指针域指针域通常在单链表的第一个结点之前增加一个类型相同的结点，称为头结点。以通常在单链表的第一个结点之前增加一个类型相同的结点，称为头结点。以便空表和非空表处理统一便空表和非空表处理统一, ,如图如图5 5-10-10所示。所示。 单链表单链表通常单链表单链表通常按图按图5-95-9所示形所示形式表示式表示。 图5-9 线性表的单链表存储结构 图5-10 带头结点的
10、单链表存储结构 15p2. 链式存储结构及操作链式存储结构及操作p链表的操作插入 图5-11 在单链表中插入结点时指针的变化情况 16p2. 链式存储结构及操作链式存储结构及操作p链表的操作删除 图5-12 在单链表中删除结点时指针的变化情况 循环单链表在内存中的存储结构如图循环单链表在内存中的存储结构如图5-13所示。所示。 图5-13 带尾指针的循环链表 双向链表的每一个结点由本身的数据元素信息双向链表的每一个结点由本身的数据元素信息(data)、指向前驱结点的指针、指向前驱结点的指针域域(prior)和指向后继结点的指针域和指向后继结点的指针域(next)三部分组成，如图三部分组成，如图
11、5-14所示。所示。图5-14 循环双向链表存储示意图p栈：栈：限定仅在限定仅在表的一端表的一端进进行插入和删除操作的行插入和删除操作的线性线性表表。p允许插入和删除的一端称允许插入和删除的一端称为栈顶，另一端称为栈底。为栈顶，另一端称为栈底。p栈的操作特性：栈的操作特性：后进先出后进先出 图5-15 栈的逻辑结构示意图 20p1. 顺序存储结构及操作顺序存储结构及操作 图5-16 栈的操作示意图 21p2. 链式存储结构及操作链式存储结构及操作 图5-17 链栈示意图 p队列：队列：只允许只允许在一端插入在一端插入（又称为入队）（又称为入队）数据元素数据元素，而在而在另一端删除（又称为另一端
12、删除（又称为出队）出队）数据元素的线性表数据元素的线性表。p允许插入的一端称为队允许插入的一端称为队尾尾，允许删除的一端称为队允许删除的一端称为队头头。p队列的操作特性队列的操作特性-先进先出先进先出 图5-18 队列的示意图 23p1. 顺序存储结构及操作顺序存储结构及操作p设置队头、队尾两个指针p循环队列：将存储队列的数组头尾相接。图5-19 循环队列的操作示意图 24p循环队列的队空和队满的判定条件循环队列的队空和队满的判定条件图5-20 循环队列队空和队满的判定的示意图 25p2. 链式存储结构及操作链式存储结构及操作图5-21 链队列的示意图 26树：树：n n（n n00）个个结点
13、结点的有限的有限集合集合。当。当n n0 0时，称为空时，称为空树；任意一棵非空树满足以下条件树；任意一棵非空树满足以下条件：p 有且仅有一个特定的称为有且仅有一个特定的称为根根的结点的结点；p 当当n n1 1时，除根结点之外的其余结点被分成时，除根结点之外的其余结点被分成m m（m m00）个个互不相交互不相交的有限集合的有限集合T T1 1, ,T T2 2, , ,T Tm m，其中其中每个集合又是一棵树，并称为这个根结点的每个集合又是一棵树，并称为这个根结点的子树子树。树的定义是采用递归方法树的定义是采用递归方法(a) 一棵树结构一棵树结构 (b)一个非树结构一个非树结构 (c)一个
14、非树结构一个非树结构 1. 树树的定义的定义ACBGFEDHIACBGFDACBGFDEp 结点的度：结点的度：结点所拥有的子树的个数。结点所拥有的子树的个数。p 树的度：树的度：树中各结点度的最大值。树中各结点度的最大值。CGBDEFIHJA2. 2. 树的基本术语树的基本术语p 叶子结点：叶子结点：度为度为0的结点，也称为终端结点。的结点，也称为终端结点。p 分支结点：分支结点：度不为度不为0的结点，也称为非终端结点。的结点，也称为非终端结点。CGBDEFIHJA2. 2. 树的基本术语树的基本术语p 孩子、双亲：孩子、双亲：树中某结点子树的根结点称为这个结点的树中某结点子树的根结点称为这
15、个结点的孩子结点孩子结点，这，这个结点称为它孩子结点的个结点称为它孩子结点的双亲结点双亲结点；p 兄弟：兄弟：具有同一个双亲的孩子结点互称为兄弟。具有同一个双亲的孩子结点互称为兄弟。 2. 2. 树的基本术语树的基本术语CGBDEFIHJACGBDEFIHJAp 路径：路径：如果树的结点序列如果树的结点序列n1, n2, , nk有如下关系：结点有如下关系：结点ni是是ni+1的双亲的双亲（1=ik），则把，则把n1, n2, , nk称为一条由称为一条由n1至至nk的路径；的路径；p 路径上经过的边的个数称为路径上经过的边的个数称为路径长度路径长度。 2. 2. 树的基本术语树的基本术语祖先
16、、子孙：祖先、子孙：在树中，如果有一条路径从结点在树中，如果有一条路径从结点x到结点到结点y，则则x称为称为y的祖先，而的祖先，而y称为称为x的子孙。的子孙。2. 2. 树的基本术语树的基本术语CGBDEFIHJAp 结点所在层数：结点所在层数：根结点的层数为根结点的层数为1 1；对其余任何结点，若某结点在第；对其余任何结点，若某结点在第k k层，则其孩子层，则其孩子结点在第结点在第k+1k+1层。层。p 树的深度：树的深度：树中所有结点的最大层数，也称树中所有结点的最大层数，也称高度高度。1 1层层2层层4 4层层3层层高度高度4CGBDEFIHJA2. 2. 树的基本术语树的基本术语CBD
17、EFIHJA71234559810层序编号：层序编号：将树中结点按照从上层到下层、同层从左到右的次序依次给将树中结点按照从上层到下层、同层从左到右的次序依次给他们编以从他们编以从1 1开始的连续自然数。开始的连续自然数。2. 2. 树的基本术语树的基本术语G有序树、无序树：有序树、无序树：如果一棵树中结点的各子树从左到右是有次序的，称如果一棵树中结点的各子树从左到右是有次序的，称这棵树为有序树；反之，称为无序树。这棵树为有序树；反之，称为无序树。数据结构中讨论的一般都是有序树数据结构中讨论的一般都是有序树 ACBGFEDACBGFED2. 2. 树的基本术语树的基本术语森林：森林：m (m0)
18、棵互不相交的树的集合。棵互不相交的树的集合。 2. 2. 树的基本术语树的基本术语CGBDEFIHJA37二叉树二叉树是是n(n0)个结点的有限集合，该集合或者为空个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树相交的、分别称为根结点的左子树和右子树的二叉树组成。组成。二叉树的定义是采用递归方法二叉树的定义是采用递归方法1. 1. 二叉树的二叉树的定义定义 每个结点最多有两棵子树；每个结点最多有两棵子树； 二叉树是有序的，其次序不二叉树是有序的，其次序不能任意颠倒能任意颠倒
19、。 ABAB 二叉树的特点二叉树的特点空二叉树空二叉树只有一个根结点只有一个根结点左子树左子树根结点只有左子树根结点只有左子树右子树右子树根结点只有右子树根结点只有右子树左子树左子树右子树右子树根结点同时有左右子树根结点同时有左右子树 二叉树的基本形态二叉树的基本形态在在一棵二叉树中，如果所一棵二叉树中，如果所有分支结点都存在左子树有分支结点都存在左子树和右子树，并且所有叶子和右子树，并且所有叶子都在都在同一层上。同一层上。满二叉树的特点满二叉树的特点： 1. 叶子只能出现在最下一层；叶子只能出现在最下一层；2. 只有度为只有度为0和度为和度为2的结点。的结点。A15234578910BCDE
20、FGHIJKLM NO1112 13 14 15 特殊的二叉树特殊的二叉树-满满二叉树二叉树对对一棵具有一棵具有n个结点的二叉树按个结点的二叉树按层序编号，如果编号为层序编号，如果编号为i（1in）的结点与同样深度的满二叉的结点与同样深度的满二叉树中编号为树中编号为i的结点在二叉树中的结点在二叉树中的位置完全相同。的位置完全相同。A15234578910BCDEFGHIJKLM NO1112 13 14 15A15234578910BCDEFGHIJ 特殊的二叉树特殊的二叉树-完全完全二叉树二叉树1. 叶子结点只能出现在最下两层叶子结点只能出现在最下两层且最下层的叶子结点都集中在二且最下层的叶
21、子结点都集中在二叉树的左面；叉树的左面；2. 完全二叉树中如果有度为完全二叉树中如果有度为1的的结点，只可能有一个，且该结点结点，只可能有一个，且该结点只有左孩子。只有左孩子。3. 深度为深度为k的完全二叉树在的完全二叉树在k-1层层上一定是满二叉树。上一定是满二叉树。4. 在同样结点个数的二叉树中，在同样结点个数的二叉树中，完全二叉树的深度最小。完全二叉树的深度最小。 特点：特点：A15234578910BCDEFGHIJ 特殊的二叉树特殊的二叉树-完全完全二叉树二叉树性质性质5-1 二叉树的第二叉树的第i层上最多有层上最多有2i- -1个结点（个结点（i1）。）。 2.2.二叉树的基本性质
22、二叉树的基本性质性质性质5-2 一棵深度为一棵深度为k的二叉树中，最多有的二叉树中，最多有2k- -1个结点，最少有个结点，最少有k个结点。个结点。 性质性质5-3 在一棵二叉树中，如果叶子结点数为在一棵二叉树中，如果叶子结点数为n0，度为度为2的结点数为的结点数为n2，则有则有: n0n21。 性质性质5-4 具有具有n个结点的完全二叉树的深度为个结点的完全二叉树的深度为 。 ) 1(log2n 二叉树的遍历是指从根结点出发，按照某种二叉树的遍历是指从根结点出发，按照某种次序次序访问二叉树中的所有结点，使得每个结点被访问一访问二叉树中的所有结点，使得每个结点被访问一次且仅被次且仅被访问访问一
23、次。一次。二叉树遍历操作的结果？二叉树遍历操作的结果？非线性结构线性化非线性结构线性化抽象操作，抽象操作，可以是对结点进行的各种可以是对结点进行的各种处理，这里处理，这里简化为输出结点的数据。简化为输出结点的数据。前序遍历前序遍历中序遍历中序遍历后序遍历后序遍历层序遍历层序遍历 若若二叉树为空，则空操作返回二叉树为空，则空操作返回；否则：；否则：访问根结点；访问根结点；前序前序遍历遍历根根结点的左子树；结点的左子树；前序前序遍历遍历根根结点的右子树。结点的右子树。前序遍历序列：前序遍历序列：A B D G C E FABCDEFG前前序（根）序（根）遍历遍历若若二叉树为空，则空操作返回；二叉树
24、为空，则空操作返回；否则：否则：中序中序遍历遍历根根结点的左子树；结点的左子树；访问根结点；访问根结点；中序中序遍历遍历根根结点的右子树。结点的右子树。 中序遍历序列：中序遍历序列：D G B A E C FABCDEFG中序中序（根）（根）遍历遍历若二叉树为空，则空操作返回；若二叉树为空，则空操作返回；否则：否则：后序后序遍历遍历根根结点的左子树；结点的左子树；后序后序遍历遍历根根结点的右子树。结点的右子树。访问根结点；访问根结点；后序遍历序列：后序遍历序列：G D B E F C AABCDEFG后序后序（根）（根）遍历遍历二叉树二叉树的层次遍历是指从二的层次遍历是指从二叉树的第一层（即根
25、结点）叉树的第一层（即根结点）开始，开始，从上至下从上至下逐层遍历，逐层遍历，在同一层中，则按在同一层中，则按从左到右从左到右的顺序对结点逐个访问。的顺序对结点逐个访问。 层序遍历序列：层序遍历序列：A B C D E F GABCDEFG层序遍历层序遍历图是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为： Graph = ( V , E ) V = x| x某个数据对象 E = | P(u , v)(u,vV) V是具有相同特性的数据元素的集合，V中的数据元素通常称为顶点。E是两个顶点之间关系的集合。P(u , v)表示u和v之间有特定的关联属性。1.1.图的定义图的定义如果图的任意
26、两个顶点之间的边都是无向边，则称该图为无向图。若顶点vi和vj之间的边没有方向，则称这条边为无向边，表示为(vi,vj)。若从顶点vi到vj的边有方向，则称这条边为有向边，表示为。 如果图的任意两个顶点之间的边都是有向边，则称该图为有向图。无向完全图：在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。有向完全图：在有向图中，如果任意两个顶点之间都存在方向相反的两条弧，则称该图为有向完全图。 V0V1V2V0V1V2V31.1.图的基本术语图的基本术语稀疏图：称边数很少的图为稀疏图；稠密图：称边数很多的图为稠密图。顶点的度：在无向图中，顶点v的度是指依附于该顶点的边数，通常记为TD
27、 (v)。顶点的入度：在有向图中，顶点v的入度是指以该顶点为弧头的弧的数目，记为ID (v)；顶点的出度：在有向图中，顶点v的出度是指以该顶点为弧尾的弧的数目，记为OD (v)。1.1.图的基本术语图的基本术语权：是指对边赋予的有意义的数值量。网：边上带权的图，也称网图。V0V1V2V327851.1.图的基本术语图的基本术语路径：在无向图G=(V, E)中，从顶点vp到顶点vq之间的路径是一个顶点序列(vp=vi0,vi1,vi2, , vim=vq)，其中，(vij-1,vij)E（1jm）。若G是有向图，则路径也是有方向的，顶点序列满足E。一般情况下，图中的路径不惟一V0 到V3的路径：
28、 V0 V3 V0 V1 V2 V3 V0 V1 V4V2 V3V0V1V2V3V41.1.图的基本术语图的基本术语路径长度：路径长度：非带权图路径上边的个数带权图路径上各边的权之和V0 V3：长度为1V0 V1 V2 V3 ：长度为3V0 V1 V4V2 V3 ：长度为4V0V1V2V3V41.1.图的基本术语图的基本术语路径长度：路径长度：非带权图路径上边的个数带权图路径上各边的权之和V0 V3：长度为8V0 V1 V2 V3 ：长度为7V0 V1 V4 V2 V3 ：长度为15V0V1V2V3V42553281.1.图的基本术语图的基本术语基本思想 ： 访问顶点v； 从v的未被访问的邻接点中选取一个顶点w，从w出发进行深度优先遍历； 重复上述两步，直至图中所有和v有路径相通的顶点都被访问到。 1 1. .深度优先遍历深度优先遍历基本思想： 访问顶点v； 依次访问v的各个未被访问的邻接点v1, v2, , vk； 分别从v1，v2，vk出发依次访问它们未被访问的邻接点，并使“先被访问顶点的邻接点”先于“后被访问顶点的邻接点”被访问。直至图中所有与顶点v有路径相通的顶点都被访问到。2 2. .广度优先遍历广度优先遍历