第五章 数组和广义表.

Presentation on theme: "第五章 数组和广义表."— Presentation transcript:

1 第五章 数组和广义表

2 5.1 数组的定义 5.2 数组的顺序表示和实现 5.3 稀疏矩阵的压缩存储 5.4 广义表的定义 5.5 广义表的存储结构

3 5.1 数组的定义 ADT Array { 数据对象： D＝{aj1,j2, ...,,ji,jn| ji =0,...,bi -1, i=1,2,..,n } 数据关系： R＝{R1, R2, ..., Rn} Ri＝{<aj1,... ji,... jn , aj1, ...ji +1, ...jn > | 0  jk  bk -1, 1  k  n 且k  i, 0  ji  bi -2, i=2,...,n } } ADT Array 基本操作:

4 二维数组的定义: 数据对象: D = {aij | 0≤i≤b1-1, 0 ≤j≤b2-1} 数据关系: R = { ROW, COL } ROW = {<ai,j,ai+1,j>| 0≤i≤b1-2, 0≤j≤b2-1} COL = {<ai,j,ai,j+1>| 0≤i≤b1-1, 0≤ j≤b2-2}

5 基本操作： InitArray(&A, n, bound1, ..., boundn) DestroyArray(&A)
Value(A, &e, index1, ..., indexn) Assign(&A, e, index1, ..., indexn)

6 InitArray(&A, n, bound1, ..., boundn)
返回OK。

7 DestroyArray(&A) 操作结果：销毁数组A。

8 Value(A, &e, index1, ..., indexn)
初始条件：A是n维数组，e为元素变量， 随后是n 个下标值。 操作结果：若各下标不超界，则e赋值为 所指定的A 的元素值，并返 回OK。

9 Assign(&A, e, index1, ..., indexn)
初始条件：A是n维数组，e为元素变量， 随后是n 个下标值。 操作结果：若下标不超界，则将e的值赋 给所指定的A的元素，并返回 OK。

10 5.2 数组的顺序表示和实现 类型特点: 1) 只有引用型操作，没有加工型操作； 2) 数组是多维的结构，而存储空间是 一个一维的结构。
5.2 数组的顺序表示和实现 类型特点: 1) 只有引用型操作，没有加工型操作； 2) 数组是多维的结构，而存储空间是 一个一维的结构。 有两种顺序映象的方式: 1)以行序为主序(低下标优先)； 2)以列序为主序(高下标优先)。

11 LOC(i,j) = LOC(0,0) + (b2×i＋j)× L
以“行序为主序”的存储映象 例如： a0,0 a0,1 a0,2 a0,0 a0,1 a0,2 a1,0 a1,1 a1,2 a1,0 a1,1 a1,2 L 二维数组A中任一元素ai,j 的存储位置 LOC(i,j) = LOC(0,0) + (b2×i＋j)× L 称为基地址或基址。

12 推广到一般情况，可得到 n 维数组数据元素存储位置的映象关系
LOC(j1, j2, ..., jn ) = LOC(0,0,...,0) + ∑ ci ji =1 i 其中 cn = L，ci-1 = bi ×ci , 1 < i  n。 称为 n 维数组的映象函数。数组元素 的存储位置是其下标的线性函数。

13 5.3 矩阵的压缩存储 何谓压缩存储？ 假若值相同的元素或者零元素在矩阵中的分布有一定规律，则我们称此类矩阵为特殊矩阵，反之，称之为稀疏矩阵。

14 5.3.1特殊矩阵 1、对称矩阵 在一个n阶方阵A中，若元素满足下述性质： aij=aji 0≦i,j≦n-1 则称A为对称矩阵。
a20 a a23 ……………….. an-1 0 a n-1 1 a n-1 2 …a n-1 n-1

15 存在对应关系： k=i*(i+1)/2+j 当 i≧j k=j*(j+1)/2+i 当 i<j 令 I=max(i,j)， J=min(i,j)，则k和 i, j的对应关系可统一为： k=I*(I+1)/2+J ≦ k<n(n+1)/2

16 =LOC(sa[0])+k*d=LOC(sa[0]+[I*(I+1)/2+J]*d 由此，称sa[n(n+1)/2]为阶对称矩阵A的压缩存储
aij的地址可用下列式计算： LOC(aij)=LOC(sa[k]) =LOC(sa[0])+k*d=LOC(sa[0]+[I*(I+1)/2+J]*d 由此，称sa[n(n+1)/2]为阶对称矩阵A的压缩存储 k= n(n-1)/ n(n-1)/2-1 例如a21和a12均存储在 sa[4]中，这是因为 k=I*(I+1)/2+J=2*(2+1)/2+1=4 a00 a10 a11 a20 …… an-1 0 an-1,n-1

17 2、三角矩阵 a00 a01 … a 0 n a00 c … c c a11 … a 1 n a10 a11 … c ………………… …………….. c c … a n-1 n an-1 0 an-1 1 … an-1 n-1 (a)上三角矩阵 (b)下三角矩阵

18 上三角矩阵sa[k]和aij的对应关系是： i(2n-i+1)/2+j-i 当i≦j n(n+1)/2 当i>j 下三角矩阵sa[k]和aij对应关系是： i(i+1)/2+j i≧j n(n+1)/2 i>j k= k=

19 3、对角矩阵 a00 a01 a10 a11 a12 a21 a22 a23 …. ….. …. 图 对角矩阵
…. ….. … 图 对角矩阵 an-2 n-3 an-2 n-2 an-2 n-1 an-1 n-2 an-1 n-1

20 由此，我们称sa[0..3*n-2]是阶三对角带状矩阵A的压缩存储表示。
… a n-1 n-2 a n-1 n-1 K= … … 3n n-1 非零元素aij的地址为： LOC(i,j)=LOC(0,0)+[3*i-1+(j-i+1)]*d =LOC(0,0)+(2i+j)*d 由此，我们称sa[0..3*n-2]是阶三对角带状矩阵A的压缩存储表示。

21 5.3.2 稀疏矩阵 何谓稀疏矩阵？ 假设 m 行 n 列的矩阵含 t 个非零元素，则称 为稀疏因子。
通常认为   0.05 的矩阵为稀疏矩阵。

22 加上(6,7)这一对行、列值便可作为下列矩阵M的另一种描述。
例如，下列三元组表 ((1,2,12)(1,3,9),(3,1,- 3),(3,6,14),(4,3,24), (5,2,18),(6,1,15),(6,4,-7)) 加上(6,7)这一对行、列值便可作为下列矩阵M的另一种描述。 –7 – 图 稀疏矩阵M和T M= T=

23 稀疏矩阵的压缩存储方法: 一、三元组顺序表 二、行逻辑链接的顺序表 三、 十字链表

24 一、三元组顺序表 #define MAXSIZE 12500 typedef struct {
int i, j; //该非零元的行下标和列下标 ElemType e; // 该非零元的值 } Triple; // 三元组类型 typedef union { Triple data[MAXSIZE + 1]; int mu, nu, tu; } TSMatrix; // 稀疏矩阵类型

25 如何求转置矩阵？

26 用常规的二维数组表示时的算法 for (col=1; col<=nu; ++col) for (row=1; row<=mu; ++row) T[col][row] = M[row][col]; 其时间复杂度为: O(mu×nu)

27 用“三元组”表示时如何实现？

28 首先应该确定每一行的第一个非零元在三元组中的位置。
cpot[1] = 1; for (col=2; col<=M.nu; ++col) cpot[col] = cpot[col-1] + num[col-1];

29 Void transmatrix(tripletable a,tripletable b) { int p q col; b. m=a
Void transmatrix(tripletable a,tripletable b) { int p q col; b.m=a.n; b.n=a.m; b.t=a.t; if(b.t<=0) printf(“A=0\n”); q=0;

30 for(col=1;col<=a. n;col++) for(p=0;p<=a. t;p++) if(a. data[p]
for(col=1;col<=a.n;col++) for(p=0;p<=a.t;p++) if(a.data[p].j==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++; } 算法的时间复杂度为O(n*n2)

31 快速转置算法如下： void fasttranstri(tritupletable b,tritupletable a){ int p,q,col,k; int num[0..a.n],copt[0..a.n]; b.m=a.n; b.n=a.m; b.t=a.t; if(b.t<=0) printf(“a=0”\n); for(col=1;col<=a.u;++col) num[col]=0; for(k=1;k<=a.t;++k) ++num[a.data[k].j];

32 cpot[0]=1; for(col=2;col<=a
cpot[0]=1; for(col=2;col<=a.t;++col) cpot[col]=cpot[col-1]+num[col-1]; for(p=1;p<=a.t;++p){ col=a.data[p].j; q=cpot[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; ++cpot[col]; }

33 分析算法FastTransposeSMatrix的时间复杂度：
for (col=1; col<=M.nu; ++col) … … for (t=1; t<=M.tu; ++t) … … for (col=2; col<=M.nu; ++col) … … for (p=1; p<=M.tu; ++p) … … 时间复杂度为: O(M.nu+M.tu)

34 二、行逻辑链接的顺序表 三元组顺序表又称有序的双下标法，它的特点是，非零元在表中按行序有序存储，因此便于进行依行顺序处理的矩阵运算。然而，若需随机存取某一行中的非零元，则需从头开始进行查找。

35 Triple data[MAXSIZE + 1]; int rpos[MAXMN + 1]; int mu, nu, tu;
#define MAXMN 500 typedef struct { Triple data[MAXSIZE + 1]; int rpos[MAXMN + 1]; int mu, nu, tu; } RLSMatrix; // 行逻辑链接顺序表类型

36 矩阵乘法的精典算法: for (i=1; i<=m1; ++i) for (j=1; j<=n2; ++j) { Q[i][j] = 0; for (k=1; k<=n1; ++k) Q[i][j] += M[i][k] * N[k][j]; } 其时间复杂度为: O(m1×n2×n1)

37 当M和N是稀疏矩阵并用三元组表存储结构时，就不能套用上述算法。假设M和N分别为：
0 2 1 0 -2 4 0 0 M= N= 则Q=M*N为： 0 6 -1 0 0 4 Q=

38 它们的三元组、和分别为： i j v i j v i j v q.data m.data n.data

39 for (arow=1; arow<=M.mu; ++arow) { // 处理M的每一行 ctemp[] = 0; // 累加器清零
两个稀疏矩阵相乘（QMN） 的过程可大致描述如下： Q初始化； if Q是非零矩阵 { // 逐行求积 for (arow=1; arow<=M.mu; ++arow) { // 处理M的每一行 ctemp[] = 0; // 累加器清零 计算Q中第arow行的积并存入ctemp[] 中； 将ctemp[] 中非零元压缩存储到Q.data； } // for arow } // if

40 void multsmatrix( rtripletable a, rtripletable b, rtripletable c){ if(a.n!=b.m){ printf(“error\n”); exit(0); } c.m=a.m; c.n=b.n; c.t=0; if(a.t*b.t!=0){ for(arow=1;arow<=a.m;++arow){ ctemp[arow]=0;

41 c. rpos[arow]=c. t+1; for(p=a. rops[arow];p<a
c.rpos[arow]=c.t+1; for(p=a.rops[arow];p<a.rpos[arow+1];++p){ brow=a.data[p].j; if(brow<b.t) t=b.rpos[brow+1] else t=b.t+1; for(q=b.rpos[brow]; q<t;++q){ ccol=n.data[q].j; ctemp[ccol]+=a.data[p].v*b.data[q].v; }

42 for(ccol=1;ccol<=c. n;++ccol) if(ctemp[ccol]){ if(++c
for(ccol=1;ccol<=c.n;++ccol) if(ctemp[ccol]){ if(++c.t>maxsize) exit(0); c.data[c.t]={arow,ccol,ctemp[ccol]}; }

43 三、 十字链表 ^ 1 1 3 1 4 5 ^ ^ 2 2 -1 ^ ^ 3 1 2 ^ ^

44 5.4 广义表的定义 ADT Glist { 数据对象：D＝{ei | i=1,2,..,n; n≥0;
ei∈AtomSet 或 ei∈GList, AtomSet为某个数据对象 } 数据关系： LR＝{<ei-1, ei >| ei-1 ,ei∈D, 2≤i≤n} } ADT Glist 基本操作:

45 广义表是递归定义的线性结构， 例如: A = ( ) F = (d, (e)) D = ((a,(b,c)), F)
LS = ( 1, 2, , n ) 其中：i 或为原子 或为广义表 例如: A = ( ) F = (d, (e)) D = ((a,(b,c)), F) C = (A, D, F) B = (a, B) = (a, (a, (a,  , ) ) )

46 例如： 广义表是一个多层次的线性结构 D D=(E, F) E F 其中: E=(a, (b, c)) F=(d, (e)) a ( ) d
( ) d ( ) e b c

47 广义表 LS = ( 1, 2, …, n )的结构特点: 1) 广义表中的数据元素有相对次序；
1) 广义表中的数据元素有相对次序； 2) 广义表的长度定义为最外层包含元素个数； 3) 广义表的深度定义为所含括弧的重数； 注意：“原子”的深度为 0 　“空表”的深度为 1 4) 广义表可以共享； 5) 广义表可以是一个递归的表。 递归表的深度是无穷值，长度是有限值。

48 Head( D ) = E Tail( D ) = ( F )
6) 任何一个非空广义表 LS = ( 1, 2, …, n) 均可分解为 表头 Head(LS) = 1 和 表尾 Tail(LS) = ( 2, …, n) 两部分。 例如: D = ( E, F ) = ((a, (b, c))，F ) Head( D ) = E Tail( D ) = ( F ) Head( E ) = a Tail( E ) = ( ( b, c) ) Head( (( b, c)) ) = ( b, c) Tail( (( b, c)) ) = ( ) Head( ( b, c) ) = b Tail( ( b, c) ) = ( c ) Head( ( c ) ) = c Tail( ( c ) ) = ( )

49 基本操作  结构的创建和销毁  状态函数  插入和删除操作  遍历 InitGList(&L); DestroyGList(&L);
 结构的创建和销毁 InitGList(&L); DestroyGList(&L); CreateGList(&L, S); CopyGList(&T, L); 基本操作  状态函数 GListLength(L); GListDepth(L); GListEmpty(L); GetHead(L); GetTail(L);  插入和删除操作 InsertFirst_GL(&L, e); DeleteFirst_GL(&L, &e);  遍历 Traverse_GL(L, Visit());

50 5.5 广义表的存储结构 通常采用头、尾指针的链表结构 表结点: 原子结点： tag=1 hp tp tag=0 data

51 构造存储结构的两种分析方法: 1) 表头、表尾分析法： 空表 ls=NIL 非空表 ls 指向表尾的指针 tag=1 指向表头的指针
若表头为原子，则为 tag=0 data 否则，依次类推。

52

53    L = ( ) L = ( a, ( x, y ), ( ( x ) ) ) a ( x, y ) ( ) ( ) x L 1
( ) ( ) x L  1 1 1  1 1 0 a  1 0 a

54 …  2) 子表分析法： 空表 ls=NIL 非空表 ls 1 1 1 指向子表1 的指针 指向子表2 的指针 指向子表n 的指针
若子表为原子，则为 tag=0 data 否则，依次类推。

55 例如: LS=( a, (x,y), ((x)) ) ls  a (x, y) ((x))