Chinaunix首页 | 论坛 | 博客

unixaaa的ChinaUnix博客unixaaa.blog.chinaunix.net

首页　| 　博文目录　| 　关于我

unixaaa

  • 博客访问： 44854
  • 博文数量： 44
  • 博客积分： 50
  • 博客等级： 民兵
  • 技术积分： 240
  • 用 户 组： 普通用户
  • 注册时间： 2011-12-16 06:05
文章分类

全部博文（44）

文章存档

2012年（32）

2011年（12）

我的朋友
最近访客
推荐博文
稀疏矩阵的存储与快速转置

分类：

2012-06-22 00:46:16

原文地址：稀疏矩阵的存储与快速转置 作者：何本俊夫


点击(此处)折叠或打开

  1. #include <stdio.h>
  2. #include <stdlib.h>

  4. typedef struct {
  5.     int row;
  6.     int col;
  7.     int e;
  8. }Triplet;
  9. typedef struct {
  10.     Triplet data[10];
  11.     int rows;
  12.     int cols;
  13.     int nums;
  14. }Table;

  16. void Create (Table *t,int *Matrix,int m,int n)
  17. {
  18.     int i,j;
  19.     /*
  20.     for (i=0;i<3;i++)
  21.     {
  22.     for (j=0;j<4;j++)
  23.             printf ("%d ",*(Matrix+i*n+j));
  24.         printf ("\n");
  25.     }
  26.     getch ();
  27.     */
  28.     t->rows=m;
  29.     t->cols=n;
  30.     t->nums=0;
  31.     for (i=0;i<m;i++)
  32.         for (j=0;j<n;j++)
  33.             if (*(Matrix+i*n+j)!=0)
  34.             {
  35.                 t->nums++;
  36.                 t->data[t->nums].row=i+1;
  37.                 t->data[t->nums].col=j+1;
  38.                 t->data[t->nums].e=*(Matrix+i*n+j);
  39.             }
  40. }
  41. void Trans (Table M,Table *T)
  42. {
  43.     int col,t,p,q;
  44.     int num[10];
  45.     int cpot[10];
  46.     T->rows=M.cols;
  47.     T->cols=M.rows;
  48.     T->nums=M.nums;
  49.     if (T->nums)
  50.     {
  51.         for (col=1;col<=M.cols;++col)
  52.             num[col]=0;
  53.         for (t=1;t<=M.nums;++t)
  54.             ++num[M.data[t].col];
  55.         cpot[1]=1;
  56.         for (col=2;col<=M.cols;++col)
  57.             cpot[col]=cpot[col-1]+num[col-1];
  58.         for (p=1;p<=M.nums;++p)
  59.         {
  60.             col=M.data[p].col;
  61.             q=cpot[col];
  62.             T->data[q].row=M.data[p].col;
  63.             T->data[q].col=M.data[p].row;
  64.             T->data[q].e=M.data[p].e;
  65.             ++cpot[col];
  66.         }
  67.     }

  69. }
  70. void ToMatrix(Table t,int *Matrix,int m,int n)
  71. {
  72.     int i,j;
  73.     for (i=0;i<m;i++)
  74.         for (j=0;j<n;j++)
  75.             *(Matrix+i*n+j)=0;
  76.     for (i=1;i<=t.nums;i++)
  77.     {
  78.         *(Matrix+(t.data[i].row-1)*n+(t.data[i].col-1))=t.data[i].e;
  79.     }
  80. }
  81. int main ()
  82. {
  83.     int i,j;
  84.     Table A,TA;
  85.     int MatrixA[3][4] =
  86.         {{3,0,0,5},
  87.          {0,-1,0,0},
  88.          {0,2,0,0}};
  89.     int MatrixB[4][3];
  90.     Create (&A,MatrixA,3,4);
  91.     Trans (A, &TA);
  92.     ToMatrix (TA,MatrixB,4,3);
  93.     for (i=0;i<4;i++)
  94.     {
  95.         for (j=0;j<3;j++)
  96.             printf ("%d ",MatrixB[i][j]);
  97.         printf ("\n");
  98.     }
  99. }

点击(此处)折叠或打开

  1. #include <stdio.h>
  2. #include <stdlib.h>

  4. typedef struct {
  5.     int row;
  6.     int col;
  7.     int e;
  8. }Triplet;
  9. typedef struct {
  10.     Triplet data[10];
  11.     int rows;
  12.     int cols;
  13.     int nums;
  14. }Table;

  16. void Create (Table *t,int *Matrix,int m,int n)
  17. {
  18.     int i,j;
  19.     /*
  20.     for (i=0;i<3;i++)
  21.     {
  22.     for (j=0;j<4;j++)
  23.             printf ("%d ",*(Matrix+i*n+j));
  24.         printf ("\n");
  25.     }
  26.     getch ();
  27.     */
  28.     t->rows=m;
  29.     t->cols=n;
  30.     t->nums=0;
  31.     for (i=0;i<m;i++)
  32.         for (j=0;j<n;j++)
  33.             if (*(Matrix+i*n+j)!=0)
  34.             {
  35.                 t->nums++;
  36.                 t->data[t->nums].row=i+1;
  37.                 t->data[t->nums].col=j+1;
  38.                 t->data[t->nums].e=*(Matrix+i*n+j);
  39.             }
  40. }
  41. void Trans (Table M,Table *T)
  42. {
  43.     int col,t,p,q;
  44.     int num[10];
  45.     int cpot[10];
  46.     T->rows=M.cols;
  47.     T->cols=M.rows;
  48.     T->nums=M.nums;
  49.     if (T->nums)
  50.     {
  51.         for (col=1;col<=M.cols;++col)
  52.             num[col]=0;
  53.         for (t=1;t<=M.nums;++t)
  54.             ++num[M.data[t].col];
  55.         cpot[1]=1;
  56.         for (col=2;col<=M.cols;++col)
  57.             cpot[col]=cpot[col-1]+num[col-1];
  58.         for (p=1;p<=M.nums;++p)
  59.         {
  60.             col=M.data[p].col;
  61.             q=cpot[col];
  62.             T->data[q].row=M.data[p].col;
  63.             T->data[q].col=M.data[p].row;
  64.             T->data[q].e=M.data[p].e;
  65.             ++cpot[col];
  66.         }
  67.     }

  69. }
  70. void MultSMatrix (Table M,Table N,Table *Q)
  71. {
  72.     int arow,brow,tp,p,q,t,ccol,row,i;
  73.     int ctemp[10];
  74.     int rpos[10];
  75.     int num[10];
  76.     int Mrpos[10];
  77.     int Nrpos[10];
  78.     if (M.cols!=N.rows)
  79.         exit (1);
  80.     Q->rows=M.rows;
  81.     Q->cols=N.cols;
  82.     Q->nums=0;
  83.     for (row=1;row<=M.rows;++row)
  84.          num[row]=0;
  85.     for (t=1;t<=M.nums;++t)
  86.         ++num[M.data[t].row];
  87.     Mrpos[1]=1;
  88.     for (row=2;row<=M.rows;++row)
  89.         Mrpos[row]=Mrpos[row-1]+num[row-1];
  90.     for (row=1;row<=N.rows;++row)
  91.          num[row]=0;
  92.     for (t=1;t<=N.nums;++t)
  93.         ++num[N.data[t].row];
  94.     Nrpos[1]=1;
  95.     for (row=2;row<=N.rows;++row)
  96.         Nrpos[row]=Nrpos[row-1]+num[row-1];
  97.     if (M.nums*N.nums!=0)
  98.     {
  99.         for (arow=1;arow<=M.rows;++arow)
  100.         {
  101.             for (i=0;i<10;i++)
  102.                 ctemp[i]=0;
  103.             rpos[arow]=Q->nums+1;
  104.             if (arow<M.rows)
  105.                 tp=Mrpos[arow+1];
  106.             else
  107.                 tp=M.nums+1;
  108.             for (p=Mrpos[arow];p<tp;++p)
  109.             {
  110.                 brow=M.data[p].col;
  111.                 if (brow<N.rows)
  112.                     t=Nrpos[brow+1];
  113.                 else
  114.                     t=N.nums+1;
  115.                 for (q=Nrpos[brow];q<t;++q)
  116.                 {
  117.                     ccol=N.data[q].col;
  118.                     ctemp[ccol]=ctemp[ccol]+M.data[p].e*N.data[q].e;
  119.                 }
  120.             }
  121.             for (ccol=1;ccol<=Q->cols;++ccol)
  122.                 if (ctemp[ccol])
  123.                 {
  124.                     Q->nums++;
  125.                     Q->data[Q->nums].row=arow;
  126.                     Q->data[Q->nums].col=ccol;
  127.                     Q->data[Q->nums].e=ctemp[ccol];
  128.                 }
  129.         }
  130.     }
  131. }

  133. void ToMatrix(Table t,int *Matrix,int m,int n)
  134. {
  135.     int i,j;
  136.     for (i=0;i<m;i++)
  137.         for (j=0;j<n;j++)
  138.             *(Matrix+i*n+j)=0;
  139.     for (i=1;i<=t.nums;i++)
  140.     {
  141.         *(Matrix+(t.data[i].row-1)*n+(t.data[i].col-1))=t.data[i].e;
  142.     }
  143. }
  144. int main ()
  145. {
  146.     int i,j;
  147.     Table A,B,AB;
  148.     int MatrixA[3][2] =
  149.         {{2,3},
  150.          {0,4},
  151.          {1,2}};
  152.     int MatrixB[2][3] =
  153.         {{2,5,1},
  154.          {0,2,4}};
  155.     int MatrixAB[3][3];
  156.     Create (&A,MatrixA,3,2);
  157.     Create (&B,MatrixB,2,3);
  158.     MultSMatrix (A,B,&AB);

  160.     ToMatrix (AB,MatrixAB,3,3);
  161.     for (i=0;i<3;i++)
  162.     {
  163.         for (j=0;j<3;j++)
  164.             printf ("%d ",MatrixAB[i][j]);
  165.         printf ("\n");
  166.     }
  167.     getchar ();
  168. }

阅读(142) | 评论(0) | 转发(0) |
0

上一篇：Notes of SICP

下一篇：python写的最简单的外挂

给主人留下些什么吧！~~
关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6