datetime:2022-04-09 17:46

author:nzb

数据结构与算法

绪论

• 基本概念

  • 数据

  • 数据元素、数据项

  • 数据对象、数据结构

  • 数据类型、抽象数据类型（ADT）

• 数据结构三要素

  • 逻辑结构

    • 集合

    • 线性结构

    • 树形结构

    • 图状结构（网状结构）

  • 物理结构（存储结构）

    • 顺序存储

      物理内存中是连续的

    • 非顺序存储

      物理内存中是分散的

      • 链式存储

      • 索引存储

      • 散列存储

  • 数据的运算

• 学习建议

  • 概念多，比较无聊。抓大放小，重要的是形成框架，不必纠结细节概念。

特殊矩阵压缩存储

• 对称矩阵

  • 特点

    对方阵中的任意一个元素，有 a(i,j) = a(j,i)

  • 压缩

    只存储主对角线 + 下三角区（或主对角线 + 上三角区）

• 三角矩阵

  • 特点

    上三角区全为常数（下三角矩阵）；或下三角区全为常数（上三角矩阵）

  • 压缩

    按行优先/列优先规则依次存储非 常量区域，并在最后一个位置存放常量 c

• 三对角矩阵（带状矩阵）

  • 特点

    当 |i - j| > 1时，有 a (i,j) = 0（1 <= i, j<=n）

  • 压缩

    按行优先/列优先规则依次存储带状区域

• 稀疏矩阵

  • 特点

    非零元素个数远小于零元素个数

  • 压缩

    只存储非零元素

    • 顺序存储

      顺序存储三元组（行，列，值）

    • 链式存储

      十字链表法