数据结构 Ch.5 数组和广义表 计算机学院 肖明军 Email: xiaomj@ustc.edu.cn http://staff.ustc.edu.cn/~xiaomj 多维数组 是最易处理的非线性结构 因为各元素类型一致, 各维上下界固定, 所以它最容易线性化, 故可看做是线性表的拓广 例如 : 二维数组可以看做是由列向量组成的线性表 1. 结构特性 例 : 二维数组, 它属于两个向量 ;i th 行和 j th 列 除边界外, 每个 a ij 恰有两个直接前驱和两个直接后继 3 非线性特征 i th 行 : 前驱 a ij-1, 后继 a ij+1 j th 列 : 前驱 a i-1j, 后继 a i-1j 仅有一个开始结点 :a 11 仅有一个终端节点 :a mn 其他边界上的结点只有一个直接前驱或一个直接后继, 类似的 m 维数组的每一个元素都属于 m 个向量 4. 存储一般均采用顺序方式存储, 原因是结构中的结点不变动, 内存是一维的, 必须将多维数组线性化 1 行优先 ( 行主序 ) 方式 : 将 (i+1)th 行向量紧接在 i th 行向量之后 : 特点 : 列下标变化快 Pascal C 等均是此方法 先排最右下标 ( 多维 ) 5 列优先 ( 列主序 ) 方法 特点行下标变化最快, 先排最左下标 ( 可推广至多维 ) Fortan 是用此方法 3 地址计算 一维存储地址 ( 内部实现 ) 基地址 开始结点存储地址 Loc(a 11 ). 维数 每维的上下界 ( 若下界固定, 则只须知道维长度 ) 每个元素占用的单元数 ( 元素大小 ):L 6 1
例 : 行主序 A[1..m,1..n] 原理 :a ij 的地址 = 基址 + 排在 a ij 之前的元素个数 每个元素的大小 Loc(a ij )=Loc(a 11 )+[(i-1) n+(j-1)] L 前 i-1 行结点总数 第 i 行上 a ij 之前的结点数 在 C 语言中, 是 A[0..m-1, 0..n-1], 故有 : Loc(a ij )=Loc(a 00 )+[i n+j] L 多维推广 : 以 C 为例, 行主序 思考 :A[c 1..d 1, c..d ] Loc(a ij )=Loc(a c1c )+[(i-c 1 ) (d -c +1)+(j-c )] L 特点 : 随机存取 i th 行前行数第 维长度 i th 行 a ij 之前结点数 7 8 用二维数组表示的特点 : 随机存取, 存储密度为 1 但对特殊和稀疏矩阵的存储则浪费空间, 尤其是大规模科学与工程计算 5..1 1 特殊矩阵 有规律 : 压缩后可找到地址变换公式, 保持随机存取功能 1. 对称阵 n 阶方阵 A, 若则称 A 为对称阵 因为矩阵元素关于主对角线对称, 故只存上三角或下三角元素即可, 节约近一半空间 不失一般性, 存储下三角 ( 包括主对角线 ), 以行主序存储 : 元素个数 9 10 压缩存储 : 将其存于向量 sa[0..n(n+1)/-1] 中 上三角中有 i < j, 只需交换上式的 j 和 i 即可得 : 如何访问 a ij? 必须将其与 sa[k] 的对应关系找出来 地址计算 : 1 下三角中有 j i. a ij 之前有 i 行 (0 ~ i-1) 第 i 行上 a ij 之前元素个数为 j(0 ~ j-1). 令 I=max (i, j),j=min (i, j), 则 k 和 i,j 之关系可统一表示为 :. 三角矩阵压缩方式同上, 在 sa 中多增加一个单元 : sa[0..n(n+1)/] 将 C 存于最后一个分量中 11 1
3. 对角矩阵总结 : 这类矩阵压缩存储后能找到地址计算公式, 使其保持随机存取的功能 13 5.. 稀疏矩阵 定义 : 设 A mn 中有 t 个非零元素, 若, 称 A 为稀疏矩阵 稀疏因子 : 一般非零元素分布无规律性 压缩存储 : 只存储非零元, 故须存储辅助信息, 才能确定其位置 三元组 (i,j,a ij ):( 行号, 列号, 非零元的值 ) 唯一确定一个非零元 当用三元组表示非零元时, 有两种压缩方式 : 顺序和链式 14 1. 三元组顺序表 ( 三元组表 ) 以行主序 ( 或列主序 ) 的顺序存储非零元, 跳过零元 得到一个其节点均是三元组的线性表, 称此顺序存储结构为三元组表 #define MaxSize 10000 typedef int DataType typedef struct{// 三元组 int i, j; DataType v; TripleNode; typedef struct{// 三元组表 TripleNode data[maxsize]; int m, n, t; // 行数, 列数, 非零元总数 TripleTable; 设 a,b 是 TripleTable 型变量 转置运算 15 16 1 方法一 : 按 B 的次序或按 A 的列序转置 A 的列是 B 的行, 故按 A 的列序转置, 所得 B 是按行主序存放的 基本思想 : 对 A 中每列, 从头至尾扫描 a.data, 找出所有列号为 col 的三元组 (0 col n-1), 将它们的行 列号互换后依次放入 b.data,, 即可得行主序表示的 B 的三元组 正确性 : 按 A 的列号递增序转置, 保证 B 按行号增序排列,B 中同一行号的三元组, 扫描 A 时所得三元组必有 i<j, 转置后保证按 B 的列号增序排列 例, 上图 17 18 3
void TransMatrix(TripleTable &a, TripleTable &b) {//A=>B int p, q, col; if (a.t == 0) Error( A is empty ); b.m = a.n; b.n = a.m; b.t = a.t ; // 行列数互换 q=0; // 指示转置过的三元组 for( col = 0; col < a.n ; col++)// 对 A 的每一列号 for( p = 0; p < a.t; p++)// 扫描 A 的三元组表 if (a.data[p].j == col) {// 找 A 的列号为 col 的三元组 b.data[q].i = a.data[p].j ; b.data[q].j = a.data[p].i ; b.data[q].v = a.data[p].v ; q++; 19 1 方法二 : 按 A 的行序转置 若简单的变换 a.data 的行和列, 则 b.data 为列主序存储, 要重排 但若预先确定 A 中每一列 ( 即 B 中每一行 ) 的第一个非零元在 b.data 中应有的位置, 则可正确转置 位置向量 : 0 思想先求出 A 中每一列的非零元个数, 可将第 col 列的非零元个数记入 pot[col+1] 中 step1: 初始化将所有 pot 中元素清 0. //O(n) step: 扫描 a.data, 将列号为 col 的非零元个数累加到 pot[col+1] 中 //O(t) step3: 令 pot[col]=pot[col-1]+pot[col] 1 col a.n-1 //O(n) step4: 扫描 a.data, 将 (i,col,v) 转置后放于 b.data[pot[col]] 中,pot[col]++. //O(t) 时间 O(n+t), 快速 key:pot[1..a.n]= 第 0~a.n-1 列的非零元个数 1 void FastTransMatrix(TripleTable &a, Tripletable &b) {//pot[0..a.n], 比 n 多 1 if (a.t == 0) Error( );//A 全零 b.m = a.n; b.n = a.n; b.t = a.t; for ( col = 0; col<=a.n ; col++) pot[col] = 0; //step1 初始化 for ( p = 0; p < a.t; p++) // step 扫描 a.data pot[a.data[p].j + 1]++; // 设 a.data[p].j = col pot[a.n] 是哨兵 for ( col = 1; col < a.n; col++)//step3. pot[a.n] 无用, 但第二个循环须统计 pot[col] = pot[col 1] + pot[col]; for ( p = 0; p < a.t; p++) {//step4 col = a.data[p].j; // 当前三元组列号. q = pot[col]++; b.data[q].i = a.data[p].j; b.data[q].j = a.data[p].i; b.data[q].v = a.data[p].v; 以上图为例, 3. 十字链表 上两种方式是顺序存储, 若非零元位置或个数经常发生变化, 会引起结点移动, 效率降低 此时宜用链式存储 例 :A A+B 稀疏矩阵的链接存储方式有多种, 这里仅介绍十字链表 结点结构. 带行表的三元组表 ( 顺序方式 ) 在行优先存储的三元组表中, 加入一个行表来记录稀疏矩阵压缩后每行非零元在三元组表中的起始位置 3 存储结构分别设两个指针数组作为各行 列单链表的头指针 4 4
typedef struct CLNode{ int i, j ; DataType v; struct CLNode * right, *down; CLNode; typedef struct t { CLNode *rhead[maxrow]; // 行链表头指针,MaxRow 在前定义 CLNode *chead[maxcol]; // 列 int m,n, t; CrossList; CrossList A; 5 6 1. 概念 是线性表的推广, 如将线性表中元素 a i 放宽到可以是自身的结构 定义 :, 它由 n 个元素构成的有限序列, 其中 a i 或是原子, 或是广义表 ( 子表 ) LS- 名字,n- 长度,n=0 为空表 一般用小写字母表示原子, 大写字母表示子表 表头 表尾 深度若, 则 a 1 成为表头 ( 首 ), 剩余元素构成的表为表尾 广义表是递归定义的, 展开到每一元素均为原子时括号的最大层数为深度 例 : E=( ) 空表, 长度 n = 0, 深度 d = 1. L=(a, b) n =,d = 1. ( 线性表 ) A=(x, L)=(x, (a, b)) n=, d=. a 1 为原子,a 为子表 B=(A, y)=((x, (a, b)), y) n =, d = 3. C=(A, B)=((x, (a, b)), ((x, (a, b)), y)) n =, d = 4. D=(a, D)=(a, (a, (a, ( )))) n =, d =. 若规定任何表都有名字, 则可在每个表前冠名 E( ) L(a, b) A(x, L(a, b)) 7 8 图示 运算求表头 表尾 head(a) = x, tail(a) = ((a, b)) // 表尾是表, 表头不一定 head(tail(a)) = (a, b) 表 各种表之关系 Note: 和 不同 为空表 n=0, 不能求表头和表尾 为非空表,n=1. 可求表头和尾 : 9 30 5
. 存储结构因为广义表数据元素可具有不同结构, 故难以用顺序方式存储 一般用链接方式存储, 称之为广义链表 (1) 广义表的头尾链表表示方法 表结点 : 图示 E=NIL 原子结点 : 存储结构见书上说明 31 3 特点 1 除空表的表头指针为空外, 头指针均指向表结点 任一表结点的 hp 均指向表头部 ( 原子结点或表结点 ) 任一表结点的 tp 均指向表尾部 ( 当表尾部为空表时, tp=nil, 否则必指向表结点 ) 3 易分清表中原子和子表所在层次 如 x L 在第一层,a b 在第二层 4 最高层的表结点数即为广义表的长度 5 浪费空间, 易求表长和表深度 () 单链表示法 模仿线性表的单链表结构, 当所有元素为原子时, 等价于单链表 结点结构 : 图示 :E=NIL C=(A, B)=((x, (a, b)), ((x, (a, b)), y)) =(A(x, L(a, b)), B(A(x, L(a, b)), y)) 33 34 存储结构说明 typedef struct GLNode{ int atom; // 亦可定义为枚举类型, 标志域 struct GLNode *slink; // 指向同层后继 union { struct GLNode *slink; // 指向子表的第一个结点 DataType data; // 原子结点数据域 optval; // 候选值 *GList; 缺点 : 1 若要在某一表中开始处插入或删除一个结点, 则要找出所有指向该结点的指针, 逐一加以修改 例如, 上图中, 删除 A 表中的 x, 修改 A 的头指针外, 须修改来自于 B C 表的指针, 引用来源点不易知道 删除一个表可能导致错误 例如, 删除 A 表时,A 的所有结点释放后, 会引起 B C 表的错误 35 36 6
改进 引入表头结点, 使子表内部的变化不会涉及外部元素的变化, 插删第一个结点方便 头结点和其他结点结构相同, 只是以示区别 : (3) 双链表示法该方法类似于第 6 章的二叉链表 结点结构 删除表时, 头结点引用计数减 1,, 仅当引用计数为 0 时, 才释放表中所有结点 存储说明 typedef struct GLNode{ DataType data; // 子表名字或原子数据 struct GLNode *link1, *link; *GList; 37 38 图示 例子 ( 姓名, 工资收入 ( 基本工资, 午餐补助, 津贴 ), 扣除 ( 公积金, 水电费, 其它 ), 实发工资 ) 特点 1 简洁方便, 类似于二叉链表, 可借助于二叉链表表示处理, 易求长度深度 在表结点中保存了子表的名字信息, 有时子表名字和原子信息同样重要 39 3. 运算 : 略 40 7