矩阵的实现
用C语言实现矩阵的加， 转置，求逆，乘，
矩阵的数据是二元的 0, 1，
怎么实现才使时间复杂度和空间复杂度，最小，
并且矩阵是稀疏矩阵，
求思路，
主要是矩阵的元素的存储
[解决办法]
哇，代数都有点忘记了，看来做这个题目还要去看书了
线形代数上都有讲怎么实现吧！
[解决办法]
在计算机上表示稀疏矩阵通常都是只存储非零元，常用的存储格式有（其中CCS最常用）
1. IJV:
row_index[nz]; // 非零元行下标
col_index[nz]; // 非零元列下标
value[nz]; // 非零元值
nz == 非零元数目
2. CCS (Compressed Column Storage):
colptr[n+1]; // 存的是每一列非零元在row_index数组开始的位置指标
row_index[nz]; // 非零元行下标
value[nz]; // 非零元值
所以第i列非零元行下标是
row_index[colptr[i]] ... row_index[colptr[i+1]-1]
非零元值是
value[colptr[i]] ... value[colptr[i]-1]
3. CRS (Compressed Row Storage):
和上面反过来，压缩行
你搜索一下，有很多稀疏矩阵的计算库的，说不一定可以找到直接拿来用
[解决办法]
转 :
存储稀疏矩阵时，往往只存放其中的非零元。稀疏矩阵的三元组表法是顺序存储方法的一种。采用这种方法时，线性表中的每个结点对应稀疏矩阵的一个非零元素，其中包括3个字段，分别为该元素的行下标、列下标和值，结点间的次序按矩阵的行优先顺序排列。另外，用第0行的三个元素分别存储矩阵的行数、列数和非零元数目。例如，矩阵A：
5 0 0 7
0 1 0 0
1 0 0 0 可以用三元组表示为： 3 4 4
1 1 5
1 4 7
2 2 1
3 1 1
在具体编程过程中，往往可以用一个简单的n*3二数组来表示此三元组。即稀疏矩阵A可以用数组a[5][3]={{3,4,4},{1,1,5},{1,4,7},{2,2,1},{3,1,1}} 来表示。
运算
1）矩阵转置（带回溯）
由于稀疏矩阵中的元素的存储是按行优先存储的，因此三元组中数据的行下标递增有序，行下标相同时列下标递增有序。存储转置后的矩阵，只要将三元组a的第一行依次将a中的列值由小到大进行选择，将选中的三元组元素行列值互换后放入三元组b，直到三元组a中的元素全部放入b中为止。
2）不带回溯的转置
不带回溯的转置要解决的关键问题是要预先确定好矩阵的每一列第一个非零元素在三元组b中应有的位置。为了确定这些位置，转置前必须求得三元组a中每一列非零元的个数，从而得到每列第一个元素在三元组b中（行）的位置。用pot数组来记录。
pot[1]=1；
pot[col]=pot[col-1]+第col-1列非零元的个数（pot[col]）
3）矩阵相加 C = A + B
稀疏矩阵相加采用的算法思想是：依次扫描 A和B的行号和列号，如果A的当前项的行号等于B的当前项的行号，则比较其列号，将较小的项存入C。若列号也相等，则将对应的元素相加后存入C；若A的当前项的行号小于B的，则将A的项存入C，否则将B的项存入C。
[注]：if a[i][0]= = b[i][0]&& a[i][1] < b[i][1] 表明该位置上B矩阵为零而A矩阵的元素不为零，相加后的C矩阵的该位置元素应为A矩阵的该元素，故将较小者存入C。
4）矩阵相乘 C = A * B
矩阵的乘法涉及到两矩阵不同行，列之间的运算，情况相对复杂。稀疏矩阵的乘法采用普通矩阵相乘的基本方法，关键是通过给顶的行号和列号找出原矩阵对应的元素值。这里设计一个函数value，当在三元组表示中找到时返回其元素值，找不到时，说明该位置为0，因此返回0。然后利用该函数计算出C的行号i和列号j 处的元素值，若该值不为0，则存入其三元组表示的矩阵 ，否则不存入。
完整的参考C程序如下:
#include <stdio.h>
#define max 20
convert(int a[max][3],int a1[max][3])
{int p,q,col;
a1[0][0]=a[0][1];
a1[0][1]=a[0][0];
a1[0][2]=a[0][2];
if(a1[0][2]!=0)
{q=1;
for(col=1;col <=a[0][1];col++)
for(p=1;p <=a[0][2];p++)
if(a[p][1]==col)
{a1[q][1]=a[p][0];
a1[q][0]=a[p][1];
a1[q][2]=a[p][2];
q++;
}
}
}
add(int a[max][3],int b[max][3],int c[max][3]) //error!!
{int i=1,j=1,k=1;
while(i <=a[0][2]&&j <=b[0][2])
{if(a[i][0]==b[j][0])
{if(a[i][1] <b[j][1])
{c[k][0]=a[i][0];
c[k][1]=a[i][1];
c[k][2]=a[i][2];
k++;
i++;
}
else if(a[i][1]> b[j][1])
{c[k][0]=b[j][0];
c[k][1]=b[j][1];
c[k][2]=b[j][2];
k++;
j++;
}
else
{c[k][0]=b[j][0];
c[k][1]=b[j][1];
c[k][2]=a[i][2]+b[j][2];
k++;
i++;
j++;
}
}
else if(a[i][0] <b[j][0])
{c[k][0]=a[i][0];
c[k][1]=a[i][1];
c[k][2]=a[i][2];
k++;
i++;
}
else
{c[k][0]=b[j][0];
c[k][1]=b[j][1];
c[k][2]=b[j][2];
k++;
j++;
}
c[0][0]=a[0][0];
c[0][1]=a[0][1];
c[0][2]=k-1;
}
}
int value(int c[max][3],int i,int j)
{int k=1;
while(k <=c[0][2]&&!(c[k][0]==i&&c[k][1]==j))
k++;
if(c[k][0]==i&&c[k][1]==j)
return(c[k][2]);
else return(0);
}
multi(int a[max][3],int b[max][3],int c[max][3])
{int i,j,p,s,q;
p=1;
for(i=1;i <=a[0][0];i++)
for(j=1;j <=b[0][1];j++)
{s=0;
for(q=1;q <=a[0][1];q++)
s=s+value(a,i,q)*value(b,q,j);
if(s!=0)
{c[p][0]=i;
c[p][1]=j;
c[p][2]=s;
p++;
}
}
c[0][0]=a[0][0];
c[0][1]=b[0][1];
c[0][2]=p-1;
}
print(int a[max][3])
{int i,j;
for(i=0;i <=a[0][2];i++)
{for(j=0;j <=2;j++)
printf( " %d ",a[i][j]);
printf( "\n ");
}
}
main()
{int a[max][3],b[max][3],a1[max][3],b1[max][3],c[max][3],d[max][3];
int i,y;
printf( "输入稀疏方阵A的行数，列数和非零元个数： ");
scanf( "%d,%d,%d ",&a[0][0],&a[0][1],&a[0][2]);
for(i=1;i <=a[0][2];i++)
{
printf( "输入第%d个非0元素的行数，列数和值: ",i);
scanf( "%d,%d,%d ",&a[i][0],&a[i][1],&a[i][2]);
}
printf( "输出A的三元组表示：\n ");
print(a);
printf( "\n输入稀疏方阵B的行数，列数和非零元个数： ");
scanf( "%d,%d,%d ",&b[0][0],&b[0][1],&b[0][2]);
for(i=1;i <=b[0][2];i++)
{
printf( "输入第%d个非0元素的行数，列数和值: ",i);
scanf( "%d,%d,%d ",&b[i][0],&b[i][1],&b[i][2]);
}
printf( "输出B的三元组表示：\n ");
print(b);
printf( "\n ");
printf( "============= 菜 单 ==============\n ");
printf( " 1 A矩阵转置\n ");
printf( " 2 B矩阵转置\n ");
printf( " 3 C = A + B\n ");
printf( " 4 D = A * B\n ");
printf( "======================================\n\n ");
loop: printf( "请选择相应操作的序号: ");
scanf( "%d ",&y);
switch(y)
{case 1: convert(a,a1);
printf( "输出A转置的三元组表示：\n ");
print(a1);
printf( "\n ");
goto loop;
case 2: convert(b,b1);
printf( "输出B转置的三元组表示：\n ");
print(b1);
printf( "\n ");
goto loop;
case 3: add(a,b,c);
printf( "输出C=A+B的三元组表示：\n ");
print(c);
printf( "\n ");
goto loop;
case 4: multi(a,b,d);
printf( "输出D=A*B的三元组表示：\n ");
print(d);
printf( "\n ");
goto loop;
}
}
[解决办法]
http://blog.csdn.net/jixingzhong/archive/2007/01/17/1486147.aspx
[解决办法]
基本运算还是比较简单的，
根据运算法则对应元素运算后保存到合适的索引位置即可。
