第5讲数组和广义表

第5章数组和广义表 数组元素的下标一般具有固定的下界和上界 因此它比其他复杂的非线性结构简单 数组 数组元素的遍历1 以行序为主序 按行排列 先排最右的下标 依次向左 最后排最左的下标2 以列序为主序 按列排列 先排最左的下标 依次向右 最后排最右的下标 例如 称为基地址或基址 以 行序为主序 的存储映象 二维数组A b1 b2 中任一元素ai j的存储位置LOC i j LOC 0 0 b2 i j a0 1 a0 0 a0 2 a1 0 a1 1 a1 2 a0 1 a0 0 a0 2 a1 0 a1 1 a1 2 L L 推广到一般情况 可得到n维数组数据元素存储位置的映象关系 称为n维数组的映象函数 数组元素的存储位置是其下标的线性函数 其中cn L ci 1 bi ci 1 i n LOC j1 j2 jn LOC 0 0 0 ciji i 1 n 特殊矩阵非零元在矩阵中的分布有一定规则例如 对称矩阵三角矩阵三对角矩阵 矩阵的压缩存储对称矩阵 三角矩阵共计元素个数为 n n 1 2 三角矩阵 对角矩阵 Loc aij Loc a11 2 i 1 j 1 L i j 1 稀疏矩阵 SparseMatrix 稀疏矩阵是非零元素个数远远少于矩阵元素个数的矩阵 以常规方法 即以二维数组表示高阶的稀疏矩阵时产生的问题 1 零值元素占了很大空间 2 计算中进行了很多和零值的运算 遇除法 还需判别除数是否为零 1 尽可能少存或不存零值元素 解决问题的原则 2 尽可能减少没有实际意义的运算 3 操作方便 即 1 能尽可能快地找到与下标值 i j 对应的元素 2 能尽可能快地找到同一行或同一列的非零值元 稀疏矩阵基本操作1 intGetRows const初始条件 稀疏矩阵已存在 操作结果 返回稀疏矩阵行数 2 intGetCols const初始条件 稀疏矩阵已存在 操作结果 返回稀疏矩阵列数 3 intGetNum const初始条件 稀疏矩阵已存在 操作结果 返回稀疏矩阵非零元素个数 4 boolEmpty const初始条件 稀疏矩阵已存在 操作结果 如稀疏矩阵为空 则返回true 否则返回false5 StatusCodeSetElem intr intc constElemType v 初始条件 稀疏矩阵已存在 操作结果 设置指定位置的元素值 6 StatusCodeGetElem intr intc ElemType v 初始条件 稀疏矩阵已存在 操作结果 求指定位置的元素值 随机稀疏矩阵的顺序压缩存储 三元组表示法 随机稀疏矩阵的链式压缩存储 十字链表 随机稀疏矩阵非零元在矩阵中随机出现 三元组表 当稀疏矩阵的阶很高时 其中0元素会很多 如采用一般矩阵的存储方法 将存储大量0元素 这样将浪费大量的存储空间 一种直观 常用的方法是 对每个非零元素 用三元组 行号 列号 元素值 来表示 这样每个元素的信息就全部记录下来了 三元组声明如下 三元组类模板templatestructTriple 数据成员 introw col 非零元素的行下标与列下标ElemTypevalue 非零元素的值 构造函数模板 Triple 无参数的构造函数模板Triple intr intc ElemTypev 已知数数据域建立三元组 以顺序表存储三元组表 可得到稀疏矩阵的顺序存储结构 三元组顺序表在三元组顺序表中 用三元组表表示稀疏矩阵时 为避免丢失信息 增设了一个信息元组 形式为 行数 列数 非零元素个数 已知稀疏矩阵 三元组顺序表示例 三元组表示为 稀疏矩阵三元组顺序表类模板templateclassTriSparseMatrix protected 稀疏矩阵三元组顺序表的数据成员 Triple triElems 存储稀疏矩阵的三元组表intmaxSize 非零元素最大个数introws cols num 稀疏矩阵的行数 列数及非零元个数 public 抽象数据类型方法声明及重载编译系统默认方法声明 TriSparseMatrix intrs DEFAULT SIZE intcs DEFAULT SIZE intsize DEFAULT SIZE 构造一个rs行cs列非零元素最大个数为size 的空稀疏矩阵 TriSparseMatrix 析构函数intGetRows const 返回稀疏矩阵行数intGetCols const 返回稀疏矩阵列数intGetNum const 返回稀疏矩阵非零元个数StatusCodeSetElem intr intc constElemType 稀疏矩阵的转置 算法的基本思想 第一次从source中取出应该放置到dest中第一个位置的元素 行列号互换后 放于dest中第一个位置 第二次从source中选取应该放到dest中的第二个位置的元素 如此进行 依次生成dest中的各元素 由于转置后列号变行号 所以转置后元素的行序排列实质上是原矩阵元素的列序排列 实现算法可形式化描述为 destPos 0 稀疏矩阵dest的下一个三元组的存放位置for col 最小列号 col 最大列号 col 在source中从头查找有无列号为col的三元组 若有 则将其行 列号交换后 依次存入dest中destPos所指位置 同时destPos加1 templatevoidTriSparseMatrix SimpleTranspose constTriSparseMatrix 分配存储空间 if dest num 0 intdestPos 0 稀疏矩阵dest的下一个三元组的存放位置for intcol 1 col source cols col 转置前的列变为转置后的行for intsourcePos 0 sourcePos source num sourcePos 查找第col列的三元组if source triElems sourcePos col col 找到第col列的一个三元组 转置后存入destdest triElems destPos row source triElems sourcePos col 列变行dest triElems destPos col source triElems sourcePos row 行变列dest triElems destPos value source triElems sourcePos value 非零元素值不变destPos 新下一个元素的存放位置 十字链表 30050 1002000 1 1 3 1 4 5 2 2 1 3 1 2 广义表GeneralList 1 广义表的概念n 0 个表元素组成的有限序列 记作GL a1 a2 a3 an GL是表名 ai是表元素 它可以是表 称为子表 可以是数据元素 称为原子 2 n为表的长度 n 0的广义表为空表3 n 0时 表的第一个表元素称为广义表的表头 head 除此之外 其它表元素组成的表称为广义表的表尾 tail 由于广义表中的元素又可以是广义表 因此对于广义表有深度的概念 广义表GL的深度Depth GL 定义如下 广义表的深度本质上就是广义表表达式中括号的最大嵌套层数 广义表基本操作1 GenListNode First const初始条件 广义表已存在 操作结果 返回广义表的第一个元素 2 GenListNode Next GenListNode elemPtr const初始条件 广义表已存在 elemPtr指向的广义表元素 操作结果 返回elemPtr指向的广义表元素的后继3 boolEmpty const初始条件 广义表已存在 操作结果 如广义表为空 则返回true 否则返回false 4 voidPush constElemType e 初始条件 广义表已存在 操作结果 将元子元素e作为表头加入到广义表最前面 5 voidPush GenList subList 初始条件 广义表已存在 操作结果 将子表subList作为表头加入到广义表最前面 6 intDepth 初始条件 广义表已存在 操作结果 返回广义表的深度 广义表的存储结构广义表通常借助引用数链式存储结构 引用数法广义表 在这种方法中 每一个表结点由三个域组成 结点分三类 1 头结点 用标志域tag HEAD标识 数据域ref用于存储引用数 子表的引用数表示能访问此子表的广义表或指针个数 后面章节将对引用数的内涵作详细的介绍 2 原子结点 用标志域tag ATOM标识 原子元素用原子结点存储 数据域atom用于存储原子元素的值 3 表结点 用标志域tag LIST标识 指针域subLink用于存储指向子表头结点的指针 A B x y z C B y z D x y z E E 引用数法广义表类模板templateclassRefGenList protected 引用数法广义表类的数据成员 RefGenListNode head 头指针 辅助函数模板 voidShowHelp RefGenListNode hd const 显示以hd为头结点的广义表intDepthHelp constRefGenListNode hd 计算以hd为表头的广义表的深度voidClearHelp RefGenListNode hd 释放以hd为表头的广义表结构 voidCopyHelp constRefGenListNode sourceHead RefGenListNode 析构函数模板 RefGenListNode First const 返回引用数法广义表的第一个元素RefGenListNode Next RefGenListNode elemPtr const 返回elemPtr指向的广义表元素的后继boolEmpty const 判断广义表是否为空voidPush constElemType templateRefGenList RefGenList 操作结果 构造一个空引用数法广义表 head newRefGenListNode HEAD head ref 1 引用数 templateRefGenListNode RefGenList First const 操作结果 返回引用数法广义表的第一个元素 returnhead nextLink templateRefGenListNode RefGenList Next RefGenListNode elemPtr const 操作结果 返回elemPtr指向的引用数法广义表元素的 后继 returnelemPtr nextLink 求广义表的深度 例如 对于广义表E B a b D B a b C u x y z A 1 1 1 1 2 3 4 templateintRefGenList DepthHelp constRefGenListNode hd 操作结果 返回以hd为表头的引用数法广义表的深度 if hd nextLink NULL return1 空广义表的深度为1intsubMaxDepth 0 子表最大深度for RefGenListNode tmpPtr hd nextLink tmpPtr NULL tmpPtr tmpPtr nextLink 求子表的最大深度 if tmpPtr tag LIST 子表intcurSubDepth DepthHelp tmpPtr subLink 子表深度if subMaxDepthintRefGenList Depth 操作结果 返回广义表深度 returnDepthHelp head 补充 广义表的两个操作1 Head 或GetHead 得到广义表的表头元素 单元素or表元素 2 Tail 或GetTail 得到广义表的表尾 除表头元素之外的剩余元素组成的子表 肯定是广义表 例1 A a b c d Head A aTail A b c d 例2 若Head L Tai