数据结构与算法ppt课件.ppt

,公共基础知识部分之,第一章 数据结构与算法,1.1 算法1.2 数据结构的基本概念1.3 线性表及其顺序存储结构1.4 栈和队列1.5 线性链表1.6 树与二叉树1.7 查找技术1.8 排序技术,1.1.1 算法的基本概念 所谓算法是指解题方案的准确而完整的描述。,1.1 算法,1、算法的基本特征可行性：算法原则上能够精确地执行，甚至人们只用笔和纸做有限次运算即可完成。确定性：算法的每一步都必须有确切的定义有穷性：一个算法必须在执行有穷步后结束，即算法必须能够终止拥有足够的情报：我们要使算法有效就必须拥有足够的情报,2、算法的基本要素数据对象的运算和操作A.算术运算（+、-、*、/）B.逻辑运算（&、|、!）C.关系运算（、算法的控制结构一个算法一般都可以用顺序、选择、循环三种基本控制结构组合而成。,3、算法设计基本方法列举法：指针对待解决的问题，列举所有可能的情况，并用问题中给定的条件来检验。归纳法：特殊一般的抽象过程递推：从已知初始条件出发，逐次推出所要求的各中间结构和最后结果递归：将复杂的问题逐层分解，最后归结为一个简单的问题，再沿原分解的逆过程逐步进行综合。分为直接递归和间接递归减半递推技术：把规模较大较复杂的问题，分成几个规模较小较简单的问题回溯法：通过对问题的分析，找出一个解决问题的线索，多次试探，若成功，则得出解，若失败，则回退，换别的路线再进行试探,1.1.2 算法复杂度,算法的复杂度主要包括时间复杂度和空间复杂度。两者之间没有必然的联系。1、算法的时间复杂度 指执行算法所需要的计算工作量。工作量可以用算法在执行过程中所需基本运算的执行次数来度量。其中基本运算次数是问题规模的函数，即 算法的工作量=f(n)。平均性态最坏情况复杂性注意:算法程序执行的具体时间受使用计算机、程序设计语言以及算法实现过程中的许多细节的影响。而算法的时间复杂度与此无关,2、算法的空间复杂度 指执行这个算法所需要的内存空间，包含：算法程序所占的空间输入的初始数据所占的空间算法执行过程中所需要的额外空间,1.2 数据结构的基本概念,数据结构作为计算机的一门学科，主要研究以下三个方面的问题：（1）数据的逻辑结构（2）数据的存储结构(物理结构)（3）对各种数据结构进行的运算数据结构学科的研究目的：提高数据处理的效率。主要包括1、数据的处理速度2、尽量节省在数据处理过程中所占用的计算机存储空间,1.2.1 数据结构的定义 数据处理：是指对数据集合中的各元素以各种形式进行运算。包括插入、删除、查找、更改等运算，也包括对数据元素进行分析。数据元素：在数据处理领域中，每一个需要处理的对象都可以抽象为数据元素。数据结构：是指反映数据元素之间关系的数据元素集合的表示。数据元素之间的任何关系都可以用前后件关系来描述。,1、数据的逻辑结构 所谓逻辑结构实际上就是指数据元素之间的前后件关系。其中前后件关系是指它们的逻辑关系，而与他们在计算机中的存储位置无关。它包含两个要素：数据元素的集合，通常记为D；数据元素之间的关系（前后件关系），通常记为R。形式表示如下：B=（D，R）其中B表示数据结构,2、数据的存储结构 数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（即数据的物理结构）。常用的存储结构有顺序、链接、索引等存储结构。,1.2.2 数据结构的图形表示 图形表示方法：对于数据集合D中的每一个数据元素用中间标有元素值的方框表示，一般称为数据结点，简称结点，对关系R中每一个二元组，用一条有向线段从前件指向后件结点，以表示数据之间的前后件关系。,春,夏,冬,秋,父亲,儿子,女儿,图1.2 一年四季数据结构的图形表示,图1.3 家庭成员辈分关系的数据结构的图形表示,例1.2 用图形表示数据结构B=(D,R),其中：D=di|1=i=6=d1,d2,d3,d4,d5,d6 R=(d1,d2),(d1,d3),(d3,d4),(d5,d4),(d5,d6),d1,d3,d5,d2,d6,d4,图1.4 数据结构的图形表示,1.2.3 线性结构与非线性结构 如果一个数据结构中一个数据元素都没有，则称为数据结构为空的数据结构。在一个空的数据结构中插入一个元素后就变成了非空。根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为两大类：线性结构（又称为线性表）非线性结构线性结构满足如下两个条件：（1）、有且只有一个根结点；（2）、每一个结点最多有一个前件，也最对多有一个后件。在一个线性结构中插入或删除任何一个结点还是线性结构常见的线性结构：线性表、栈、队列、线性链表常见的非线性结构：树、二叉树、图,1.3 线性表及其顺序存储结构,1.3.1 线性表的基本概念 线性表是n个元素的有限序列，它们之间的关系可以排成一个线性序列：a1，a2，ai，an其中n称作表的长度，当n=0时，称作空表。n(n=0)，表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件。,1.3.2 线性表的顺序存储结构 线性表的顺序存储结构有以下两个基本特点：（1）线性表中所有元素所占的存储空间是连续的；（2）线性表中各数据元素在存储空间中是按逻辑顺序依 次存放的。逻辑上相邻的结点，物理位置上也相邻 在程序设计语言中，通常定义一个一维数组来表示线性表的顺序存储空间，该一维数组的长度通常要定义得比线性表的实际长度大一些，以便对线性表进行各种运算，特别是插入运算。线性表的主要操作有：（1）插入、（2）删除、（3）查找、（4）排序、（5）分解、（6）合并、（7）复制、（8）逆转。,元素an,.,元素ai,.,元素a2,元素a1,b,b+m,b+(i-1)*m,b+(maxlen-1)*m,存储地址,内存状态,Loc(元素i)=b+（i-1)*m,顺序存储结构示意图(顺序表)：,首地址起始地址基地址,每个元素所占用的存储单元个数,1.4 栈和队列,1.4.1 栈及其基本运算 1、栈（stack）的定义栈是限定在一端进行插入和删除的线性表。性质：a.按照“先进后出”（FILO first in last out)或“后进先出”（LIFOlast in first out)的原则组织数据。b.通常用指针top来指示栈顶的位置，用指针bottom指向栈底。c.当表中没有元素时称栈为空栈d.栈具有记忆功能e.往栈中插入一个元素称为入栈运算，从栈中删除一个元素（即删除栈顶元素）称为退栈运算。Top栈顶指针反映了栈中元素的变化,2、栈的顺序存储及其运算 在程序设计语言中，一般用一维数组S(1:m)作为栈的顺序存储空间，其中m为栈的最大容量。在S(1:m)中，S(bottom)通常为栈底元素（在栈非空的情况下），S(top)为栈顶元素。top=0表示栈空；top=m表示栈满。栈的基本运算有3种：入栈运算退栈运算读栈顶元素,栈中的运算：1.设置空栈；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,队 列 示 意 图,队头,队尾,front,rear,举例1：到医院看病，首先需要到挂号处挂号，然后，按号码顺序救诊。举例2：乘坐公共汽车，应该在车站排队，车来后，按顺序上车。,队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。Rear指针指向队尾，front指针指向队头。队列是“先进先出”（FIFO）或“后进后出”（LILO）的线性表。队列运算包括（1）入队运算：从队尾插入一个元素；（2）退队运算：从队头删除一个元素。循环队列:在循环队列中，用队尾指针r指向队尾，用排头指针f指向队头的前一个位置*循环对队中的元素的个数=rear-front(rf)=rear-front+容量(rf)m=50 r=20 f=35,线性表的链式存储结构简称线性链表 线性表的链式存储结构是指用一组任意的存储单元（可以连续，也可以不连续）存储线性表中的数据元素。因此，链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示数据元素间的逻辑关系，对于每个数据元素不仅要表示它的具体内容，还要附加一个表示它的直接后继元素存储位置的信息。这个信息称为指针(pointer)或链(link)。这两部分组成了链表中的结点结构：,指针域，用来存放结点的直接后继的地址,数据域，用来存放结点的值,将线性表的元素放到一个具有头指针的链表中，链表中每个结点包含数据域和指针域。数据域存放数据，指针域存放后继结点的地址，最后一个结点的指针域为空。逻辑上相邻的数据元素在内存中的物理存储空间不一定相邻。,1.5 线性链表,例如：线性表（a,b,c,d),术语表示每个数据元素的两部分信息组合在一起被称为结点；其中表示数据元素内容的部分被称为数据域（data）；表示直接后继元素存储地址的部分被称为指针或指针域（next）。,单链表结构示意图,其中，head是头指针，它指向单链表中的第一个结点，这是单链表操作的入口点。由于最后一个结点没有直接后继结点，所以，它的指针域放入一个特殊的值NULL。NULL值在图示中常用（）符号表示。带头结点的单链表为了简化对链表的操作，人们经常在链表的第一个结点之前附加一个结点，并称为头结点。这样可以免去对链表第一个结点的特殊处理。如下图所示：,带头结点的单链表结构示意图,head,空表,110 hat 200,130 cat 135,135 eat 170,160 mat nil,165 bat 130,170 fat 110,200 jat 205,205 lat 160,165,head,头指针,数据域,指针域,例如：线性表（bat,cat,eat,fat,hat,jat,lat,mat）,单链表只注重结点的逻辑顺序，不关心每个结点的实际存储位置，因此用箭头来表示链域中的指针。,bat,cat,eat,mat,head,1.6 树和二叉树,1.6.1 树的基本概念 树是一种简单的非线性结构，由一个或多个结点组成的有限集合。仅有一个根结点，结点间有明显的层次结构关系。,现实世界中，能用树的结构表示的例子：学校的行政关系、书的层次结构、人类的家族血缘关系等。,树形结构,全校学生档案管理的组织方式,(C)是有13个结点的树，其中A是根，其余结点分成3个子集：T1、T2、T3。都是根A的子树，且本身也是一棵树。例如：T1 其根为B，两棵子树为 T11=F T12=E,K,L，T12 又是一棵子树，树根为F，K 和 L是E的两个互不相交的子集。,结点：数据元素的内容及其指向其子树根的分支统称为结点。结点的度（Degree):结点的分支数，即结点拥有的子树数。终端结点（叶子leaf）:度为0的结点。非终端结点:度不为0的结点。结点的层次:树中根结点的层次为1，根结点子树的根为第2 层，以此类推。树的度:树中所有结点度的最大值。树的深度:树中所有结点层次的最大值。有序树、无序树:如果树中每棵子树从左向右的排列拥有一定的顺序，不得互换，则称为有序树，否则称为无序树。,术语,相关概念：父结点、根结点、子结点、叶子结点、结点的度、树的度、树的深度、子树。,1.6.2 二叉树及其基本性质 1、什么是二叉树 二叉树具有以下两个特点：（1）非空二叉树只有一个根结点；（2）每一个根结点最多只有两棵子树，且分别为该结点的左子树和右子树。（子树有左右之分，左右树不能互换）,二叉树的五种基本形态,两棵不同的二叉树,2、二叉树的基本性质（1）在二叉树的K层上，最多有2k-1(k=1)个结点；（2）深度为m的二叉树最多有2m-1个结点；（3）在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点数多一个；（4）具有n个结点的二叉树，其深度至少为log2n+1，其中log2n表示取不大于log2n的最大整数。2007.9.8题：一棵二叉树中共有70个叶子结点和80个度为1的结点，则二叉树中总结点数为：A.219 B.221 C.229 D.231,3、满二叉树和完全二叉树（1）满二叉树 除最后一层外，每一层上的所有结点都有两个子结点。即在第K层上有2k-1个结点。深度为m的满二叉树有2m-1个结点,特点：每一层上都含有最大结点数。,（2）完全二叉树 除最后一层外，每一层上的结点数都达到最大值；在最后一层上只缺少右边的若干结点。,特点：除最后一层外，每一层都取最大结点数，最后一层结点都集中在该层最左边的若干位置。,一棵满二叉树一定是一棵完全二叉树，而一棵完全二叉树不一定是满二叉树。,2i+2,2i 2i+1 2i+2 2i+3 i+1 2i 2i+1,i,i i+1,另：性质：完全二叉树中度为1的结点数为0或1完全二叉树总数为奇数时，度为1的结点数为0 为偶数时，度为1的结点数为1,1.6.4 二叉树的遍历所谓遍历二叉树就是按某种顺序访问二叉树中的每个结点一次且仅一次的过程。这里的访问可以是输出、比较、更新、查看元素内容等等各种操作。1、前序遍历（DLR）若二叉树为空，则结束遍历操作；否则访问根结点，按前序遍历左子树，按前序遍历右子树。2、中序遍历（LDR）若二叉树为空，则结束遍历操作；否则按中序遍历左子树，访问根结点，按中序遍历右子树。3、后序遍历（LRD）若二叉树为空，则结束遍历操作；否则按后序遍历左子树，按后序遍历右子树，访问根结点。,G H,B C,A,先序序列：ABDGCEFH中序序列：DGBAECHF后序序列：GDBEHFCA,先序：DLR中序：LDR后序：LRD,先序序列：FCADBEGHP中序序列：ACBDFEHGP后序序列：ABDCHPGEF,先序：DLR中序：LDR后序：LRD,D G B A E C H F,G H,D E F,B C,A,（2）遍历算法,先序遍历：D L R中序遍历：L D R后序遍历：L R D,A,D,B,C,T1,T2,T3,D L R,以先序遍历D L R为例演示遍历过程,ABDC,BDAC,DBCA,1.7 查找技术,1.7.1 顺序查找 下列两种情况只能用顺序查找：（1）如果线性表为无序表，则不管是顺序存储结构还是链式存储结构，都只能用顺序查找。（2）即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。,1.7.2 二分法查找(又称折半查找)只适用于顺序存储的有序表（递增排列）。,基本思想：查找区间逐步缩小(折半)对于长度为n的有序线性表，在最坏情况下，二分查找只需要log2n次，而顺序查找需比较n次。对半分，中间值为m，若xm 在右边找，若xm 在左边找查找成功示例：1 2 3 4 5 6 7 8 9(12,33,40,45,53,55,64,66,77)，key=64,1.8 排序技术,