第3章算法与数据结构

第3章算法与数据结构

3.1绪论3.2线性表3.3栈和队列3.4数组3.5树与二叉树3.6图3.7查找技术3.8排序技术第3章算法与数据结构3.1绪论程序=算法+数据结构算法是指对操作的描述，即操作的步骤；数据结构是指对数据的描述，即数据的类型和组织形式； 线性结构：线性表、栈、队列、数据的逻辑结构字符串、数组、广义表非线性结构：树、图

顺序存储数据结构数据的存储结构链式存储 检索、排序、数据的运算插入、删除、修改等

图3-1数据结构主要研究的三个方面问题3.1.1数据结构的基本概念1.数据：是指用符号来描述客观事物,包含数值、字符、图形、图像、声音等。2.数据项：是指能用来描述数据的最小单位。3.数据元素(记录)：是描述数据的基本单位，一个数据元素可以由一个或多个数据项组成。4.数据对象：是一类性质相同的数据元素的集合，是数据的子集。数据结构的基本概念5.数据结构数据结构是指相互之间有关系的数据元素的集合。组成：数据和结构数据：数据元素的集合；结构：数据元素之间关系的集合。数据元素之间的关系：（1）集合结构：所有数据元素“属于同一个集合，关系松散。（2）线性结构：数据元素之间存在“一对一”的相邻关系（3）树状结构：数据元素之间存在“一对多”的层次关系（4）图状结构：数据元素之间存在“多对多”的任意关系逻辑结构和存储结构分类：逻辑结构和存储结构。（1）逻辑结构：用数学模型来描述数据元素之间的逻辑关系一个数据的逻辑结构包括两个方面内容：①数据元素的信息；②数据元素之间的前后关系（前驱和后继）。表示方法：Data_Structure=（D，R）D为数据元素的有限集合，R为D上关系的有限集合例如，每周的数据结构表示为：Week=(D,R)D={周一,周二,周三,周四,周五,周六,周日}R={(周一,周二),(周二,周三),(周三,周四),(周四,周五),(周五,周六),(周六,周日)}逻辑结构和存储结构(2)存储结构：数据的逻辑结构在计算机内的存储形式。分类：顺序存储结构、链式存储结构等顺序存储结构的特点：借助于数据元素在存储器中的相邻位置来表示数据元素之间的逻辑关系。即逻辑上相邻的数据元素在物理存储地址上也相邻。链式存储结构的特点：使用一组任意的存储单元来存储线性表中的数据元素，借助于指示数据元素存储地址的指针来表示数据元素之间的逻辑关系。即逻辑上相邻的数据元素在物理存储地址上不一定相邻。另外还有索引存储结构和散列存储结构，但是它们都是通过顺序存储结构和链式存储结构复合而成。数据的逻辑结构和数据的存储结构是数据结构不可分开的两个方面。一方面，数据的逻辑结构是数据结构的抽象；另一方面，数据的存储结构是数据结构的具体实现在进行数据处理时候，一种数据的逻辑结构可以依据需要而采用多种不同的存储结构，只要能反映出所要求的逻辑关系即可。但是，选用其中最合适的存储结构对于提高数据处理的效率是非常重要的。

3.1.2算法

1.算法的定义算法：是问题求解逻辑步骤的一种准确而完整地描述。同一个算法如果采用不同的编程语言能够编写出不同的程序，所以，算法不等于程序，程序的编写也绝不可能优于算法的设计。描述算法的工具：自然语言、传统流程图、N-S流程图、伪代码、类计算机语言、计算机语言。

2.算法的基本特性

（1）有穷性：一个算法应包含有限的操作步骤（2）确定性：一个算法中的每一步骤必须有确定的含义，不能是含糊不清的。并且算法只有一个入口和一个出口。（3）可行性：一个算法应可以有效地执行（4）输入：一个算法有零个或多个外部输入。零个输入是指算法本身具有初始条件。（5）输出：一个算法至少要有一个输出。3.算法的基本要素两个基本要素：（1）算法中对数据对象的运算和操作：算法中基本的运算和操作包括算术运算、关系运算、逻辑运算和数据传输。（2）算法的控制结构：是指算法中各个操作之间的先后执行次序。一个算法的执行次序可以使用顺序、选择和循环三种基本结构组合而成。

4.算法设计的基本方法

（1）列举法：根据实际问题，列举出所有可能的情况（2）归纳法：通过对特殊的情况进行归纳分析后找出一般的关系。（3）递推法：从已知的条件逐渐推出结果。它也属于归纳法。（4）递归法：先将复杂问题逐层分解（即回推）成最简单的问题，当解决了最简单的问题后，再沿着原来分解的逆过程逐步回归（即递推）以便解决复杂问题（5）减半递推法：将复杂问题的规模减少一半，并且重复进行减半的过程。

5.算法的评价

（1）正确性：根据算法编写的程序能够得到满足问题要求的结果。（2）可读性：算法首先应是便于理解、其次才是计算机可以执行。（3）健壮性：输入不合法数据时算法能作出相应的处理，而不是陷入瘫痪。（4）高效率：根据算法编写的程序有较快的运算速度。（5）低存储量：根据算法编写的程序在运行时占用较少的存储空间。6.算法的复杂度（1）算法的时间复杂度算法的时间复杂度：是指执行算法所需要的计算工作量。算法的计算工作量应使用算法在执行过程中的基本运算执行次数来度量。算法执行的基本运算次数与问题的规模有关例如，两个30阶矩阵相乘的基本运算次数一定大于两个5阶矩阵相乘的基本运算次数。算法的复杂度（2）算法的空间复杂度

算法的空间复杂度：是指执行算法所需存储空间的度量。它包括算法程序占用的存储空间、输入的原始数据占用的存储空间和执行算法所需额外占用的存储空间（如在链式存储结构中，既要存储数据又要额外存储链接地址以便来表示数据元素之间的关系）。

3.2线性表

3.2.1线性表的基本概念线性表是最简单的一种数据结构，它是由一组数据元素组成。一年的月份号（1，2，3，…，12）是一个线性表，每个数据元素是一个整型数。英文小写字母表（a，b，c，…，z）是一个线性表，每个数据元素是一个小写字母。学生成绩表也是一个线性表，每个数据元素是由学号、姓名、数学、外语、计算机等数据项组成。

线性表的基本概念

综上所述，线性表是由n（n≥0）个类型相同的数据元素a1，a2，…，ai-1，ai，ai+1，…，an组成的有限序列。一般可以表示为：L=（a1，a2，…，ai-1，ai，ai+1，…，an）其中，L称为线性表的名称。n称为线性表的长度。当n=0时称为空线性表。非空线性表的特征①有且只有一个根结点，它没有前驱结点。②有且只有一个终端结点，它没有后继结点③除根结点和终端结点外，每个结点有且只有一个直接前驱结点，有且只有一个直接后继结点。

3.2.2线性表的顺序存储及其基本运算

在计算机中存放线性表，主要有两种基本存储结构：顺序存储结构和链式存储结构。顺序存储结构：把线性表中逻辑结构上相邻的数据元素依次存放在计算机内一组物理地址连续的存储单元中，即把逻辑关系上相邻接的数据元素存储在物理地址也相邻接的存储单元之中。顺序表：用顺序存储结构来存储的线性表。顺序表具有的两个基本特点：（1）顺序表的所有数据元素所占的存储空间是连续的；（2）顺序表的各个数据元素在存储空间中是按照逻辑顺序依次存放的。线性表的顺序存储假设长度为n的顺序表（a1，a2，…，ai-1，ai，ai+1，…，an）中每个数据元素所占的存储空间相同（假设都为k字节），并且第i个数据元素ai的存储地址用Address（ai）表示，顺序表中第i个数据元素ai在计算机存储空间中的存储地址可以表示为：Address（ai）=Address（a1）+（i-1）*k（1≤i≤n）若知道顺序表的起始地址Address（a1）和每个数据元素所占的字节数k，则顺序表中任意一个数据元素都可随机存取。顺序表的存储结构是一个随机存取的存储结构。1.顺序表的插入运算（1）在通常情况下，若在第i（1≤i≤n+1）个数据元素之前插入一个新的数据元素时，要从最后一个（即第n个）数据元素开始，直到第i个数据元素之间共n-i+1个数据元素依次向后移动一个位置。（2）在特殊情况下，若要在顺序表第一个数据元素之前插入一个新的数据元素，则需要依次向后移动表中所有的n个数据元素若要在顺序表最后一个数据元素之后插入一个新的数据元素，只要在表的末尾后面增加一个新的数据元素即可。（3）在平均情况下，插入一个新的数据元素需要移动表中一半的数据元素。数据元素的移动消耗很多时间，因此顺序表的插入运算效率低。2.顺序表的删除运算（1）在通常情况下，若要在第i（1≤i≤n）个位置上删除一个数据元素时，要从第i+1个数据元素开始，直到最后一个数据元素依次向前移动一个位置。（2）在特殊情况下，若要删除第一个数据元素，则需要依次向前移动表中所有其它的数据元素；若要删除最后一个数据元素，只要删除表中末尾一个数据元素即可。（3）在平均情况下，删除一个数据元素需要移动表中一半的数据元素。数据元素的移动消耗很多时间，因此顺序表的删除运算效率低

线性表顺序存储结构的优缺点：

（1）优点：存储的物理位置相邻，不需要增加额外的存储空间可以根据初始地址随机存取线性表中任一数据元素运算简单方便，存储空间紧凑，占用最少存储空间（2）缺点：进行插入、删除操作时需要移动大量的数据元素，消耗许多处理时间；由于占用连续存储空间，只能进行预先静态分配，若开辟的存储空间太大，造成存储空间浪费，若开辟的存储空间小，当分配的存储空间已满时，再插入数据就会发生“上溢”错误，不便于扩充；由于使用相邻整块存储单元，会产生较多的碎片。结论：线性表的顺序存储结构不适用于大线性表或者其中数据元素经常变动的线性表。适合于主要是进行查找而很少做插入和删除操作。

3.2.3线性表的链式存储及其基本运算

链式存储结构：使用一组任意的存储单元来存储线性表中的数据元素，借助于指示数据元素存储地址的指针来表示数据元素之间的逻辑关系。即逻辑上相邻的数据元素在物理存储地址上不一定相邻。线性链表：用链式存储结构来存储的线性表简称为链表。根据链接的方式把链表分为单链表、双链表和循环链表等。链表适合于频繁地进行插入和删除操作。

1．单链表

每个结点的存储空间被分为两个部分。数据域：存储结点的值；指针域：存储指向直接后继的指针（地址）。所有的结点通过指针（地址）的连接按其逻辑顺序链接在一起而组成了链表。线性单链表：每一个结点只包含一个指针域。头指针（HEAD）：为了增强程序的可读性，在线性单链表中增加一个指针指向链表的第一个结点。最后一个结点由于没有直接后继结点，则它的指针域值为空(用NULL、0或∧表示)，表示链表终止。由于任意一个结点的存取都必须从头指针出发，顺着链域逐个结点往下进行，所以单链表是顺序存取的存储结构。

（1）建立线性单链表

建立线性单链表①头插法建立线性单链表：从空链表开始，每次申请生成一个新的结点，将读入的数据存放到数据域，并设置指针域为空。然后将新结点插入到链表头结点的后面，即新结点的指针域存储原来头结点指针域存放的指针，再将头结点的指针域存储指向新结点的指针（或存储地址），重复以上的操作，直到读入的数据为结束标志。使用头插法建立线性单链表时，结点的逻辑顺序与输入数据元素的顺序相反。

（1）建立线性单链表

建立线性单链表②尾插法建立线性单链表：从空链表开始，每次申请生成一个新的结点，将读入的数据存放到数据域，并设置指针域为空。然后将新结点插入到链表尾结点的后面，即原来链表尾结点的指针域存储指向新结点的指针（或存储地址），此时新结点转变为新的尾结点，重复以上操作，直到读入的数据为结束标志。使用尾插法建立线性单链表时，结点的逻辑顺序与输入数据元素的顺序相同

（2）线性单链表的查找

①按照值进行查找：从线性单链表的头指针出发，顺着链表逐个将结点数据域的值和要查找的给定值作比较。实际应用中，为了便于操作，需要在线性单链表中查找包含给定值x元素的前一结点存储位置（用指针pre指向），可以方便地在该结点后插入新的结点或者删除该结点后的结点。查找的结果如下：若单链表中存在要查找的给定值，则返回的（pre）为第一次找到的包含给定值x元素的前一结点位置；若单链表中不存在要查找的给定值，则返回的(pre)为单链表的最后结点位置。线性单链表的查找②按照序号进行查找：从线性单链表的头指针出发，顺着链表逐个结点往下扫描直到第i个结点为止。实际应用中，为了便于操作，在线性单链表中查找第i个结点的前一结点存储位置（用指针pre指向），就可以方便地在该结点后插入新的结点或者删除该结点后的结点。查找的结果：查找到结点（1≤i≤n），则返回的（pre）为第i个结点的前一结点位置；没查找到返回的(pre)为单链表的最后结点位置.

（3）线性单链表的插入

线性单链表的插入：在线性单链表中插入一个新的数据元素。①按照值进行插入：是在线性单链表中指定值数据元素之前插入一个新数据元素。运算过程：1）申请新结点：生成一个新结点，输入数据存放到数据域；2）查找：在单链表中查找包含给定值x元素的前一结点存储位置（用指针pre指向）；3）修改链接：首先设置新结点的指针域指向结点x，然后再设置x前一结点的指针域指向新结点。线性单链表的插入②按照序号进行插入：是指在线性单链表中第i个结点之前插入一个新的结点。运算过程：1）申请新结点：生成一个新结点，输入数据;2）查找：在单链表中查找第i个结点之前的结点ai-1的存储位置（用指针pre指向）；3）修改链接：首先设置新结点的指针域指向结点ai，再设置结点ai-1的指针域指向新结点（注意，在程序设计时此顺序不能颠倒）。在线性单链表的插入过程中，不需要移动数据元素，只要改变相关结点的指针就可以实现，提高了效率。

（4）线性单链表的删除

线性单链表的删除:是指在线性单链表中删除一个数据元素。①按照值进行删除：是指在线性单链表中删除指定值的数据元素。运算过程：1）查找：在单链表中查找包含给定值x元素的前一结点存储位置，用指针pre指向；2）修改链接：设置x的前一结点指向x的直接后继结点；3）释放结点：释放结点x所占用的存储空间。

线性单链表的删除

②按照序号进行删除：是指在线性单链表中删除第i个结点。运算过程：1）查找：在单链表中查找第i个结点之前的结点ai-1的存储位置（用指针pre指向）；2）修改链接：设置ai-1指向ai的直接后继结点ai+1，即把ai-1的指针域改变为存放结点ai指针域的值（为ai+1的存储地址），就能把结点ai从链上摘下；3）释放结点：最后释放结点ai所占用的存储空间链表的优缺点：①优点:在链表中进行插入、删除操作时只需要修改指针而不需要移动表中的数据元素.适合对于频繁进行插入、删除操作的线性表；②缺点:对链表中的数据元素只能顺着链表进行顺序存取而不能进行随机存取。

2．双链表

在线性单链表中，指针可以很方便地找到后继结点，但是却不能找到前驱结点；在线性单链表的每个结点中再增加一个指针域用来指向该结点的直接前驱。每个结点包含两个指针指向直接前驱结点的指针称为左指针(llink)，指向直接后继结点的指针称为右指针(rlink)，由此形成的线性链表就有两个不同方向的链，则称为双向链表，简称为双链表（doublelinkedlist）。3．循环链表将单链表中最后一个结点的指针域由空（NULL）改变为指向头结点而使链表头尾相接形成环状，称为单向循环链表，简称为循环链表（circularlinkedlist）。在单向循环链表中，只是对表的链接方式稍微改变一些，就使得可以从任意一个结点出发来访问表中所有其它的结点，提高了查找的效率。而线性单链表却做不到这一点。

循环链表

循环链表的特点：①循环链表增加一个头结点，其数据域可以依据需要设置，其指针域指向第一个结点。即循环链表的头指针HEAD指向头结点，而头结点指向第一个结点；②循环链表最后一个结点的指针域指向头结点而不是空。

3.3栈和队列

3.3.1栈及其基本运算1．栈的基本概念栈（stack）是一种特殊的线性表，它是限定仅在一端进行插入或删除操作的线性表。允许进行插入或删除操作的一端称为栈顶（top）；不允许进行插入、删除操作的另一端称为栈底（bottom）。不含数据元素的栈称为空栈。栈是根据“先进后出或“后进先出”的原则组织数据。向栈中插入一个数据元素称为入栈；从栈中删除一个数据元素称为退栈。

2．栈的顺序存储及其基本运算栈的顺序存储结构的基本运算：入栈运算、退栈运算、读栈运算。（1）顺序栈的入栈运算顺序栈的入栈运算是指在栈顶位置插入一个新的数据元素。运算过程：①修改指针：将栈顶指针加1（top加1）；②插入；在当前栈顶指针所指向的位置将新的数据元素插入。在顺序栈的入栈运算过程中，若栈顶指针已经指向栈存储空间的最后位置（即top=n），表明此时栈的空间已满，不能再进行入栈运算，否则会产生栈的上溢错误。

栈的顺序存储及其基本运算

（2）顺序栈的退栈运算顺序栈的退栈运算是指在栈顶位置取走一个数据元素并且把它赋给某个变量。运算过程：①退栈：将栈顶指针所指向的栈顶元素读取后并且赋给一个变量；②修改指针：将栈顶指针减1（top减1）。在顺序栈的退栈运算过程中，若栈顶指针已经为0时（即top=0），表明此时栈空，不能再进行退栈运算，否则会产生栈的下溢错误。

栈的顺序存储及其基本运算

（3）顺序栈的读栈运算顺序栈的读栈运算是指在栈顶位置读取一个数据元素并且把它赋给某个变量。运算过程：将栈顶指针所指向的栈顶元素读取并赋给一个变量，栈顶指针保持不变。在顺序栈的读栈运算过程中，若栈顶指针已经为0时（即top=0），表明此时栈空，不能再进行读栈运算，即读不到栈顶元素。

3．栈的链式存储及其基本运算

与一般的线性表类似，在程序设计时，栈也可以使用链式存储结构。用链式存储结构来存储的栈，称为带链的栈，简称为链栈。它其实就是运算受限的单链表，其插入和删除操作仅限制在链表的表头位置上进行，所以，栈顶指针就是链表的头指针，头指针指向栈顶结点（不带头结点）或者头结点（带头结点）。

3.3.2队列及其基本运算

1．队列的基本概念队列也是一种特殊的线性表，它是限定在一端进行插入操作，而在另一端进行删除操作的线性表。其中，允许进行插入操作的一端称为队尾，允许进行删除操作的另一端称为队头。不含数据元素的队列称为空队列。队列是根据“先进先出或“后进后出的原则组织数据，一般用队头指针（front）指向队头位置数据元素的前一个单元，用队尾指针（rear）指向队尾位置数据元素。向队列中插入一个数据元素称为入队，插入的结点只能加到队尾。从队列中删除一个数据元素称为退队，删除的结点只能来自队头位置。

2．队列的顺序存储及其运算

与一般的线性表类似，在程序设计时，可以使用一维数组作为队列的顺序存储空间。用顺序存储结构来存储的队列简称为顺序队列。队列的顺序存储结构可以采用循环队列的形式。将顺序存储的队列的最后一个位置指向第一个位置，从而使顺序队列形成逻辑上的环状空间，称为循环队列。当循环队列的最后一个位置已经被使用而还要进行入队运算时，此时只要第一个位置空闲，就可以将数据元素插入到第一个位置，即将第一个位置作为新的队尾。可以设置n表示循环队列的最大存储空间。循环队列在循环队列中，从队头指针front指向的下一个位置到队尾指针rear指向的队尾位置之间的所有数据元素都是队列中的数据元素。循环队列具有两种基本运算：入队运算、退队运算。循环队列的初始状态为空，此时front=rear=n。循环队列进行一次退队运算，队头指针front就加1，若front=n+1时，则设置front=1。循环队列进行一次入队运算，队尾指针rear就加1，若rear=n+1时，则设置rear=1。由于在循环队列中，循环队列为空或满都有front=rear，即根据front=rear不能判定队列是空还是满，一般还要增加一个标志sign，用sign=0表示队列空；用sign=1且front=rear表示队列满。

循环队列的两种基本运算

（1）循环队列的入队运算循环队列的入队运算是指在循环队列的队尾位置插入一个新的数据元素。运算过程：①修改队尾：将队尾加1（即rear=rear+1），此时若rear=n+1则设置rear=1；②结点插入：将新结点插入到将队尾指针所指向的位置。当sign=1并且rear=front，循环队列空间已满，就不能进行入队，否则会产生上溢错误。（2）循环队列的退队运算。循环队列的退队运算是指在循环队列的队头位置退出一个数据元素并且保存在指定的变量中。运算过程：①修改队头：先将队头加1（即front=front+1），此时若front=n+1则设置front=1；②结点退出保存：将队头指针所指向位置的数据元素退出并且赋给一个指定变量。当sign=0时循环队列为空，就不能进行退队，否则会产生下溢错误。

3.4数组

3.4.1数组的基本概念数组是一种特殊的线性表，它的数据元素自身也是一个线性表。在科学计算中，矩阵是一种常用的数学对象，在使用高级语言编写程序时，一般将一个矩阵描述为一个二维数组。所以在此主要研究二维数组。因为计算机的内存空间是一维结构，而数组是多维结构，所以使用计算机的内存单元存储数组元素存在次序问题。二维数组有两种存储次序：以行为主序的顺序存储和以列为主序的顺序存储。

3.4.2数组的存储结构

以行为主序的顺序存储是将数组中的数据元素从第一行开始一行接一行地顺序存储在计算机内连续的存储空间中。以列为主序的顺序存储是将数组中的数据元素从第一列开始一列接一列地顺序存储在计算机内连续的存储空间中。例如，C语言的数组在计算机中采用以行为主序的顺序存储方式。在二维数组以行为主序的顺序存储中，数据元素aij在一维内存空间中存储地址为：Address(aij)=Address(a11)+[(i-1)*n+j-1]k其中，Address(a11)为二维数组中第一个数据元素的存储地址，每个数据k字节,n为列数。

3.5树与二叉树

树是一类非线性数据结构，其中最为常用的是二叉树。使用图形来表示树这样的数据结构时，很像是自然界中一棵倒长的树。在现实生活中，有许多能用树的结构表示的关系：人类家族的血缘关系、银行的行政关系、书目录的层次关系等。3.5.1树的基本概念树（tree）是n（n≥0）个结点的有限集合，在任意一棵非空树中：①有且仅有一个结点称为树的根（root）；②其余n-1个结点被分成为m（m≥0）个互相不相交的有限集合，其中每一个集合自身又是一棵树，称为根结点的子树（subtree）。树的定义是一个递归定义。树的基本概念在树的结构中，树中的每个数据元素也称为结点。可分为根结点、分支结点和叶子结点。每个结点的上一层结点称为该结点的双亲结点。没有双亲的结点称为树的根。每个结点的下一层结点称为该结点的孩子结点。每个结点拥有的子树数目称为该结点的度。所有结点的度中最大的值称为树的度。树中度为0的结点称为叶子结点。从根结点开始到某结点的层数称为该结点的深度。所有结点的层数中最大的值称为树的深度。若树中结点的各棵子树是从左至右有先后次序的，则称该树为有序树，否则称为无序树。

3.5.2二叉树及其基本性质

由于对二叉树的操作算法相对简单，所以二叉树在树结构的实际应用中起着重要的作用，它解决了树的存储结构及其运算中的复杂性问题。1．什么是二叉树二叉树是n（n≥0）个结点的有限集合。它或者为空集，或者是由一个根结点加上两棵互相不相交的左子树和右子树组成，并且左子树和右子树也都是二叉树。二叉树的特点：①二叉树的每个结点至多有二棵子树（即不存在度大于2的结点）。②二叉树的子树分为左子树、右子树，其次序也不能任意颠倒互换。

2．二叉树的基本性质

性质1：在二叉树的第i（i≥1）层上，至多有2i-1个结点。性质2：在深度为k（k≥1）的二叉树上，至多有2k-1个结点。性质3：在任意一棵二叉树中，叶子结点的数目总比度为2的结点数目多一个。性质4：在具有n个结点的一棵二叉树中，其深度至少为【log2n】＋1。其中【log2n】为取log2n的整数部分

二叉树的基本性质

满二叉树除最后一层叶子结点以外的各层任何结点都有两个子结点，并且所有的叶子结点都在同一层上。就是说满二叉树中的每一层的结点数都达到了最大值。完全二叉树除最后一层外，每一层结点数都达到最大值；最后一层结点在该层左对齐，但可以缺少右边的若干结点。完全二叉树的特点是：（1）如果最大层次为k，则叶子结点都在第k－1层或k层上。（2）对任意结点，如果其右子树的最大层次为k，则其左子树的最大层次为k或k＋1。

二叉树的基本性质

性质5：在具有n个结点的一棵完全二叉树中，其深度为【log2n】＋1。其中【log2n】为取log2n的整数部分。性质6：在具有n个结点的一棵完全二叉树中，若把结点按层序编号（从上层到下层，每层从左到右)，则对任一结点i（1≤i≤n)，有：（1）如果i＝1，则结点i是二叉树的根，无双亲结点；如果i>1，则结点i的双亲结点编号是【i/2】。其中【i/2】为取i/2的整数部分。（2）如果2i≤n，则结点i的左孩子结点编号是2i；否则无左孩子结点。（3）如果2i+1≤n，则结点i的右孩子结点编号是2i＋1；否则无右孩子结点。性质7：在具有n个结点的一棵完全二叉树中，当n为偶数时，有且只有一个度为1的结点；当n为奇数时，则没有度为1的结点。性质8：在具有n个结点的一棵完全二叉树中，编号大于【n/2】的结点均为叶子结点。其中【n/2】为取n/2的整数部分。

3.5.3二叉树的存储结构

1．二叉树的顺序存储结构在二叉树中，将所有结点的数值按照由上到下、由左到右的顺序来存储在一个一维数组（线性结构）中，这样的存储方式称为二叉树的顺序存储结构。对于满二叉树或完全二叉树可以使用顺序存储结构来存储。因为满二叉树或完全二叉树可以按照层的顺序进行顺序存储，并能很快确定每一个结点的双亲结点和左右孩子结点，能明确树中各个结点的之间的相互关系，并且可以节省存储空间。对于一般的二叉树应使用链式存储结构来存储。

2．二叉树的链式存储结构在二叉树的链式存储结构中，存储二叉树的每个结点的存储空间也被分为两个部分：数据域和指针域。由于二叉树的每个结点可以有两个子结点，使得每个结点上需要有两个指针域，分别指向其左子树和右子树，这种二叉树的链式存储结构称为二叉链表。与分别指向直接前驱结点和直接后继结点的双向链表不同，二叉链表的两个指针一个用于指向该结点的左子结点，另一个用于指向该结点的右子结点。3.5.4二叉树的遍历不重复地访问二叉树中的所有结点。一般先遍历左子树，再遍历右子树。根据访问根结点的次序，可分为三种：前序遍历、中序遍历、后序遍历二叉树的前序遍历（根左右）先访问根结点，然后遍历左子树，最后遍历右子树。再遍历左右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。如下图前序序列：ABDECFABCDEF二叉树的中序遍历（左根右）先遍历左子树，然后访问根结点，最后遍历右子树。再遍历左右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。如下图中序序列：DBEAFCABCDEF二叉树的后序遍历（左右根）先遍历左子树，然后遍历右子树，最后访问根结点。再遍历左右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。如下图后序序列：DEBFCAABCDEF二叉树的遍历例：设一颗二叉树的中序遍历结果为DBEAFC，前序遍历结果为ABDECF，则后序遍历结果为

。结果：DEBFCA

3.7查找技术

3.7.1查找的基本概念查找:在一个含有若干记录（或数据元素）的列表中找出关键字值与给定值相同的记录的过程。若找到相应的记录，则查找成功，返回记录在表中的位置或记录的信息；否则，查找失败，返回空地址或失败的信息。在查找过程中，若只是对表内数据进行查询，则称为静态查找；在对表内数据进行查询的同时，还对表进行更新（如插入或删除）操作，则称为动态查找。

3.7.2基于线性表的查找

基于线性表的查找分为：顺序查找、二分法查找和分块查找。1．顺序查找顺序查找是最简单的一种查找方法。它是从线性表的任意一端开始，从前向后或从后向前逐个将表中数据元素与给定的关键字进行比较，若表中某个记录的关键字值与给定的关键字值相等，则查找成功；若到达表的另一端后，所有记录的关键字值与给定的关键字值都不相等，则查找失败。顺序查找的存储结构既可以采用顺序存储结构，也可以采用链式存储结构。只能使用顺序查找的两种情况：①对于无序线性表（即线性表中数据元素排列是无序的），无论是采用顺序存储结构，还是采用链式存储结构，都必须使用顺序查找；②对于有序线性表（即线性表中数据元素排列是有序的），若采用的是链式存储结构，也必须使用顺序查找。

基于线性表的查找

（1）线性表在顺序存储结构下的顺序查找返回为要查找的数据元素x在线性表中的序号；若不存在时，返回NULL。若线性表的存储空间中含有多个数据元素值为x的记录，则只能返回第一个查找到的数据元素x在线性表中的序号。例如，已知线性表（5，15，20，40，60，35，50，70，85，100）用顺序存储结构来存储。若顺序查找与给定的关键字值“60”相等的数据元素，则要将给定的关键字从前向后依次与线性表中第1个位序（数据元素为5）到第5个位序（数据元素为60）之间的数据元素进行比较，返回的是要查找的数据元素在线性表中的序号5。

基于线性表的查找

（2）线性表在链式存储结构下的顺序查找返回要查找的数据元素x在线性链表中的存储地址；若不存在时，返回NULL。若线性链表的存储空间中含有多个数据元素值为x的记录，只能返回第一个查找到的数据元素x在线性链表中的存储地址。顺序查找的算法简单，查找的效率与数据元素所在的位置有关。优点是对表中数据元素的存储没有特别要求；它的缺点是在平均情况下查找大约要与表中一半的数据元素进行比较，当线性表的长度很大时效率较低，即不适用于长度较大的线性表的查找。

2．二分法查找

线性表采用顺序存储结构存储并按照关键字有序排列。二分查找的查找过程：①若线性表中间位置记录的关键字值与给定的关键字值相等，则查找成功；②若线性表中间位置记录的关键字值大于给定的关键字值，则在线性表的前半部分子表以同样的方法进行查找；③若线性表中间位置记录的关键字值小于给定的关键字值，则在线性表的后半部分子表以同样的方法进行查找。重复以上过程，直到查找成功；或者直到子表不存在为止，此时查找失败。长度为n的有序线性表在最坏情况下，顺序查找需要比较n次，而二分查找只需要比较log2n次。

3.8排序技术

按照排序过程中依据的原则不同，将排序分为以下几类：①插入排序：将无序序列中的数据元素依次插入到有序序列中。②交换排序：通过比较数据元素的关键字大小决定是否进行交换。例如，冒泡排序、快速排序。③选择排序：将无序序列中关键字值最小的数据元素依次放到有序序列中的指定位置。例如，简单选择排序、树型选择排序、堆排序。

3.8.1插入类排序

插入排序是指每次将一个待排序的数据元素插入到有序序列中，直到将所有待排序的数据元素全部插入为止。常用的插入排序有直接插入排序、