1、大学计算机基础：第7章-数据结构、算法及程序设计本章概要本章概要(6(6学时学时)1.1.数据结构的基本概念数据结构的基本概念2.2.算法的基本概念算法的基本概念3.3.典型的数据结构典型的数据结构4.4.典型算法典型算法2/773/777.17.1 数据结构基本概念数据结构基本概念 1.1.数据结构示例数据结构示例4/77 2.2.数据结构的定义数据结构的定义 数据结构是指具有数据结构是指具有相同特征相同特征、相互之间、相互之间有有关联关联的的数据数据集合。集合。数据数据也称为也称为数据元素数据元素或或结点结点，现实世界现实世界中每个对象都可以映像成数据元素。中每个对象都可以映像成数据元素。
2、数据结构中数据元素都具有某种数据结构中数据元素都具有某种共同特征共同特征数据结构中数据元素之间存在着某种数据结构中数据元素之间存在着某种关系关系 5/77学生信息学生信息数据结构数据结构向量2 2，4343，6868，4545，3232是数据结构季度季度名称组成的集合是数据结构：名称组成的集合是数据结构：春，夏，秋，冬春，夏，秋，冬 家庭成员家庭成员 祖父、父亲、儿子祖父、父亲、儿子 是数据结构是数据结构每个数据元素由一个数据项组成，每个数据元素由一个数据项组成，数据元素之间有数据元素之间有位置上的前后位置上的前后关系关系 每个数据元素由一个数据项组成，每个数据元素由一个数据项组成，数据元素之
3、间有数据元素之间有层次上的高低层次上的高低关系关系 每个数据每个数据元素元素由由多个数据项多个数据项组成组成6/77 数据结构数据结构是指带有是指带有结构特性结构特性的的数数据元素集合据元素集合。主要研究：主要研究：数据数据逻辑结构逻辑结构数据数据存储结构存储结构(物理结构物理结构)对数据所进行的对数据所进行的操作操作数据处理时数据在计算机中的数据处理时数据在计算机中的存储关系存储关系数据集合中数据元素之间所固有的数据集合中数据元素之间所固有的关系关系即即算法算法7/773.3.数据逻辑结构数据逻辑结构 数据结构中数据元素之间所数据结构中数据元素之间所固有固有的关的关系描述成系描述成前后件前后
4、件(前驱与后继前驱与后继)关系。数据关系。数据之间前后件关系是它们之间的之间前后件关系是它们之间的逻辑关系逻辑关系，与它们在计算机中的存储位置无关，因此与它们在计算机中的存储位置无关，因此将这种关系称为将这种关系称为逻辑结构逻辑结构。一个数据结构可以表示为：一个数据结构可以表示为：S S=(=(D D,R R)季节数据结构可以定义成季节数据结构可以定义成 S=(D,R)S=(D,R)其中其中:D=:D=春春,秋秋,冬冬,夏夏 R=(R=(春春,夏夏),(),(夏夏,秋秋),(),(秋秋,冬冬)8/77数据结构的表示数据结构的表示S S表示数据结构表示数据结构D D数据元素集合数据元素集合 数据
5、元素之间的前数据元素之间的前 后件关系的集合后件关系的集合9/77一般来说，数据之间有一般来说，数据之间有集合，线性，集合，线性，树型树型和和图形图形 4 4 种基本逻辑结构。种基本逻辑结构。是一种是一种松散松散结构，数据元素之间的结构，数据元素之间的关系只是同属于一个集合，可以用其他结关系只是同属于一个集合，可以用其他结构来表示。构来表示。集集 合合10/77数据元素之间是数据元素之间是一对一一对一的关系的关系除第一个结点无前件外除第一个结点无前件外,其他结点都其他结点都 只只有一个前件有一个前件除最后一个结点无后件外除最后一个结点无后件外,其他结点都其他结点都只有一个后件只有一个后件例如例
6、如:春春夏夏冬冬秋秋一般来说，数据之间有一般来说，数据之间有集合，线性，集合，线性，树型树型和和图形图形 4 4 种基本逻辑结构。种基本逻辑结构。11/77数据之间存在数据之间存在一对多一对多的关系的关系一个结点最多有一个一个结点最多有一个前件前件,可以有多个后件可以有多个后件前件与后件之间有前件与后件之间有层层次次关系关系一般来说，数据之间有一般来说，数据之间有集合，线性，集合，线性，树型树型和和图形图形 4 4 种基本逻辑结构。种基本逻辑结构。12/77数据元素之间存在数据元素之间存在多多对多对多的关系的关系一个结点可以有多个一个结点可以有多个前件和多个后件前件和多个后件一般来说，数据之间
7、有一般来说，数据之间有集合，线性，集合，线性，树型树型和和图形图形 4 4 种基本逻辑结构。种基本逻辑结构。13/774.4.数据物理结构数据物理结构数据在计算机存储器中的数据在计算机存储器中的存储方式存储方式称称为数据为数据物理结构物理结构(数据存储结构数据存储结构)。在数据存储结构中，不仅要存放各个在数据存储结构中，不仅要存放各个数据元素信息数据元素信息，还要存放数据元素之间，还要存放数据元素之间前前后件关系信息后件关系信息。数据元素在计算机中通常。数据元素在计算机中通常有四种存储方式：有四种存储方式：、和和。14/77顺序存储结构顺序存储结构 顺序存储结构是在内存中开辟一块顺序存储结构是
8、在内存中开辟一块连连续续内存单元用于存放数据，逻辑上相邻的内存单元用于存放数据，逻辑上相邻的结点在物理位置上也相邻。结点在物理位置上也相邻。即：即：结点之间的逻辑关系由存储单元结点之间的逻辑关系由存储单元的相邻关系来体现。的相邻关系来体现。例如：有如下顺序关系例如：有如下顺序关系 a,b,c,d a,b,c,d a a地址地址2000H2000H2001H2001Hc c2002H2002H2003H2003Hd d数据数据b b如果在如果在b b和和c c之间增加新数据之间增加新数据x x构成构成 a,b,x,c,da,b,x,c,d的顺序关系的顺序关系,应应该如何存储？该如何存储？15/7
9、7 链式存储结构链式存储结构链式存储结构中，结点由两部分组成：链式存储结构中，结点由两部分组成：用于存放数据元素用于存放数据元素(数据域数据域)用于存放前件或后件的存储地址用于存放前件或后件的存储地址(指针域指针域)即即:通过指针反映数据元素之间的逻辑关系通过指针反映数据元素之间的逻辑关系例如：有如下顺序关系例如：有如下顺序关系 a,b,c a,b,c a a20002000b bc c3001300110031003300130011003100316/77顺序存储结构与链式存储结构比较顺序存储结构与链式存储结构比较顺序存储结构：顺序存储结构：优点：优点：每个结点占用存储空间最少每个结点占用
10、存储空间最少 缺点：缺点：如果数据元素很多，则可能找不到一如果数据元素很多，则可能找不到一 块足够大的连续存储单元块足够大的连续存储单元 不能很好利用存储单元不能很好利用存储单元,容易产生碎片容易产生碎片链式存储结构链式存储结构:优点：优点：充分利用所有存储单元充分利用所有存储单元缺点：缺点：每个结点占用较多存储单元每个结点占用较多存储单元 17/777.2.17.2.1 算法的定义算法的定义算法算法就是操作步骤，是解决就是操作步骤，是解决“做什么做什么”和和“怎么做怎么做”的问题。算法是程序的灵魂，的问题。算法是程序的灵魂，广义来说，广义来说，为解决一个问题而采取的方法和为解决一个问题而采取
11、的方法和步骤步骤就称为算法。就称为算法。算法是算法是定义在逻辑结构上定义在逻辑结构上的操作，的操作，独立独立于计算机，但算法的实现于计算机，但算法的实现依赖依赖于数于数据的存储结构。据的存储结构。18/77算法的特征算法的特征可行性可行性确定性确定性有穷性有穷性输入输入输出输出 采取的方法和步骤采取的方法和步骤可可行行，结构另人满意。，结构另人满意。算法中的每一个步骤都必算法中的每一个步骤都必须须确定确定，不能产生歧义。，不能产生歧义。算法得到的算法得到的结果结果就是输出就是输出,没没有输出的算法是没有意义的有输出的算法是没有意义的,一个一个算法应该算法应该有一个或多个输出有一个或多个输出。算
12、法必须由算法必须由有限有限步步组成，并能在有效组成，并能在有效时间内完成。时间内完成。执行算法时从外界取得必执行算法时从外界取得必要的信息。一个算法可以要的信息。一个算法可以有零有零或多个输入或多个输入。7.2.2 7.2.2 算法的描述方法算法的描述方法 用于描述算法的工具很多，通常有用于描述算法的工具很多，通常有自自然语言然语言、伪代码伪代码、流程图流程图和和N-SN-S图图等工具。等工具。19/77 例如：例如：计算计算1001nns20/777.2.3 7.2.3 算法的评价算法的评价 在计算机程序设计中，某一任务的算在计算机程序设计中，某一任务的算法设计得优与劣，将直接影响程序的法设
13、计得优与劣，将直接影响程序的运行运行效率效率、稳定性稳定性和和可维护性可维护性。通常从以下。通常从以下4 4个个方面评价一个算法。方面评价一个算法。U正确性正确性U可读性可读性U健壮性健壮性U执行效率执行效率算法本身没有语法错误算法本身没有语法错误,执行时输执行时输入正确数据能够得到正确结果入正确数据能够得到正确结果算法要容易理解和阅读算法要容易理解和阅读,容易实现容易实现,同时也要便于程序维护和完善同时也要便于程序维护和完善指算法执行的指算法执行的时间时间性能和性能和空间空间性能性能算法能够对输入的各种数据给予适算法能够对输入的各种数据给予适当的提示和处理当的提示和处理 。多个算法解决同一个
14、问题时多个算法解决同一个问题时,执行时间短的算法时间效率执行时间短的算法时间效率高高;占用存储空间少的算法空占用存储空间少的算法空间效率高。间效率高。21/777.3 7.3 线性表结构线性表结构数据数据逻辑逻辑结构分为：结构分为：线性结构线性结构非线性结构非线性结构有且只有一个开始结点和有且只有一个开始结点和一个终端结点，并且每个一个终端结点，并且每个结点最多只有一个前件和结点最多只有一个前件和一个后件，线性结构也称一个后件，线性结构也称为为线性表线性表。栈栈、队列队列、数数组组和和串串等是特殊线性表等是特殊线性表非线性结构包括非线性结构包括树树和和图图22/777.3.1 7.3.1 线性
15、表线性表 线性表是一组线性表是一组特征相同数据特征相同数据的的有限有限序列，序列，表示为表示为 L=(a L=(a1 1,a,a2 2,a,a3 3 a an n)。线性表中数据元素个数线性表中数据元素个数n(n0)n(n0)称为线称为线性表性表长度长度。当。当n=0n=0时时,称为称为空表空表。在。在非空线非空线性表性表中，每个数据元素都有一个确定位置，中，每个数据元素都有一个确定位置，其位置取决于它的其位置取决于它的序号序号。线性表通常采用线性表通常采用顺序存储结构顺序存储结构或或链式存链式存储结构储结构。除除a a1 1无前件外无前件外,其它任意数据元素其它任意数据元素a ai i有且只
16、有一个前有且只有一个前件件a ai-1i-1 除除a an n无后件外无后件外,其它任意数据元素其它任意数据元素a ai i有且只有一个后有且只有一个后件件a ai+1i+1a a1 1是第一个元素，是第一个元素，a a2 2 是第二个元素，是第二个元素，a an n是最后一个元素是最后一个元素顺序表顺序表链表链表23/77线性表线性表顺序存储结构顺序存储结构具有以下两个基本特点：具有以下两个基本特点：线性表中所有元素占用一段线性表中所有元素占用一段连续连续的存储空的存储空间。间。线性表中各元素在存储空间中线性表中各元素在存储空间中按逻辑顺序按逻辑顺序依次存放依次存放，即线性表的逻辑结构与存储
17、结，即线性表的逻辑结构与存储结构相构相一致一致。顺序表中前后两个元素在存储空间中是顺序表中前后两个元素在存储空间中是紧邻紧邻的，前件元素一定存放在后件元素的前面。的，前件元素一定存放在后件元素的前面。线性表的顺序存储线性表的顺序存储24/77例如：例如：线性结构线性结构 a a1 1，a a2 2，a a3 3，其中每个数，其中每个数据元素占据元素占2 2个存储空间，假设存储个存储空间，假设存储a a1 1的首地址的首地址为为20002000。20002000a a1 1占占2 2个字节个字节a a2 2a a3 32004200420022002占占2 2个字节个字节占占2 2个字节个字节存
18、储地址：存储地址：结论：结论：假设一个数据元素占用假设一个数据元素占用d d个字节个字节,线性表的线性表的首地址首地址Addr(aAddr(a1 1)为为K K，则存储任意一个数据元素，则存储任意一个数据元素a ai i的首地址为的首地址为:Addr(a Addr(ai i)=Addr(a)=Addr(a1 1)+(i-1)+(i-1)d=K+(i-1)d=K+(i-1)d d 其中其中 1 i n 1 i n 优点：优点：可以方便地随机读取表中任意元素可以方便地随机读取表中任意元素缺点：缺点：插入和删除运算需要移动大量元素，浪费大插入和删除运算需要移动大量元素，浪费大量时间，时间效率较低。量
19、时间，时间效率较低。25/77线性表的链式存储线性表的链式存储 用一组存储单元用一组存储单元(可以连续，也可以不可以连续，也可以不连续连续)存储线性表中数据元素。为了反映数存储线性表中数据元素。为了反映数据元素之间的据元素之间的逻辑关系逻辑关系，每个数据元素由，每个数据元素由两部分组成：两部分组成：存放数据元素的内容存放数据元素的内容(数据域数据域)存放前件或后件的存储地址存放前件或后件的存储地址(指针域指针域)结点之间逻辑关系结点之间逻辑关系由由指针域指针域来确定来确定26/77线性表的单链表存储线性表的单链表存储定义：每个结点只有定义：每个结点只有一个一个指针域的链表。指针域的链表。a a
20、1 1 a a2 2a a3 3a a4 4a a5 5 headhead每个单链表都有一个每个单链表都有一个头指针头指针，存放表中，存放表中第一个结点的存储地址。第一个结点的存储地址。每个结点指针域存放每个结点指针域存放后件后件结点的存储地结点的存储地址，最后一个结点无后件结点，指针域址，最后一个结点无后件结点，指针域为空，用为空，用NULLNULL或或 表示。表示。a a1 1,a,a2 2,a,a3 3,a,a4 4,a,a5 5 27/77线性表的循环链表存储线性表的循环链表存储 循环链表中增设一个循环链表中增设一个表头结点表头结点，其数，其数据域的值可以任意或根据情况来设置，指据域的
21、值可以任意或根据情况来设置，指针域指向针域指向第一个第一个结点。结点。将单链表最后一个结点的空指针域改为将单链表最后一个结点的空指针域改为指向该链表的第一个结点，即指向该链表的第一个结点，即首尾相连首尾相连。headhead非空循环链表非空循环链表a a1a a2.headheada an注意注意头指针头指针和和表表头结点头结点的区别的区别空循环链表空循环链表28/77循环链表特点：循环链表特点：从表中从表中任一结点任一结点出发，均可以找到其它所有出发，均可以找到其它所有结点；结点；在任何情况下，带有表头结点的循环链表中在任何情况下，带有表头结点的循环链表中至少有一个结点存在至少有一个结点存在
22、，从而使空表和非空表，从而使空表和非空表运算统一。运算统一。循环链表运算与单链表区别：循环链表运算与单链表区别：对单链表进行操作时，要判断是否是表尾，对单链表进行操作时，要判断是否是表尾，即指针是否为即指针是否为NULLNULL；而对循环链表操作时，要判断是否是而对循环链表操作时，要判断是否是头指针头指针。29/777.3.2 7.3.2 栈栈 定义：栈是只能在表的定义：栈是只能在表的一端一端进行插入进行插入和删除运算的和删除运算的线性表线性表。将允许插入和删除运算的一端称为将允许插入和删除运算的一端称为栈顶栈顶(top)(top)，另一端称为，另一端称为栈底栈底(bottom)(bottom
23、)不含不含元素的栈元素的栈向栈中向栈中插入插入元素元素从栈中从栈中删除删除元素元素30/77 设有一个栈设有一个栈S=aS=a1 1,a,a2 2,a,an n，入栈顺序是，入栈顺序是a a1 1、a a2 2最后是最后是a an n。栈的状态如图所示：。栈的状态如图所示：a1 a2 an栈底栈底bottombottom栈顶栈顶toptop入栈入栈出栈出栈栈特点：栈特点：。故也称为故也称为“先先进后出进后出”表或表或“后后进先出进先出”表表 31/77栈的基本运算栈的基本运算 栈初始化栈初始化 空栈判断空栈判断 入栈入栈 出栈出栈 读栈读栈构造一个构造一个空栈空栈判断栈是否为判断栈是否为空空在
24、栈顶在栈顶插入插入一个元素一个元素在栈顶在栈顶删除删除一个元素一个元素仅读取栈顶数据，仅读取栈顶数据，并不删除并不删除元素元素32/77栈的顺序存储栈的顺序存储栈栈顺序存储结构顺序存储结构是用一块是用一块连续连续存存储区域存放栈中元素。连续区域的储区域存放栈中元素。连续区域的低低地址地址一端作为一端作为栈底栈底，栈底，栈底固定不变固定不变。设用变量设用变量toptop表示栈顶位置，用表示栈顶位置，用n n表示栈中最多能容纳元素的个数。表示栈中最多能容纳元素的个数。33/77入栈运算入栈运算 a a1 1 a a2 2a a3 3bottombottomtoptopa a4 4S1S1：如果：如
25、果top=ntop=n，则，则栈已栈已满满，提示入栈失，提示入栈失败败(栈栈“上溢上溢”错误错误)，并结束入栈；并结束入栈；S2S2：top+1 top+1 top top；S3S3：将新元素放在当：将新元素放在当前栈顶位置前栈顶位置(top)(top)上。上。34/77出栈运算出栈运算a a3 3toptop a a1 1 a a2 2bottombottomS1S1：如果如果top=0top=0，则栈，则栈为为空空，提示出栈失败，提示出栈失败(栈栈“下溢下溢”错误错误)，并，并结束出栈；结束出栈；S2S2：将当前栈顶将当前栈顶(top)(top)元素赋给一个变量；元素赋给一个变量；S3S3
26、：top-1 top-1 top top35/77 例如，容量为6的栈中已有3个元素,如图所示：123456A AC CB BbottombottomtoptopX X、Y Y两个元素两个元素先后入栈先后入栈X XY Y元素元素Y Y出栈出栈36/777.3.3 7.3.3 队队 列列 允许在一端进行插入、而在另一允许在一端进行插入、而在另一端进行删除的端进行删除的线性表线性表，允许插入的一，允许插入的一端称为端称为队尾队尾，允许删除的一端称为，允许删除的一端称为队队头头。入队入队退队退队队尾队尾a ab bc c队头队头37/77队列的基本运算队列的基本运算初始化队列初始化队列空队列判断空队
27、列判断入队运算入队运算出队运算出队运算读队头元素读队头元素队列长度队列长度创建一个创建一个空空队列队列判断队列是否为判断队列是否为空空在在队尾插入队尾插入一个元素一个元素在在队头删除队头删除一个元素一个元素读取队头元素读取队头元素赋给一个指定赋给一个指定变量，变量，不删除不删除队头元素队头元素求队列中元素求队列中元素个数个数38/77队列顺序存储及其常用运算队列顺序存储及其常用运算队列的特点队列的特点:先进先出先进先出 入队和出队运算时队头和队尾位置入队和出队运算时队头和队尾位置要发生变化要发生变化 front front(指向第一个元素的前一个单元位置指向第一个元素的前一个单元位置)rear
28、 rear(指向最后一个元素的位置指向最后一个元素的位置)队列中容纳元素队列中容纳元素 的个数为的个数为n n39/77创建一个创建一个空空队列队列,并令并令 front=rear=front=rear=frontfront -1-1 2 2 0 0 1 1rearrear1.1.初始化队列初始化队列40/772.2.入队运算入队运算frontfrontrearrear -1 -1 2 2 0 0 1 1A AB BC CS1S1：如果：如果rear=n-1rear=n-1，则队列已则队列已满满，入队，入队失败失败(“(“上溢上溢”错错误误)，并结束入队，并结束入队S2S2：rear+1 re
29、ar+1 rearrearS3S3：将新元素放在：将新元素放在当前队列位置当前队列位置(rear)(rear)上上41/773.3.退队运算退队运算frontfrontrearrear -1 -1 2 2 0 0 1 1A AB BC CS1S1：如：如front=rearfront=rear，则队列已则队列已空空,退队失退队失败败(“(“下溢下溢”错误错误),),并并结束退队；结束退队；S2S2：front+1front+1front;front;S3S3：取：取frontfront所指元素所指元素此时虽然队列有空此时虽然队列有空位置，但也位置，但也不能插不能插入入新结点。新结点。假溢出现象
30、假溢出现象42/777.4.2 7.4.2 二叉树二叉树二叉树二叉树是另一种树形结构，每个结点是另一种树形结构，每个结点最多只有两个后件最多只有两个后件(即即最大度为最大度为2 2)。特点：特点：非空二叉树有且只有一个根结点；非空二叉树有且只有一个根结点；每个结点最多有两棵子树每个结点最多有两棵子树,且且有左右之有左右之分分A AT TX XC CZ ZY YB BP P43/77二叉树有五种基本形态二叉树有五种基本形态 空二叉树空二叉树只有根结点只有根结点只有左子树只有左子树有左和右子树有左和右子树只有右子树只有右子树44/77二叉树基本性质二叉树基本性质 性质一：性质一：在二叉树的第在二叉
31、树的第i i层上，最多有层上，最多有2 2i-1i-1个结点个结点(i1).(i1).性质二：性质二：深度为深度为k k的二叉树最多有的二叉树最多有2 2k k-1-1个结点个结点(k1).(k1).性质三：性质三：对于任意一棵二叉树，度为对于任意一棵二叉树，度为0 0的结点的结点(即叶子即叶子结点结点)总比度为总比度为2 2的结点多一个的结点多一个.45/77满满二叉树二叉树 如果一个如果一个深度为深度为k k的二叉树拥有的二叉树拥有2 2k k-1-1个个结点，则称它为结点，则称它为满二叉树满二叉树。每一层的结点数都达到每一层的结点数都达到最大值最大值,叶子结点都在叶子结点都在最下面的同一
32、层上最下面的同一层上 完全二叉树完全二叉树 一棵深度为一棵深度为k k的二叉树的二叉树,如果第一层到如果第一层到第第k-1k-1层是一棵满二叉树层是一棵满二叉树,第第k k层上的结点层上的结点数没有达到最大值数没有达到最大值2 2k-1k-1,但这些结点都满放但这些结点都满放在该层在该层最左边最左边,则称此二叉树为则称此二叉树为完全二叉完全二叉树树。如果某个结点没有左子如果某个结点没有左子树树,则它一定没有右子树则它一定没有右子树 46/77注：注：满二叉树是完全二叉树，但完全满二叉树是完全二叉树，但完全二叉树不一定是满二叉树。二叉树不一定是满二叉树。A AT TX XC CE EMMB BP
33、 P1515个结点的满二叉树个结点的满二叉树S SD DNNF FR RY YQQ47/77完全二叉树性质：完全二叉树性质：1212个结点的完全二叉树个结点的完全二叉树A AT TX XC CR RB BP PS SE EG GF FY Y性质一：性质一：具有具有n n个结点的完全二叉树的深度为个结点的完全二叉树的深度为 loglog2 2n n+1+1。其中，。其中，loglog2 2n n 表示取表示取loglog2 2n n的的整数部分整数部分。48/77完全二叉树性质：完全二叉树性质：性质性质二：二：在有在有n n个结点的完全二叉树中个结点的完全二叉树中,将所有结将所有结点按从上到下点
34、按从上到下,从左到右的顺序用自然数从左到右的顺序用自然数1,2,n1,2,n进行编号进行编号,则对于编号为则对于编号为k k的结的结点有如下结论：点有如下结论：k=1k=1时时,该结点为根结点。该结点为根结点。k1k1时时,该结点的父结点编号为该结点的父结点编号为int(k/2)int(k/2)。2k=n2k=n时时,编号为编号为k k的结点的左子结点编号为的结点的左子结点编号为2k,2k,否则无左子结点。否则无左子结点。2k+1=n2k+1=n时时,编号为编号为k k的结点的右子结点编号为的结点的右子结点编号为 2k+1,2k+1,否则无右子结点。否则无右子结点。A AT TX XC CR
35、RB BP PS SE EQQF FY Y1 12 23 34 45 56 67 7101011 119 98 8121249/77二叉树的顺序存储二叉树的顺序存储 二叉树顺序存储是指用一组二叉树顺序存储是指用一组连续连续存储存储单元存储二叉树中的结点。结点存储顺序单元存储二叉树中的结点。结点存储顺序是是按着从上到下、从左到右顺序按着从上到下、从左到右顺序。A AC CB BE EG GD DF F 1 1 2 2 3 3 4 4 5 5 6 7 6 7 按照按照完全二叉树每个结点完全二叉树每个结点编号编号的的顺序存顺序存放结点放结点，通过通过结点的结点的编号编号准确地准确地反映反映结点之结点
36、之间的间的逻辑关系逻辑关系。1 12 23 34 45 56 67 750/77非完全二叉树顺序存储非完全二叉树顺序存储A AC CB BE EG GF F 1 1 2 2 3 3 4 4 5 5 6 7 6 7 显然显然,顺序顺序结构结构适用于完适用于完全二叉树全二叉树，对，对于非完全二叉于非完全二叉树，会树，会浪费浪费许许多多存储空间存储空间。二叉树每个结点由数据域和二叉树每个结点由数据域和指针域指针域组成。组成。51/77二叉树链式存储二叉树链式存储两个两个指针域：指针域：一个用于指向一个用于指向左子结点左子结点 一个用于指向一个用于指向右子结点右子结点 常见二叉树结点结构如图：常见二叉
37、树结点结构如图：数据域数据域 存储左子结点存储左子结点的存储地址的存储地址 存储右子结点存储右子结点的存储地址的存储地址 52/77A 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 YBTBT53/77二叉树的遍历二叉树的遍历遍历二叉树是指按照某种顺序遍历二叉树是指按照某种顺序访访问问二叉树中二叉树中每个每个结点的过程，每个结点的过程，每个结点被访问结点被访问一次一次且且仅一次仅一次。根据对根访问的次序，二叉
38、树的根据对根访问的次序，二叉树的遍历分为遍历分为先序遍历先序遍历、中序遍历中序遍历和和后后序遍历序遍历。54/77先序遍历先序遍历 访问根结点访问根结点 先序遍历左子树先序遍历左子树 先序遍历右子树先序遍历右子树A AT TX XC CZ ZY YB BP P深度为深度为4 4的二叉树的二叉树A A遍历结果：遍历结果：T TB BZ ZX XC CP PY Y因为左子树空，因为左子树空，故遍历右子树故遍历右子树55/77中序遍历中序遍历 中序遍历左子树中序遍历左子树 访问根结点访问根结点 中序遍历右子树中序遍历右子树A AT TX XC CZ ZY YB BP P深度为深度为4 4的二叉树的二
39、叉树A AT TZ ZB BC CX XY YP P因为左子树空因为左子树空遍历结果：遍历结果：56/77 后序遍历左子树后序遍历左子树 后序遍历右子树后序遍历右子树 访问根结点访问根结点后序遍历后序遍历A AT TX XC CZ ZY YB BP P深度为深度为4 4的二叉树的二叉树遍历结果：遍历结果：A AT TX XC CZ ZY YB BP P深度为深度为4 4的二叉树的二叉树A AT TZ ZB BC CX XY YP P因为左子树空，因为左子树空，故遍历右子树故遍历右子树57/776.4 6.4 典型算法典型算法 对非数值型数据通常有插入、删对非数值型数据通常有插入、删除、查找和排
40、序等操作。其中除、查找和排序等操作。其中查找查找和和排序排序是数据处理中比较重要的算法。是数据处理中比较重要的算法。查找查找又称又称检索检索，是指在数据集合中查找，是指在数据集合中查找某个数据元素的过程。若存在这样数据某个数据元素的过程。若存在这样数据元素元素,则查找成功；否则，查找失败。则查找成功；否则，查找失败。6.4.1 6.4.1 查找查找58/771.1.顺序查找顺序查找适用于适用于线性表线性表，其基本方法是，其基本方法是 ：从线性表中第一个元素开始，依次将线从线性表中第一个元素开始，依次将线性表中的元素性表中的元素与给定值进行比较与给定值进行比较。若相等，则查找成功；若相等，则查找
41、成功；若直到最后一个元素，还没找到与给定若直到最后一个元素，还没找到与给定值相等的元素，则查找失败。值相等的元素，则查找失败。59/77例如：在顺序表例如：在顺序表(88,15,23,80,63,8,86,46,(88,15,23,80,63,8,86,46,71,101)71,101)中中,查找查找 值为值为7171的数据元素。的数据元素。从线性表中第一个元素从线性表中第一个元素8888开始开始,依次将依次将 线性表中元素与线性表中元素与7171进行比较。进行比较。直到第九个元素为直到第九个元素为71,71,查找成功。查找成功。特点：顺序查找算法简单特点：顺序查找算法简单,但是执行但是执行效
42、率较低效率较低 在下列两种情况下在下列两种情况下,只能使用顺序查找法：只能使用顺序查找法：线性表是线性表是线性链表线性链表。线性表是顺序表，但表中元素线性表是顺序表，但表中元素无序无序排列。排列。此题比较了此题比较了9 9次次60/772.2.二分查找二分查找又称又称折半查找折半查找，要求被查找的表采用，要求被查找的表采用顺序存储结构顺序存储结构且数据元素按数据值且数据元素按数据值升序升序或或降序降序排列排列,即二分查找法只适用于即二分查找法只适用于。基本思想是基本思想是(设顺序表升序排列设顺序表升序排列)：P将给定值与将给定值与中间位置中间位置元素比较元素比较,若相等若相等,则则 查找成功；
43、查找成功；P若给定值小于元素值若给定值小于元素值,则继续对则继续对前半部分前半部分 再进行折半查找；再进行折半查找；P若给定值大于中间位置元素值若给定值大于中间位置元素值,则继续对则继续对后半部分后半部分再进行折半查找。再进行折半查找。61/77例：在例：在有序顺序表有序顺序表(8(8，1515，2323，4646，6363，7171，8080，8686，8888，101)101)中，用折半查找法查找值为中，用折半查找法查找值为 71 71 的数据元素。的数据元素。key=71 key=71 8 15 23 46 63 71 80 86 88 101 8 15 23 46 63 71 80 8
44、6 88 101 1 2 3 4 5 6 7 8 9 101 2 3 4 5 6 7 8 9 10第一次查找第一次查找mid=5mid=5第二次查找第二次查找mid=8mid=8第三次查找第三次查找mid=6mid=6 71 80 86 88 101 71 80 86 88 101 6 7 8 9 10 6 7 8 9 106371,6371,8671,故在前半部分进行折半查找故在前半部分进行折半查找 71 8071 80 6 76 7 71=71,71=71,查找成功查找成功 62/776.4.2 6.4.2 排序算法排序算法 排序排序是将一组无序数据按值递增是将一组无序数据按值递增(或递减
45、或递减)进行重新排列。进行重新排列。三三类基本排序方法类基本排序方法 交换排序法交换排序法选择排序法选择排序法插入排序法插入排序法63/771.1.交换排序法交换排序法在排序过程中在排序过程中,通过数据元素之间不断通过数据元素之间不断地进行地进行比较比较与与交换交换,最终达到排序目的。最终达到排序目的。的基本思想是：的基本思想是：对所有对所有元素进行比较，若元素进行比较，若逆顺逆顺，则将其则将其交换交换，最终达到有序化。，最终达到有序化。64/77交换排序法交换排序法原序列：原序列：4242232316 16474711 11454513 1349494242232316 16474711 1
46、1454513 134949第第1 1 遍遍第第2 2遍遍第第3 3遍遍第第4 4遍遍第第5 5遍遍第第6 6遍遍232316 16424211 114545474713 13494916 16232311 114242454513 134747494916 16232311 114242454513 134747494911 11232316 1613 13454542424747494911 1113 1316 1623234545424247474949每次从每次从待待排序数据序列中，选择出排序数据序列中，选择出最最小小元素并定位到待排序元素并定位到待排序(升序升序)序列最前面。序列最前
47、面。简单选择排序法简单选择排序法的基本思想是：的基本思想是：扫描整个序列，从中扫描整个序列，从中选出最小元素选出最小元素，将它，将它交换到最前面交换到最前面；再从再从剩余子序列剩余子序列中，选出最小元素中，选出最小元素，交换到子序列最前面。，交换到子序列最前面。依次类推，直到依次类推，直到子序列长度为子序列长度为1 1为止为止。65/772.2.选择排序法选择排序法由于每遍扫描只能确定由于每遍扫描只能确定一个元素位置，所以对于长一个元素位置，所以对于长度为度为n n的序列，需要扫描的序列，需要扫描n-1n-1遍才能将每个元素位置确定遍才能将每个元素位置确定下来。下来。66/77原序列：原序列：
48、4242232316 16272711 11454513 134949选择排序法选择排序法第第1 1遍选择遍选择4242232316 16272711 11454513 13494911 11232316 1627274242454513 134949第第2 2遍选择遍选择11 1113 1316 1627274242454523234949第第3 3遍选择遍选择11 1113 1316 1627274242454523234949第第4 4遍选择遍选择11 1113 1316 1623234242454527274949第第5 5遍选择遍选择11 1113 1316 162323272745
49、4542424949第第6 6遍选择遍选择11 1113 1316 1623232727424245454949第第7 7遍选择遍选择67/773.3.插入排序法插入排序法插入排序是不断地将待排序的插入排序是不断地将待排序的元素元素插入插入到前面的到前面的有序序列有序序列中中,直至直至所有元素都进入有序序列。所有元素都进入有序序列。简单插入排序简单插入排序又称又称直接插入排直接插入排序序,基本思想是：将由基本思想是：将由n n个元素组成个元素组成的序列分成前后两个子序列的序列分成前后两个子序列,前者为前者为有序序列有序序列,后者为后者为无序序列无序序列。68/77将待排序序列中将待排序序列中第
50、一个第一个元素作为元素作为有序序有序序列列，将，将第二个第二个元素元素插入插入到到有序序列有序序列中，中，形成由两个元素组成的有序序列。形成由两个元素组成的有序序列。再将再将第三个第三个元素元素插入插入到到有序序列有序序列中。依中。依此类推，直到最后一个元素插入到有序此类推，直到最后一个元素插入到有序序列中，形成序列中，形成n n个元素组成的有序序列。个元素组成的有序序列。简单插入排序的步骤：简单插入排序的步骤：69/77插入排序法插入排序法原序列：原序列：4242232316 16272711 11454513 134949第第1 1遍遍2323424216 16272711 1145451
