2005年8月31日星期三,广东建设职业技术学院计算机系,1,3.1稀疏矩阵3.1.1稀疏矩阵的定义,矩阵（matrix）是一个具有m行n列的数表，共包含有mn个数(元素)，每个元素处在确定行和列的交点位置上，都与一对行号和列号唯一对应当一个矩阵中的行数和列数相同时，即m=n时则称为n阶矩阵或方阵稀疏矩阵的概念,2005年8月31日星期三,广东建设职业技术学院计算机系,2,3.1 稀疏矩阵 3.1.1稀疏矩阵的定义,稀疏矩阵（sparse matrix）是矩阵中的一种特殊情况，其非零元素的个数远远小于零元素的个数如图3-1(b)就是一个56的稀疏矩阵，该矩阵中共有30个元素，其中非零元素为7个，占元素总数的7/30稀疏矩阵的概念,2005年8月31日星期三,广东建设职业技术学院计算机系,3,3.1 稀疏矩阵 3.1.1稀疏矩阵的定义,一般方法是采用二维数组，其优点是可以随机地访问每一个元素，因而能够较容易地实现矩阵的各种运算，如转置运算、加法运算、乘法运算等但对于稀疏矩阵来说，采用二维数组的存储方法既浪费大量的存储单元用来存放零元素，又要在运算中花费大量的时间来进行零元素的无效计算，显然是不可取的。
一种较好的方法是：只考虑存储占元素中极少数的非零元素稀疏矩阵的三元组表示,2005年8月31日星期三,广东建设职业技术学院计算机系,4,3.1 稀疏矩阵 3.1.1稀疏矩阵的定义,稀疏矩阵中的每个非零元素，可用它所在的行号、列号以及元素值这三元组(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)) 稀疏矩阵采用三元组线性表表示后，可以使用顺序或链接方式存储，从而比采用二维数组存储要大大地节省存储空间稀疏矩阵的三元组表示,2005年8月31日星期三,广东建设职业技术学院计算机系,5,3.1 稀疏矩阵 3.1.1稀疏矩阵的定义,假定用M表示一个采用三元组线性表存储的稀疏矩阵，其存储类型用标识符Matrix表示 (1) 初始化稀疏矩阵M void InitMatrix(Matrix M) (2) 根据三元组线性表建立稀疏矩阵的存储结构 void InputMatrix(Matrix M) (3) 输出稀疏矩阵 void OutputMatrix(Matrix M) (4) 返回稀疏矩阵M的转置矩阵 Matrix TransposedMatrix(Matrix M) (5) 返回稀疏矩阵M1和M2之和 Matrix AddMatrix(Matrix M1, Matrix M2) (6) 返回稀疏矩阵M1和M2之乘积 Matrix MultiplyMatrix(Matrix M1, Matrix M2),稀疏矩阵的运算概述,2005年8月31日星期三,广东建设职业技术学院计算机系,6,3.1稀疏矩阵 3.1.2 稀疏矩阵的存储结构,每个非零元素的三元组用如下记录结构定义： struct Triple { int row, col; ElemType val; };row和col分别存储元素的行号和列号，val存储元素值。
一个稀疏矩阵的顺序存储类型定义如下： struct SMatrix { int m, n, t; struct Triple sm[MaxTerms+1]; }; 其中m,n和t域分别存储稀疏矩阵的行数、列数和非零元素的个数，sm数组域用来顺序存储每个三元组元素,稀疏矩阵的顺序存储,2005年8月31日星期三,广东建设职业技术学院计算机系,7,3.1稀疏矩阵 3.1.2 稀疏矩阵的存储结构,稀疏矩阵的顺序存储,下标1234567…Maxterms,row col val,MaxTerms为一个事先定义的全局常量，其值要大于等于非零元素的个数t，由它决定sm数组的大小例如，若用SMatrix类型的对象存储图3-1(b)所示的稀疏矩阵，则m,n和t域的值应分别为5,6和7，sm数组中的内容如图,2005年8月31日星期三,广东建设职业技术学院计算机系,8,3.1稀疏矩阵 3.1.2 稀疏矩阵的存储结构,稀疏矩阵的链接存储就是对其相应的三元组线性表进行链接存储 1、带行指针向量的链接存储把具有相同行号的三元组结点按照列号从小到大的顺序链接成一个单链表，每个三元组结点的类型可定义为： struct TripleNode { int row, col; /*存储行号和列号*/ ElemType val; /*存储元素值*/ struct TripleNode* next; /*指向同一行的下一个结点*/ };,稀疏矩阵的链接存储,2005年8月31日星期三,广东建设职业技术学院计算机系,9,3.1稀疏矩阵 3.1.2 稀疏矩阵的存储结构,稀疏矩阵中的每一行对应一个单链表，每一个单链表都有一个表头指针，为了把它们保存起来，便于访问每一个单链表，需要使用一个行指针向量（即一维数组），该向量中的第i个分量（即对应数组中下标为i的元素）用来存储稀疏矩阵中第i行所对应的单链表的表头指针。
带行指针向量的链接存储类型定义如下： struct LMatrix { int m, n, t; struct TripleNode* lm[MaxRows+1]; }; 其中，m、n和t分别用来保存稀疏矩阵的行数、列数和非零元素的个数，lm向量用来存储m个行单链表的表头指针，第i行单链表的表头指针存于第i分量lm[i]中，而第0分量lm[0]未用，MaxRows为全局变量，其值要大于等于所存储矩阵的行数,稀疏矩阵的链接存储,2005年8月31日星期三,广东建设职业技术学院计算机系,10,3.1稀疏矩阵 3.1.2 稀疏矩阵的存储结构,例如，若利用LMatrix类型的对象存储图3-1(b)所示的稀疏矩阵，则链接存储结构如图3-3所示，其中每个单链表中的结点由动态分配链接而成稀疏矩阵的链接存储,2005年8月31日星期三,广东建设职业技术学院计算机系,11,3.1稀疏矩阵 3.1.2 稀疏矩阵的存储结构,2、十字链接存储每个三元组结点的类型可定义为： struct CrossNode { int row, col; /*存储行号和列号*/ ElemType val; /*存储元素值*/ struct CrossNode* down,*right; /* right指向同一行的下一个结点;down指向同一列的下一个结点*/ };,稀疏矩阵的链接存储,2005年8月31日星期三,广东建设职业技术学院计算机系,12,3.1稀疏矩阵 3.1.2 稀疏矩阵的存储结构,稀疏矩阵的十字链接存储中需要使用两个指针向量，一个行指针向量存储行单链表的表头指针，一个列指针向量存储列单链表的表头指针。
稀疏矩阵的十字链接存储类型定义如下： struct CLMatrix { int m, n, t; struct CrossNode* rm[MaxRows+1]; struct CrossNode* cm[Maxcolumns+1]; }; 其中，m、n和t分别用来保存稀疏矩阵的行数、列数和非零元素的个数，MaxRows为全局变量，其值要大于等于所存储矩阵的行数; Maxcolumns为全局变量，其值要大于等于所存储矩阵的列数稀疏矩阵的链接存储,2005年8月31日星期三,广东建设职业技术学院计算机系,13,3.1稀疏矩阵 3.1.2 稀疏矩阵的存储结构,稀疏矩阵的十字链接存储示意图,稀疏矩阵的链接存储,,∧,2005年8月31日星期三,广东建设职业技术学院计算机系,14,3.1稀疏矩阵 3.1.3 稀疏矩阵的运算,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; i<=MaxRows; i++) M->lm[i]=NULL; },稀疏矩阵初始化运算,2005年8月31日星期三,广东建设职业技术学院计算机系,15,3.1稀疏矩阵 3.1.3 稀疏矩阵的运算,CLMatrix类型的对象，初始化过程为：void InitMatrix3(struct CLMatrix* M) { int i; M->m=0; M->n=0; M->t=0; for(i=1; i<=MaxRows; i++) M->rm[i]=NULL; for(i=1; i<=MaxColumns; i++) M->cm[i]=NULL; },稀疏矩阵初始化运算,2005年8月31日星期三,广东建设职业技术学院计算机系,16,3.1稀疏矩阵 3.1.3 稀疏矩阵的运算,void InputMatrix1(struct SMatrix* M, int m, int n) /*m和n分别表示稀疏矩阵的行数和列数*/ { int k=0，row, col; ElemType val; M->m=m; M->n=n; printf("输入每个三元组:\n"); scanf("%d %d %d",&row,&col,&val); while(row!=0) { k++; M->sm[k].row=row; M->sm[k].col=col; M->sm[k].val=val; scanf("%d，%d，%d",&row,&col,&val); } M->t=k; },稀疏矩阵的建立,struct Triple { int row, col; ElemType val; };struct SMatrix { int m, n, t; struct Triple sm[MaxTerms+1]; };,2005年8月31日星期三,广东建设职业技术学院计算机系,17,3.1稀疏矩阵 3.1.3 稀疏矩阵的运算,void InputMatrix3(struct CLMatrix* M, int m, int n) { int k=0; int row, col; ElemType val; M->m=m; M->n=n; printf("输入每个三元组:\n"); scanf("%d %d %d",&row,&col,&val); while(row!=0) { struct CrossNode *cp, *newp;,。