数据结构与算法

考研计算机专业基础408数据结构与算法，将知识点进行了归纳和整理，帮助学习者理解和记忆。直击重点，可以作为学习笔记和复习资料，帮助大家系统地回顾和巩固所学知识，知识点系统且全面，希望对大家有所帮助！

数据结构与算法

• 排序
• 查找
• 数据结构三要素
  • 运算
    • 定义：针对逻辑结构
    • 实现：针对物理结构
  • 物理结构/存储结构
    • 顺序存储：逻辑相邻物理也相邻
      • 优点：随机存取
      • 缺点：一整块存储单元
    • 链式存储：不要求逻辑相邻物理也相邻-用指针
      • 优点：不会出现碎片，不会溢出
      • 缺点：只能顺序存取，指针占用额外空间
    • 索引存储：存储时建立索引表
      • 优点：快
      • 缺点：占用额外空间，修改索引表麻烦
    • 散列存储/哈希存储：直接计算
      • 优点：快
      • 缺点：若散列函数不好会冲突
  • 逻辑结构
    • 线性结构
      • 相同类型 有限序列 有次序
      • 线性表
        • 顺序存储
          • 顺序表
            • 优点：随机存取 ，缺点：插入删除需要移动大量元素
            • 分配方式
              • 动态分配：占满时开辟更大的空间，替换原来的空间 仍然连续，但是是执行时动态分配的
              • 静态分配：固定，会溢出
        • 链式存储
          • 单链表
            • 判空条件：头结点指针为空
          • 双链表
          • 循环链表
            • 不存在空指针
            • 循环单链表
              • 方便删除尾结点一定要循环双链表
              • 头结点是尾结点下一个，有尾结点方便找头结点
              • 判空条件：头结点的指针=头指针L
            • 循环双链表
              • 判空条件：头结点的prior和next都=头指针L
          • 静态链表
            • 用数组表示链表
            • 需要连续空间，但插入删除不需要移动
            • 不方便，在没有指针时可以用
      • 受限线性表
        • 栈
          • 后进先出
            • 顺序存储
              • 顺序栈：用连续的存储单元存储自栈底到栈顶的元素
              • 共享栈：有效利用存储空间
            • 链式存储
              • 链栈：便于多个栈共享存储空间，不会上溢 用单链表实现：所有操作在表头进行（没有头结点）
          • 卡特兰数公式：有n各不同元素进栈时，出栈元素不同排列个数为1/(n+1)Cn/2n
          • 应用
            • 括号匹配
              • 最后出现的左括号最先被匹配（后进先出）
              • 不合法情况
                • 括号序列不匹配
                • 左括号单身（算法结束时栈不为空）
                • 右括号单身
            • 表达式求值
              • 中缀表达式转后缀表达式 （左优先原则）
                • 手算：①.按运算顺序加括号 ②.将运算符移至括号后面(左 右 符)
                  • 转前缀：符 左 右
                • 机算：①.遇到操作数，直接加入后缀表达式 ②.遇到"("直接入栈，遇到")"依次弹出栈中运算符，直到遇到"(" ③.遇到运算符，若优先级高于栈顶运算符，则直接入栈， 否则从栈顶开始依次弹出高于或等于当前运算符的所有运算符， 直到遇到低于它的或"("停止 ④.字符扫描完，弹出栈中剩余运算符
              • 后缀表达式求值
                • 从左往右扫描后缀表达式，若是操作数就压入栈中 若是操作符就弹出两个数，先弹出的是右操作数 并将结果压入栈
              • 在中缀转后缀的同时计算
                • 初始化两个栈，扫到数压入数栈，扫到操作符按照"中缀转后缀"的 规律压入和弹出栈，每弹出一个符，就弹出两个数，并将结果压回数栈
              • 前缀表达式求值
                • 从左往右扫描先出栈的是左操作数
            • 递归
              • 递归模型必须满足①.递归体②.递归出口
              • 系统为每一层开辟递归工作栈
              • 递归效率不太高（包含很多重复计算），但代码简单
              • 栈可以将递归算法转换为非递归算法
              • 递归不是必须使用栈
        • 队列
          • 先进先出
            • 顺序存储
              • 用数组存放的连续存储单元，随着元素出队会出现“假溢出”
              • 循环队列--解决“假溢出”（逻辑上是一个环）--用%实现
            • 链式存储
              • 有头指针和尾指针的单链表
            • 双端队列
              • 两端都可以插入和删除
                • 输入受限：只有一端可以输入
                • 输出受限：只有一端可以输出
                • 输入1234 通过输入受限不能输出：4213，4231 通过输出受限不能输出：4132，4231
          • 应用
            • 层次遍历中
              • 对下一步预处理
                • 树的层次遍历
                • 图的广度优先遍历
            • 计算机系统中
              • 解决主机与外部设备速度不匹配问题
                • 打印机缓冲区FIFO
              • 解决多用户引起的资源竞争问题
                • 先来先服务FCFS
      • 线性表推广
        • 数组
          • 顺序存储
            • 一维数组
              • LOC(ai)=LOC(a0)+i*size （i从0开始）
                • 若是从1开始就是i-1
            • 二维数组
              • 元素是定长数组的线性表
                • 按行优先
                  • LOC(aij)=LOC(a00)+[i*(h2+1)+j]*size
                • 按列优先
                  • 下标范围 i∈[0，h1]，j∈[0，h2]
                  • LOC(aij)=LOC(a00)+[j*(h1+1)+i]*size
            • 应用
              • 压缩存储
                • 多个值相同的元素分配一个存储空间
                • 对称矩阵aij=aji
                  • 存放在一维数组[n(n+1)/2]中 下标从0开始
                    • 数组长度是n(n+1)/2 最后一位下标是n(n+1)/2-1
                    • 下三角区和主对角线：k=i(i-1)/2+j-1
                      • 1+2+3+...+(i-1)+(j-1)
                    • 上三角区ij互换
                • 三角矩阵
                  • 存放在一维数组[n(n+1)/2+1]中 比对称矩阵多一位储存常量
                    • 数组下标从零开始 多出的一位下标应该是n(n+1)/2
                    • 下三角矩阵
                    • 上三角矩阵：k=(i-1)(2n-i+2)/2+j-i
                      • n+n-1+n-2+...+(n-i+2)+(j-i)
                • 三对角矩阵/带状矩阵 当|i-j|＞1时，aij=0
                  • 第一行和最后一行每行两个元素 其他行每行三个元素
                  • k=2i+j-3
                  • 若已知k
                    • i=|(k+1)/3+1|
                    • j=k-2i+3
              • 稀疏矩阵
                • 压缩后就失去了随机存取特性
                  • 三元组（行标，列标，值）,还要保存矩阵大小
                  • 十字链表存储
      • 类似于线性表
        • 数据对象是字符集
        • 字符串/串
          • '零个或多个字符，有限'
            • 单引号不算长度
            • 顺序存储
              • 长度大于max会截断
            • 堆存储
              • 动态分配
            • 块链存储
              • 每个节点可以存放一个或多个字符，称为块
              • 不满用#补上
          • 空格算长度，组成的串叫空格串不是空串
          • 任意连续字符叫子串，子串第一个字符为位置（从1开始）
          • 长度相等且对应字符相等才算相等
          • 字符集编码：英文ASCII字符集，中英文Unicode字符集
          • 模式匹配
            • 子串的定位操作
            • 暴力匹配算法
              • 将主串所有与模式串长度相同串依次与模式串对比
              • 最坏o(mn) m，n为主串和模式串长度
              • 主串指针会回溯
            • KMP算法
              • 在子串P与主串S很多部分匹配时 快
              • o（m+n）
              • 主串已匹配相等的序列有某个后缀是模式串的前缀 则将模式串后移到他们相对应的位置 且模式串后移的位数只与模式串本身有关
                • 手算：在不匹配的位置前划一条线 模式串一步步后退直到分界线之前 能对上或模式串完全跨过分界线 此时j（分界线右边的位置）就是next[j]
                  • i不变，j=next[j]
                • next[j]：模式串第j位不匹配时，从next[j]往后比
                  • next[1]=0，next[2]=1
                • 若Pj=P[nextj]，会出现模式串中相同的字符重复和主串Sj比较
              • KMP的进一步优化
                • next[j]与目前j所指字符
                  • 不同nextval[j]=next[j]
                  • 相同nextval[j]=nextval[next[j]]
    • 非线性结构
      • 集合
      • 树
        • 一种递归的数据结构，分层结构
          • n个节点有n-1条边
            • 每个树中结点都比边多1 所以森林中 结点-边=树数
            • 总度数=孩子数=边数=结点数-1
          • n=0叫空树，没有结点
          • n=1，只有一个根结点，它是唯一没有双亲的节点，是第一层
          • 深度是所在层次，从上往下数 高度是该节点子数高度，从下往上数
          • 孩子的个数叫度，结点最大度数叫树的度
          • 有孩子叫分支结点/非终端结点，没有孩子叫叶结点
        • 性质
          • 度为m的树第i层至多有mⁱ⁻¹
          • 高度为h的m叉树至多(1-mʰ)/(1-m)
            • 等比数列
          • 度为m，n个结点的树，最小高度「log(n(m-1)+1) / m
          • 度为m，n个结点的树，最大高度n-m+1
            • 有一层有m个结点，其他层就一个
          • 高度h，度为m，至少结点h+m-1
        • 二叉树
          • 分类
            • 满二叉树
              • 编号i，左孩子2i，右孩子2i+1,双亲i/2向下取整
            • 完全二叉树
              • 最后一个分支结点是2/n
              • 最多只有一个度为1的结点
                • 有左孩子无右孩子
              • 若结点数n为奇数，没有度为1的结点 若为偶数，有一个度为1的结点n/2
              • 结点i所在层次（log₂ⁱ向下取整+1）
              • 有n个结点的树高度为log₂(n+1)向上取整
            • 顺序存储
            • 二叉排序树
              • 左＜根＜右
            • 平衡二叉树
              • 任意结点左右子高度差小于1
            • 正则二叉树
              • 度只有0和2
            • 顺序存储要添加空结点
              • 把n层的节点全存起来
              • 链式存储
                • 二叉链表
                  • n个结点就有n+1个空链域
                    • 2n-(n-1)
                  • 只能体现父子关系，不能找前驱后继
                • 三叉链表
                  • n+1个空链
          • 性质
            • n0(叶结点数)=n2+1
            • 高度h至多2ʰ-1个结点
          • 遍历
            • 先序NLR
              • 根左右
            • 中序LNR
              • 左根右
            • 后序LRN
              • 适合用于删除二叉树，先删孩子再删根
              • 后序遍历二叉树找后继目前仍不能求解
              • 左右根
            • 层次遍历
              • 利用队列
            • 由遍历序列构造二叉树
              • 中序+三选一
                • 先序
                  • 第一个结点是根结点，把中序分割成两个子序列 分别是左子树的中序和右子树的中序，在按长度在先序中 也划分左子树和右子树，首结点又是两子树的根节点......
                • 后序
                  • 最后一个结点是根节点
                • 层次
                  • 第一个结点是根结点，第二个结点是左子树的根 第三个结点是右子树的根......
          • 线索二叉树
            • 是物理结构（线索链表）
            • 可以加快寻找前驱后继的速度
            • 线索化的实质是遍历二叉树
            • 中序线索二叉树找后继
              • 若tag为1，右链为后继
              • 若tag为0，右子树的最左下结点为后继
            • 后序二叉树找后继
              • 若是根，后继为空
              • 若是右孩子或没有右兄弟的左孩子，后继为双亲
              • 若是左孩子，右兄弟树后序遍历的第一个结点
        • 存储结构
          • 双亲表示法（顺序）
            • 利用双亲的唯一性
              • 但求孩子要遍历
          • 孩子表示法（顺序+链式）
            • 也可以存储森林
            • 每个结点的孩子结点视为一个链表，n个头指针又是一个数组
            • n个结点有n个孩子链表，没有孩子是空表
            • 找孩子简单，但求双亲要遍历
          • 孩子兄弟表示法（链式）
            • 二叉链表
              • 方便实现树与二叉树转换
              • 若没有parent指针找双亲麻烦
              • 也可以储存森林，根节点视为平级的兄弟关系
        • 树、二叉树、森林
          • 树转二叉树
            • “左孩子右兄弟”
              • 每个结点的左指针指向他的第一个孩子
              • 右指针指向他在树中相邻的右兄弟
          • 森林转二叉树
            • 先把每颗树转为二叉树，每棵树的根视为兄弟，第二颗做第一颗的右子树，第三颗做第二颗的右子树...
          • 二叉树转森林
            • 根节点及其右指针串作为多颗树的根节点
            • 每个根节点的左指针及其一连串右指针顺序挂在该根节点下方
          • 树的遍历
            • 先根
              • 与相应二叉树先序序列相同
            • 后根
              • 与相应二叉树中序序列相同
              • 其实根是最后访问的
          • 森林的遍历
            • 先序
              • 依次对各个树先根
            • 中序
              • 依次对各个树后跟
            • 先转成二叉树也一样
        • 应用
          • 哈夫曼树（最优二叉树）
            • 带权路径长度最小的树
              • 所有结点的路过的结点数*权值的总和
            • 构造过程
              • 所有结点放到一个F
              • 构造一个新结点，从剩余结点选两个权值最小的做左子树右子树，权值为他们权值的和
              • 新结点放回F，重复操作
            • 特点
              • 每个结点都成为叶结点
              • 权值越小路径越长
              • 共新建n-1个结点，总结点数2n-1
              • 不存在度为1的结点
            • 哈夫曼编码
              • 可变长度编码：对频率高的字符用短编码
              • 前缀编码：没有一个编码是另一个编码的前缀
              • 用二叉树，左0右1，必前缀编码
              • 每个字符出现的频率作为权值，路径上分支的字符串作为编码
          • 并查集
            • 查找:从下往上找根
            • 合并:一个根的双亲指针指向另一个根
            • 根结点的下标设置为该子集合元素数量的相反数
            • 优化：成员少的指向成员多的根，尽可能让树不长高
              • 深度不超过 log₂ⁿ向下取整+1
        • 图不可以是空图，顶点集V一定非空，边集E可以空
      • 图
        • 简单图：没有重复的，自己到自己的边
        • 完全图：任意两个定点之间都存在（方向相反的两条）边
        • 子图：V'是V的子集，E'是E的子集，若包含所有原点，则称为生成子图
        • 带权图：边被标上权值
        • 相对而言稀疏，稠密图
        • 路径：顶点序列，路径上的边数叫路径长度，第一个顶点和最后一个顶点相同是环/回路
        • 顶点不会重复出现叫简单路径，除第一个和最后一个其他不重复叫简单回路
        • 有向图
          • E取值0~n(n-1)
          • 弧：顶点的有序对‹v(尾),w(头)›
          • 强连通
            • 两个顶点相互有路径存在，他们是强连通的，任意一对顶点都强连通，就是强连通图， 极大连通子图称为强连通分量
            • n个顶点的强连通图最少n条边
              • 形成环路
            • 非强连通图最多(n-1)(n-2)+1条边
          • 度TD
            • 依附于顶点v的边数
            • 全部顶点度之和等于边数的二倍
            • 一个顶点入度为0，其余顶点入度为1，叫有向树
        • 无向图
          • E取值0~n(n-1)/2
          • (v,w)=(w,v)
          • 连通
            • 极大连通子图称为连通分量
            • 若两个顶点有路径存在，他们就是连通的，任意两个顶点都连通，就是连通图
            • n个顶点的连通图至少n-1条边
              • 有一个顶点和其他全连
              • 大于n-1条边一定有环路
            • n个顶点的非连通图最多Cn-₁²条边
              • 其他全两两相连，只有一个顶点不连
          • 生成树
            • 不唯一
            • 不存在回路且连通的无向图
            • 连通图
              • 包含全部顶点的极小连通子图(n-1条边)
              • 砍去一条边就是非连通图，加上一条边就会有环路
            • 非连通图的连通分量的生成树构成生成森林
          • 度
            • 入度ID：以v为终点的数目
            • 出度OD：以v为起点的边数
            • TD
            • 全部顶点的出度之和和入度之和相等，并且等于边数
            • 所有顶点的度之和是偶数
        • 存储
          • 邻接矩阵法
            • 顺序存储
              • 一维数组存顶点（可省略），二维数组存边
            • 1有0没有
              • 带权图写权值
              • Aij--i指向j
            • 无向图的邻接矩阵是对称矩阵
              • 压缩存储
            • 空间o（n²）
            • 无向图第i行/列的元素个数就是度 有向图第i行元素个数是出度，第i列是入度
            • 适合稠密图
            • 唯一
            • Aⁿij--从i到j长度为n的路径数
            • 适合找两个点是否有邻边，但找一个点的邻边要o（n）
          • 邻接表法
            • 顺序存储和链式存储
              • 顶点顺序存储，每个顶点一个单链表（边表）
            • 无向图空间o（v+2E） 有向图空间o（V+E）
              • 无向图每条边在邻接表出现两次
            • 适合稀疏图
            • 适合找一个顶点的邻边
            • 不唯一
            • 无向图边表结点个数就是度 有向图边表结点个数是出度
          • 十字链表法
            • 有向图 链式存储（顶点结点间是顺序存储）
            • 图的十字链表不固定，但十字链表确定唯一的图
            • 空间o（v+E）
          • 邻接多重表法
            • 无向图 链式存储
          • 弧用结点表示
• 程序=数据结构+算法
• 算法
  • 五个特性
    • 有穷性
      • 算法是有穷的，程序可以无穷
    • 确定性：相同的输入相同的输出
    • 可行性
    • 输入：零个或多个
    • 输出：一个或多个
  • 效率
    • 时间复杂度低
      • 问题规模n的函数
    • 空间复杂度低
      • 额外的辅助空间