前言

“数组、矩阵与广义表”学习提纲。

数组

多维数组的存储方式

行优先
列优先

矩阵

常见的特殊矩阵

矩阵分区：上三角区，主对角线，下三角区

对称矩阵
三角矩阵：上三角矩阵，下三角矩阵
对角矩阵/带状矩阵：三对角矩阵

对称矩阵的压缩存储计算

数组表示：a[n][n]。其中a为数组名称，n为行和列数
元素表示：a[i][j]。其中i为行下标，j为列下标

存储元素数量：(1+n)×n÷2

存储下标（从0开始；行下标和列下标从1开始，行优先，存下三角区）：

i×(i-1)÷2+j-1，i>=j（下三角区和主对角线元素）
j×(j-1)÷2+i-1，i<j（上三角区元素）

注意：

关注：行下标和列下标从0或1开始，存储下标从0或1开始，依据行或列优先存储。对称矩阵还要多关注存储在上或下三角区
行下标和列下标从0开始相比从1开始需要重新推导公式
存储下标从1开始相比从0开始需要多+1
选择题可以使用特殊值代入法判断

三角矩阵的压缩存储计算

数组表示：a[n][n]。其中a为数组名称，n为行和列数
元素表示：a[i][j]。其中i为行下标，j为列下标

存储元素数量：(1+n)×n÷2+1

下三角矩阵的存储下标（从0开始；行下标和列下标从1开始，行优先）：

i×(i-1)÷2+j-1，i>=j（下三角区和主对角线元素）
(1+n)×n÷2，i<j（上三角区元素）

上三角矩阵的存储下标（从0开始；行下标和列下标从1开始，行优先）：

(2×n-i+2)×(i-1)÷2+(j-i)，i<=j（上三角区和主对角线元素）
(1+n)×n÷2，i>j（下三角区元素）

下三角矩阵的存储下标（从0开始；行下标和列下标从1开始，列优先）：

(2×n-j+2)×(j-1)÷2+(i-j)，i>=j（下三角区和主对角线元素）
(1+n)×n÷2，i<j（上三角区元素）

上三角矩阵的存储下标（从0开始；行下标和列下标从1开始，列优先）：

j×(j-1)÷2+i-1，i<=j（上三角区和主对角线元素）
(1+n)×n÷2，i>j（下三角区元素）

三对角矩阵的压缩存储计算

数组表示：a[n][n]。其中a为数组名称，n为行和列数
元素表示：a[i][j]。其中i为行下标，j为列下标

存储下标（从0开始；行下标和列下标从1开始）：2×i+j-3

由存储下标得行下标（从1开始）和列下标（从1开始）（假设存储下标为k）：

i=[(k+1)÷3+1]下取整
j=k-2i+3

稀疏矩阵的压缩存储方式

顺序存储：

三元组表示法：结构体或二维数组，行数为非零元素数量，列数为3：值，行下标，列下标
伪地址表示法：二维数组，行数为非零元素数量，列数为2：值，伪地址/相对位置

伪地址表示法的相关存储计算：

数组表示：a[m][n]。其中a为数组名称，m为行数，n为列数
元素表示：a[i][j]。其中i为行下标，j为列下标
伪地址/相对位置（从0开始，行优先）：(i-1)×n+j

链式存储：

邻接表表示法：一行为一个单链表，头结点有行下标和指针，其他结点有值、列下标和指针
十字链表表示法：一行为一个单链表，一列为一个单链表，单链表纵横链接。结点有5个分量：值，行下标，列下标，指向下方结点的指针，指向右方结点的指针

广义表

广义表的属性

长度：最上层元素的数量
深度：展开子表后，括号的最大层数
表头：表非空时，第一个元素
表尾：表非空时，除第一个元素的其他元素

广义表的存储方式

头尾链表（类似无头结点的单链表）：原子结点：标记，值；广义表结点：标记，头指针，尾指针
扩展线性表链表（类似有头结点的单链表）：原子结点：标记，值，尾指针；广义表结点：标记，头指针，尾指针

总结

“数组、矩阵与广义表”学习提纲。

参考资料

《2023版数据结构高分笔记》主编：率辉
《2023年计算机组成原理考研复习指导》组编：王道论坛

作者的话

感谢参考资料的作者/博主
作者：夜悊
如果文章对你有帮助，请点个赞或加个粉丝吧，你的支持就是作者的动力~
文章在描述时有疑惑的地方，请留言，定会一一耐心讨论、解答
文章在认识上有错误的地方, 敬请批评指正
望读者们都能有所收获