基本数据结构与算法

基本数据结构与算法第一页，共七十三页，2022年，8月28日二级ACCESS—基本数据结构与算法本章主要内容算法

数据结构

数据结构研究的主要内容

基本概念和术语

数据结构类型

线性结构和非线性结构

顺序存储与链式存储

线性表

栈和队列

线性链表

树与二叉树

查找和排序

图

第二页，共七十三页，2022年，8月28日二级ACCESS—基本数据结构与算法3.1算法算法的基本概念算法：解题方案的准确而完整的描述。算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。算法不等于程序，程序不可能优于算法。基本特性可行性：根据实际问题设计的算法，执行得到满意结果确定性：每一步骤必须有明确定义，不允许有多义性。有穷性：算法必须能在有限的时间内做完。输入和输出：拥有足够的情报，方可执行。第三页，共七十三页，2022年，8月28日二级ACCESS—基本数据结构与算法3.1算法算法的基本要素1.对数据对象的运算和操作算术运算：＋、－、×、÷等逻辑运算：>、<、＝、>=、<=、!=等关系运算：and、or、not等数据传输：w、r等2.算法的控制结构算法中各操作之间的执行顺序描述算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言等算法可以用顺序、选择、循环三种基本机构组合而成。第四页，共七十三页，2022年，8月28日二级ACCESS—基本数据结构与算法3.1算法算法设计基本方法（1）列举法：根据问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。（2）归纳法：通过列举少量的特殊情况，经过分析，最后找出一般的关系。（3）递推：是指从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。（4）递归：将问题逐层分解的过程。（5）减半递推技术：“减半”，是指将问题规模减半，而问题性质不变；“递推”，是指重复“减半”过程。（6）回溯法：分析问题，找出一个解决总线索，然后沿着这个线索逐步试探。第五页，共七十三页，2022年，8月28日二级ACCESS—基本数据结构与算法3.1算法算法的复杂度：时间复杂度、空间复杂度

算法的时间复杂度算法时间复杂度是指执行算法所需要的计算工作量。工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即

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

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

c9

c4

c2

c12

c10

c11

c5

c3

c6

c7

c8

3.2.1数据结构研究的主要内容特点课程的先后关系用图结构描述；通过实施创建图结构，按要求将图结构中的顶点进行线性排序。

第十页，共七十三页，2022年，8月28日二级ACCESS—基本数据结构与算法

数据结构主要研究以下三个方面的问题：数据的逻辑结构：数据集合中各元素的信息，及元素之间所固有的逻辑关系（前后件关系）

数据的存储结构：各数据元素在计算机中的存储关系

对各种数据结构进行的运算

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

数据结构是一门研究数据组织、存储和运算的一般方法的学科。是相互有关联的数据元素的集合。3.2.2基本概念和术语

第十二页，共七十三页，2022年，8月28日二级ACCESS—基本数据结构与算法能输入到计算机中并能被计算机程序处理的符号的集合。整数(1,2)、实数(1.1,1.2)字符串(Beijing)、图形、声音。数据结构是一门研究数据组织、存储和运算的一般方法的学科。3.2.2基本概念和术语第十三页，共七十三页，2022年，8月28日二级ACCESS—基本数据结构与算法计算机管理图书问题

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

数据结构是一门研究数据组织、存储和运算的一般方法的学科。

3.2.2基本概念和术语

第十四页，共七十三页，2022年，8月28日二级ACCESS—基本数据结构与算法最简单的办法之一是建立一张表，每一本书的信息在表中占一行，如

数据结构是一门研究数据组织、存储和运算的一般方法的学科。

3.2.2基本概念和术语

第十五页，共七十三页，2022年，8月28日二级ACCESS—基本数据结构与算法如何将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

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

数据结构是一门研究数据组织、存储和运算的一般方法的学科。

3.2.2基本概念和术语

第十六页，共七十三页，2022年，8月28日二级ACCESS—基本数据结构与算法对数据结构中的节点进行操作处理(插入、删除、修改、查找、排序)

数据结构是一门研究数据组织、存储和运算的一般方法的学科。

3.2.2基本概念和术语

第十七页，共七十三页，2022年，8月28日二级ACCESS—基本数据结构与算法数据元素(DataElement)

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

有时一个数据元素可由若干数据项(DataItem)组成。数据项是数据的最小单位。数据元素亦称节点或记录。3.2.2基本概念和术语

第十八页，共七十三页，2022年，8月28日二级ACCESS—基本数据结构与算法数据结构可描述为Group=（D，R）有限个数据元素的集合有限个节点间关系的集合3.2.2基本概念和术语

第十九页，共七十三页，2022年，8月28日二级ACCESS—基本数据结构与算法1．数据的逻辑结构

2、数据的存储结构

3、数据的运算：检索、排序、插入、删除、修改等。

A．线性结构

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

B链式存储

线性表栈队树形结构图形结构数据结构的三个方面

3.3数据结构类型

第二十页，共七十三页，2022年，8月28日二级ACCESS—基本数据结构与算法3.3.1线性结构和非线性结构

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

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

树形结构

第二十二页，共七十三页，2022年，8月28日二级ACCESS—基本数据结构与算法ABCDEFGH树形结构—结点间具有分层次的连接关系HBCDEFGA3.3.1线性结构和非线性结构

树形结构

第二十三页，共七十三页，2022年，8月28日二级ACCESS—基本数据结构与算法3.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日二级ACCESS—基本数据结构与算法Lo+（n-1)*m元素n……..元素i……..元素2元素1Lo

Lo+mLo+(i-1)*m存储地址存储内容Loc(a)=Lo+（i-1)*m每个元素所占用的存储单元个数3.3.2顺序存储与链式存储

顺序存储常用于线性数据结构，将逻辑上相邻的数据元素存储在物理上相邻的存储单元里。三个弱点插入或删除操作时，需移动大量元数。长度变化较大时，需按最大空间分配。表的容量难以扩充第二十五页，共七十三页，2022年，8月28日二级ACCESS—基本数据结构与算法每个节点都由两部分组成：数据域和指针域。数据域：存放元素本身的数据，指针域：存放指针，体现数据元素之间的逻辑联系3.3.2顺序存储与链式存储1536元素21400元素11346元素3

∧元素4head1345

链接存储结构特点

比顺序存储结构的存储密度小(每个节点都由数据域和指针域组成)。逻辑上相邻的节点物理上不必相邻。插入、删除灵活(不必移动节点，仅改变节点中的指针)。

链接存储结构

第二十六页，共七十三页，2022年，8月28日二级ACCESS—基本数据结构与算法1346元素31536…….……..…….1536元素21400…….……..…….∧元素413461400元素11345指针存储内容存储地址1536元素21400元素11346元素3

∧元素4head1345

3.3.2顺序存储与链式存储链式存储的地址映射表第二十七页，共七十三页，2022年，8月28日二级ACCESS—基本数据结构与算法3.3.3线性表线性表的基本概念

线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。非空线性表的结构特征有且只有一个根结点a1，它无前件；有且只有一个终端结点an，它无后件；除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。结点个数n称为线性表的长度，当n=0时，称为空表。Lo+（n-1)*m元素n……..元素i……..元素2元素1Lo

Lo+mLo+(i-1)*m存储地址存储内容Loc(a)=Lo+（i-1)*m第二十八页，共七十三页，2022年，8月28日二级ACCESS—基本数据结构与算法在线性表上常用的运算有初始化、求长度、取元素、修改、插入、删除、检索、排序。

线性表的插入操作

在线性表L中第i个数据元素之前插入数据元素e检查插入要求的有关参数的合理性把原来第n个数据元素至第i个元素（共n-i+1)依次后移一个数组元素的位置。把新数据元素放在第i个位置上修正线性表的数据元素个数。线性表中含有n个数据元素，在进行插入操作时，若假定在n+1个位置上插入元素的可能性均等，则平均移动元素的个数为：n/23.3.3线性表第二十九页，共七十三页，2022年，8月28日二级ACCESS—基本数据结构与算法线性表的插入操作（时间复杂度O(n)）插入前插入xlastMaxsize-1aia1a0ai-1ai+1an-1a0a1ai-1aian-1lastMaxsize-1后移后ai＋1a0a1ai-1ai+1ai+1anxlastMaxsize-1插入后ai+23.3.3线性表第三十页，共七十三页，2022年，8月28日二级ACCESS—基本数据结构与算法线性表的删除操作（时间复杂度O(n)）3.3.3线性表a0a1ai-1aiai+1an-1删除lastmaxsize删除前a0a1ai-1ai+2an-1lastmaxsize删除后ai+1第三十一页，共七十三页，2022年，8月28日二级ACCESS—基本数据结构与算法3.3.4栈和队列栈和队列是两种运算时要受到某些特殊限制的线性表，故也称为限定性的数据结构。栈：限定只能在表的一端进行插入和删除的特殊的线性表,此种结构称为后进先出。设栈s=（a1，a2，…,ai，…，an）其中a1是栈底元素，an是栈顶元素。栈顶（top)：允许插入和删除的一端；约定top始终指向新数据元素将存放的位置。栈底（bottom):不允许插入和删除的一端。

a1a2….an

进栈出栈栈顶栈底第三十二页，共七十三页，2022年，8月28日二级ACCESS—基本数据结构与算法队列的主要运算

设置一个空队列；插入一个新的队尾（rear）元素，称为进队；删除队头（front）元素，称为出队；读取队头元素；a1,

a2,

a3,

a4,…………

an-1,

an队头队尾3.3.4栈和队列队列：限定只能在表的一端进行插入，在表的另一端进行删除的线性表。此种结构称为先进先出（FIFO）表。第三十三页，共七十三页，2022年，8月28日二级ACCESS—基本数据结构与算法

3210(a)rear=front=0(队空）

e3

e4

(c)e1,e2出队，e4入队rear=4fronte1e2e3

(b)rearfront(b)e1,e2,e3入队3.3.4栈和队列队列的主要运算

队空时，令rear=front=0;元素个数＝rear-front当有新元素入队时，尾指针加1，当有元素出队时，头指针加1。故在非空队列中，头指针始终指向队头元素前一个位置，而尾指针始终指向队尾元素的位置第三十四页，共七十三页，2022年，8月28日二级ACCESS—基本数据结构与算法循环队列元素个数=(rear-front+n)modn

a1,

a2,

a3,

a4,…………

an-1,

an队头队尾3.3.4栈和队列循环队列：首尾相接的队列，逻辑上形成一个环状。第三十五页，共七十三页，2022年，8月28日二级ACCESS—基本数据结构与算法3.3.5线性链表线性表顺序存储结构的特点简单、方便，要求数据元素依次存放在连续的存储单元中，从而利用数据元素的存储顺序表示相应的逻辑顺序，这种存储方式属于静态存储形式。暴露的问题在做插入或删除元素的操作时，会产生大量的数据元素移动；对于长度变化较大的线性表，要一次性地分配足够的存储空间，但这些空间常常又得不到充分的利用；线性表的容量难以扩充。第三十六页，共七十三页，2022年，8月28日二级ACCESS—基本数据结构与算法

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

数据域存放数据，指针域存放后继结点的地址，最后一个结点的指针域为空。逻辑上相邻的数据元素在内存中的物理存储空间不一定相邻。线性链表分为：单链表、双链表、循环链表

3.3.5线性链表

a1

a2∧an

a3

L…..带头结点的单链表第三十七页，共七十三页，2022年，8月28日二级ACCESS—基本数据结构与算法单链表：每个结点只有一个指针域，由该指针只能找到其后件结点。3.3.5线性链表第三十八页，共七十三页，2022年，8月28日二级ACCESS—基本数据结构与算法3.3.5线性链表线性链表的计算

在指定节点前插入一个元素(不必移动节点，仅改变节点中的指针，且不会出现“上溢”现象)删除指定节点(不必移动节点，仅改变节点中的指针)合并两个线性链表逆转线性链表复制线性链表线性链表排序线性链表查找第三十九页，共七十三页，2022年，8月28日二级ACCESS—基本数据结构与算法

b

a

b

a

xPP单链表的插入运算：在节点a之后插入一新节点S3.3.5线性链表第四十页，共七十三页，2022年，8月28日二级ACCESS—基本数据结构与算法ai-1

a1

ai

ai+1

Lp

单链表的删除运算：删除节点ai3.3.5线性链表

a1

qq

第四十一页，共七十三页，2022年，8月28日二级ACCESS—基本数据结构与算法循环链表:

首尾相接的链表

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

2、增加了头结点，使得任何时候循环链表中至少有一个结点。1、从表中任一结点出发均可找到表中其他结点，提高查找效率。

L

a1

a2

an

…..循环单链表3.3.5线性链表L

空链表第四十二页，共七十三页，2022年，8月28日二级ACCESS—基本数据结构与算法双向链表：在每个结点中设置两个指针，一个指向后继，一个指向前驱。可直接确定一个结点的前驱和后继结点。可提高效率。datanextbefore非空双向循环链表：LAB3.3.5线性链表第四十三页，共七十三页，2022年，8月28日二级ACCESS—基本数据结构与算法3.3.5线性链表线性链表的特点

插入、删除节点方便(不必移动节点，仅改变节点中的指针)只能顺序存取（查找只能从头指针开始），不能随即存取。适应于数据的动态变化第四十四页，共七十三页，2022年，8月28日二级ACCESS—基本数据结构与算法练习参考答案1～6、BCDABB7、插入、删除结点方便8、前趋结点，后继结点9、n/2第四十五页，共七十三页，2022年，8月28日二级ACCESS—基本数据结构与算法树的定义：由一个或多个结点组成的有限集合。仅有一个根结点，结点间有明显的层次结构关系。

A

C

G

T2

D

H

IT3

J

M

B

EL

K

T1

F

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

A

C

G

T2

D

H

IT3

J

M

B

EL

K

T1

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

空二叉树

仅有根结点

右子树为空

左子树为空左右子树均非空因为树的每个结点的度不同，存储困难，使对树的处理算法很复杂。所以引出二叉树的理论。3.3.6树与二叉树第四十八页，共七十三页，2022年，8月28日二级ACCESS—基本数据结构与算法满二叉树

42

3

16

78910

11

12

13

14

15

5

特点：所有分支结点都存在左右子树，且所有叶子结点都在同一层上。3.3.6树与二叉树第四十九页，共七十三页，2022年，8月28日二级ACCESS—基本数据结构与算法423167891011

12

5

非完全二叉树

完全二叉树

423167891011

12

5

完全二叉树

特点：除最后一层外，每一层都取最大结点数，最后一层结点都集中在该层最左边的若干位置。3.3.6树与二叉树第五十页，共七十三页，2022年，8月28日二级ACCESS—基本数据结构与算法A、二叉树的第i层上至多有2i-1（i1）个结点。B、深度为h的二叉树中至多含有2h-1个结点。C、若在任意一棵二叉树中，有n0个叶子结点（度为0），有n2个度为2的结点，则：n0=n2+1D、具有n个结点的完全二叉树的深度为[log2n]+1，其中[log2n]表示log2n的整数部分。二叉树的基本性质42

3

16

78910

11

12

13

14

15

53.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日二级ACCESS—基本数据结构与算法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；否则该结点无右子结点。二叉树的基本性质42

3

16

78910

11

12

13

14

15

53.3.6树与二叉树例如结点6，其父结点为3，左子结点为12，左子结点为13第五十二页，共七十三页，2022年，8月28日二级ACCESS—基本数据结构与算法3.3.6树与二叉树二叉树的存储结构顺序存储结构链式存储结构顺序存储结构用一组连续的存储单元存放二叉树的数据元素。结点在数组中的相对位置蕴含着结点之间的关系。用数组存储时，若父结点在数组中i下标处，其左孩子在2*i处，右孩子在2*i+1处。顺序存储二叉树必须按完全二叉树的形式存储，将造成存储的浪费。第五十三页，共七十三页，2022年，8月28日二级ACCESS—基本数据结构与算法二叉树的顺序存储结构T[16]11ABcFED

●●●●●●●●●124

8

9105637121314152h-1=24-1=150000FE00

0DC0BA

151413121110987654321003.3.6树与二叉树第五十四页，共七十三页，2022年，8月28日二级ACCESS—基本数据结构与算法3.3.6树与二叉树二叉树链式存储结构

在顺序存储结构中，对于非完全二叉树，需要将空缺的位置用特定的符号填补，若空缺结点较多，势必造成空间利用率的下降。在这种情况下，就应该考虑使用链式存储结构。常见的二叉树结点结构如下所示：LchilditemRchildparentAB第五十五页，共七十三页，2022年，8月28日二级ACCESS—基本数据结构与算法3.3.6树与二叉树GH

DEF

BC

A^G^^H^

^D^E^F^

B^C

A

BT

二叉树的链接存储结构第五十六页，共七十三页，2022年，8月28日二级ACCESS—基本数据结构与算法二叉树的遍历

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

先序遍历(DLR):

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

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

后序遍历(LRD):按后序遍历左子树，按后序遍历右子树，访问根结点。二叉树为空时，执行空操作，即空二叉树已遍历完。3.3.6树与二叉树第五十七页，共七十三页，2022年，8月28日二级ACCESS—基本数据结构与算法遍历算法先序遍历：DLR中序遍历：LDR后序遍历：LRDADBCT1

T2

T3

DLRADLRDLR>B>>D>>CDLR以先序遍历DLR为例演示遍历过程ABDCBDACDBCA3.3.6树与二叉树第五十八页，共七十三页，2022年，8月28日二级ACCESS—基本数据结构与算法查找：在一个给定的数据结构中，根据给定的条件找到满足条件的结点。不同的数据结构采用不同的查找方法。查找的效率直接影响数据处理的效率。平均查找长度：查找过程中比较的次数查找的结果查找成功：找到满足条件的结点查找失败：找不到满足条件的结点。3.3.7查找和排序第五十九页，共七十三页，2022年，8月28日二级ACCESS—基本数据结构与算法顺序查找（线性查找）

对给定的一关键字K，从线性表的一端开始，逐个进行记录的关键字和K的比较，直到找到关键字等于K的记录或到达表的另一端。可以采用从前向后查，也可采用从后向前查的方法。在平均情况下，大约要与表中一半以上元素进行比较，效率较低。平均查找长度=(n+1)/2。时间复杂度＝O(n)在下面两种情况下只能采取顺序查找：线性表为无序表（元素排列是无序的）；即使是有序线性表，但采用的是链式存储结构。3.3.7查找和排序第六十页，共七十三页，2022年，8月28日二级ACCESS—基本数据结构与算法折半查找（二分法查找）思想：先确定待查找记录所在的范围，然后逐步缩小范围，直到找到或确认找不到该记录为止。前提：必须在具有顺序存储结构的有序表中进行。分三种情况：若中间项的值等于x,则说明已查到。若x小于中间项的值，则在线性表的前半部分查找；若x大于中间项的值，则在线性表的后半部分查找。特点：比顺序查找方法效率高。最坏的情况下，需要比较log2n次。3.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日二级ACCESS—基本数据结构与算法排序的功能：将一个数据元素（或记录）的任意序列，重新排成一个按关键字有序的序列。

排序过程的组成步骤1、首先比较两个关键字的大小；2、然后将记录从一个位置移动到另一个位置。

3.3.7查找和排序堆排序起泡排序排序方法插入排序选择排序交换排序归并排序直接、折半插入排序希尔排序简单选择排序快速排序第六十四页，共七十三页，2022年，8月28日二级ACCESS—基本数据结构与算法该算法适合于n较小的情况，时间复杂度为O(n2).待排元素序列：[53]2736156942第一次排序：

[2753]36156942第二次排序：

[273653]156942第三次排序：

[15273653]6942第四次排序：

[1527365369]42第五次排序：

[152736425369]

直接插入排序示例对于有n个数据元素的待排序列，插入操作要进行n-1次3.3.7直接插入排序从数组的第2号元素开始，顺序取出后续元素，并将该元素插入到其左端已排好序数组的适当位置。需比较n(n-1)/2次第六十五页，共七十三页，2022年，8月28日二级ACCESS—基本数据结构与算法例：有6个记录，前5个已排序的基础上，对第6个记录排序。[1527365369]42lowmidhigh[1527365369]42

lowhigh

mid

[1527365369]42

highlow

[152736425369](high<low，查找结束，插入位置为low或high+1)

(42>36)

(42<53)

3.3.7折半插入排序折半插入排序在寻找插入位置时，不是逐个比较而是利用折半查找的原理寻找插入位置。待排序元素越多，改进效果越明显。第六十六页，共七十三页，2022年，8月28日思想：首先从1～n个元素中选出关键字最小的记录交换到第一个位置上。然后再从第2个到第n个元素中选出次小的记录交换到第二个位置上，依次类推。时间复杂度为O(n2)，最坏情况下需要比较n(n-1)/2次适用于待排序元素较少的情况。3.3.7简单选择排序初态83916839168391683916ijkijkijkijk1

3986互换ijk1

3986ik