数据结构

计算机考研必收藏!一张思维导图带你学懂计算机专业重要的专业基础课-数据结构树与二叉树知识点汇总。该导图详细著明了树的基本概念、二叉树、树与二叉树的相互转化、树与二叉树的应用、应用知识点。如果有帮到你，不妨点个赞吧!

数据结构

• 第一章：绪论
  • 估计
    • 时间复杂度：耗时的度量
    • 空间复杂度：所需存储空间的度量
    • 取最高次项：O(……)
• 第二章：线性表
  • 线性关系：一对一
  • 基本操作
    • 初始化、销毁
    • 查询：个体、整体
    • 动态变化：插入、删除
  • 存储结构
    • 顺序存储：顺序表SqList
      • 空间利用率不高 表的容量不可扩充，或扩充代价大（耗时） 插入和删除需要移动大量元素，耗时
      • 类型定义
        • 定长数组、当前长度
        • 基址、当前长度、当前分配的容量
      • 基本操作的实现
        • 求表长、取第i个元素
          • 随机存取，能直接找到第i个
        • 按值查找
          • 逐个比较
        • 指定位置插入
          • 先使待插入位置及后面的元素后移，腾出位置； 再插入。 注意： 溢出的判断，重新分配动态空间； 程序的健壮性
        • 指定位置删除并返回
          • 待删除位置之后的元素，从前到后逐个前移，覆盖。
        • 移动操作很耗时间
    • 链式存储：线性链表LinkList
      • 类型定义
        • 单链表
          • 线性、单向、不连续存储 结点：数据域、后向指针域(*next) 动态空间
            • 是否引入头节点？
              • 有头节点：使空表成为实体，不必单独处理第一个元素
              • 无头节点：空表时L=NULL
        • 循环链表
          • 从一个结点出发，单向遍历就能访问到所有节点：把末尾指针回指，循环链表 在O(1)时间内访问到头尾节点：修改数据结构，头尾指针表示
        • 静态链表
          • 不支持指针类型时
          • 借用数组来表示链表，借用int来指示位置替代指针
          • vs 动态链表
        • 双向链表
          • 固定时间内找到某一结点的前驱和后继
          • 双向链，插入删除注意每步的顺序
      • 基本操作的实现
        • 以带头结点的单链表为例 体会利用流程图和例子来分析设计算法
          • 流程图： 画出初始状态、结果状态； 明确中间需要哪些步骤； 明确中间步骤的次序：根据步骤之间的依赖关系，是否会发生信息丢失；
        • 指定位置插入
          • 寻址：先找待插入位置之前的元素位置p p=L; j=0; while(p!=NULL && j<i-1){ p=p->next; j++; } 如果地址正确，则按步骤插入，注意步骤的先后 否则返回error
        • 指定位置删除并返回
          • 需要free掉该结点，故需要两个指针p、q，其一来指向待删除结点。 同样需要注意各步骤之间的次序。
        • 寻址挺耗时
        • 创建操作
          • 头插法
            • 新节点插入到线性表中第一个节点之前
          • 尾插法
            • 新节点插入到线性表最后一个节点之后
• 第三章：栈和队列
  • 栈
    • 仅在表尾（栈顶）进行插入或删除操作 后进先出
    • 基本操作
      • 初始化空栈、判断栈空、判断栈满
      • 取栈顶元素
      • 入栈
      • 出栈
    • 存储结构
      • 顺序栈SqStack
        • 顺序存储 通过重新分配空间realloc来实现空间扩充
        • 类型定义
          • 注意top的含义 顺序表第二种定义
          • 栈底指针、栈顶指针(指向下一个空位置)、当前分配的存储容量
        • 基本操作的实现
          • 初始化：S.base=S.top
          • 栈空：S.base==S.top
          • 栈满：S.top-S.base==S.stacksize
          • 入栈：*S.top++=e
          • 出栈：e=*--S.top
      • 链栈
        • 链式存储 无法通过top随机存取，一般用的少 通过动态分配空间malloc来扩充 可以不必引入头节点
    • 应用
      • 数制转换
      • 括号匹配的检验
      • 行编辑程序
        • 需要有字符来标识
      • 迷宫求解
      • 表达式求值、转换
        • 表达式分类
          • 中缀
            • 需要比较算符优先级，并判断结合性！
          • 前缀：波兰式
            • 算符入栈后，判断其后是否连续入栈两个操作数，若是则求值并将整个过程看作一个操作数入栈； 需要递归 不需要比较优先级，也不需要判断结合性
          • 后缀：逆波兰式
            • 遇到算符时，立即计算，后将结果存入 不需要比较优先级，也不需要判断结合性
        • 算符间优先级关系
        • 大致思路
          • 用两个栈，一个存操作符，一个存操作数 一定条件下操作符、操作数出栈运算后重新入栈 条件与表达式的形式有关
      • 递归栈
        • 递归：递推式+回归 减小问题规模，将原问题的求解分解为若干有重复操作的子问题的求解。 当满足递归结束条件后，逐级返回，依次获得较复杂问题的解
        • 会画递归栈的工作状态
  • 队列
    • 只允许在一端（队尾）插入，在另一端（队头）删除 先进先出
    • 基本操作
      • 初始化空队列
      • 入队列、出队列
      • 判断队空、判断队满
      • 取队头元素
    • 存储结构
      • 链式存储：链队列LinkQueue
        • 线性链表
          • 队头指针指向队头元素
          • 队尾指针指向队尾元素
      • 顺序存储：顺序队列SqQueue
        • 类型定义
          • 基址
          • 头指针，指示队头元素
          • 尾指针，指向队尾元素的下一个位置
          • 均为int型，标识关于基址的偏移量
        • 基本操作的实现
          • 初始化空队列
            • Q.front=Q.rear=0;
          • 入队列
            • 判断是否队满；若未满则放入到Q.rear++的位置上
          • 出队列
            • 判断是否队空；若非空则Q.front++
          • 队空
            • Q.front==Q.rear
          • 队满
            • Q.rear==MAXQSIZE
      • 链式和顺序都可以做成循环的
        • 链式存储的，通过每次都使末尾指针回指 顺序存储的，通过取模
        • 如不设置头节点，队满和队空条件冲突
          • 设标志位，保存上次的动作
          • 修改数据结构，增加当前队列长度
          • 有维护代价
          • 头结点
            • 少用一个元素空间
    • 应用
      • 离散事件模拟
        • 见代码
• 第四章：串
  • 串：由零个或多个字符组成的有限序列 子串：串中任意个连续的字符组成的子序列 串用一对单引号括起来，但是这对单引号不属于串
  • 基本操作
    • 与线性表的相同
  • 存储结构
    • 定长顺序存储表示SString
      • 会发生溢出，超过定长的部分舍去
      • 类型定义
        • 一般字符型数组
      • 基本操作的实现
        • 串联接
        • 求从某位置开始的某长度的子串
    • 堆分配存储表示HString
      • 优化了上述两个基本操作
      • 类型定义：基址+长度
      • 基本操作的实现
        • 串联接
        • 求从某位置开始的某长度的子串
    • 块链存储表示LString
      • 类型定义
        • 头指针、尾指针
        • 当前长度
        • 每个结点都是一个小数组+后向指针域
      • 基本操作：方便对串中一小部分进行插入、删除处理
  • *模式匹配
    • 子串的定位操作
    • 有点类似状态机里的序列识别
    • 匹配+回退
    • 改进：不一定需要回退到首字母的后继，可以根据子串的特点，来求每个字母失配时需要返回的位置，
• 第五章：广义表
  • 定义
    • LS=(a1,a2,...,an)
    • 其中ai可以是单个元素（原子），也可以是广义表（子表）
    • 意味着可以无限套娃
  • 存储结构
    • 头尾链表存储表示
      • 每向下一层，就加一层括号，深度和层次有关，见p109
    • 扩展线性链表存储表示
      • 像是线性表扩展到高维，比头尾链表多了一个头结点，不占层数，见p110
• 第六章：树
  • 一对多
  • 定义和基本术语（见课本）
    • 分层，根作为第一层，最大层数为树的深度
    • 叶子=终端结点
    • 孩子、双亲、兄弟、祖先、子孙
    • 有序树：左右兄弟有顺序，不能互换
    • 森林
  • 二叉树
    • 一对二
    • 定义
      • 二叉树不是有序树、二叉树不是树
      • 二叉树的子树有左右之分，决定形状
    • 性质
      • 在二叉树的第i层上至多有2的i-1次方个结点
      • 深度为k的二叉树至多有2的k次方-1个结点
        • 最多时成为满二叉树
      • 完全二叉树：最下层不一定满，但一定有
      • 对完全二叉树从上到下，从左到右，从1到n编号，则有
        • i=1为根
        • 非根结点，双亲的编号为|_ i/2 _|
        • 结点i的左孩子是2i，右孩子是2i+1（不一定存在）
        • 顺序存储，能在O(1)内找到任意结点
    • 存储结构
      • *顺序存储
      • 链式存储
        • 二叉链表
          • data：当前结点数据
          • lchild：左孩子
          • rchild：右孩子
        • 三叉链表：比二叉链表多一个指向双亲的
  • 二叉树的遍历
    • 顺序
      • 以当前结点的访问次序命名，左子树总比右子树先访问
      • 先序：中左右
      • 中序：左中右
      • 后序：左右中
      • 递归
        • 设计时常回溯+剪枝
      • 层次遍历：从上到下，从左到右
        • 用队列： 根访问并入队列； 若队列非空执行循环：出队头，左右孩子依次访问并入队列
    • 两序列唯一确定一棵二叉树：必须有中序序列
    • 应用：表达式树
  • *线索二叉树
    • 把原先是null的指针利用起来，指向遍历序列中的前驱(l)/后继(r)
      • 增设l/rTag域，标识该指针是指向孩子还是别的
  • 树的存储结构
    • 双亲表示法：线性表
      • 结构体数组，结点中
        • 一个域存储结点信息
        • 另一个域存储当前结点双亲在数组中的存储位置
          • 不方便：求结点孩子时需要遍历整个数组
    • 孩子表示法：多重链表
      • 类似于一组单链表
        • 头结点存储一个结点的信息
        • 表结点依次存储该结点从左到右的孩子在数组中的存储位置
    • 孩子兄弟表示法：二叉链表
      • lchild指向当前结点的第一个孩子
      • rchild指向当前结点右侧的兄弟
      • 将树转化为了二叉树
  • Huffman树及应用
    • 定义
      • 树的带权路径长度：树中所有叶子到根的带权路径长度和
      • Huffman树：带权路径长度和最小的二叉树
      • 前缀编码：任何一个字符的编码都不能 是另一个字符的编码前缀
    • 操作
      • 构造Huffman树
        • 选择两棵根节点权值最小的树（结点）作为新树的左右子树 新树的根节点没有数据，其权值为左右子树根节点权值和
      • Huffman编码：以出现频率为权，构造Huffman树，从根开始寻址，左0右1
• 第七章：图
  • 多对多，注意时间复杂度
  • 图的定义和术语（见图论课本）
  • 图的存储结构
    • 基本操作不难，难在对存储结构本身的理解
    • 邻接矩阵：二维数组
      • n个顶，n*n的矩阵，存储权值/∞或1/0
        • 容易求得每个顶点的度
    • 邻接表
      • 类似于树的孩子表示法，把孩子替换为邻顶
    • *十字链表
      • 对有向图
        • 类似于邻接表，结点中存的是弧的信息，结点指针域指向的是弧头/弧尾相同的
    • *邻接多重表
      • 对无向图中十字链表的改进
        • 每条边只对应一个结点
    • 不要求算法，大概理解见课本示意图
  • 图的遍历
    • 深搜DFS
      • 类似于树的先序遍历
      • 一条线走到底，不行再逐层回退试探下一个
        • 递归函数DFS：访问顶v；对v尚未访问的邻顶递归调用DFS
          • 考虑到非连通图，一次递归只能访问完一个连通片 所以给递归函数加一个上层函数，增设visited数组，确保每条路都访问到
        • 非递归函数DFS：使用栈，起点先入栈；每次出一个，入它的邻顶
          • 入栈时访问
    • 广搜BFS
      • 类似于图的层次遍历
      • 离出发点近的先访问，“层次”
        • 非递归函数BFS：使用队列，起点先入队；每次出一个，入它的邻顶
          • 入队列时访问
  • 图的连通性问题
    • 无向图的连通分量和生成树
      • 前面DFS、BFS访问顶点时，顺便把弧/边收集了
    • *有向图的强连通分量
      • 从一顶u向外做单向DFS，筛选出u能单向到达的顶 在筛选过程中，通过finished数组记录下第一个所有邻顶都被访问过的顶v
        • 再以v为中心，向外逆向遍历刚才筛选出的所有顶点构成的顶点导出子图 将这些顶点划分成几组，得到的即为强连通分量
    • 最小生成树
      • prim
        • 通过边权选顶，逐个扩大顶集S
          • O(n²)
      • kruscal
        • 选边，逐个填充无边的图
          • O(eloge)
    • *关节点和重连通分量
      • 关节点：一顶的顶割集
      • 重连通分量：没有关节点的连通分量
  • 有向无环图（DAG图）及其应用
    • 拓扑排序：由偏序（有先后顺序的关系）得到全序
      • 例如已知A>C, B>C, 现在人为指定A>B>C
    • 关键路径：从源点到汇点的最长路径
  • 最短路径
    • Dijkstra
      • 同样是逐步扩大顶集S
• 第九章：查找
  • 查找表
    • 同一类型的数据元素（或记录）构成的集合
    • 常见操作
      • 查询是否在表中
      • 检索某元素存储的信息
      • 关键字
        • 唯一地标识一个记录
          • 主关键字
        • 标识若干记录
          • 次关键字
      • 插入
      • 删除
    • 分类
      • 只做前两种“查找”操作
        • 静态查找表
      • 查找过程中涉及插入删除
        • 动态查找表
  • 查找的性能分析
    • 平均查找长度
      • 为了找到，需要和给定值进行比较的关键字个数的期望值 查找成功时的+查找不成功时的
  • 静态查找表
    • 顺序表或线性链表表示
      • 不知是否有序
        • 顺序查找
          • 平均查找长度
            • 等概率时的，为(n+1)*3/4
          • 提高效率
            • 访问频度表，把查找概率大的排的靠前些
      • 有序表
        • 等概率查找
          • 折半查找
            • 指针low、high、mid mid=|_(low+high)/2_| 每次与中间比较，决定替换上界还是下界
              • 平均查找长度
                • |_log2(n)_|+1
              • 不同的分割方式
                • 斐波那契查找
                • 插值查找
                  • 类似于线性的把待查找key映射到存储位置上，适用于线性均匀分布情况
        • 不等概率查找
          • *静态树表
            • 寻找查找过程判定树的最优情况
            • 静态最优查找树
              • 有别于Huffman树 Huffman树是为了两两之间编码不重叠，从而浪费了许多结点空间 而静态最优查找树的结点均为表中元素
              • 构造时花费的时间代价太大
            • 次优查找树
              • 希望每个作为根的结点的左右子树的带权路径长度和近似均衡
      • 索引顺序表
        • 由索引表和存储表组成 存储表分块存储，块内无序块间有序
        • 通过索引表实现块间的二分查找，定位到块； 再通过块内的顺序查找，定位到元素
  • 动态查找表
    • 表结构本身就是在查找过程中动态生成的，即查找失败时则插入。
    • 二叉链表存储
      • 二叉排序树
        • 定义
          • 从定义可以看出，二叉排序树具体啥样，与它的构造过程中各结点的插入顺序有关，如p227
          • 若左子树非空，则其上所有节点的值均小于根节点的值
          • 若右子树非空，则其上所有结点的值均大于根节点的值
          • 左右子树均为二叉排序树
          • 很有意思，先序遍历得到非递减有序序列，后序遍历得到非递增有序序列
        • 操作
          • 查找
            • 类似于二叉排序树，逐层与根比较，决定向左走还是向右走
          • 插入（创建）
            • 如比较后应该向左走，但左边是空，说明没找到，就在那个位置插入
          • 删除，不改变特性
            • 分情况讨论（为了减少操作） 设待删除结点为*p，它的双亲为*f，不妨设*p为*f的左孩子
              • 如果是右孩子，则后面的操作也要相应变化
              • *p为叶子节点
                • 直接删去
              • *p只有一棵子树
                • 令*p的子树直接成为双亲*f的子树
              • *p有两棵子树，详见p230
                • 利用*p在关键字序列中的直接前驱*s1或直接后继*s2
                  • 因为容易知道，它们必然不可能同时有两棵子树
                  • 令*p的左子树代替*p的位置，成为*f的左子树; 令*p的右子树成为*s1的右子树;
                  • 令*s1替代*p（元素覆盖），然后在二叉排序树中删去原先的*s1
          • 效率分析
            • 性能
              • 树高
                • 与创建时的插入顺序有关
      • 平衡二叉（排序）树
        • 对二叉排序树的优化，减少查找失败的平均比较次数
        • 定义
          • 若非空则有后面性质
            • 左子树和右子树都为平衡二叉树
            • 左右子树的深度之差的绝对值不超过1
          • 平衡因子：左子树深度-右子树深度
        • 操作
          • 查找：与二叉排序树相同
          • 效率分析
            • O( log2(n) )
          • 二叉排序树的平衡化
            • 每次插入都及时平衡化，则因插入而失衡的情况必然只有后面四种； 假设a是离插入结点最近，且平衡因子绝对值超过1的祖先节点；
            • 单向
              • 单向右旋
              • 单向左旋
            • 双向
              • 先左后右
              • 先右后左
    • 多叉链表存储
      • B-树
        • 查找失败时比较次数相同
        • m阶B-树定义
          • 有点类似多叉的排序树，指针指示的子树，数值夹在左右两边存储的数值之间。
          • 每个节点至多有m棵子树
          • 若不为叶子节点，则至少有两棵子树
          • 除了根节点外的非终端节点至少有m/2取上整棵子树
          • 叶子节点都出现在树的同一层上
        • 操作
          • 查找分析：分析B-树的深度
            • 从定义
          • 插入
            • 若多则向上分裂
          • 删除
            • 无影响
            • 临近兄弟可借，换下双亲中的一个
            • 临近兄弟借不了，则合并，向上分裂的逆过程
          • 一般仅考2-3树，即三阶B-树
            • 每个结点至少有两棵子树，至多有三棵子树，也就意味着至少存储一个数，至多存储两个数
            • 从例子中学习，如何分裂、合并
              • 详见课本p242~p245，以及作业题9.14、9.15
  • 哈希表
    • 希望尽可能减少与关键字进行比较的次数
    • 定义
      • 哈希函数：存储位置和关键字之间的一一对应关系f
      • 冲突：k1!=k2,f(k1)=f(k2)
        • 处理冲突的方法g
      • Hash表：经过冲突处理后，把一组数据的关键字key转化为g( f( key ) )， 作为表中相应key的元素的存储位置
      • 散列：上述映射的过程
      • 哈希地址：上述方法最终得到的g
    • 操作
      • 构造哈希函数
        • 直接定址：线性函数
        • 平方取中
        • 折叠：将关键字分割成位数相同的几部分，取这几部分的叠加和（舍去进位）
        • 除留余数：取模
        • 随机数
      • 处理冲突
        • 开放定址法：在原地址基础上加一个逐次变化的偏移量
          • 线性探测再散列：1，2，3……
          • 二次探测再散列：1²，-1²，2²，……
          • 伪随机数
        • 其它
      • 查找
        • 给定key值，求得哈希地址，定位到哈希表中该地址的元素
          • 该位置上没有记录
            • 查找不成功
          • 有记录，比较key和该记录的关键字
            • 相等，查找成功
            • 不相等，根据造表时设定的处理冲突方法，寻找下一地址
• 有意思的是，此时左右也是平衡的
• 记不住啊啊啊！
  • 看课本p234~p238，其实只需要学两种，也没必要记住
• 利用二叉树来表示查找过程