数据结构与算法.ppt课件

1、公共根底知识部分之公共根底知识部分之第一章第一章 数据构造与算法数据构造与算法1.1 算法1.2 数据构造的根本概念1.3 线性表及其顺序存储构造1.4 栈和队列1.5 线性链表1.6 树与二叉树1.7 查找技术1.8 排序技术1.1.1 1.1.1 算法的根本概念算法的根本概念 所谓算法是指解题方案的准确而完好的描画。所谓算法是指解题方案的准确而完好的描画。1.1 1.1 算法算法 1 1、算法的根本特征、算法的根本特征 可行性：算法原那么上可以准确地执行，甚至人们只可行性：算法原那么上可以准确地执行，甚至人们只用笔和纸做有限次运算即可完成。用笔和纸做有限次运算即可完成。 确定性：算法的每一

2、步都必需有确切的定义确定性：算法的每一步都必需有确切的定义 有穷性：一个算法必需在执行有穷步后终了，即算法有穷性：一个算法必需在执行有穷步后终了，即算法必需可以终止必需可以终止 拥有足够的情报：我们要使算法有效就必需拥有足够拥有足够的情报：我们要使算法有效就必需拥有足够的情报的情报2 2、算法的根本要素、算法的根本要素 数据对象的运算和操作数据对象的运算和操作A.A.算术运算算术运算+ +、- -、* *、/ /B.B.逻辑运算逻辑运算& &、|、! !C.C.关系运算关系运算 、 算法的控制构造算法的控制构造一个算法普通都可以用顺序、选择、循环三种根本控一个算法普通都可以用顺

3、序、选择、循环三种根本控制构造组合而成。制构造组合而成。3 3、算法设计根本方法、算法设计根本方法列举法：指针对待处理的问题，列举一切能够的情况，列举法：指针对待处理的问题，列举一切能够的情况，并用问题中给定的条件来检验。并用问题中给定的条件来检验。归纳法：特殊归纳法：特殊普通的笼统过程普通的笼统过程递推：从知初始条件出发，逐次推出所要求的各中间递推：从知初始条件出发，逐次推出所要求的各中间构造和最后结果构造和最后结果递归：将复杂的问题逐层分解，最后归结为一个简单递归：将复杂的问题逐层分解，最后归结为一个简单的问题，再沿原分解的逆过程逐渐进展综合。分为直的问题，再沿原分解的逆过程逐渐进展综合。

4、分为直接递归和间接递归接递归和间接递归减半递推技术：把规模较大较复杂的问题，分成几个减半递推技术：把规模较大较复杂的问题，分成几个规模较小较简单的问题规模较小较简单的问题回溯法：经过对问题的分析，找出一个处理问题的线回溯法：经过对问题的分析，找出一个处理问题的线索，多次试探，假设胜利，那么得出解，假设失败，索，多次试探，假设胜利，那么得出解，假设失败，那么回退，换别的道路再进展试探那么回退，换别的道路再进展试探1.1.2 1.1.2 算法复杂度算法复杂度算法的复杂度主要包括时间复杂度和空间复杂度。两者算法的复杂度主要包括时间复杂度和空间复杂度。两者之间没有必然的联络。之间没有必然的联络。1 1

5、、算法的时间复杂度、算法的时间复杂度 指执行算法所需求的计算任务量。指执行算法所需求的计算任务量。 任务量可以用算法在执行过程中所需根本运算的执任务量可以用算法在执行过程中所需根本运算的执行次数来度量。其中根本运算次数是问题规模的函数，行次数来度量。其中根本运算次数是问题规模的函数，即即 算法的任务量算法的任务量=f(n)=f(n)。 平均性态平均性态 最坏情况复杂性最坏情况复杂性留意留意: :算法程序执行的详细时间受运用计算机、程序设算法程序执行的详细时间受运用计算机、程序设计言语以及算法实现过程中的许多细节的影响。而算法计言语以及算法实现过程中的许多细节的影响。而算法的时间复杂度与此无关的

6、时间复杂度与此无关2 2、算法的空间复杂度、算法的空间复杂度 指执行这个算法所需求的内存空间，包含：指执行这个算法所需求的内存空间，包含： 算法程序所占的空间算法程序所占的空间 输入的初始数据所占的空间输入的初始数据所占的空间 算法执行过程中所需求的额外空间算法执行过程中所需求的额外空间 1.2 1.2 数据构造的根本概念数据构造的根本概念 数据构造作为计算机的一门学科，主要研讨以下三个方面的数据构造作为计算机的一门学科，主要研讨以下三个方面的问题：问题： 1 1数据的逻辑构造数据的逻辑构造 2 2数据的存储构造数据的存储构造( (物理构造物理构造) ) 3 3对各种数据构造进展的运算对各种数

7、据构造进展的运算数据构造学科的研讨目的：提高数据处置的效率。主要包括数据构造学科的研讨目的：提高数据处置的效率。主要包括1 1、数据的处置速度、数据的处置速度2 2、尽量节省在数据处置过程中所占用的计算机存储空间、尽量节省在数据处置过程中所占用的计算机存储空间 1.2.1 1.2.1 数据构造的定义数据构造的定义 数据处置：是指对数据集合中的各元素以各种数据处置：是指对数据集合中的各元素以各种方式进展运算。包括插入、删除、查找、更改等运方式进展运算。包括插入、删除、查找、更改等运算，也包括对数据元素进展分析。算，也包括对数据元素进展分析。 数据元素：在数据处置领域中，每一个需求处数据元素：在数

8、据处置领域中，每一个需求处置的对象都可以笼统为数据元素。置的对象都可以笼统为数据元素。 数据构造：是指反映数据元素之间关系的数据数据构造：是指反映数据元素之间关系的数据元素集合的表示。数据元素之间的任何关系都可以元素集合的表示。数据元素之间的任何关系都可以用前后件关系来描画。用前后件关系来描画。1 1、数据的逻辑构造、数据的逻辑构造 所谓逻辑构造实践上就是指数据元素之间的前后件所谓逻辑构造实践上就是指数据元素之间的前后件关系。其中前后件关系是指它们的逻辑关系，而与他关系。其中前后件关系是指它们的逻辑关系，而与他们在计算机中的存储位置无关。它包含两个要素：们在计算机中的存储位置无关。它包含两个要

9、素：数据元素的集合，通常记为数据元素的集合，通常记为D D；数据元素之间的关系前后件关系，通常记为数据元素之间的关系前后件关系，通常记为R R。方式表示如下：方式表示如下： B=B=D D，R R 其中其中B B表示数据构造表示数据构造 2 2、数据的存储构造、数据的存储构造 数据的逻辑构造在计算机存储空间中的存放方数据的逻辑构造在计算机存储空间中的存放方式称为数据的存储构造即数据的物理构造。式称为数据的存储构造即数据的物理构造。常用的存储构造有顺序、链接、索引等存储构造。常用的存储构造有顺序、链接、索引等存储构造。 1.2.2 1.2.2 数据构造的图形表示数据构造的图形表示 图形表示方法：

10、对于数据集合图形表示方法：对于数据集合D D中的每一个数据中的每一个数据元素用中间标有元素值的方框表示，普通称为数据元素用中间标有元素值的方框表示，普通称为数据结点，简称结点，对关系结点，简称结点，对关系R R中每一个二元组，用一条中每一个二元组，用一条有向线段从前件指向后件结点，以表示数据之间的有向线段从前件指向后件结点，以表示数据之间的前后件关系。前后件关系。 春春夏夏冬冬秋秋父亲父亲儿子儿子女儿女儿图图1.2 1.2 一年四季数一年四季数据构造的图形表示据构造的图形表示图图1.3 1.3 家庭成员辈分关系家庭成员辈分关系的数据构造的图形表示的数据构造的图形表示例例1.2 1.2 用图形表

11、示数据构造用图形表示数据构造B=(D,R),B=(D,R),其中：其中： D=di|1=i=6=d1,d2,d3,d4,d5,d6D=di|1=i=0)，表中的每一个数据元素，除了第一个外，有且只需一个前件，除了，表中的每一个数据元素，除了第一个外，有且只需一个前件，除了最后一个外，有且只需一个后件。最后一个外，有且只需一个后件。 1.3.2 线性表的顺序存储构造线性表的顺序存储构造 线性表的顺序存储构造有以下两个根本特点：线性表的顺序存储构造有以下两个根本特点： 1线性表中一切元素所占的存储空间是延续的；线性表中一切元素所占的存储空间是延续的； 2 线 性 表 中 各 数 据 元 素 在 存

12、 储 空 间 中 是 按 逻 辑 顺 序 依 线 性 表 中 各 数 据 元 素 在 存 储 空 间 中 是 按 逻 辑 顺 序 依 次存放的。次存放的。逻辑上相邻的结点，物理位置上也相邻逻辑上相邻的结点，物理位置上也相邻 在程序设计言语中，通常定义一个一维数组来表示线性表的顺序存储空间，在程序设计言语中，通常定义一个一维数组来表示线性表的顺序存储空间，该一维数组的长度通常要定义得比线性表的实践长度大一些，以便对线性表该一维数组的长度通常要定义得比线性表的实践长度大一些，以便对线性表进展各种运算，特别是插入运算。进展各种运算，特别是插入运算。 线性表的主要操作有：线性表的主要操作有： 1插入、

13、插入、2删除、删除、3查找、查找、4排序、排序、5分解、分解、6合合并、并、7复制、复制、8逆转。逆转。 元素元素anan.元素元素aiai.元素元素a2a2元素元素a1a1bb+mb+(i-1)*m b+(maxlen-1)*m存储地址存储地址内存形状内存形状Loc(元素元素i)=b +i-1)*m顺序存储构造表示图顺序存储构造表示图(顺序表顺序表)：首地址首地址起始地址起始地址基地址基地址每个元素所占用每个元素所占用的存储单元个数的存储单元个数1.4 1.4 栈和队列栈和队列 1.4.1 栈及其根本运算栈及其根本运算 1、栈、栈stack的定义的定义栈是限定在一端进展插入和删除的线性表。栈

14、是限定在一端进展插入和删除的线性表。性质：性质：a.按照按照“先进后出先进后出FILO first in last out)或或“后进先出后进先出LIFOlast in first out)的原那么组织数据。的原那么组织数据。b.通常用指针通常用指针top来指示栈顶的位置，用指针来指示栈顶的位置，用指针bottom指向栈底。指向栈底。c.当表中没有元素时称栈为空栈当表中没有元素时称栈为空栈d.栈具有记忆功能栈具有记忆功能e.往栈中插入一个元素称为入栈运算，从栈中删除一个元素即删除栈顶元往栈中插入一个元素称为入栈运算，从栈中删除一个元素即删除栈顶元素称为退栈运算。素称为退栈运算。Top栈顶指针反

15、映了栈中元素的变化栈顶指针反映了栈中元素的变化 2、栈的顺序存储及其运算、栈的顺序存储及其运算 在程序设计言语中，普通用一维数组在程序设计言语中，普通用一维数组S(1:m)作为栈的顺序作为栈的顺序存储空间，其中存储空间，其中m为栈的最大容量。为栈的最大容量。 在在S(1:m)中，中，S(bottom)通常为栈底元素在栈非空的情况通常为栈底元素在栈非空的情况下，下，S(top)为栈顶元素。为栈顶元素。top=0表示栈空；表示栈空；top=m表示栈满。表示栈满。 栈的根本运算有栈的根本运算有3种：种：入栈运算入栈运算退栈运算退栈运算读栈顶元素读栈顶元素栈中的运算：栈中的运算：1.设置空栈设置空栈

16、； 2. 插入一个新的栈顶元素插入一个新的栈顶元素 3. 删除栈顶元素；删除栈顶元素； 4. 读取栈顶元素读取栈顶元素 。 1.4.2 队列及其根本运算队列及其根本运算 1、队列、队列queue的定义的定义 队列是允许在一端队列是允许在一端(队尾队尾rear)进展插入、而在另一端进展插入、而在另一端(队头队头front)进展删进展删除的线性表。它按照除的线性表。它按照“先进先出先进先出FIFO first in first out) 或或“后进后出后进后出LILOlast in last out)的原那么组织数据。的原那么组织数据。 a1 , a2 , a3 , a4 , an-1 , an

17、队 列 示 意 图队头队尾frontrear 举例举例1：到医院看病，首先需求到挂号处：到医院看病，首先需求到挂号处挂号，然后，按号码顺序救诊。挂号，然后，按号码顺序救诊。 举例举例2：乘坐公共汽车，应该在车站排：乘坐公共汽车，应该在车站排队，车来后，按顺序上车。队，车来后，按顺序上车。 队列是指允许在一端队尾进入插入，而在另一端队头进展删除的线性表。Rear指针指向队尾，front指针指向队头。 队列是“先进先出FIFO或“后进后出LILO的线性表。 队列运算包括 1入队运算：从队尾插入一个元素； 2退队运算：从队头删除一个元素。 循环队列:在循环队列中，用队尾指针r指向队尾，用排头指针f指

18、向队头的前一个位置 *循环对队中的元素的个数=rear-front(rf) =rear-front+容量(r=1)2k-1(k=1)个结点；个结点； 2 2深度为深度为m m的二叉树最多有的二叉树最多有2m-12m-1个结点；个结点； 3 3在恣意一棵二叉树中，度为在恣意一棵二叉树中，度为0 0的结点即叶子的结点即叶子结点总是比度为结点总是比度为2 2的结点数多一个；的结点数多一个； 4 4具有具有n n个结点的二叉树，其深度至少为个结点的二叉树，其深度至少为log2n+1log2n+1，其中，其中log2nlog2n表示取不大于表示取不大于log2nlog2n的最大的最大整数。整数。2019

19、.9.82019.9.8题：一棵二叉树中共有题：一棵二叉树中共有7070个叶子结点和个叶子结点和8080个度为个度为1 1的结点，那么二叉树中总结点数为：的结点，那么二叉树中总结点数为：A.219 B.221 C.229 D.231A.219 B.221 C.229 D.2313 3、满二叉树和完全二叉树、满二叉树和完全二叉树 1 1满二叉树满二叉树 除最后一层外，每一层上的一切结点都有两个除最后一层外，每一层上的一切结点都有两个子结点。子结点。 即在第即在第K K层上有层上有2k-12k-1个结点。个结点。深度为深度为m m的满二叉树有的满二叉树有2m-12m-1个结点个结点42316789

20、1011121314155特点：每一层上都含有最大结点数。特点：每一层上都含有最大结点数。2 2完全二叉树完全二叉树 除最后一层外，每一层上的结点数都到达最大值；在除最后一层外，每一层上的结点数都到达最大值；在最后一层上只短少右边的假设干结点。最后一层上只短少右边的假设干结点。4231678910 11125 非完全二叉树4231678910 11125 完全二叉树特点：除最后一层外，每一层都取最大结点数，特点：除最后一层外，每一层都取最大结点数，最后一层结点都集中在该层最左边的假设干位置。最后一层结点都集中在该层最左边的假设干位置。 8 9 10 11 12 4 5 6 72 31 7 8

21、94 5 6 2 31 4 5 62 31一棵满二叉树一定是一棵完全二叉树，而一棵完全二叉树不一定是满二叉树。2i +2 2i 2i+1 2i+2 2i+3 i+1 2i 2i+1i i i+1另：性质：完全二叉树中度为1的结点数为0或1完全二叉树总数为奇数时，度为1的结点数为0 为偶数时，度为1的结点数为1 1.6.4 二叉树的遍历二叉树的遍历所谓遍历二叉树就是按某种顺序访问二叉树中的每个结点一次且仅一次的所谓遍历二叉树就是按某种顺序访问二叉树中的每个结点一次且仅一次的过程。这里的访问可以是输出、比较、更新、查看元素内容等等各种操作。过程。这里的访问可以是输出、比较、更新、查看元素内容等等各

22、种操作。1、前序遍历、前序遍历DLR假设二叉树为空，那么终了遍历操作；否那么假设二叉树为空，那么终了遍历操作；否那么访问根结点，按前序遍历左子树，按前序遍历右子树。访问根结点，按前序遍历左子树，按前序遍历右子树。2、中序遍历、中序遍历LDR假设二叉树为空，那么终了遍历操作；否那么假设二叉树为空，那么终了遍历操作；否那么按中序遍历左子树，访问根结点，按中序遍历右子树。按中序遍历左子树，访问根结点，按中序遍历右子树。3、后序遍历、后序遍历LRD假设二叉树为空，那么终了遍历操作；否那么假设二叉树为空，那么终了遍历操作；否那么按后序遍历左子树，按后序遍历右子树，访问根结点。按后序遍历左子树，按后序遍历右子树，访问根结点。G HB CAD E F先序序列：先序序列：ABDGCEFH中序序列：中序序列：DGBAECHF后序序列：后序序列：GDBEHFCA先序：DLR中序：LDR后序：LRDACEFGBHPD先序序列：先序序列：FCADBEGHP中序序列：中序序列：ACBDFEHG