数据结构实验五矩阵的压缩存储与运算

1、精选优质文档-倾情为你奉上第五章  矩阵的压缩存储与运算【实验目的】1. 熟练掌握稀疏矩阵的两种存储结构(三元组表和十字链表)的实现；2. 掌握稀疏矩阵的加法、转置、乘法等基本运算；3. 加深对线性表的顺序存储和链式结构的理解。 第一节 知识准备    矩阵是由两个关系（行关系和列关系）组成的二维数组，因此对每一个关系上都可以用线性表进行处理；考虑到两个关系的先后，在存储上就有按行优先和按列优先两种存储方式，所谓按行优先，是指将矩阵的每一行看成一个元素进行存储；所谓按列优先，是指将矩阵的每一列看成一个元素进行存储；这是矩阵在计算机中用

2、一个连续存储区域存放的一般情形，对特殊矩阵还有特殊的存储方式。一、 特殊矩阵的压缩存储1. 对称矩阵和上、下三角阵若n阶矩阵A中的元素满足   =  （0i，jn-1 ）则称为n阶对称矩阵。对n阶对称矩阵，我们只需要存储下三角元素就可以了。事实上对上三角矩阵（下三角部分为零）和下三角矩阵（上三角部分为零），都可以用一维数组ma0. 来存储A的下三角元素（对上三角矩阵做转置存储），称ma为矩阵A的压缩存储结构，现在我们来分析以下，A和ma之间的元素对应放置关系。问题已经转化为：已知二维矩阵Ai，j，如图5-1，我们将A用一个一

3、维数组mak来存储，它们之间存在着如图5-2所示的一一对应关系。 任意一组下标(i,j)都可在ma中的位置k中找到元素mk= ；这里：k=i(i+1)/2+j   (ij)  图5-1 下三角矩阵a00 a10 a11 a20 an-1,0 an-1,n-1k=  0        1      2      

4、;  3          n(n-1)/2     n(n+1)/2-1                    图5-2下三角矩阵的压缩存储反之，对所有的k=0,1，2,n(n+1)/2-1，都能确定mak中的元素在矩阵A中的位

5、置（i,j）。这里，i=d-1，（d是使sum=  > k的最小整数），j=  。2. 三对角矩阵在三对角矩阵中，所有的非零元素集中在以主对角线为中心的带内状区域中，除了主对角线上和直接在对角线上、下方对角线上的元素之外，所有其它的元素皆为零，见图5-3。 图5-3 三对角矩阵A与下三角矩阵的存储一样，我们也可以用一个一维数组ma0.3n-2来存放三对角矩阵A，其对应关系见图5-4。a00 a01 a10 a11 a12 an-1,n-2 an-1,n-1k=  0   

6、;     1      2        3      4             3n-3    3n-2      

7、;              图5-4下三角矩阵的压缩存储A中的一对下标(i,j)与ma中的下标k之间有如下的关系： 公式中采用了C语言的符号，int()表示取整，%表示求余。二、 稀疏矩阵在m×n 的矩阵中，有t个非零元。令= ,称矩阵的稀疏因子，常认为0.05时称为稀疏矩阵。稀疏矩阵在工程中有着大量的应用，不少工程问题都可以转化为对稀疏矩阵的计算问题。如何进行稀疏矩阵的压缩存储呢？为节省存储空间，应只存储非零元素

8、。除了存储非零元的值之外，还必须记下所在行和列的位置（i,j），即一个三元组（i,j,  ）唯一确定了矩阵A的一个非零元素。1. 三元组顺序表以顺序存储结构来表示三元组表，则可称稀疏矩阵的一种压缩存储方式。/稀疏矩阵的三元组顺序表存储表示。#define MaxSize 10   /用户自定义typedef int Datatype;  /用户自定义typedef struct   /定义三元组  int i； /非零元的行下标int j;

9、60; /非零元的列下标   Datatype v;  /非零元的数据值TriTupleNode;typedef structTriTupleNode dataMaxSize; /非零元的三元组表int m,n,t; /矩阵行，列及三元组表长度TriTupleTable;2. 十字链表当矩阵的非零元个数和位置在操作过程中变化较大时，就不宜采用顺序存储结构来表示三元组的线性表，采用纵横交叉的十字链表就比较好。在十字链表中，每个非零元可用一个含五个域的结点表示，其中i, j和e三个域分别表示该非零元所在的行、列和非零元

10、的值，向右域right用以链接同一行中下一个非零元。向下域down用以链接同一列中下一个非零元。同一行中的非零元通过right域链接成一个线性链表，每个非零元既是某个行链表中的一个结点，又是某个列链表中的一个结点，整个矩阵构成了一个十字交叉的链表，故称这样的存储结构为十字链表，如图5-5所示。 图5-5 稀疏矩阵M的十字链表typedef int Datatype; /用户自定义typedef struct OLNode   int i,j;    

11、60;             /该非零元的行和列下标Datatype v;      Struct OLNode *right,*down /该非零元所在行表和列表的后继链域OLNode;*OLink;typedef struct          

12、0;     OLink *rhead,*cheadint mu,nu,tu;CrossList;第二节 用三元组表实现稀疏矩阵的基本操作【问题描述】用三元组表实现稀疏矩阵的按列转置。【数据描述】typedef int Datatype; /用户自定义typedef struct /定义三元组int i,j;   / 非零元素的行下标和列下标Datatype v;TriTupleNode;typedef struct /定义三

13、元组表TriTupleNode dataMaxSize;int m,n,t; /矩阵行，列及三元组表长度TriTupleTable;【算法描述】按照列序来进行转置。为了找到每一列中所有的非零元素，需要对其三元组表从第一行起整个扫描一遍。Status TransposeSMatrix(TriTupleTable a, 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)    

14、0; for(p=0;p<=a.t;+p)      if(a.datap.j=col)b.dataq.i=a.datap.j;b.dataq.j=a.datap.i;b.dataq.v=a.datap.v;+q;return OK;【C源程序】#include <stdio.h>#include <string.h>#define Ok 1#define Maxsize 10 /用户自定义三元组最大长度typede

15、f struct     /*定义三元组表*/int i，j;int v;TriTupleNode;typedef struct  /*定义三元组表*/ TriTupleNode dataMaxsize; int m; int n; int t; /*矩阵行，列及三元组表长度*/ TriTupleTable; void InitTriTupleNode (T

16、riTupleTable *a)  /*输入三元组表*/ int i,j,k,val,maxrow,maxcol; char contiue; maxrow=0; maxcol=0; i=j=0; k=0; while(i!=-1&&j!=-1)   /*rol=-1&&col=-1结束输入*/ printf("input row n"); scanf(&

17、quot;%d",&i); printf("input col n"); scanf("%d",&j); printf("input valuen"); scanf("%d",&val); a->datak.i=i; a->datak.j=j; a->datak.v=val; if (maxrow<i) maxrow=i;

18、0;if (maxcol<j) maxcol=j; k+; a->m=maxrow;a->n=maxcol;a->t=k-1;  void showMatrix(TriTupleTable *a)   /*输出稀疏矩阵*/int p,q;  int t=0; for(p=1;p<=a->m;p+) for(q=1;q<=a->n;q+)   if&#

19、160;(a->datat.i=p&&a->datat.j=q)    printf("%d   ",a->datat.v);    t+;        else printf("0   ");       printf(&

20、quot;n"  );       TransposeSMatrix(TriTupleTable *a,TriTupleTable *b)  int q,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)

21、for(p=0;p<a->t;+p) if(a->datap.j=col)  b->dataq.i=a->datap.j;  b->dataq.j=a->datap.i;  b->dataq.v=a->datap.v;+q;      void main( void)   TriTupleTable *a,*b;   Ini

22、tTriTupleNode(a);   showMatrix(a);  /*转置前*/   TransposeSMatrix(a,b);   showMatrix(b);  /*转置后*/   【测试数据】  输入：                 

23、         输出：1 2 0 0                       1 4 04 3 0 7       

24、0;               2 3 00 0 0 8                       0 0 0   

25、                           0 7 8【说明】分析算法,主要的工作是在p和col的两重循环中完成，算法的时间复杂度为O(n*t)。如果非零元素个数t和m*n同数量级时，算法的时间复杂度变为O(m*n2)。【实验题】1. 稀疏矩阵按行序进行转置。2. 两个稀疏矩阵的相加运算。第三节&#

26、160;十字链表表示稀疏矩阵的基本操作【问题描述】两个相同行数和列数的稀疏矩阵用十字链表实现加法运算【数据描述】typedef struct ele /* 十字链表结点类型*/  int row, col;  double val;  struct ele *right, *down;eleNode;【算法描述】 (1) 若q->j>v->j，则需要在C矩阵的链表中插入一个值为bij的结点,，修改v

27、=v->right。(2) 如q->j<v->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源程序】#

28、include <stdio.h>#include <malloc.h>typedef struct ele /* 十字链表结点类型*/int row,col;int val;struct ele *right,*down;eleNode;/*建立一个元素全为零的稀疏矩阵的十字链表*/eleNode *createNullMat(int m,int n)  / * m行n列 */eleNode 

29、;*h,*p;int k;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;k<m;k+,p+

30、)p->col=1000;  / * 设矩阵不会超过1000列 */p->right=p;   / * 每个行链表是一个环 * /p->down=k<m-1?p+1:h->down;  / * 使全部行链表头结点构成环*/for(p=h->right,k=0;k<n;k+,p+)p->row=1000;  / * 设矩阵不会超过1000行 * /   

31、;p-down = p;   / * 每个列链表是一个环 * /   p-right = kn-1 ? p+1 : h-right;  / *使全部列链表头结点构成环 * /return h;/ int insertNode(eleNode *a ,int row,int col,double val)/*&

32、#160;在十字链表中插入一个结点*/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

33、->col<col)p=q;q=q->right; if(q->col=col) return -1;  / * 该行已有col列元素 * / u=a->right+col;v=u->down; while(v->row<row)u=v;v=v->down; if(v->row=row) return -1;  / * 该列已有row行元素 * /p-rig

34、ht = r; r-right = q;  / * 插入到行链中 * /u-down = r; r-down = v;  / * 插入到列链中 * /a->val=val; return 0;  / * 插入成功 * /    eleNode *readMat()/*输入数

35、据建立十字链表*/ eleNode *h; int i,j,m,n; int v; printf("输入稀疏矩阵的行数和列数");  scanf("%d%d",&m,&n); h=createNullMat(m,n);printf("输入有非零元素的行号")； scanf("%d",&i); while(i>=0)  / * 逐行输入非零

36、元素 * /   printf("输入非零元素的列号")；    scanf("%d",&j);    while(j>=0)  / * 输入一行非零元素 * /     printf("输入非零元素的值"); scanf("%d",&v);insertNo

37、de(h,i,j,v);   printf("输入当前行下一个非零元素的列号（-1表示当前行一组数据结束）")； scanf("%d",&j); printf("输入下一行有非零元素的行号（-1表示输入结束）")； scanf("%d",&i);  return h;  void showMat(eleNode *a) int row,col,i,j;

38、 eleNode *p; row=a->row; col=a->col; for (i=0;i<row;i+)    p=a->down+i;p=p->right;for(j=0;j<col;j+) if(p->row=i&&p->col=j) printf("%d  ",p->val);p=p->right; else printf(&qu

39、ot;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  / * 逐行相加 * /

40、60;q=p->right;v=u->right; while(q!=p|v!=u)  / * 两矩阵中有一个一行未结束循环 */   if(q->col=v->col)  / * 有相同列的元素 * /    if(q->val+v->val!=0) / * 和非零插入 * /insertNode(r,q->row,q->col,q-&g

41、t;val+v->val);q=q->right;v=v->right;    else if(q->col<v->col)  / * 插入a的元素 * /    insertNode(r,q->row,q->col,q->val);    q=q->right;       else /

42、 * 插入b的元素 * /   insertNode(r,v->row,v->col,v->val);   v=v->right;    p=p->down;u=u->down; while(p!=a->down); return r;  void main()  eleNode *a,*b,*c;  &#

43、160;a=readMat();   printf("an");   showMat(a);   b=readMat();   printf("bn");   showMat(b);  c= matAdd(a,b);  printf("cn");  showMat(c);  【测试数据】输入a

44、60;矩阵:  4  0  0  0       输入b矩阵: 0  1  0  1       输出:4  1  0  10  5  0  9    

45、;              0 5  0  0            0  0  0  90  0  1  0     

46、;             1  0  9  0             1  0  10 0输入数据注意事项：（1） 如上面a矩阵，应输入3行4列（2） 若某行有非零元素，则按下列格式（三元组格式）输入：行号  列号  值  列号  值    列号  值  -1，如a矩阵的第0行，应输入0