数组和广义表

复习定位

数组是最简单的数据结构——连续内存存放同类型元素。多维数组在内存中实际上是线性的——按行优先或列优先展开。特殊矩阵(对称/三角/稀疏)在计算机中采用压缩存储节省内存。广义表是数组的推广——元素可以是单个数据元素也可以是另一个广义表(链表嵌套)——LISP语言的核心数据结构。

数组的存储

一维数组A[i]的地址 = 基地址 + i × sizeof(ElemType)。

二维数组A[m][n]——在内存中行优先(一行存完再存下一行——C/C++/Java使用行优先)或列优先(FORTRAN/Julia使用列优先)：

• 行优先：A[i][j]的地址= 基地址 + (i×n + j)×元素大小。
• 列优先：A[i][j]的地址= 基地址 + (j×m + i)×元素大小。

特殊矩阵的压缩存储

对称矩阵——A[i][j]==A[j][i]——只存下三角(或上三角)元素——将二维下标(i,j)映射到一维数组下标k。下三角行优先映射：k = i×(i+1)/2 + j(i≥j)。

三角矩阵——下三角矩阵(上三角全为0或常数)类似对称矩阵的压缩。

对角矩阵——非零元素集中在主对角线附近(如三对角矩阵非零元素在主对角线及相邻两条对角线上)——采用按对角线存储的方法将三对角线上的元素压缩到一维数组。

稀疏矩阵——非零元素很少——用二维数组存所有元素浪费大量空间。压缩存储只存非零元素及其行列索引——称为三元组表：(row, col, value)。三元组按行序排列——提供转置、加法等操作。

稀疏矩阵的另一种存储结构：十字链表(Orthogonal List)——每个非零元素用一个结点表示——结点包含行号、列号、值、指向同一行下一非零元素的指针、指向同一列下一非零元素的指针。在矩阵非零元的位置频繁变化时(如作加法/乘法)——十字链表在链表中插入/删除结点更方便。

广义表

广义表(Generalized List)是线性表的推广——一个表的元素可以是原子(单个数据)或另一个子表。

广义表的长度——直接元素个数；深度——嵌套的最大层数。

A = ()                 // 空表——长度为0
B = (a, b)            // 长度为2——元素是原子
C = (a, (b, c), d)    // 长度为3——第二个元素是子表
D = (A, B, C)         // 长度为3——元素全是子表

广义表在LISP/Proglog中以S-表达式为处理核心——用于表示树形结构和编程语言的语法树。广义表可以用链式结构存储(每个结点区分是原子还是子表——用标志位tag标识)。

复习检查

1. 二维数组A[10][20]按行优先存储——A[0][0]的地址为1000——每个元素占4字节——A[3][7]的地址和值的大小——利用公式1000+(3×20+7)×4=1268——推出正确的行偏移乘以列宽的句式。

2. 对称矩阵压缩至一维数组——下三角按行优先——当i>=j时映射公式k=i(i+1)/2+j并i<j时取A[j][i]的映射——为什么可以节省近一半空间？

3. 稀疏矩阵的三元组表示——三个字段(row,col,value)——假设只存非零元素——与二维数组相比存储空间减少的量级取决于稀疏度(非零元比例)——稀疏度5%时三元组占用大约是二维数组的3×5%=15%但加上整数的字节长度空间可不比原来的二维数组少在稀疏度太低(如80%元素非零)时反而空间更多。

4. 十字链表的结点有哪些属性——row/col/value/right(同行的下一非零元素指针)/down(同列的下一非零元素指针)——列指针链和行指针链分别用一个头结点数组维护。

5. 广义表的深度与长度的区别——长度是直接元素个数——深度是括号最大嵌套层数。例如C=(a,(b,c),d)长度为3——深度为2。