2014/47 §5.2矩阵的压缩存储 §5.2矩阵的压缩存储 typedef struct CLNode( inti,j; DataType v. struct CLNode right,*down; )CLNode; typedef struct{ 123 CLNode*head[MaxRow]:行链表头指针，MaxRow在前定义 每个结点是在”十 CLNode *chead[MaxCol]: int m,n,t; )CrossList; CrossListA: s5.3广义表(Lists) s5.3广义表(Lists) 1概念 。例： 是线性表的推广，如将线性表中元素放宽到可以是自 E=()—空表，长度n=0,深度d=1. 身的结构。 L=(a,b)一一n=2,d=1.(线性表) 。 定义：LS=(g,4,,4)n之0，它由n个元素构成的有限 序列，其中，或是原子，或是广义表（字子表）。 A=(x,L=(x,(a,b》一n=2,d=2.a,为原子，a2为子表 LS-名字，n-长度，n=0为空表。 B=(Ay=(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(m》—n=2,d=o 若LS≠D,则，成为衰头（首），剩余元素构成的表 ·若规定任何衰都有名字，则可在每个夜前冠名。 (4,…,a)为表尾。广义表是地归定义的，展开到每 E()L(a,b)A(x,L(a,b)) 元素均为原字时括号的量大层数为深度。 85.3广义表(Lists) 85.3广义表(Lists) ,图示 。运算 求表头、表尾。 head(A)=x,taA)=(a,b)表尾是表，表头不一定 head(tail(A》=(ab)—表 纯表（与衬树应） 编归表〔允许地) head(head(ta(A》=a—原子 tail(head(tail(A)》=b一表 再入表（允许结点共享） 。各种表之关系 head(tail(head(tail(A》=b—原子 ti(il(hcad(tail(A)》=()表 递归表一再入表一纯表一线性表 Noter()和()》不同. ()为空表m0,不能求表头和表属。 ()为非空表，1.可求表头和具： head()月=(，t(=() 52014/4/7 5 §5.2 矩阵的压缩存储 typedef struct CLNode{ int i, j ; DataType v; struct CLNode * right, *down; }CLNode; t d f t t{ 25 typedef struct { CLNode *rhead[MaxRow]; //行链表头指针，MaxRow在前定义 CLNode *chead[MaxCol]; //列… int m,n, t; }CrossList; CrossList A; §5.2 矩阵的压缩存储 26 §5.3 广义表（Lists） 1. 概念 是线性表的推广，如将线性表中元素ai 放宽到可以是自 身的结构。  定义： ，它由n个元素构成的有限 序列，其中ai 或是原子，或是广义表（子表）。 LS-名字，n-长度，n=0为空表。 27 一般用小写字母表示原子，大写字母表示子表。  表头、表尾、深度 若 ，则a1成为表头（首），剩余元素构成的表 为表尾。广义表是递归定义的，展开到每一 元素均为原子时括号的最大层数为深度。 §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) (( ( b)) (( ( b)) )) 2d 4 28 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)) §5.3 广义表（Lists）  图示 29  各种表之关系 §5.3 广义表（Lists）  运算 求表头、表尾。 head(A) = x, tail(A) = ((a, b)) //表尾是表，表头不一定 head(tail(A)) = (a, b) ——表 30 Note： 和 不同。 为空表n=0，不能求表头和表尾。 为非空表，n=1. 可求表头和尾：