c语言稀疏矩阵
1. 稀疏矩阵的转置运算用c语言
#include<string.h>
#include<ctype.h>
#include<malloc.h> // malloc()等
#include<limits.h> // INT_MAX等
#include<stdio.h> // EOF(=^Z或F6),NULL
#include<stdlib.h> // atoi()
#include<io.h> // eof()
#include<math.h> // floor(),ceil(),abs()
#include<process.h> // exit()
#include<iostream.h> // cout,cin
// 函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
// #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此行
typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等
typedef int Boolean; // Boolean是布尔类型,其值是TRUE或FALSE
typedef int ElemType;
// c5-2.h 稀疏矩阵的三元组顺序表存储表示
#define MAXSIZE 100 // 非零元个数的最大值
struct Triple
{
int i,j; // 行下标,列下标
ElemType e; // 非零元素值
};
struct TSMatrix
{
Triple data[MAXSIZE+1]; // 非零元三元组表,data[0]未用
int mu,nu,tu; // 矩阵的行数、列数和非零元个数
};
// bo5-2.cpp 三元组稀疏矩阵的基本操作,包括算法5.1(9个)
Status CreateSMatrix(TSMatrix &M)
{ // 创建稀疏矩阵M
int i,m,n;
ElemType e;
Status k;
printf("请输入矩阵的行数,列数,非零元素数：");
scanf("%d,%d,%d",&M.mu,&M.nu,&M.tu);
M.data[0].i=0; // 为以下比较顺序做准备
for(i=1;i<=M.tu;i++)
{
do
{
printf("请按行序顺序输入第%d个非零元素所在的行(1～%d),列(1～%d),元素值：",i,M.mu,M.nu);
scanf("%d,%d,%d",&m,&n,&e);
k=0;
if(m<1||m>M.mu||n<1||n>M.nu) // 行或列超出范围
k=1;
if(m<M.data[i-1].i||m==M.data[i-1].i&&n<=M.data[i-1].j) // 行或列的顺序有错
k=1;
}while(k);
M.data[i].i=m;
M.data[i].j=n;
M.data[i].e=e;
}
return OK;
}
void DestroySMatrix(TSMatrix &M)
{ // 销毁稀疏矩阵M
M.mu=0;
M.nu=0;
M.tu=0;
}
void PrintSMatrix(TSMatrix M)
{ // 输出稀疏矩阵M
int i;
printf("%d行%d列%d个非零元素。\n",M.mu,M.nu,M.tu);
printf("行 列 元素值\n");
for(i=1;i<=M.tu;i++)
printf("%2d%4d%8d\n",M.data[i].i,M.data[i].j,M.data[i].e);
}
Status CopySMatrix(TSMatrix M,TSMatrix &T)
{ // 由稀疏矩阵M复制得到T
T=M;
return OK;
}
int comp(int c1,int c2) // 另加
{ // AddSMatrix函数要用到
int i;
if(c1<c2)
i=1;
else if(c1==c2)
i=0;
else
i=-1;
return i;
}
Status AddSMatrix(TSMatrix M,TSMatrix N,TSMatrix &Q)
{ // 求稀疏矩阵的和Q=M+N
Triple *Mp,*Me,*Np,*Ne,*Qh,*Qe;
if(M.mu!=N.mu)
return ERROR;
if(M.nu!=N.nu)
return ERROR;
Q.mu=M.mu;
Q.nu=M.nu;
Mp=&M.data[1]; // Mp的初值指向矩阵M的非零元素首地址
Np=&N.data[1]; // Np的初值指向矩阵N的非零元素首地址
Me=&M.data[M.tu]; // Me指向矩阵M的非零元素尾地址
Ne=&N.data[N.tu]; // Ne指向矩阵N的非零元素尾地址
Qh=Qe=Q.data; // Qh、Qe的初值指向矩阵Q的非零元素首地址的前一地址
while(Mp<=Me&&Np<=Ne)
{
Qe++;
switch(comp(Mp->i,Np->i))
{
case 1: *Qe=*Mp;
Mp++;
break;
case 0: switch(comp(Mp->j,Np->j)) // M、N矩阵当前非零元素的行相等,继续比较列
{
case 1: *Qe=*Mp;
Mp++;
break;
case 0: *Qe=*Mp;
Qe->e+=Np->e;
if(!Qe->e) // 元素值为0，不存入压缩矩阵
Qe--;
Mp++;
Np++;
break;
case -1: *Qe=*Np;
Np++;
}
break;
case -1: *Qe=*Np;
Np++;
}
}
if(Mp>Me) // 矩阵M的元素全部处理完毕
while(Np<=Ne)
{
Qe++;
*Qe=*Np;
Np++;
}
if(Np>Ne) // 矩阵N的元素全部处理完毕
while(Mp<=Me)
{
Qe++;
*Qe=*Mp;
Mp++;
}
Q.tu=Qe-Qh; // 矩阵Q的非零元素个数
return OK;
}
Status SubtSMatrix(TSMatrix M,TSMatrix N,TSMatrix &Q)
{ // 求稀疏矩阵的差Q=M-N
int i;
for(i=1;i<=N.tu;i++)
N.data[i].e*=-1;
AddSMatrix(M,N,Q);
return OK;
}
Status MultSMatrix(TSMatrix M,TSMatrix N,TSMatrix &Q)
{ // 求稀疏矩阵的乘积Q=M*N
int i,j,h=M.mu,l=N.nu,Qn=0;
// h,l分别为矩阵Q的行、列值,Qn为矩阵Q的非零元素个数，初值为0
ElemType *Qe;
if(M.nu!=N.mu)
return ERROR;
Q.mu=M.mu;
Q.nu=N.nu;
Qe=(ElemType *)malloc(h*l*sizeof(ElemType)); // Qe为矩阵Q的临时数组
// 矩阵Q的第i行j列的元素值存于*(Qe+(i-1)*l+j-1)中，初值为0
for(i=0;i<h*l;i++)
*(Qe+i)=0; // 赋初值0
for(i=1;i<=M.tu;i++) // 矩阵元素相乘，结果累加到Qe
for(j=1;j<=N.tu;j++)
if(M.data[i].j==N.data[j].i)
*(Qe+(M.data[i].i-1)*l+N.data[j].j-1)+=M.data[i].e*N.data[j].e;
for(i=1;i<=M.mu;i++)
for(j=1;j<=N.nu;j++)
if(*(Qe+(i-1)*l+j-1)!=0)
{
Qn++;
Q.data[Qn].e=*(Qe+(i-1)*l+j-1);
Q.data[Qn].i=i;
Q.data[Qn].j=j;
}
free(Qe);
Q.tu=Qn;
return OK;
}
Status TransposeSMatrix(TSMatrix M,TSMatrix &T)
{ // 求稀疏矩阵M的转置矩阵T。算法5.1
int p,q,col;
T.mu=M.nu;
T.nu=M.mu;
T.tu=M.tu;
if(T.tu)
{
q=1;
for(col=1;col<=M.nu;++col)
for(p=1;p<=M.tu;++p)
if(M.data[p].j==col)
{
T.data[q].i=M.data[p].j;
T.data[q].j=M.data[p].i;
T.data[q].e=M.data[p].e;
++q;
}
}
return OK;
}
Status FastTransposeSMatrix(TSMatrix M,TSMatrix &T)
{ // 快速求稀疏矩阵M的转置矩阵T。算法5.2
int p,q,t,col,*num,*cpot;
num=(int *)malloc((M.nu+1)*sizeof(int)); // 生成数组（[0]不用）
cpot=(int *)malloc((M.nu+1)*sizeof(int)); // 生成数组（[0]不用）
T.mu=M.nu;
T.nu=M.mu;
T.tu=M.tu;
if(T.tu)
{
for(col=1;col<=M.nu;++col)
num[col]=0; // 设初值
for(t=1;t<=M.tu;++t) // 求M中每一列含非零元素个数
++num[M.data[t].j];
cpot[1]=1;
for(col=2;col<=M.nu;++col) // 求第col列中第一个非零元在T.data中的序号
cpot[col]=cpot[col-1]+num[col-1];
for(p=1;p<=M.tu;++p)
{
col=M.data[p].j;
q=cpot[col];
T.data[q].i=M.data[p].j;
T.data[q].j=M.data[p].i;
T.data[q].e=M.data[p].e;
++cpot[col];
}
}
free(num);
free(cpot);
return OK;
}
void main()
{
TSMatrix A,B;
printf("创建矩阵A: ");
CreateSMatrix(A);
PrintSMatrix(A);
FastTransposeSMatrix(A,B);
printf("矩阵B(A的快速转置): ");
PrintSMatrix(B);
DestroySMatrix(A);
DestroySMatrix(B);
}
稀疏矩阵三元组转置，你参考下
2. 稀疏矩阵的转置，要求如下：（C语言编写代码）
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define maxsize 12500
int num[maxsize]={0},copt[maxsize]={0};
typedef struct
{
int i,j;
int e;
}Triple;
struct TSMatrix
{
Triple data[maxsize+1];
int mu,nu,tu;
}M,T;
int main()
{
int i=1,j,k,col;
scanf("%d%d%d",&M.mu,&M.nu,&M.tu);
copt[1]=1;
while(scanf("%d%d%d",&M.data[i].i,&M.data[i].j,&M.data[i].e)!=EOF)
{
num[M.data[i].j]++;
i++;
}
printf("num:%d,",num[1]);
for(col=2;col<=M.nu;col++)
{
copt[col]=copt[col-1]+num[col-1];
printf("%d,",num[col]);
}
printf("\n");
printf("cpot:");
for(i=1;i<=M.nu;i++)
printf("%d,",copt[i]);
printf("\n");
for(j=1;j<=M.tu;j++)
{
col=M.data[j].j;
k=copt[col];
T.data[k].i=M.data[j].j;
T.data[k].j=M.data[j].i;
T.data[k].e=M.data[j].e;
copt[col]++;
}
for(i=1;i<=M.tu;i++)
printf("%d,%d,%d\n",T.data[i].i,T.data[i].j,T.data[i].e);
return 0;
}
3. C语言课程设计：稀疏矩阵应用 要求：实现三元组，十字链表下的稀疏矩阵的加、转、乘的实现。
我刚写了一个稀疏矩阵的代码，如下
#include <iostream>
#include <iomanip>
using namespace std;
template<class T>
//三元组
struct Trituple
{
int row;
int col;
T val;
};
//稀疏矩阵声明
template<class T>
class SparseMatrix
{
public:
SparseMatrix(int maxt=100);
~SparseMatrix();
bool TransposeTo(SparseMatrix &);
bool AddTo(const SparseMatrix&);
bool TransposeTo_Faster(SparseMatrix&);
void Input();
void Output();
private:
Trituple<T>* data;
int rows,cols,terms;
int maxterms;
};
template<class T>
SparseMatrix<T>::SparseMatrix(int maxt)
{
maxterms=maxt;
data=new Trituple<T>[maxterms];
terms=rows=cols=0;
}
template<class T>
SparseMatrix<T>::~SparseMatrix()
{
if (data!=NULL)
{
delete[] data;
}
}
//普通转置
template<class T>
bool SparseMatrix<T>::TransposeTo(SparseMatrix &B)
{
if (terms>B.maxterms)
{
return false;
}
B.rows=cols;
B.cols=rows;
B.terms=terms;
if (terms>0)
{
int p=0;
for (int j=1;j<=cols;j++)
{
for (int k=0;k<terms;k++)
{
if (data[k].col==j)
{
B.data[p].row=j;
B.data[p].col=data[k].row;
B.data[p].val=data[k].val;
p++;
}
}
}
}
return true;
}
//快速转置
template<class T>
bool SparseMatrix<T>::TransposeTo_Faster(SparseMatrix& B)
{
if (terms>B.maxterms)
{
return false;
}
B.rows=cols;
B.cols=rows;
B.terms=terms;
if (terms>0)
{
int *num,*cpot;
num=new int[cols];
cpot=new int[cols];
for (int j=0;j<cols;j++)
{
num[j]=0;
}
for (int k=0;k<terms;k++)
{
num[data[k].col-1]++;
}
//求出B中每一行的起始下标cpot[]
cpot[0]=0;
for (int j=1;j<cols;j++)
{
cpot[j]=cpot[j-1]+num[j-1];
}
//执行转置操作
for (int p,k=0;k<terms;k++)
{
p=cpot[data[k].col-1]++;
B.data[p].row=data[k].col;
B.data[p].col=data[k].row;
B.data[p].val=data[k].val;
}
delete[] num;
delete[] cpot;
}
return true;
}
template<class T>
void SparseMatrix<T>::Input()
{
cout<<"intput the matrix' row:";
int row1;
cin>>row1;
cout<<"intput the matrix' col:";
int col1;
cin>>col1;
cout<<"input "<<row1<<"*"<<col1<<" matrix"<<endl;
int number;
rows=row1;
cols=col1;
for (int i=0;i<rows;i++)
{
for (int j=0;j<cols;j++)
{
cin>>number;
if (number!=0)
{
data[terms].row=i+1;
data[terms].col=j+1;
data[terms].val=number;
terms++;
}
}
}
}
template<class T> //输出好看，但是违背了最初的原则
void SparseMatrix<T>::Output()
{
T **tempArray=new T*[rows];
for (int i1=0;i1<rows;i1++)
{
tempArray[i1]=new int[cols];
}
for (int j=0;j<rows;j++)
{
for (int k=0;k<cols;k++)
{
tempArray[j][k]=0;
}
}
for (int i=0;i<terms;i++)
{
tempArray[data[i].row-1][data[i].col-1]=data[i].val;
}
for (int j=0;j<rows;j++)
{
for (int k=0;k<cols;k++)
{
cout<<setw(4)<<tempArray[j][k];
}
cout<<endl;
}
for (int l=0;l<rows;l++)
{
delete[] tempArray[l];
}
delete tempArray;
cout<<endl;
}
template<class T>
bool SparseMatrix<T>::AddTo(const SparseMatrix& B)
{
if (rows!=B.rows||cols!=B.cols)
{
return false;
}
bool flag=false;
int tempTerms=terms;
for (int i=0;i<B.terms;i++)
{
flag=false;
for (int j=0;j<tempTerms;j++)
{
if (data[j].col==B.data[i].col&&data[j].row==B.data[i].row)
{
data[j].val+=B.data[i].val;
flag=true;
}
}
if (flag==false)
{
data[++terms-1].col=B.data[i].col; //数组下标操作注意事项
data[terms-1].row=B.data[i].row;
data[terms-1].val=B.data[i].val;
}
}
return true;
}
int main()
{
cout<<"此程序演示稀疏矩阵的普通转置和快速转置操作"<<endl;
SparseMatrix<int> sm(50);
SparseMatrix<int> sm1(50);
SparseMatrix<int> sm2(50);
sm.Input();
cout<<"sm is"<<endl;
sm.Output();
sm.TransposeTo(sm1);
cout<<"Transposition of sm is "<<endl;
sm1.Output();
sm.TransposeTo_Faster(sm2);
cout<<"Transposition of sm is "<<endl;
sm2.Output();
SparseMatrix<int> sm3;
cout<<"input a new matrix"<<endl;
sm3.Input();
cout<<"sm3 is"<<endl;
sm3.Output();
if(sm.AddTo(sm3))
{
cout<<"after adding sm3 ,sm is"<<endl;
sm.Output();
}
else
cout<<"the two matrix can't add"<<endl;
cout<<"Good job!"<<endl;
system("pause");
return 0;
}
4. C语言编写稀疏矩阵的加，减，乘和转置，要求用矩阵输出
#include <stdio.h>
#include <iostream>
#include <math.h>
#include <stdlib.h>
using namespace std;
#define Max 12500
#define Elemtype int
typedef struct {
int i ,j ;
Elemtype e;
}Triple;
typedef struct {
Triple data[Max+1];
int mu,nu,tu;
}Tsmatrix;
int Createsmatrix(Tsmatrix &M)
{ int n;
cout<<"请输入稀疏矩阵的元素个数n"<<endl;
cin>>n;
M.tu=n;
cout<<"请输入稀疏矩阵的行数，列数："<<endl;
cin>>M.mu>>M.nu;
int i;
for(i=1;i<=n;i++){
cout<<"请输入稀疏矩阵的行下标和列下标，及数据;"<<endl;
cin>>M.data[i].i>>M.data[i].j>>M.data[i].e ;
}
return 1;
}
int Transpose(Tsmatrix M , Tsmatrix &T)
{
T.mu=M.nu; T.nu=M.mu ; T.tu=M.tu;
if(T.tu){
int col , p , q=1;
for(col=1; col<=M.nu;++col)
for(p=1;p<=M.tu;++p)
if (M.data[p].j==col){
T.data[q].i=M.data[p].j; T.data[q].j=M.data[p].i;
T.data[q].e=M.data[p].e ; ++q;}
}
return 1;
}
int Print(Tsmatrix M)
{
int i;int p=1;
{
for (i=1;i<=M.mu*M.nu;i++)
if(i==((M.data[p].i-1)*M.nu+M.data[p].j))
{
if(M.data[p].j==M.nu)
{ cout<<M.data[p].e<<endl; p++;}
else
{ cout<<M.data[p].e<<" "; p++;}
}
else if(i%M.nu==0) cout<<"0"<<endl;
else cout<<"0 ";
}
cout<<"\n"<<endl;
return 1;
}
int Addsmatrix(Tsmatrix a, Tsmatrix b, Tsmatrix &c)
{
int s=1,t=1,k=1; Elemtype temp;
if(a.mu!=b.mu||a.nu!=b.nu) return 0;
if(a.tu == 0) {c=b; return 1;}
if(b.tu==0) {c=a; return 1;}
if(a.tu==0 && b.tu==0) { c=a; return 1;}
while(!(s>a.tu && t>b.tu))
{
if(a.data[s].i>b.data[t].i)
{
c.data[k]=b.data[t];
k++ ;t++;
}
if(a.data[s].i<b.data[t].i)
{
c.data[k]=a.data[s];
k++ ;s++;
}
if(a.data[s].i==b.data[t].i)
{
if(a.data[s].j>b.data[t].j)
{
c.data[k]=b.data[t];
k++; t++;
}
if(a.data[s].j<b.data[t].j)
{
c.data[k]=a.data[s];
k++; s++;
}
if(a.data[s].j==b.data[t].j)
{
temp=a.data[s].e+b.data[t].e;
if(temp==0){s++;t++;}
else
{ c.data[k].e=temp;c.data[k].i=a.data[s].i;c.data[k].j=a.data[s].j;
s++;t++;k++;
}
}
}//if
if(s>a.tu&&t<=b.tu)
{
while(t<=b.tu)
{
c.data[k]=b.data[t];
k++; t++;
}
}
if(t>b.tu&&s<=a.tu)
{
while(s<=a.tu)
{
c.data[k]=a.data[s];
k++; s++;
}
}
}//while
c.tu=k-1; c.mu=a.mu; c.nu=a.nu;
}
return 1;int main()
{
Tsmatrix a,b,c;
Createsmatrix( a);
Createsmatrix( b);
Print(a);
Print(b);
Addsmatrix(a,b,c);
Print(c);
return 1;
}
5. c语言如何随机生成稀疏矩阵
在一个指定的n*m的矩阵arr中要生成一个含有k个非零元素的稀疏矩阵，可以通过下面的循环实现：
for(i=0;i<k;i++)
{a=rand()%n;
b=rand()%m;
arr[a][b]=rand()%9+1;
}
6. c语言稀疏矩阵的加法问题
#include <stdio.h>
#include <malloc.h>
#define MAX 100
struct matnode //十字链表结点的定义
{
int row,col;
struct matnode *right,*down;
union {
int val;//表结点使用V域
struct matnode *next;//表头结点使用next域
}tag;
};
struct matnode *createmat(struct matnode *hmone[MAX])
{
int m,n,t,s,i,r,c,v;
// struct matnode *l,*p,*q;
struct matnode *h[100],*l,*p,*q; //h[]是十字链表每行的表头指针数组
printf("行数m,列数n,非零元素个数t:");
//scanf("%d,%d,%d",&m,&n,&t); //输入行、列数，非零元素个数
scanf("%d,%d,%d",&m,&n,&t);//输入行、列数，非零元素个数
l=(struct matnode *)malloc(sizeof(struct matnode));
h[0]=l;//h[]是指针数组，分别指向头节点和行、列表头结点
l->row=m; //建立十字链表头结点*l
7. 用C语言实现稀疏矩阵的除法
一般人在使用MATLAB时
对于矩阵的左除与右除很难正确的!区别出须要使用那一个
因此借此机会说明一下
希望能更大家多多讨论
矩阵之除法是有其特别的定义
下面是例子：
假设A矩阵为方矩阵，且有反矩阵存在；b为配合之列向量或行向量，x为与b同大小之未知向量。
则以矩阵表示之联立方程式可以表示如下：
A*x=b
利用两矩阵”左除”即 ” \ ”之意义可以获得上式之解，即：
x = A\b
换言之，利用这样的左除指令，可以解联立方程式。
反之若方程式写成另一种型式：
x*A=b
则其解可以用右除表示：
x=b/A
利用左除法，若A 方矩阵，则其乘幂是使用高斯递减法解A*x=b 之矩阵方程式。
若A 不为方矩阵，则其乘幂是使用欧斯侯德之正交法，以最小平方之方式就不足或过多变数系统求解。右除法与左除法之关系实际上可表示如下：
b/A = (A'\b')'
8. 用C语言写； 一个稀疏矩阵
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 20
struct array
{
int r,c,v;
};
struct Tarray
{
array data[MAXSIZE];
int num;
int a[4][5];
}*p;
void creat_the_Tarray()//creat the array;
{
int i,j;
p=(Tarray*)malloc(sizeof(Tarray));//give the space the array;
p->num=0;//
printf(
9. 稀疏矩阵的构建 C语言
这个是稀疏矩阵相乘的算法吧
num[col]表示矩阵M中第col列中非零元个数
rpos[row]表示矩阵N中第row行中第一个非零元在B.data中的序号，那么rpos[row+1]-1就是矩阵B第row行中最后一个非零元在B.data的序号，而最后一行中最后一个非零元在B.data中的位置显然就是B.tu了
这个比较绕 好好想想就理解了