考研数据结构3 矩阵.pdf

DotNetWalker 计算机考研资料 图解数据结构 1 a11 a12 a1n a21 a22 a2n am1 am2 amn a 一个二维数组 b 二维数组的每个元素是线性表 图 4 1 数组是线性表的推广 A A A1 A2 An 其中 Ai a1i a2i ami 第 l1行 第 l1 1 行 本行中aij前面的元素个数 l2 h2 aij l1 h1 每行元素个数 整 行 数 aij前面的元素个数 阴影部分的面积 整行数 每行元素个数 本行中aij前面的元素个数 i l1 h2 l2 1 j l2 b 寻址的计算方法 图 4 2 二维数组按行优先存储寻址示意图 al1l2 al1h2 a l1 1 l2 a l1 1 h2 ail2 aij ah1h2 LOC aij LOC al1l2 第 i 行 i l1 h2 l2 1 j l2 个元素 a 二维数组 c 二维数组按行优先存储 b 按行优先存储的三维数组内存映象 图 4 3 三维数组及其存储示意图 a111 a112 a121 a122 a131 a132 a141 a142 a211 a212 a 221 a222 a231 a232 a241 a242 a311 a312 a321 a322 a331 a332 a341 a342 三维 二维 一维 1 2 3 1 2 3 4 1 2 a111 a121 a131 a141 a211 a231 a 241 a221 a331 a341 a321 a311 a142 a132 a122 a112 a242 a342 a 一个 3 4 2 的三维数组的逻辑结构 DotNetWalker 计算机考研资料 图解数据结构 2 3 6 4 7 8 6 2 8 4 2 4 8 1 6 9 7 4 6 0 5 8 2 9 5 7 A 图 4 4 一个 5 阶对称矩阵 第1行 第 n 1 行 第 0 行 图 4 5 对称矩阵的压缩存储 a00 a10 a11 a20 a21 a22 aij a n 10 an 11 an 1n 1 第2行 0 1 2 3 4 5 k n n 1 2 1 0 i n 1 a 下三角矩阵 b 存储说明 c 计算方法 图 4 6 对称矩阵按行优先存储寻址示意图 0 j n 1 每行元素个数 1 2 aij在本行中的序号 aij在一维数组中的序号 阴影部分的面积 i i 1 2 j 1 一维数组下标从 0 开始 aij在一维数组中的下标 k i i 1 2 j aij aij 第0 行 第1 行 3 c c c c 6 2 c c c 4 8 1 c c 7 4 6 0 c 8 2 9 5 7 a 下三角矩阵 3 4 8 1 0 c 2 9 4 6 c c 5 7 c c c 0 8 c c c c 7 b 上三角矩阵 图 4 7 三角矩阵 DotNetWalker 计算机考研资料 图解数据结构 3 常 数 项 第1行 第 n 1 行 第 0 行 图 4 8 下三角矩阵的压缩存储 a00 a10 a11 a20 a21 a22 aij an 10 an 11 an 1n 1 第2行 0 1 2 3 4 5 k n n 1 2 c a 三对角矩阵 a00 a01 0 0 0 a10 a11 a12 0 0 0 a21 a22 a23 0 0 0 a32 a33 a34 0 0 0 a43 a44 A b 压缩为 5 3 的矩阵 0 a00 a01 a10 a11 a12 a21 a22 a23 a32 a33 a34 a43 a44 0 B 将 带 状 区 图 4 9 对角矩阵的压缩存储方法 1 c 压缩到一维数组中 a 三对角矩阵 0 0 0 0 0 0 0 0 0 0 0 0 A 图 4 10 对角矩阵的压缩存储方法 2 a00 a01 a43 a44 a10 a11 a12 a21 a22 a23 a32 a33 a34 按 行 存 储 非 零 元素 元素aij在一维数组中的序号 2 3 i 1 j i 2 2i j 1 一维数组下标从 0 开始 元素aij在一维数组中的下标 2i j b 寻址的计算方法 a00 a01 a10 a11 a12 a21 a22 a23 a32 a33 a34 a43 a44 0 1 2 3 4 5 6 7 8 9 10 11 12 DotNetWalker 计算机考研资料 图解数据结构 4 15 0 0 22 0 15 0 11 3 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 91 0 0 0 0 0 图 4 11 稀疏矩阵 A 图 4 12 A 的三元组顺序表 0 0 15 0 3 22 0 5 15 1 1 11 1 2 3 2 3 6 4 0 91 空 空 空 闲 闲 闲 5 6 7 row col item 0 1 2 3 4 5 6 MaxTerm 1 矩阵的行数 矩阵的列数 非零元个数 15 0 0 0 91 0 11 0 0 0 0 3 0 0 0 22 0 6 0 0 0 0 0 0 0 15 0 0 0 0 图 4 13 A 的转置 B B 图 4 14 B 的三元组顺序表 0 0 15 0 4 91 1 1 11 2 1 3 3 0 22 3 2 6 5 0 15 空 空 空 闲 闲 闲 矩阵的行数 6 矩阵的列数 5 非零元个数 7 row col item 0 1 2 3 4 5 6 MaxTerm 1 DotNetWalker 计算机考研资料 图解数据结构 5 图 4 15 稀疏矩阵 A 的 num 与 cpot 值 col 0 1 2 3 4 5 num col 2 1 1 2 0 1 cpot col 0 2 3 4 6 6 cpot 0 num 0 图 4 16 num 与 cpot 之间关系示意图 cpot 1 num 1 cpot 2 num 2 cpot 3 row col item 0 1 2 3 4 5 6 num 3 cpot 4 cpot 5 element down right 图 4 17 十字链表的结点结构 图 4 18 稀疏矩阵的十字链表表示 1 1 3 1 4 7 3 1 2 2 3 1 5 4 8 HA DotNetWalker 计算机考研资料 图解数据结构 6 a 广义表 D b 广义表 E c 广义表 F 图 4 19 广义表的图形表示 a e b c d a D C B A FE tag 1 hp tp tag 0 data a 表结点 b 元素结点 图 4 20 头尾表示法的结点结构 1 1 1 1 1 1 1 1 1 1 1 1 0 a 0 d 0 c 0 b 0 a 0 e B C D E F 图 4 21 广义表头尾表示法的存储示意图 A NULL DotNetWalker 计算机考研资料 图解数据结构 7 6 1 8 7 5 3 2 9 4 15 8 1 24 17 16 14 7 5 23 22 20 13 6 4 3 21 19 12 10 9 2 25 18 11 a 3 阶魔方阵 b 5 阶魔方阵 图 4 22 魔方阵示例 1 1 2 1 3 2 a n 1 2 1 0 1 位置填 1 b 0 1 的左上为 1 0 c 2 0 的左上为 1 1 调整位置为 2 0 填 2 调整位置为 1 2 填 3 1 3 2 4 1 5 3 2 4 6 1 5 3 2 4 d 1 2 的左上为 0 1 已有 e 2 2 的左上为 1 1 填 5 f 1 1 的左上为 0 0 填 6 数字 调整位置为 2 2 填 4 6 1 7 5 3 2 4 6 1 8 7 5 3 2 4 6 1 8 7 5 3