数据结构

3.1 线性结构

3.1.1 线性表

• 线性表的定义：n个元素的有限序列
• 线性表的存储结构
  • 顺序存储
    • 用一组地址连续的存储单元依次存储线性表中的数据元素，使得逻辑上相邻的元素物理上也相邻
    • 优点：可以随机存取表中元素，读取、查找比较方便。
    • 缺点：必须按最大可能长度预分配存储空间，存储空间的利用率低，表的容量难以扩容，是一种静态存储结构；插入与删除需要移动大量元素，平均移动次数为n/2
    • 
  • 链式存储
    • 存储各元素的结点的地址并不要求是连续的，逻辑上相邻的数据元素，物理上不一定相邻
    • 链式存储中每个元素都包括数据域和指针域两部分。如a元素就由数据a和指针a->next两部分组成
    • 优点：插入与删除不需要移动元素，较为方便，只需要修改指针即可；存储空间不需要提前确定，可以动态改变，是一种动态存储结构。
    • 缺点：不能对数据元素进行随机访问；需要存储指针，有空间浪费存在。
    • 
    • 单链表的插入和删除操作
      • 在ab之间插入s元素：
        • ①将s->next指向b，即s->next = b
        • ②将a->next指向s，即a->next = s
        • 两步不能颠倒，如果先执行 a->next = s，会导致原有的 a->next（也就是 b 的地址）被覆盖丢失
      • 删除abs中的b元素：a->next = a->next->next

3.1.2 栈和队列

栈和队列属于受限线性表，极特殊的线性表。

• 栈
  • 栈是限定仅在表尾 (栈顶）进行插入或删除操作的线性表，是一种先进后出 (LIFO） 的线性结构。
  • 表尾称为栈顶，表头称为栈底
  • 栈的应用：括号匹配、迷宫求解、汉诺塔
  • 
• 队列
  • 队列是只允许在表的一端进行插入，在另一端进行删除操作的线性，是一种先进先出 (FIFO） 的线性结构。
  • 允许插入的一端称为队尾，允许删除的一端称为队头
  • 队列的应用：操作系统中的作业排队
  • 
• 循环队列
  • 循环队列是一种顺序表示的队列，用一组地址连续的存储单元依次存放从队头到队尾的元素。由 于队列中队头和队尾的位置是动态变化的，要附设两个指针front和rear，分别指示队头元素和队尾元素在数组中的位置
  • 
  • 设置循环队列Q的容量为M
    • 队空：Q.front == Q.rear
    • 队满：Q.front == (Q.rear + 1) % M
    • 入队：Q.rear = (Q.rear + 1) % M
    • 出队：Q.front = (Q.front + 1) % M
    • 队长：(Q.rear - Q.front + M) % M

3.1.3 串

• 串是仅由字符构成的有限序列，是一种线性表。本质就是字符串
• 串的模式匹配算法
  • 基本概念
    • 主串：就是原始字符串 (如：S = “ABCABD”）
    • 模式串：待查找的子字符串 (如 P = “ABD”）
    • 匹配成功：即在主串中能匹配到模式串
  • 匹配算法
    • 基本算法：一个字符一个字符匹配，直到匹配到。
    • KMP算法 (3个人名的简称）：是对基本匹配算法的改进，其改进之处在于：每当匹配过程中出现相比较的字符不相等时，不再需要回溯主串的字符位置指针，而是利用己经得到“部分匹配”结果，将模式串向右“滑动”尽可能远的距离，再继续比较即可
      • next函数：当模式串第j个字符与主串失配时，模式串中与主串继续匹配的位置
      • 
      • 

3.2 数组、矩阵和广义表

3.2.1 数组

• 一维数组a[n]
  • 则a[i]的存储地址为：a[0]的地址 + i*len
• 二维数组a[m][n] (m行n列）
  • 按行存储：则a[i][j]的存储地址为：a[0]的地址 + (i*n+j)*len
  • 按列存储：则a[i][j]的存储地址为：a[0]的地址 + (j*m+i)*len

3.2.2 矩阵

所有矩阵都可以用数组表示，但并非所有数组都能称为矩阵，矩阵在形式上常表现为二维数组。

• 对称矩阵
  • n阶矩阵A中的元素满足a[i][j] = a[j][i] (其中i≥1，j≥1），则称为n阶对称矩阵
• 三角矩阵
  • 矩阵的上三角或下三角 (不包括对角线）中的元素均为常数c或0的n阶矩阵。
• 对角矩阵
  • 矩阵中的非零元素都集中在以主对角线为中心的带状区域
• 稀疏矩阵
  • 在一个矩阵中，若非零元素的个数远远小于零元素的个数，且非零元素的分布没有规律，则称之为稀疏矩阵
  • 稀疏矩阵的存储方式：
    • 三元组，用三个域存储每个非零元素，即行、列、值。
    • 十字链表，对于每个非零元素会有5个域，分别是行、列、值、指向同行下一个非零元素的指针right和指向同列下一个非零元素的指针down

3.2.3 广义表

• 了解即可
• 是由0个或多个单元素或子表组成的有限序列，线性表的元素都是结构上不可分的单元素，而广义表的元素既可以是单元素，也可以是有结构的表，包括其本身
• head() 和tail()：
  • 取表头 (广义表的第一个表元素，可以是子表，也可以是单元素）
  • 取表尾 (广义表中，除了第一个表元素之外的 其他所有表元素构成的表，非空广义表的表尾必定是一个表，即使表尾是单元素）

3.3 树

3.3.1 树与二叉树的定义

• 树是一种非线性结构，树中的每一个数据元素可以有两个或两个以上的直接后继元素，用来描述层次结构关系
• 树的基本概念
  • 
  • 双亲、孩子和兄弟
    • 结点子树的根称为该结点的孩子结点，B、C、D分别是节点A的孩子节点
    • 该结点称为其子结点的双亲，A是B、C、D的双亲节点
    • 具有相同双亲的结点互为兄弟，B、C、D互为兄弟节点
  • 结点的度：一个结点拥有子树的个数称力该结点的度，即斜线的数量。A的度为3，B的度为2，C的度为1，D的度为1
  • 叶子结点：度为O的结点。E、F、G、H都是叶子结点
  • 结点的层次：结点A在第一层，B、C、D在第二层，E、F、G、H在第三层
  • 树的深度：树的深度为3
  • 结点总数n = 分支总数m + 1
    • 假设树T的度为4，则n0是度为0的结点数，n1是度为1的结点数，n2是度为2的结点数，n3是度为3的结点数，n4是度为4的结点数。
    • 结点总数n = n0 + n1 + n2 + n3 + n4
    • 分支总数m = n0*0 + n1*1 + n2*2 + n3*3 + n4*4
    • 所以：n0 + n1 + n2 + n3 + n4 = n0*0 + n1*1 + n2*2 + n3*3 + n4*4 + 1
• 二叉树
  • 与树的区别是二叉树各个结点的度最大为2
  • 满二叉树：在一棵二叉树中，如果所有非叶子结点都同时具有左孩子和右孩子，并且所有叶子结点都在同一层上，即一棵深度为k并且含有 $2^k$-1 个结点的二叉树称为满二叉树
  • 完全二叉树：一棵深度为k，有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i (1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树，完全二叉树几乎和满二叉树一样，仅是最后一层的叶子节点不满而已
  • 

3.3.2 二叉树的性质与存储结构

• 二叉树的性质
  • 在二叉树的第i层上最多有 $2^{i-1}$ 个结点 (i≥1）
  • 深度为k的二叉树最多有 $2^k$-1 个结点 (k≥1）
  • 对于任何一棵二叉树，如果其叶子结点数为n0，度为2的结点数为n2，则有n0= n2+1。 注意叶子节点，即度为0的节点，他可能不是在最后一层的
• 二叉树的存储结构
  • 顺序存储：在采用顺序存储时，完全二叉树与一般二叉树相比节省了空间，这是因为一般二叉树需要添加一些“虚结点”而造成了空间的浪费。即没有孩子节点的位置会存空值。
  • 链式存储：一般用二叉链表来存储二叉树结点，二叉链表中除了该结点本身的数据外，还存储有左孩子结点的指针、右孩子结点的指针，即一个数据+两个指针 (lchild、data、rchild）。每个二叉链表结点存储一个二叉树结点，头指针则指向根结点。
  • 

3.3.3 二叉树的遍历

• 
• 前序遍历：根左右
  • 无轮那种遍历方式都是从上到小，从左到右
  • ① abc
  • ② bde，也就是将①中的b替换成②中的bde，即abdec
  • ③ cf，也就是将②中的c替换成cf，即abdecf
  • ④ eg，也就是将③中的e替换成eg，即abdegcf
  • ⑤ gh，也就是将④中的g替换成gh，即abdeghcf
  • 中序遍历和后续遍历也是一样的道理
• 中序遍历：左根右，dbgheacf
• 后序遍历：左右根，dhgebfca
• 层次遍历：按层次，从上到下，从左到右，abcdefgh

3.3.4 线索二叉树

• ① 若n个结点的二叉树使用二叉链表存储，则必然有n+1个空指针域，这些空指针完全闲置，相当于浪费了近一半的指针存储空间
• ② 普通二叉树的遍历 (如中序遍历）依赖递归或栈，空间复杂度高。如果需要定位某个节点的 “前驱” 或 “后继” (比如中序遍历中某节点的前一个/后一个节点），普通二叉树必须重新完整遍历一次树
• 为了解决①空间利用率不高和②遍历的空间效率低的问题，就引入了线索二叉树。利用这些空指针域来存储结点的前驱结点和后继结点信息，为此需要增加两个标志，以区分指针域存放的到底是孩子结点还是遍历结点
  • 线索二叉树结构为：ltag、lchild、data、rchild、rtag ，
    • ltag为0，lchild 指向左子节点；ltag为1，lchild 遍历顺序下的前驱节点 (左线索）；
    • rtag为0，rchild 指向右子节点；rtag为1，rchild 遍历顺序下的后继节点 (右线索）；
  • 遍历过程中，如中序遍历结果为dbgheacf，则d的前驱为空，后继为b，就是遍历结果前后内容

3.3.5 最优二叉树

• 最优二叉树
  • 最优二叉树也称为哈夫曼树 (霍夫曼、赫夫曼），是一种带权路径长度最短的二叉树
  • 哈夫曼树的结点数一定为奇数
  • 哈夫曼树的结点的度为0或者2，不能为1
  • 
  • 路径：树中一个结点到另一个结点之间的通路，A到F的路径为A-C-E-F
  • 路径长度：通路上的分支个数，A到F的路径长度为3
  • 树的路径长度：根结点到每一个叶子结点之间的路径长度之和，到B为1，到D为2，到F为3，到G为3，所以输的路径长度为1+2+3+3=9
  • 权：结点代表的值，B旁边的数字5，就是权值
  • 结点的带权路径长度：该结点到根结点之间的路径长度与该结点权值的乘积，F结点的带权路径长度=3*1=3
  • 树的带权路径长度：树中所有叶子结点的带权路径长度之和，5*1+4*2+1*3+2*3 = 22
• 最优二叉树的构建
  • 有n个权值，则构造出的哈夫曼树有n个叶子结点
  • 构造哈夫曼树时一般遵循权值左小右大的原则
  • 构建步骤：
    • （1）将所有权值看成是有n棵树的森林
    • （2）选权值最小的两个数，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和
    • （3）从森林中删除选取的两棵树，并将新树加入森林
    • （4）重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树
• 哈夫曼编码
  • 先构造哈夫曼树，左分支表示字符0，右分支表示字符1，可得到字符的哈夫曼编码，如上面A到F的哈夫曼编码值就是110

3.3.6 树和森林

• 树的存储结构：了解即可，双亲表示法、孩子表示法、孩子兄弟表示法
• 树和森林的遍历：和二叉树的遍历方法一样
  • 树的先根遍历
  • 树的后根遍历
• 树、森林和二叉树之间的相互转换
  • 树转二叉树原理：树的最左边结点作为二叉树的左子树，树的其他兄弟结点作为其左边兄弟结点的右子树。
    • 用 “左孩子” 表示原树中的 “父子关系”
    • 用 “右孩子” 表示原树中的 “兄弟关系”
  • 任何一颗与树对应的二叉树，其右子树必为空
  • 
• 二叉排序树
  • ① 要么为空树，要么具有②、③点的性质
  • ② 若左子树不为空，则左子树的所有结点值均小于根结点
  • ③ 若右子树不为空，则右子树的所有结点值均大于根结点
• 平衡二叉树
  • ① 要么为空树，要么具有②、③点的性质
  • ② 它的左子树和右子树都是平衡二叉树
  • ③ 左子树和右子树的深度之差的绝对值不超过1

3.4 图

3.4.1 图的定义与存储

图也是一种非线性结构，图中任意两个顶点之间都可能有直接关系

• 
• 有向边和无向边：带箭头的单通道为有向边，不带箭头的双通道为无向边
• 无向图：图中任意顶点之间均为无向边
• 有向图：图中任意顶点之间均为有向边
• 完全图：
  • ① 无向完全图中，两两顶点之间均有连线，n个项点的无向完全图有n*(n-1)/2条边
  • ② 有向完全图中，两两顶点之间均有连线，n个顶点的有向完全图有n*(n-1)条边
• 度、出度和入度：
  • 度：进出某个顶点的边的数目，有向图中，顶点的度为出度和入度之和
  • 入度：在有向图中，进入该顶点的边数
  • 出度：在有向图中，从该顶点出去的边数，在无向图中，不分入度和出度
• 路径：存在一条通路，可以从一个顶点到达另一个顶点，有向图的路径也是有方向的
• 连通图和连通分量：针对无向图。若从顶点v到顶点u之间是有路径的，则说明v和u之间是连通的，若无向图中任意两个顶点之间都是连通的，则成为连通图。无向图G的极大连通子图称为其连通分量。
• 强连通图和强连通分量：针对有向图。若有向图中任意两个顶点之间都相互存在路径，即存在顶点v到顶点u，也存在顶点u到顶点v的路径，则称为强连通图。有向图中的极大连通子图称为其强连通分量
• 生成树：一个连通图的生成树就是该图的连通性不变，但没有环路的子图。一个有n个顶点的生成树有且仅有n-1条边
• 网：边带权值的图称为网

图的存储结构

• 邻接矩阵
  • n个顶点的图可以用n*n的邻接矩阵来表示。如果顶点i到顶点j存在边，则矩阵元素A[i,j]的值置为1，否则为0
  • 
• 邻接表
  • 邻接表是链式存储结构。用一个一维数组存储所有的顶点，对于数组中的每个顶点都生成一个链表。链表中每个顶点(表结点)包括顶点号、顶点信息(如边的权值)、以及指向下一个顶点的指针
  • 

3.4.2 图的遍历

图的遍历是从图中的任意一个顶点出发，对图中的所有顶点访问一次且只访问一次。分为深度优先搜索和广度优先搜索

• 深度优先搜索：类似于树的先根遍历，一条分支走到头，直到无路可走再退回上一层
• 广度优先搜索：类似于树的层次遍历，访问所有同层次邻居，本层次结束访问下一层
• 具体步骤：
  • 第一步：必须先将图转化为邻接矩阵或邻接表 (计算机只能理解这种结构化数据）
  • 第二步：从起始顶点开始，以 “当前访问的顶点” 为核心，通过存储结构 (邻接矩阵的行/邻接表的链表）找到它的邻居
  • 第三步：按 DFS (栈/递归）或 BFS (队列）的规则，选择下一个要访问的邻居，重复第二步直到所有顶点访问完
• 两种优先搜索的时间复杂度：使用邻接矩阵均为 O($n^2$)，使用邻接表均为 O(n+e)，其中n为顶点的 个数，e为边的个数

3.4.3 生成树及最小生成树

• 生成树：一个连通图的生成树就是该图的连通性不变，但没有环路的子图。一个有n个顶点的生成树有且仅有n-1条边。本质是树
• 最小生成树：所有可能的生成树中，边的权值之和最小的那棵树。注意：最小生成树是一棵树，而不是图，也没有环路
• 求连通带权无向图的最小生成树：
  • 
  • 普里姆算法 (Prim）
    • 选择一条权值最小的边，并选中边的顶点，从已选顶点中连接权值量小的边，直至连接所有顶点，但不能出现环路。时间复杂度为 O($n^2$)，n为顶点个数，因此只与顶点相关，适用于求稠密图的最小生成树
    • ①先选权值最小的边，即1，选中的顶点就是v1和v3；
    • ②从已选的顶点中选择权值最小的边，v1和v3连接的边的权值有v1的5、6和v3的4、5、5、6，权值最小的为4，选中的顶点就为v6，所有选中的顶点为v1、v3、v6；
    • ③重复第②步，找到权值最小的边，即v6和v4之间的2，选中的顶点为v1、v3、v6、v4；
    • ④重复第②步，找到v1、v3、v6、v4对应的权值最小的边为5，有v1-v4、v3-v4、v2-v3，由于如果选v1-v4、v3-v4会形成环路，所以只能选v2-v3，选中的顶点为v1、v3、v6、v4、v2；
    • ⑤接着选中v2权值最小的边，v2-v5，至此顶点v1、v3、v6、v4、v2、v5都被包含，就生成了最小生成树。
  • 克鲁斯卡尔算法 (Kruskal）
    • 选择权值最小的边连接，直至连接所有的顶点，但不能出现环路。时间复杂度为O(elog2e)，e为边的个数，因此只与边相关，适用于求稀疏图的最小生成树。
    • 如果过程中出现相同权值，并且连接后不出现环路，可以随意连接一条就行，接着可以尝试连接另一个相同权值的边，如果没有环路仍可以连接
    • ①择权值最小的边连接，即1，连接边为v1-v3；
    • ②重复第①步，即2，连接边为v4-v6；
    • ③重复第①步，即3，连接边为v2-v5；
    • ④重复第①步，即4，连接边为v3-v6；
    • ⑤重复第①步，即5，因为连接v1-v4、v3-v4会形成环路，所以只能连接v2-v3，至此顶点v1、v2、v3、v4、v5、v6都被包含，就生成了最小生成树。；

3.4.4 拓扑排序和关键路径

• 拓扑排序
  • AOV网 (Activity On Vertex）：顶点 = 活动，侧重 “谁先谁后”，指顶点表示活动的网络，是一种用节点代表任务、用边表示任务间先后依赖关系的有向图。
  • 拓扑排序：拓扑排序并不唯一
    • 
    • ① 在AOV网中选择入度为0的顶点并输出
    • ② 从网中删除该顶点及与该顶点有关的弧
    • ③ 重复前两步，直到网中不存在入度为0的顶点为止
• 关键路径
  • AOE网 (Activity On Edge）：边 = 活动，侧重 “多久完成”，指边表示活动的网络，是一种用边代表任务、用节点代表事件（状态）的有向图，常用于估算项目完成的最短时间
  • 关键路径：关键路径并不唯一
    • 
    • 在从源点到汇点的路径中，长度最长的路径称力关键路径。关键路径上的所有活动均是关键活动。如果任何一项关键活动没有按期完成，就会影响整个工程的进度，而缩短关键活动的工期通常可以缩短整个工程的工期。关键路径上的长度就是完成整个工程项目的最短工期
    • 不同路径相当于并行的任务线，要完成该任务就需要完成所有任务线，所以任务完成的最短工期，就是耗时最长的任务线的耗时。

3.4.5 最短路径

• 最短路径：从源点到各顶点最短的路径
• 关键路径：从源点到汇点最短的路径

3.5 查找

3.5.1 查找的基本概念

略

3.5.2 静态查找表的查找方法

• 顺序查找
  • 从表的一端开始，将给定值与表中记录的关键字逐个进行比较，若相等，则查找成功；若整个表中记录的关键字与给定值均不相等，则查找失败
  • 平均查找长度：(1+2+…+n)/n = (n+1)/2，其中为表中记录的个数
  • 优点：算法简单且适应面广，对表的结构没有要求，表中记录也无须有序。
  • 缺点：n值较大时，平均查找长度较大，查找效率较低。
• 折半查找
  • 假设表中的元素存储在一维数组r[1，…，N]中，且表中元素按递增方式排序（），则折半查找的基本思想：将给定值key与表中中间位置元素r[mid]进行比较，若key==r[mid]，则查找成功；若key>r[mid]，则给定值key在后半个子表r[mid+1，...，n]中继续递归查找：若key<r[mid]，则给定值key在前半个子表r[1，...mid-1]中继续递归查找；递归以上步骤，直到查找成功或子表为空为止
  • 平均查找长度：log2(n+1) - 1
  • 优点：查找效率较高
  • 缺点：顺序存储且表中元素必须有序排列；插入和删除需要移动大量元素
• 分块查找
  • 又称为索引顺序查找，是对顺序查找方法的一种改进，查找效率介于顺序查找和折半查找之间。在分块查找中，首先将表分成若干块，每一块内的关键字不一定有序，但块之间是有序的；此外还建立了一个索引表，索引表引表按关键字有序排列。分块查找的基本思想：在索引表中确定给定值所在的块，在块内顺序查找。
  • 平均查找长度：(b+1)/2+(s+1)/2，b是块数，s是块内元素数
  • 优点：查找效率好于顺序查找，可通过索引表，查找给定值所在的块
  • 缺点：查找效率不及折半查找
  • 

3.5.3 动态查找表

略

3.5.4 哈希表

• 也称为散列表，通过计算以记录的关键字为自变量的函数(哈希函数)来得到该记录的存储地址。在查找操作时，用同一哈希函数H(key)计算待查记录的存储地址，到相应的存储单元中匹配信息来判定是否查找成功。如 存储时，12 mod 11=1，就将12存储到1的位置，查找时，依然使用12 mod 11=1，去1的位置查找是否为12
• 对于不同的关键字，却有相同的哈希函数值，则称为冲突，12 mod 11=1，34 mod 11=1，这就会出现12和34都要存储在1的位置，这就出现了冲突
• 常见的处理冲突的方法：
  • 线性探测再散列
  • 链地址法

3.6 排序

3.6.1 排序的基本概念

3.6.2 简单排序

3.6.3 希尔排序

3.6.4 快速排序

3.6.5 堆排序

3.6.6 归并排序

3.6.7 基数排序

3.6.8 内部排序方法小结

3.6.9 外部排序