当前位置：首页 > article >正文

中级软考笔记-基础知识-3-数据结构

article 2025/2/23 18:50:16

数据结构
- 数组
  - 顺序存储
  - 分类
    - 静态数组
    - 动态数组
- 矩阵
- 广义表
  - 链式存储结构
- 线性表
  - 定义
    - n个元素的有限序列
  - 存储结构
    - 顺序存储
      - 地址连续的存储单元依次存储
      - 逻辑关系相邻的两个元素在物理地址上也相邻
      - 优点：可以随机存取表中元素
      - 缺点：插入和删除操作需要移动大量的元素
      - 线性表插入元素，等概率下平均移动元素的次数 Einsert = n/2
      - 线性表删除元素，等概率下平均移动元素的次数 Edelete = (n-1)/2
      - 时间复杂度O(1)
    - 链式存储
      - 优点：插入和删除操作不需要移动元素
      - 缺点：不能进行数据元素的随机访问
      - 链表结构
        单向链表
        时间复杂度O(n)
        
        插入
        
        删除
        
        双向链表
        插入
        
        删除
        
        循环链表
- 队列
  - 先进先出FIFO（First In First Out）
  - 允许一端插入（队尾），一端删除元素（队头）
  - 存储结构
    - 顺序存储
    - 链式存储
  - 应用
    - OS中处理打印任务的打印队列、离散事件的计算机模拟
- 栈
  - 先进后出FILO（First In Last Out）
  - 应用
    - 表达式求值、括号匹配、计算机语言的实现以及递归过程转变为非递归过程
  - 存储结构
    - 顺序存储
    - 链式存储
- 串
  - 特殊的线性表，其数据元素为字符
  - 基本概念
    - 空串：长度为0的串，不包含任何字符
    - 空格串：由一个或多个空格组成的串
    - 子串：串中任意长度的连续字符构成的序列
    - 串相等：两个串长度相等且对应位置上的字符也相同
    - 串比较：字符的ASCII码值作为依据
  - 存储结构
    - 静态存储：定长存储结构
    - 链式存储：块链
  - 串的模式匹配/字串的定位操作
    - 字串也称为模式串
    - 算法
      - 朴素的模式匹配算法
        最好情况时间复杂度O(n+m)
        
        最坏情况时间复杂度O(n*m)
      - 改进的模式匹配算法/KMP算法
        时间复杂度O(n+m)
- 树
  - 基本概念
    - 节点的度
      - 一个节点的子树（子节点）个数
    - 节点的层次
      - 根为第一层，根的孩子为第二层，以此类推
    - 树的高度（深度）
      - 一棵树的最大层次
    - 树的度
      - 一棵树所有子节点的度中最大值为树的度
    - 树的遍历
      - 转换为完全二叉树
        先根遍历
        二叉树的先序遍历
        
        后根遍历
        二叉树的中序遍历
  - 类型
    - 二叉树
      - 二叉树性质
        空树或由左右子树组成的树
        
        具有递归性质
        
        节点的最大度为2
        
        第i（i >= 1）层上的节点数目最多为2^(i-1)个
        
        深度为k的二叉树最多有2^k - 1（k>=1）个节点
        
        任意一棵二叉树中，若终端节点数为n0，度为2的节点数为n2，则n0=n2 + 1
        
        具有n个节点的完全二叉树的深度为[log2 n] + 1
      - 存储结构
        顺序存储
        一般二叉树不适用，但用于完全二叉树简单且节省空间
        
        链式存储
      - 二叉树的遍历
        n个节点的二叉树，遍历算法的时间复杂度都是 O(n)
        
        n个节点且深度为n的二叉树，遍历算法空间复杂度为 O(n)
      - 二叉树分类
        满二叉树
        所有节点要么是叶子节点，要么拥有两个子节点
        
        完全二叉树
        如果一棵二叉树的层数为 h，且前 h-1 层的节点数都达到最大值，第 h 层的节点从左到右依次排列，中间没有空缺，则称这棵树为完全二叉树
        
        除最后一层，其他层的节点都是满的
        
        完美二叉树
        二叉树的所有内部节点都有两个子节点，并且所有叶子节点都在同一层
        
        特点
        所有叶子节点都在同一层。
        
        每个节点要么是叶子节点，要么拥有两个子节点。
        
        完美二叉树一定是满二叉树，但满二叉树不一定是完美二叉树。
        
        平衡二叉树
        二叉树中任意节点的左右子树的高度差不超过 1
        
        常见的平衡二叉树有 AVL 树、红黑树等
        
        退化二叉树
        一棵二叉树的每个节点最多只有一个子节点
        
        二叉排序树/二叉查找树/二叉搜索树
        性质
        若左子树不空，则左子树上所有节点的值均小于它的根节点的值
        
        若右子树不空，则右子树上所有节点的值均大于它的根节点的值
        
        左、右子树也分别为二叉排序树
      - 二叉树的应用
        最优二叉树/霍夫曼树
        带权路径长度最短
    - 查找树
    - 平衡树
    - 线索树
      - 线索二叉树
        存储结构
        链表
        
        含有n+1个空指针域
    - 堆
- 图
  - 定义
  - 存储
  - 操作
  - 遍历
    - 深度优先DFS
    - 广度优先BFS
- 哈希Hash
  - 存储地址计算
  - 冲突处理
算法时间复杂度
- O(1) < O(log2 n) < O(n)< O(nlog2 n) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)
排序