Ch.5 数组和广义表 黄刘生 中国科学技术大学计算机系 国家高性能计算中心（合肥）

Presentation on theme: "Ch.5 数组和广义表 黄刘生 中国科学技术大学计算机系 国家高性能计算中心（合肥）"— Presentation transcript:

1 Ch.5 数组和广义表 黄刘生 中国科学技术大学计算机系 国家高性能计算中心（合肥） 2008.3.25

2 §5.1 多维数组 多维数组 是最易处理的非线性结构。因为各元素类型一致，各维上下界固定，所以它最容易线性化，故可看做是线性表的拓广。例如：二维数组可以看做是由列向量组成的线性表。

3 §5.1 多维数组 结构特性 例：二维数组 ∀aij∈Amn，它属于两个向量；ith行和jth列。
3 3

4 §5.1 多维数组 非线性特征 ith行：前驱aij-1，后继aij+1 jth列：前驱ai-1j，后继ai+1j 仅有一个开始结点：a11
仅有一个终端节点：amn 其他边界上的结点只有一个直接前驱或一个直接后继，类似的m维数组 的每一个元素都属于m个向量。 4 4

5 §5.1 多维数组 存储 一般均采用顺序方式存储，原因是结构中的结点不变动，内存是一维的，必须将多维数组线性化。 行优先（行主序）方式：
将(i+1)th行向量紧接在ith行向量之后： 特点：列下标变化快。Pascal、C等均是此方法。先排最右下标（多维）。 5 5

6 §5.1 多维数组 列优先（列主序）方法 特点行下标变化最快，先排最左下标（可推广至多维）。Fortan是用此方法。 地址计算
一维存储地址（内部实现）。 基地址——开始结点存储地址Loc(a11). 维数——每维的上下界（若下界固定，则只须知道维长度） 每个元素占用的单元数（结点大小）：L 6 6

7 §5.1 多维数组 例：行主序Am×n 。 A[1..m,1..n] 原理： aij的地址=基址+排在aij之前的元素个数×每 个元素的大小
Loc(aij)=Loc(a11)+[(i-1)×n+(j-1)] ×L 前i-1行结点总数 第i行上aij之前的结点数 在C语言中，Am×n是A[0..m-1 , 0..n-1]，故有： Loc(aij)=Loc(a00)+[i×n+j] ×L 7 7

8 §5.1 多维数组 多维推广：以C为例，行主序。 思考：A[c1..d1 , c2..d2]
Loc(aij)=Loc(ac1c2)+[(i-c1) ×(d2-c2+1)+(j-c2)] ×L ith行前行数 第2维长度 ith行aij之前结点数 特点：随机存取。 8 8

9 §5.2 矩阵的压缩存储 用二维数组表示的特点：随机存取，存储密度为1。但对特殊和稀疏矩阵的存储则浪费空间，尤其是大规模科学与工程计算。
§5.2.1 特殊矩阵 有规律：压缩后可找到地址变换公式，保持随机存取功能。 9 9

10 §5.2 矩阵的压缩存储 对称阵 因为矩阵元素关于主对角线对称，故只存上三角或下三角元素即可，节约近一半空间。
n阶方阵A，若aij=aji 0≤i, j≤n-1, 则称A为对称阵。 因为矩阵元素关于主对角线对称，故只存上三角或下三角元素即可，节约近一半空间。 不失一般性，存储下三角（包括主对角线），行主序存储： 元素个数 10 10

11 §5.2 矩阵的压缩存储 压缩存储： 将其存于向量sa[0..n(n+1)/2－1]中。
如何访问aij？必须将其与sa[k]的对应关系找出来。 地址计算： 下三角中有i ≥ j. aij之前有i行（0 ~ i-1） 第i行上aij之前元素个数为j(0 ~ j-1). 11 11

12 §5.2 矩阵的压缩存储 上三角中有i < j ∵aji=aij ,只需交换上式的j和i即可得：
令I=max (i , j)，J=min (i , j)，则k和i，j之关系可统一表示为： 三角矩阵 压缩方式同上，在sa中多增加一个单元： sa[0..n(n+1)/2] 将C存于最后一个分量中。 12 12

13 §5.2 矩阵的压缩存储 总结：这类矩阵压缩存储后能找到地址计算公式，使其保持随机存取的功能。 对角矩阵 Ex.5.5，5.6，5.7 13

14 §5.2 矩阵的压缩存储 § 5.2.2 稀疏矩阵 定义：设Amn中有t个非零元素，若t≪m×n，称A为稀疏矩阵。
稀疏因子： 一般非零元素分布无规律性 压缩存储： 只存储非零元，故须存储辅助信息，才能确定其位置。 三元组(i，j，aij)：（行号，列号，非零元的值）唯一确定一个非零元。 当用三元组表示非零元时，有两种压缩方式：顺序和链式。 14 14

15 §5.2 矩阵的压缩存储 三元组顺序表（三元组表）
以行主序（或列主序）的顺序存储非零元，跳过零元。得到一个其节点均是三元组的线性表，称此顺序存储结构为三元组表。 #define MaxSize 10000 typedef int DataType typedef struct{//三元组 int i, j； DataType v; }TripleNode; 15 15

16 A[i][j]=B[j][i] 0≤i≤m-1, 0≤j≤n-1
typedef struct{//三元组表 TripleNode data[MaxSize]; int m, n, t; //行数，列数，非零元总数 }TripleTable; 设a，b是TripleTable型变量。 转置运算 Am×n  Bn×m A[i][j]=B[j][i] 0≤i≤m-1, 0≤j≤n-1 16 16

17 17 17

18 §5.2 矩阵的压缩存储 方法一：按B的次序或按A的列序转置。 ∵A的列是B的行，故按A的列序转置，所得B是按行主序存放的。
基本思想：对A中每列，从头至尾扫描a.data，找出所有列号为col的三元组(0≤col≤n-1)，将它们的行、列号互换后依次放入b.data，即可得行主序表示的B的三元组。 正确性：∵按A的列号递增序转置，保证B按行号增序排列，B中同一行号的三元组，扫描A时所得三元组( i,col,v1 ), ( j,col,v2 )必有i<j，转置后保证按B的列号增序排列。 例，上图。 18 18

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

20 §5.2 矩阵的压缩存储 方法二：按A的行序转置。
若简单的变换a.data的行和列，则b.data为列主序存储，要重排。但若预先确定A中每一列（即B中每一行）的第一个非零元在b.data中应有的位置，则可正确转置。 位置向量： 20 20

21 §5.2 矩阵的压缩存储 时间：O(n+t)，快速
思想：先求出A中每一列的非零元个数，可将第col列的非零元个数记入pot[col+1]中。 step1：初始化将所有pot中元素清0. //O(n) step2：扫描a.data，将列号为col的非零元个数累加到pot[col+1]中，即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列的非零元个数 //step2 pot[0..a.n-1]=第0~a.n-1列的非零元转置后的起址 //step3 21 21

22 void FastTransMatrix(TripleTable &a , Tripletable &b) {
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++) // step2扫描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的行号. b.data[q].i = a.data[p].j; b.data[q].j = a.data[p].i; b.data[q].v = a.data[p].v; } 22 22

23 §5.2 矩阵的压缩存储 以上图为例，A4×5 23 23

24 §5.2 矩阵的压缩存储 Ex. 5.22 带行表的三元组表。（顺序方式）
在行优先存储的三元组表中，加入一个行表来记录稀疏矩阵压缩后每行非零元在三元组表中的起始位置。 Ex. 5.22 24 24

25 §5.2 矩阵的压缩存储 十字链表 上两种方式是顺序存储，若非零元位置或个数经常发生变化，会引起结点移动，效率低。此时宜用链式存储。
例：A←A+B 稀疏矩阵的链接存储方式有多种，这里仅介绍十字链表 结点结构 存储结构 分别设两个指针数组作为各行、列单链表的头指针。 25 25

26 §5.2 矩阵的压缩存储 typedef struct CLNode{ int i, j ; DataType v;
struct CLNode * right, *down; }CLNode; typedef struct { CLNode *rhead[MaxRow]; //行链表头指针，MaxRow在前定义 CLNode *chead[MaxCol]; //列… int m, n, t; }CrossList; CrossList A; 26 26

27 27 27

28 §5.3 广义表（Lists） 概念 是线性表的推广，如将线性表中元素ai放宽到可以是自身的结构。
定义：LS=(a1, a2, … , an), n≥0, 它由n个元素构成的有限序列，其中ai或是原子，或是广义表（子表）。 LS-名字，n-长度，n=0为空表。 一般用小写字母表示原子，大写字母表示子表。 表头、表尾、深度 若 LS≠Φ，则a1成为表头（首），剩余元素构成的表 (a2, … , an)为表尾。广义表是递归定义的，展开到每一元素均为原子时括号的最大层数为深度。 28 28

29 §5.3 广义表（Lists） 例 E=( ) ——空表，长度n = 0，深度d = 1.
L=(a, b) ——n = 2，d = 1. （线性表） A=(x, L)=(x, (a, b)) ——n=2, d=2. a1为原子，a2为子表 B=(A, y)=((x, (a, b)), y) ——n = 2, d = 3. C=(A, B)=((x, (a, b)), ((x, (a, b)), y)) ——n = 2, d = 4. D=(a, D)=(a, (a, (a, (…)))) ——n = 2, d = ∞ . 若规定任何表都有名字，则可在每个表前冠名。 E( ) L(a, b) A(x, L(a, b)) 29 29

30 §5.3 广义表（Lists） 图示 各种表之关系 30 30

31 §5.3 广义表（Lists） 运算 求表头、表尾。人工智能语言Lisp——表处理语言的基本结构
head(A) = x, tail(A) = ((a, b)) //表尾是表，表头不一定 head(tail(A)) = (a, b) ——表 Note： ( )和(( ))不同。 ( )为空表n=0，不能求表头和表尾。 (( )) 为非空表，n=1. 可求表头和尾： head[ (( )) ]=( )， tail[ (( )) ]=( ) n 31 31

32 §5.3 广义表（Lists） 存储结构 因为广义表数据元素可具有不同结构，故难以用顺序方式存储。一般用链接方式存储，称之为广义链表。
广义表的头尾链表表示方法 表结点： 原子结点： 存储结构见书上说明 32 32

33 §5.3 广义表（Lists） 图示 E=NIL 33 33

34 §5.3 广义表（Lists） 特点 除空表的表头指针为空外，头指针均指向表结点。 任一表结点的hp均指向表头部（原子结点或表结点）
任一表结点的tp均指向表尾部（当表尾部为空表时，tp=NIL，否则必指向表结点） 易分清表中原子和子表所在层次。 如x、L在第一层，a、b在第二层。 最高层的表结点数即为广义表的长度。 浪费空间，易求表长和表深度。 34 34

35 §5.3 广义表（Lists） (2) 单链表示法 模仿线性表的单链表结构，当所有元素为原子时，等价于单链表。 结点结构 35 35

36 (2) 单链表示法 图示：E=NIL C=(A, B)=((x, (a, b)), ((x, (a, b)), y))
=(A(x, L(a, b)), B(A(x, L(a, b)), y)) 36 36

37 §5.3 广义表（Lists） (2) 单链表示法 存储结构说明 typedef struct GLNode{
int atom; //亦可定义为枚举类型，标志域 struct GLNode *link; //指向同层后继 union { struct GLNode *slink; //指向子表的第一个结点 DataType data； //原子结点数据域 }optval; //候选值 } *GList; 37 37

38 §5.3 广义表（Lists） (2) 单链表示法 缺点
若要在某一表中开始处插入或删除一个结点，则要找出所有指向该结点的指针，逐一加以修改。 例如，上图中，删除A表中的x，修改A的头指针外，须修改来自于B、C表的指针，引用来源点不易知道。 删除一个表可能导致错误。 例如，删除A表时，A的所有结点释放后，会引起B、C表的错误。 38 38

39 引入表头结点，使子表内部的变化不会涉及外部元素的变化，插删第一个结点方便。头结点和其他结点结构相同，只是以示区别：
改进 引入表头结点，使子表内部的变化不会涉及外部元素的变化，插删第一个结点方便。头结点和其他结点结构相同，只是以示区别： 删除表时，头结点引用计数减1，仅当引用计数为0时，才释放表中所有结点。 39 39

40 §5.3 广义表（Lists） (3) 双链表示法 该方法类似于第6章的二叉链表。 结点结构 存储说明
(3) 双链表示法 该方法类似于第6章的二叉链表。 结点结构 存储说明 typedef struct GLNode{ DataType data; //子表名字或原子数据 struct GLNode *link1, *link2; } *GList; 40 40

41 图示 特点 简洁方便，类似于二叉链表，可借助于二叉链表表示处理，易求长度深度。
在表结点中保存了子表的名字信息，有时子表名字和原子信息同样重要。 41 41

42 (3) 双链表示法 例子 (姓名,工资收入(基本工资,餐补,津贴),扣除(公积金,水电费,其它),实发工资) 3. 运算：略 42 42

43 Ex. 5.10，5.12，5.13（按照书上的定义） 43 43