4.数组与串-东南大学计算机科学与工程学院.ppt

第四章 数组、串与广义表 东南大学计算机学院 方效林 本课件借鉴了清华大学殷人昆老师 和哈尔滨工业大学张岩老师的课件 本章主要内容 多维数组的概念与存储 特殊矩阵 稀疏矩阵 字符串 * 多维数组的概念与存储 多维数组是一维数组的扩展 * 二维数组 三维数组 多维数组的概念与存储 多维数组存储在连续的空间中 存储地址计算方法（假设数组首地址为a ，元素大小为 l） 一维数组：a[m1] 二维数组：a[m1][m2] 三维数组：a[m1][m2] [m3] n维数组： a[m1][m2] …[mn] * Loc i a + i*l Loc i, j a + i*m2 + j *l Loc i, j, k a + i*m2*m3 + j*m3 + k *l 特殊矩阵 二维数组也称为矩阵 特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。 对称矩阵 三对角矩阵 利用特殊矩阵的性质，节省存储空间 * 对称矩阵 三对角矩阵 特殊矩阵 对称矩阵的压缩存储 设有一个 n?n 的矩阵 A。如果在在矩阵中，aij aji，则此矩阵是对称矩阵。 只保存对称矩阵的对角线和对角线以上 或以下 的元素，则称此为对称矩阵的压缩存储 压缩存储方式：用一维数组存储 * 特殊矩阵 对称矩阵的压缩存储 下三角阵存储： 用一维数组B存储对称矩阵A中对角线及对角线以下的元素 矩阵A中元素a[i][j]对应一维数组B中的下标为 * i+1 *i/2 + j, i ≥ j Loc i, j j+1 *j/2 + i, i j a00 a10 a11 a20 a21 a22 a30 a31 a32 …… an-1n-1 0 1 2 3 4 5 6 7 8 n n+1 /2-1 B 特殊矩阵 对称矩阵的压缩存储 上三角阵存储： 用一维数组B存储对称矩阵A中对角线及对角线以上的元素 矩阵A中元素a[i][j]对应一维数组B中的下标为 * 2n - i + 1 *i/2 + j-i, i ≤ j 2n - j - 1 *j/2 + i, i j Loc i, j a00 a01 a02 … a0n-1 a11 a12 … a1n-1 a22 … an-1n-1 0 1 2 n-1 n n+1 2n-2 2n-1 n n+1 /2-1 B 稀疏矩阵 设矩阵 A 中有 s 个非零元素，若 s 远远小于矩阵元素的总数（即s m×n），则称 A 为稀疏矩阵。 稀疏因子： δ s/ m×n 一般δ ≤ 0.05可称为稀疏 * 稀疏矩阵表示 稀疏矩阵 用三元组 i, j, aij 表示稀疏矩阵一个元素aij * 三元组表示 稀疏矩阵表示 稀疏矩阵 三元组表示的稀疏矩阵转置的直观方法 按列从小到大排序 行列交换 * 稀疏矩阵 三元组表示的稀疏矩阵转置的扫描方法 假设A有Cols列，则扫描Cols趟 第k趟扫描在表中找列号为k的三元组，取出，交换行列号 * 扫描列号为0的三元组 扫描列号为1的三元组 扫描列号为2的三元组 扫描列号为3的三元组 扫描列号为4的三元组 扫描列号为5的三元组 扫描列号为6的三元组 6 5 -52 5 3 -17 4 4 19 3 5 -8 3 2 -6 3 1 -11 2 0 2 1 4 9 0 1 3 稀疏矩阵 三元组表示的稀疏矩阵转置的快速方法 统计各列非零数rowSize 扫描三元组表 计算各列在转置三元组中的索引位置rowStart 扫描三元组表，放入相应索引位置，相应索引加1 rowSize 1 1 1 3 1 1 1 rowStart 0 1 2 3 6 7 8 6 5 -52 5 3 -17 4 4 19 3 5 -8 3 2 -6 3 1 -11 2 0 2 1 4 9 0 1 3 4 5 3 2 1 6 7 8 9 * 作业：稀疏矩阵相加 两个m*n的稀疏矩阵A，B struct SMat int row; //行 int col; //列 int val; //值 A[100], B[100], C[200]; A中非零元素P P 100 个，B中非零元素Q Q 100 个， 请以以下函数名写出A与B相加的程序，结果保存到C中，返回结果非零元素个数 int AddSparseMatrix SMat A[ ], P, SMat B[ ], Q, SMat C[ ] …… 字符串 字符串 n n≥0 个字符的一个有限序列，简称为串 记为S “a0 a1 a2 … an-1” n是串的长度，n等于0的串叫空串 子串 串中连续若干个字符组成的串 S “maintenance”，P