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

《数据结构与算法ppt课件.ppt》由会员分享，可在线阅读，更多相关《数据结构与算法ppt课件.ppt（46页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构与算法ppt课件 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望1.1.1 1.1.1 算法的基本概念算法的基本概念 所谓算法是指解题方案的准确而完整的描述。所谓算法是指解题方案的准确而完整的描述。1.1 1.1 算法算法 1 1、算法的基本特征、算法的基本特征 可行性可行性：算法原则上能够精确地执行，甚至人们只用笔和纸做有限次运算即可完成。确定性确定性：算法的每一步都必须有确切的定义 有穷性有穷性：一个算法必须在执行有穷步后结束，即算法必须能够终止 拥有

2、足够的情报拥有足够的情报：我们要使算法有效就必须拥有足够的情报2 2、算法的基本要素、算法的基本要素 数据对象的运算和操作数据对象的运算和操作A.A.算术运算算术运算（+、-、*、/）B.B.逻辑运算逻辑运算（&、|、!）C.C.关系运算关系运算（、算法的控制结构算法的控制结构一个算法一般都可以用一个算法一般都可以用顺序、选择、循环顺序、选择、循环三种基本控制结构组合三种基本控制结构组合而成。而成。3 3、算法设计基本方法、算法设计基本方法列举法：列举法：指针对待解决的问题，列举所有可能的情况，并用问题中给定的条件来检验。归纳法归纳法：特殊一般的抽象过程递推：递推：从已知初始条件出发，逐次推出

3、所要求的各中间结构和最后结果递归：递归：将复杂的问题逐层分解，最后归结为一个简单的问题，再沿原分解的逆过程逐步进行综合。分为直接递归和间接递归减半递推技术：减半递推技术：把规模较大较复杂的问题，分成几个规模较小较简单的问题回溯法：回溯法：通过对问题的分析，找出一个解决问题的线索，多次试探，若成功，则得出解，若失败，则回退，换别的路线再进行试探1.1.2 1.1.2 算法复杂度算法复杂度算法的复杂度主要包括时间复杂度和空间复杂度。两者算法的复杂度主要包括时间复杂度和空间复杂度。两者之间没有必然的联系。之间没有必然的联系。1 1、算法的时间复杂度、算法的时间复杂度 指执行算法所需要的计算工作量。指

4、执行算法所需要的计算工作量。工作量可以用算法在执行过程中所需基本运算的执行次数来工作量可以用算法在执行过程中所需基本运算的执行次数来度量。其中基本运算次数是问题规模的函数，即度量。其中基本运算次数是问题规模的函数，即 算法的工作量算法的工作量=f(n)=f(n)。平均性态平均性态 最坏情况复杂性最坏情况复杂性注意注意:算法程序执行的具体时间受使用计算机、程序设计语言以及算法实现过程中的许多细节的影响。而算法的时间复杂度与此无关2 2、算法的空间复杂度、算法的空间复杂度 指执行这个算法所需要的内存空间，包含：指执行这个算法所需要的内存空间，包含：算法程序所占的空间算法程序所占的空间 输入的初始数

5、据所占的空间输入的初始数据所占的空间 算法执行过程中所需要的额外空间算法执行过程中所需要的额外空间 1.2 1.2 数据结构的基本概念数据结构的基本概念 数据结构作为计算机的一门学科，主要研究以下三个方面的数据结构作为计算机的一门学科，主要研究以下三个方面的问题：问题：（1 1）数据的逻辑结构）数据的逻辑结构 （2 2）数据的存储结构）数据的存储结构(物理结构物理结构)（3 3）对各种数据结构进行的运算）对各种数据结构进行的运算数据结构学科的研究目的：提高数据处理的效率。主要包括数据结构学科的研究目的：提高数据处理的效率。主要包括1 1、数据的处理速度、数据的处理速度2 2、尽量节省在数据处理

6、过程中所占用的计算机存储空间、尽量节省在数据处理过程中所占用的计算机存储空间 1.2.1 1.2.1 数据结构的定义数据结构的定义 数据处理数据处理：是指对数据集合中的各元素以各种形式进行：是指对数据集合中的各元素以各种形式进行运算。包括插入、删除、查找、更改等运算，也包括对数据运算。包括插入、删除、查找、更改等运算，也包括对数据元素进行分析。元素进行分析。数据元素数据元素：在数据处理领域中，每一个需要处理的对象：在数据处理领域中，每一个需要处理的对象都可以抽象为数据元素。都可以抽象为数据元素。数据结构数据结构：是指反映数据元素之间关系的数据元素集合：是指反映数据元素之间关系的数据元素集合的表

7、示。数据元素之间的任何关系都可以用前后件关系来描的表示。数据元素之间的任何关系都可以用前后件关系来描述。述。1 1、数据的逻辑结构、数据的逻辑结构 所谓逻辑结构实际上就是指数据元素之间的所谓逻辑结构实际上就是指数据元素之间的前后件关系前后件关系。其。其中前后件关系是指它们的逻辑关系，而与他们在计算机中的存中前后件关系是指它们的逻辑关系，而与他们在计算机中的存储位置无关。它包含两个要素：储位置无关。它包含两个要素：数据元素的集合，通常记为数据元素的集合，通常记为D D；数据元素之间的关系（前后件关系），通常记为数据元素之间的关系（前后件关系），通常记为R R。形式表示如下：形式表示如下：B=B=

8、（D D，R R）其中其中B B表示数据结构表示数据结构 2 2、数据的存储结构、数据的存储结构 数据的逻辑结构在计算机存储空间中的存放形式称为数数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（即据的存储结构（即数据的物理结构数据的物理结构）。）。常用的存储结构有常用的存储结构有顺序、链接、索引顺序、链接、索引等存储结构。等存储结构。1.2.2 1.2.2 数据结构的图形表示数据结构的图形表示 图形表示方法图形表示方法：对于数据集合：对于数据集合D D中的每一个数据元素用中中的每一个数据元素用中间标有元素值的方框表示，一般称为数据结点，简称结点，间标有元素值的方框表示，一般称为数

9、据结点，简称结点，对关系对关系R R中每一个二元组，用一条有向线段从前件指向后件结中每一个二元组，用一条有向线段从前件指向后件结点，以表示数据之间的前后件关系。点，以表示数据之间的前后件关系。春春夏夏冬冬秋秋父亲父亲儿子儿子女儿女儿图图1.2 1.2 一年四季数一年四季数据结构的图形表示据结构的图形表示图图1.3 1.3 家庭成员辈分关系家庭成员辈分关系的数据结构的图形表示的数据结构的图形表示例例1.21.2 用图形表示数据结构用图形表示数据结构B=(D,R),B=(D,R),其中：其中：D=d D=di i|1=i=6=d|1=i=0)，表表中中的的每每一一个个数数据据元元素素，除除了了第第

10、一一个个外外，有有且且只只有有一一个个前件，除了最后一个外，有且只有一个后件。前件，除了最后一个外，有且只有一个后件。1.3.2 1.3.2 线性表的顺序存储结构线性表的顺序存储结构线性表的顺序存储结构有以下两个基本特点：线性表的顺序存储结构有以下两个基本特点：（1）线性表中所有元素所占的存储空间是连续的；）线性表中所有元素所占的存储空间是连续的；（2）线线性性表表中中各各数数据据元元素素在在存存储储空空间间中中是是按按逻逻辑辑顺顺序序依依次存放的。次存放的。逻辑上相邻的结点，物理位置上也相邻逻辑上相邻的结点，物理位置上也相邻在在程程序序设设计计语语言言中中，通通常常定定义义一一个个一一维维数

11、数组组来来表表示示线线性性表表的的顺顺序序存存储储空空间间，该该一一维维数数组组的的长长度度通通常常要要定定义义得得比比线线性性表表的的实实际际长度大一些，以便对线性表进行各种运算，特别是插入运算。长度大一些，以便对线性表进行各种运算，特别是插入运算。线性表的主要操作有线性表的主要操作有：（1）插插入入、（2）删删除除、（3）查查找找、（4）排排序序、（5）分分解、（解、（6）合并、（）合并、（7）复制、（）复制、（8）逆转。）逆转。元素元素a an n.元素元素a ai i.元素元素a a2 2元素元素a a1 1bb+mb+(i-1)*mb+(maxlen-1)*m存储地址存储地址内存状态

12、内存状态Loc(元素元素i)=b+（i-1)*m顺序存储结构示意图顺序存储结构示意图(顺序表顺序表)：首地址首地址起始地址起始地址基地址基地址每个元素所占用每个元素所占用的存储单元个数的存储单元个数1.4 1.4 栈和队列栈和队列 1.4.1 1.4.1 栈及其基本运算栈及其基本运算1、栈（、栈（stack）的定义）的定义栈是限定在一端进行插入和删除的线性表。栈是限定在一端进行插入和删除的线性表。性质：性质：a.按按照照“先先进进后后出出”（FILO first in last out)或或“后后进进先先出出”（LIFOlastinfirstout)的原则组织数据。的原则组织数据。b.通常用指

13、针通常用指针top来指示栈顶的位置，用指针来指示栈顶的位置，用指针bottom指向栈底。指向栈底。c.当表中没有元素时称栈为空栈当表中没有元素时称栈为空栈d.栈具有记忆功能栈具有记忆功能e.往往栈栈中中插插入入一一个个元元素素称称为为入入栈栈运运算算，从从栈栈中中删删除除一一个个元元素素（即即删删除除栈栈顶顶元元素素）称称为为退退栈栈运运算算。Top栈栈顶顶指指针针反反映映了了栈栈中中元元素素的的变化变化2、栈的顺序存储及其运算、栈的顺序存储及其运算在在程程序序设设计计语语言言中中，一一般般用用一一维维数数组组S(1:m)作作为为栈栈的的顺顺序序存储空间，其中存储空间，其中m为栈的最大容量。为

14、栈的最大容量。在在S(1:m)中中，S(bottom)通通常常为为栈栈底底元元素素（在在栈栈非非空空的的情情况况下），下），S(top)为栈顶元素。为栈顶元素。top=0表示栈空；表示栈空；top=m表示栈满。表示栈满。栈的基本运算有栈的基本运算有3种：种：入栈运算入栈运算退栈运算退栈运算读栈顶元素读栈顶元素栈中的运算：栈中的运算：1.设置空栈设置空栈；2.插入一个新的栈顶元素插入一个新的栈顶元素3.删除栈顶元素；删除栈顶元素；4.读取栈顶元素读取栈顶元素。1.4.2 1.4.2 队列及其基本运算队列及其基本运算1、队列（、队列（queue）的定义）的定义队队列列是是允允许许在在一一端端(队队

15、尾尾rear)进进行行插插入入、而而在在另另一一端端(队队头头front)进进行行删删除除的的线线性性表表。它它按按照照“先先进进先先出出”（FIFOfirstinfirstout)或或“后后进进后后出出”（LILOlastinlastout)的的原原则则组组织织数数据。据。a1,a2,a3,a4,an-1,an 队 列 示 意 图队头队尾frontrear举例举例1：到医院看病，首先需要到挂号处：到医院看病，首先需要到挂号处挂号，然后，按号码顺序救诊。挂号，然后，按号码顺序救诊。举例举例2：乘坐公共汽车，应该在车站排：乘坐公共汽车，应该在车站排队，车来后，按顺序上车。队，车来后，按顺序上车。

16、队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。Rear指针指向队尾，front指针指向队头。队列是“先进先出”（FIFO）或“后进后出”（LILO）的线性表。队列运算包括（1）入队运算：从队尾插入一个元素；（2）退队运算：从队头删除一个元素。循环队列:在循环队列中，用队尾指针r指向队尾，用排头指针f指向队头的前一个位置 *循环对队中的元素的个数=rear-front(rf)=rear-front+容量(r=1)(k=1)个结点；个结点；（2 2）深度为）深度为m m的二叉树最多有的二叉树最多有2 2m m-1-1个结点；个结点；（3 3）在在任任意意一一棵棵二二叉叉树

17、树中中，度度为为0 0的的结结点点（即即叶叶子子结结点点）总总是比度为是比度为2 2的结点数多一个；的结点数多一个；（4 4）具具有有n n个个结结点点的的二二叉叉树树，其其深深度度至至少少为为loglog2 2n+1n+1，其其中中loglog2 2nn表示取不大于表示取不大于loglog2 2n n的最大整数。的最大整数。2007.9.82007.9.8题题：一一棵棵二二叉叉树树中中共共有有7070个个叶叶子子结结点点和和8080个个度度为为1 1的结点，则二叉树中总结点数为：的结点，则二叉树中总结点数为：A.219 B.221 C.229 D.231A.219 B.221 C.229 D

18、.2313 3、满二叉树和完全二叉树、满二叉树和完全二叉树 （1 1）满二叉树）满二叉树 除最后一层外，每一层上的所有结点都有两个子结点。除最后一层外，每一层上的所有结点都有两个子结点。即在第即在第K K层上有层上有2 2k k-1-1个结点。个结点。深度为深度为m的满二叉树有的满二叉树有2m-1个结点个结点423167891011121314155特点：每一层上都含有最大结点数。特点：每一层上都含有最大结点数。（2 2）完全二叉树）完全二叉树 除除最最后后一一层层外外，每每一一层层上上的的结结点点数数都都达达到到最最大大值值；在在最后一层上只缺少右边的若干结点。最后一层上只缺少右边的若干结点

19、。4231678910 11125 非完全二叉树非完全二叉树4231678910 11125 完全二叉树完全二叉树特点：除最后一层外，每一层都取最大结点数，特点：除最后一层外，每一层都取最大结点数，最后一层结点都集中在该层最左边的若干位置。最后一层结点都集中在该层最左边的若干位置。8 9 10 11 12 4 5 6 72 31 7 8 94 5 6 2 31 4 5 62 31一棵满二叉树一定是一棵完全二叉树，而一棵完全二叉树不一定是满二叉树。2i+2 2i2i+12i+22i+3i+12i2i+1iii+1另：性质：完全二叉树中度为1的结点数为0或1完全二叉树总数为奇数时，度为1的结点数为

20、0 为偶数时，度为1的结点数为11.6.4 1.6.4 二叉树的遍历二叉树的遍历所谓遍历二叉树就是按某种顺序访问二叉树中的每个结点一次且仅一次的过程。这里的访问可以是输出、比较、更新、查看元素内容等等各种操作。1、前序遍历（、前序遍历（DLR）若二叉树为空，则结束遍历操作；否则访问根结点，按前序遍历左子树，按前序遍历右子树。访问根结点，按前序遍历左子树，按前序遍历右子树。2、中序遍历（、中序遍历（LDR）若二叉树为空，则结束遍历操作；否则按中序遍历左子树，访问根结点，按中序遍历右子树。按中序遍历左子树，访问根结点，按中序遍历右子树。3、后序遍历（、后序遍历（LRD）若二叉树为空，则结束遍历操作

21、；否则按后序遍历左子树，按后序遍历右子树，访问根结点。按后序遍历左子树，按后序遍历右子树，访问根结点。G HB CAD E F先序序列：先序序列：ABDGCEFH中序序列：中序序列：DGBAECHF后序序列：后序序列：GDBEHFCA先序：DLR中序：LDR后序：LRDACEFGBHPD先序序列：先序序列：FCADBEGHP中序序列：中序序列：ACBDFEHGP后序序列：后序序列：ABDCHPGEF先序：DLR中序：LDR后序：LRDD G B A E C H F G HD E FB CA（2）遍历算法遍历算法先序遍历：先序遍历：DLR中序遍历：中序遍历：LDR后序遍历：后序遍历：LRDADB

22、CT1T2T3DLRADLRDLRBDCDLR以先序遍历以先序遍历D L RD L R为例演示遍历过程为例演示遍历过程 ABDCBDACDBCA1.7 1.7 查找技术查找技术 1.7.1 1.7.1 顺序查找顺序查找 下列两种情况只能用顺序查找：下列两种情况只能用顺序查找：（1 1）如如果果线线性性表表为为无无序序表表，则则不不管管是是顺顺序序存存储储结结构构还还是是链式存储结构，都只能用顺序查找。链式存储结构，都只能用顺序查找。（2 2）即即使使是是有有序序线线性性表表，如如果果采采用用链链式式存存储储结结构构，也也只只能用顺序查找。能用顺序查找。1.7.2 1.7.2 二分法查找二分法查

23、找(又称折半查找又称折半查找)只适用于只适用于顺序存储的有序表顺序存储的有序表（递增排列）（递增排列）。基本思想基本思想：查找区间逐步缩小：查找区间逐步缩小(折半折半)对于长度为对于长度为n的有序线性表，在最坏情况下，二分查找只的有序线性表，在最坏情况下，二分查找只需要需要log2n次，而顺序查找需比较次，而顺序查找需比较n次次。对半分，中间值为对半分，中间值为m，若，若xm在右边找，若在右边找，若xm在左边找在左边找查找成功示例：查找成功示例：123456789(12,33,40,45,53,55,64,66,77)，key=64lowhighmidlowmid1.8 1.8 排序技术排序技术