算法与数据结构基础.ppt

《算法与数据结构基础.ppt》由会员分享，可在线阅读，更多相关《算法与数据结构基础.ppt（87页珍藏版）》请在金锄头文库上搜索。

1、第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作第六章 算法与数据结构基础 计算机程序主要对数据进行计算机程序主要对数据进行加工加工和和处处理理。程序中需要说明程序中需要说明数据结构数据结构: :数据的数据的组织形式组织形式和和存储方式存储方式算法算法: :操作数据的操作数据的步骤步骤和和方法方法 数据结构数据结构算法算法1第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作6.1 数据结构基本概念 随着计算机技术的发展随着计算机技术的发展, ,其应用

2、领域其应用领域越来越广。计算机应用已不在局限于数值越来越广。计算机应用已不在局限于数值计算，更多地用于数据处理和信息管理等计算，更多地用于数据处理和信息管理等非数值非数值计算。计算。 例如：学生、图书、财务和例如：学生、图书、财务和人事等信息管理系统。人事等信息管理系统。 学号姓名性别出生日期班级专业20040001刘强男1984/02/1314001机械制造20040002 王晓红女1986/05/0614001机械制造20040003李明男1984/10/2514001机械制造20040041张宇男1984/06/1414002机械电子工程 每个学生对应一个数据，由学号、姓名、性别和出生日

3、期等多个数据项构成，通常对学生信息进行插入、删除或查找等操作。2第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作 数据结构的定义 数据结构是指具有相同特征、相互之数据结构是指具有相同特征、相互之间有关联的间有关联的数据数据集合。集合。 现实世界中每个对象都可以映像成数现实世界中每个对象都可以映像成数据元素。数据元素可以由一个数、一个字据元素。数据元素可以由一个数、一个字符或一个名字等单个数据项组成，也可以符或一个名字等单个数据项组成，也可以由多个数据项组成。由多个数据项组成。 数据元素、结点数据结构中数据元素都具有某种数

4、据结构中数据元素都具有某种共同特征共同特征数据结构中数据元素之间存在着某种数据结构中数据元素之间存在着某种关系关系 3第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作9向量2 2，4343，6868，4545，3232是数据结构每个数据元素由一个数据项组成数据元素之间有位置上的前后关系 每个数据元素由一个数据项组成数据元素之间有位置上的前后关系 9季度名称组成的集合是数据结构： 春，夏，秋，冬9家庭成员祖父、父亲、儿子是数据结构每个数据元素由一个数据项组成数据元素之间有层次上的高低关系 4第六章第六章 算法与数据结构基础

5、算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作 数据结构数据结构是指带有是指带有结构特性结构特性的的数据元素集合数据元素集合。 主要研究：主要研究：数据集合中数据元素之间所固有数据集合中数据元素之间所固有的关系，即数据的关系，即数据逻辑结构逻辑结构；数据处理时数据在计算机中的存数据处理时数据在计算机中的存储关系，即数据储关系，即数据存储结构存储结构( (物理结物理结构构) )；对数据所进行的对数据所进行的操作操作, ,即算法。即算法。5第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中

6、心制作数据逻辑结构 数数据据结结构构中中数数据据元元素素之之间间所所固固有有的的关关系系描描述述成成前前后后件件( (前前驱驱与与后后继继) )关关系系。数数据据之之间间前前后后件件关关系系是是它它们们之之间间的的逻逻辑辑关关系系，与与它它们们在在计计算算机机中中的的存存储储位位置置无无关关，因因此此将将这这种种关关系系称称为为逻辑结构逻辑结构。6第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作一个数据结构可以表示为 S = ( D, R )季节数据结构可以定义成 S=(D,R) 其中: D= 春, 秋, 冬, 夏 R=

7、 (春,夏), (夏,秋), (秋,冬) S表示数据结构D数据元素集合向量数据结构可以定义成 S=(D,R) 其中: D=2,43,68,45,32 R=(2,43),(43,68),(68,45), (45,32) 数据元素之间的前后件关系的集合7第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作线性结构： 一般来说,数据之间有集合,线性,树型和图形 4 种基本逻辑结构。数据元素之间是一对一的关系除第一个结点无前件外,其他结点都 只有一个前件除最后一个结点无后件外,其他结点都只有一个后件例如:春夏冬秋8第六章第六章 算法

8、与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作O数数据据之之间间存存在在一一对对多的关系多的关系O一一个个结结点点最最多多有有一一个个前前件件, ,可可以以有有多多个个后件后件O前前件件与与后后件件之之间间有有层次关系层次关系 一般来说,数据之间有集合,线性,树型和图形 4 种基本逻辑结构。树型结构：9第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作9数据元素之间存在数据元素之间存在多对多多对多的关系的关系9一个结点可以有多一个结点可以有多个前件和多个后件个前件和

9、多个后件 一般来说,数据之间有集合,线性,树型和图形 4 种基本逻辑结构。图形结构：10第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作 一般来说,数据之间有集合,线性,树型和图形 4 种基本逻辑结构。 集集合合：是是一一种种松松散散结结构构，数数据据元元素素之之间间的的关关系系只只是是同同属属于于一一个个集集合合，可可以以用其他结构来表示。用其他结构来表示。集合11第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作数据物理结构 数数据据在在计计算算

10、机机存存储储器器中中的的存存储储方方式式称称为为数数据据物物理理结结构构( (数数据据存存储储结构结构) )。 在在数数据据存存储储结结构构中中，不不仅仅要要存存放放各各个个数数据据元元素素信信息息，还还要要存存放放数数据据元元素素之之间间前前后后件件关关系系信信息息。数数据据元元素素在在计计算算机机中中通通常常有有四四种种存存储储方方式式：顺序顺序、链式链式、索引索引和和散列散列。12第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作顺序存储结构 顺序存储结构是在内顺序存储结构是在内存中开辟一块连续内存单元用于存中开辟一

11、块连续内存单元用于存放数据，逻辑上相邻的结点在存放数据，逻辑上相邻的结点在物理位置上也相邻。物理位置上也相邻。 即：即：结点之间的逻辑结点之间的逻辑关系由存储单元的相邻关系来体关系由存储单元的相邻关系来体现现。13第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作有如下顺序关系 a, b, c, d 例如：a a地址2000H2000H2001H2001Hc c2002H2002H2003H2003Hd d数据顺序存储结构 如果在如果在b b和和c c之之间增加新数据间增加新数据x x构成构成 a,b,x,c,da,b,x

12、,c,d 的顺序的顺序关系关系, ,应该如何存储应该如何存储？b b14第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作 链式存储结构链式存储结构中，结点由两部分组成： 用于存放数据元素(数据域) 用于存放前件或后件的存储地址(指针域) 即：通过指针反映数据元素之间的逻辑关系15第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作 链式存储结构有如下顺序关系 a, b, c 例如：a a2000b bc c30011003300130011003100

13、316第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作顺序存储结构与链式存储结构比较顺序存储结构：优点：每个结点占用存储空间最少 缺点：如果数据元素很多，则可能找不到一块足够大的连续存储单元 不能很好利用存储单元,容易产生碎片链式存储结构: 优点：充分利用所有存储单元缺点：每个结点占用较多存储单元 17第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作链式存储的插入 J L U S在J,L之间插入接点S链式存储的删除 J L U 删除接点L显然,链式

14、存储的插入和删除操作比较简单、方便18第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作6.2 算法基本概念 程序包含两方面的内容： 对数据的描述 对操作的描述 算法就是操作步骤，是解决“做什么”和“怎么做”的问题。算法是程序的灵魂，广义来说，为解决一个问题而采取的方法和步骤就称为算法。19第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作计算机算法分为： 数值算法 非数值算法 各种数学问题的解法 常用于事物管理领域，如排序、查询 算法是定义在逻辑结构

15、上的操作，独立于计算机，但算法的实现依赖于数据的存储结构。20第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作算法的特征Z可行性Z确定性Z有穷性Z输入Z输出 采取的方法和步骤可行，结果另人满意。 算法中的每一个步骤都必须确定，不能产生歧义。 执行算法时从外界取得必要的信息。一个算法可以有零或多个输入。 算法得到的结果就是输出,没有输出的算法是没有意义的,一个算法应该有一个或多个输出。算法必须由有限步组成，并能在有效时间内完成。21第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大

16、学公共计算机教学与研究中心制作算法描述方法 计算写出其算法。分析：分析：1 1、展开上面算式、展开上面算式 S=1+2+3+S=1+2+3+99+100+99+1002 2、按传统方法求解、按传统方法求解S 1 S S +2 S S + 3 S S + 99 S S + 10022第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作 计算写出其算法。main()main() intint s=0; s=0; s=1; s=1; s=s+2; s=s+2; s=s+3; s=s+3; s=s+99; s=s+99; s=s+1

17、00; s=s+100; printfprintf( (“s=%ds=%d/ /n n”,s,s) ); ; 利利用用程程序序设设计计中中的的顺顺序序结结构构很不理想算法23第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作 用于描述算法的工具很多，通常有流程图、N-S图、自然语言和伪代码等工具。自然语言：带序号的人类语言描述方法。1.1.将变量将变量s s清清0 0；2.2.将变量将变量n n置置1 1；3.3.把把s+ns+n的值赋给的值赋给s s；4.4.把把n+1n+1的值赋给的值赋给n n；5.5.判断判断 n

18、n 100 100？是否成立？是否成立，若成立，转，若成立，转3 3；否则转否则转6 66.6.6. 6. 输出输出s s的值的值; ;S=1+2+3+99+100特点特点: :易懂却不直观易懂却不直观, ,对复杂算法描述很对复杂算法描述很困难困难, ,易产生歧义。易产生歧义。若成立若成立,24第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作伪代码法：是一种假的代码不能被计算机所理解，但可以用你熟悉的计算机语言的语句加上自然语言构成。 0 S 1 n while n 100 S+n S n+1 n print S 这样就

19、接近于某种语这样就接近于某种语言编写的程序言编写的程序, , 便于便于转换成编程语言。转换成编程语言。25第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作 用于描述算法的工具很多，通常有流程图、N-S图、自然语言和伪代码等工具。流程图法：用一些图框、线条以及文字说明 来形象地、直观地描述算法。输入/输出处理判断起止连接点流程线符号说明：26第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作开始0 S1 nSn Sn1 n输出S结束T F n 100S

20、=1+2+3+S=1+2+3+99+100+99+100优点:直观形象缺点:算法复杂时,篇幅 较多,费时且不方便修改。27第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作N-S图: : 完全去掉了带箭头的流程线、算法的所有处理步骤都写在一个大矩形框内, 框内还可以包含一些从属于它的小矩形框, 适于结构化程序设计。顺序顺序AB判断判断条件FTBA“当型当型”循循环环当条件成立当条件成立A“直到型直到型”循循环环直到条件成立直到条件成立A0 S1 nn 100Sn Sn1 n输出输出S S的值的值28第六章第六章 算法与数据

21、结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作算法评价 在计算机程序设计中,某一任务的算法设计得优与劣,将直接影响程序的运行效率、稳定性和可维护性。通常从以下4个方面评价一个算法。正确性可读性健壮性执行效率算法本身没有语法错误,执行时输入正确数据能够得到正确结果.算法要容易理解和阅读,容易实现，同时也要便于程序维护和完善。 指算法执行的时间性能和空间性能 。算法能够对输入的各种数据给予适当的提示和处理 。 多多个个算算法法解解决决同同一一个个问问题题时时, ,执执行行时时间间短短的的算算法法时时间间效效率率高高; ;占占用用存存储储空空间间少

22、少的的算算法法空空间间效效率高。率高。29第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作算法复杂度 算法复杂度是对算法效率的度量，是评算法复杂度是对算法效率的度量，是评价算法优劣的价算法优劣的重要依据。重要依据。 一个算法复杂度高低体现在运行该算法一个算法复杂度高低体现在运行该算法所需要所需要资源资源的多少。的多少。时间资源时间资源空间空间( (即存储器即存储器) )资源资源 因而因而, ,算法复杂度包含算法复杂度包含时间复杂度时间复杂度和和空间复杂度空间复杂度。 时间复杂度时间复杂度指执行算法所需时间指执行算法所需时

23、间 : 执行时间执行时间= =语句执行时间语句执行时间语句执行次数语句执行次数 空间复杂度空间复杂度指在算法执行过程中指在算法执行过程中, ,所占用所占用附加附加空间数量空间数量30第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作6.3 典型数据结构数据逻辑结构分为: 线性结构 非线性结构有且只有一个开始结点和一个终端结点，并且每个结点最多只有一个前件和一个后件，线性结构也称为线性表。栈、队列、数组和串等是特殊线性表非线性结构包括树和图31第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心

24、制作吉林大学公共计算机教学与研究中心制作6.3.1 线性表 线性表是一组特征相同数据的有限序列，表示为 L=(a1 1, a2 2 , a3 3 an n)。非空线性表的特征:除a1 1无前件外,其它任意数据元素ai i有且只有一个前件ai-1i-1 。除了an n无后件外,其它任意数据元素ai i有且只有一个后件ai+1i+1。 线性表中数据元素个数n(n0)称为线性表长度。当n=0时,称为空表。在非空线性表中，每个数据元素都有一个确定位置，其位置取决于它的序号。a a1 1是第一个元素，是第一个元素，a a2 2 是第二个元素，是第二个元素，a an n是最后一个元素。是最后一个元素。 3

25、2第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作向量2，43，68，45，32是线性表。季度名称 春，夏，秋，冬是线性表。学生基本信息: (20040001, (20040001,刘强刘强, ,男男,1984/02/13,14001, ,1984/02/13,14001, 机械制造机械制造),), (20040002, (20040002,王晓红王晓红, ,女女,1986/05/06,14001,1986/05/06,14001,机械制造机械制造),), (20040003, (20040003,李明李明, ,男男,1

26、984/10/25,14001,1984/10/25,14001,机械制造机械制造) ) 是线性表。33第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作线性表顺序存储结构顺序存储结构具有以下两个基本特点特点： 线性表中所有元素所占的存储空间是连续的。 线性表中各元素在存储空间中按逻辑顺序依次存放,即线性表的逻辑结构与存储结构相一致一致。线性表通常采用顺序存储结构或链式存储结构。顺序表顺序表链表链表由此可以看出由此可以看出: : 在线性表的顺序存储结构中,其前后两个元素在存储空间中是紧邻的，前件元素一定存放在后件元素的前面

27、。34第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作例如：线性结构 a1 1，a2 2，a3 3，其中每个数据元素占2个存储空间，假设存储a1 1的首地址为2000。20002000a a1 1占占2 2个字节个字节a a2 2a a3 32004200420022002占占2 2个字节个字节占占2 2个字节个字节存储地址：存储地址：结论：假假设设一一个个数数据据元元素素占占用用d d个个字字节节, ,线线性性表表的的首首地地址址Addr(aAddr(a1 1) )为为K K，则则存存储储任任意意一一个个数数据据元元素

28、素a ai i的首地址为的首地址为: : AddrAddr( (a ai i)= Addr(a)= Addr(a1 1)+(i-1)+(i-1)d=K+(i-d=K+(i-1)1)d d 其中其中 1 i n 1 i n 优点：可以方便地随机读取表中任意元素缺点：插入和删除运算需要移动大量元素，浪费大 量时间，时间效率较低。 35第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作线性表的链式存储 用一组存储单元(可以连续，也可以不连续)存储线性表中数据元素。为了反映数据元素之间的逻辑关系，每个数据元素由两部分组成： 1用于

29、存放数据元素(数据域) 2用于存放前件或后件的存储地 址(指针域)数据域数据域指针域指针域结点之间逻辑关系由指针域来确定36第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作单链表 定义：每个结点只有一个指针域的链表 a1a2a3a4a5headhead每个单链表都有一个头指针，存放表中第一个结点的存储地址。每个结点指针域存放后件结点的存储地址，最后一个结点无后件结点，指针域为空，用NULL或表示。 37第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制

30、作循环链表 循环链表中增设一个表头结点，其数据域的值可以任意或根据情况来设置，指针域指向第一个结点。 将单链表最后一个结点的空指针域改为指向该链表的第一个结点，即首尾相连。head空循环链表非空循环链表a1a2.headan注意头指针和表头结点的区别38第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作循环链表特点：Z从表中任一结点出发，均可以找到其它所有结点；Z在任何情况下，带有表头结点的循环链表中至少有一个结点存在，从而使空表和非空表运算统一。循环链表运算与单链表区别：9对单链表进行操作时，要判断是否是表尾，即指针是否

31、为NULL；9而对循环链表操作时，要判断是否是头指针。39第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作6.3.2 栈 定义：栈是只能在表的一端进行插入和删除运算的线性表。 通常将允许插入和删除运算的一端称为栈顶(top)，另一端称为栈底(bottom) 不含元素的栈称为空栈。 向栈中插入元素称为入栈。 从栈中删除元素称为出栈。40第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作 设有一个栈S=a1,a2,an，入栈顺序是a1、a2最后是an n

32、。栈的状态如图所示： a1a2an栈底栈底bottombottom栈顶栈顶toptop入栈入栈出栈出栈栈特点：栈特点：后进先出后进先出。 故也称为“先进后出”表或“后进先出”表 41第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作栈的基本运算 栈初始化：构造一个空栈。 空栈判断：判断栈是否为空。 入栈：在栈顶插入一个元素。 出栈：在栈顶删除一个元素。 读栈：仅读取栈顶数据，并不删除元素。42第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作栈的顺序存

33、储 设用变量top表示栈顶位置，用n表示栈中最多能容纳元素的个数。 栈顺序存储结构是用一块连续存储区域存放栈中元素。连续区域的低地址一端作为栈底，栈底固定不变。43第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作入栈运算S1：如果top=n，则栈已满，提示入栈失败(栈“上溢”错误)，并结束入栈；S2：top+1 top；S3：将新元素放在当前栈顶位置(top)上。 a1 a2a3bottomtopa444第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心

34、制作出栈运算S1：如果top=0，则栈为空，提示出栈失败(栈“下溢”错误)，并结束出栈；S2：将当前栈顶(top)元素赋给一个变量；S3：top 1 top。a3top a1 a2bottom45第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作 例如，容量为6的栈中已有3个元素,如图所示：123456A AC CB BbottomtopX、Y两个元素先后入栈X XY Y元素Y出栈46第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作6.3.3 队 列

35、 允许在一端进行插入、而在另一端进行删除的线性表，允许插入的一端称为队尾，允许删除的一端称为队头。入队退队队尾队尾abc队头队头47第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作队列的基本运算初始化队列空队列判断入队运算出队运算读队头元素队列长度48第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作队列顺序存储及其常用运算队列的特点: 先进先出 入队和出队运算时队头和队尾位置要发生变化 队头队头 front(指向第一个元素的前一个单元位置)队尾队尾

36、 rear(指向最后一个元素的位置)队列中容纳元素个数为n49第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作创建一个空队列,并令 front= rear=-11.初始化队列front - -1 1 2 2 0 0 1 1rear50第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作2. 入队运算S1： 如 果 rear=n-1，则队列已满，提示入队失败(队列“上溢”错误)，并结束入队；S2：rear+1 rear；S3：将新元素放在当前队列位置(r

37、ear)上frontrear - -1 1 2 2 0 0 1 1A AB BC C51第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作3. 退队运算S1：如果front=rear，则队列已空,提示退队失败(队列“下溢”错误),并结束退队；S2：front+1 front;S3：取front所指元素frontrear - -1 1 2 2 0 0 1 1A AB BC C此时虽然队列有空位置，但也不能插入新结点。52第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教

38、学与研究中心制作循环队列将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，这样可以把退队的空间利用起来。0 02 23 31 10 02 21 13 34 453第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作循环队列的运算1.初始化队列创建一个空队列,并令 front= rear=01 13 3 2 24 40 0frontrear54第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作S1: 先判断队列是否已满，若队满则入队失败，否

39、则元素入队S2: (rear+1)%nrear当 rear+1=n时 ， 0 rearS3:将新元素放在当前队尾位置（rear）。循环队列的运算2.入队运算1 13 32 24 40 0 rear fronta ab bc c例如：插入结点a,b,c显然,再插入两个结点后front=rearfront=rear,此时为满队列55第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作循环队列的运算3.出队(退队)运算S1: 先判断队列是否为空，若队空则出队失败（上溢）S2: (front+1)%nfront当front+1=n时

40、 ， 0 front0 02 21 13 34 4a ab bc c rear front例如：删除结点a显然,再删除两个结点后front=rearfront=rear,此时为空队列因此：通常需要增加一个变量用来标识当front=rear时，队列是满还是空。56第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作6.3.5 树 树是一种常用的非线性结构，树是由n(n0)个结点组成的有限集合。当n=0时，称为空树；否则，有且仅有一个根结点，当n1时，其余结点被分成m(m0)个互不相交的子集T1，T2,.,Tm，每个子集又是一棵

41、树。 树是递归定义的，即一棵树由根及若干子树构成，每棵子树又是由更小的子树构成。 57第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作结点的度：一个结点所拥有后件个数树的度：树中所有结点的最大度 AEBCDFGHIJKL根子结点叶结点58第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作 AEBCDFGHIJKL结点的层次从根结点算起，根结点在第一层，根的直接后继结点在第二层，同一层上所有结点的后继结点均在下一层。 1 1 2 2 3 3 4 4树中

42、结点的最大层次称为树的深度或高度 59第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作6.3.6 二叉树非空二叉树有且只有一个根结点；每个结点最多有两棵子树, 且有左右之分 二叉树是另一种树形结构，每个结点最多只有两个后件(即最大度为2)。特点：60第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作二叉树有五种基本形态 空二叉树只有根结点只有左子树有左和右子树只有右子树A AT TX XC CZ ZY YB BP P深度为4的二叉树A AT TX X

43、C CZ ZY YB BP P深度为4的二叉树61第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作二叉树基本性质 性质一：在二叉树的第i层上，最多有2i-1i-1个结点(i1).性质二：深度为k的二叉树最多有2k k-1个结点(k1). 性质三：对于任意一棵二叉树，度为0的结点(即叶子结点)总比度为2的结点多一个.62第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作满二叉树 如果一个深度为k的二叉树拥有2k k-1个结点，则称它为满二叉树。每一层的

44、结点数都达到最大值,叶子结点都在最下面的同一层上 完全二叉树 一棵深度为k的二叉树, 如果第一层到第k-1层是一棵满二叉树, 第k层上的结点数没有达到最大值2k-1k-1, 但这些结点都满放在该层最左边, 则称此二叉树为完全二叉树。 如果某个结点没有左子树,则它一定没有右子树63第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作注：满二叉树是完全二叉树，但完全二叉树不一定是满二叉树。A AT TX XC CE EM MB BP P15个结点的满二叉树S SD DN NF FR RY YQ Q64第六章第六章 算法与数据结构

45、基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作完全二叉树性质：12个结点的完全二叉树A AT TX XC CR RB BP PS SE EG GF FY Y性质一：具有n个结点的完全二叉树的深度为 log2n+1。其中，log2n 表示取log2n的整数部分。65第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作完全二叉树性质：性质二：在有n个结点的完全二叉树中, 将所有结点按从上到下, 从左到右的顺序用自然数1, 2, , n进行编号, 则对于编号为k的结点有如下结论：k=

46、1时, 该结点为根结点。k1时, 该结点的父结点编号为int(k/2)。2k=n时, 编号为k的结点的左子结点编号为2k, 否则无左子结点。2k+1=n时, 编号为k的结点的右子结点编号为 2k+1, 否则无右子结点。A AT TX XC CR RB BP PS SE EQ QF FY Y1 12 23 34 45 56 67 7101011119 98 8121266第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作二叉树的顺序存储二叉树顺序存储是指用一组连续存储单元存储二叉树中的结点。结点存储顺序是按着从上到下、从左到

47、右顺序。 ACBEGDFABCDE FG 1 2 3 4 5 6 7 按照完全二叉树每个结点编号的顺序存放结点,通过结点的编号准确地反映结点之间的逻辑关系。1 12 23 34 45 56 67 767第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作非完全二叉树顺序存储ACBEGFABC E FG 1 2 3 4 5 6 7 显 然 ,顺序结构适用于完全二叉树，对于非完全二叉树，会浪费许多存储空间。68第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制

48、作二叉树链式存储二叉树每个结点由数据域和指针域组成 。两个指针域： o 一个用于指向左子结点 o 一个用于指向右子结点 常见二叉树结点结构如图： LChildDataRChild数据域 存储左子结点的存储地址存储右子结点的存储地址 69第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作A AT TX XC CZ ZY YB BP P深度为深度为4 4的二叉树的二叉树二叉树链式存储A AT TX XC CZ ZY YB BP P深度为深度为4 4的的二叉树二叉树A AT TX XB BC CP PZ ZY YBTBT70第六

49、章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作二叉树的遍历 遍历二叉树是指按照某种顺序访问二叉树中每个结点的过程，每个结点被访问一次且仅一次。 根据对根访问的次序，二叉树的遍历分为先序遍历、中序遍历和后序遍历。71第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作先序遍历 访问根结点 先序遍历左子树 先序遍历右子树A AT TX XC CZ ZY YB BP P深度为4的二叉树A A遍历结果：T TB BZ ZX XC CP PY Y因为左子树因为左子

50、树空，故遍历空，故遍历右子树右子树72第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作中序遍历 中序遍历左子树 访问根结点 中序遍历右子树A AT TX XC CZ ZY YB BP P深度为4的二叉树A AT TZ ZB BC CX XY YP P因为左子树空因为左子树空遍历结果：73第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作 后序遍历左子树 后序遍历右子树 访问根结点后序遍历A AT TX XC CZ ZY YB BP P深度为4的二叉树

51、遍历结果：A AT TX XC CZ ZY YB BP P深度为4的二叉树A AT TZ ZB BC CX XY YP P因为左子树因为左子树空，故遍历空，故遍历右子树右子树74第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作6.4 典型算法对非数值型数据通常有插入、删除、查找和排序等操作。其中查找和排序是数据处理中比较重要的算法。 查找又称检索，是指在数据集合中查找某个数据元素的过程。若存在这样数据元素,则查找成功；否则，查找失败。 6.4.1 6.4.1 查找查找75第六章第六章 算法与数据结构基础算法与数据结构基础

52、吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作1 顺序查找适用于线性表，其基本方法是 ：从线性表中第一个元素开始，依次将线性表中的元素与给定值进行比较。若相等，则查找成功；若直到最后一个元素，还没找到与给定值相等的元素，则查找失败。 76第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作例如：在顺序表( 88, 15, 23, 80, 63, 8, 86, 46, 71, 101 )中, 查找 值为71的数据元素。从线性表中第一个元素88开始, 依次将 线性表中元素与71进行比较。直到第九个元素为

53、71, 查找成功。 特点：顺序查找算法简单,但是执行效率较低 在下列两种情况下,只能使用顺序查找法： 线性表是线性链表。 线性表是顺序表，但表中元素无序排列。 此题比较了9次77第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作2 二分查找又称折半查找,要求被查找的表采用顺序存储结构且数据元素按数据值升序或降序排列,即二分查找法只适用于有序表。 基本思想是(设顺序表升序排列)：P将给定值与中间位置元素比较,若相等,则 查找成功；P若给定值小于元素值,则继续对前半部分 再进行折半查找；P若给定值大于中间位置元素值,则继续对后

54、半部分再进行折半查找。 78第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作例：在有序顺序表(8，15，23，46，63，71，80，86，88，101)中，用折半查找法查找值为 71 的数据元素。 key=71 8 15 23 46 63 71 80 86 88 101 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 107 8 9 10第一次查找mid=5第二次查找mid=8第三次查找mid=6 71 80 86 88 101 6 7 8 6 7 8 9 109 106371,6371,8671,故在前半

55、部分进行折半查找故在前半部分进行折半查找 71 80 6 76 7 71=71,71=71,查找成功查找成功 79第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作2.排序算法 排序是将一组无序数据按值递增(或递减)进行重新排列。 三类基本排序方法 交换排序法选择排序法插入排序法80第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作1交换排序法在排序过程中, 通过数据元素之间不断地进行比较与交换, 最终达到排序目的。冒泡排序法的基本思想是： 对所有相邻

56、元素进行比较，若逆顺，则将其交换，最终达到有序化。 81第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作交换排序法原序列：原序列：4242232316164747111145451313494942422323161647471111454513134949第第1 1 遍遍第第2 2遍遍第第3 3遍遍第第4 4遍遍第第5 5遍遍第第6 6遍遍2323161642421111454547471313494916162323111142424545131347474949161623231111424245451313474

57、74949111123231616131345454242474749491111131316162323454542424747494982第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作2选择排序法简单选择排序法的基本思想是：1扫描整个序列，从中选出最小元素，将它 交换到最前面；2再从剩余子序列中，选出最小元素，交换 到子序列最前面。3依次类推，直到子序列长度为1为止。 每次从待排序数据序列中，选择出最小元素并定位到待排序(升序)序列最前面。 由于每遍扫描只能确定一个元素位置，所以对于长度为n的序列，需要扫描n-1遍

58、才能将每个元素位置确定下来。83第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作原序列：原序列：42422323161627271111454513134949选择排序法第第1 1遍选择遍选择4242232316162727111145451313494911112323161627274242454513134949第第2 2遍选择遍选择11111313161627274242454523234949第第3 3遍选择遍选择11111313161627274242454523234949第第4 4遍选择遍选择111113

59、13161623234242454527274949第第5 5遍选择遍选择11111313161623232727454542424949第第6 6遍选择遍选择11111313161623232727424245454949第第7 7遍选择遍选择84第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作3插入排序法 插入排序是不断地将待排序的元素插入到前面的有序序列中, 直至所有元素都进入有序序列。 简单插入排序又称直接插入排序,基本思想是：将由n个元素组成的序列分成前后两个子序列, 前者为有序序列, 后者为无序序列。85第六

60、章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作将待排序序列中第一个元素作为有序序列，将第二个元素插入到有序序列中，形成由两个元素组成的有序序列。再将第三个元素插入到有序序列中。依此类推，直到最后一个元素插入到有序序列中，形成n个元素组成的有序序列。简单插入排序的步骤：86第六章第六章 算法与数据结构基础算法与数据结构基础吉林大学公共计算机教学与研究中心制作吉林大学公共计算机教学与研究中心制作插入排序法原序列：原序列：42422323161627271111454513134949第第1 1遍遍23234242161627271111454513134949第第2 2遍遍16162323424227271111454513134949第第3 3遍遍16162323272742421111454513134949第第4 4遍遍11111616232327274242454513134949第第5 5遍遍11111616232327274242454513134949第第6 6遍遍11111616232327274242454549491313第第7 7遍遍1313161623232727424245454949111187