第二章数据结构与算法

第二章数据结构与算法第一页，共一百一十一页，2022年，8月28日2考试方式1、考试形式无纸化考试全部采用上机考试的方式进行考试，取消原来的纸质试卷。考生只参加一次考试，合格即可拿到证书。

无纸化考试因为不需要再分笔试和机试，因此不再有补考。考生若未能通过考试，则下次必须全部重考。从整体上来说，无纸化考试相对于传统考试，难度有所降低。

第二页，共一百一十一页，2022年，8月28日考试方式2、考试题型全国计算机等级考试二级无纸化考试中，共有4个大题。第一个大题为单项选择题；其余三个大题为上机操作题。单选题为四选一或三选一，共40分，考40个小题。二级考试各科上机操作题均考3个大题，共60分。3第三页，共一百一十一页，2022年，8月28日4考试内容：第一章1.数据库的基本概念：数据库，数据库管理系统，数据库系统。2.数据模型，实体联系模型及E-R图，从E-R图导出关系数据模型。3.关系代数运算，包括集合运算及选择、投影、连接运算，数据库规范化理论。4.数据库设计方法和步骤：需求分析、概念设计、逻辑设计和物理设计的相关策略。第四页，共一百一十一页，2022年，8月28日5考试内容：第二章1.算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复杂度）。2.数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。3.线性表的定义；线性表的顺序存储结构及其插入与删除运算。4.栈和队列的定义；栈和队列的顺序存储结构及其基本运算。5.线性单链表、双向链表与循环链表的结构及其基本运算。6.树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。7.顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序）。第五页，共一百一十一页，2022年，8月28日6考试内容：第三章1.程序设计方法与风格。2.结构化程序设计。3.面向对象的程序设计方法，对象，方法，属性及继承与多态性。第六页，共一百一十一页，2022年，8月28日7考试内容：第四章1.软件工程基本概念，软件生命周期概念，软件工具与软件开发环境。2.结构化分析方法，数据流图，数据字典，软件需求规格说明书。3.结构化设计方法，总体设计与详细设计。4.软件测试的方法，白盒测试与黑盒测试，测试用例设计，软件测试的实施，单元测试、集成测试和系统测试。5.程序的调试，静态调试与动态调试。第七页，共一百一十一页，2022年，8月28日8学习方法基本概念要理解理解的基础上适当记忆一些概念多做练习，从练习中总结与所学的知识结合起来，以增加对知识的理解能力第八页，共一百一十一页，2022年，8月28日第二章数据结构与算法9第九页，共一百一十一页，2022年，8月28日本章主要内容算法数据结构数据结构研究的主要内容基本概念和术语数据结构类型线性结构和非线性结构顺序存储与链式存储线性表栈和队列线性链表树与二叉树查找和排序图第十页，共一百一十一页，2022年，8月28日2.1算法算法的基本概念算法：解题方案的准确而完整的描述。算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。算法不等于程序，程序不可能优于算法。基本特性可行性：根据实际问题设计的算法，执行得到满意结果确定性：每一步骤必须有明确定义，不允许有多义性。有穷性：算法必须能在有限的时间内做完。输入和输出：拥有足够的情报，方可执行。第十一页，共一百一十一页，2022年，8月28日2.1算法算法的基本要素1.对数据对象的运算和操作算术运算：＋、－、×、÷等运算逻辑运算：and、or、not等运算关系运算：>、<、＝、>=、<=、!=等运算数据传输：赋值、输入、输出等操作2.算法的控制结构算法中各操作之间的执行顺序描述算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言等算法可以用顺序、选择、循环三种基本结构组合而成。第十二页，共一百一十一页，2022年，8月28日2.1算法算法设计基本方法（1）列举法：根据问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。（2）归纳法：通过列举少量的特殊情况，经过分析，最后找出一般的关系。（3）递推：是指从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。（4）递归：将问题逐层分解的过程。（5）减半递推技术：

“减半”，是指将问题规模减半，而问题性质不变；“递推”，是指重复“减半”过程。（6）回溯法：分析问题，找出一个解决总线索，然后沿着这个线索逐步试探。第十三页，共一百一十一页，2022年，8月28日2.1算法算法的复杂度：时间复杂度、空间复杂度算法的时间复杂度算法时间复杂度是指执行算法所需要的计算工作量。工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即

算法的工作量=f(n)O(1)常量级O(n)线性级O(n2)平方级第十四页，共一百一十一页，2022年，8月28日时间复杂度举例举例1

X=X+1S=0执行次数：2时间复杂度：O(1)此算法的基本操作是赋值语句。执行两条语句各一次，共2次,与规模无关。时间复杂度为Ｏ(1)，即常量阶。第十五页，共一百一十一页，2022年，8月28日时间复杂度举例举例2

Fori=1tonx=x+1s=s+xNexti

执行次数为：2n其时间复杂度为：O(n)即时间复杂度为线性阶。第十六页，共一百一十一页，2022年，8月28日时间复杂度举例举例3Fori=1tonForj=1tonx=x+1s=s+xnextjNexti

执行次数2n2其时间复杂度为：O(n2)即时间复杂度为平方阶。基本语句第十七页，共一百一十一页，2022年，8月28日例，for(j=1

；j<=n；j++)X=X+1；for(i=1

；i<=n；i++)(c)for(i=1

；i<=n；i++)X=X+1；(b)X=X+1；(a)基本操作重复执行的次数分别为1，n，n2第十八页，共一百一十一页，2022年，8月28日2.1算法算法空间复杂度算法空间复杂度是指执行这个算法所需要的内存空间。存储空间包括：①算法程序所占的空间②输入数据所占的空间③算法执行过程中所需要的额外空间。第十九页，共一百一十一页，2022年，8月28日2.2.1数据结构研究的主要内容当今计算机应用的特点所处理的数据量大且具有一定的关系；对其操作不再是单纯的数值计算，而更多地是需要对其进行组织、管理和检索。应用举例1——学籍档案管理

假设一个学籍档案管理系统应包含如下表所示的学生信息。第二十页，共一百一十一页，2022年，8月28日特点每个学生的信息占据一行，所有学生的信息按学号顺序依次排列构成一张表格；表中每个学生的信息依据学号的大小存在着一种前后关系.对它的操作通常是插入某个学生的信息，删除某个学生的信息，更新某个学生的信息，按条件检索某个学生的信息等等。2.2.1数据结构研究的主要内容第二十一页，共一百一十一页，2022年，8月28日应用举例2—制定教学计划在制定教学计划时，需要考虑各门课程的开设顺序。有些课程需要先导课程，有些则不需要;而有些课程又是其他课程的先导课程。比如，计算机专业课程的开设情况如下表所示：2.2.1数据结构研究的主要内容第二十二页，共一百一十一页，2022年，8月28日课程先后关系的图形描形式c1c9c4c2c12c10c11c5c3c6c7c82.2.1数据结构研究的主要内容特点课程的先后关系用图结构描述；通过实施创建图结构，按要求将图结构中的顶点进行线性排序。第二十三页，共一百一十一页，2022年，8月28日

数据结构主要研究以下三个方面的问题：数据的逻辑结构：数据集合中各元素的信息，及元素之间所固有的逻辑关系（前后件关系）数据的存储结构：各数据元素在计算机中的存储关系对各种数据结构进行的运算

主要目的是为了提高数据的效率。所谓提高数据处理的效率，主要包括两个方面：一是提高数据处理的速度，二是尽量节省在数据处理过程中所占用的计算机存储空间。2.2.1数据结构研究的主要内容第二十四页，共一百一十一页，2022年，8月28日

数据结构是一门研究数据组织、存储和运算的一般方法的学科。是相互有关联的数据元素的集合。2.2.2基本概念和术语第二十五页，共一百一十一页，2022年，8月28日能输入到计算机中并能被计算机程序处理的符号的集合。整数(1,2)、实数(1.1,1.2)字符串(Beijing)、图形、声音。

数据结构是一门研究数据组织、存储和运算的一般方法的学科。2.2.2基本概念和术语第二十六页，共一百一十一页，2022年，8月28日计算机管理图书问题

图书馆里有各种卡片：有按书名编排的、有按作者编排的、有按分类编排。如何将查询图书的这些信息存入计算机中既要考虑查询时间短，又要考虑节省空间

数据结构是一门研究数据组织、存储和运算的一般方法的学科。2.2.2基本概念和术语第二十七页，共一百一十一页，2022年，8月28日

最简单的办法之一是建立一张表，每一本书的信息在表中占一行，如

数据结构是一门研究数据组织、存储和运算的一般方法的学科。2.2.2基本概念和术语第二十八页，共一百一十一页，2022年，8月28日

如何将0,1,2,3,4,5,6,7,8,9这10个数存放在计算机中能最快地达到你所需要的目的？目的不同，最佳的存储方方法就不同。

从大到小排列：9,8,7,6,5,4,3,2,1,0输出偶数：0,2,4,6,8,1,3,5,7,9

数据元素在计算机中的表示

数据结构是一门研究数据组织、存储和运算的一般方法的学科。2.2.2基本概念和术语第二十九页，共一百一十一页，2022年，8月28日对数据结构中的节点进行操作处理(插入、删除、修改、查找、排序)

数据结构是一门研究数据组织、存储和运算的一般方法的学科。2.2.2基本概念和术语第三十页，共一百一十一页，2022年，8月28日数据元素(DataElement)

数据元素是数据的基本单位，即数据集合中的个体。

有时一个数据元素可由若干数据项(DataItem)组成。数据项是数据的最小单位。数据元素亦称节点或记录。2.2.2基本概念和术语第三十一页，共一百一十一页，2022年，8月28日数据结构可描述为Group=（D，R）有限个数据元素的集合有限个节点间关系的集合2.2.2基本概念和术语第三十二页，共一百一十一页，2022年，8月28日1．数据的逻辑结构2、数据的存储结构3、数据的运算：检索、排序、插入、删除、修改等。A．线性结构

B．非线性结构A顺序存储

B链式存储

线性表栈队树形结构图形结构数据结构的三个方面2.3数据结构类型第三十三页，共一百一十一页，2022年，8月28日2.3.1线性结构和非线性结构

线性结构条件（1）有且只有一个根结点；（2）每一个结点最多有一个前件（前驱），也最多有一个后件（后驱）。（3）首节点无前件，尾节点无后件。

非线性结构：不满足线性结构条件的数据结构注意：在一个线性结构中插入或删除任何一个节点后还应是线性结构；否则，不能称为线性结构。学生成绩表86胡孝臣986110395刘忠赏9861107100张卓9861109成绩姓名学号第三十四页，共一百一十一页，2022年，8月28日2.3.1线性结构和非线性结构全校学生档案管理的树形结构的组织方式非线性结构

树形结构第三十五页，共一百一十一页，2022年，8月28日ABCDEFGH树形结构—结点间具有分层次的连接关系HBCDEFGA2.3.1线性结构和非线性结构

树形结构第三十六页，共一百一十一页，2022年，8月28日2.3.1线性结构和非线性结构

图形结构：节点间的连接任意1423D={1,2,3,4}R={(1,2),(1,3),(1,4),(2,3)(3,4),(2,4)}无向图213D={1,2,3}R={<1,2>,<2,3>,<3,2>,<1,3>}有向图第三十七页，共一百一十一页，2022年，8月28日Lo+（n-1)*m元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*m存储地址存储内容Loc(a)=Lo+（i-1)*m每个元素所占用的存储单元个数2.3.2顺序存储与链式存储

顺序存储常用于线性数据结构，将逻辑上相邻的数据元素存储在物理上相邻的存储单元里。三个弱点插入或删除操作时，需移动大量元数。长度变化较大时，需按最大空间分配。表的容量难以扩充第三十八页，共一百一十一页，2022年，8月28日每个节点都由两部分组成：数据域和指针域。数据域：存放元素本身的数据，指针域：存放指针，体现数据元素之间的逻辑联系2.3.2顺序存储与链式存储1536元素21400元素11346元素3∧元素4head1345链接存储结构特点比顺序存储结构的存储密度小(每个节点都由数据域和指针愈组成)。逻辑上相邻的节点物理上不必相邻。插入、删除灵活(不必移动节点，仅改变节点中的指针)。链接存储结构第三十九页，共一百一十一页，2022年，8月28日1346

元素31536

…….

……..

…….1536

元素21400

…….

……..

…….∧

元素413461400

元素11345

指针

存储内容存储地址1536元素21400元素11346元素3∧元素4head13452.3.2顺序存储与链式存储链式存储的地址映射表第四十页，共一百一十一页，2022年，8月28日1、链表不具有的特点是（）A)不必事先估计存储空间B)插入删除不需要移动元素C)可随机访问任一元素D)所需空间与线性表长度成正比2、数据结构中，与所使用的计算机无关的是数据的（）A)存储结构 B)物理结构C)逻辑结构 D)物理和存储结构

3、根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分成（）A)动态结构和静态结构 B)紧凑结构和非紧凑结构C)线性结构和非线性结构D)内部结构和外部结构4、数据处理的最小单位是（）A)数据B)数据元素C)数据项D)数据结构过关练习第四十一页，共一百一十一页，2022年，8月28日5、下列叙述中，错误的是（）A)数据的存储结构与数据处理的效率密切相关B)数据的存储结构与数据处理的效率无关C)数据的存储结构在计算机中所占空间不一定是连续的D)一种数据的逻辑结构可以有多种存储结构6、线性表的顺序存储结构和线性表的链式存储结构分别是A)顺序存取的存储结构、顺序存取的存储结构B)随机存取的存储结构、顺序存取的存储结构C)随机存取的存储结构、随机存取的存储结构D)任意存取的存储结构、任意存取的存储结构7、数据结构作为计算机的一门学科，主要研究数据的逻辑结构、对各种数据结构进行的运算，以及（）A)数据的存储结构 B)计算方法C)数据映象D)逻辑存储过关练习第四十二页，共一百一十一页，2022年，8月28日8、下列叙述中正确的是（）A）程序执行的效率与数据的存储结构密切相关B）程序执行的效率只取决于程序的控制结构C）程序执行的效率只取决于所处理的数据量D）以上都不对9、数据的存储结构是指（）A）数据所占的存储空间B）数据的逻辑结构在计算机中的表示C）数据在计算机中的顺序存储方式D）存储在外存中的数据10、数据（）包括集合、线性结构、树形结构和图4种类型。A)算法描述B)基本运算C)逻辑结构D)存储结构过关练习第四十三页，共一百一十一页，2022年，8月28日11、数据在计算机内存种的表示是指（）A）数据的存储结构B）数据结构C）数据的逻辑机构D）数据元素间的关系12、数据结构研究的主要内容包括（）、（）和数据元素之间的三方面联系。13、顺序存储方法是把逻辑上相邻的结点存储在物理位置（）的存储单元中。14、数据结构包括数据的逻辑结构、数据的（）以及对数据的操作运算。15、数据的基本单位是（）。16、数据结构分为逻辑结构与存储结构，线性链表属于（）。17、数据的逻辑结构有线性结构和（）两大类。过关练习第四十四页，共一百一十一页，2022年，8月28日练习参考答案1～5、CCCCB6～11、BAABCA12、数据存储结构、数据逻辑结构13、相邻14、存储结构15、数据元素16、非线性结构第四十五页，共一百一十一页，2022年，8月28日2.3.3线性表线性表的基本概念

线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。非空线性表的结构特征有且只有一个根结点a1，它无前件；有且只有一个终端结点an，它无后件；除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。结点个数n称为线性表的长度，当n=0时，称为空表。Lo+（n-1)*m元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*m存储地址存储内容Loc(a)=Lo+（i-1)*m第四十六页，共一百一十一页，2022年，8月28日在线性表上常用的运算有初始化、求长度、取元素、修改、插入、删除、检索、排序。线性表的插入操作

在线性表L中第i个数据元素之前插入数据元素e检查插入要求的有关参数的合理性把原来第n个数据元素至第i个元素（共n-i+1)依次后移一个数组元素的位置。把新数据元素放在第i个位置上修正线性表的数据元素个数。线性表中含有n个数据元素，在进行插入操作时，若假定在n+1个位置上插入元素的可能性均等，则平均移动元素的个数为：n/22.3.3线性表第四十七页，共一百一十一页，2022年，8月28日线性表的插入操作（时间复杂度O(n)）插入前插入xlastMaxsize-1aia1a0ai-1ai+1an-1a0a1ai-1aian-1lastMaxsize-1后移后ai＋1a0a1ai-1ai+1ai+1anxlastMaxsize-1插入后ai+22.3.3线性表第四十八页，共一百一十一页，2022年，8月28日线性表的删除操作（时间复杂度O(n)）2.3.3线性表a0a1ai-1aiai+1an-1删除lastmaxsize删除前a0a1ai-1ai+2an-1lastmaxsize删除后ai+1第四十九页，共一百一十一页，2022年，8月28日1、线性表L=(a1,a2,a3,…ai，…an)，下列说法正确的是（）A)每个元素都有一个直接前件和直接后件B)线性表中至少要有一个元素C)表中诸元素的排列顺序必须是由小到大或由大到小D)除第一个元素和最后一个元素外，其余每个元素都有一个且只有一个直接前件和直接后件2、线性表采用链式存储结构时，则内存中可用存储单元地址A)必须是连续的 B)部分地址必须是连续的C)一定是不连续的D)连续不连续都可以3、在一个长度为n的顺行表种，向第i个元素位置插入一个新元素时，需要向后移动（）个元素A)n-iB)iC)n-i-1D)n-i+14、长度为n的顺序存储线性表，当在任何位置上插入一个元素概率都相等时，插入一个元素所需移动元素的平均个数为（）。过关练习第五十页，共一百一十一页，2022年，8月28日练习参考答案1、D2、C3、D3、n/2第五十一页，共一百一十一页，2022年，8月28日2.3.4栈和队列栈和队列是两种运算时要受到某些特殊限制的线性表，故也称为限定性的数据结构。栈：限定只能在表的一端进行插入和删除的特殊的线性表,此种结构称为后进先出。设栈s=（a1，a2，…,ai，…，an）其中a1是栈底元素，an是栈顶元素。栈顶（top)：允许插入和删除的一端；约定top始终指向新数据元素将存放的位置。栈底（bottom):不允许插入和删除的一端。a1a2….an进栈出栈栈顶栈底第五十二页，共一百一十一页，2022年，8月28日队列的主要运算设置一个空队列；插入一个新的队尾（rear）元素，称为进队；删除队头（front）元素，称为出队；读取队头元素；a1,

a2,

a3,

a4,…………

an-1,

an队头队尾2.3.4栈和队列队列：限定只能在表的一端进行插入，在表的另一端进行删除的线性表。此种结构称为先进先出（FIFO）表。第五十三页，共一百一十一页，2022年，8月28日

3210(a)rear=front=-1(队空）e3e4(c)e1,e2出队，e4入队rear=4fronte1e2e3

(b)rearfront(b)e1,e2,e3入队2.3.4栈和队列队列的主要运算队空时，令rear=front=-1当有新元素入队时，尾指针加1，当有元素出队时，头指针加1。故在非空队列中，头指针始终指向队头元素前一个位置，而尾指针始终指向队尾元素的位置第五十四页，共一百一十一页，2022年，8月28日循环队列元素个数=rear-fronta1,

a2,

a3,

a4,…………

an-1,

an队头队尾2.3.4栈和队列循环队列：首尾相接的队列，逻辑上形成一个环状。第五十五页，共一百一十一页，2022年，8月28日1、栈和队列的共同特点是（）A)都是先进先出B)都是先进后出C)只允许在端点处插入和删除元素D)没有共同点2、如果进栈序列为e1,e2,e3,e4，则可能的出栈序列是A)e3,e1,e4,e2 B)e2,e4,e3,e1C)e3,e4,e1,e2 D)任意顺序3、一些重要的程序语言(如C语言和Pascal语言)允许过程的递归调用。而实现递归调用中的存储分配通常用（）A)栈 B)堆C)数组 D)链表4、栈通常采用的两种存储结构是A)线性存储结构和链表存储结构B)散列方式和索引方式C)链表存储结构和数组D)线性存储结构和非线性存储结构过关练习第五十六页，共一百一十一页，2022年，8月28日5、下列数据结构中，按先进后出原则组织数据的是（）A)线性链表B)栈C)循环链表D)顺序表6、下列关于栈的叙述中正确的是（）Ａ）在栈中只能插入数据B）在栈中只能删除数据C）栈是先进先出的线性表D）栈是后进先出的线性表7、下列关于队列的叙述中正确的是（）Ａ）在队列中只能插入数据B）在队列中只能删除数据C）队列是先进先出的线性表D）队列是后进先出的线性表8、在顺序栈中进行退栈操作时，（）。Ａ）谁先谁后都可以B）先移动栈顶指针，后取出元素C）不分先后，同时进行D）先取出元素，后移动栈顶指针过关练习第五十七页，共一百一十一页，2022年，8月28日9、假定利用数组a[n]顺序存储一个栈，利用top表示栈顶指针，用top=n+1表示栈空，该数组所能存储的栈的最大长度为n，则表示栈满的条件是（）。A)top=-1B)top=0C)top>1D)top=110、线性表的存储结构主要分为顺序存储结构和链式存储结构。队列是一种特殊的线性表，循环队列是队列的（）存储结构。11、数据结构分为线性结构和非线性结构，带链的队列属于（）。12、通常元素进栈的循序是（）。13、从一个循环队列中删除一个元素，通常的操作是（）。过关练习第五十八页，共一百一十一页，2022年，8月28日练习参考答案1～5、CBACB6～9、DCDD10、顺序11、线性结构12、先移动栈顶指针，后存入元素13、先取出元素，后移动对头指针第五十九页，共一百一十一页，2022年，8月28日2.3.5线性链表线性表顺序存储结构的特点简单、方便，要求数据元素依次存放在连续的存储单元中，从而利用数据元素的存储顺序表示相应的逻辑顺序，这种存储方式属于静态存储形式。暴露的问题在做插入或删除元素的操作时，会产生大量的数据元素移动；对于长度变化较大的线性表，要一次性地分配足够的存储空间，但这些空间常常又得不到充分的利用；线性表的容量难以扩充。第六十页，共一百一十一页，2022年，8月28日

将线性表的元素放到一个具有头指针的链表中，链表中每个结点包含数据域和指针域。

数据域存放数据，指针域存放后继结点的地址，最后一个结点的指针域为空。逻辑上相邻的数据元素在内存中的物理存储空间不一定相邻。线性链表分为：单链表、双链表、循环链表2.3.5线性链表a1a2∧ana3L…..带头结点的单链表第六十一页，共一百一十一页，2022年，8月28日单链表：每个结点只有一个指针域，由该指针只能找到其后件结点。2.3.5线性链表第六十二页，共一百一十一页，2022年，8月28日2.3.5线性链表线性链表的计算在指定节点前插入一个元素(不必移动节点，仅改变节点中的指针，且不会出现“上溢”现象)删除指定节点(不必移动节点，仅改变节点中的指针)合并两个线性链表逆转线性链表复制线性链表线性链表排序线性链表查找第六十三页，共一百一十一页，2022年，8月28日babaxPP单链表的插入运算：在节点a之后插入一新节点S2.3.5线性链表第六十四页，共一百一十一页，2022年，8月28日ai-1a1aiai+1Lp单链表的删除运算：删除节点ai2.3.5线性链表a1qq第六十五页，共一百一十一页，2022年，8月28日循环链表:

首尾相接的链表循环链表是表中最后一个结点的指针非空，而是指向头结点，使链表构成环状。特点：

2、增加了头结点，使得任何时候循环链表中至少有一个结点。

1、从表中任一结点出发均可找到表中其他结点，提高查找效率。

La1a2an…..循环单链表2.3.5线性链表L空链表第六十六页，共一百一十一页，2022年，8月28日双向链表：在每个结点中设置两个指针，一个指向后继，一个指向前驱。可直接确定一个结点的前驱和后继结点。可提高效率。datanextbefore非空双向循环链表：LAB2.3.5线性链表第六十七页，共一百一十一页，2022年，8月28日2.3.5线性链表线性链表的特点插入、删除节点方便(不必移动节点，仅改变节点中的指针)只能顺序存取（查找只能从头指针开始），不能随即存取。适应于数据的动态变化第六十八页，共一百一十一页，2022年，8月28日1、链表不具有的特点是（）A)不必事先估计存储空间B)可随机访问任一元素C)插入删除不需要移动元素D)所需空间与线性表长度成正比2、用链表表示线性表的优点是（）A)便于随机存取B)花费的存储空间较顺序存储少C)便于插入和删除操作D)数据元素的物理顺序与逻辑顺序相同3、线性表L=(a1,a2,a3,…ai，…an)，下列说法正确的是（）A)每个元素都有一个直接前件和直接后件B)线性表中至少要有一个元素C)表中诸元素的排列顺序必须是由小到大或由大到小D)除第一个元素和最后一个元素外，其余每个元素都有一个且只有一个直接前件和直接后件过关练习第六十九页，共一百一十一页，2022年，8月28日4、下列叙述中正确的是（）。A)线性链表是线性表的链式存储结构B)栈与队列是非线性结构C)双向链表是非线性结构D)只有根结点的二叉树是线性结构5、循环链表的主要优点是（）A)不再需要头指针了B)从表中任一结点出发都能访问到整个链表C)在进行插入、删除运算时，能更好的保证链表不断开D)已知某个结点的位置后，能够容易的找到它的直接前件过关练习第七十页，共一百一十一页，2022年，8月28日6、线性表的顺序存储结构和线性表的链式存储结构分别是A)顺序存取的存储结构、顺序存取的存储结构B)随机存取的存储结构、顺序存取的存储结构C)随机存取的存储结构、随机存取的存储结构D)任意存取的存储结构、任意存取的存储结构7、用链表表示线性表的突出优点是（）。8、在双向链表中，每个结点有两个指针域，一个指向（），另一个指向（）。9、长度为n的顺序存储线性表中，当在任何位置上插入一个元素概率都相等时，插入一个元素所需移动元素的平均个数为（）。过关练习第七十一页，共一百一十一页，2022年，8月28日练习参考答案1～6、BCDABB7、插入、删除结点方便8、前趋结点，后继结点9、n/2第七十二页，共一百一十一页，2022年，8月28日树的定义：由一个或多个结点组成的有限集合。仅有一个根结点，结点间有明显的层次结构关系。

A

C

GT2D

HIT3J

M

BEL

KT1F

现实世界中，能用树的结构表示：学校的行政关系、书的层次结构、人类的家族血缘关系等。2.3.6树与二叉树第七十三页，共一百一十一页，2022年，8月28日树的基本概念：结点（Node）：树中的元素结点的度（Degree）：结点拥有的子树数。结点的层次：从根结点开始算起，根为第一层。叶子（Leaf）：度为零的结点，也称端结点。孩子（Child）：结点子树的根称为该结点的孩子结点。兄弟（Sibling）：同一双亲的孩子。双亲（Parent）：孩子结点的上层结点，称为其的双亲。深度（Depth)：树中结点的最大层次数。森林（Forest）：M棵互不相交的树的集合。

A

C

GT2D

HIT3J

M

BEL

KT1F2.3.6树与二叉树第七十四页，共一百一十一页，2022年，8月28日二叉树（BinaryTree）的定义二叉树的五种基本形态二叉树一种特殊的树型结构，特点是树中每个结点只有两棵子树，且子树有左右之分，次序不能颠倒。

空二叉树

仅有根结点

右子树为空

左子树为空左右子树均非空因为树的每个结点的度不同，存储困难，使对树的处理算法很复杂。所以引出二叉树的理论。2.3.6树与二叉树第七十五页，共一百一十一页，2022年，8月28日满二叉树423167891011121314155

特点：所有分支结点都存在左右子树，且所有叶子结点都在同一层上。2.3.6树与二叉树第七十六页，共一百一十一页，2022年，8月28日423167891011125

非完全二叉树完全二叉树423167891011125

完全二叉树

特点：除最后一层外，每一层都取最大结点数，最后一层结点都集中在该层最左边的若干位置。2.3.6树与二叉树第七十七页，共一百一十一页，2022年，8月28日A、二叉树的第i层上至多有2i-1（i1）个结点。B、深度为h的二叉树中至多含有2h-1个结点。C、若在任意一棵二叉树中，有n0个叶子结点（度为0），有n2个度为2的结点，则：n0=n2+1D、具有n个结点的完全二叉树的深度为[log2n]+1，其中[log2n]表示log2n的整数部分。二叉树的基本性质4231678910111213141552.3.6树与二叉树第三层(i=3)，有23-1=4个节点深度h=4，共有24-1=15个节点n0=8,n2=7,n0=n2+115个节点，深度=[log215]+1=4第七十八页，共一百一十一页，2022年，8月28日E、设完全二叉树共有n个结点，如从根结点开始，按层序（每一层从左到右）用自然数1,2,…,n给结点进行编号，则对于编号为k（k=1,2,…,n）的结点有以下结论：①若k=1，则该结点为根结点，它没有父结点；若k>1，则该结点的父结点的编号为INT(k/2)。②若2k≤n，则结点k的左子结点编号为2k；否则该结点无左子结点（显然也没有右子结点）。③若2k+1≤n，则结点k的右子结点编号为2k+1；否则该结点无右子结点。二叉树的基本性质4231678910111213141552.3.6树与二叉树例如结点6，其父结点为3，左子结点为12，左子结点为13第七十九页，共一百一十一页，2022年，8月28日2.3.6树与二叉树二叉树的存储结构顺序存储结构链式存储结构顺序存储结构用一组连续的存储单元存放二叉树的数据元素。结点在数组中的相对位置蕴含着结点之间的关系。用数组存储时，若父结点在数组中i下标处，其左孩子在2*i处，右孩子在2*i+1处。顺序存储二叉树必须按完全二叉树的形式存储，将造成存储的浪费。第八十页，共一百一十一页，2022年，8月28日二叉树的顺序存储结构T[16]11ABcFED

●●●●●●●●●12489105637121314152h-1=24-1=150000FE000DC0BA151413121110987654321002.3.6树与二叉树第八十一页，共一百一十一页，2022年，8月28日2.3.6树与二叉树二叉树链式存储结构在顺序存储结构中，对于非完全二叉树，需要将空缺的位置用特定的符号填补，若空缺结点较多，势必造成空间利用率的下降。在这种情况下，就应该考虑使用链式存储结构。常见的二叉树结点结构如下所示：LchilditemRchildparentAB第八十二页，共一百一十一页，2022年，8月28日2.3.6树与二叉树GHDEFBCA^G^^H^^D^E^F^B^CABT二叉树的链接存储结构第八十三页，共一百一十一页，2022年，8月28日二叉树的遍历

遍历是指按某条搜索路线寻访树中每个结点，且每个结点只被访问一次。按先左后右的原则，一般使用三种遍历：

先序遍历(DLR):

访问根结点，按先序遍历左子树，按先序遍历右子树。

中序遍历(LDR):

按中序遍历左子树，访问根结点，按中序遍历右子树。

后序遍历(LRD):

按后序遍历左子树，按后序遍历右子树，访问根结点。二叉树为空时，执行空操作，即空二叉树已遍历完。2.3.6树与二叉树第八十四页，共一百一十一页，2022年，8月28日遍历算法先序遍历：DLR中序遍历：LDR后序遍历：LRDADBCT1T2T3DLRADLRDLR>B>>D>>CDLR以先序遍历DLR为例演示遍历过程ABDCBDACDBCA2.3.6树与二叉树第八十五页，共一百一十一页，2022年，8月28日1、已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为（）A)GEDHFBCA B)DGEBHFCAC)ABCDEFGH D)ACBFEDHG2、树是结点的集合，它的根结点数目是（）A)有且只有1B)1或多于1C)0或1 D)至少23、在深度为5的满二叉树中，叶子结点的个数为（）A)32 B)31C)16 D)154、下列叙述中正确的是（）A)线性表是线性结构 B)栈与队列是非线性结构C)线性链表是非线性结构 D)二叉树是线性结构过关练习第八十六页，共一百一十一页，2022年，8月28日5、具有3个结点的二叉树有（）A)2种形态B)4种形态C)7种形态D)5种形态6、设有下列二叉树,其前序遍历的结果为（）

A)ZBTTCPXAB)ATBZXCTPC)ZBTACTXPD)ATBZXCPT7、一棵二叉树中，共有70个叶子结点与80个度为1的结点，则其总结点为（）。A)219 B)221C)229D)231过关练习第八十七页，共一百一十一页，2022年，8月28日8、设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为（）A)12 B)13C)14D)159、设有下列二叉树，中序遍历的结果为（）A)ABCDEFB)DBEAFCC)ABDECFD)DEBFCA过关练习第八十八页，共一百一十一页，2022年，8月28日10、在树结构中，树根结点没有（）11、在深度为7的满二叉树中，度为2的结点个数为（）。12、一棵二叉树第6层（根结点为第1层）的结点数最多为（）个。13、深度为K的完全二叉树，至少有（）个结点，至多有（）个结点，若按至上而下，从左到右的次序编号（从1开始），则编号最小的叶子结点的编号是（）。过关练习第八十九页，共一百一十一页，2022年，8月28日练习参考答案1～5、BCCAD6～9、BABB10、双亲11、6312、3213、2k-1,2k-1,2k-1第九十页，共一百一十一页，2022年，8月28日查找：在一个给定的数据结构中，根据给定的条件找到满足条件的结点。不同的数据结构采用不同的查找方法。查找的效率直接影响数据处理的效率。平均查找长度：查找过程中比较的次数查找的结果查找成功：找到满足条件的结点查找失败：找不到满足条件的结点。2.3.7查找和排序第九十一页，共一百一十一页，2022年，8月28日顺序查找（线性查找）

对给定的一关键字K，从线性表的一端开始，逐个进行记录的关键字和K的比较，直到找到关键字等于K的记录或到达表的另一端。可以采用从前向后查，也可采用从后向前查的方法。在平均情况下，大约要与表中一半以上元素进行比较，效率较低。平均查找长度=(n+1)/2。时间复杂度＝O(n)在下面两种情况下只能采取顺序查找：线性表为无序表（元素排列是无序的）；即使是有序线性表，但采用的是链式存储结构。2.3.7查找和排序第九十二页，共一百一十一页，2022年，8月28日折半查找（二分法查找）思想：先确定待查找记录所在的范围，然后逐步缩小范围，直到找到或确认找不到该记录为止。前提：必须在具有顺序存储结构的有序表中进行。分三种情况：若中间项的值等于x,则说明已查到。若x小于中间项的值，则在线性表的前半部分查找；若x大于中间项的值，则在线性表的后半部分查找。特点：比顺序查找方法效率高。最坏的情况下，需要比较log2n次。2.3.7查找和排序第九十三页，共一百一十一页，2022年，8月28日折半查找（二分法查找）算法假设查找表存放在数组a的a[1]～a[n]中，且升序，查找关键字值为k。折半查找的主要步骤为：（1）置初始查找范围：low=1，high=n;（2）求查找范围中间项：mid=(low+high)/2（3）将指定的关键字值k与中间项a[mid].key比较。

若相等，查找成功，找到的数据元素为此时mid指向的位置；

若小于，查找范围的低端数据元素指针low不变，高端数据元素指针high更新为mid-1;

若大于，查找范围的高端数据元素指针high不变，低端数据元素指针low更新为mid+1;（4）重复步骤（2）、（3）直到查找成功或查找范围空（low>high），即查找失败为止。（5）如果查找成功，返回找到元素的存放位置，即当前的中间项位置指针mid；否则返回查找失败标志。第九十四页，共一百一十一页，2022年，8月28日查找23和79的过程如下图：9元素mid=(low+high)/2不进位取整(08,14,23,37,46,55,68,79,91)(08,14,23,37,46,55,68,79,91)lowhighmid(08,14,23,37,46,55,68,79,91)lowhigh=mid-1mid(08,14,23,37,46,55,68,79,91)low=mid+1highmid(08,14,23,37,46,55,68,79,

91)lowhighmid(08,14,23,37,46,55,68,79,91)lowhighmid(08,14,23,37,46,55,68,79,91)lowhighmid第九十五页，共一百一十一页，2022年，8月28日

排序的功能：将一个数据元素（或记录）的任意序列，重新排成一个按关键字有序的序列。

排序过程的组成步骤

1、首先比较两个关键字的大小；

2、然后将记录从一个位置移动到另一个位置。1.3.7查找和排序堆排序起泡排序排序方法插入排序选择排序交换排序归并排序直接、折半插入排序希尔排序简单选择排序快速排序第九十六页，共一百一十一页，2022年，8月28日该算法适合于n较小的情况，时间复杂度为O(n2).待排元素序列：[53]2736156942第一次排序：[2753]36156942第二次排序：[273653]156942第三次排序：[15273653]6942第四次排序：[1527365369]42第五次排序：[152736425369]

直接插入排序示例对于有n个数据元素的待排序列，插入操作要进行n-1次2.3.7直接插入排序

从数组的第2号元素开始，顺序取出后续元素，并将该元素插入到其左端已排好序数组的适当位置。需比较n(n-1)/2次第九十七页，共一百一十一页，2022年，8月28日例：有6个记录，前5个已排序的基础上，对第6个记录排序。[1527365369]42lowmidhigh[1527365369]42

lowhigh

mid

[1527365369]42

highlow[152736425369](high<low，查找结束，插入位置为low或high+1)(42>36)(42<53)2.3.7折半插入排序

折半插入排序在寻找插入位置时，不是逐个比较而是利用折半查找的原理寻找插入位置。待排序元素越多，改进效果越明显。第九十八页，共一百一十一页，2022年，8月28日

思想：首先从1～n个元素中选出关键字最小的记录交换到第一个位置上。然后再从第2个到第n个元素中选出次小的记录交换到第二个位置上，依次类推。时间复杂度为O(n2)，最坏情况下需要比较n(n-1)/2次适用于待排序元素较少的情况。2.3.7简单选择排序初态83916839168391683916ijkijkijkijk1

3986互换ijk1

3986ikj1

3986ikj第一趟第二趟1

3986ikj第三趟第九十九页，共一百一十一页，2022年，8月28日

交换排序的特点在于交换，有冒泡和快速排序两种。冒泡排序（起泡排序）思想：小的浮起，大的沉底。从左端开始比较。第一趟：第1个与第2个比较，大则交换；第2个与第3个比较，大则交换，…关键字最大的记录交换到最后一个位置上；第二趟：对前n-1个记录进行同样的操作，关键字次大的记录交换到第n-1个位置上；依次类推，则完成排序。正序：时间复杂度为O(n)逆序：时间复杂度为O(n2)排序n个记录的文件最多需要n-1趟冒泡排序。2.3.7