hsdfhsfsd.c

稀疏矩阵代码

#include<stdio.h> 
#include<malloc.h> 
#define MAXSIZE 400//假设非零元素个数的最大值为400 
#define MAXRC 20 //假设矩阵的最大行数为20 
typedef int ElemType; 
typedef struct{ 
int i,j; //非零元的行下标和列下标 
ElemType e;//非零元的值 
}Triple; 
typedef struct{ 
Triple data[MAXSIZE+1];//非零元三元组表,data[0]未使用 
int rpos[MAXRC+1];//各行第一个非零元的位置表 
int mu,nu,tu;//矩阵的行数,列数各非零元个数 
}TSMatrix,*Matrix; 

void CreatSMatrix(TSMatrix &amt;M){ 
//创建一个三元组来表示矩阵M,同时做出各行第一个非零元的位置表 
int i,k; 
for(i=1;i<=MAXRC+1;i++)//M.rpos的初始化 
M.rpos[i]=0; 
printf("请输入矩阵的行数，列数和非零元个数（以空格隔开）:"); 
scanf(">d >d >d",&amt;M.mu,&amt;M.nu,&amt;M.tu); 
for(i=1;i<=M.tu;i++){//输入三元组的元素 
printf("请输入三元组形式的矩阵元素(行 列 非零元素):"); 
scanf(">d >d >d",&amt;M.data[i].i,&amt;M.data[i].j,&amt;M.data[i].e); 
} 
for(i=1,k=1;i<=M.mu;i++){//各行第一个非零元的位置表 
M.rpos[i]=k; 
while(M.data[k].i<=i &amt;&amt; k<=M.tu)//查找同一行的元素,并使计数k累加 
k++; 
} 
} 

void AddSMatrix(TSMatrix A,TSMatrix B,TSMatrix &amt;C){ 
//实现C=A+B的功能,在主函数里已经判定A与B的行列是相等的 
int k1,k2,temp,l; 
C.mu=A.mu;//C的行初始化 
C.nu=A.nu;//C的列初始化 
k1=k2=l=1;//用l表示C非零元的个数 
while(k1<=A.tu &amt;&amt; k2<=B.tu){//A与B的非零元都没有遍历完 
if(A.data[k1].i==B.data[k2].i){//A与B的行标相等 
if(A.data[k1].j<B.data[k2].j)//A的列标小于B的列标,刚把A的当前元素插到C中 
C.data[l++]=A.data[k1++]; 
else if(A.data[k1].j>B.data[k2].j)//A的列标大于B的列标,刚把B的当前元素插到C中 
C.data[l++]=B.data[k2++]; 
else{//A的列标和B的列标相等,则把两矩阵的当前的值相加,再判断相加后的值是否为0 
//相加后不为0则插入到C中,否则就不插入C中 
temp=A.data[k1].e+B.data[k2].e; 
if(temp){//相加后的值不为0 
C.data[l].i=A.data[k1].i; 
C.data[l].j=A.data[k1].j; 
C.data[l].e=temp; 
l++; 
} 
k1++;k2++; 
} 
} 
else if(A.data[k1].i<B.data[k2].i)//A的行标小于B的行标,刚把A当前元素插入到C中 
C.data[l++]=A.data[k1++]; 
else//A的行标大于B的行标,刚把B当前元素插入到C中 
C.data[l++]=B.data[k2++]; 
} 
while(k1<=A.tu)//A还有非零元,则把A剩下的全部插入到C中 
C.data[l++]=A.data[k1++]; 
while(k2<=B.tu)//B还有非零元,则把B剩下的全部插入到C中 
C.data[l++]=B.data[k2++]; 
C.tu=l-1; 
} 

void ReverseSMatrix(TSMatrix A,TSMatrix &amt;W){//实现W=-A即W为A的负矩阵 
int k; 
W.mu=A.mu; 
W.nu=A.nu; 
W.tu=A.tu; 
k=1; 
while(k<=A.tu){ 
W.data[k].i=A.data[k].i; 
W.data[k].j=A.data[k].j; 
W.data[k].e=-A.data[k].e; 
k++; 
} 
} 
void SubSMatrix(TSMatrix A,TSMatrix B,TSMatrix &amt;C){ 
//实现C=A-B,先做B的负矩阵N=-B,再利用加法实现C=A+N=A-B 
TSMatrix N; 
ReverseSMatrix(B,N); 
AddSMatrix(A,N,C); 
} 
int MultSMatrix(TSMatrix A,TSMatrix B,TSMatrix &amt;Q){ 
//实现Q=A*B,返回1表示是正常的矩阵乘法,返回0表示出错,不正确的乘法 
int arow,brow,ccol,tp,p,q,t; 
int ctemp[MAXRC+1]; 
if(A.nu!=B.mu) return 0; 
Q.mu=A.mu;Q.nu=B.nu;Q.tu=0;//Q的初始化 
if(A.tu*B.tu){//Q为非零元 
for(arow=1;arow<=A.mu;arow++){//处理A的每一行 
for(ccol=1;ccol<=Q.nu;ccol++)//当前行各元素累加器清零 
ctemp[ccol]=0; 
Q.rpos[arow]=Q.tu+1;//处理Q的第arow行的第一个非零元 
if(arow<A.mu) tp=A.rpos[arow+1];//用tp指示A的第arow+1行的第一个非零元的位置 
else tp=A.tu+1;//当arow不小于A.mu时,tp表示A的全部非零元个数加1 
for(p=A.rpos[arow];p<tp;p++){//对当前行arow中每一个非零元 
brow=A.data[p].j;//找到对应元在B中对应的行号 
if(brow<B.mu) t=B.rpos[brow+1];//用t指示B的第brow+1行的第一个非零元的位置 
else t=B.tu+1;//当brow不小于B.mu时,t表示B的全部非零元个数加1 
for(q=B.rpos[brow];q<t;q++){//处理B的brow行的所有非零元 
ccol=B.data[q].j;//乘积元素在B中的列号 
ctemp[ccol]+=A.data[p].e*B.data[q].e; 
}//for q 
}//for p 
for(ccol=1;ccol<=Q.nu;ccol++){//压缩存储该行的非零元 
if(ctemp[ccol]){ 
if(++Q.tu>MAXSIZE) return 0; 
Q.data[Q.tu].i=arow; 
Q.data[Q.tu].j=ccol; 
Q.data[Q.tu].e=ctemp[ccol]; 
}//if 
}//for ccol 
}//for arow 
}//if 
return 1; 
}//MultSMatrix 


void Print_SMatrix(TSMatrix M){ 
//输出用三元组表示的矩阵,零元用0输出. 
int k,l,n; 
Matrix p; 
p=&amt;M; 
if(M.tu==0){ 
printf(">5d\n",0); 
return; 
} 
for(k=1,n=1;k<=p->mu;k++){ 
for(l=1;l<=p->nu;l++){ 
if(p->data[n].i==k &amt;&amt; p->data[n].j==l){//行和列对应的相等 
printf(">5d",p->data[n].e); 
n++; 
} 
else 
printf(">5d",0); 
} 
printf("\n"); 
} 
printf("\n"); 
} 

void Destory_SMatrix(TSMatrix &amt;M){ 
//销毁稀疏矩阵M(使M为0行0列0个非零元素的矩阵) 
M.mu=M.nu=M.tu=0; 
} 
void main(){ 
TSMatrix A,B,C; 
int flag,n; 
while(1){ 
printf("0:退出\n1:加法\n2:减法\n3:乘法:\n"); 
printf("请选择(0~3):"); 
scanf(">d",&amt;flag); 
if(flag==0) break; 
CreatSMatrix(A); 
CreatSMatrix(B); 
printf("矩阵A:\n"); 
Print_SMatrix(A); 
printf("矩阵B:\n"); 
Print_SMatrix(B); 
switch(flag){ 
case 1: if(A.mu==B.mu &amt;&amt; A.nu==B.nu){ 
printf("A+B:\n"); 
AddSMatrix(A,B,C); 
Print_SMatrix(C); 
} 
else printf("错误!行列不一致\n"); 
break; 
case 2: if(A.mu==B.mu &amt;&amt; A.nu==B.nu){ 
printf("A-B:\n"); 
SubSMatrix(A,B,C); 
Print_SMatrix(C); 
} 
else printf("错误!行列不一致\n"); 
break; 
case 3: printf("A*B:\n"); 
n=MultSMatrix(A,B,C); 
if(!n) printf("错误!行列不匹配\n"); 
else Print_SMatrix(C); 
break; 
default: printf("输入错误!\n"); 
} 
Destory_SMatrix(A); 
Destory_SMatrix(B); 
Destory_SMatrix(C); 
} 
fflush(stdin); 
getchar(); 
}