资源描述：
《第三章稀疏矩阵和广义表》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、3.1稀疏矩阵3.1.1稀疏矩阵的定义非零元素个数较少，且分布没有一定规律的矩阵第三章稀疏矩阵和广义表三元组线性表表示：只存矩阵的行列维数和每个非零元素的行列下标及其值.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）唯一确定稀疏矩阵的运算概述：与用二维数组所表示的矩阵的运算相同,通常为求一个稀疏矩阵的转置,计算两个矩阵的和,计算两个矩阵的乘积等。3.1.2稀疏矩阵的存储结构顺序存储结构三元组表#defineM20typedefstructnode{
2、inti,j;intv;}JD;JDma[M];三元组表所需存储单元个数为3(t+1)其中t为非零元个数678121213931-3361443245218611564-7maijv012345678ma[0].i,ma[0].j,ma[0].v分别存放矩阵行列维数和非零元个数行列下标非零元值课本中三元组用如下记录结构定义：structTriple{introw,col;ElemTypeval;};其中row和col用来分别存储元素的行号和列号，val用来存储元素值。一个稀疏矩阵的顺序存储类型定义如下：structSMatrix{intm,n,t;structTrip
3、lesm[MaxTerms+1];};链接存储结构带行指针向量的链接存储需要把具有相同行号的三元组结点按照列号从小到大的顺序链接成一个单链表，每个三元组结点的类型可定义为：structTripleNode{introw,col;/*存储行号和列号*/ElemTypeval;/*存储元素值*/structTripleNode*next;};/*指向同一行的下一个结点*/为便于访问每一个单链表，需要使用一个行指针向量（即一维数组），该向量中的第i个分量（即对应数组中下标为i的元素）用来存储稀疏矩阵中第i行所对应的单链表的表头指针。带行指针向量的链接存储类型定义如下：str
4、uctLMatrix{intm,n,t;structTripleNode*lm[MaxRows+1];};其中，lm向量用来存储m个行单链表的表头指针，MaxRows为全局变量，其值要大于等于所存储矩阵的行数。如对应以上矩阵的带行指针向量的链接存储十字链表设行指针数组和列指针数组，分别指向每行、列第一个非零元结点定义tpedefstructnode{introw,col,val;structnode*down,*right;}JD;rowcolvaldownright113418225234^^^^^^^十字链接存储3.2.1稀疏矩阵的运算稀疏矩阵的建立假定采用键盘输
5、入，输入时应按照对应三元组线性表中三元组排列的次序进行，可以每行输入一个三元组，行号、列号和元素值之间用空格分开，最后以按下回车键结束，当输入完所有三元组后，以输入一个特殊的三元组(0,0,0)结束整个输入过程。若稀疏矩阵采用SMatrix类型存储，则相应的输入算法为：voidInputMatrix1(structSMatrix*M,intm,intn){intk=0;introw,col;ElemTypeval;M->m=m;M->n=n;printf("输入每个三元组:");scanf("%d%d%d",&row,&col,&val);while(row!=0
6、){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;}稀疏矩阵的输出若稀疏矩阵采用SMatrix类型存储，则相应的输出算法为：voidOutputMatrix1(structSMatrix*M){inti;printf(“(”);for(i=1;it;i++){printf(“(%d,%d,%d),”,M->sm[i].row,M->sm[i].col,M->sm[i].val);}if(M->t!=0){printf(“
7、(%d,%d,%d),”,M->sm[i].row,M->sm[i].col,M->sm[i].val);}printf(“)”);}3.2广义表3.2.1广义表的定义广义表（generalizedlist）简称表，它是线性表的推广。一个广义表是n(n≥0)个元素的一个序列，当n=0时则称为空表。在一个非空的广义表中，其元素可以是某一确定类型的对象(这种元素被称做单元素)，也可以是由单元素构成的表(这种元素可相对地被称做子表或表元素)。显然，广义表的定义是递归的，广义表是一种递归的数据结构。设ai为广义表的第i个元素，则广义表的一般表示与线性表相
