数组和广义表

第五章数组和广义表引言 线性表 L a1 a2 an ai是同类型的元素 1 i n数组 A a1 a2 an 若ai是同类型的元素 A是一维数组 1 i n若ai是同类型的定长线性表 A是多维数组 1 i n广义表 Ls a1 a an ai可以是同类型的元素或不定长的线性表 1 i n5 1数组及其操作简单地说 向量和矩阵称为数组 5 1 1数组的递归定义1 一维数组是一个定长线性表 a1 a2 an 其中 ai为元素 i为下标 序号 1 i n a1 a2 an 又称为向量 2 二维数组是一个定长线性表 1 2 m 其中 i ai1 ai2 ain 为行向量 1 i m由m个行向量组成 记作 a11a12 a1n a21a22 a2n am1am2 amn Am n 即Am n a11a12 a1n a21a22 a2n am1am2 amn 或由n个列向量组成 记作 a11a12a1na21a22a2nam1am2amn Amxn 3 三维数组是一个定长线性表 1 2 p 其中 k 1 2 m 为定长二维数组 1 k p例三维数组A 1 3 1 4 1 2 p 3 m 4 n 2 a111a112a121a122a131a132a141a142 a211a212a221a222a231a232a241a242 a311a312a321a322a331a332a341a342 第1页 第2页 第3页 5 1 2数组的类型定义和变量说明 例1inta 10 10个整数的一维数组charb 4 5 4行5列个字符的二维数组floatc 3 4 2 3 4 2个实数的三维数组 A3 4 2 5 2数组的顺序表示和实现5 2 1顺序表示 顺序存储结构 1 以行序为主序的顺序存储方式左边的下标后变化 右边的下标先变化2 以列序为主序的顺序存储方式左边的下标先变化 右边的下标后变化例1二维数组a 1 3 1 2 b是首地址 s是元素所占的单元数 a11a12a21a22a31a32 序号内存地址 123456 123456 序号内存地址 bb sb 2 sb 3 sb 4 sb 5 s bb sb 2 sb 3 sb 4 sb 5 s 以行序为主序 以列序为主序 逻辑结构 例2三维数组a 1 2 1 3 1 2 a111a112a121a122a131a132 序号内存地址 123456789101112 序号内存地址 bb sb 2 sb 3 sb 4 sb 5 sb 6 sb 11 s bb sb 2 sb 3 sb 4 sb 5 sb 6 sb 11 s 以行序为主序 以列序为主序 逻辑结构 a211a212a221a222a231a232 第1页 第2页 123456789101112 5 2 2数组的映象函数数组元素的存储地址 实现元素的随机存取 例1一维数组a 0 n 1 设 b为首地址 s为每个元素所占的存储单元数则 元素a i 的存储地址 Loc i Loc 0 i s b i s0 i n 1 下标012in 1地址bb sb 2 sb i sb n 1 s 下标123in地址bb sb 2sb i 1 sb n 1 s 例2一维数组a 1 n 元素a i 的存储地址Loc i Loc 1 i 1 s b i 1 s1 i n例3二维数组a 1 m 1 n 假定无零行零列 a11 a1j a1n ai1 aij ain am1 amj amn Amxn 1 以行序为主序 a i j 的地址为Loc i j Loc 1 1 n i 1 j 1 s b n i 1 j 1 s1 i m 1 j n其中 b为首地址 s为每个元素所占的存储单元数n 列数m 行数 共i 1行 共j 1列 例3二维数组a 1 m 1 n 假定无零行零列 a11a11 a1j a1n ai1ai1 aij ain am1am1 amj amn Amxn 2 以列序为主序 a i j 的地址为Loc i j Loc 1 1 m j 1 i 1 s b m j 1 i 1 s1 i m 1 j n其中 b为首地址 s为每个元素所占的存储单元数n 列数m 行数 共i 1行 共j 1列 例4二维数组a 0 m 1 0 n 1 有零行零列 a00 a0j a0n 1a10 a1j a1n 1 ai0 aij ain 1 am 10 am 1j am 1n 1 Amxn 1 以行序为主序 a i j 的地址为Loc i j Loc 0 0 n i j s b n i j s0 i m 1 0 j n 1其中 b为首地址 s为每个元素所占的存储单元数n 列数m 行数 共i行 共j列 例4二维数组a 0 m 1 0 n 1 有零行零列 a00a01 a0j a0n 1a10a11 a1j a1n 1 ai0ai1 aij ain 1 am 10am 11 am 1j am 1n 1 Amxn 2 以列序为主序 a i j 的地址为Loc i j Loc 0 0 m j i s b m j i s0 i m 1 0 j n 1其中 b为首地址 s为每个元素所占的存储单元数n 列数m 行数 共i行 共j列 例5三维数组a 1 p 1 m 1 n 假定无0页0行0列1 以行序为主序 a k i j 的地址为Loc k i j Loc 1 1 1 m n k 1 n i 1 j 1 s b m n k 1 n i 1 j 1 s1 k p 1 i m 1 j n其中 b为首地址 s为每个元素所占的存储单元数p 页数n 列数m 行数 2 以列序为主序 a k i j 的地址为Loc k i j Loc 1 1 1 p m j 1 p i 1 k 1 s b p m j 1 p i 1 k 1 s1 k p 1 i m 1 j n其中 b为首地址 s为每个元素所占的存储单元数p 页数n 列数m 行数 例6三维数组a 0 p 1 0 m 1 0 n 1 假定有0页0行0列 1 以行序为主序 a k i j 的地址为Loc k i j Loc 0 0 0 m n k n i j s b m n k n i j s0 k p 1 0 i m 1 0 j n 1其中 b为首地址 s为每个元素所占的存储单元数p 页数n 列数m 行数 2 以列序为主序 a k i j 的地址为Loc k i j Loc 0 0 0 p m j p i k s b p m j p i k s0 k p 1 0 i m 1 0 j n 1其中 b为首地址 s为每个元素所占的存储单元数p 页数n 列数m 行数 5 3矩阵的压缩存储5 3 1特殊矩阵的压缩存储特殊矩阵 指非零元素或零元素的分布有一定规律的矩阵 1 n阶对称矩阵151375080018926A为5 5的对称方阵3025170613性质 aij aji0 i j n 1压缩存储 上三角和下三角对称的两个元素共享一个存储空间设按行顺序存储下三角矩阵元素 a00 a10a11 a20a21a22 an 1 0an 1 1 an 1 n 1下三角矩阵中 第i行 0 i n 正好有i 1个元素 总数为 i 1 n n 1 2需存放元素的数组 sa 0 n n 1 2 1 A 上三角 下三角 n 1 i 0 为了便于访问对称矩阵中的元素 找aij与sa k 间的对应关系 1 设i j aij在下三角 第0 i 1行共有元素 1 2 3 i i i 1 2 个 ai0 aij 1共有j个元素 aij的序号为 k i i 1 2 j0 k i i 1 2 2 设i j aij在上三角 上三角的aij 下三角的aji 交换i和j 下三角的aji的序号为k j j 1 2 i0 k n n 1 2 3 一般 令I max i j J min i j 则k与i j的对应关系统一为 k I I 1 2 J0 k n n 1 2aij地址计算公式 LOC aij LOC sa k LOC sa 0 k d d 元素占的单元数 LOC sa 0 I I 1 2 J d上例 a12和a21均存储在sa 4 中 k I I 1 2 J 2 2 1 2 1 4 实现随机存取 2 三角矩阵以对角线分上三角矩阵和下三角矩阵 c为0或相同的常数 a00a01 a0 n 1a00c cca11 a1 n 1a10a11c c c can 1 n 1an 1 0an 1 1 an 1 n 1下三角矩阵上三角矩阵c可共存储在一个空间中 其余元素的个数 n n 1 2 则 使用数组sa 0 n n 1 2 存储元素 其中c存储在最后一个分量中 1 上三角矩阵第p行 0 p n 有n p个元素 按行存储aij aij前的i行一共 n p i 2n i 1 2在第i行上 aij前刚好有i j个元素 Aij和sa k 的对应关系 k 2 下三角矩阵存储与对称矩阵类似k i 2n i 1 2 j i当i jn n 1 2当i j i i 1 2 ji jn n 1 2i j 实现随机存取 3 三对角矩阵 a11a12a21a22a23a32a33a34 an 2n 3an 2n 2an 2n 1an 1n 2an 1n 1 Anxn 全0 全0 假定以行序为主 顺序存储非0元素到sa 1 maxleng k 123456 3n 2 任意aij 0 在sa中的序号 k 3 i 1 1 j i 2 2 i 1 j 随机存取 5 3 2稀疏矩阵的压缩存储1 稀疏矩阵矩阵Amn中的非0元素的个数s远远小于矩阵元素的总数 s m n 则称A为稀疏矩阵 0500803000 200060000 A4 5 稀疏矩阵压缩存储 只存非0元素 非0元素的确定 三元组 i j aij 对压缩存储后的矩阵元素 不能随机存取 稀疏矩阵压缩存储的方法 顺序存储和链式存储 只讲顺序存储 2 三元组表将稀疏矩阵中每个非0元素的三元组按行 或列 次序排列 得到的三元组的线性表 称为三元组表 即 三元组表是稀疏矩阵压缩存储的顺序存储结构 05008103000 200060000 A4 5 01 a t 1 MaxSize 1 ijv aij A的三元组表 考虑运算的方便 将矩阵的总行数 总列数和非0元素的总个数作为三元组表的属性 三元组表数据结构定义 defineMaxSize100 用户自定typedefintDataType 用户自定typedefstruct 三元组inti j 行 列号和元素vDataTypev TnTupleNode typedefstruct 三元组表TnTupleNodedata MaxSize m n行列总数和非0元素的总数tintm n t TnTupleTable 表a 3 例子 下面以稀疏矩阵的转置矩阵为例 说明压缩存储结构如何实现矩阵运算 A的转置矩阵B 010650 20030000008000 B5 4 01 b t 1 MaxSize 1 ijv aij B的三元组表 特征 行列数交换 Amn Bnm元素下标交换 A i j B j i A的行是B的列 A的列是B的行 表b 问题 1 将A矩阵的三元组表中各元素的行列交换得到的三元组表 是否就是其对应的转置矩阵B的按行存储的三元组表 不是 是对应转置矩阵B的按列存储的三元组表 交换表a中的行列 01 a t 1 MaxSize 1 ijv aij 2 如何由A矩阵的三元组表求对应的转置矩阵B的按行存储的三元组表 即 由表a求表b 将表a转置成表b 步骤 a 在表a的j列中按顺序找所有列号为j j初值为0 的三元组 b 将该三元组中的行列号交换后的三元组 依次送入表b的三元组表中 c 列号j加1 j n 1 是 转a 否则结束 算法 三元组表a转置成三元组表bvoidTransMatrix TnTupleTable b TnTupleTable a intp q t col b m a n b n a m b t a t 交换行列和非0元素总数if b tn col for p 0 pt p if a data p j col 在j列中找所有0 1 n 1 b data q i a data p j 将表a的列号j送表b的行中 b data q j a data p i 将表a的行号i送表b的列中 b data q v a data p v 送元素的值到b中 q 将表a中的列号从0 1 n 1依次找所有的三元组 带行表的三元组表是稀疏矩阵另一种顺序存储结构 见书p65 5 4广义表 generalizedlist 列表 lists 5 4 1广义表的定义和术语n n 0 个数据元素或广义表的一个有限序列叫做广义表 记作 LS e1 e2 en n为LS的长度 其中 LS 广义表名若ei不可再分的项称为原子 约定用小写 1 i n若ei又是广义表 则称为LS的子表 约定用大写 1 i n 1 空表LS n 0 2 非空表LS e1 e2 en n 0其中 e1 LS的表头 首部 记作 head LS e1 e2 en 除表头外 其余的元素构成的表称为LS的表尾 尾部 记作 tail LS e2 en 广义表是线性表的推广 例 1 M 空表n 0 2 N e n 1 3 L a b n 2线性表 4 A x L x a b n 2 5 B A y x a b y n 2 6 C A B x a b x a b y n 2 7 D a D a a 递归广义表n 2深度 广义表展开后所含括号的的层数 如 广义表M N L A B C D的深度分别为 1 1 1 2 3 4 无穷大 带有表名的广义表的表示 1 M 2 N e 3 L a b 4 A x a b 5 B x a b y 6 C x a b x a b y 7 D a D a D 5 4 2广义表的图型表示非分支结点对应原子 分支结点对应广义表 例 1 M 2 N e 3 L a b 4 A x L M N e a b L a B A b x L A y b a x L C b A a x L B y D a 5 B A y 6 C A B 7 D a D 5 4 3广义表的操作广义表的操作 求表长 求深度 求表头 主要介绍求表尾 主要介绍求第i个元素和插入等操作 广义表不仅是线性表的推广 也是树的推广 纯表 与树对应的广义表 特点 不允许表中成分共享和递归 如 1