Microsoft PowerPoint - DS_Ch5.ppt [兼容模式]

Size: px

Start display at page:

Download "Microsoft PowerPoint - DS_Ch5.ppt [兼容模式]"

赴卓
5 years ago
Views:

1 数据结构 Ch.5 数组和广义表计算机学院肖明军多维数组是最易处理的非线性结构因为各元素类型一致, 各维上下界固定, 所以它最容易线性化, 故可看做是线性表的拓广例如 : 二维数组可以看做是由列向量组成的线性表 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

.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.

2 例 : 行主序 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 但对特殊和稀疏矩阵的存储则浪费空间, 尤其是大规模科学与工程计算特殊矩阵有规律 : 压缩后可找到地址变换公式, 保持随机存取功能 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.

三元组 (i,j,a ij ):( 行号, 列号, 非零元的值 ) 唯一确定一个非零元当用三元组表示非零元时, 有两种压缩方式 : 顺序和链式 14 1.

typedef int DataType typedef struct{// 三元组 int i, j; DataType v; TripleNode; typedef struct{//

转置运算 15 16 1 方法一 : 按 B 的次序或按 A 的列序转置 A 的列是 B 的行, 故按 A 的列序转置, 所得 B 是按行主序存放的基本思想 : 对 A 中每列, 从头至尾扫描

3 3. 对角矩阵总结 : 这类矩阵压缩存储后能找到地址计算公式, 使其保持随机存取的功能稀疏矩阵定义 : 设 A mn 中有 t 个非零元素, 若, 称 A 为稀疏矩阵稀疏因子 : 一般非零元素分布无规律性压缩存储 : 只存储非零元, 故须存储辅助信息, 才能确定其位置三元组 (i,j,a ij ):( 行号, 列号, 非零元的值 ) 唯一确定一个非零元当用三元组表示非零元时, 有两种压缩方式 : 顺序和链式三元组顺序表 ( 三元组表 ) 以行主序 ( 或列主序 ) 的顺序存储非零元, 跳过零元得到一个其节点均是三元组的线性表, 称此顺序存储结构为三元组表 #define MaxSize typedef int DataType typedef struct{// 三元组 int i, j; DataType v; TripleNode; typedef struct{// 三元组表 TripleNode data[maxsize]; int m, n, t; // 行数, 列数, 非零元总数 TripleTable; 设 a,b 是 TripleTable 型变量转置运算方法一 : 按 B 的次序或按 A 的列序转置 A 的列是 B 的行, 故按 A 的列序转置, 所得 B 是按行主序存放的基本思想 : 对 A 中每列, 从头至尾扫描 a.data, 找出所有列号为 col 的三元组 (0 col n-1), 将它们的行列号互换后依次放入 b.data,, 即可得行主序表示的 B 的三元组正确性 : 按 A 的列号递增序转置, 保证 B 按行号增序排列,B 中同一行号的三元组, 扫描 A 时所得三元组必有 i<j, 转置后保证按 B 的列号增序排列例, 上图

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.

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 中应有的位置, 则可正确转置位置向量 : 0 思想先求出 A 中每一列的非零元个数, 可将第 col 列的非零元个数记入 pot[col+1] 中 step1: 初始化将所有 pot 中元素清 0. //O(n) step: 扫描 a.

data, 将 (i,col,v) 转置后放于 b.data[pot[col]] 中,pot[col]++. //O(t) 时间 O(n+t), 快速 key:pot[1..a.n]= 第 0~a.

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.

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.

4 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 {

一般用小写字母表示原子, 大写字母表示子表表头表尾深度若, 则 a 1 成为表头 ( 首 ), 剩余元素构成的表为表尾广义表是递归定义的, 展开到每一元素均为原子时括号的最大层数为深度例 : E=( )

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.

5 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; 概念是线性表的推广, 如将线性表中元素 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. 可求表头和尾 :

. 存储结构因为广义表数据元素可具有不同结构, 故难以用顺序方式存储一般用链接方式存储, 称之为广义链表 (1) 广义表的头尾链表表示方法表结点 : 图示 E=NIL 原子结点 :

当表尾部为空表时, tp=nil, 否则必指向表结点 ) 3 易分清表中原子和子表所在层次如 x L 在第一层,a b 在第二层 4 最高层的表结点数即为广义表的长度 5 浪费空间,

b)), y)) =(A(x, L(a, b)), B(A(x, L(a, b)), y)) 33 34 存储结构说明 typedef struct GLNode{ int atom; //

DataType data; // 原子结点数据域 optval; // 候选值 *GList; 缺点 : 1 若要在某一表中开始处插入或删除一个结点, 则要找出所有指向该结点的指针,

6 . 存储结构因为广义表数据元素可具有不同结构, 故难以用顺序方式存储一般用链接方式存储, 称之为广义链表 (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)) 存储结构说明 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 表的错误

7 改进引入表头结点, 使子表内部的变化不会涉及外部元素的变化, 插删第一个结点方便头结点和其他结点结构相同, 只是以示区别 : (3) 双链表示法该方法类似于第 6 章的二叉链表结点结构删除表时, 头结点引用计数减 1,, 仅当引用计数为 0 时, 才释放表中所有结点存储说明 typedef struct GLNode{ DataType data; // 子表名字或原子数据 struct GLNode *link1, *link; *GList; 图示例子 ( 姓名, 工资收入 ( 基本工资, 午餐补助, 津贴 ), 扣除 ( 公积金, 水电费, 其它 ), 实发工资 ) 特点 1 简洁方便, 类似于二叉链表, 可借助于二叉链表表示处理, 易求长度深度在表结点中保存了子表的名字信息, 有时子表名字和原子信息同样重要运算 : 略 40 7

PowerPoint Presentation

PowerPoint Presentation 数据结构与数据库课号 21050301 2012 秋第五章数组 5.1 数组的定义 5.2 数组的顺序表示和实现 5.3 矩阵的压缩存储 5.3.1 特殊矩阵 5.3.2 稀疏矩阵 2 同理, 一个 n 维数组类型可以定义为其数据元素为 n-1 维数组类型的一维数组类型数组一旦被定义, 它的维数和维界就不再改变因此, 除了结构的初始化和销毁之外, 数组只有存取元素和修改元素值的操作抽象数据类型数组的定义参见教材