一、数组的存储与地址计算
1. 数组的存储方式
- 数组的顺序存储有两种：按行序存储与按列序存储。
- 无论哪种方式，数组元素在内存中都是连续存放的。
2. 一维数组地址计算
若首地址为 LOC(a₁)，每个元素占 L 个存储单元，则第 i 个元素的地址（从1计数）：
LOC(aᵢ) = LOC(a₁) + (i - 1) × L
示例（第9题）：首地址100，元素长度2，第5个元素地址 = 100 + (5-1)×2 = 108。
示例（第18题）：首地址2000，元素长度3，第9个元素地址 = 2000 + (9-1)×3 = 2024。
3. 二维数组地址计算（通用公式）
设二维数组 a[m][n]，下标范围行 0~m-1 或 1~m，列 0~n-1 或 1~n，首地址为 LOC，每个元素占 L 个单元。
关键：先明确下标起点和存储方式（行序/列序），再套公式。
(1) 按行序优先（行主序）存储
- 先存第0行（或第1行）全部元素，再存下一行。
- 若下标从0开始：
LOC(a[i][j]) = LOC(a[0][0]) + (i × n + j) × L - 若下标从1开始（无第0行/列）：
LOC(a[i][j]) = LOC(a[1][1]) + [(i-1) × 列数 + (j-1)] × L
(2) 按列序优先（列主序）存储
- 先存第0列（或第1列）全部元素，再存下一列。
- 若下标从0开始：
LOC(a[i][j]) = LOC(a[0][0]) + (j × m + i) × L - 若下标从1开始：
LOC(a[i][j]) = LOC(a[1][1]) + [(j-1) × 行数 + (i-1)] × L
通用解法三步走：
- 确认下标起止（从0还是从1）和元素大小L。
- 确认存储方式（行序/列序）。
- 计算目标元素前面有多少个元素，乘以L，加上基地址。
示例1（第6题）：a[6][10]，每个4字节，a[0][0]地址860，行优先，求a[3][5]地址。
- 行下标0
5，列09。行优先：(i×列数 + j)×L a[3][5]前面有3×10 + 5 = 35个元素。- 地址 = 860 + 35×4 = 860 + 140 = 1000。
示例2（第8题）：a[1…60, 1…70]，列序为主序，基地址10000，每个2字节，求a[32][58]地址。
- 下标从1开始，行数60，列数70。列优先：前面有
(j-1)×行数 + (i-1)个元素。 - 元素前个数 =
(58-1)×60 + (32-1) = 57×60 + 31 = 3420 + 31 = 3451。 - 地址 = 10000 + 3451×2 = 10000 + 6902 = 16902。
示例3（第13题）：a[1…50][1…80]，基地址2000，每个2字节。
- 行优先求
a[45][68]：前面有(45-1)×80 + (68-1) = 44×80 + 67 = 3520+67=3587。地址 = 2000+3587×2=9174。 - 列优先求
a[45][68]：前面有(68-1)×50 + (45-1) = 67×50+44 = 3350+44=3394。地址 = 2000+3394×2=8788。
示例4（第16题）：A[1…6][0…7]，每个6字节，A[1][0]地址0，求数组体积、最后一个元素地址、A[2][4]行存储地址、A[5][7]列存储地址。
- 行数=6，列数=8（0~7共8列），元素总数=6×8=48，体积=48×6=288。
- 最后一个元素按行序是
A[6][7]，前面共47个元素（0号是第一个），首地址=0+47×6=282。 A[2][4]行优先：前面有(2-1)×8 + (4-0) = 1×8+4=12个元素（注意A[1][0]是第一个，前面0个），地址=0+12×6=72。A[5][7]列优先：列7前面有列0~6共7列，每列6个元素，再加本列前4个元素（A[1][7]到A[4][7]），总数=7×6+4=46，地址=0+46×6=276。
二、特殊矩阵的压缩存储
1. 对称矩阵压缩存储
- 仅存下三角（或上三角）元素，占用空间
n(n+1)/2。 - 下三角按行序存储到一维数组 B（下标从1或0开始），元素
aᵢ,ⱼ（i ≥ j）的位置：- 若B下标从1开始：
k = i(i-1)/2 + j。 - 若B下标从0开始：
k = i(i-1)/2 + j - 1。
- 若B下标从1开始：
示例（第5题）：下三角按行序存放在 B[1, n(n-1)/2] 中，但题目描述有“对下三角部分中任一元素 ai,j (i≤j)”——此处 i≤j 指上三角元素，利用对称性映射到下三角。若实际存储的是下三角且按行序，对于 aᵢ,ⱼ（i ≤ j），取 aⱼ,ᵢ，位置为 j(j-1)/2 + i。但选项C i(i-1)/2+j 是标准下三角公式（i≥j）。根据给出的答案C，可判断题目实际是按行存储下三角且对 i≥j 使用，括号条件可能描述有误，实际应取i≥j。
通用公式（下三角行序，数组下标从1开始）：
- i ≥ j 时，
aᵢ,ⱼ对应B[ i(i-1)/2 + j ]。
2. 稀疏矩阵
- 非零元素很少且分布无规律。
- 压缩存储的目的是节省存储空间。
- 常用存储方法：三元组表、十字链表等。
三、广义表
1. 广义表的定义与性质
- 广义表是线性表的推广，元素可以是原子（单个数据元素），也可以是子表（另一个广义表）。
- 与线性表的最大区别：广义表允许使用子表作为元素，即可以嵌套，可以递归。
- 广义表的元素类型可以不同。
- 表头：广义表的第一个元素（可以是原子或子表）。
- 表尾：除去表头后剩余元素组成的广义表（一定是广义表，即使只有一个元素也要加括号）。
2. 表头与表尾运算（核心）
记 Head(L) 取第一个元素，Tail(L) 取除第一个元素外剩下的元素构成的广义表。
必须牢记：
Tail的结果永远是广义表（带括号），即使只剩一个元素。Head的结果可能是原子，也可能是广义表。
示例1（第12题）：广义表 (a,b,c,d,e) 的表尾是去掉a后的剩余部分：(b,c,d,e)。注意不是 c 或 (c)。
示例2（第10题）：((a,b),c,d) 表头是 (a,b)，表尾是 (c,d)。
示例3（第14题）：((a),((b),(c,d,e))) 表头是第一个元素 (a)，表尾是去掉表头后的 (((b),(c,d,e)))。
示例4（第15题）：(a,b,c) 表尾是 (b,c)。
3. Head与Tail复合运算（通用解法）
方法：从最内层括号或函数开始，逐层向外推导。每一步明确结果是原子还是广义表，是否带括号。
示例5（第2题）：广义表 A=(a,b,(c,d),(e,(f,g)))，求 Head(Tail(Head(Tail(Tail(A)))))。
Tail(A)=(b,(c,d),(e,(f,g)))（去掉a）Tail(Tail(A))=((c,d),(e,(f,g)))（去掉b）Head(Tail(Tail(A)))=(c,d)（取第一个元素）Tail(Head(...))=Tail((c,d))=(d)（去掉c后的广义表）Head(...)=Head((d))=d（取原子d）
示例6（第1题）：L=((x,y,z), a, (u,t,w))，取出原子t。
- 先要定位到第三个元素
(u,t,w)：Tail(Tail(L))=((u,t,w))。 - 取表头：
Head(...)=(u,t,w)。 - 再取表尾去掉u：
Tail(...)=(t,w)。 - 再取表头：
Head(...)=t。 - 完整运算：
Head(Tail(Head(Tail(Tail(L)))))。
示例7（第4题）：LS=((a,b,c),(d,e,f))，取出原子e。
Tail(LS)=((d,e,f))Head(...)=(d,e,f)Tail(...)=(e,f)Head(...)=e
- 组合：
Head(Tail(Head(Tail(LS))))。
示例8（第17题）：A=(a,b,(c,d),(e,(f,g)))，求 GetHead(GetTail(GetHead(GetTail(GetTail(A)))))。
Tail(A)=(b,(c,d),(e,(f,g)))Tail(...)=((c,d),(e,(f,g)))Head(...)=(c,d)Tail(...)=(d)Head(...)=d
四、易混概念辨析
| 概念 | 要点 |
|---|---|
| 数组存储 | 行序/列序两种，地址计算注意下标起点（0或1） |
| 对称矩阵压缩 | 只存下三角或上三角，元素位置 i(i-1)/2+j（行序，i≥j） |
| 稀疏矩阵压缩目的 | 节省存储空间，非零元素很少且分布无规律 |
| 广义表 vs 线性表 | 广义表元素可为子表（可嵌套、递归），线性表元素只能是原子 |
| 表头 vs 表尾 | 表头是第一个元素（原子或子表）；表尾一定是广义表 |
| 广义表递归 | 广义表可以递归定义，即元素可以是自身 |
五、知识速记卡
- 数组地址：行优先
(i×列数 + j)×L，列优先(j×行数 + i)×L，注意下标起始。 - 对称矩阵：下三角行序
k = i(i-1)/2 + j（i≥j，下标从1开始）。 - 稀疏矩阵：压缩存储为省空间。
- 广义表核心：
Head取第一个，Tail取剩余并永远带括号。 - 复合运算：从内向外，逐层判断是原子还是子表，注意括号的保留与去除。
- 表尾一定是表：
(a,b,c)的表尾是(b,c)，不是b或c。