第五章 数组和广义表.

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

1 第五章 数组和广义表

2 5.1 数组的类型定义 5.2 数组的顺序表示和实现 5.3 稀疏矩阵的压缩存储 5.3 广义表的类型定义 5.4 广义表的表示方法 5.5 广义表操作的递归函数

3 5.1 数组的类型定义 ADT Array { 数据对象：
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 LOC(i,j) = LOC(0,0) + (b1×j＋i)× L
以“列序为主序”的存储映象 例如： a0,0 a0,1 a0,2 a0,0 a1,0 a0,1 a1,1 a0,2 a1,2 a1,0 a1,1 a1,2 L 二维数组A中任一元素ai,j 的存储位置 LOC(i,j) = LOC(0,0) + (b1×j＋i)× L 称为基地址或基址。

13 “行序为主序” 即 “低下标优先” 如: A[3][2][4] 的存储次序为: “列序为主序” 即 “高下标优先”
(0,0,0),(0,0,1),(0,0,2),(0,0,3),(0,1,0),…,(0,1,3),…,(1,0,0),…,(1,1,0),…,(1,1,3),(2,0,0),…,(2,1,3) “列序为主序” 即 “高下标优先” 则 A[3][2][4] 的存储次序为: (0,0,0),(1,0,0),(2,0,0),(0,1,0),…,(2,1,0),(0,0,1)…,(0,1,1),…,(0,0,2),…,(2,1,2),(0,0,3),…,(2,1,3)

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

15 5.3 稀疏矩阵的压缩存储 何谓稀疏矩阵？ 假设 m 行 n 列的矩阵含 t 个非零元素，则称 为稀疏因子
通常认为   0.05 的矩阵为稀疏矩阵

16 高阶的稀疏矩阵时产生的问题: 1) 零值元素占了很大空间; 2) 计算中进行了很多和零值的运算， 遇除法，还需判别除数是否为零;
以常规方法，即以二维数组表示 高阶的稀疏矩阵时产生的问题: 1) 零值元素占了很大空间; 2) 计算中进行了很多和零值的运算， 遇除法，还需判别除数是否为零;

17 解决问题的原则: 1) 尽可能少存或不存零值元素; 2) 尽可能减少没有实际意义的运算; 3) 操作方便; 即: 能尽可能快地找到
与下标值 (i, j) 对应的元素; 同一行或同一列的非零值元;

18 有两类稀疏矩阵： 1) 特殊矩阵 非零元在矩阵中的分布有一定规则 例如: 三角矩阵 对角矩阵 2) 随机稀疏矩阵 非零元在矩阵中随机出现

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

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

21 如何求转置矩阵？

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

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

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

25 T.mu = M.nu; T.nu = M.mu; T.tu = M.tu; if (T.tu) {
Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T){ T.mu = M.nu; T.nu = M.mu; T.tu = M.tu; if (T.tu) { for (col=1; col<=M.nu; ++col) num[col] = 0; for (t=1; t<=M.tu; ++t) ++num[M.data[t].j]; cpot[1] = 1; for (col=2; col<=M.nu; ++col) cpot[col] = cpot[col-1] + num[col-1]; for (p=1; p<=M.tu; ++p) { } } // if return OK; } // FastTransposeSMatrix 转置矩阵元素

26 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]

27 分析算法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)

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

29 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; // 行逻辑链接顺序表类型

30 例如：给定一组下标，求矩阵的元素值 ElemType value(RLSMatrix M, int r, int c) {
p = M.rpos[r]; while (M.data[p].i==r &&M.data[p].j < c) p++; if (M.data[p].i==r && M.data[p].j==c) return M.data[p].e; else return 0; } // value

31 矩阵乘法的精典算法: 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)

32 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

33 if (M.nu != N.mu) return ERROR; Q.mu = M.mu; Q.nu = N.nu; Q.tu = 0;
Status MultSMatrix (RLSMatrix M, RLSMatrix N, RLSMatrix &Q) { if (M.nu != N.mu) return ERROR; Q.mu = M.mu; Q.nu = N.nu; Q.tu = 0; if (M.tu*N.tu != 0) { // Q是非零矩阵 for (arow=1; arow<=M.mu; ++arow) { // 处理M的每一行 } // for arow } // if return OK; } // MultSMatrix

34 处理 的每一行 M ctemp[] = 0; // 当前行各元素累加器清零 Q.rpos[arow] = Q.tu+1;
for (p=M.rpos[arow]; p<M.rpos[arow+1];++p) { //对当前行中每一个非零元 brow=M.data[p].j; if (brow < N.nu ) t = N.rpos[brow+1]; else { t = N.tu+1 } for (q=N.rpos[brow]; q< t; ++q) { ccol = N.data[q].j; // 乘积元素在Q中列号 ctemp[ccol] += M.data[p].e * N.data[q].e; } // for q } // 求得Q中第crow( =arow)行的非零元 for (ccol=1; ccol<=Q.nu; ++ccol) if (ctemp[ccol]) { if (++Q.tu > MAXSIZE) return ERROR; Q.data[Q.tu] = {arow, ccol, ctemp[ccol]}; } // if 处理 的每一行 M

35 分析上述算法的时间复杂度 若M是m行n列的稀疏矩阵，N是n行p列的稀疏矩阵， 则M中非零元的个数 M.tu = Mmn，
累加器ctemp初始化的时间复杂度为(M.muN.nu)， 求Q的所有非零元的时间复杂度为(M.tuN.tu/N.mu)， 进行压缩存储的时间复杂度为(M.muN.nu)， 总的时间复杂度就是(M.muN.nu+M.tuN.tu/N.mu)。 若M是m行n列的稀疏矩阵，N是n行p列的稀疏矩阵， 则M中非零元的个数 M.tu = Mmn， N中非零元的个数 N.tu = Nnp， 相乘算法的时间复杂度就是 (mp(1+nMN)) ， 当M<0.05 和N<0.05及 n <1000时， 相乘算法的时间复杂度就相当于 (mp)。

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

37 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 基本操作:

38 广义表是递归定义的线性结构， 例如: 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,  , ) ) )

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

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

41 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 ) ) = ( )

42 基本操作  结构的创建和销毁  状态函数  插入和删除操作  遍历 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());

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

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

45

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

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

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

49 5.6 广义表操作的递归函数 递归函数 一个含直接或间接调用本函数语句的函数被称之为递归函数，它必须满足以下两个条件:
1)在每一次调用自己时，必须是(在某 种意义上)更接近于解; 2)必须有一个终止处理或计算的准则。

50 例如: 梵塔的递归函数 void hanoi (int n, char x, char y, char z) { if (n==1)
move(x, 1, z); else { hanoi(n-1, x, z, y); move(x, n, z); hanoi(n-1, y, x, z); }

51 PreOrderTraverse(T->lchild, Visit); } } // PreOrderTraverse
二叉树的遍历 void PreOrderTraverse( BiTree T,void (Visit)(BiTree P)) { if (T) { Visit(T->data); PreOrderTraverse(T->lchild, Visit); PreOrderTraverse(T->rchild, Visit); } } // PreOrderTraverse

52 如何设计递归函数？ 一、分治法 (Divide and Conquer) (又称分割求解法)

53 分治法的设计思想为: 对于一个输入规模为 n 的函数或问题， 用某种方法把输入分割成 k(1<k≤n)个子集，
从而产生 l 个子问题，分别求解这 l 个问题， 得出 l 个问题的子解，再用某种方法把它们 组合成原来问题的解。若子问题还相当大， 则可以反复使用分治法，直至最后所分得 的子问题足够小，以至可以直接求解为止。

54 在利用分治法求解时，所得子问题的类型常常和原问题相同，因而很自然地导致递归求解。

55 例如: 焚塔问题: Hanoi(n, x, y, z) 将 n 个盘分成两个子集(1至n-1 和 n )，从而产生下列三个子问题:
可递归求解 Hanoi(n-1, x, z, y) 2) 将 n号盘从 x 轴移动至 z 轴; 3) 将1至n-1号盘从y轴移动至z轴; 可递归求解 Hanoi(n-1, x, z, y)

56 又如: 遍历二叉树: Traverse(BT) 将 n 个结点分成三个子集(根结点、左子树 和右子树 )，从而产生下列三个子问题:
1) 访问根结点; 2) 遍历左子树; 可递归求解 Traverse(LBT) 3) 遍历右子树; 可递归求解 Traverse(RBT)

57 广义表从结构上可以分解成 广义表 = 表头 + 表尾 或者 广义表 = 子表1 + 子表2 + ··· + 子表n 因此常利用分治法求解之。 算法设计中的关键问题是，如何将 l 个子问题的解组合成原问题的解。

58 广义表的头尾链表存储表示： typedef enum {ATOM, LIST} ElemTag;
typedef struct GLNode { ElemTag tag; // 标志域 union{ AtomType atom; // 原子结点的数据域 struct {struct GLNode *hp, *tp;} ptr; }; } *GList 表结点 tag=1 hp tp ptr

59 例一 求广义表的深度 例二 复制广义表 例三 创建广义表的存储结构

60 例一 求广义表的深度 广义表的深度=Max {子表的深度} +1 空表的深度 = 1 原子的深度 = 0
将广义表分解成 n 个子表，分别(递归)求得每个子表的深度, 广义表的深度=Max {子表的深度} +1 可以直接求解的两种简单情况为: 空表的深度 = 1 原子的深度 = 0

61 int GlistDepth(Glist L) {
if (!L) return 1; if (L->tag == ATOM) return 0; for (max=0, pp=L; pp; pp=pp->ptr.tp){ dep = GlistDepth(pp->ptr.hp); if (dep > max) max = dep; } return max + 1;

62 …  例如: pp pp pp 1 L for (max=0, pp=L; pp; pp=pp->ptr.tp){
pp->ptr.hp pp->ptr.hp pp->ptr.hp for (max=0, pp=L; pp; pp=pp->ptr.tp){ dep = GlistDepth(pp->ptr.hp); if (dep > max) max = dep; }

63 例二 复制广义表 新的广义表由新的表头和表尾构成。 空表复制求得的新表自然也是空表; 原子结点可以直接复制求得。
例二 复制广义表 将广义表分解成表头和表尾两部分，分别(递归)复制求得新的表头和表尾， 新的广义表由新的表头和表尾构成。 可以直接求解的两种简单情况为: 空表复制求得的新表自然也是空表; 原子结点可以直接复制求得。

64 复制求广义表的算法描述如下: 若 ls= NULL 则 newls = NULL 否则 构造结点 newls, 由 表头ls->ptr.hp 复制得 newhp 由 表尾 ls->ptr.tp 复制得 newtp 并使 newls->ptr.hp = newhp, newls->ptr.tp = newtp

65 Status CopyGList(Glist &T, Glist L) {
if (!L) T = NULL; // 复制空表 else { if ( !(T = new GLNode) ) exit(OVERFLOW); // 建表结点 T->tag = L->tag; if (L->tag == ATOM) T->atom = L->atom; // 复制单原子结点 else { } } // else return OK; } // CopyGList 分别复制表头和表尾

66 CopyGList(T->ptr.hp, L->ptr.hp);
CopyGList(T->ptr.tp, L->ptr.tp); // 复制求得表尾T->ptr.tp 的一个副本L->ptr.tp 语句 CopyGList(T->ptr.hp, L->ptr.hp); 等价于 CopyGList(newhp, L->ptr.tp); T->ptr.hp = newhp;

67 例三 创建广义表的存储结构 对应广义表的不同定义方法相应地有不同的创建存储结构的算法。

68 假设以字符串 S = (1, 2, , n ) 的形式定义广义表 L，建立相应的存储结构。
由于S中的每个子串i定义 L 的一个子表，从而产生 n 个子问题，即分别由这 n个子串 (递归)建立 n 个子表，再组合成一个广义表。 可以直接求解的两种简单情况为: 由串( )建立的广义表是空表; 由单字符建立的子表只是一个原子结点。

69 首先分析广义表和子表在存储结构中的关系。
如何由子表组合成一个广义表？ 首先分析广义表和子表在存储结构中的关系。 先看第一个子表和广义表的关系: 指向广义表 的头指针 1 L 指向第一个 子表的头指针

70 再看相邻两个子表之间的关系: 1 指向第i个 子表的头指针 指向第i+1个 子表的头指针 可见，两者之间通过表结点相链接。

71 若 S = ( ) 则 L = NULL 否则 构造第一个表结点 *L, 并从串 S 中分解出第一个子串 1, 对应 创建第一个子广义表 L->ptr.hp; 若剩余串非空，则构造第二个表结点 L->ptr.tp, 并从串 S 中分解出第二个子串 2, 对应建第二个子广义表 ………; 依次类推，直至剩余串为空串止。

72 ( a, ( ),(x,y), ((x)) ) ( a, ( ),(x,y), ((x)) ) a ( ) (x,y) p p p 1 L
 1 1 0 a p->ptr.hp 1 p->ptr.hp

73 void CreateGList(Glist &L, String S) {
if (空表串) L = NULL; // 创建空表 else { L = new GLNode; // 生成表结点 L->tag=List; p=L; sub=SubString(S,2,StrLength(S)-1); // 脱去串 S 的外层括弧 } // else } 由sub中所含n个子串建立n个子表;

74 do { sever(sub, hsub); // 分离出子表串hsub=i if (!StrEmpty(sub) { p->ptr.tp=newGLNode; // 建下一个子表的表结点*(p->ptr.tp) p=p->ptr.tp; } } while (!StrEmpty(sub)); p->ptr.tp = NULL; // 表尾为空表 创建由串hsub定义的广义表p->ptr.hp;

75 if (StrLength(hsub)==1) {
p->ptr.hp=new GLNode; p->ptr.hp->tag=ATOM; p->ptr.hp->atom=hsub; // 创建单原子结点 } else CreateGList(p->ptr.hp, hsub); //递归建广义表

76 了解数组类型的特点以及在高级编程语言中的两种存储表示和实现方法，并熟练掌握数组在以行为主的存储结构中的地址计算方法。

77 1. 掌握广义表的结构特点及其存储表示方法，学会对非空广义表进行分解的两种分析方法：即可将一个非空广义表分解为表头和表尾两部分或者分解为n个子表。
2. 学习利用分治法的算法设计思想编制递归算法的方法。