1、数据结构实验五矩阵的压缩存储与运算学习资料数据结构实验五矩阵的压缩存储与运算第五章 矩阵的压缩存储与运算【实验目的】1. 熟练掌握稀疏矩阵的两种存储结构(三元组表和十字链表)的实现；2. 掌握稀疏矩阵的加法、转置、乘法等基本运算；3. 加深对线性表的顺序存储和链式结构的理解。 第一节知识准备矩阵是由两个关系（行关系和列关系）组成的二维数组，因此对每一个关系上都可以用线性表进行处理；考虑到两个关系的先后，在存储上就有按行优先和按列优先两种存储方式，所谓按行优先，是指将矩阵的每一行看成一个元素进行存储；所谓按列优先，是指将矩阵的每一列看成一个元素进行存储；这是矩阵在计算机中用一个连续存储区域存放的
2、一般情形，对特殊矩阵还有特殊的存储方式。一、 特殊矩阵的压缩存储1. 对称矩阵和上、下三角阵若n阶矩阵A中的元素满足=（0i，jn-1）则称为n阶对称矩阵。对n阶对称矩阵，我们只需要存储下三角元素就可以了。事实上对上三角矩阵（下三角部分为零）和下三角矩阵（上三角部分为零），都可以用一维数组ma0.来存储A的下三角元素（对上三角矩阵做转置存储），称ma为矩阵A的压缩存储结构，现在我们来分析以下，A和ma之间的元素对应放置关系。问题已经转化为：已知二维矩阵Ai，j，如图5-1，我们将A用一个一维数组mak来存储，它们之间存在着如图5-2所示的一一对应关系。任意一组下标(i,j)都可在ma中的位置k
3、中找到元素mk=；这里：k=i(i+1)/2+j(ij) 图5-1下三角矩阵a00 a10 a11 a20 an-1,0 an-1,n-1k=0123n(n-1)/2n(n+1)/2-1图5-2下三角矩阵的压缩存储反之，对所有的k=0,1，2,n(n+1)/2-1，都能确定mak中的元素在矩阵A中的位置（i,j）。这里，i=d-1，（d是使sum=k的最小整数），j=。2. 三对角矩阵在三对角矩阵中，所有的非零元素集中在以主对角线为中心的带内状区域中，除了主对角线上和直接在对角线上、下方对角线上的元素之外，所有其它的元素皆为零，见图5-3。图5-3三对角矩阵A与下三角矩阵的存储一样，我们也可以
4、用一个一维数组ma0.3n-2来存放三对角矩阵A，其对应关系见图5-4。a00 a01 a10 a11 a12 an-1,n-2 an-1,n-1k=012343n-33n-2图5-4下三角矩阵的压缩存储A中的一对下标(i,j)与ma中的下标k之间有如下的关系：公式中采用了C语言的符号，int()表示取整，%表示求余。二、 稀疏矩阵在mn的矩阵中，有t个非零元。令=,称矩阵的稀疏因子，常认为0.05时称为稀疏矩阵。稀疏矩阵在工程中有着大量的应用，不少工程问题都可以转化为对稀疏矩阵的计算问题。如何进行稀疏矩阵的压缩存储呢？为节省存储空间，应只存储非零元素。除了存储非零元的值之外，还必须记下所在行
5、和列的位置（i,j），即一个三元组（i,j,）唯一确定了矩阵A的一个非零元素。1. 三元组顺序表以顺序存储结构来表示三元组表，则可称稀疏矩阵的一种压缩存储方式。/稀疏矩阵的三元组顺序表存储表示。#defineMaxSize10 /用户自定义typedefintDatatype; /用户自定义typedefstruct /定义三元组 inti； /非零元的行下标intj; /非零元的列下标 Datatypev; /非零元的数据值TriTupleNode;typedefstructTriTupleNodedataMaxSize; /非零元的三元组表intm,n,t; /矩阵行，列及三元组表长度Tr
6、iTupleTable;2. 十字链表当矩阵的非零元个数和位置在操作过程中变化较大时，就不宜采用顺序存储结构来表示三元组的线性表，采用纵横交叉的十字链表就比较好。在十字链表中，每个非零元可用一个含五个域的结点表示，其中i,j和e三个域分别表示该非零元所在的行、列和非零元的值，向右域right用以链接同一行中下一个非零元。向下域down用以链接同一列中下一个非零元。同一行中的非零元通过right域链接成一个线性链表，每个非零元既是某个行链表中的一个结点，又是某个列链表中的一个结点，整个矩阵构成了一个十字交叉的链表，故称这样的存储结构为十字链表，如图5-5所示。图5-5稀疏矩阵M的十字链表type
7、defintDatatype;/用户自定义typedefstructOLNode inti,j;/该非零元的行和列下标Datatypev;StructOLNode*right,*down/该非零元所在行表和列表的后继链域OLNode;*OLink;typedefstructOLink*rhead,*cheadintmu,nu,tu;CrossList;第二节 用三元组表实现稀疏矩阵的基本操作【问题描述】用三元组表实现稀疏矩阵的按列转置。【数据描述】typedefintDatatype;/用户自定义typedefstruct /定义三元组inti,j; /非零元素的行下标和列下标Datatype
8、v;TriTupleNode;typedefstruct /定义三元组表TriTupleNodedataMaxSize;intm,n,t; /矩阵行，列及三元组表长度TriTupleTable;【算法描述】按照列序来进行转置。为了找到每一列中所有的非零元素，需要对其三元组表从第一行起整个扫描一遍。StatusTransposeSMatrix(TriTupleTablea,TriTupleTable&b)b.m=a.n;b.n=a.m;b.t=a.t;if(b.t)q=0;for(col=1;col=a.n;+col)for(p=0;p=a.t;+p)if(a.datap.j=col)b.dat
9、aq.i=a.datap.j;b.dataq.j=a.datap.i;b.dataq.v=a.datap.v;+q;returnOK;【C源程序】#include#include#defineOk1#defineMaxsize10/用户自定义三元组最大长度typedefstruct/*定义三元组表*/inti，j;intv;TriTupleNode;typedefstruct/*定义三元组表*/TriTupleNodedataMaxsize;intm;intn;intt;/*矩阵行，列及三元组表长度*/TriTupleTable;voidInitTriTupleNode(TriTupleTab
10、le*a)/*输入三元组表*/inti,j,k,val,maxrow,maxcol;charcontiue;maxrow=0;maxcol=0;i=j=0;k=0;while(i!=-1&j!=-1)/*rol=-1&col=-1结束输入*/printf(inputrown);scanf(%d,&i);printf(inputcoln);scanf(%d,&j);printf(inputvaluen);scanf(%d,&val);a-datak.i=i;a-datak.j=j;a-datak.v=val;if(maxrowi)maxrow=i;if(maxcolm=maxrow;a-n=ma
11、xcol;a-t=k-1;voidshowMatrix(TriTupleTable*a)/*输出稀疏矩阵*/intp,q;intt=0;for(p=1;pm;p+)for(q=1;qn;q+)if(a-datat.i=p&a-datat.j=q)printf(%d,a-datat.v);t+;elseprintf(0);printf(n);TransposeSMatrix(TriTupleTable*a,TriTupleTable*b)intq,col,p;b-m=a-n;b-n=a-m;b-t=a-t;if(b-t)q=0;for(col=1;coln;+col)for(p=0;pt;+p)
12、if(a-datap.j=col)b-dataq.i=a-datap.j;b-dataq.j=a-datap.i;b-dataq.v=a-datap.v;+q;voidmain(void)TriTupleTable*a,*b;InitTriTupleNode(a);showMatrix(a);/*转置前*/TransposeSMatrix(a,b);showMatrix(b);/*转置后*/【测试数据】输入：输出：120014043072300008000078【说明】分析算法,主要的工作是在p和col的两重循环中完成，算法的时间复杂度为O(n*t)。如果非零元素个数t和m*n同数量级时，算法
13、的时间复杂度变为O(m*n2)。【实验题】1. 稀疏矩阵按行序进行转置。2. 两个稀疏矩阵的相加运算。第三节十字链表表示稀疏矩阵的基本操作【问题描述】两个相同行数和列数的稀疏矩阵用十字链表实现加法运算【数据描述】typedefstructele/*十字链表结点类型*/introw,col;doubleval;structele*right,*down;eleNode;【算法描述】(1)若q-jv-j，则需要在C矩阵的链表中插入一个值为bij的结点,，修改v=v-right。(2)如q-jj，则需要在C矩阵的链表中插入一个值为aij的结点，修改q=q-right。(3)若q-j=v-j且q-e+
14、v-e!=0，则需要在C矩阵的链表中插入一个值为aij+bij的结点，修改q=q-right,v=v-right。重复（1）-（3）完成一行的操作。修改p=p-down,u=u-down后，再继续下一行。【C源程序】#include#includetypedefstructele/*十字链表结点类型*/introw,col;intval;structele*right,*down;eleNode;/*建立一个元素全为零的稀疏矩阵的十字链表*/eleNode*createNullMat(intm,intn) /*m行n列*/eleNode*h,*p;intk;h=(eleNode*)malloc
15、(sizeof(eleNode); /*十字链表头结点*/h-row=m;h-col=n;h-val=0; /*行数、列数和非零元素个数*/h-right=(eleNode*)malloc(sizeof(eleNode)*n);h-down=(eleNode*)malloc(sizeof(eleNode)*m);for(p=h-down,k=0;kcol=1000; /*设矩阵不会超过1000列*/p-right=p; /*每个行链表是一个环*/p-down=kdown; /*使全部行链表头结点构成环*/for(p=h-right,k=0;krow=1000; /*设矩阵不会超过1000行*/
16、p-down=p; /*每个列链表是一个环*/p-right=kn-1?p+1:h-right; /*使全部列链表头结点构成环*/returnh;/intinsertNode(eleNode*a,introw,intcol,doubleval)/*在十字链表中插入一个结点*/eleNode*p,*q,*r,*u,*v;if(row=a-row|col=a-col)return-2; /*不合理的行列号*/r=(eleNode*)malloc(sizeof(eleNode);r-row=row;r-col=col;r-val=val;p=a-down+row;q=p-right;while(q-
17、colright;if(q-col=col)return-1; /*该行已有col列元素*/u=a-right+col;v=u-down;while(v-rowdown;if(v-row=row)return-1; /*该列已有row行元素*/p-right=r;r-right=q; /*插入到行链中*/u-down=r;r-down=v; /*插入到列链中*/a-val=val;return0; /*插入成功*/eleNode*readMat()/*输入数据建立十字链表*/eleNode*h;inti,j,m,n;intv;printf(输入稀疏矩阵的行数和列数);scanf(%d%d,&m
18、,&n);h=createNullMat(m,n);printf(输入有非零元素的行号)；scanf(%d,&i);while(i=0) /*逐行输入非零元素*/printf(输入非零元素的列号)；scanf(%d,&j);while(j=0) /*输入一行非零元素*/printf(输入非零元素的值);scanf(%d,&v);insertNode(h,i,j,v);printf(输入当前行下一个非零元素的列号（-1表示当前行一组数据结束）)；scanf(%d,&j);printf(输入下一行有非零元素的行号（-1表示输入结束）)；scanf(%d,&i);returnh;voidshowMa
19、t(eleNode*a)introw,col,i,j;eleNode*p;row=a-row;col=a-col;for(i=0;idown+i;p=p-right;for(j=0;jrow=i&p-col=j)printf(%d,p-val);p=p-right;elseprintf(0);printf(n);eleNode*matAdd(eleNode*a,eleNode*b)eleNode*r,*p,*q,*u,*v;r=createNullMat(a-row,a-col);p=a-down;u=b-down;do /*逐行相加*/q=p-right;v=u-right;while(q!
20、=p|v!=u) /*两矩阵中有一个一行未结束循环*/if(q-col=v-col) /*有相同列的元素*/if(q-val+v-val!=0) /*和非零插入*/insertNode(r,q-row,q-col,q-val+v-val);q=q-right;v=v-right;elseif(q-colcol) /*插入a的元素*/insertNode(r,q-row,q-col,q-val);q=q-right;else /*插入b的元素*/insertNode(r,v-row,v-col,v-val);v=v-right;p=p-down;u=u-down;while(p!=a-down)
21、;returnr;voidmain()eleNode*a,*b,*c;a=readMat();printf(an);showMat(a);b=readMat();printf(bn);showMat(b);c=matAdd(a,b);printf(cn);showMat(c);【测试数据】输入a矩阵:4000输入b矩阵:0101输出:41010509050000090010109010100输入数据注意事项：（1） 如上面a矩阵，应输入3行4列（2） 若某行有非零元素，则按下列格式（三元组格式）输入：行号列号值列号值列号值-1，如a矩阵的第0行，应输入004-1，最后的-1表示该行的一组数据输
22、入结束。（3）按以上格式逐行地输入数据，直到输入的行号的值为-1时，表示稀疏矩阵的全部数据输入结束。【说明】从一个结点来看，进行比较、修改指针所需的时间是一个常数；整个运算过程在于对A和B的十字链表逐行扫描，其循环次数主要取决于A和B矩阵中非零元素的个数ta和tb；由此算法的时间复杂度为O(ta+tb)。【实验题】1. 设矩阵采用十字链表存结构，试编写下列程序实现下列运算：del(hm,i,j,x)删除第i行第j列的结点。revise(hm,i,j)修改第i行第j列的结点的数据值。2. 上述例子采用的是新开辟c十字链表存放a矩阵和b矩阵之和，试用a存放a矩阵和b矩阵之和，改写上述例子。第四节思
23、考题1. 假设稀疏矩阵A的大小是mn，稀疏矩阵B的大小是n1（一维向量），A和B均采用三元组表示，编程实现C=AB，其结果C也采用三元组表形式输出。【简要分析】本题的关键是要确定i行j列的元素在三元组表中的位置，由于B是一个一维向量，在用三元组表进行矩阵相乘时并不方便，可以先将B做转置存放后，一遍扫描A就可以实现乘法。2.如果矩阵A中存在这样的一个元素Aij满足以下条件：Aij是第i行中值最小的元素，且又是第j列中值最大的元素，则称Aij为矩阵A的一个鞍点；假设稀疏矩阵A（大小是mn）已经用三元组表存放，编程实现求鞍点的算法，如果没有鞍点，也给出相应信息。【简要分析】如果A采用二维数组存放，本
24、题的解法是很容易的，只需要求出每行的最小元素，放入min0.m-1中，再求出每列的最大元，放入max0.n-1之中，如果某元素Aij，既在mini中，又在maxj中，则Aij必是鞍点。对三元组存放的A，在求max数组时会有一些困难，可参考教材，增设一个cpot数组和一个num数组，用来记录A的列元素。ChapterFiveCompressedstorageforMatrixanditsalgorithmsObjectives1. Tounderstandimplementationoftwostructuresofsparsematrix,Forexample,Triple_Tuple_TableandCross-List.2. Tounderstandbasiccomputationofaddition,transformation,andmultiplicationforsparsematrix.3. TobeabletounderstandthestructureofOrder_ListandLink_ListinLinear_List.
