数据结构与算法.ppt

1、数据结构与算法,2020年7月27日,数据结构讲义,2,1.3.1 算法及其特性,算法（Algorithm）是对特定问题求解步骤的一种描述，是指令的有限序列。其中每一条指令表示一个或多个操作。 一个算法应该具有下列特性： 有穷性。一个算法必须在有穷步之后结束，即必须在有限时间内完成。 确定性。算法的每一步必须有确切的定义，无二义性。算法的执行对应着的相同的输入仅有唯一的一条路经。 可行性。算法中的每一步都可以通过已经实现的基本运算的有限次执行得以实现。 输入。一个算法具有零个或多个输入，这些输入取自特定的数据对象集合。 输出。一个算法具有一个或多个输出，这些输出同输入之间存在某种特定的关系。,

2、2020年7月27日,数据结构讲义,3,1.3.3 算法的性能分析,时间复杂度、空间复杂度：也成为时间性能和空间性能，是对某个算法的时间效率和空间效率的度量。 时间复杂度 将一个算法转换成程序并在计算机上执行时，其运行所需要的时间取决于下列因素： 空间复杂度： 一个算法的空间复杂度（Space complexity）是指算法运行从开始到结束所需的存储量。,2020年7月27日,数据结构讲义,4,1.2.1 有关概念和术语,1、数据项 2、数据元素 3、数据对象 4、数据结构,数据结构（Data Structure）是指互相之间存在着一种或多种关系的数据元素的集合。在任何问题中，数据元素之间都不

3、会是孤立的，在它们之间都存在着这样或那样的关系，这种数据元素之间的关系称为结构。 根据数据元素间关系的不同特性，通常有下列四类基本的结构： 集合结构。线性结构。树结构。图结构。,2020年7月27日,数据结构讲义,5,图1.5为表示上述四类基本结构的示意图。,2020年7月27日,数据结构讲义,6,数据结构课程集中讨论软件开发过程中的设计阶段、同时涉及编码和分析阶段的若干基本问题。此外，为了构造出好的数据结构及其实现，还需考虑数据结构及其实现的评价与选择。因此，数据结构的内容包括三个层次的五个“要素”。,2、 数据结构课程的内容,2020年7月27日,数据结构讲义,7,2.1.1 线性表的定义

4、 线性表是线性结构的一般形式。 线性结构的特点是数据元素之间是一种线性关系，数据元素“一个接一个的排列”。在一个线性表中数据元素的类型是相同的，或者说线性表是由同一类型的数据元素构成的线性结构。 线性表是具有相同数据类型的n(n=0)个数据元素的有限序列，通常记为： (a1，a2， ai-1，ai，ai+1，an),2020年7月27日,数据结构讲义,8,(a1，a2， ai-1，ai，ai+1，an) 其中n为表长， n0 时称为空表。表中相邻元素之间存在着顺序关系。将 ai-1 称为 ai 的直接前趋，ai+1 称为 ai 的直接后继。就是说：对于ai，当 i=2，.，n 时，有且仅有一个

5、直接前趋ai-1，当i=1，2，.，n-1 时，有且仅有一个直接后继ai+1，而 a1是表中第一个元素，它没有前趋，an是最后一个元素无后继。 需要说明的是：ai为序号为i的数据元素（i=1,2,n），通常我们将它的数据类型抽象为datatype，datatype根据具体问题而定，如在学生情况信息表中，它是用户自定义的学生类型； 在字符串中，它是字符型；等等。,2020年7月27日,数据结构讲义,9,2.1.2 线性表的基本运算, 线性表初始化：Init_List(L) 求线性表的长度：Length_List(L) 取表元：Get_List(L,i) 按值查找：Locate_List(L,x)

6、 插入操作：Insert_List(L,i,x) 删除操作：Delete_List(L,i) 线性表的顺序存储是指在内存中用地址连续的一块存储空间依次顺序存放线性表各元素，用这种存储形式存储的线性表称其为顺序表。 因为内存的地址空间是一维线性空间，因此顺序表的存储特点是：用物理上的相邻实现逻辑上的相邻。,2020年7月27日,数据结构讲义,10,插入运算 (1) 运算说明： 线性表的插入是指在表的第i个位置上插入一个值为 x 的新元素。,插入前：(a1, a2, . , ai-1, ai , ai+1 , . , an) 插入后：(a1, a2, . , ai-1, x, ai, ai+1 ,

7、 . , an ) 其中：1in+1，n是原来的表长。 (3) 本算法中注意以下问题： 顺序表中数据区域有MAXSIZE个存储单元，所以在向顺序表中做插入时先检查表空间是否满了，在表满的情况下不能再做插入，否则产生溢出错误。 要检验插入位置的有效性，这里 i 的有效范围是：1in+1，其中 n 为原表长。 注意数据的移动方向。 表长的修改。,2020年7月27日,数据结构讲义,11,删除运算 (1) 运算说明： 线性表的删除运算是指将表中第 i 个元素从线性表中去掉。,删除前：(a1, a2, . , ai-1, ai , ai+1 , . , an) 删除后：(a1, a2, . , ai-

8、1, ai+1 , . , an ) 其中：1in，n是原来的表长。,2020年7月27日,数据结构讲义,12,按值查找,(1) 运算说明： 线性表中的按值查找是指在线性表中查找与给定值x相等的数据元素。,2020年7月27日,数据结构讲义,13,2.3.3 循环链表,对于单链表而言，最后一个结点的指针域是空指针，如果将该链表头指针置入该指针域，则使得链表头尾结点相连，就构成了单循环链表。,2020年7月27日,数据结构讲义,14,(2) 和单链表类似，双向链表通常也是用头指针标识，也可以带头结点和做成循环结构。,2020年7月27日,数据结构讲义,15,3.1.1 栈的定义及基本运算,1.栈

9、的定义 栈是限制在表的一端进行插入和删除的线性表。允许插入、删除的这一端称为栈顶，另一个固定端称为栈底。当表中没有元素时称为空栈。,右图所示栈中有三个元素，进栈的顺序是a1、a2、a3，当需要出栈时其顺序为a3、a2、a1，所以栈又称为后进先出的线性表（Last In First Out），简称 LIFO表。,2020年7月27日,数据结构讲义,16,2.栈的基本运算： 栈初始化：Init_Stack(s) 操作结果是构造了一个空栈。 判栈空：Empty_Stack(s) 操作结果是若s为空栈返回为1，否则返回为0。 入栈： Push_Stack(s，x) 操作结果是在栈s的顶部插入一个新元素

10、x，x成为新的栈顶元素。 出栈：Pop_Stack(s) 在栈s存在且非空的情况下，操作结果是将栈s的顶部元素从栈中删除。 读栈顶元素：Top_Stack(s) 在栈s存在且非空情况下，操作结果是读栈顶元素，栈不变化。,2020年7月27日,数据结构讲义,17,3.3.1 队列的定义及基本运算,在实际问题中经常用到一种“先进先出” (FIFO-First In First Out)的数据结构：即插入在表一端进行，删除在表的另一端进行，这种数据结构称为队或队列，把允许插入的一端叫队尾(rear) ，把允许删除的一端叫队头(front)。 队列也是一种运算受限制的线性表，又叫先进先出表。,如图所示

11、是一个有5 个元素的队列。 入队的顺序依次为a1、 a2 、a3 、a4 、 a5。 出队时的顺序将依然是a1、a2、a3、a4 、 a5 。,2020年7月27日,数据结构讲义,18,在队列上进行的基本操作有： 队列初始化：Init_Queue(q) 操作结果是构造一个空队。 入队操作：In_Queue(q,x) 在队q存在情况下，操作结果是对已存在的队列q，插入一个元素x到队尾。 出队操作：Out_Queue(q,x) 队q存在且非空情况下，操作结果是删除队首元素，并返回其值。 读队头元素：Front_Queue(q,x) 队q存在且非空情况下，操作结果是读出队头元素，并返回其值。 判队空

12、操作：Empty_Queue(q) 队q存在时，操作结果是若q为空队则返回为1，否则返回为0。,2020年7月27日,数据结构讲义,19,第5章 树结构 本章首先对二叉树结构进行较为深刻的讨论，然后再介绍树结构中一般意义的树和它们与二叉树之间的关系。,1教学内容 5.1 二叉树 5.2 二叉树的遍历 5.3二叉树遍历的应用 5.4 线索二叉树 5.5 哈夫曼树及哈夫曼编码 5.6 树 5.7 树和森林与二叉树之间的转换 5.8 树或森林的遍历,2020年7月27日,数据结构讲义,20,1二叉树的定义 二叉树（Binary Tree）是个有限元素的集合，该集合或者为空、或者由一个称为根(root

13、)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点。 二叉树是有序的，即若将其左、右子树颠倒，就成为另一棵不同的二叉树。即使树中结点只有一棵子树，也要区分它是左子树还是右子树。,2020年7月27日,数据结构讲义,21,2相关术语 在下列的的术语中，除特殊指明了二叉树之外，否则也都适用于普通的树型结构（称为树）。 (1) 结点的度：结点所拥有的子树的个数称为该结点的度。 (2) 叶结点：度为0的结点称为叶结点，或者称为终端结点。 (3) 分支结点：度不为0的结点称为分支结点，或者称为非终端结点。一棵树的结点除叶结

14、点外，其余的都是分支结点。 (4) 左孩子、右孩子、双亲、兄弟：树中一个结点的子树的根结点称为这个结点的孩子。在二叉树中，左子树的根称为左孩子，右子树的根称为右孩子。反过来这个结点称为它孩子结点的双亲。具有同一个双亲的孩子结点互称为兄弟。,2020年7月27日,数据结构讲义,22,(5) 路径、路径长度：如果一棵树中的一串结点n1,n2,nk,有如下关系：结点ni是ni+1的父结点(1ik) ,就把n1,n2,nk称为一条由n1至nk的路径，这条路径的长度是k-1。 (6) 祖先、子孙：在树中，如果有一条路径从结点M到结点N，那么M就称为N的祖先，而N称为M的子孙。 (7) 结点的层数：规定树

15、的根结点的层数为1，其余结点的层数等于它的双亲结点的层数加1。 (8) 树的深度：树中结点的最大层数称为树的深度。,2020年7月27日,数据结构讲义,23,(9) 满二叉树。 在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的一棵二叉树称作满二叉树。如图所示，(a)图就是一棵满二叉树，(b)图则不是满二叉树，因为，虽然其所有结点要么是含有左右子树的分支结点，要么是叶子结点，但由于其叶子未在同一层上，故不是满二叉树。,2020年7月27日,数据结构讲义,24,(10) 完全二叉树。 一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序

16、进行编号，如果编号为i（1in）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。完全二叉树的特点是：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。显然，一棵满二叉树必定是一棵完全二叉树，而完全二叉树未必是满二叉树。如图所示(a)为一棵完全二叉树，(b)不是完全二叉树。,2020年7月27日,数据结构讲义,25,5.1.2 二叉树的主要性质,性质1 一棵非空二叉树的第i层上最多有2i-1个结点（i1）。该性质可由数学归纳法证明。证明略。 性质2 一棵深度为k的二叉树中，最多具有2k1个结点。 性质3：对于一棵非空的二叉树，若叶子结点数为n0

17、，度数为2的结点数为n2，则有：n0n21。,2020年7月27日,数据结构讲义,26,5.1.3 二叉树的存储,1顺序存储结构 所谓二叉树的顺序存储，是用一组连续的存储单元存放二叉树中的结点。一般是按照二叉树结点从上至下、从左到右的顺序存储。 因此，依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，树中结点的序号可以唯一地反映出结点之间的逻辑关系，这样既能够最大可能地节省存储空间，又可以利用数组元素的下标值确定结点在二叉树中的位置，以及结点之间的关系。,2020年7月27日,数据结构讲义,27,下面给出一棵完全二叉树的顺序存储示意。,2020年7月27日,数据结构讲义,28,对于一

18、般的二叉树，如果仍按从上至下和从左到右的顺序将树中的结点顺序存储在一维数组中，则数组元素下标之间的关系不能够反映二叉树中结点之间的逻辑关系，只有增添一些并不存在的空结点，使之成为一棵完全二叉树的形式，然后再用一维数组顺序存储。,2020年7月27日,数据结构讲义,29,2链式存储结构 (1)二叉链表存储 链表中每个结点由三个域组成，除了数据域外，还有两个指针域，分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。结点的存储的结构为： 其中，data域存放某结点的数据信息；lchild 与rchild分别存放指向左孩子和右孩子的指针，当左孩子或右孩子不存在时，相应指针域值为空（用符号或NUL

19、L表示）。,2020年7月27日,数据结构讲义,30,5.2.1 递归方法实现二叉树的三种遍历,由二叉树的定义可知，一棵二叉树由根结点、根结点的左子树和根结点的右子树三部分组成。因此，只要依次遍历这三部分，就可以遍历整个二叉树。 若以D、L、R分别表示访问根结点、遍历根结点的左子树、遍历根结点的右子树，则二叉树的遍历方式有六种：DLR、LDR、LRD、DRL、RDL和RLD。 如果限定先左后右，则只有前三种方式，即： DLR（称为先序遍历) LDR（称为中序遍历) LRD（称为后序遍历) 。,2020年7月27日,数据结构讲义,31,1先序遍历 先序遍历的递归过程为：若二叉树为空，遍历结束。否

20、则， (1) 访问根结点； (2) 先序遍历根结点的左子树； (3) 先序遍历根结点的右子树。 【算法 5-5】先序遍历二叉树的递归算法 void PreOrder(BiTree bt) if (bt=NULL) return; /*递归调用的结束条件*/ Visit(bt) ; /*访问根结点*/ PreOrder(btlchild); /*先序递归遍历bt的左子树*/ PreOrder(btrchild);/*先序递归遍历bt的右子树*/ ,2020年7月27日,数据结构讲义,32,对于上图所示的二叉树，按先序遍历所得到的结点序列为： A B D G C E F,2020年7月27日,数据

21、结构讲义,33,2中序遍历 中序遍历的递归过程为：若二叉树为空，遍历结束。否则， (1) 中序遍历根结点的左子树； (2) 访问根结点； (3) 中序遍历根结点的右子树。 【算法 5-6】中序遍历二叉树的递归算法 void InOrder(BiTree bt) if (bt=NULL) return; /*递归调用的结束条件*/ InOrder(btlchild); /*中序递归遍历bt的左子树*/ Visit(bt); /*访问根结点*/ InOrder(btrchild); /*中序递归遍历bt的右子树*/ ,2020年7月27日,数据结构讲义,34,对于上图所示的二叉树，按中序遍历所得到的结点序列为：