02142数据结构导论

2025-01-09 17:32:11   1  举报





AI智能生成

它精心梳理了教材中的关键知识点，涵盖线性表、栈与队列、树与二叉树、图等重要数据结构内容，清晰呈现各知识点间的关联与逻辑。对每种数据结构的定义、特点、操作都做了详细总结，便于理解记忆。同时，还归纳了常见算法思路与复杂度分析要点，助力考生把握核心考点。自考学子利用该文件，能快速搭建知识体系，高效复习，加深对复杂知识的理解，有效节省时间，提升备考效率，是我们自考生攻克 “数据结构导论 02142” 这门课程的优质学习资源。

自考

高效复习

数据结构导论

作者其他创作

大纲/内容

记笔记小Tips

第一章概论

一、绪论

1.2 基本概念和术语

1 数据、数据元素和数据项

数据

数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机被计算机存储和处理的对象。

数据元素

a. 数据元素是数据的基本单位。在计算机程序中常作为一个整体进行考虑和处理。 b. 数据元素是运算的基本单位，简称为元素。

数据项

a. 一个数据元素可以由若干数据项组成。 b. 数据项是数据的不可分割的最小标识单位。 c. 在数据库中数据项又称为字段或域。

数据结构

a. 数据结构是相互之间存在一种或多种特定关系的数据元素的集合； b. 包括数据的逻辑结构、数据的存储结构和数据的基本运算。

2 数据逻辑结构

数据的逻辑结构是指数据元素之间的逻辑关系。

数据的逻辑结构是一种数据模型。

根据数据元素之间的关系，通常有四类基本结构

1）集合结构

2）线性结构

3）树形结构

4）图结构

3 数据存储结构

数据的逻辑结构在计算中的实现称为数据的存储结构，或物理结构

一个存储结构包括两个部分

（1）存储数据元素

（2）数据元素之间的关联方式

数据元素之间的关联方式主要有

常用分为：顺序存储、链式存储

还有索引存储和散列存储方式

4 运算

运算是指在某种逻辑结构上施加的操作，即在每组逻辑结构上定义的基本运算。 这些运算包括：建立、查找、读取、插入和删除等。

1.3 算法及描述

算法是对特定问题求解步骤的一种描述，是一有限长的操作序列。

算法特性（次要：书本没有，拓展！）

1. 有穷性：算法在执行有穷步后能结束。 2. 确定性：每步定义都是确切的、无歧义的。 3. 可行性：算法描述的操作都是可以通过已实现的基本运算经过有限次来实现的。 4. 输入：有0个或多个输入。

1.4 算法分析

评价算法好坏的因素包括以下几个方面

1. 正确性：满足具体问题的需要。 2. 易读性：便于理解和修改。 3. 健壮性：输入非法数据，算法也能适当地做出反应或进行处理。 4. 时空性：一个算法的时空性是指改算法的时间性能和空间性能。（前者是算法包含的计算量，后者是算法需要的存储量）

1 时间复杂度

衡量算法的效率，主要依据算法执行所需要的时间，即时间复杂度（不是时间单位分/秒。）

时间复杂度常见的阶数有： a. 常数阶O(1) b. 对数阶O(log2n) c. 线性阶O(n) d. 多项式阶O(n²)、O(n³) e. 指数阶O(2^n)

时间复杂度具有指数阶的算法是实际不可计算的，而阶数低于平方阶的算法是高效率的。

O(1) < O(log2n) < O(n) < O(log n) < O(n²)  < O(n³) < O(2^n)  ==== 需要记住！！！

时间复杂度的例题分析！

2 空间复杂度

一个算法的空间复杂度定义为该算法所耗费的存储空间（存储空间主要指内存，不考虑硬盘空间）。

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。

一个算法在执行期间所需要的存储空间量应包括以下三个部分： （1）程序代码所占用的空间； （2）输入数据所占用的空间； （3）辅助变量所占用的空间。 在估算算法空间复杂度时，一般只需要分析辅助变量所占用的空间。

第二章  线性表

2.1 线性表的基本概念

线性表

线性表是有n个数据元素组成的有限序列，相邻数据元素之间存在着序偶关系。 a.数据元素又称为结点; b.结点个数n称为表长；

线性表的基本特征

a.线性表中结点具有一对一的关系，除起始节点没有直接前驱外，其他每个节点有且仅有一个直接前驱；除终端节点没有直接后继外，其他每个节点有且仅有一个直接后继。 b.同一个线性表中的所有结点代表的数据元素具有相同的特性。是指只能是同一类数值，比如整数或浮点数，也可以是同一类数据组合。

线性表基本运算

待补充(不重要)

线性表的存储结构

1.顺序存储

2.链接存储

2.2 线性表的顺序存储

1.线性表顺序存储的类型定义

顺序表

用顺序存储实现的线性表称为顺序表；一般使用数组来表示顺序表。

顺序表是线性表的顺序表示，用一组地址连续的存储单元依次存储线性表的数据元素。

顺序表的创建（代码）

P37

2.线性表的基本运算在顺序表上的实现

（1）插入

a.顺序表的"第i个数据元素"存放在数组下标为"i-1"的位置；

b.插入操作包括：1）先后移；2）元素插入；3）表长加1；

插入运算代码 —— P38

（2）删除

a.删除第i个元素，在数组位置(下标)是：i-1;

b.删除操作步骤是：1）前移(左移)；2）长度减1；

删除运算代码 —— P40

（3）定位

定位包括1）查找第i个位置的元素值；2）查找元素所在位置(下标)；

删除运算代码 —— P40(一般不考)

3.顺序表实现算法的分析

1）插入操作要向后移动元素个数为：n-i+1，时间复杂度为：O(n)；

2）删除操作要往前移动元素个数为：n-i 个，时间复杂度为：O(n)；

3）定位操作 a.平均比较次数为：(n-1)/2，时间复杂度为：O(n)； b.求表长和读表元素算法的时间复杂度为O(1)。

2.3 线性表的链接存储

线性表常见的链式存储结构有单链表、循环链表和双向循环链表。

1.单链表的类型定义

单链表

链表是线性表的链式存储表示，每个结点只包含一个指针域的链表称为单链表。

a. 指针表示数据元素之间的逻辑关系， b. 一个数据元素和一个指针组成单链表的一个结点， c. 各个结点在内存中的存储位置不一定连续。

1）data：数据域； 2）next：指针域或链域，用于存放一个指针，该指针指向本结点所含数据元素的直接后继结点。 3）head：头指针变量，指向单链表第一个结点的指针，可以用头指针变量来命名单链表； 4）首结点：链表中的第一个数据元素结点； 5）尾结点或终端节点：P->next == NULL； 6）尾结点指针域的值NULL称为空指针，它不指向任何结点，表示链表结束。 7）如果head等于NULL，则表示该链表吴任何结点，是空单链表。

填空P43： 1）为了便于运算的实现，在单链表的第一个结点之前增设一个类型相同的结点，称之为（头结点），其他结点称为（表结点）； 2）表结点中的第一个和最后一个结点分别就是（首结点）和（尾结点）； 3）头结点的数据域可以不存储任何信息，也可以存放一个特殊标志或表长。

设有一个单链表，若结点的指针域为next，则指针P所指的节点为最后一个结点的条件是： P->next == NULL。（== 双等号表判断；= 单等号表赋值）

2.线性表的基本运算在单链表上的实现

（1）初始化单链表的创建

判断链表为空：head->next == NULL;

单链表的创建代码 —— P44

（2）求表长

a. 在单链表存储结构中，线性表的表长等于单链表中数据元素的结点个数，即除了头结点以外的结点的个数;

求单链表表长代码 —— P45

（3）读表元素

没什么知识点

读表元素算法代码 —— P45(一般不考)

（4）定位查找第i个元素

定位：给定表元素的值，找出这个元素的位置(下标)；又称作按值查找；

定位算法代码代码 —— P46(一般不考)

（5）插入

a. 基本操作为：找到链表中第i-1个结点q，创建新结点P，然后修改第i-1个结点和P结点的后继指针,即完成单链表的插入运算。

b. 链表的插入不是移动，而是修改指针。

C. P46 图2-12  插入结点的指针变化步骤图

插入运算算法代码 —— P46

（6）删除

将单链表的第i个元素删除

删除算法代码代码 —— P47

2.4 其他运算在单链表上的实现

1. 建表

建立线性表的单链表

1）首先建立带头结点的空表； 2）其次建立一个新结点； 3）然后将新结点链接到头结点之后，这个结点为尾结点（也是首结点）

单链表的建表方法（代码）

方法一：尾插法；时间复杂度为O(n²)。P48

方法二：加入尾指针；时间复杂度为O(n)。P48

方法三：始终在头结点和首元素之间插入（头插法，在哈希查找中非常常见）； 时间复杂度也为O(n)。P49

2. 删除重复结点

1）搜索当前结点到末尾结点之间，查找与当前结点相同的结点，执行删除；

2）双while循环；

3）时间复杂度为O(n)。

删除重复结点运算中的删除操作- 图2-16。P51

2.5 其他链表

1. 循环链表

1）在单链表中，如果让最后一个结点的指针域指向第一个结点可以构成循环链表。 在循环链表中，从任一结点出发能够扫描整个链表。

2）链表没有设头指针，只设尾指针rear，首结点表示为：rear—>next—>next。

3）在循环链表上实现线性表的运算与在单链表上实现线性表的运算十分类似，这节不再讨论。

2. 双向循环链表

1）在单链表的每个结点中再设置一个指向其直接前驱结点的指针域prior，这样每个结点有两个指针。

2）头结点的prior指向最后一个结点，最后一个结点的next指向头结点，由这种结点构成的链表称为双向循环链表。图2-19-P52

3）双向循环链表的对称性可以用下列等式表示：对于任何一个中间结点有       P= P—>next—>prior;     解释：P的下一个结点P—>next的前驱结点prior还是P结点本身！       P= P—>prior—>next；  解释：P的前一个结点P—>prior的下一个结点next还是P结点本身！

4）删除

tips：= 号左边的next或prior表示指针，其他情况都表示结点。 在双循环链表中，设P指向待删结点，删除*P可通过下述语句完成：图2-20-P53 （1）p->prior->next = p->next; （2）p->next->prior = p->prior; （3）free(p);————修改了2个指针

5）插入

在P所指结点的后面插入一个新结点*t，需要修改四个指针：图2-21-P53 （1）t->prior = p; （2）t->next  = p->next; （3）p->next ->prior = t; （4）p->next = t;

2.6 顺序实现与链接实现的比较

1）按位置查找运算：顺序表是随机存取，时间复杂度为O(1)；单链表需要对表元素进行扫描，它的时间复杂度为O(n)。

2）定位运算，基本操作是比较，顺序表和单链表上的实现算法的时间复杂度是相同的，均为O(n).

3）插入和删除运算：       在顺序表中，基本操作是元素的比较和结点的移动，平均时间复杂度为O(n)。       在单链表中，基本操作是元素的比较，尽管不需要移动结点，其平均时间复杂度仍然为O(n)。

4）单链表的每个结点包括数据域与指针域，指针域需要占用额外空间。 顺序表要预分配存储空间，单链表不需要预先分配空间，只要内存空间没有耗尽， 单链表的结点个数就没有限制。

顺序表的存储空间是静态分配的

链表的存储空间是动态分配的。

存储密度=结点数据本身所占的存储量/结点结构所占的存储总量。 举例： 顺序表的存储密度：         int a[100]：结构是100，目前存储了5个，那存储密度=5/100=0.05。 链表的存储密度：         5/（5+1）≈ 1%（待确认）。

第三章栈、队列和数组

3.1 栈

栈的基本概念

1）栈是运算受限的线性表，插入和删除运算限定在表的某一端进行； 2）允许进行插入和删除的一端称为栈顶，另一端称为栈底； 3）栈的修改原则是后进先出。 4）栈的插入和删除运算分别称为进栈和出站。

栈的顺序实现

栈的顺序存储结构是用一组连续的存储单元依次存放栈中的每个元素； 栈的顺序实现称为顺序栈。通常用一个一维数组和一个记录栈顶位置的变量来实现栈的顺序存储。

单顺序栈的特性

1）top=0或top=base：表栈空； 2）base=NULL：表栈不存在； 3）当插入新的栈顶元素时，指针top+1； 4）删除栈顶元素时，指针top-1； 5）当top>stacksize时，栈满溢出。

双栈 P62

双栈判断上溢：top1+1=top2；

双栈判栈空： top1=0，top1栈空； top2=max-1，top2栈空；

栈的链接实现

1）栈的链式存储结构称为链栈，插入和删除操作仅限在表头位置上进行； 2）LS指向链表的头结点，首结点是栈顶结点，LS->next指向栈顶结点，尾结点为栈底结点； 3）头结点不存储数据，仅表示位置，首结点才存储数据； 4）每个结点空间都是动态分配产生，链栈不用预先考虑容量的大小。

栈的基本运算在链栈上的实现算法

1）初始化：栈初始化时，生成一个结点，将该结点的next域设置为NULL；

2）判栈空：LS—>next==NULL;

3）进栈：P64 在进栈操作算法中采用前插操作，新增结点始终插入到头结点之后；

4）出栈：s.pop( ); 

- 注意，出栈操作只是删除栈顶元素，并不返回该元素。 - 出栈操作始终是栈顶结点出栈，即删除头结点之后的结点。

【例3-3】设一个链栈的输入序列为A、B、C，试写出所得到的所有可能的输出序列。P65

5）取栈顶元素：return LS->next -> data;

栈的链接实现

栈的基本运算在链栈上的实现算法

1）初始化：栈初始化时，生成一个结点，将该结点的next域设置为NULL；

2）判栈空：LS—>next==NULL;

3）进栈：P64 在进栈操作算法中采用前插操作，新增结点始终插入到头结点之后；

4）出栈：s.pop( ); 

- 注意，出栈操作只是删除栈顶元素，并不返回该元素。 - 出栈操作始终是栈顶结点出栈，即删除头结点之后的结点。

【例3-3】设一个链栈的输入序列为A、B、C，试写出所得到的所有可能的输出序列。P65

5）取栈顶元素：return LS->next -> data;

栈的简单应用和递归

（1）栈的简单应用举例【例3-4】栈的倒序功能-P66

（2）递归与栈

考点：不考递归代码，而是如果需要用递归，应该用什么数据结构？

P68-70 阶乘函数递归

1）当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三项任务： a. 将所有实参，返回地址等信息传递给被调用函数保存； b. 为被调用函数的局部变量分配存储区； c. 将控制转移到被调用函数的入口。

2）从被调用函数返回调用函数之前，应该完成下列三项任务： a. 保存被调用函数的计算结果； b. 释放被调用函数的数据区； c. 依照被调用函数保存的返回地址将控制转移到调用函数。

3）多个函数嵌套调用的规则是：后调用先返回！此时的内存管理实行“栈式管理”！

4）递归函数执行的过程可视为同一函数嵌套嗲用。-----就是函数自己本身调用自己！

总结： A. 在函数递归调用过程中，用栈保存中间结果； B. 读取数据在CPU中比在内存中要快，在内存中读取比硬盘要快！

3.2 队列

队列的基本概念

是一种先进先出的线性表，新加入的数据元素插在队列尾端，出队列的数据元素在队列首部被删除。

1）队列是只允许在表的一段进行插入，而在另一端删除元素的线性表； 2）在队列中，允许插入的一段叫队尾rear，允许删除的一段称为队头front。（类似于做核酸队伍，队尾插入排队，队首做完走人删除）

队列的基本运算

（1）队列初始化； （2）判队列空：若队列为空，返回1，否则返回0； （3）入队列：将数据元素x从队尾一端插入队列，使其成为队列的新尾元素； （4）出队列：删除队列首元素； （5）取队列首元素：返回队列首元素的值。

队列的顺序实现

1）它是由一个一维数组及两个分别指示队列首和队列尾的变量组成， 这两个变量分别称为“队列首指针”和“队列尾指针”。 2）顺序队列结构类型中有三个域：data、front和rear。期中data为一维数组， front和rear定义为整型变量，实际取值范围是0~maxsize-1. 3）为方便操作，规定front指向队列首元素的前一个单元，rear指向实际的队列尾元素单元。

第三点：3）为方便操作，规定front指向队列首元素的前一个单元，rear指向实际的队列尾元素单元。 ----在其他教材上，队头指针始终指向队列首元素的实际位置，队尾指针指向队列尾元素的下一个空白位置。 因此此教材上的front和rear仅适用于这本教材，只用于考试。

入队列赋值语句：        SQ.rear=SQ.rear+1;        SQ.data[SQ.rear]=x.

出队列：SQ.front = SQ.front + 1.

用循环队列来解决顺序队列的溢出问题。 1）循环队列采用一组地址连续的存储单元，将整个队列存储单元首尾相连； 2）front指向队列第一个元素之前的空白位置；rear指向队列最后一个元素的位置； 3）入队和出队操作都加入取模运算：%maxsize。

循环队列入队列操作语句：        SQ.rear=(SQ.rear+1) % maxsize;        SQ.data[SQ.rear]=x.

循环队列出队列操作语句：        SQ.front = (SQ.front + 1) % maxsize.

循环队列空条件：front == rear;

队列为满时，亦有front==rear，因为无法区分队空还是队满这两种情况。

为了解决上述问题，有两种解决方法： 1）一是为队列另设一个标志，用来区分队列是空还是满； 2）二是队列少用一个元素空间，当只剩下一个单元时就认为队列满，队尾 指针只差一步将追上队列首指针。本书采用第二种解决方法。

循环队列满条件：        (rear+1) % maxsize == front;

求队列元素个数len: （front+length）%maxsize = rear  （rear - length）%maxsize= front

循环队列求front或rear值：        rear = (front+length)%maxsize;        front = (rear-length)%maxsize;

队列的链接实现

1）使用一个带有头结点的单链表来表示队列，称为链队列。链队列采用链表存储单元； 2）有两个分别指示队头和队尾的指针。头指针指向链表的头结点，单链表的头结点的next域指向队列首结点，尾指针指向队列尾结点，即单链表的最后一个结点。所以出队位置是front->next,入队位置是rear->next. 3）链队列在进队时无队满问题，但有队空问题； 4）链接实现需要动态申请空间，故不会出现队列满的情况；

入队列：(入队列时，新结点总是增加到队尾)rear—>next;

出队列：front—>next;free( );

链栈判队空：front==rear或front—>next==NULL;

队列应用

P78 【例3-7】银行办理业务，按照“先到先服务”的原则，用计算机来模拟等待和接收服务这一过程。

3.3 数组

3.3.1 数组的逻辑结构和基本运算

1）一维数组又称向量，由一组具有相同类型的数据元素组成，并存储在一组连续的存储单元中； 2）二维数组可以看成是m个行向量或者n个列向量（一维数组）组成的线性表； 3）在数组中，对于一组有意义的下标，都存在一个与其对应的值； 4）一维数组对应一个下标值，二维数组对应两个下标值，依次类推。

数组通常只有两种基本运算

（1）读：给定根据下标，返回该位置的元素内容；

（2）写：给定根据下标，修改该位置的元素内容；

3.3.2 数组的存储结构

思考：二维数组怎样存入计算机内存？ -  还是以一维数组的方式存入；(逻辑上的二维数组下边转换为物理上的一维数组存储) -  存入时一种是以列序为主序，另一种是以行序为主序的存储。 ---在C语音的编译程序中，数组采用的是以行序为主序的存储方法；P81 图3-26 数组的存储方式

对于二维数组a[m][n]，如果每个元素占k个存储单元，以行为主序为例，讨论数组元素a[i][j]位置与下标的关系；

二维数组元素求存储在一维数组的物理位置： 1）以行为主： loc[ i , j ] = loc[0,0]+( n * i + j ) * k; 2）以列为主： loc[ i , j ] = loc[0,0]+( m * j + i ) * k.

3.3.3 矩阵的压缩存储

高阶矩阵中有许多值相同的元素或零元素，为了节省存储空间，对这类矩阵采用多个值相同的元素只分配 一个存储空间，零元素不存储的策略，这一方法称为矩阵的压缩存储。

特殊矩阵

概念：如果值相同的元素或者零元素在矩阵中的分布有一定规律，称此类矩阵为特殊矩阵。

对称矩阵

a(ij) = a(ji) ,满足这个条件的则称为对称矩阵。

对称矩阵行列一定相等； 为每一对对称元素只分配一个存储单元，可将n²个元素压缩存储到含有n(n+1)/2个元素的一维数组中。 （n是行）

设矩阵元素aij在数组M中的位置为k，( i,  j)和k存在的关系： 1）当i ≥ j，[(i+1)*i]/2 + j; 2）当i < j，[(j+1)*j]/2 +i;

三角矩阵P83

上三角矩阵中，M[K]和aij的对应关系是： 1）当i ≤ j，[i(2n-i+1)]/2 + j - i; 2）当i ＞j，[n(n+1)]/2;

下三角矩阵中，M[K]和aij的对应关系是： 1）当i ≥ j，[i(i+1)]/2 + j; 2）当i < j，[n(n+1)]/2;

稀疏矩阵

矩阵的非零元素个数很少的矩阵称为稀疏矩阵。----P84 【图3-30】

概念：假设m行n列的矩阵有t个非零元素，当t << m*n时，则称为稀疏矩阵。

稀疏矩阵三元表示法：====掌握三元组表示法 用三个项来表示稀疏矩阵中的非零元素aij：( i, j, aij ), 其中i表示行序号，j表示列序号，aij是非零元素的值，称为三元组。

3.4 应用举例

用模拟停车场管理来说明栈和队列两种数据结构的应用

3.5 小结

栈是只能在一段（栈顶）进行插入和删除运算的线性表，具有后进先出特征。 以顺序存储结构实现的栈称为顺序栈，以链式存储结构实现的栈称为链栈。 顺序栈需要预先定义栈的大小，在难以估计栈的大小时，可以采用链栈，链栈是用单链表实现。 栈适合具有后进先出特性的问题，如实现程序递归、函数调用等。

队列适合于具有先进先出特征的问题，如操作系统重进程调度队列、打印队列等。

数组采用顺序存储结构来存储数据元素，本章给出了根据元素的下标求地址的方法（分别考虑 以行序为主序和列序为主序的存放方式），介绍了特殊矩阵和稀疏矩阵的压缩存储方法。

第四章树和二叉树

4.1 树的基本概念

4.1.1 概念

线性结构中的一个结点至多只有一个直接后继； 而树形结构中一个结点可以有一个或多个直接后继。

树是n个结点的有限集合； （1）当n=0时，称为空树； （2）当n＞0时，有且仅有一个称为根的结点

森林是m棵互不相交的树的集合； 树的每个结点的子树是森林；

4.1.2 树的相关术语

结点的度：树上任一结点所拥有的子树的数目称为该结点的度

叶子：度为0的结点称为叶子或终端节点

树的度：一棵树中所有结点的度的最大值称为该树的度

孩子：直接后继，可能有多个；

双亲：孩子的直接前驱，最多只能有1个；

兄弟：同一双亲的孩子；

子孙：以某结点为根的树中的所有结点； 一棵树上除根结点以外的任何其他结点称为根的子孙。

结点的层次：从根开始算起，根的层次为1，其余结点的层次为其双亲的层次加1。

树的高度：一棵树中所有结点层次数的最大值称为该树的高度或深度。

有序树：树种各结点的子树从左到右是有次序的，不能互换，称为有序树；

无序树：树中各结点的子树是无次序的，可以互换，则称为无序树。

树的基本运算

P95---不重要

4.2 二叉树

4.2.1 基本概念

二叉树是n个元素的有限集合；由一个根及两棵互不相交的左子树和右子树组成； （1）二叉树的任一结点都有两棵子树（它们中的任何一个都可以是空子树），并且这两颗子树之间有次序关系。 （2）二叉树上任一结点左右子树的根分别称为该结点的左孩子和右孩子。

二叉树有五种基本形态：---P96图4-4 1）空二叉树； 2）只有根结点的二叉树； 3）右子树为空的二叉树； 4）左子树为空的二叉树； 5）左右子树都非空的二叉树。

4.2.2 二叉树的性质

性质1：二叉树的第 i 层上至多有 2^(i - 1) 个结点（i≥1）；—指的是(i)层的结点个数

性质2：深度为K的二叉树至多有(2^k)-1个结点；— 指的是总结点数

性质3：对任何一棵二叉树，若度数为0的结点（叶结点）个数为n0,度数为2的结点个数为n2，则n0=n2+1。

性质4：含有n个结点的完全二叉树的深度为⌊log₂n⌋+1;— 不常考

性质5：如果将一棵有n个结点的完全二叉树按层编号。 则对任一编号为i的结点A有：(1≤i≤n) ---只对完全二叉树有效，对普通二叉树不成立！！！

若i=1，则结点A是根； 若i＞1，则A的双亲Parent(A)的编号为：[i/2] —> 不做四舍五入3/2=1.5,取1

A的左孩子Lchild(x)的编号为 2*i ；若2*i > n，则结点A既无左孩子，也无右孩子；（n是总结点）

A的右孩子Rchild(A)的编号为 2*i + 1 ；若 2*i + 1> n，则结点A无右孩子；（n是总结点）

满二叉树

深度为K且有(2^k)-1个结点的二叉树称为满二叉树。

完全二叉树

对比满二叉树，按层次遍历相反顺序，减少部分结点的二叉树(注意一定是按顺序减少的结点)，称为完全二叉树。

4.3 二叉树的存储结构

4.3.1 顺序存储结构

a. 二叉树的顺序存储结构可以用一维数组来实现，二叉树上的结点按某种次序分别存入该数组的各个单元中。

b. 对于任何完全二叉树来说，可以采用以编号作为数组的下标的方法将结点存入一维数组中。

4.3.2 链式存储结构 ---是二叉树最常用的存储结构

a. 最常用的是二叉链表与三叉链表

二叉链表：左孩子指针域+data数据域+右孩子指针域； 每个二叉链表还必须有一个指向根结点的指针，称为根指针。

三叉链表：左孩子指针域+data数据域+双亲指针域+右孩子指针域；

二叉链表的类型定义代码---P101

b. 若二叉树为空，则root=NULL

c. 具有n个结点的二叉树中，有2n个指针域（左右孩子指针2）

d. 其中只有 n-1个用来指向结点的左、右孩子

e. 其余的 n+1个指针域为NULL

4.4 二叉树的遍历

4.4.1 二叉树遍历的递归实现

a. 概念：二叉树的遍历是指按照某种次序访问二叉树上的所有结点， 使每个结点被访问一次且仅被访问一次。(是指可以经过多次，但是只访问一次，做一次操作)

b. 先序遍历DLR

先序遍历的递归算法代码P103

c. 中序遍历LDR

中序遍历的递归算法代码P103

e. 后续遍历LRD

后序遍历的递归算法代码P103

f. P106 例4-2：利用二叉树遍历的递归算法，求二叉树的高度（考过两次）。

拓展三分钟学会先序、中序、后序遍历，链接（https://www.bilibili.com/video/BV1Ub4y147Zv/?spm_id_from=333.337.search-card.all.click）

4.4.2 二叉树的层次遍历

a. 概念：二叉树的层次遍历，是指从二叉树的根结点的这一层开始， 逐层向下遍历，在每一层上按从左到右的顺序对结点逐个访问。

b. 层次遍历可以用一个队列来实现

层次遍历的算法代码P107

4.4.3 二叉树遍历的非递归实现

递归转非递归，用栈实现！----不考

4.4.4 二叉树的应用举例

如何利用二叉树结点的先序序列和中序序列，确定这棵二叉树： （由先序序列和中序序列构造二叉树）

求解规则： （1）先序遍历的最左边结点必定是根结点； （2）中序遍历的根结点的左边序列是它的左子树，右边序列是它的右子树。

先序序列和中序序列构造二叉树的算法代码P110

如何利用二叉树结点的中序序列和后序序列，确定一棵二叉树： （由中序序列和后序序列构造二叉树）

求解规则： （1）后序遍历的最右边结点必定是根结点； （2）中序遍历的根结点的左边序列是它的左子树，右边序列是它的右子树。

4.5 树和森林

4.5.1 树的存储结构

树是一种常用的数据结构；

（1）孩子链表表示法

孩子链表表示法是树的一种链式存储结构。 它的主体是一个数组元素个数和树中结点个数相同的一维数组；

单链表的头结点含有两个域：数据域和指针域; 除头结点外，其余所有表节点也含有两个域：孩子域(child)和指针域(next)

数据域存储结点数据元素

指针域存储指向该结点第一个孩子结点的指针

P112 图4-15b是图4-15a中树的孩子链表存储结构示意图。

带双亲的孩子链表表示法

为了便于找到双亲，在各个头结点中增加一个双亲域在头结点数组中的下标值。 这种存储结构称为带双亲的孩子链表表示法。

P113 图4-16 树的带双亲的孩子链表表示

（2）孩子兄弟链表表示法

概念：存储时每个结点除了数据域外，还有指向该结点第一个孩子和下一个兄弟结点的指针。

a. 采用二叉链表； b. 左边指针指向第一个孩子，右边指针指向兄弟。

P114 图4-18 树的孩子兄弟链表表示示意图！

实现了树和二叉树的转换！

（3）双亲表示法

概念：双亲表示法，由一个一维数组构成；

数组的每个分量包含两个域：数据域和双亲域

数据域：存储树上结点中数据元素

双亲域存储本结点的双亲结点在数组中的序号（下标值）

4.5.2 树/森林与二叉树的关系

（1）树转换成二叉树

a. 树与二叉树都可以采用二叉链表作为存储结构；

b. 任意给定一棵树，可以找到一个唯一的二叉树；

c. 将树转换成二叉树的方法：     左边指针指向第一个孩子，右边指针指向兄弟。

P115 图4-20 树与二叉树的对应关系示例图！

（2）森林转换成二叉树

森林转换成二叉树的方法： 每棵树转成一棵二叉树，再把各二叉树的根结点按右孩子关系链接起来。

P116 图4-21 森林到二叉树的转换过程示例图！

（3）二叉树转换成森林

二叉树转换成森林的方法： 1) 根结点右孩子是一棵新树； 2) 其他节点的右孩子是兄弟。

P117 图4-22 从二叉树到森林的转换过程示例图！

4.5.3 树和森林的遍历

（1）树的遍历 树的遍历只有先序和后序，没有中序！

先序遍历：树的先序遍历 == 二叉树的先序遍历

后序遍历：树的后序遍历 == 二叉树的中序遍历（先子树再根）

层次遍历：当第i层结点已访问，第i+1层未访问，访问第i+1层。

（2）森林的遍历 森林的遍历只有先序和中序，没有后序！

先序遍历森林：从左到右每棵树的先序；

中序遍历森林：从左到右每棵树的中序== 二叉树的中序遍历；---(把森林转换成二叉树做中序遍历)

判定树和哈夫曼树

分类与判定树

分类是一种常用运算，将输入数据按预定的标准划分成不同的种类。

用于描述分类过程的二叉树称为判定树；

哈夫曼树与哈夫曼算法

哈夫曼树又称为最优树，是一类带权路径长度最短的树。

构造哈夫曼树的原则：

权值越大的叶结点越靠近根结点

权值越小的叶结点越远离根结点

带权路径长度：从结点到树根之间的路径长度与结点上权的乘积；

树的带权路径长度(WPL)：树中所有叶子结点的带权路径长度之和。

哈夫曼树中共有2n-1个结点， 其中n个叶结点是初始森林中的n个结点， 并且哈夫曼树中没有度数为1的分支结点。

哈夫曼编码

规定哈夫曼树中的左分支为0，右分支为1， 则从根结点到每个叶结点所经过的分支对应的0和1组成的序列便为该结点对应字符的编码。 这样的编码称为哈夫曼编码。

4.6 判定树和哈夫曼树

4.6.1 分类与判定树

树有广泛的应用，其中一种重要应用是描述分类过程。 用于描述分类过程的二叉树称为判定树。（选择or填空题）

按照不同判定树进行分类的计算量是不同的，是否存在计算量最小的判定树呢？ 如果存在，怎样构造出这种判定树？由此引申出哈夫曼树和哈夫曼算法，可以给出这个答案

4.6.2  哈夫曼树与哈夫曼算法

概念：具有最小带权路径长度的二叉树称为哈夫曼树，也称最优树。

构造哈夫曼树的原则：

权值越大的叶结点越靠近根结点

权值越小的叶结点越远离根结点

哈夫曼树遵循左小右大

带权路径长度：从结点到树根之间的路径长度与结点上权的乘积；

树的带权路径长度(WPL)：树中所有叶子结点的带权路径长度之和。

哈夫曼树中共有 2n-1 个结点， 其中n个叶结点是初始森林中的n个结点， 并且哈夫曼树中没有度数为1的分支结点。

4.6.3 哈夫曼编码

作用：通过哈夫曼树把电文缩短，减少传送时间！

考：给一段电文电报，如何做压缩？

哈夫曼算法的关键点是：每次合并具有最小权值和次小权值的两个根结点，直到只剩一个根结点为止。 对哈夫曼树的每个结点的左分支和右分支分别置“0”或“1”，就可得到哈夫曼编码。

例4-4，设某通信系统中一个待传输的文本有6个不同字符，它们的出现评率分别是0.5,0.8,1.4,2.2,2.3,2.8，试设计哈夫曼编码。---P124

第五章图

5.1 图的基本概念

5.1.1 图的应用背景

地图着色问题可以用图结构来表示；

地图在计算机中的存储方法也可以用图结构；

还可以用图结构来描述通信网络：       用一个小圆圈代表一个城市，       用之间的连线代表对应两个城市之间的通信线路，       在连线旁边附加一个数值表示该通信线路的造价。

5.1.2 图的定义和术语

概念：图是由顶点集合及顶点间的关系集合组成的一种数据结构，Graph=(V,E）

（1）有向图、无向图： - 若顶点的偶对是有序的则称此图为有向图，有序偶对用尖括号<>括起来； - 若顶点的偶对是无序的，则称此图为无向图，无序偶对用圆括号（）括起来。

（2）邻接点：在无向图中，如果（x,y）∈E，则称x、y互为邻接点； （3）邻接：在有向图中，如果<x, y>∈E，则称x邻接到y。

（4）弧、弧头、弧尾：有向图的边称为弧；例：<v,w>,v称为弧尾货始点，w称为弧头或终点； 注意：在无向图中（v，w）与（w，v）是同一条边，但在有向图中<v，w><w，v>是不同的两条弧。 ====P131,【图5-2】

（5）权、带权图：图的边附带数值，这个数值叫权。每条边都带权的图称为带权图。 表示从一个顶点到另一个顶点的距离、代价或耗费等。

（6）顶点的度：无向图中顶点V的度是与该顶点相关联的边的数目，记为D(v). （7）入度、出度：用于有向图中， - 把以顶点V为终点的弧的数目称为v的入度，记为ID(v); - 把以顶点V为始点的弧的数目称为v的出度，记为OD(v); - 顶点v的度为入度与出度的和，即D(v)=ID(v)+OD(v).

顶点的度/入度/出度

度：是指与该顶点相关联的边的数目；D(v)

入度：箭头进去的数目称为入度；ID(v)

出度：箭头出去的数目称为出度。OD(v)

（8）子图：详见P131子图【图5-4】

（9）路径/路径长度

路径：一个顶点出发到达另一个点，其中经过多个点，便形成一个路径； 导航就是典型的路径算法。

路径长度：路径上边或弧的数目称为路径长度。

（10）简单路径/回路/简单回路

简单路径：路径中（序列中）顶点不重复出现的路径称为简单路径；

含n个顶点的连通图中的任意一条简单路径，其长度不可能超过n-1;

回路：第一个顶点和最后一个顶点相同的路径称为回路或环；

简单回路：除了第一个顶点和最后一个顶点外，其余顶点不重复的回路，称为简单回路或简单环。

（11）连通/连通图/连通分量

连通：在无向图中，如果从顶点V到顶点V'有路径，则称V和V'是连通的；

连通图：在无向图中，如果图中任意两个顶点Vi和Vj都是连通的，则称为连通图；

连通分量：在无向图中，连通分量（点多边多）是极大连通子图；

（12）强连通/强连通图/强连通分量            P132 【图5-6】

强连通：对于有向图，如果图中任意一对顶点Vi和Vj都有顶点Vi到Vj的路径，               也有从Vj到Vi的路径，即两个顶点间双向连通。

强连通图：则称上述有向图是强连通图。

强连通分量：有向图的极大强连通子图称为强连通分量。

（13）生成树/生成森林

生成树：一个连通图的生成树，是含有该连通图的全部顶点的一个极小连通子图。               P133 【图5-7】

若连通图G的顶点个数为n，则G的生成树的边数为n-1；

如果G的一个子图G'的边数大于n-1，则G'中一定有环；

相反，如果G'的边数少于n-1，则G'一定不连通；

生成森林：

在非连通图中，由每个连通分量都可得到一个极小连通子图，即一棵生成树（点多边少）；

接上，那这些连通分量的生成树就组成了一个非连通图的生成森林。

无向完全图

任何两点之间都有边的无向图称为无向完全图。

无向完全图

一个具有n个顶点的无向完全图的边数为C² = n(n-1)/2;

有向完全图

任何两点之间都有弧的有向图称为有向完全图。

一个具有n个顶点的有向完全图的弧数为P² = n(n-1);

图的基本运算

P133  详见“图的基本运算”

5.2 图的存储结构

5.2.1 邻接矩阵

概念： - 邻接矩阵就是用矩阵来描述图中顶点之间的关联关系； - 记录图中各顶点之间关系的二维数组；

无向图的邻接矩阵是一个对称矩阵；A[i][j]=A[j][i]

有向图的邻接矩阵，行表示出度，列表示入度。

利用邻接矩阵可以判定任意两个顶点之间是否有边，并容易求得各个顶点的度。 - 对于无向图，顶点Vi的度是邻接矩阵中第i行或第i列的元素之和。 - 对于有向图，顶点Vi的出度OD(vi)是邻接矩阵中的第i行元素之和，                         顶点vi的入度ID(vi)是邻接矩阵中第i列元素之和。

用邻接矩阵也可以表示带权图。P135【图5-8 带权图及其邻接矩阵】

无向带权图邻接矩阵的建立算法：P135

5.2.2 邻接表

概念： - 邻接表是顺序存储与链式存储相结合的存储方法。 - 是图的一种链式存储结构（数组+链表）;

如果一个无向图有n个顶点，e条边，那它的邻接表需要n个头结点和2e个表结点。

P136 【图5-10】无向图G2的邻接表 P137 【图5-11】有向图邻接表和逆邻接表

在边稀疏 (e < n(n-1)/2) 的情况下，用邻接表比用邻接矩阵节省存储空间。

邻接表上如何求顶点的度P137

无向图：无向图中顶点Vi的度是第i个单链表中的结点数；

有向图

求出度：有向图的邻接表，链表结点的个数是顶点Vi的出度；

求入度：必须遍历整个邻接表。               在所有单链表中，其邻接点域的值为i的结点的个数就是顶点Vi的入度；

对于有向图，有时需要建立一个（逆邻接表），即对每个顶点Vi建立一个以Vi为弧头的邻接点的链表。 ===P137<x，y>x是弧尾，y是弧头。

建立有向图的邻接表的算法：P138

5.3 图的遍历

基本概念

从图中的某一顶点出发访问图中的其余顶点，且每个顶点仅访问一次，这一过程称为图的遍历。 注意：访问一次，但可以经过很多次！

遍历图的方法有两种：深度优先搜索和广度优先搜索。

为了避免重复访问，一般可增设一个辅助数组visited[n]，每个visited[i]初值置为零。一旦顶点Vi被访问，就讲visited[i]置为1。 为了避免重复访问，可设置一个标志顶点是否被访问过的辅助数组。

5.3.1 连通图的深度优先搜索

深度优先搜索(Depth First Search)的基本思想：假定以图中某个顶点Vi为出发点，首先访问出发点Vi， 然后任选一个Vi的未访问过的邻接点Vj，以Vj为新的出发点继续进行深度优先搜索，以此类推， 直至图中所有顶点都被访问过。

图的深度优先搜索遍历类似于树的先序遍历；可以看成是一个递归过程；DFS使用堆栈。

深度搜索的顶点的访问序列不是唯一的。

以邻接表为存储结构，相应的深度优先搜索算法代码：P140; 以邻接表为存储结构，实际上是顺序查找链表，深度优先搜索算法的时间复杂度是O(n+e);===n是图的顶点数，e是图的边数。

以邻接矩阵为存储结构，相应的深度优先搜索算法代码：P141; 以邻接矩阵为存储结构，实际上是通过循环语句顺序访问邻接矩阵的某一行.深度优先搜索算法的时间复杂度是O(n²);

5.3.2 连通图的广度优先搜索

广度优先搜索(Breadth First Search)的基本思想：即从某个结点开始，先访问该结点，然后访问该结点的所有邻接点，再依次访问各邻接点的邻接点。 如此进行下去，直到所有的结点都被访问到。

广度优先搜索遍历类似于树的按层次遍历；

广度优先搜索邻接电的寻找具有先进先出的特征，可采用队列来暂存那些刚访问过的顶点。

以邻接表为存储结构，队列采用链队列，相应的广度优先搜索算法代码：P142 下；

以邻接矩阵为存储结构，查找邻接点是通过循环语句顺序访问邻接矩阵的某一行，相应的广度优先搜索算法代码：P143 ；

5.3.3 应用举例

以邻接表作为存储结构，通过调用深度优先搜索算法实现的计算连通分量的算法：P143；

5.4 图的应用

5.4.1 最小生成树

1）图的一种重要应用——求最小生成树。 2）一个图的最小生成树是指该图的所有生成树中权总和最小的生成树； 3）最小生成树的结构不能生成回路（环）； 4）必须能连结图结构中的所有顶点；

P145,构造最小生成树的Prim(普里姆)算法

是由点找点的算法，需给出一个起点！

P148,构造最小生成树的克鲁斯卡尔(Kruskal)方法

直接选择权值最小的边； 由边找边，不需要知道起点； 构造中，如果形成环，造成环的那条边丢弃，继续选择下一条边。

P149 【图5-18】用Kruskal方法求最小生成树过程示例图

最短路径Dijkstra(迪杰斯特拉)算法

最短路径与最小生成树主要有三点不同：

a. 最短路径的操作对象主要是有向图，而最小生成树的操作对象是无向图；

b. 最短路径有一个始点，最小生成树没有；

c. 最短路径关心的是始点到每个顶点的路径最短，而最小生成树关心的是整个树的代价最小。

5.4.2 拓扑排序

1. AOV网

工程或者某种流程可以分为若干个小的工程或阶段，这些小的工程或阶段就称为活动。 如果以图中的顶点来表示活动，有向边表示活动之间的优先关系，这种用顶点表示活动的有向图称为AOV网。

AOV网中的弧表示了活动之间存在着的制约关系。

2. 拓扑排序

(1)把入度为0的顶点输出后，删除该顶点和相关联的弧， (2)把剩下入度为0的顶点继续输出后删除顶点和相关联的弧， (3)直到所有入度为0的顶点均被输出，拓扑排序完成。====P151

完成拓扑排序的前提条件是AOV网中不允许出现回路。

拓扑排序就是把一个图最终转成线性序列。

拓扑排序的结果不唯一，可能有多种结果！

拓扑排序算法的时间复杂度为O(n+e); n是图的顶点个数，e是图的弧的数目。

第六章查找

6.1 基本概念

查找表中某一元素、读取表中“特定”数据元素、插入和删除一个数据元素等。 若对查找表只进行前两项操作，则称此类查找表为“静态查找表”； 若在查找过程中，向表中插入不存在的数据元素，或者从表中删除某个元素，则称此类表为动态查找表。

静态查找表是以相同特性的数据元素集合为逻辑结构；

动态查找表也是以集合为逻辑结构；在动态查找表中检索和修改操作是相互交叉的。

6.2 静态查找表

概念：仅作查询和检索操作的查找表。

6.2.1 顺序表上的查找

优点：简单、适应面广，对表的结构无任何要求； 缺点：平均查找长度较大，特别是当n很大时，查找效率低。

“查找成功时的平均查找长度(ASL)”作为评价查找算法时间性能的度量。 当查找表有n个元素时，有ASL= Pi * Ci；

Pi的值是难以确定的，通常假设Pi概率相等，即对所有i，有Pi = 1/n;

顺序查找算法的平均查找长度为ASL：（n+1）/2;

6.2.2 有序表上的查找     折半查找/二分查找

在顺序表上，查找运算可以用效率更高的二分查找法实现。

二分查找算法是有序表的查找方法。缺点是要先排序！

二分查找算法每进行一次键值与给定值的比较，查找区间的长度至少减少为原来二分之一，故名“二分查找”

二分查找的长度不超过⌊㏒₂ n⌋ + 1;

二分查找的平均查找长度为：ASL = ㏒₂(n + 1)-1;

二分查找算法的代码实现：P165;

6.2.3 索引顺序表上的查找 （分块查找）

索引顺序表（分块有序表）将整个表分成几块， （1）块内无需，块间有序； （2）块间有序是指后一块表中所有记录的关键字均大于前一块表中的最大关键字。

索引顺序查找的平均查找长度为：ASL = ½（n/s+s）+1;

6.3 动态查找

概念：在查找过程中同时插入查找表中不存在的数据元素，或从查找表中删除已存在的某个数据元素。

动态查找的引入：当查找表以线性表的形式组织时，若对查找表进行插入、删除或排序操作， 就必须移动大量的记录，当记录数量很多时这种移动的代价很大！

二叉排序树概念

利用树的形式组织查找表可以对查找表进行动态高效的查找。

实现动态查找的树表 — 二叉排序树        这种树表的结构本身是在查找过程中动态生成的，对于给定key，若表中存在与key 相等的元素，则查找成功，不然插入关键字等于key的元素。

一棵二叉排序树或者是一颗空二叉树，或者是具有以下性质的二叉树：

左子树上所有结点的键值均小于它的根结点键值；（不存在等于）

右子树上所有结点的键值均大于它的根结点键值；（不存在等于）

左子树和右子树也是二叉排序树。

1. 二叉排序树上的查找

二叉排序树的平均查找长度ASL ≤ 1 + ㏒₂n---P172

算法实现----P169

2. 二叉排序树的插入

二叉排序树的构建---P171

二叉排序树（中序遍历）

中序遍历二叉排序树，可得到一个关键字的有序序列。

二叉排序树（删除）

删除二叉排序树中的一个结点后，必须保持二叉排序树的特性 （左子树所有结点值小于根结点，右子树所有结点值大于根结点）， 即保持中序遍历后，输出为有序序列。

被删除结点具有一下三种情况：

（1）是叶子结点

直接删除结点，并让其父结点指向该结点的指针变为空。

（2）只有左子树或右子树

删除结点，让其父结点指向该结点的指针指向其左子树或右子树， 即用孩子结点替代被删除结点即可。

（3）被删除结点P同时有左右子树

以中序遍历时的直接前驱S替代被删除结点P， 然后再删除该直接前驱（只可能有左孩子）

3. 二叉排序树的查找分析

在最好的情况下，二叉排序树为一个近似完全二叉树， 其查找深度为log2n量级，其时间复杂度为O(log2n)

最坏的情况是退化为顺序查找，二叉树近似线性表， 其查找深度为n量级，其时间复杂度为O(n);

6.4 散列表

- 散列查找（哈希hash查找）：在记录的存储地址和它的关键字之间建立一个确定的对应关系； 不经过比较，一次存取就能得到所查元素的查找方法； - 散列表是一种直接计算记录存放地址的方法，它在关键码与存储位置之间直接建立了映像。

数据元素的键值和存储位置之间建立的对应关系H称为散列函数，用键值通过散列函数获取存储位置 的这种存储方式构造的存储结构称为散列表，这一映射过程称为散列。

设有散列函数H和键值K1/K2，若K1 ≠ K2，但是H(K1) = H(K2)，则称这种现象为冲突，且称K1/K2是相对于H的 同义词。 冲突只能尽可能减少而不能完全避免。

6.4.1 常用散列法 （构造散列函数的方法）

1. 数字分析法

2. 除留余数法：H(key) = key mod p (p ≤ n)

3. 平方取中法

4. 基数转换法

6.4.2 散列表的实现 （解决冲突的方法）

“处理冲突”的实际含义是：为产生冲突的地址寻找下一个散列地址

1. 线性探测法：Hi= [H(key) + di] MOD m;---P174

优点生成后继散列地址计算简单； 缺点非同义词之间对同一个散列地址容易产生堆积；

2. 二次探测法(P175)： d0 = H(key); Di = (d0+i) mod m;

缺点是不易探测到整个散列表的所有空间。

3. 链地址法

4. 多重散列法

优点是不易产生堆积； 缺点是计算量较大；

5. 公共溢出区法

不可能发生堆积！

6.4.3 散列表的基本操作算法

不考！

第七章排序

7.1 概述

排序可分为两大类： （1）内部排序：待排序的记录全部存放在计算机内存中进行的排序过程。 （2）外部排序：待排序的记录数量很大，内存不能存储全部记录，需要对外存进行访问的排序过程。 - 本教材只讨论内部排序。

评价一个排序算法的优劣，通常也用时间复杂度和空间复杂度这两个指标，主要讨论时间复杂度。 在排序过程中主要有比较两个键值大小和将记录从一个位置移动另一个位置这两种基本操作。 因此从键值的比较次数和记录的移动次数两个方面来分析时间复杂度。

当待排序序列已基本有序时，插入排序和交换排序比较有效； 当待排记录数量较大时，选择排序毕竟有效。

时间复杂度O(n²)，空间复杂度O(1);

待排序记录量大时，不适用；

直接插入排序方法是稳定的。

每趟排序不能确定元素的最终排序位置。

7.2 插入排序

1：直接插入排序

算法设计： 每步将一个待排序的对象,按其关键字大小，插入到前面已经排好序的有序表的适当位置上，直到对象全部插入为止。

时间复杂度O(n²)，空间复杂度O(1);

待排序记录量大时，不适用；

直接插入排序方法是稳定的。

每趟排序不能确定元素的最终排序位置。

算法实现

7.3 交换排序

2：冒泡排序

算法设计： 1）设待排序记录序列中的记录个数为n； 2）第i趟冒泡排序从1到n-i+1； 3）依次比较相邻两个记录的关键字，如果发生逆序，则交换之； 4）其结果是这n-i+1个记录中，关键字最大的记录被交换到第n-i+1的位置上，最多作n-1趟。

时间复杂度O(n²)，空间复杂度O(1);

初始排列越有序，对冒泡排序越好； 冒泡排序最少1趟，最多n-1趟；

冒泡排序是稳定的。

每趟排序能够确定元素的最终排序位置。

冒泡排序算法实现---P188

3：快速排序

算法设计： 1）取待排序记录序列中第一个记录作为基准（枢轴），按照该记录的关键字大小，将整个记录序列划分为左右两个子序列； 2）左侧子序列中所有记录的关键字都雄小于或等于基准记录的关键字； 3）右侧子序列中所有记录的关键字都大于基准记录的关键字； 4）基准记录则排在这两个子序列中间（这也是该记录最终应安放的位置）； 5）然后分别最这两个子序列重复施行上述方法，直到所有的记录都排在相应位置上为止。

时间复杂度O(n log2n)，是所有内部排序方法中最好的一个;空间复杂度O(log2n);

初始排列越有序，效率越低O(n²)； 对于较小的n值效果不明显，对较大的n值效果较好。

快速排序是一种不稳定的排序方法。

每趟排序能够确定元素的最终排序位置。

P189 【例7-3】用快速排序方法对45 38 66 90 88 10 25 45进行排序；

7.4 选择排序

4：直接选择排序

算法设计： 第一轮找出最小的与第一个位置交换，第二轮找出第二小的与第二个位置交换。（注意与直接插入排序的区别）

时间复杂度O(n²)，空间复杂度O(1);

初始排序与直接选择排序无关，是否有序都不影响； 不适宜于n较大的情况；

直接选择排序是一种不稳定的排序方法。

每趟排序能够确定元素的最终排序位置。

5：堆排序

算法设计： 在输出堆顶的最小键值之后，使得剩余的n-1个简直重新建成一个堆，则可得到n个键值中的最小值。如此反复执行，便能得到有序序列，这个过程称之为堆排序。

实现堆排序需要解决两个问题（P194）： （1）如何根据给定的序列建初始堆？ （2）如何在输出堆顶元素之后调整剩余元素成为一个新堆？

堆排序性能分析： - 对于长度为n的序列，其对应的完全二叉树的深度为K（2^(k-1）≤n ＜ 2^k； - 对深度为k的堆，筛选算法中进行的关键字比较次数最多为2(k-1)次； - 堆排序时间主要耗费在建初始堆和调整建新堆(筛选)上； - 建初始堆最多做n/2次筛选； - 对长度为n的序列，排序最多需要做n-1次调整建新堆(筛选)；

时间复杂度O(n log2n)，空间复杂度O(1);

初始排序与堆排序无关，是否有序都不影响算法性能； 不适宜于n（记录值）较少的情况；对较大的n值效果较好。

堆排序是不稳定的。

每趟排序能够确定元素的最终排序位置。

7.5 归并排序

6：二路归并排序

算法设计： 1）归并是将两个或两个以上的有序表合并成一个新的有序表； 2）从排序操作来看，当两个位置的元素不符合前小后大，其他排序算法是使用交换操作。 3）而归并排序算法是借助额外空间，省略了交换操作，直接把排好序的元素插入到新空间中。（每轮两个序列，两两比较）

时间复杂度O(n log2n)，空间复杂度O(n);

初始排序不影响二路归并排序性能； 在n较大时，归并排序时间性能优于堆排序，但需要的辅助存储量较多。

二路归并排序是稳定的。

每趟排序不能确定元素的最终排序位置。

总结