数据结构C语言版第5章数组和广义表.ppt

《数据结构C语言版第5章数组和广义表.ppt》由会员分享，可在线阅读，更多相关《数据结构C语言版第5章数组和广义表.ppt（64页珍藏版）》请在三一办公上搜索。

1、数 组 和 广 义 表,1、数组的定义和顺序存储方式；2、特殊矩阵的压缩存储；3、稀疏矩阵；4、广义表的概念、表示及基本操作；广义表存储结构的实现。,教学内容,5.1 数组的定义,数组：按一定格式排列起来的 具有相同类型的数据元素的集合。,一维数组：若线性表中的数据元素为非结构的简单元素，则称为一维数组。,一维数组的逻辑结构：线性结构。定长的线性表。,声明格式：数据类型 变量名称长度；,例：int num5=0，1，2，3，4;,二维数组：若一维数组中的数据元素又是一维数组结构，则称为二维数组。,非线性结构,num5=0，1，2，3，4;,A=(0,1,p)(p=m-1 or n-1),j=(

2、a0j,a1j,am-1,j)0jn-1,i=(ai0,ai1,ai,n-1)0im-1,二维数组的逻辑结构,线性结构定长的线性表,每一个数据元素 既在一个行表中，又在一个列表中。,该线性表的每个数据元素 也是一个定长的线性表。,在 C 语言中，一个二维数组类型也可以定义为 一维数组类型（其分量类型为一维数组类型），即：typedef elemtype array2mn;等价于：typedef elemtype array1n;typedef array1 array2m;,声明格式：数据类型 变量名称行数 列数；,例：int num5 8;,三维数组：若二维数组中的元素又是一个一维数组结构，

3、则称作三维数组。,n 维数组：若 n-1 维数组中的元素又是一个一维数组结构，则称作 n 维数组。,线性表结构是数组结构的一个特例，而数组结构又是线性表结构的扩展。,结论,数组特点：结构固定定义后，维数和维界不再改变。,数组基本操作：除了结构的初始化和销毁之外，只有取元素和修改元素值的操作。,数组的抽象数据类型的定义,ADT Array 数据对象：Da j1 j2 jn|ji=0,.,bi-1,i=1,2,.,n,n(0)称为数组的维数，bi 是数组第 i 维的长度，ji 是数组元素的第 i 维下标，a j1 j2 jnElemSet 数据关系：RR1,R2,.,Rn Ri|0jkbk-1,1

4、kn 且 ki,0jibi-2,aj1jijn,aj1ji+1jnD,i=2,.,n,数据对象:D=aij|0 i b1-1,0 j b2-1 数据关系:R=ROW,COL ROW=|0 i b1-2,0 j b2-1 COL=|0 i b1-1,0 j b2-2,二维数组的抽象数据类型的数据对象和数据关系的定义,基本操作：InitArray(&A,n,bound1,.,boundn)操作结果：若维数 n 和各维长度合法，则构造相应的数组 A，并返回 OK。DestroyArray(&A)操作结果：销毁数组 A。Value(A,&e,index1,.,indexn)初始条件：A 是 n 维数组

5、，e 为元素变量，随后是 n 个下标值。操作结果：若各下标不超界，则 e 赋值为所指定的A的元素值，并返回 OK。Assign(&A,e,index1,.,indexn)初始条件：A 是 n 维数组，e 为元素变量，随后是 n 个下标值。操作结果：若下标不超界，则将 e 的值赋给所指定的A的元素，并返回 OK。ADT Array,数组特点：结构固定维数和维界不变。,数组基本操作：初始化、销毁、取元素、修改元素值。,5.2 数组的顺序表示和实现,一般不做插入和删除操作。,因为,所以：,一般都是采用顺序存储结构来表示数组。,注意：数组可以是多维的，但存储数据元素的内存单元地址 是一维的，因此，在存

6、储数组结构之前，需要解决将 多维关系映射到一维关系的问题。,两种顺序存储方式,以行序为主序(低下标优先)BASIC、COBOL和PASCAL,以列序为主序(高下标优先)FORTRAN,以行序为主序存放：,二维数组中任一元素 aij 的存储位置 LOC(i,j)=LOC(0,0)+(b2ij)L,某个元素的地址就是它前面所有行 所占的单元加上它所在行前面所有列元 素所占的单元数之和。,二维数组的映象函数,按列序为主序存放,二维数组中任一元素 aij 的存储位置 LOC(i,j)=LOC(0,0)+(b1ji)L,某个元素的地址就是它前面所有列 所占的单元加上它所在列前面所有行元 素所占的单元数之

7、和。,例 1：一个二维数组 A，行下标的范围是 1 到 6，列下标 的范围是 0 到 7，每个数组元素用相邻的 6 个字节 存储，存储器按字节编址。那么，这个数组的体积 是 个字节。,答：Volume=mnL=(6 1+1)(7 0+1)6=486=288,288,例 2：某校计算机系考研题 设数组 A059,069 的基地址为 2048，每个元素占 2 个 存储单元，若以列序为主序顺序存储，则元素 A31,57 的存储 地址为。,解：LOC(i,j)=LOC(31,57)=LOC(0,0)+(b1ji)L=2048+(605731)2=8950,8950,作业：5.1,5.3 矩阵的压缩存储

8、,矩阵定义：一个由 mn 个元素排成的 m 行（横向）n 列（纵向）的表。,矩阵的常规存储：将矩阵描述为一个二维数组。,矩阵的常规存储的特点：可以对其元素进行随机存取；矩阵运算非常简单；存储的密度为 1。,不适宜常规存储的矩阵：值相同的元素很多且呈某种规律 分布；零元素多。,矩阵的压缩存储：为多个相同的非零元素只分配一个存储 空间；对零元素不分配空间。,5.3.1 特殊矩阵,特殊矩阵：元素值的排列具有一定规律的矩阵。,对称矩阵、下（上）三角矩阵、对角线矩阵等。,1、对称矩阵 在一个 n 阶方阵 A 中，若元素满足下述性质：aij=aji 1 i,j n 则称 A 为对称矩阵。,对称矩阵上下三角

9、中的元素数均 为：n(n+1)/2 可以行序为主序将元素存放在一 个一维数组 san(n+1)/2 中。,对称矩阵的存储结构,k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1,以行序为主序存储下三角：,则 aij 和 sak 存在着一一对应关系：,aij 前的 i-1 行有 1+2+(i-1)=i(i-1)/2 个元素，在第 i 行上有 j 个元素。,因为aij=aji，所以只要交换上述 对应关系式中的 i 和 j 即可。,k=0 1 2 3 4 n(n-1)/2,以行序为主序存储下三角：,2、三角矩阵 以主对角线划分，三角矩阵有上（下）三角两种。上（下）三角矩阵的下（上）三角（

10、不含主对角线）中的元素均为常数。在大多数情况下，三角矩阵常数为零。,三角矩阵的存储：除了存储主对角线及上（下）三角中的元 素外，再加一个存储常数 c 的空间。,3、对角矩阵 在对角矩阵中，所有的非零元素集中在以主对角线为中心的 带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角 线上的元素之外，其余元素皆为零。,对角矩阵可按行优先顺序或对角线的顺序，将其压缩存储到 一维数组中，且也能找到每个非零元素和向量下标的对应关系。,5.3.2 稀疏矩阵,稀疏矩阵：设在 mn 的矩阵中有 t 个非零元素。令=t/(mn)当 0.05 时称为稀疏矩阵。,压缩存储原则：存各非零元的值、行列位置和矩阵的行

11、列数。,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)唯一确定。,三元组(i,j,aij)惟一确定矩阵的一个非零元。,三元组的不同表示方法可决定稀疏矩阵不同的压缩存储方法。,#define MAXSIZE 12500/假设非零元个数的最大值 typedef struct int i,j;/该非零元的行列下标 Elemtype e;Triple;typedef struct Triple dataMAXSIZE+1;int mu,nu,tu;/矩阵的行、列数和非零元个数 TSM

12、atrix;,i j tu,0 1 2 3 4 5 6 7 8,稀疏矩阵的压缩存储方法顺序存储结构,1、三元组顺序表,转置矩阵：一个 mn 的矩阵 M，它的转置 T 是一个 nm 的矩阵，且 T(i,j)=M j,i，1in，1jm，即 M 的行是 T 的列，M 的列是 T 的行。,求转置矩阵,问题描述：已知一个稀疏矩阵的三元组表，求该矩阵转置矩 阵的三元组表。,i j tu,0 1 2 3 4 5 6 7 8,解决思路：,将矩阵行、列 维数互换,将每个三元组 中的 i 和 j 相 互调换,重排三元组次 序，使 b.data 中元素以 T 的 行(M的列)为 主序。,M.data,i j tu

13、,0 1 2 3 4 5 6 7 8,T.data,T.data,i j tu,0 1 2 3 4 5 6 7 8,7 6 8,2 1 12,3 1 9,1 3-3,6 3 14,3 4 24,2 5 18,1 6 15,4 6-7,方法一：按 M 的列序转置,为找到 M 中每一列所有非零元素，需对其三元组表 M.data 从第一行起扫描一遍。由于 M 的列是 T 的行，且 T.data 中以 M 行序为主序，所以由此得到的 T.data 必定是按行优先存放的。,T.data,M.data,1 3-3,1 6 15,2 1 12,2 5 18,3 1 9,3 4 24,4 6-7,6 3 14

14、,typedef struct Triple dataMAXSIZE+1;int mu,nu,tu;/行、列、非零元数 TSMatrix;,Status TransposeSMatrix(TSMatrix M,TSMatrix/TransposeSMatrix,时间复杂度：O(nutu),若 tu 与munu 同数量级，则为：O(munu2),1 3-3,1 6 15,2 1 12,2 5 18,3 1 9,3 4 24,4 6-7,6 3 14,7 6 8,for(col=1;col=nu;+col)for(row=1;row=mu;+row)Tcolrow=Mrowcol;,一般矩阵转置算

15、法：,一般矩阵转置算法时间复杂度：O(munu),用三元组顺序表存储的矩阵转置算法时间复杂度：O(nutu),若 tu 与munu 同数量级，则为：O(munu2),算法仅适用于 tu munu 的情况。,结论,用三元组顺序表存储稀疏矩阵节约存储空间（优点）；,tu与munu同数量级时，算法时间复杂度高（缺点）；,方法二：按 M 的行序转置 快速转置,T.data,M.data,实施步骤：,1、确定 M 的第 1 列的第 1 个非零元在 T.data 中的位置。,1,3、确定 M 的第 col 列的第一个非零元在 T.data 中的位置。,2、确定 M 的第 col-1 列的非零元个数。,存入

16、数组 numM.nu,存入数组 cpotM.nu,cpot1=1;,cpotcol=cpotcol 1+numcol 1 2cola.nu,Status FastTransposeSMatrix(TSMatrix M,TSMatrix/求 M 中各列的第一个非零元在 T.data 中的序号,7 6 8,0 0 0 0 0 0 0,1,1,1,1,2,2,2,1,1,3,5,7,8,8,9,for(p=1;p=M.tu;+p)/转置矩阵元素 col=M.datap.j;q=cpotcol;T.dataq.i=M.datap.j;T.dataq.j=M.datap.i;T.dataq.e=M.da

17、tap.e;+cpotcol;/for/if return OK;/FastTransposeSMatrix,7 6 8,2,1,12,4,3,1,9,6,1,3,-3,2,6,3,14,9,3,4,24,7,2,5,18,5,1,6,15,3,4,6,-7,8,0 12345678,0 12345678,Status FastTransposeSMatrix(TSMatrix M,TSMatrix/FastTransposeSMatrix,时间复杂度为:,O(nu+tu),若 tu 与munu 同数量级，则为：O(munu),三元组顺序表又称有序的双下标法。,三元组顺序表的优点：非零元在表中

18、按行序有序存储，因此便于进行依行顺序处理的矩阵运算。,三元组顺序表的缺点：不能随机存取。若按行号存取某 一行中的非零元，则需从头开始进行查找。,2、行逻辑联接的顺序表（带行表的三元组）,在稀疏矩阵中，若要随机存取任意一行的非零元，需要知道 每一行的第一个非零元在三元组表中的位置，而这必须从第一个 元素起进行搜索查询。,若在稀疏矩阵的存储结构中增加一个行表 rpos 快速转置算法中的 cpot，指示稀疏矩阵中每行的 非零元素在三元组表中的起始位置，则不必从第一个 元素起进行搜索查询。称这种“带行链接信息”的三元 组表为：行逻辑联接的顺序表。,#define MAXSIZE 12500/假设非零元

19、个数的最大值 typedef struct int i,j;/该非零元的行列下标 Elemtype e;Triple;typedef struct Triple dataMAXSIZE+1;int mu,nu,tu;/矩阵的行、列数和非零元个数 TSMatrix;,int rposMAXRC+1;/指示各行第一个非零元的位置,两个稀疏矩阵相乘时，可以看出这种表示方法的优越性。,RLSMatrix;,矩阵乘法,设矩阵 M 是 m1n1 矩阵，N 是 m2n2 矩阵；只有 n1=m2 时，才能相乘得到结果矩阵 Q=MN（一个 m1n2 的矩阵）。,矩阵相乘的经典算法：,for(i=1;i=m1;i

20、+)for(j=1;j=n2;j+)Qij=0;for(k=1;k=n1;k+)Qij=Qij+Mik*Nkj;,不论是否为零，都要进行一次乘法运算。,没必要！,Mik*Nkj;,6,-1,0,0,4,注意：两个稀疏矩阵相乘的结果 不一定是稀疏矩阵。,int MulSMatrix(RLSMatrix M,RLSMatrix N,RLSMatrix*Q)if(M.nu!=N.mu)return ERROR;Q.mu=M.mu;Q.nu=N.nu;Q.tu=0;/Q 初始化 if(M.tu*N.tu!=0)/Q 是非零矩阵 for(arow=1;arow=M.mu;+arow)/逐行处理 M ct

21、emp=0;/当前行各元素的累加器清零 Q.rposarow=Q.tu+1;if(arowM.mu)tp=M.rposarow+1;else tp=M.tu+1;for(p=M.rposarow;pM.rposarow+1;+p)/对当前行中每一个非零元找到对应元在 N 中的行号 brow=M.datap.j;if(brow N.nu)t=N.rposbrow+1;else t=N.tu+1;,for(q=N.rposbrow;q MAXSIZE)return ERROR;Q.dataQ.tu=arow,ccol,ctempccol;/if/for arow/if return OK;/Mul

22、tSMatrix,上述算法的时间复杂度分析：累加器ctemp初始化的时间复杂度为 O(M.muN.mu)求Q的所有非零元的时间复杂度为 O(M.tuN.tu/N.mu)进行压缩存储的时间复杂度为 O(M.muN.nu)总的时间复杂度就是 O(M.muN.nu+M.tuN.tu/N.mu)。若M是m行n列的稀疏矩阵，N是n行p列的稀疏矩阵，则M中 非零元的个数 M.tu=d Mmn，N中非零元的个数 N.tu=d Nnp，相乘算法的时间复杂度就是 O(mp(1+nd Md N)，当d M0.05 和d N0.05 及 n 1000时，相乘算法的时间复杂度就相当于 O(mp)。显然，这是一个相当理

23、想的结果。如果事先能估算出所求 乘积矩阵Q不再是稀疏矩阵，则以二维数组表示Q，相乘的 算法也就更简单了。,3、稀疏矩阵的链式存储结构：十字链表,优点：它能够灵活地插入因运算而产生的新的非零元素，删除 因运算而产生的新的零元素，实现矩阵的各种运算。,在十字链表中，矩阵的每一个非零元素用一个结点表示，该结点除了（row，col，value）以外，还要有两个域：,right：用于链接同一行中的下一个非零元素；down：用以链接同一列中的下一个非零元素。,十字链表中结点的结构示意图：,M.rhead,M.chead,M.rhead,M.chead,十字链表的结构类型说明如下：,typedef stru

24、ct OLNode int i,j;/非零元素的行和列下标 ElementType e;struct OLNode*right,*down;/非零元素所在行表列表的后继链域 OLNode;*OLink;typedef struct OLink*rhead,*chead;/行、列链表的头指针向量基址 int mu,nu,tu;/稀疏矩阵的行数、列数、非零元个数 CrossList;,建立稀疏矩阵的十字链表算法：,CreateCrossList(CrossList*M)/采用十字链表存储结构，创建稀疏矩阵M if(M!=NULL)free(M);scanf(/生成结点,if(M-row_headi

25、=NULL)M-row_headi=p;else/*寻找行表中的插入位置*/for(q=M-row_headi;q-right/*完成插入*/,两个矩阵相加的算法描述：,(1)初始令pa和pb分别指向A和B的第一行的第一个非零元素的结点，即paA.rhead1;pbB.rhead1;pre=NULL;且令hl初始化 for(j=1;jjpb-j（即A的这一行中非零元素已处理完），则需在A中插入一个pb所指结点的复制结点。假设新结点的地址为p，则A的行表中的指针作如下变化：if pre=NULL rheadp-i=p;else pre-rightp;p-rightpa;pre=p;,A的列链表中

26、的指针也要作相应的改变。首先需从hlp-j开始找到新结点在同一列中的前驱结点，并让hlp-j指向它，然后在列链表中插入新结点：if cheadp-j=NULL cheadp-j=p;p-down=NULL;else p-downhlp-j-down;hlp-j-downp;hlp-j=p;若pa-jpb-j且pa-j!=0，则令pa指向本行下一个非零元结点，即 prepa;papa-right;若pa-j=pb-j，则将B中当前结点的值加到A中当前结点上，即pa-epb-e;,此时若pa-e!=0，则指针不变，否则删除A中该结点，即行表中指针变为：if pre=NULL rheadpa-i=p

27、a-right;else pre-rightpa-right;p=pa;pa=pa-right;同时，为了改变列表中的指针，需要先找到同一列中的前驱结点，且让hlpa-j指向该结点，然后如下修改相应指针：if cheadp-j=pcheadp-j=hlp-j=p-down;else hlp-j-downp-down;free(p);(3)若本行不是最后一行，则令pa和pb指向下一行的第一个非零元结点，转(2)；否则结束。此算法时间复杂度：O(ta+tb),广义表（又称列表 Lists）是 n0 个元素 a0,a1,an-1 的有限序列，其中每一个 ai 或者是原子，或者是一个子表。,5.4 广

28、义表的定义,例：中国举办的国际足球邀请赛，参赛队名单可表示如下：（阿根廷，巴西，德国，法国，（），西班牙，意大利，英国，（国家队，鲁能，实德）,在这个表中，韩国队应排在法国队后面，但由于其水平低 未敢参加，成为空表。国家队、鲁能队、实德队均作为东道主 的参赛队参加，构成一个小的线性表，成为原线性表的一个数 据元素。这种拓宽了的线性表就是广义表。,单个元素,广义表通常记作：,LS=(a1，a2，an),其中：LS 为表名，n 为表的长度，每一个 ai 为表的元素。,习惯上，一般用大写字母表示广义表，小写字母表示原子。,表头：若 LS 非空(n1)，则其第一个元素 a1 就是表头。记作 head(

29、LS)=a1。注：表头可以是原子，也可以是子表。,表尾：除表头之外的其它元素组成的表。记作 tail(LS)=(a2,.,an)。注：表尾不是最后一个元素，而是一个子表。,(1)A=(),例：,空表，长度为 0。,(2)B=(),(3)C=(a,(b,c),长度为 1，表头、表尾均为()。,长度为 2，由原子 a 和子表(b,c)构成。,(4)D=(x,y,z),表头为 a；表尾为(b,c)。,长度为 3，每一项都是原子。,(5)E=(C,D),表头为 x；表尾为(y,z)。,(6)F=(a,F),长度为 2，每一项都是子表。,表头为 C；表尾为(D)。,长度为 2，第一项为原子，第二项为它本

30、身。,F=(a,(a,(a,),表头为 a；表尾为(F)。,广义表的性质,(1)广义表中的数据元素有相对次序；,广义表的长度定义为最外层所包含元素的个数；如：C=(a,(b,c)是长度为 2 的广义表。,(3)广义表的深度定义为该广义表展开后所含括号的重数；A=(b,c)的深度为 1，B=(A,d)的深度为 2，C=(f,B,h)的 深度为 3。注意：“原子”的深度为 0;“空表”的深度为 1。,(4)广义表可以为其他广义表共享；如：广义表 B 就共享表 A。在 B 中不必列出 A 的值，而是通过名称来引用。,(5)广义表可以是一个递归的表。如：F=(a,F)=(a,(a,(a,)注意：递归表

31、的深度是无穷值，长度是有限值。,广义表是多层次结构，广义表的元素可以是单元素，也可以 是子表，而子表的元素还可以是子表，。可以用图形象地表示。,例：,D=(E,F),其中：E=(a,(b,c)F=(d,(e),D,a,d,b,c,e,E,F,广义表可以看成是线性表的推广，线性表是广义表的特例。广义表的结构相当灵活，在某种前提下，它可以兼容线性 表、数组、树和有向图等各种常用的数据结构。当二维数组的每行（或每列）作为子表处理时，二维数组 即为一个广义表。另外，树和有向图也可以用广义表来表示。由于广义表不仅集中了线性表、数组、树和有向图等常见 数据结构的特点，而且可有效地利用存储空间，因此在计算机

32、 的许多应用领域都有成功使用广义表的实例。,取表头运算 GetHead 和取表尾运算 GetTail,若广义表 LS=(a1,a2,an)，则 GetHead(LS)=a1。GetTail(LS)=(a2,an)。注意：取表头运算得到的结果可以是原子，也可以是一个子表。取表尾运算得到的结果一定是一个子表。,例:D=(E,F)=(a,(b,c)，F),GetHead(D)=E GetTail(D)=(F),GetHead(E)=a GetTail(E)=(b,c),GetHead(b,c)=(b,c)GetTail(b,c)=(),GetHead(b,c)=b GetTail(b,c)=(c),

33、GetHead(c)=c GetTail(c)=(),广义表基本运算,5.5 广义表的存储结构,由于广义表是递归定义的，其中的数据元素可具有不同的结 构（原子或列表），故难以用顺序存储结构表示，故常采用链式 存储结构，每个数据元素用一个结点表示，并称之为广义链表。,1、首尾链表(单链存储结构),若广义表不空，则可分解成表头和表尾；反之，一对确定的表头和表尾可惟一地确定一个广义表。首尾表示法就是根据这一性质设计而成的一种存储方法。,结点的结构形式,标志域 tag=1指示表头的指针域 hp 指示表尾的指针域 tp,表结点由三个域组成,原子结点由两个域组成,标志域 tag=0 值域 atom,typ

34、edef enum ATOM,LIST ElemTag;/ATOM=0：单元素；LIST=1：子表typedef struct GLNode Elemtag tag;/标志域，用于区分元素结点和表结点 union/元素结点和表结点的联合部分 Atomtype atom;/atom 是原子结点的值域 struct struct GLNode*hp,*tp;ptr;/ptr是表结点的指针域，ptr.hp 和 ptr.tp分别/指向表头和表尾;*GList;/广义表类型,结点的链接,A=(),A=NULL,B=(e),B,C=(a,(b,c,d),C,(b,c,d),(c,d),(b,c,d),(d

35、),D,D=(A,B,C),(B,C),(C),E=(a,E),E,(E),采用首尾表示法容 易分清列表中原子 或子表所在的层次,最高层的表结点的个 数即为广义表的长度,2、扩展线性链表（孩子兄弟链表双链存储法）,在孩子兄弟链表中，也有两种结点形式：一种是有孩子结 点，用以表示列表；另一种是无孩子结点，用以表示单元素。,结点的结构形式,表结点,原子结点,指向第一个孩子,指向下一个兄弟,元素值,指向兄弟,C,C=(a,(b,c,d),typedef enum ATOM,LIST Elemtag;/ATOM=0：单元素；LIST=1：子表 typedef struct GLNode Elemtag

36、 tag;/标志域，用于区分元素结点和表结点 union/元素结点和表结点的联合部分 Atomtype atom;/atom 是原子结点的值域 struct GLNode*hp;/表结点的表头指针;struct GLNode*tp;/指向下一个结点*GList;/广义表类型,A=(),A,B=(e),B,结点的链接,C,C=(a,(b,c,d),D,D=(A,B,C),E=(a,E),E,表达式中的左括号“（”对应 存储表示中的 tag=1 的结点,最高层结点 tp 域必为 NULL,1、了解数组的两种存储表示方法，并掌握数组在以行 为主的存储结构中的地址计算方法；2、掌握对特殊矩阵进行压缩存储时的下标变换公式；3、了解稀疏矩阵的两种压缩存储方法的特点和适用范 围，理解以三元组表示稀疏矩阵时进行矩阵运算采 用的处理方法；4、掌握广义表的结构特点及其存储表示方法，会对非 空广义表进行分解。,教学要求,作业：,5.1、5.10、5.11-(1、2、3)、5.12-(2)、5.13-(1),