Chapter 05 Sparse Matrix & Lists 第五章 稀疏数组和广义表

Presentation on theme: "Chapter 05 Sparse Matrix & Lists 第五章 稀疏数组和广义表"— Presentation transcript:

1 Chapter 05 Sparse Matrix & Lists 第五章 稀疏数组和广义表
Prof. Qing Wang

2 本章学习的线索 主要线索 重点 难点 稀疏矩阵的三元组存储 广义表的概念和存储表示 稀疏矩阵的运算（转置、乘法） 十字链表存储结构
矩阵的压缩存储 稀疏矩阵 的运算 广义表的表示和实现 广义表的 应用 Prof. Q. Wang

3 Content Definition of Array Representation of Sparse Matrix
Typical operations of Sparse Matrix Definition of General List (Lists) Physical form of General List Applications of General List Prof. Q. Wang

4 5.1 Generic array Array is the extension of the sequential list.
User can re-define specific functions to avoid the exceedingly access of the array. Categories 1D array 2D array 3D array High dimensional array Prof. Q. Wang

5 1D array LOC ( i ) = LOC ( i -1 ) + l =α+ i*l Prof. Q. Wang

6 2D array Row subscript i, Column subscript j Prof. Q. Wang

7 Memory address of 2D array
a[0][m-1] a[1][0] a[1][m-1] Row-first: LOC ( j, k ) = a + ( j * m + k ) * l a[n-1][0] Prof. Q. Wang a[n-1][m-1]

8 3D Array Page subscript i , Row subscript j , Column subscript k m n s
Prof. Q. Wang

9 Memory address of 3D array
i k j a[0][0][1] a[0][m-1][l-1] a[1][0][0] a[1][m-1][l-1] a[n-1][0][0] Row-first: LOC ( i, j, k ) = a + ( i * n * s + j * s + k ) * l a[n-1][m-1][l-1] Prof. Q. Wang

10 Memory address of n-D array
n-Dimension array The dimensions are m1, m2, m3, …, mn respectively. The element with subscripts (i1, i2, i3, …, in) is in the space： LOC ( i1, i2, …, in ) = a + ( i1*m2*m3*…*mn + i2*m3*m4*…*mn+ + ……+ in-1*mn + in ) * l Prof. Q. Wang

11 5.2 Compact storage of special matrix
矩阵是很多科学与工程计算问题中研究的数学对象。在此我们感兴趣的是如何存储矩阵的元从而使矩阵的各种运算等能够有效地进行。 压缩存储：在数值分析中经常出现一些阶数很高的矩阵，同时在矩阵中有很多值相同的元素或零元素，为了节省空间，可以为多个值相同的元只分配一个空间，对零元不分配空间。 特殊矩阵：值相同的元素或零元素在矩阵中的分布有一定 的规律。反之称稀疏矩阵。 Symmetric matrix Triangle matrix Diagonal matrix Prof. Q. Wang

12 5.2.1 Special matrix (1) Symmetric matrix：nxn matrix
if aij = aji 1<=i, j <= n we only need to take the low triangle and diagonal elements into account. As a result, the space for these elements is n(n+1)/2. Suppose we use a 1D array s[0..n(n+1)/2] to save these values, the corresponding address k in 1D array for the element aij is: Prof. Q. Wang

13 i j k Symmetric matrix 0-th row 0-th column a11 a21 a22 a31 a32 a33
a11 a21 a22 a31 a32 a33 ... ... ... an,1 an,2 an,3 ... ... an,n-1 an,n Prof. Q. Wang

14 (2) Triangle matrix：指矩阵的上（下）三角中的元素（不包括对角线）均为常数c或0的n阶矩阵。可以采用和对称矩阵一样的方法存储。
j 1 2 3 4 5 6 ... ... ... 16 17 18 ... ... 20 21 Prof. Q. Wang

15 (3) 对角矩阵：所有的非零元都集中在以主对角线为中心的带状区域中。即除了主对角线上和直接在对角线上、下方若干个对角线上的元之外，所有其他的元皆为零。
Prof. Q. Wang

16 5.2.2 Sparse Matrix Sparse factor：设在m*n的矩阵中，有t个非零元素，令
称为矩阵的稀疏因子。通常情况下，当 <=0.05时，该矩阵称为稀疏矩阵。 我们在存储的时候，除了存储非零元的值之外，还得存储它所在的行号和列号。由此构成一个三元组 (i, j, aij)，该三元组唯一确定了该矩阵元素。 注意：三元组表中的元素是有序排列的。(按照行优先、行相同列大小方式) Prof. Q. Wang

17 Example Row: m=6; Column: n=7; The number of non-zero elements: t=8
Prof. Q. Wang

18 1. Sequential list of triple (三元组表)
#define MaxSize 20000 typedef struct { int i, j; /* 行号和列号 */ ElemType elem; /* 元素值 */ }Triple; Triple data[MaxSize]; int mu, nu, tu; /* 行数、列数和非零元个数*/ }TSMatrix; Prof. Q. Wang

19 Prof. Q. Wang

20 A6X7 B7x6 Prof. Q. Wang

21 Matrix Transposition Rule: (1) Swap the value of row and column;
(2) Sort the triple according to the requirement of the structure. Prof. Q. Wang

22 Method 1: matrix transposition
Two algorithms for matrix transposition. (1) Naive algorithm Rule: 按照列序。 找到矩阵的每一列所有元素，变成相应的行即可。为了找到矩阵的某一列的所有非零元素，需要对矩阵从第一行起整个扫描一遍。 具体可以如下实现： Prof. Q. Wang

23 A6X7 B7x6 Prof. Q. Wang

24 Status TransposeSMatrix (TSMatrix M, TSMatrix *T) { int p, q, col;
T->mu = M.nu; T->nu = M.mu; T->tu = M.tu; if (T->tu){ q = 0; for (col = 0; col< M.nu; ++col) for (p = 0; p< M.tu; ++p) if (M.data[p].j == col) { T->data[q].i = M.data[p].j; T->data[q].j = M.data[p].i; T->data[q].elem = M.data[p].elem; q++; } return OK; Prof. Q. Wang

25 Analysis The time complexity: O(M.nu*M.tu)
当矩阵中非零元个数tu和mu*nu同数量级时，则该算法的时间复杂度为O(M.mu*M.nu2）。因此该算法只适用于M.tu << M.mu*M.nu的情况。 Prof. Q. Wang

26 Method 2: matrix transposition
(2) Fast transposition algorithm 将矩阵M的每一个转置后的三元组放入矩阵T的合适位置。 原理：如果能预先确定矩阵M中每一列（即T中的每一行）的第一个非零元素在T中的合适位置，那么在对M进行转置时就可以直接放到T中的恰当位置上去。为了确定这些位置，应先求得M的每一列中非零元的个数，进而求得每一列的第一个非零元在T中的位置。 Prof. Q. Wang

27 Fast transposition algorithm
设num[]和cpot[]分别用来存放每一列的非零元的个数和该列第一个非零元在转置后矩阵T中的位置。则显然有： 而每一列的非零元的个数可以通过对整个矩阵M扫描一遍得到。 cpot[0]= 0; cpot[col] = cpot[col-1]+num[col-1] 0<=col <M.nu Prof. Q. Wang

28 Number of non-zero elements in each column
Position of the first non-zero element in each column Prof. Q. Wang

29 A6X7 B7x6 Prof. Q. Wang

30 Status FastTransposeSMatrix (TSMatrix M, TSMatrix *T)
{ int col, p, q, t; T->mu = M.nu; T->nu = M.mu; T->tu = M.tu; if (T->tu) { for (col=0; col< M.nu; ++col) num[col] = 0; for (t = 0; t < M.tu; ++t) /*统计每列的非零元个数*/ ++num[M.data[t].j]; cpot[0] = 0; /*计算每列第一个非零元转置后的位置*/ for (col = 1; col < M.nu; ++col) cpot[col] = cpot[col-1] + num[col-1]; for (p = 0; p <= M.tu; ++p){ 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].elem = M.data[p].elem; ++cpot[col]; } /* for */ } /* if */ return OK; } Prof. Q. Wang

31 Analysis 该算法的总的循环次数为： M.nu+M.tu+M.nu-1 +M.tu = 2(M.nu + M.tu)-1
所以其时间复杂度为：O(M.nu+M.tu)。 即使非零元个数与mu*nu同数量级，其时间复杂度为O(M.mu * M.nu)，与经典算法时间复杂度相同。 三元组顺序表（有序的双下标法）的特点： （1）便于进行以行顺序处理的矩阵运算。 （2）若需按行号存取某一行的非零元，需从开始进行查找。 Prof. Q. Wang

32 2. Advanced triple list (行逻辑链接的顺序表)
为了便于随机存取任意一行的非零元，则需知道每一行的第一个非零元在三元组表中的位置。为此，可将快速转置矩阵的算法中创建的辅助数组cpot，rpos固定在稀疏矩阵的存储结构中。这种带“行链接信息”的三元组表称为行逻辑链接的顺序表。 typedef struct{ Triple data[MaxSize]; int rpos[MaxRC+1]; int mu, nu, tu; }RLSMatrix; 我们以矩阵相乘为例来看一下这种表示方法的优越性。 其时间复杂度为：O(M.mu*N.nu+M.tu*N.tu/N.mu) The position of the first non-zero element in the rows. Prof. Q. Wang

33 Matrix multiplication
Theory: Prof. Q. Wang

34 2D Array Implementation
C=AxB for (i=0; i<m; i++) for (j=0; j<l; j++) { C[i][j]=0; for (k=0; k<n; k++) C[i][j] += A[i][k]*B[k][j] } Time complexity: O(m*n*l) Prof. Q. Wang

35 Matrix multiplication
Prof. Q. Wang

36 B A C Prof. Q. Wang

37 A B Example 10*2 ctemp[] 5*14 2*2 3*2 7*3 7*5 1*4 1*8 4*14 41 105 8 8 6 56 Prof. Q. Wang

38 A B Example 10*2 ctemp[] 5*14 2*2 3*2 7*3 7*5 1*4 1*8 4*14 ∑ 20 8 8 6 56 Prof. Q. Wang

39 A B Example 10*2 ctemp[] 5*14 2*2 3*2 7*3 7*5 1*4 1*8 4*14 ∑ 20 70 8 8 6 56 Prof. Q. Wang

40 A B Example 10*2 ctemp[] 5*14 2*2 3*2 7*3 7*5 1*4 1*8 4*14 ∑ 41 105 8 8 6 56 Prof. Q. Wang

41 ∑ Example 41 105 8 8 6 56 A B C 10*2 5*14 2*2 3*2 7*3 7*5 1*4 1*8 4*14
ctemp[] 5*14 2*2 3*2 7*3 7*5 1*4 1*8 4*14 ∑ 41 105 8 8 6 56 Prof. Q. Wang

42 ∑ Example 41 105 8 8 6 56 A B C 10*2 5*14 2*2 3*2 7*3 7*5 1*4 1*8 4*14
ctemp[] 5*14 2*2 3*2 7*3 7*5 1*4 1*8 4*14 ∑ 41 105 8 8 6 56 Prof. Q. Wang

43 ∑ Example 41 105 8 8 6 56 A B C 10*2 5*14 2*2 3*2 7*3 7*5 1*4 1*8 4*14
ctemp[] 5*14 2*2 3*2 7*3 7*5 1*4 1*8 4*14 ∑ 41 105 8 8 6 56 Prof. Q. Wang

44 A B Example C X Prof. Q. Wang

45 Number of non-zero element in each row
Position of the first non-zero element in each row Prof. Q. Wang

46 Matrix multiplication
Prof. Q. Wang

47 Procedure of multiplication
C=AxB C initialization; if (C is not NULL matrix) { for (arow=0; arow<M.mu; arow++) ctemp[]=0; //reset to 0 calculate the result  ctemp[]; ctemp[]  C.data; //store to C compactly } Prof. Q. Wang

48 Matrix multiplication
Status MultiSMatrix (RLSMatrix M, RLSMatrix N, RLSMatrix *Q) { int arow, brow, ccol, p, q, t; float ctemp[]; if (M.mu != N.nu) return ERROR; Q->mu = M.nu; Q->nu = N.mu; Q->tu = 0; if (M.tu*N.tu != 0) { for (arow=0; arow< M.mu; ++arow) { ctemp[]=0; //memset(ctemp,0,n*sizeof(float)); Q->rpos[arow]=Q->tu; for (p=M.rpos[arow]; p< M.rpos[arow+1]; ++p) { brow=M.data[p].j; for (q = N.rpos[brow]; q<N.rpos[brow+1]; ++q) { ccol=N.data[q].j; ctemp[ccol]+=M.data[p].elem*N.data[q].elem; } //for q } // for p A矩阵某行所有非零元 Prof. Q. Wang

49 乘积矩阵对应于A矩阵arow行所有非零元进入三元组表
for (ccol=0; ccol<Q.nu; ++ccol) { if (ctemp[ccol] { if (++Q->tu > MAXSIZE) return ERROR; else { Q->data[T->tu].i = arow; Q->data[T->tu].j = ccol; Q->data[T->tu].elem = ctemp[ccol]; Q->tu++; } //if } //for ccol } //for arow return OK; } 乘积矩阵对应于A矩阵arow行所有非零元进入三元组表 Prof. Q. Wang

50 Complexity analysis The loop numbers in the algorithm:
1 ctemp initialization  O(M.mu*N.nu) 2 for all non-zero elements in result matrix Q  O(M.tu*N.tu/N.mu) 3 compacted  O(M.mu*N.nu) 4 The total time complexity is: O(M.mu*N.nu+M.tu*N.tu/N.mu) If the total complexity is: Prof. Q. Wang

51 Question? Triple sequential list of sparse matrix Addition
C=A+B: similar to the addition of polynomial A=A+B: it is very hard to implement due to the drawbacks of the sequential structure Prof. Q. Wang

52 3. Cross linked list (Orthogonal list)
当矩阵的非零元个数和位置在操作过程中变化较大时，就不宜采用顺序存储结构，这时可以采用链式结构。 由于矩阵有行和列，所以一个结点除了数据域(i, j, elem)之外，还应该用两个方向的指针(right, down)，分别指向行和列。这样整个矩阵构成了一个十字交叉的链表，因此称十字链表。每一行或每一列的头指针，可以用两个一维指针数组来存放。 如下所示: typedef struct OLNode { int i, j; ElemType elem; struct OLNode *right, *down; }OLNode, *OLink; 结点结构 i j elem down right Prof. Q. Wang

53 typedef struct { OLink *rHead, *cHead; int mu, nu, tu; }CrossList; ^ 3
M.cHead ^ M.rHead 3 3 5 ^ 1 -1 ^ 2 ^ typedef struct { OLink *rHead, *cHead; int mu, nu, tu; }CrossList; Prof. Q. Wang

54 Example of initialization of cross-linked list
typedef struct OLNode { int i, j; ElemType elem; struct OLNode *right, *down; }OLNode, *OLink; typedef struct { OLink *rHead, *cHead; int mu, nu, tu; }CrossList; CrossList *M M.cHead ^ M.rHead 3 3 5 ^ 1 -1 ^ 2 ^ Prof. Q. Wang

55 Initialization of cross-linked list
Status CreateOLSMatrix (CrossList *M) { if (M) free(M); scanf(&m, &n, &t); M.mu=m; M.nu=n; M.tu=t; if (!(M.rhead=(OLink *)malloc((m+1)*sizeof(OLink)))) exit (OVERFLOW); if (!(M.chead=(OLink *)malloc((n+1)*sizeof(OLink)))) for (scanf(&i, &j, &e); i!=0; scanf(&i, &j, &e)) { if (!(p=(OLink*)malloc(sizeof(OLNode))) exit(OVERFLOW); p->i=i; p->j=j; p->elem=e; if (M.rhead[i]==NULL || M.rhead[i]->j>j) { p->right=M.rhead[i]; M.rhead[i]=p; } else { for (q=M.rhead[i]; (q->right) && q->right->j<j; q=q->right); p->right=q->right; q->right=p; } //完成行插入 Prof. Q. Wang

56 if (M.chead[j]==NULL || M.chead[j]->i>i) {
p->down=M.chead[j]; M.rhead[j]=p; } else { for (q=M.chead[j]; (q->down) && q->down->i<i; q=q->down); p->down=q->down; q->down=p; } //完成列插入 return OK; Prof. Q. Wang

57 补充材料：Cross linked list for Sparse Matrix
True next False row col down right down value right (a) Head node for each row & col (b) Head node for matrix False i j a[i][j] (c) Element node with (i, j, a[i][j]) Prof. Q. Wang

58 Example Point to Prof. Q. Wang

59 // Cross Linked List Class enum Boolean { False, True };
struct Triple { int row, col; float value; }; class Matrix; class MatrixNode { friend class Matrix; friend istream &operator >> ( istream &, Matrix & ); private: MatrixNode *down, *right; Boolean head; Union { Triple triple; MatrixNode *next; } MatrixNode ( Boolean, Triple* ); } Prof. Q.Wang

60 typedef MatrixNode *MatrixNodePtr; class Matrix {
friend istream& operator >> ( istream &, Matrix & ); public: ~Matrix ( ); private: MatrixNode *headnode; }; MatrixNode::MatrixNode ( Boolean b, Triple *t ) { head = b; if ( b ) { right = next = this; } else triple = *t; } Prof. Q.Wang

61 // Initialization of Sparse Matrix using Orthogonal list
istream & operator >> ( istream & is, Matrix & matrix ) { Triple s; int p; is >> s.row >> s.col >> s.value; if ( s.row > s.col ) p = s.row; else p = s.col; matrix.headnode = new MatrixNode ( False, &s ); if ( !p ) { matrix.headnode→right = matrix.headnode; return is; } MatrixNodePtr *H = new MatrixNodePtr ( p ); for ( int i = 0; i < p; i++ ) H[i] = new MatrixNode ( True, 0 ); int CurrentRow = 0; MatrixNode *last = H[0]; Prof. Q.Wang

62 for ( i = 0; i < s.value; i++ ) {
Triple t; is >> t.row >> t.col >> t.value; if ( t.row > CurrentRow ) { last→right = H[CurrentRow]; CurrentRow = t.row; last = H[CurrentRow]; } last = last→right = new MatrixNode ( False, &t ); H[t.col]→next = H[t.col]→next→down = last; last→right = H[CurrentRow]; for ( i = 0; i < s.col; i++ ) H[i]→next→down = H[i]; for ( i = 0; i < p-1; i++ ) H[i]→next =H[i+1]; H[p-1]→next = matrix.headnode; matrix.headnode→right = H[0]; delete [ ] H; return is; Prof. Q.Wang

63 enum Boolean { False, True };
typedef struct Triple { int i, j; float elem; }; typedef struct { MatrixNode *down, *right; Boolean head; Union { Triple triple; MatrixNode *next; } } MatrixNode; typedef struct { MatrixNode *headnode; } Matrix; Prof. Q. Wang

64 Triple data[MaxSize]; int mu, nu, tu; }TSMatrix; typedef struct OLNode
#define MaxSize 20000 typedef struct { int i, j; ElemType elem; }Triple; Triple data[MaxSize]; int mu, nu, tu; }TSMatrix; typedef struct OLNode { int i, j; ElemType elem; struct OLNode *right, *down; }OLNode, *OLink; typedef struct { OLink *rHead, *cHead; int mu, nu, tu; }CrossList; typedef struct{ Triple data[MaxSize]; int rpos[MaxRC+1]; int mu, nu, tu; }RLSMatrix; Prof. Q. Wang

65 5.3 General list (lists) 广义表是线性表的推广，也称为列表(Lists)。广泛应用于人工智能等领域。 一般记作：
LS = (1,2,…, n) 其中，LS是广义表的名称，n是它的长度。 I (i=1,2,…,n)可以是单个元素(原子)，也可以是广义表(子表)。习惯上用小写字母代表原子，大写字母代表子表。 Prof. Q. Wang

66 Definition 当广义表非空时，称其第一个元素1为LS的表头(即Head)，称其余元素组成的表(2, 3,…, n)为表尾(即Tail)。显然广义表的定义是一个递归定义。 下面是一些例子： A = ( ) —— 空表； B = (e) —— 只有一个原子的列表； C = (a, (b, c, d)) —— 有两个元素,第一个为原子，第二个是列表； D = (A, B, C) —— 三个元素均为列表的列表； E = (a, E) —— 递归列表。 Prof. Q. Wang

67 表头和表尾示例 list1=(5, 12, ‘s’, 47, ‘a’) Head(list1)=5
Tail(list1)=(12, ‘s’, 47, ‘a’) Head(Tail(list1))=12 Tail(Tail(list1))=(‘s’, 47, ‘a’) Prof. Q. Wang

68 表头和表尾示例 Complex general list
Head(list2)=5 Tail(list2)=((3, 2, (14, 9, 3), ( ), 4), 2, (6, 3, 10)) Head(Tail(list2))=(3, 2, (14, 9, 3), ( ), 4) Head(Head(Tail(list2)))=3 Prof. Q. Wang

69 Example E D E A B C a e a E b c d a Prof. Q. Wang

70 Characteristics of General List
（1）元素可以是子表，子表的元素还可以是子表，形成一个层次结构。 （2）广义表可以为其他广义表所共享。如A,B,C均为D的子表。 （3）广义表可以是一个递归表。 （4）表头可以是原子，也可以是子表；表尾必定是子表。 注意：( ) 和(( ))的区别。 Prof. Q. Wang

71 Examples Prof. Q. Wang

72 ((a+b)*(b*(c+d))+(c+d)*e)*((c+d)*e)
＋ * * * ＋ (c+d)*e e + + e * c d a b b + c d * + e a b c d c d (c+d)*e c+d Prof. Q. Wang

73 5.4 Representation of General list
通常采用链式存储结构，因为难以用顺序存储结构表示。每个数据元素可以用一个结点来表示。 由于广义表的数据元素可能是原子，也可能是子表，因此必须用两种结构来存储，而且为了区分元素是原子还是子表，需设立一个标志。 另外，由定义可知，对于非空广义表，是由表头和表尾构成的，因此 一个 表结点 可以由三个域构成：标志域、指示表头的指针域和指示表尾的指针域； 而 原子结点 只需两个域：标志域和值域。 Prof. Q. Wang

74 Representation of General list: 表头-表尾表示法
typedef enum {Atom, List} ElemTag; typedef int AtomType; typedef struct _GLNode { ElemTag tag; union AtomType atom; //原子结点的值域 struct /* 想一想，为什么这儿又使用一个结构体 */ struct _GLNode *head, *tail; }ptr; //表结点的指针域，p.head是表头，p.tail表尾 } p; }*GList; Prof. Q. Wang

75 A = ( ) B = (e) C = (a, (b, c, d)) D = (A, B, C) E = (a, E)
Atom node 原子结点 Lists node 表结点 tag=0 atom tag=1 head tail A=NULL 1 B e 1 C a b c d 1 D A = ( ) B = (e) C = (a, (b, c, d)) D = (A, B, C) E = (a, E) 1 E a Prof. Q. Wang

76 Alternative representation of General list: 表结点头指针+下一个结点
typedef enum {Atom, List} ElemTag; typedef int AtomType; typedef struct _GLNode { ElemTag tag; union AtomType atom; //原子结点的值域 struct _GLNode *head; //表结点的表头指针 }; struct _GLNode *tail; //指向下一个元素结点 }*GList; Prof. Q. Wang

77 A = ( ) B = (e) C = (a, (b, c, d)) D = (A, B, C) E = (a, E) Atom node
Lists node tag=0 atom tail tag=1 head tail A 1 1 B e 1 C a b c d 1 D A = ( ) B = (e) C = (a, (b, c, d)) D = (A, B, C) E = (a, E) 1 E a Prof. Q. Wang

78 Application of general list
Multi-item Sequential list Single linked list coef1 expx1 expy1 expz1 coef2 expx2 expy2 expz2 coef3 expx3 expy3 expz3 ……………………………………………. coefn expxn expyn expzn coef expx expy expz link Prof. Q. Wang

79 Variable separation

80

81 General List for Multi-polynomial
z 2 1 y 3 2 y 4 1 x 3 8 x 2 x 1 10 2 8 x 1 4 6 3

82 1 y x 15

83 typedef enum {Atom, List} ElemTag; typedef struct MPNode {
ElemTag tag; int exp; union { float coef; struct MPNode *head; } struct MPNode *tail; } *MPList; See P.112 Prof. Q. Wang

84 5.5 Recursive algorithms of General list
求广义表的深度 复制广义表 建立广义表的存储结构 Prof. Q. Wang

85 Review of recursive function
递归函数的特点 结构清晰 程序易读 正确性证明 设计递归函数的注意事项 函数的首部和规格说明，接口保持一致； 函数中的每一个调用都看成一个简单的操作 Prof. Q. Wang

86 The depth of general list
深度：广义表中括弧的重数。 广义表LS = (1,2,…, n)的深度Depth(LS) 递归定义为： 基本项：Depth(LS) = 1 当LS为空表时 Depth(LS) = 0 当LS为原子时 归纳项：Depth(LS) = 1 + Max{Depth(i)} i=1..n, n>=1 Prof. Q. Wang

87 int GListDepth (GList L) { if (!L) return 1;
if (L->tag == ATOM) return 0; for ( max=0, pp=L; pp; pp=pp->ptr.tail) { dep = GListDepth (pp->ptr.head); if (dep > max) max = dep; } return (max+1); Depth(D) = 1+ Max{ 1, 1, 2} = 3 D=(A,B,C)=((), (e), (a, (b,c,d))) Depth(D) = 1+Max{ Depth(A), Depth(B), Depth(C)} Depth(A) = 1; Depth(B) = 1+ Max{Depth(e)} = 1+0 = 1; Depth(C) = 1+ Max{Depth(a), Depth((b,c,d))} = 2 Depth(a) = 0; Depth ((b,c,d)) = 1+Max{Depth(b), Depth(c), Depth(d)} = 1+0 = 1; Prof. Q. Wang

88 D = ((), (e), (a, (b, c, d))) Depth(D) = 1+ Max{ 1, 1, 2} = 3 3 2 1 D
e a 1 1 1 x6 x7 x1 = ( (e), (a, (b, c, d))) b c d x2 = ((a, (b, c, d))) x3 = (a, (b, c, d)) x4 = ((b, c, d)) x5 = (b, c, d) x6 = (c, d) Prof. Q. Wang x7 = (d)

89 Duplication of general list
基础 任何一个非空广义表均可以分解成表头和表尾； 一对确定的表头和表尾可唯一确定一个广义表。 复制一个广义表只要分别复制其表头和表尾，然后合成即可。 步骤 基本项：InitGList(NewLS) {置空表} 当LS为空表时 归纳项：Copy(GetHead(LS)->GetHead(NewLS)) {复制表头} Copy(GetTail(LS)->GetTail(NewLS)) {复制表尾} Prof. Q. Wang

90 Status CopyGList (GList T, GList L) { if (!L) T = NULL; else {
if (!(T = (GList)malloc(sizeof(GLNode)) exit(OVERFLOW); T->tag = L->tag; if (L->tag == ATOM ) T->atom = L->atom; CopyGList (T->ptr.head, L->ptr.head); // 复制广义表L->ptr.head的一个副本 CopyGList (T->ptr.tail, L->ptr.tail); // 复制广义表L->ptr.tail的一个副本 } return OK; Prof. Q. Wang

91 Conclusion Compact storage of special matrix
Representation and operations of sparse matrix Definition and representation of general list The recursive algorithm of general list Depth, visit, duplication Application of general list Prof. Q. Wang