您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 商业计划书 > 数据结构实验五矩阵的压缩存储与运算
第五章矩阵的压缩存储与运算【实验目的】1.熟练掌握稀疏矩阵的两种存储结构(三元组表和十字链表)的实现;2.掌握稀疏矩阵的加法、转置、乘法等基本运算;3.加深对线性表的顺序存储和链式结构的理解。第一节知识准备矩阵是由两个关系(行关系和列关系)组成的二维数组,因此对每一个关系上都可以用线性表进行处理;考虑到两个关系的先后,在存储上就有按行优先和按列优先两种存储方式,所谓按行优先,是指将矩阵的每一行看成一个元素进行存储;所谓按列优先,是指将矩阵的每一列看成一个元素进行存储;这是矩阵在计算机中用一个连续存储区域存放的一般情形,对特殊矩阵还有特殊的存储方式。一、特殊矩阵的压缩存储1.对称矩阵和上、下三角阵若n阶矩阵A中的元素满足=(0≤i,j≤n-1)则称为n阶对称矩阵。对n阶对称矩阵,我们只需要存储下三角元素就可以了。事实上对上三角矩阵(下三角部分为零)和下三角矩阵(上三角部分为零),都可以用一维数组ma[0..]来存储A的下三角元素(对上三角矩阵做转置存储),称ma为矩阵A的压缩存储结构,现在我们来分析以下,A和ma之间的元素对应放置关系。问题已经转化为:已知二维矩阵A[i,j],如图5-1,我们将A用一个一维数组ma[k]来存储,它们之间存在着如图5-2所示的一一对应关系。任意一组下标(i,j)都可在ma中的位置k中找到元素m[k]=;这里:k=i(i+1)/2+j(i≥j)图5-1下三角矩阵a00a10a11a20…an-1,0…an-1,n-1k=0123…n(n-1)/2…n(n+1)/2-1图5-2下三角矩阵的压缩存储反之,对所有的k=0,1,2,…,n(n+1)/2-1,都能确定ma[k]中的元素在矩阵A中的位置(i,j)。这里,i=d-1,(d是使sum=k的最小整数),j=。2.三对角矩阵在三对角矩阵中,所有的非零元素集中在以主对角线为中心的带内状区域中,除了主对角线上和直接在对角线上、下方对角线上的元素之外,所有其它的元素皆为零,见图5-3。图5-3三对角矩阵A与下三角矩阵的存储一样,我们也可以用一个一维数组ma[0..3n-2]来存放三对角矩阵A,其对应关系见图5-4。a00a01a10a11a12…an-1,n-2an-1,n-1k=01234…3n-33n-2图5-4下三角矩阵的压缩存储A中的一对下标(i,j)与ma中的下标k之间有如下的关系:公式中采用了C语言的符号,int()表示取整,‘%’表示求余。二、稀疏矩阵在m×n的矩阵中,有t个非零元。令δ=,称δ矩阵的稀疏因子,常认为δ≤0.05时称为稀疏矩阵。稀疏矩阵在工程中有着大量的应用,不少工程问题都可以转化为对稀疏矩阵的计算问题。如何进行稀疏矩阵的压缩存储呢?为节省存储空间,应只存储非零元素。除了存储非零元的值之外,还必须记下所在行和列的位置(i,j),即一个三元组(i,j,)唯一确定了矩阵A的一个非零元素。1.三元组顺序表以顺序存储结构来表示三元组表,则可称稀疏矩阵的一种压缩存储方式。//稀疏矩阵的三元组顺序表存储表示。#defineMaxSize10//用户自定义typedefintDatatype;//用户自定义typedefstruct{//定义三元组inti;//非零元的行下标intj;//非零元的列下标Datatypev;//非零元的数据值}TriTupleNode;typedefstruct{TriTupleNodedata[MaxSize];//非零元的三元组表intm,n,t;//矩阵行,列及三元组表长度}TriTupleTable;2.十字链表当矩阵的非零元个数和位置在操作过程中变化较大时,就不宜采用顺序存储结构来表示三元组的线性表,采用纵横交叉的十字链表就比较好。在十字链表中,每个非零元可用一个含五个域的结点表示,其中i,j和e三个域分别表示该非零元所在的行、列和非零元的值,向右域right用以链接同一行中下一个非零元。向下域down用以链接同一列中下一个非零元。同一行中的非零元通过right域链接成一个线性链表,每个非零元既是某个行链表中的一个结点,又是某个列链表中的一个结点,整个矩阵构成了一个十字交叉的链表,故称这样的存储结构为十字链表,如图5-5所示。图5-5稀疏矩阵M的十字链表typedefintDatatype;//用户自定义typedefstructOLNode{inti,j;//该非零元的行和列下标Datatypev;StructOLNode*right,*down//该非零元所在行表和列表的后继链域}OLNode;*OLink;typedefstruct{OLink*rhead,*cheadintmu,nu,tu;}CrossList;第二节用三元组表实现稀疏矩阵的基本操作【问题描述】用三元组表实现稀疏矩阵的按列转置。【数据描述】typedefintDatatype;//用户自定义typedefstruct{//定义三元组inti,j;//非零元素的行下标和列下标Datatypev;}TriTupleNode;typedefstruct{//定义三元组表TriTupleNodedata[MaxSize];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.data[p].j==col){b.data[q].i=a.data[p].j;b.data[q].j=a.data[p].i;b.data[q].v=a.data[p].v;++q;}}returnOK;}【C源程序】#includestdio.h#includestring.h#defineOk1#defineMaxsize10//用户自定义三元组最大长度typedefstruct{/*定义三元组表*/inti,j;intv;}TriTupleNode;typedefstruct{/*定义三元组表*/TriTupleNodedata[Maxsize];intm;intn;intt;/*矩阵行,列及三元组表长度*/}TriTupleTable;voidInitTriTupleNode(TriTupleTable*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(inputrow\n);scanf(%d,&i);printf(inputcol\n);scanf(%d,&j);printf(inputvalue\n);scanf(%d,&val);a-data[k].i=i;a-data[k].j=j;a-data[k].v=val;if(maxrowi)maxrow=i;if(maxcolj)maxcol=j;k++;}a-m=maxrow;a-n=maxcol;a-t=k-1;}voidshowMatrix(TriTupleTable*a){/*输出稀疏矩阵*/intp,q;intt=0;for(p=1;p=a-m;p++){for(q=1;q=a-n;q++){if(a-data[t].i==p&&a-data[t].j==q){printf(%d,a-data[t].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;col=a-n;++col)for(p=0;pa-t;++p)if(a-data[p].j==col){b-data[q].i=a-data[p].j;b-data[q].j=a-data[p].i;b-data[q].v=a-data[p].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同数量级时,算法的时间复杂度变为O(m*n2)。【实验题】1.稀疏矩阵按行序进行转置。2.两个稀疏矩阵的相加运算。第三节十字链表表示稀疏矩阵的基本操作【问题描述】两个相同行数和列数的稀疏矩阵用十字链表实现加法运算【数据描述】typedefstructele{/*十字链表结点类型*/introw,col;doubleval;structele*right,*down;}eleNode;【算法描述】(1)若q-jv-j,则需要在C矩阵的链表中插入一个值为bij的结点,,修改v=v-right。(2)如q-jv-j,则需要在C矩阵的链表中插入一个值为aij的结点,修改q=q-right。(3)若q-j==v-j且q-e+v-e!=0,则需要在C矩阵的链表中插入一个值为aij+bij的结点,修改q=q-right,v=v-right。重复(1)--(3)完成一行的操作。修改p=p-down,u=u-down后,再继续下一行。【C源程序】#includestdio.h#includemalloc.htypedefstructele{/*十字链表结点类型*/introw,col;intval;structele*right,*down;}eleNode;/*建立一个元素全为零的稀疏矩阵的十字链表*/eleNode*createNullMat(intm,intn)/*m行n列*/{eleNode*h,*p;intk;h=(eleNode*)malloc(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;km;k++,p++){p-col=1000;/*设矩阵不会超过1000列*/p-right=p;/*每个行链表是一个环*/p-down=km-1?p+1:h-down;/*使全部行链表头结点构成环*/}for(p=h-right,k=0;kn;k++,p++){p-row=1000;/*设矩阵不会超过1000行*/p->down=p;/*每个列链表是一个环*/p->right=k<n-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
本文标题:数据结构实验五矩阵的压缩存储与运算
链接地址:https://www.777doc.com/doc-5360310 .html