第三章 多维数组和广义表

第三章多维数组和广义表 数组可以看成是一种特殊的线性表 即线性表中数据元素本身也是一个线性表 例如二维数组 3 1多维数组 数组的两种顺序存储结构以行序为主序 行优先顺序 以列序为主序 列优先顺序 数组特点数组结构固定数据元素同构数组运算给定一组下标 存取相应的数据元素给定一组下标 修改数据元素的值 Loc aij Loc a11 i 1 n j 1 d 按行序为主序存放 若行列下标均从0开始 则Loc aij Loc a00 i n j d 按列序为主序存放 Loc aij Loc a11 j 1 m i 1 d 若行列下标均从0开始 则Loc aij Loc a00 j m i d 3 2矩阵的压缩存储 3 2 1特殊矩阵1 对称矩阵 0 i n 0 j n aij aji 2 三角矩阵 下三角 Loc aij Loc a00 i i 1 2 j d 共占用n n 1 2 1个单元 按行序为主序 k 012345n n 1 2n n 1 2 1 三角矩阵 上三角 Loc aij Loc a00 i 2n i 1 2 j i d 按行序为主序 k 012n 1n n 1 2 1n n 1 2 3对角矩阵 按行序为主序 k 012345673 n 1 13 n 1 3 2 2特殊矩阵的抽象数据类型 ADTSpecialMatrixisData 特殊矩阵线性表 a1 an an 1 Matrix为类型描述符Operations voidInitMatrix Matrix清除特殊矩阵endSpecialMatrix structMatrix 特殊矩阵线性表数据类型 ElemType data 定义线性表向量指针inttype size 特殊矩阵类型和规模 type 1对称矩阵 type 2下三角矩阵 type 3上三角矩阵 3 2 3特殊矩阵基本算法描述 voidInitMatrix Matrix 给下三角赋值 ElemTypeGetMatrixElem Matrixm inti intj 取特殊矩阵元素if m type 1 对称矩阵if i j returnm data i i 1 2 j elsereturnm data j j 1 2 i elseif m type 2 下三角矩阵if i j returnm data i i 1 2 j elsereturnm data m size m size 1 2 else 上三角矩阵if j i returnm data i 2 m size i 1 2 j i elsereturnm data m size m size 1 2 VoidSetMatrixElem Matrix VoidClearMatrix Matrix 稀疏矩阵的压缩存储原则 只存矩阵的行列数和每个非零元的行列下标及其值 矩阵M可由 0 1 12 0 2 9 2 0 3 2 5 14 3 2 24 4 1 18 5 0 15 5 3 7 和矩阵行列数 6 7 唯一确定 定义 若矩阵的非零元素个数远远少于它的零元素个数 且非零元素的分布没有一定规律 则该矩阵为稀疏矩阵 3 2 4稀疏矩阵 稀疏矩阵的压缩存储方法1 三元组表 顺序存储结构 defineMaxTerms100 非零元素的最大个数typedefintElemType structTriple introw col 行号 列号ElemTypeval 非零元素 structSMatrix intm n t 行数 列数 非零元素个数Tripledata MaxTerms 1 结点数组 rowcolval 01234567 行列下标 非零元值 mntdata SMatrix M矩阵的三元组存储结构 求转置矩阵问题描述 已知一个稀疏矩阵的三元组表 求该矩阵转置矩阵的三元组表 问题分析 转置矩阵B中的元素bij即为矩阵A中的元素aji B的行数等于A的列数 B的列数等于A的行数 将A三元组中的i和j互换后拷贝到B三元组中 重排B三元组次序 使其中元素以i 行 为主序 SMatrix TransMat SMatrix a 求矩阵a转置矩阵b intcol n SMatrix b newSMatrix 1 为转置矩阵B申请内存b m a n b n a m b t a t if b t 0 returnb for col 1 n 1 col a m col 按A的列次序拷贝for intk 1 k a t k 扫描整个三元组if a data k col col 拷贝第col列的三元组 b data n col a data k row b data n row a data k col b data n val a data k val n returnb 算法分析 T n O A的列数 非零元个数 矩阵转置的改进算法 按a中三元组次序一次转置并拷贝到b三元组中 将a中的每个三元组转置后放入b中恰当位置 此法关键是要预先确定a中每一列第一个非零元在b中位置 为确定这些位置 转置前应先求得a中每一列的非零元个数 rowcolval 列元素个数b中起始位置 123456 b中起始位置 A B 123456 rowcolval rowcolval SMatrix TransMat SMatrix a 矩阵a转置改进算法 int pos newint a n 1 SMatrix b newSMatrix 1 为转置矩阵B申请内存b m a n b n a m b t a t if b t 0 returnb for intk 0 k a n k pos k 0 for intk 1 k a t k 扫描三元组apos a data k col A各列非0元素计数intadd 1 for intk 1 k b m k 计算B三元组各行起始位置 intn pos k pos k add add n for intk 1 k a t k 扫描三元组 intn pos a data k col b data n row a data k col b data n col a data k row b data n val a data k val returnb 算法分析 T n O 2 非零元个数 行数 列数 在十字链表中 每一个非零元素用一个结点表示 分别存放该元素的行 列 元素值 指向本行下一非零元素的指针 指向本列下一非零元素的指针 为索引各行和各列的第一个非零元素 设置一组同样结构的行列头结点 每个头结点的行指针指向本行第一个非零元结点 列指针指向本列第一个非零元结点 若本行或本列无非零元 则相应指针域为空 十字链表结点类型定义如下 structMatLink introw col MatLink down right ElemTypevalue 2 十字链表 链式存储结构 稀疏矩阵的结点 稀疏矩阵元素结点 稀疏矩阵的正交链表表示示例 建立稀疏矩阵的十字链表 MatLink CreateLinkMat MatLink p q cp inti j m n t s ElemTypev cout m n t s m n m n cp newMatLink s 1 开辟头指针数组cp 0 newMatLink cp 0 row m cp 0 col n for i 1 i s i 构造头结点单链表 cp i newMatLink cp i row cp i col 0 cp i right cp i down cp i 初始指向自身 for i 1 i i j v p newMatLink p row i p col j p value v q cp i 取i行表头while q right cp i q cp j 取j列表头while q down cp j 算法分析 T n O t s 其中 t 非零元个数s max m n 广义表 GeneralLists 的概念 广义表是由n 0 个表元素组成的有限序列 记作LS a1 a2 a3 an 其中LS是表名 ai是表元素 可以是数据元素 称为原子 也可以是表 称为子表 n为表的长度 n 0的广义表为空表 n 0时 表的第一个表元素a1称为广义表的表头 head 除此之外 其它表元素组成的表 a2 a3 an 称为广义表的表尾 tail 3 3广义表的概念 广义表的特性 有次序性有长度有深度 可递归可共享 A B 6 2 C a 5 3 x D B C A E B D F 4 F 各种广义表的示意图 广义表的表示 只包括整数和字符型数据的广义表链表表示 表中套表情形下的广义表链表表示 广义表结点定义 标志域utype 表明结点类型 0为表头结点 1为整型原子结点 2为字符型原子结点 3为子表结点 值域value 当utype 0时为表引用计数 1时为整数值 2时为字符值 3时为指向子表的表头结点的指针 尾指针域tlink 当utype 0时为指向该表表头元素的指针 当utype 0时为指向同一层下一个表结点的指针 utype 0 1 2 3 value ref intgrinfo charinfo hlink tlink 广义表的带表头结点的存储表示 广义表结点类型定义 StructGLNode unsignedcharutype union ElemTypedata GLNode sublist GLNo