5_数组和广义表.ppt

1 第五章数组和广义表 2 本章内容 5 1数组的类型定义5 2数组的顺序表示和实现5 3特殊矩阵的压缩存储5 4广义表的类型定义5 5广义表的表示方法5 6广义表操作的递归函数 3 数组 二维数组 三维数组 一维数组 顺序表 4 supplier SUP1 SUP2 SUP3 四维数组 5 5 1数组的类型定义 ADTArray 二维数组的定义数据对象 数据关系 基本操作 ADTArray 0 i b1 1 0 j b2 1D aij aij ElemSet R ROW COL ROW 0 i b1 2 0 j b2 1 COL 0 i b1 1 0 j b2 2 6 5 1数组的类型定义 ADTArray n维数组数据对象 数据关系 基本操作 ADTArray ji 0 bi 1 i 1 2 nD aj1 j2 ji jn aj1 j2 ji jn ElemSet R R1 R2 Rn Ri 0 ji bi 2 i 2 n 0 jk bk 1 1 k n且k iaj1 ji jn aj1 ji 1 jn ElemSet n 数组的维数 bi 第i维的长度 7 基本操作 InitArray A n bound1 boundn 操作结果 若维数n和各维长度合法 则构造相应的数组A 并返回OK DestroyArray A 操作结果 销毁数组A 8 基本操作 Value A e index1 indexn 初始条件 A是n维数组 e为元素变量 随后是n个下标值 操作结果 若各下标不超界 则e赋值为所指定的A的元素值 并返回OK Assign A e index1 indexn 初始条件 A是n维数组 e为元素变量 随后是n个下标值 操作结果 若下标不超界 则将e的值赋给所指定的A的元素 并返回OK 9 5 2数组的顺序表示和实现 类型特点 1 只有引用型操作 没有加工型操作 2 数组是多维的结构 而存储空间是一个一维的结构 两种顺序映象方式 1 以行序为主序 低下标优先 2 以列序为主序 高下标优先 10 11 以 行序为主序 的存储映象 二维数组A中任一元素aj1 j2的存储位置LOC j1 j2 LOC 0 0 b2 j1 j2 L A 2 3 基地址 LOC 1 2 LOC 0 0 3 1 2 L 12 数组A 3 4 5 求LOC 2 3 1 LOC 2 3 1 LOC 0 0 0 4 5 2 4 3 1 L 三维数组A中任一元素aj1 j2 j3的存储位置LOC j1 j2 j3 LOC 0 0 0 b3 b2 j1 b2 j2 j3 L 13 以 行序为主序 的存储映象 n维数组数据元素存储位置的映象关系 称为n维数组的映象函数 数组元素的存储位置是其下标的线性函数 14 5 3特殊矩阵的压缩存储 特殊矩阵的种类1 特种矩阵非零元在矩阵An n中的分布有一定规律例如 对称矩阵 三角矩阵 对角矩阵2 随机稀疏矩阵非零元很少 且在矩阵Am n中随机出现 15 5 3 1对称矩阵的压缩存储 存储下三角数据 矩阵中任意位置的元素aij与它的存储位置k是一一对应的 其关系是 aij aji 16 什么是稀疏矩阵 假设m行n列的矩阵 其中非零元素 t个 占总数的比例小于5 的矩阵为稀疏矩阵 即 稀疏因子 0 05的矩阵为稀疏矩阵 稀疏因子为 17 稀疏矩阵的存储 以二维数组表示高阶的稀疏矩阵 产生的问题 零值元素占了很大空间 计算中进行了很多和零值的运算 遇除法 还需判别除数是否为零 解决问题的原则 尽可能少存或不存零值元素 尽可能减少没有实际意义的运算 操作方便 能尽可能快地找到与下标值 i j 对应的元素操作方便 能尽可能快地找到同一行或同一列的非零值元 18 5 3 2随机稀疏矩阵的压缩存储方法 一 三元组顺序表二 行逻辑链接顺序表三 十字链表 19 M data 行数M mu列数M nu元素个数M tu 一 三元组顺序表 按行序存储 20 三元组顺序表的定义 defineMAXSIZE12500typedefstruct inti j 该非零元的行下标和列下标ElemTypee 该非零元的值 Triple 三元组类型 typedefstruct Tripledata MAXSIZE 1 data 0 未用intmu nu tu 行数 列数 元素个数 TSMatrix 稀疏矩阵类型 21 如何求转置矩阵 22 用常规的二维数组表示时的算法 其时间复杂度为 O mu nu for col 1 col nu col for row 1 row mu row T col row M row col Tij Mji 23 用 三元组 表示时如何实现 2114 51 5 22 7 1336 4328 按行序存储 基本操作 按照M的列序 依次从M中找出属于当前列的元素放在T中 24 用 三元组 表示时的操作步骤 voidTranMatrix TSMatrixM TSMatrix p 25 voidTranMatrix TSMatrixM TSMatrix TransposeSMtrix q 1 q为T data 当前三元组的位置 下标 for row 1 row T mu row for p 1 p M tu p p 扫描M data指示器if M data p j row T data q i M data p j T data q j M data p i T data q e M data p e q O nu tu 26 如何求转置矩阵 回顾 TranMatrix TSMatrixM TSMatrix T 方法一 用常规的二维数组表示矩阵的算法Tij Mji 复杂度为 O mu nu M T 27 如何求转置矩阵 回顾 方法二 用三元组表存储稀疏矩阵按照T的行序 在M中依次找出属于当前行的元素复杂度为 O nu tu 按行序存储 2114 51 5 22 7 1336 4328 M T 28 按行序存储 2114 51 5 22 7 1336 4328 能否直接放到正确位置 M中每一列的第一个非零元素在T中开始的位置 29 矩阵快速转置算法 1 确定M中每一列的第一个非零元素在T三元组中的位置2 将M中的元素放在T中恰当位置 30 矩阵快速转置算法 1 M中每一列的第一个非零元素在T中开始的位置Num col M中第col列非零元素个数Cpot col M中第col列第一个非零元素的位置 cpot 1 1 for col 2 col M nu col cpot col cpot col 1 num col 1 Num col col Cpot col 31 矩阵快速转置算法 2 将M中的元素放在T中恰当位置 col Cpot col 按行序存储 2114 51 5 22 7 1336 4328 3 6 4 2 5 for p 1 p M tu p col M data p j q cpot col T data q i M data p j T data q j M data p i T data q e M data p e cpot col 32 矩阵快速转置算法的操作步骤 设置T的各个参数 T mu M nu T nu M mu T tu M tu 依次求M中第col列的元素个数依次求M中第col列的元素在T中的起始位置依次将M中的元素放到正确的位置 33 StatusFastTransposeSMatrix TSMatrixM TSMatrix FastTransposeSMatrix O nu tu for p 1 p M tu p 转置矩阵元素 步骤4 T mu M nu T nu M mu T tu M tu 步骤1if T tu 0 returnNOELEM for col 1 col T mu col num col 0 步骤2for t 1 t M tu t num M data t j cpot 1 1 步骤3for col 2 col M nu col cpot col cpot col 1 num col 1 34 算法分析 用常规的二维数组表示时的算法时间复杂度 O mu nu 矩阵转置算法1 时间复杂度 O nu tu 仅适用于 tu mu nu矩阵快速转置算法时间复杂度 O nu tu 当tu接近mu nu时 复杂度为O mu nu 当tu mu nu时 O nu tu O mu nu 35 二 行逻辑链接顺序表 带行表的三元组 M data 行数M mu列数M nu元素个数M tu 按行序存储 M rpos 36 带行表的三元组 definemaxrow100typedefstruct tripledata maxsize intrpos maxrow 行逻辑链接 每行第一个元素在表中的位置intmu nu tu rtripletable 37 矩阵的乘法 0050 1002000 M 06 1004 Q 如果用二维数组存储矩阵 算法包含三重循环进行m1 n2 n1次乘法 m1 n1 m2 n2 m1 n2 n1 m2 38 用带行表三元组表示矩阵时的算法 每个M i j 分别与N中第j行的元素 j ccol 相乘 乘积累加到Q i ccol 中 m1 n1 m2 n2 m1 n2 39 用三元组表示矩阵时的算法 算法的基本思想 每次计算Q中的一行元素 设当前行号为arow设临时变量ctemp n2 保存该行元素计算完后将该行元素压缩存储到Q的三元组中计算方法 M中的每一个元素 i j 分别与N中第j行的元素 j ccol 相乘 其结果累加到Q i ccol 中 40 二 十字链表 适合于对矩阵频繁修改的情况 41 十字链表的类型定义 typedefstructOLNode inti j 非零元的行下标和列下标ElemTypee 非零元值STRUCTOLNode right down OLNode OLink typedefstruct OLink rhead chead 行 列表头指针数组intmu nu tu 行数 列数和非零元个数 CrossList ije downright 42 十字链表的操作 类似线性表区别 对横纵两个方向的链表同时操作 1 1 3 1 4 5 2 2 1 3 1 2 1 M chead M rhead 43 5 4广义表 ADTGList 数据对象 D ei i 1 2 n n 0 ei AtomSet或ei GList AtomSet为某个数据对象集合 数据关系 LR ei 1 ei D 2 i n 基本操作 ADTGList 44 基本操作 结构的创建和销毁InitGList 状态函数GListLength L GListDepth L GListEmpty L GetHead L GetTail L 插入和删除操作InsertFirst GL 遍历Traverse GL L Visit 45 5 4 1广义表的定义 广义表 generalizedlist 一种不同构的线性结构 LS 1 2 n 其中 i或为原子 atom 或为广义表 广义表的基本性质广义表的定义是一个递归定义 因为在描述广义表时又用到了广义表 在线性表中数据元素是单个元素 而在广义表中 元素可以是单个元素称为原子 atom 也可以是广义表 称为广义表的子表 sublist 当每个元素均为原子且类型相同时 就是线性表 46 5 4 1广义表的定义 广义表的术语 LS 1 2 n 表头head 表名 表尾tail n是表长 表头 LS的第一个元素称为表头 表尾 其余元素组成的表称为LS的表尾 表长 为最外层包含元素个数 深度 所含括弧的重数 原子的深度为0 空表 的深度为1 2 n 47 5 4 1广义表的定义 例如 A 空表F d e D a b c F C A D F B a B a a a 递归定义 长度 0 深度 1 长度 2 深度 2 长度 2 深度 3 长度 3 深度 4 长度 2 深度 无限 48 广义表的结构特点 广义表的应用LISP语言专家系统数据挖掘广义表的结构特点1 广义表中的数据元素有相对次序 2 广义表可以共享 3 广义表可以是一个递归的表 49 广义表的结构特点 4 广义表是一个多层次的线性结构例如 D E F E a b c F d e 用 表示子表用 表示原子 D 长度 2 深度 3 深度 括号的重数 结点的层数 50 广义表的结构特点 5 任何一个非空广义表LS 1 2 n 均可分解为表头 Head LS 1表尾 Tail LS 2 n 第一个元素 其余元素构成的广义表 例如 D E F a b c F Head D ETail D F Head E aTail E b c Head b c b c Tail b c Head b c bTail b c c Head c cTail c 51 5 5 2广义表的存储结构 通常采用头 尾指针的链表结构 原子结点 表结点 52 若表头为原子 则为 空表ls NULL 非空表ls tag 1 指向表头的指针 指向表尾的指针 tag 0data 否则 依次类推 广义表的头尾链表存储表示 53 typedefstructGLNode ElemTagtag 标志域union At