第3章++稀疏矩阵和广义表.ppt

1、第三章 稀疏矩阵和广义表,3.1 稀疏矩阵 3.1.1 稀疏矩阵的定义 为了说明什么是稀疏矩阵，首先要知道什么是矩阵。矩阵（matrix）是一个具有m行n列的数表，共包含有mn个数(元素)，每个元素处在确定行和列的交点位置上，都与一对行号和列号唯一对应。当一个矩阵中的行数和列数相同时，即m=n时则称为n阶矩阵或方阵。如图3-1(a)就是一个34的矩阵，它包含3行、4列，具有12个元素，每个元素都对应着唯一的行号和列号，如第1行与第1列交点位置上的元素5对应的行号和列号均为1，第2,行与第4列交点位置上的元素9对应的行号和列号分别为2和4。 图3-1 矩阵和稀疏矩阵,稀疏矩阵（sparse ma

2、trix）是矩阵中的一种特殊情况，其非零元素的个数远远小于零元素的个数。如图3-1(b)就是一个56的稀疏矩阵，该矩阵中共有30个元素，其中非零元素为7个，占元素总数的7/30。在实际应用中，稀疏矩阵一般都比较大，非零元素所占的比例都比较小。如对于一个100100的稀疏矩阵，若非零元素的个数为200，则非零元素占总元素个数的比例仅为1/50。,2. 稀疏矩阵的三元组线性表表示 在计算机中存储矩阵的一般方法是采用二维数组，其优点是可以随机地访问每一个元 素，因而能够较容易地实现矩阵的各种运算，如转置运算、加法运算、乘法运算等。但对于稀疏矩阵来说，采用二维数组的存储方法既浪费大量的存储单元用来存放

3、零元素，又要在运算中花费大量的时间来进行零元素的无效计算，显然是不可取的。一种较好的方法是：只考虑存储占元素中极少数的非零元素。 对于稀疏矩阵中的每个非零元素，可用它所在的行号、列号以及元素值这三元组(i,j,aij)来表示。若把所有的三元组按照行号为主序（即为主关键字）、列号为辅序（即为次关键字，当行号相同时再考虑列号次序）进行排列，则就构成了一个表示稀疏矩阵的三元组线性表。图3-1(b)稀疏矩阵所对应的三元组线性表表示为： (1,1,3),(1,4,5),(2,3,-2),(3,1,1),(3,3,4),(3,5,6),(5,3,-1) 稀疏矩阵采用三元组线性表表示后，可以使用顺序或链接方

4、式存储，从而比采用二维数组存储要大大地节省存储空间。,3. 稀疏矩阵的运算概述 对稀疏矩阵的运算与对一般用二维数组所表示的矩阵的运算相同，通常为求一个稀疏矩阵的转置，计算两个矩阵的和，计算两个矩阵的乘积等。一个矩阵的转置结果仍是一个矩阵，该矩阵中的第i行与第j列交点位置上的元素等于被转置矩阵中第j行与第i列交点位置上的元素。两个矩阵的和仍然是一个矩阵，该矩阵中的第i行第j列位置上的元素等于两个相加矩阵中对应位置上的元素之和。两个相乘矩阵的乘积仍然是一个矩阵，该矩阵中的第i行第j列位置上的元素等于第一个乘数矩阵中的第i行与第二个乘数矩阵中的第j列上对应元素乘积之累加和。假定第一个乘数矩阵为Amn

5、，第二个乘数矩阵为Bnp，乘积结果矩阵为Cmp，则C中任一元素Cij等于 ，其中1im，1jp。,下面给出对稀疏矩阵的一些典型运算(操作)，假定用M表示一个采用三元组线性表存储的稀疏矩阵，其存储类型用标识符Matrix表示。 (1) 初始化稀疏矩阵M，使它成为不含任何元素的空矩阵 void InitMatrix(Matrix M) (2) 根据稀疏矩阵的三元组线性表建立稀疏矩阵的存储结构 void InlutMatrix(Matrix M),(3) 按照一定格式输出稀疏矩阵 void OutputMatrix(Matrix M) (4) 返回稀疏矩阵M的转置矩阵 Matrix Transpos

6、edMatrix(Matrix M (5) 返回稀疏矩阵M1和M2之和，要求两个矩阵的行、列数均分别相同 Matrix AddMatrix(Matrix M1, Matrix M2) (6) 返回稀疏矩阵M1和M2之乘积，要求M1的列数等于M2的行数 Matrix MultiplyMatrix(Matrix M1, Matrix M2),3.1.2 稀疏矩阵的存储结构 1. 顺序存储 稀疏矩阵的顺序存储就是对其相应的三元组线性表进行顺序存储。假定每个非零元素的三元组用如下记录结构定义： struct Triple int row, col; ElemType val; ; 其中row和col用

7、来分别存储元素的行号和列号，val用来存储元素值。 一个稀疏矩阵的顺序存储类型定义如下： struct SMatrix int m, n, t; struct Triple smMaxTerms+1; ;,其中m,n和t域分别用来存储稀疏矩阵的行数、列数和非零元素的个数，sm数组域用来顺序存储每个三元组元素，假定下标为0的元素sm0不用，从下标为1起使用。MaxTerms为一个事先定义的全局常量，其值要大于等于非零元素的个数t，由它决定sm数组的大小。例如，若用SMatrix类型的对象存储图3-1(b)所示的稀疏矩阵，则m,n和t域的值应分别为5,6和7，sm数组中的内容如图3-2所示。,2.

8、 链接存储 稀疏矩阵的链接存储就是对其相应的三元组线性表进行链接存储。下面介绍两种链接存储方法。 (1)带行指针向量的链接存储 在这种链接存储中，需要把具有相同行号的三元组结点按照列号从小到大的顺序链接成一个单链表，每个三元组结点的类型可定义为： struct TripleNode int row, col; /*存储行号和列号*/ ElemType val; /*存储元素值*/ struct TripleNode* next; /*指向同一行的下一个结点*/ ; 稀疏矩阵中的每一行对应一个单链表，每一个单链表都有一个表头指针，为了把它们保存起来，便于访问每一个单链表，需要使用一个行指针向量（

9、即一维数组），该向量中的第i个分量（即对应数组中下标为i的元素）用来存储稀疏矩阵中第i行所对应的单链表的表头指针。带行指针向量的链接存储类型定义如下： struct LMatrix int m, n, t; struct TripleNode* lmMaxRows+1; ;,其中，m、n和t分别用来保存稀疏矩阵的行数、列数和非零元素的个数，lm向量用来存储m个行单链表的表头指针，第i行单链表的表头指针存于第i分量lmi中，而第0分量lm0未用，MaxRows为全局变量，其值要大于等于所存储矩阵的行数。 例如，若利用LMatrix类型的对象存储图3-1(b)所示的稀疏矩阵，则链接存储结构如图3-

10、3所示，其中每个单链表中的结点由动态分配链接而成。,图3-3 带行指针向量的链接存储结构,3.1.3 稀疏矩阵的运算 1. 初始化运算 稀疏矩阵的存储类型不同，其初始化过程也不同，对于SMatrix类型的对象，初始化过程为： void InitMatrix1(struct SMatrix* M) M-m=0; M-n=0; M-t=0; 对于LMatrix类型的对象，其初始化如下： void InitMatrix2(struct LMatrix* M) int i; M-m=0; M-n=0; M-t=0; for(i=1; ilmi=NULL; 对于CLMatrix类型的对象，初始化过程为：

11、,void InitMatrix3(struct CLMatrix* M) int i; M-m=0; M-n=0; M-t=0; for(i=1; irmi=NULL; for(i=1; icmi=NULL; 2. 稀疏矩阵的建立 稀疏矩阵的建立假定采用键盘输入，输入时应按照对应三元组线性表中三元组排列的次序进行，可以每行输入一个三元组，行号、列号和元素值之间用空格分开，最后以按下回车键结束，当输入完所有三元组后，以输入一个特殊的三元组(0,0,0)结束整个输入过程。若稀疏矩阵采用SMatrix类型存储，则相应的输入算法为： void InputMatrix1(struct SMatrix*

12、 M, int m, int n) /*m和n分别表示稀疏矩阵的行数和列数*/ int k=0; int row, col; ElemType val;,M-m=m; M-n=n; printf(输入每个三元组:n); scanf(%d %d %d,while(row!=0) struct CrossNode *cp, *newp; k+; /*得到和建立一个新结点*/ newp=malloc(sizeof(struct CrossNode); newp-row=row; newp-col=col; newp-val=val; newp-right=newp-down=NULL; /*把新结点

13、链接到所在行单链表的末尾*/ cp=M-rmrow; if(cp=NULL) M-rmrow=newp; else while(cp-right!=NULL) cp=cp-right; cp-right=newp; /*把新结点链接到所在列单链表的末尾*/,cp=M-cmcol; if(cp=NULL) M-cmcol=newp; else while(cp-down!=NULL) cp=cp-down; cp-down=newp; /*输入下一个三元组*/ scanf(%d %d %d, 3.2 广义表 3.2.1 广义表的定义 广义表（generalized list）简称表，它是线性表的

14、推广。一个广义表是n(n0)个元素的一个序列，当n=0时则称为空表。在一个非空的广义表中，其元素可以是某一确定类型的对象(这种元素被称做单元素)，也可以是由单元素构成的表(这种元素可相对地被称做子表或表元素)。显然，广义表的定义是递归的，广义表是一种递归的数据结构。,设ai为广义表的第i个元素，则广义表的一般表示与线性表相同： (a1,a2,ai,ai+1,an) 其中n表示广义表的长度，即广义表中所含元素的个数，n0。 同线性表一样，也可以用一个标识符来命名一个广义表，如用LS命名上面的广义表，则为： LS=(a1,a2,ai,ai+1,an) 在广义表的讨论中，为了把单元素同表元素区别开来

15、，一般用小写字母表示单元素，用大写字母表示表，如： A=( ) B=(e) C=(a,(b,c,d) D=(A,B,C)=(),(e),(a,(b,c,d) E=(a,(a,b),(a,b),c) 其中A是一个空表，其长度为0；B是一个只含有单元素e的表，其长度为1；C中有两个元素，一个是单元素a，另一个是表元素(b,c,d)，C的长度为2；D中有三个元素，其中每个元素又都是一个表，D的长度为3；E中只含有一个元素，该元素是一个表，该表中包含有三个元素，其中后两个元素又都是表。,把每个表的名字（若有的话）写在其表的前面也是一种表示广义表的方法，对于上面的五个广义表可相应地表示为： A( ) B

16、(e) C(a,(b,c,d) D(A( ),B(e),C(a,(b,c,d) E(a,(a,b),(a,b),c) 若用圆圈和方框分别表示表（表元素）和单元素，并用线段把表和它的元素（元素结点应在其表结点的下方）连接起来，则可得到一个广义表的图形表示。如上面五个广义表的图形表示如图3-6所示。,图3-6 广义表的图形表示,3.2.2 广义表的存储结构 struct GNode int tag; /*标志域*/ union /*值域或子表的表头指针域*/ ElemType data; struct GNode* sublist; ; struct GNode* next; /*指向后继结点的指

17、针域*/ ;,3.2.3 广义表的运算 求广义表长度的递归算法如下： int LenthGList(struct GNode* GL) /*求GL所指向的广义表的长度*/ if(GL!=NULL) return 1+LenthGList(GL-next); else return 0; 下面是求一个广义表深度的算法： int DepthGList(struct GNode* GL) /*求GL所指向的广义表的深度*/ /*给max赋初值0*/ int max=0; /*遍历表中的每一个结点,求出所有子表的最大深度*/,while(GL!=NULL) if(GL-tag=1) /*递归调用求出一个子表的深度*/ int dep=DepthGList(GL-sublist); /*让max始终为同一层所求过的子表中深度的最大值*/ if(depmax) max=dep; GL=GL-next; /*使GL指向同一层的下一个结点*/ /*返回表的深度*/ return max+1; ,3.2.4 简单程序举例 该程序比较简单，如下所示： #include #include typede