【数据结构】数组与特殊矩阵

数据结构的学习中数组与特殊矩阵是基础且核心的内容。它们不仅是程序设计中最常用的线性结构更是处理复杂矩阵运算的基础。本文将结合解析与真题带你彻底搞懂数组的存储方式和特殊矩阵的压缩存储技巧。一、一维数组与二维数组存储是基础1. 一维数组的存储一维数组是最基础的线性结构在内存中连续存储每个元素占用相同大小的存储单元。int main() { int a[] {16,47,89,42,38}; }地址101105109113117元素1647894238下标a[0]a[1]a[2]a[3]a[4]地址计算若基地址为LOC(a[0])每个元素占k字节则a[i]的地址为LOC(a[i])LOC(a[0])i×k2. 二维数组的存储行优先 vs 列优先二维数组在内存中本质是一维线性存储有两种常见的存储顺序1行优先存储C 语言默认地址101105109113117121元素123456下标a[0][0]a[0][1]a[0][2]a[1][0]a[1][1]a[1][2]地址公式m行n列LOC(a[i][j])LOC(a[0][0])(i×nj)×k2列优先存储Fortran、Matlab 等语言先存储第 0 列再存储第 1 列以此类推。地址101105109113117121元素142536下标a[0][0]a[1][0]a[0][1]a[1][1]a[0][2]a[1][2]地址公式m行n列LOC(a[i][j])LOC(a[0][0])(j×mi)×k3. 真题实战二维数组地址计算步骤解析设数组为m行n列行优先地址公式LOC(A[i][j])100i×nj代入A[3][3] 2201003n3220⟹3n117⟹n39计算A[5][5]LOC(A[5][5])1005×3951001955300答案B二、特殊矩阵压缩存储是关键特殊矩阵如对称矩阵、三角矩阵、三对角矩阵、稀疏矩阵存在大量重复或零元素为了节省空间需要对其进行压缩存储。1. 对称矩阵对称矩阵满足a[i][j] a[j][i]因此只需存储上三角或下三角部分。以n×n对称矩阵为例下三角部分i ≥ j共有n(n1)/2个元素。存储映射行优先存储下三角元素到一维数组B中k2i(i1)​j(i≥j)若i j则a[i][j] a[j][i]直接映射到k j(j1)/2 i。真题实战步骤解析上三角元素行优先存储先存第 1 行j1~12再存第 2 行j2~12……前 5 行的元素总数∑k15​(12−k1)1211109850第 6 行中m_{6,6}是第 1 个元素因此下标为50 1 - 1 50C 语言下标从 0 开始。答案A. 502. 三角矩阵上三角矩阵主对角线以下i j的元素均为 0。下三角矩阵主对角线以上i j的元素均为 0。存储方式与对称矩阵类似只存储非零部分零元素不再重复存储。数组从 0 开始计数题目条件12×12 对称矩阵只存上三角部分含对角线满足 1≤i≤j≤12按行优先存入 C 语言一维数组数组下标从 0 开始目标元素m6,6​第 6 行、第 6 列步骤 1计算前 5 行i1 到 i5的元素总数上三角第i行的元素个数为12−i1从第i列到第 12 列第 1 行12−1112 个第 2 行12−2111 个第 3 行12−3110 个第 4 行12−419 个第 5 行12−518 个前 5 行总元素数1211109850步骤 2确定m6,6​的下标C 语言数组下标从 0 开始所以前 5 行的元素下标范围是0∼49共 50 个元素第 6 行的第一个元素是m6,6​它的下标就是前 5 行的元素总数50所以m6,6​在数组N中的下标是 50答案A. 50步骤 1明确 “列优先” 规则对称矩阵上三角部分满足 1≤i≤j≤10按列优先存储时先存第 1 列的上三角元素再存第 2 列依此类推。对于第 j 列上三角元素的行号 i 范围是 1≤i≤j共有 j 个元素。步骤 2计算前 1 列j1的元素总数第 1 列j1的上三角元素只有 m1,1​共1个。步骤 3计算第 2 列中 m7,2​ 的位置注意m7,2​ 属于上三角部分根据对称矩阵性质 m7,2​m2,7​所以实际存储的是 m2,7​对应列 j7行 i2。先计算前 6 列j1 到 j6的元素总数12345621第 7 列中m2,7​ 是第 2 个元素i1,2所以在数组中的下标为212−122C 语言数组下标从 0 开始所以需要减 1答案C. 223. 三对角矩阵三对角矩阵是指除了主对角线及其上下两条对角线外其余元素均为 0 的矩阵。对于n×n三对角矩阵非零元素总数为3n - 2可按行优先压缩存储到一维数组中。地址映射公式k2ij(∣i−j∣≤1)步骤 1理解三对角矩阵的结构三对角矩阵中只有当 ∣i−j∣≤1 时元素 mi,j​ 非零或需要存储。行优先存储时每行最多有 3 个元素第 1 行j1,22 个元素第 2~99 行ji−1,i,i13 个元素第 100 行j99,1002 个元素步骤 2计算前 29 行的元素总数第 1 行2 个元素第 2~29 行共 29−128 行每行 3 个元素前 29 行总元素数228×328486步骤 3计算 m30,30​ 在第 30 行的位置第 30 行的元素依次是 m30,29​、m30,30​、m30,31​。m30,30​ 是第 30 行的第 2 个元素。所以它在数组中的下标为862−187数组下标从 0 开始所以减 1答案B. 874. 稀疏矩阵稀疏矩阵是指零元素个数远多于非零元素个数的矩阵。常用的压缩存储方式有1三元组存储用三元组(i, j, value)记录每个非零元素的行号、列号和值。i j value 0 1 3 2 0 1 3 3 72十字链表将每行和每列的非零元素分别用链表连接便于快速访问行和列的元素。三、总结与思考结构类型存储特点核心公式 / 方法一维数组连续线性存储LOC(a[i]) LOC(a[0]) i*k二维数组行优先按行展开存储LOC(a[i][j]) LOC(a[0][0]) (i*n j)*k二维数组列优先按列展开存储LOC(a[i][j]) LOC(a[0][0]) (j*m i)*k对称矩阵只存上 / 下三角部分k i(i1)/2 j下三角三角矩阵只存非零部分同对称矩阵零元素不存储三对角矩阵只存三条对角线元素k 2i j稀疏矩阵三元组 / 十字链表存储仅存储非零元素数组与特殊矩阵的存储本质是空间与时间的权衡通过压缩存储减少空间占用同时保证高效的访问效率。在实际开发中理解这些存储方式是优化算法和处理大规模数据的基础。