第3章 数据结构与算法
3.1 线性结构
3.1.1 线性表
- 线性表的定义
一个线性表是n个元素的有限序列（n≥0），通常表示为（a1，a2， a3，……，an）。 - 线性表的存储结构
(1) 顺序存储
用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑关系相邻的两个元素在物理位置上也相邻。
优点：可以随机存取表中的元素
缺点：插入和删除操作需要移动大量的元素
(2) 链式存储
用节点来存储数据元素，元素的节点地址可以是连续的，也可以是不连续的。
优点：插入和删除操作不需要移动元素
缺点：不能进行数据元素的随机访问
链表的类别：
单链表：
单链表存储不能随机访问表中的任一结点，必须从头结点依次.next。
循环链表：
双向链表：
线性表的查找方法 （09年第26题）
(1) 顺序查找
算法非常简单，但是效率较低，因为它是用所给关键字与线性表中各元素的关键字逐个比较，直到成功或失败。
(2) 折半查找
优点是比较次数少，查找速度快，平均性能好；
缺点是要求待查表是有序表，且插入和删除困难。
适用于不经常变动而查找频繁的有序列表。
一般不进行表的插入和删除操作。
需要对中间元素进行快速定位，在链表结构上无法实现。
(3) 分块查找
又称索引查找，主要用于分块有序表的查找。所谓分块有序是指将线性表 L (一堆数组)分成m个子表(要求每个子表的长度相等)，且第 i+1 个子表中的每一个项目均大于第 i 个子表中的所有项目。因此，分块查找的关键在于建立索引表，其查找的平均长度介于顺序查找和折半查找之间。
3.1.2 栈和队列
- 栈 （21年第5题）
1）栈的定义和基本运算
2）栈的存储结构
栈是按“后进先出”的规则进行操作的。
（1）顺序栈
用一组地址连续的存储单元依次存储自栈顶到栈底的数据元素。
存储空间是预先定义或申请的，因此可能会出现栈满的情况。每一个元素入栈时都要判断栈是否已满。需要设置一个头指针指到栈顶。需要附设指针 top 指示栈顶元素的位置
（2）链栈
用链表存储栈中的元素。栈中元素的插入和删除仅在栈顶进行，因此不必设置头节点，链表的头指针就是栈顶指针。
3）栈的应用
函数调用和返回控制是用栈实现的。（19年第22题） - 队列
1）队列的定义和基本运算
2）队列的存储结构
队列是按“先进先出”的规则进行操作的。 （21年第7题）
（1）顺序队列
用一组地址连续的存储单元依次存储队列的数据元素。由于队中元素的插入和删除限定在表的两端进行，因此设置队头指针和队尾指针。
（2）链队列
为了便于操作，可给链队列添加一个头节点，并令头指针指向头节点。因此，队列为空的判定条件是头指针和尾指针的值相同，且均指向头节点。
例题：
设栈 s 和队列 q 的初始状态为空，元素a、b、c、d、e依次进入栈s，当一个元素从栈中出来后立即进入队列q。若从队列的输出端依次得到元素c、d、b、a、e，则栈s的容量至少为（）
解：看栈最多的时候能容纳多少元素。
3.1.3 串
字符串是一串文字及符号的简称，是一种特殊的线性表。
字符串的基本数据元素是字符，常常把一个串作为一个整体来处理。
- 串的定义及基本运算
串是仅由字符构成的有限序列，是取值范围受限的线性表。
一般记为 S=‘a1a2…an’,其中 S 是串名，单引号括起来的字符序列是串值。
• 串长：即串的长度，指字符串中的字符个数。
• 空串：长度为0的空串，空串不包含任何字符。
• 空格串：由一个或多个空格组成的串。
• 子串：由串中任意长度的连续字符构成的序列称为子串。
• 串相等：指两个串长度相等且对应位置上的字符也相同。
• 串比较：两个串比较大小时以字符的ASCII码值作为依据。 - 串的存储结构
（1）顺序存储：用一组地址连续的存储单元来存储串值的字符序列
（2）链式存储：字符串可以采用链表作为存储结构，当用链表存储串 中的字符时，每个结点中可以存储一个字符，也可以存储多个字符。
- 字符串运算
- 串的模式比较
3.2 数组和矩阵 87
- 数组
1）数组的定义及基本运算
一维数组是长度固定的线性表，数组中的每个数据元素类型相同。n维数组是定长 线性表在维数上的扩张，即线性表中的元素又是一个线性表。
2）数组的顺序存储
由于数组一般不做插入和删除，且元素个数和元素之间的关系不再发生变动，那 么数组适合采用顺序存储结构。
二维数组的存储结构可分为以行为主序（按行存储）和以列为主序 （按列存储）两种方法。
设每个数据元素占用L个单元，m、n为数组的行数和列数，那么：
以行为主序优先存储的地址计算公式为： Loc(aij)=Loc(a11)+((i-1)×n+(j-1))×L
以列为主序优先存储的地址计算公式为： Loc(aij)=Loc(a11)+((j-1)×m+(i-1))×L - 矩阵
• 这里主要讨论一些特殊矩阵的压缩存储的问题。
• 对多个值相同的元素可以只分配一个存储单元，零元素不分配存储单 元。
• 下面主要讨论对称矩阵、三对角矩阵、稀疏矩阵。
1） 特殊矩阵
（1）对称矩阵
若矩阵An×n中的元素有aij=aji（1≤i，j≤n）的特点，则称之为对称矩阵。 如：
• 则矩阵An×n的n2个元素可以压缩存储到可以存放n(n+1)/2个元素的存储 空间中。 • 假设以行为主序存储下三角（包括对角线）中的元素，并以一个一维 数组B[n(n+1)/2]作为n阶对称矩阵A中元素的存储空间，则B[k] （0≤k<n(n+1)/2）与矩阵元素aij（aji）之间存在着一一对应的关系：
（2）三对角矩阵
• 对角矩阵是指矩阵中的非零元素都集中在以主对角线为中心的带状区 域中，其余的矩阵元素都为零。
• 下面主要考虑三对角矩阵，即只有主对角线及其左右两边为非零元素。
• 若以行为主序将n阶三对角矩阵An×n的非零元素存储在一维数组B[k] （0≤k<3n-2）中，则元素位置之间的对应关系为： k=3 × (i-1)-1+j-i+1=2i+j-3 (1≤i,j≤n)
2）稀疏矩阵：
• 在一个矩阵中，若非零元素的个数远远少于零元素的个数，且非零元 素的分布没有规律，则称之为稀疏矩阵。
• 可以用一个三元组(i,j,aij）唯一确定矩阵中的一个元素。
3.3 树和图 90
3.3.1 树 90
- 树的定义
树是n(n≥0)个结点的有限集合。当n=0时称为空树。在任一非空树中，有且仅有一个称为根的结点；其余结点可分为m(m≥0)个互不相交的有限集T1,T2…,Tm，其中每个集合又都是一棵树，并且称为根结点的子树。
（1）双亲、孩子和兄弟
（2）结点的度：一个结点的子树的个数记为该结点的度。
（3）叶子结点：也称为终端结点，指度为零的结点。
（4）内部结点：度不为零的结点称为分支结点或非终端结点。除根结点之外，分支 结点也称为内部结点。
（5）结点的层次：根为第一层，根的孩子在第二层，依此类推。
（6）树的高度：一棵树的最大层次数记为树的高度（或深度）。
（7）有序（无序）树：若将树中结点的各子树看成是从左到右具有次序的，即不能 交换，则称该树为有序树，否则称为无序树。
（8）森林：m(m≥0)棵互不相交的树的集合。 - 二叉树的定义
定义：二叉树是n(n≥0) 个结点的有限集合，它或者是空树 (n=0)，或者是由一个根结点及两棵不相交的、分别称为左子树和右子树的二叉树所组成。
树和二叉树的区别：
（1）二叉树中结点的子树要区分左子树和右子树， 即使只有一棵子树，而树中不用区分。
（2）二叉树中结点的最大度为 2，而树中无限制。 - 二叉树的性质 （21年第8题）
性质1：二叉树第i（i≥1）层上至多有 2^(i-1) 个节点。
性质2：深度为k 的二叉树至多有 2^k-1 个结点（k≥1）。
性质3：对任何一棵二叉树，若其终端结点数为n0，度为2的结点数为n2，则 n0=n2+1
性质4：具有n个结点的完全二叉树的深度为log2n + 1 - 二叉树的存储结构
1）二叉树的顺序存储结构
2）二叉树的链式存储结构
- 二叉树的遍历 （15年第21题）
遍历是按某种策略访问树中的每个结点，且仅访问一次。
依据访问根结点次序的不同，可分为前序遍历法、中序遍历法、后序遍历法。
（1）中序遍历法：（左、根、右）
① 中序遍历根的左子树。
② 访问根结点。
③ 中序遍历根的右子树。
依此类推。
（2）前序遍历法：先访问根结点（根、左、右）
（3）后序遍历法：后访问根结点（左、右，根）
（4）层序遍历法：按层从上至下、每层从左至右的顺序遍历
前序遍历：A B E F I J C D G H
后序遍历：E I J F B C G H D A
层次遍历：A B C D E F G H I J - 最优二叉树
最优二叉树又称哈夫曼树，是一类带权路径长度最短的树。
• 权：是一个人为的概念，表示计算机对每个结点的访问频率。
• 路径长度：是每一个结点到根结点的路径的长度。
• 结点的带权路径长度：是指从该结点到根结点之间的路径长度与该结点权的乘积。
• 树的带权路径长度为树中所有叶子结点的带权路径长度之和。
• 构造最优二叉树的哈夫曼方法：
（1）根据给定的 n 个权值{w1，w2，…，wn}构成n棵二叉树的集合F={T1,T2，…，Tn}， 其中每棵树 Ti 只有一个带权为 wi 的根结点，其左右子树均空。
（2）在F中选取两棵根结点的权值最小的树作为左右子树，构造一棵新的二叉树， 置新构造二叉树的根结点的权值为其左、右子树根结点的权值之和。
（3）从F中删除这两棵树，同时将新得到的二叉树加入到F中。 重复（2）（3）步，直到F中只含一棵树时为止，这棵树便是最优二叉树（哈夫曼树）。
• 最优二叉树的一个应用是对字符集中的字符进行编码和译码。 - 二叉查找树 （二叉排序树）（09年第27题）
• 它或者是一棵空树，或者是具有如下性质的二叉树：
（1）若它的左子树非空，则左子树上所有结点的关键码值均小于根结点的关键码值。
（2）若它的右子树非空，则右子树上所有结点的关键码值均大于根结点的关键码值。
（3）左、右子树本身就是两棵二叉查找树。
• 对二叉查找树进行中序遍历，可得到一个关键码递增有序的结点序列。
• 二叉查找树的作用：使用二叉查找树来查找树中的数值比普通的二叉树更为方便。
• 构造二叉树时需进行平衡华处理，使每个节点左右子树的高度的绝对值不超过1。
给定N个权值作为N个叶子结点，构造一颗二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
霍夫曼树可以用来进行通信电文的编码和解码。
B-树是一种平衡的多路查找树
(1) B-树中，所有非终端结点也就是非叶子结点都会包含关键字；
(2) 所有叶子结点都出现在同一层次上并且不带信息（可以看作是外部结点或查找失败的结点），层次相同也就是高度相同，从根结点到每个叶子结点的路径长度相同；
(3) 所有非终端结点包含的关键字数量是不确定的，指向的子树个数也是不确定的。
3.3.2 图 97
1. 图的定义及术语
图G（Graph）是由两个集合：V和E所组成的，V是有限的非空顶点 （Vertex）集合，E是用顶点表示的边（Edge）集合，图G的顶点集和边集分别记为V（G）和E（G），而将图G记作G=(V，E)。
可以看出，一个顶点集合与连接这些顶点的边的集合可以唯一表示一个图。
在图中，数据结构中的数据元素用顶点表示，数据元素之间的关系用边表示
1）有向图：图中每条边都是有方向的。从顶点vi到顶点vj表示为<vi,vj>， 而从顶点vj到顶点vi表示为<vj,vi>。有向边也称为弧。起点称为弧尾， 终点称为弧头。
有向图a的顶点集合为： V(a)={1，2，3，4}
边的集合为： E(a)={<1, 2>，<1, 3>，<4, 2>，<1, 4>，<4, 1>}
2）无向图：图中每条边都是无方向的。顶点 vi和 vj之间的边用(vi,vj)表 示。在无向图中，(vi,vj)和(vj,vi)表示的是同一条边。
左侧无向图b的顶点集合为： V(b)={1，2，3，4，5}
边的集合为： E(b)={(1, 2)，(1, 3)，(1, 4)，(4, 5)，(2, 3)，(3, 4)， (3, 5)}
3）完全图：若一个无向图具有n个顶点，而每一个顶点与其他n-1个顶点之间都有边，则称之为无向完全图。显然，含有n个顶点的无向完全图 共有n(n-1)/2条边，类似地，有n个顶点的有向完全图中弧的数目为 n(n-1)，即任意两个不同顶点之间都存在方向相反的两条弧。
4）度、出度、入度：
顶点 v 的度是指关联于该顶点的边的数目，记作D(v)
若为有向图，度表示该顶点的入度和出度之和
顶点的入度是以该顶点为终点的有向边的数目
顶点的出度指以该顶点为起点的有向边的数目
5）路径
6）子图
7）连通图
8）强连通图
9）网：边或者弧具有权值的图
- 图的存储结构
1）邻接矩阵表示法
2）邻接链表表示法
邻接链表是为图的每一个顶点建立一个单链表，第i个单链表中的节点 表示依附于顶点vi的表（对于有向图是以vi为尾的弧）。
• 邻接链表中的表节点有表节点和表头节点两种类型：
无向图的邻接链表表示法
有向图的邻接链表表示法
带权值的网的邻接链表表示法
3.4 常用算法 102
3.4.1 算法概述 102
3.4.2 排序 105
可参考这篇博文，结合动画浅显易懂：六大排序算法
1. 直接插入排序
• 具体做法是：在插入第 i 个记录时，R1，R2，… ，Ri-1已经排好序，将记录Ri 的关键字 ki 依次与关键字 ki-1，ki-2，… ，k1进行比较，从而找到 Ri 应该插入的位置，插入位置及其后的记录依次向后移动。
例： 待排序列：35 12 67 29 51 第1步：35 第2步：12 35 第3步：12 35 67 第4步：12 29 35 67 第5步：12 29 35 51 67 12345678
2. 冒泡排序
• 首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则交换两个记录的值，然后比较第二个记录和第三个记录的关键字，依此类推
（左边大于右边交换一趟排下来最大的在右边）
待排序列：35 12 67 29 51 第一次冒泡排序： ①：12 35 67 29 51 ②：12 35 67 29 51 ③：12 35 29 67 51 ④：12 35 29 51 67 第二次冒泡排序： ①：12 35 29 51 67 ②：12 29 35 51 67 12345678910
3. 简单选择排序 （不稳定的排序算法） （21年上第6题）
• n个记录进行简单选择排序的基本方法是： 通过 n-i 次关键字之间的比较，从 n-i+1 个记录中选出关键字最小的记录，并和第 i（1≤i≤n）个记录进行交换，当 i 等于 n 时所有记录有序排列
找出每次剩下数字中的最小值
例： 待排序列：35 12 67 29 51 ①：找出最小值12，与第一个关键字进行交换：12 35 67 29 51 ②：找出剩下4个记录中的最小值29，与第二个关键字交换：12 29 67 35 51 ③：找出剩下3个记录中的最小值35，与第三个关键字交换：12 29 35 67 51 ④：找出剩下2个记录中的最小值51，与第四个关键字交换：12 29 35 51 67 123456
4. 希尔排序
• 希尔排序又称 “缩小增量排序”，是对直接插入排序方法的改进。 （21年上第9题）
• 先将整个待排记录序列分割成若干子序列，然后分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序
例： 待排序列： 48 37 64 96 75 12 26 48 54 03 d1=5（距离为5的倍数的记录为同一组）： 48 37 64 96 75 12 26 48 54 03 d1=5 排序后： 12 26 48 54 03 48 37 64 96 75 d2=3（距离为3的倍数的记录为同一组）： 12 26 48 54 03 48 37 64 96 75 d2=3 排序后： 12 03 48 37 26 48 54 64 96 75 d3=1（距离为1的倍数的记录为同一组，即所有记录为一组）： 12 03 48 37 26 48 54 64 96 75 d3=1 排序后： 03 12 26 37 48 48 54 64 75 96 12345678
5. 快速排序
• 通过一趟排序将待排的记录划分为独立的两部分，称为前半区和后半区，其中，前半区中记录的关键字均不大于后半区记录的关键字，然后再分别对这两部分记录继续进行快速排序，从而使整个序列有序。
• 具体做法：附设两个位置指示变量 i 和 j ,它们的初值分别指向序列的第一个记录和最后一个记录。设枢轴记录（通常是第一个记录）的关键字为 pivot，则首先从 j 所指位置起向前搜索，找到第一个关键字小于 pivot 的记录时将该记录向前移到 i 指示的位置，然后从 i 所指位置起向 后搜索，找到第一个关键字大于 pivot 的记录时将该记录向后移到 j 所指位置，重复该过程直至 i 与 j 相等为止
