高效矩阵运算：稀疏矩阵处理方法详解

大家好，今天来为大家分享高效矩阵运算：稀疏矩阵处理方法详解的一些知识点，和的问题解析，大家要是都明白，那么可以忽略，如果不太清楚的话可以看看本篇文章，相信很大概率可以解决您的问题，接下来我们就一起来看看吧！

left[ begin{matrix} 4-3001 \ 00080 \ 00100 \ 00000 end{matrix}right] times left[ begin{matrix} 300 \ 420 \ 010 \ 100 \ 000 end{矩阵}right]=left[ begin{矩阵} 0-60 \ 800 \ 010 \ 000 end{矩阵}right]

二、概要设计

1.数据结构

ADT 稀疏矩阵{

数据对象：D={ aij|我=1,2,m; j=1,2,n；

aijElemSet，m和n分别是矩阵的行数和列数}

数据关系：R={行，列}

row={i,j，ai,j+1|1im，1jn-1}

Col={i,j，ai+1,j|1im-1，1jn}

基本操作：CreateSMatrix(M)运算结果：创建稀疏矩阵M。

PrintSMatrix(M)初始条件：稀疏矩阵M存在。

运算结果：输出稀疏矩阵M。

AddSMatrix(M, N, Q)初始条件：稀疏矩阵M和N的行数和列数相等。

运算结果：求稀疏矩阵Q=M+N之和。

SubtSMatrix(M, N, Q)初始条件：稀疏矩阵M和N的行数和列数相等。

运算结果：求稀疏矩阵Q=M-N的差。

MultSMatrix(M, N, Q)初始条件：稀疏矩阵M的列数等于N的行数。

运算结果：求稀疏矩阵乘积Q=M*N。

}ADT 稀疏矩阵

2. 使用函数

（1）行逻辑链接的顺序表

int CreateSMatrix(RLSMatrix *M)

运算结果：创建稀疏矩阵

int PrintSMatrix(RLSMatrix M)

运算结果：打印稀疏矩阵

int AddSMatrix(RLSMatrix M, RLSMatrix N, RLSMatrix *Q)

运算结果：稀疏矩阵相加，Q=M+N

int SubSMatrix(RLSMatrix M, RLSMatrix N, RLSMatrix *Q)

运算结果：稀疏矩阵减法，Q=M-N

int MultSMatrix(RLSMatrix M, RLSMatrix N, RLSMatrix *Q)

运算结果：稀疏矩阵乘法，Q=M*N

（2）十字链表

int CreateSMatrix_OL(CrossList *M)

运算结果：创建稀疏矩阵

int PrintSMatrix_OL(CrossList M)

运算结果：打印稀疏矩阵

int AddSMatrix_OL(CrossList *A, CrossList *B)

运算结果：稀疏矩阵B与稀疏矩阵A相加

int SubSMatrix_OL(CrossList *A, CrossList *B)

运算结果：稀疏矩阵A减去稀疏矩阵B

int MultSMatrix_OL(CrossList A, CrossList B, CrossList *C)

运算结果：稀疏矩阵乘法，C=A*B

三、详细设计

1. 数据储存结构

（1）行逻辑链接顺序表

#define MAXSIZE 400 //非零元素的最大数量

#define MAXRC 20 //最大行数和列数

类型定义结构{

整数i,j; //非零元素的行、列下标

整数e；

}三倍；

类型定义结构{

三倍数据[MAXSIZE+1]； //非零三元组表

int rpos[MAXRC+1]; //每行第一个非零元素位置表

int mu,nu,tu； //矩阵的行数、列数和非零元素数

}RLS矩阵；

（2）十字链表

#define MAXSIZE 400 //非零元素的最大数量

#define MAXRC 20 //最大行数和列数

typedef 结构OLNode{

整数i,j; //非零元素的行索引和列索引

整数e；

结构OLNode *右，*下； //非零元素所在列表的行表和后继链字段

}OLNode，*OLink；

类型定义结构{

OLink *rhead, *chead; //行列链表头指针向量的基地址由CreateSMatrix分配

int mu、nu、tu； //稀疏矩阵的行数、列数和非零元素数

}交叉列表；

2.基本功能实现

2.1行逻辑链接顺序表

（1）稀疏矩阵创建

分别读取矩阵的行数、列数和非零元素个数，并提示输入每个非零元素的位置和值。判断输入的非零元素是否合法，并根据行号和列号以行优先顺序存储，最后计算出每行的第一个非零元素位置。

int CreateSMatrix(RLSMatrix *M){

如果（M）自由（M）；

int m,n,t；

做{

printf("输入矩阵的行数、列数和非零元素数，以空格分隔n");

scanf("%d %d %d", m, n, t);

if(m 0 || n 0 || t 0 || t m*n){

printf("参数错误n");

}

} while(m 0 || n 0 || t 0 || t m*n);

M-mu=m； M-nu=n; M-tu=t；

printf("请按行优先级输入三元组n");

整数i,j,e,k;

整数p，q；

for(k=1; k=t; k++){

做{

printf("输入第%d个非零行号、列号、值，以空格分隔n",k);

scanf("%d %d %d", i, j, e);

if(i=0 || j=0 || i m || j n|| e==0){

printf("参数错误n");

}

} while(i=0 || j=0 || i m || j n|| e==0);

for(p=1; p=k-1 (i M-data[p].i || (i==M-data[p].i j M-data[p].j)); p++); //找到三元组插入的位置

for(q=k-1;q=p; q--) M-data[q+1]=M-data[q]; //行序大的三元组按顺序向后移动

M-data[p].i=i;

M-data[p].j=j;

M-data[p].e=e;

}

整数行，x；

int num[MAXRC + 1];

for（行=1；行=M-mu；++行）num[行]=0；

for(x=1; x=M-tu; ++x) ++num[M-data[x].i]; //每行非零元素个数

M-rpos[1]=1；

for(row=2; row=M-mu; ++row) M-rpos[row]=M-rpos[row-1] + num[row-1]; //每行第一个非零元素位置

返回1；

}

（2）稀疏矩阵加减法

加法和减法的基本思想是相同的。这里我们以加法为例。找到M、N矩阵各行非零元素的起始和结束位置后，开始遍历，分别处理列数相等和不等两种情况，并处理相加结果等于0的情况。

int AddSMatrix(RLSMatrix M, RLSMatrix N, RLSMatrix *Q){

整数箭头；

int p,q,s=1;

int tp，tq；

if(M.mu !=N.mu || M.nu !=N.nu) 返回0;

Q-mu=M.mu； Q-nu=M.nu;

for(arow=1;arow=M.mu;++arow){

Q-rpos[arow]=Q-tu + 1;

p=M.rpos[arow]; q=N.rpos[arow];

if(arow M.mu){

tp=M.rpos[arow + 1];

tq=N.rpos[arow + 1];

}

别的{

tp=M.tu + 1；

tq=N.tu + 1;

}

而（p tp q tq）{

if(M.data[p].j !=N.data[q].j){ //列数不相等

if(M.data[p].j N.data[q].j){

Q-data[s].i=arow;

Q-data[s].j=M.data[p].j;

Q-data[s].e=M.data[p].e;

s++； p++； Q-tu++；

}别的{

Q-data[s].i=arow;

Q-data[s].j=N.data[q].j;

Q-data[s].e=N.data[q].e;

s++； q++； Q-tu++；

}

}else{ //列数相等

if(M.data[p].e + N.data[q].e !=0){ //结果非零

Q-data[s].i=arow;

Q-data[s].j=M.data[p].j;

Q-data[s].e=M.data[p].e + N.data[q].e;

s++； q++； p++； Q-tu++；

}否则{q++; p++;}

}

而（p tp）{

Q-data[s].i=arow;

Q-data[s].j=M.data[p].j;

Q-data[s].e=M.data[p].e;

p++； s++； Q-tu++；

}

而（qtq）{

Q-data[s].i=arow;

Q-data[s].j=N.data[q].j;

Q-data[s].e=N.data[q].e;

q++； s++； Q-tu++；

}

返回1；

}

（3）稀疏矩阵乘法

对于M中的每个元素M.data[p]，找到N中满足条件M.data[p].j=N.data[q].i的所有元素N.data[q]，并且得到M.data[p].e * N.data[q].e，为Q中的元素设计一个累加和变量，初始值为0，扫描数组M，求对应元素的乘积并将它们添加到适当的累积和变量中。 Q中元素的行号与M中元素的行号一致，且M中元素的行序为主序。因此，对Q进行逐行处理，首先得到累加和的中间结果（Q的一行），然后将其压缩存储在Q.data中。

int MultSMatrix(RLSMatrix M, RLSMatrix N, RLSMatrix *Q){

//求矩阵乘积Q=MN，采用行逻辑链接存储表示

int arow，眉毛；

int p,q,t,tp;

int ccol;

int ctemp[MAXRC + 1];

if(M.nu !=N.mu) 返回0;

Q-mu=M.mu； Q-nu=N.nu; Q-tu=0; //Q 初始化

if(M.tu * N.tu !=0){ //Q 是非零矩阵

for(arow=1; arow=M.mu; ++arow){ //处理M的每一行

for(int i=1; i=N.nu; i++) ctemp[i]=0; //清空当前行每个元素的累加器。

Q-rpos[arow]=Q-tu + 1;

if(arow M.mu) tp=M.rpos[arow + 1];

否则{tp=M.tu + 1;}

for(p=M.rpos[arow]; pnu; ++ccol){ //压缩并存储非零元素

如果（ctemp [ccol]）{

if(++Q-tu MAXSIZE) 返回0;

Q-data[Q-tu].i=arow;

Q-data[Q-tu].j=ccol;

Q-data[Q-tu].e=ctemp[ccol];

}//如果

} //对于ccol

}//对于箭头

}//如果

返回1；

}//MultSMatrix

（4）稀疏矩阵输出

通过双循环打印稀疏矩阵中的非零元素和零元素

int PrintSMatrix(RLSMatrix M){

int 行，列，t=1;

for(行=1;行=M.mu;行++){

for(col=1; col=M.nu; col++){

if(M.data[t].i==行M.data[t].j==col){

printf("%dt",M.data[t].e);

t++；

}别的{

printf("0t");

}

printf("n");

}

返回1；

}

2.2十字链表

（1）稀疏矩阵创建

读入矩阵的行数、列数和非零元素数，并提示输入每个非零元素的位置和值。判断输入的非零元素是否合法，生成节点并完成行链表和列链表的插入。

int CreateSMatrix_OL(CrossList *M){

如果（M）自由（M）；

整数c;

int m,n,t；

整数i,j,k,e;

OLink p,q;

做{

printf("输入矩阵的行数、列数和非零元素数，以空格分隔n");

scanf("%d %d %d", m, n, t);

if(m 0 || n 0 || t 0 || t m*n){

printf("参数错误n");

}

} while(m 0 || n 0 || t 0 || t m*n);

M-mu=m； M-nu=n; M-tu=t；

if(!(M-rhead=(OLink*)malloc((m+1)*sizeof(OLink)))) 退出(-2);

if(!(M-chead=(OLink*)malloc((n+1)*sizeof(OLink)))) 退出(-2);

for(c=1; c=M-mu; c++) M-rhead[c]=NULL; //初始化列头指针向量

for(c=1; c=M-nu; c++) M-chead[c]=NULL;

for(k=1; k=t; k++){ //以任意顺序输入非零元素

做{

printf("输入第%d个非零行号、列号、值，以空格分隔n",k);

scanf("%d %d %d", i, j, e);

if(i=0 || j=0 || i m || j n|| e==0){

printf("参数错误n");

}

} while(i=0 || j=0 || i m || j n|| e==0);

if(!(p=(OLNode*)malloc(sizeof(OLNode)))) 退出(-2);

p-i=i； p-j=j； p -e=e; //生成节点

if(M-rhead[i]==NULL || M-rhead[i]-j j){

p-右=M-rhead[i];

M-rhead[i]=p；

}else{ //查找行表中的插入位置

for(q=M-rhead[i]; (q-right) (q-right-j j); q=q-right);

p-右=q-右；

q-右=p;

} //完成行插入

if(M-chead[j]==NULL || M-chead[j]-i i){ //查找列表中的插入位置

p-down=M-chead[j];

M-头[j]=p;

}别的{

for(q=M-chead[j]; (q-down) (q-down-i i); q=q-down);

p-向下=q-向下；

q-向下=p;

} //完成列插入

}

返回1；

}

（2）稀疏矩阵加减法

加法和减法的基本思想是相同的。这里我们以加法为例。

非空指针pa和pb分别指向矩阵A和B中具有相同行值的两个节点。 pa==NULL表示矩阵A在换行时没有非零元素，可分为以下四种情况：

如果pa==NULL或者pa-jpb-i，则需要在A矩阵的链表中插入一个值为bij的节点。这时候就需要改变同一行上一个节点的right字段值，以及同一列的right字段值。前一个节点的下域值。如果pa-jj，则将pa 指针进一步向右推。如果pa-j==pb-j，并且pa-e+pb-e!=0，则将aij+bij的值发送到pa指向的节点。此时，需要更改同一行上一个节点的右域值和同一列上一个节点的向下阈值。

为了方便节点的插入和删除，还需要设置一些辅助指针。首先是在A的行链表上设置pre指针，指示pa所指向的节点的前驱节点；二是设置A的每一列的链表

上设一个指针hl[j]，其初值和列链表的头指针相同，即hl[j]=chead[j]int AddSMatrix_OL(CrossList *A, CrossList *B){ OLink pa, pb, pre, p, hl[MAXRC + 1]; int i, j; if(A->mu != B->mu || A->nu != B->nu) return 0; for(j = 1; j<= A->nu; j++) hl[j] = A->chead[j]; for(i = 1; i<= A->mu; i++){ pa = A->rhead[i]; pb = B->rhead[i]; pre = NULL; while(pb){ if(!(p = (OLNode*)malloc(sizeof(OLNode)))) exit(-2); p->i = pb->i; p->j = pb->j; p->e = pb->e; if(pa == NULL || pa->j >pb->j){ // 在A中插入pb所指结点的复制结点p if(pre == NULL) A->rhead[p->i] = p; else{pre->right = p; } p->right = pa; pre = p; if(A->chead[p->j] == NULL || A->chead[p->j]->i >p->i){ p->down = A->chead[p->j]; A->chead[p->j] = p; }else{ // 在hl[p->j]中找到新结点的前驱，插入结点 p->down = hl[p->j]->down; hl[p->j]->down = p; } hl[p->j] = p; pb = pb->right; A->tu++; }else if(pa && pa->j< pb->j){ // pa指向本行下一个非零结点 pre = pa; pa = pa->right; }else if(pa->j == pb->j){ // 加和 pa->e += pb->e; if(pa->e == 0){ // 加和为0，删除结点，修改行表和列表相应指针 if(pre == NULL) A->rhead[pa->i] = pa->right; else{pre->right = pa->right; } p = pa; pa = pa->right; if(A->chead[p->j] == p) A->chead[p->j] = hl[p->j] = p->down; else{hl[p->j]->down = p->down; } free(p); pb = pb->right; A->tu--; }else{pre = pa; pa = pa->right; pb = pb->right; } } } } return 1; }

（3）稀疏矩阵乘法

对于C中i行j列的元素，分别使p指向A中i行链表头指针，q指向B中j列链表头指针，累加和e置为零。p，q不为空时，当p->j >q->i，q指针下移当p->j< q->i，p指针右移当p->j == q->i，对乘积累计求和，并移动指针累加器e不为0时，则在矩阵C行列链表中插入节点p1，设置cpre和rpre分别指示行列链表中p1的前驱结点。int MultSMatrix_OL(CrossList A, CrossList B, CrossList *C){ int i, j, e; OLink p, q, p1, rpre, cpre; if(A.nu != B.mu) return 0; C->mu = A.mu; C->nu = B.nu; C->tu = 0; // 初始化矩阵C if(!(C->rhead = (OLink*)malloc((C->mu+1)*sizeof(OLink)))) exit(-2); if(!(C->chead = (OLink*)malloc((C->nu+1)*sizeof(OLink)))) exit(-2); for(i = 1; i<= C->mu; i++) C->rhead[i] = NULL; for(j = 1; j<= C->nu; j++) C->chead[j] = NULL; for(i = 1; i<= C->mu; i++){ for(j = 1; j<= C->nu; j++){ p = A.rhead[i]; q = B.chead[j]; e = 0; // p,q分别指向A中该行链表头指针，B中该列链表头指针 while(p && q){ if(p->j >q->i){ q = q->down; }else if(p->j< q->i){ p = p->right; }else{ e += p->e * q->e; // 乘积累加 q = q->down; p = p->right; } } if(e){ // 累加不为0 C->tu++; if(!(p1 = (OLNode*)malloc(sizeof(OLNode)))) exit(-2); p1->i = i; p1->j = j; p1->e = e; p1->right = NULL; p1->down = NULL; // 行插入 if(C->rhead[i] == NULL) {C->rhead[i] = p1; rpre = p1;} else{rpre->right = p1; rpre = p1; } // 列插入 if(C->chead[j] == NULL) {C->chead[j] = p1; cpre = p1;} else{cpre->down = p1; cpre = p1; } } } } return 1; }

（4）稀疏矩阵输出

通过双重循环，打印稀疏矩阵中非零元和零元素 int PrintSMatrix_OL(CrossList M){ OLink p; int row,col; for(row = 1; row<= M.mu; row++){ if(M.rhead[row]){ p = M.rhead[row]; for(col = 1; col<= M.nu; col++){ if(p->i == row && p->j == col && p != NULL){ printf("%dt",p->e); if(p->right) p = p->right; }else{printf("0t");} } }else{for(col = 1; col<= M.nu; col++) printf("0t");} printf("n"); } return 1; }

4.主程序

通过读入操作序号来进行相应操作，在满足操作对应条件下进行相应操作，并打印结果，两种储存方式下主程序结构基本一致，只是运算时调用函数不同。 int main(){ int num; CrossList M, N, Q; do{ printf("操作：1.矩阵相加 2.矩阵相减 3.矩阵相乘 4.退出n"); scanf("%d",&num); if(num == 1 || num == 2 || num == 3){ printf("请输入矩阵1n"); CreateSMatrix_OL(&M); printf("请输入矩阵2n"); CreateSMatrix_OL(&N); printf("两矩阵为：n"); PrintSMatrix_OL(M); printf("n"); PrintSMatrix_OL(N); switch(num){ case 1: { if(AddSMatrix_OL(&M, &N)){ printf("结果:n"); PrintSMatrix_OL(M); } else {printf("参数错误n");} break; } case 2: { if(SubSMatrix_OL(&M, &N)){ printf("结果:n"); PrintSMatrix_OL(M); } else {printf("参数错误n");} break; } case 3: { if(MultSMatrix_OL(M,N,&Q)){ printf("结果：n"); PrintSMatrix_OL(Q); } else {printf("参数错误n");} break; } default: break; } } }while(num == 1 || num == 2 || num == 3); return 1; }

5.程序的层次结构

层次结构

四、用户手册

本程序的运行环境为DOS操作系统，执行文件为：sparsematrix.exe和crossmatrix.exe 分别对应行逻辑链接顺序表和十字链表实现的稀疏矩阵计算器进入程序按提示操作，输入要进行操作对应的序号根据操作提示输入两矩阵的行数、列数和非零元个数，并输入非零元的行号，列号以及值结果打印根据操作提示退出程序

五、测试结果

left[ begin{matrix} 10&0& 0 \ 0&0&9 \ -1&0&0 \ end{matrix}right] + left[ begin{matrix} 0&0& 0 \ 0&0&-1 \ 1&0&-3 \ end{matrix}right]= left[ begin{matrix} 10&0& 0 \ 0&0&8 \ 0&0&-3 \ end{matrix}right] left[ begin{matrix} 10&9 \ 0&9 \ -1&0 \ end{matrix}right] - left[ begin{matrix} 0&0 \ 0&-1 \ 1&-3 \ end{matrix}right]= left[ begin{matrix} 10&0 \ 0&10 \ -2&-3 \ end{matrix}right] left[ begin{matrix} 4&-3&0&0&1 \ 0&0&0&8&0 \ 0&0&1&0&0 \ 0&0&0&0&0 end{matrix}right] times left[ begin{matrix} 3&0&0 \ 4&2&0 \ 0&1&0 \ 1&0&0 \ 0&0&0 end{matrix}right] = left[ begin{matrix} 0&-6&0 \ 8&0&0 \ 0&1&0 \ 0&0&0 end{matrix}right] 测试结果1测试结果2测试结果3

六、源代码

sparsematrix.c #include#include#define MAXSIZE 400 #define MAXRC 20 typedef struct{ int i,j; int e; }Triple; typedef struct{ Triple data[MAXSIZE+1]; int rpos[MAXRC+1]; int mu,nu,tu; // 行，列，非零元个数 }RLSMatrix; int CreateSMatrix(RLSMatrix *M){ if(M) free(M); int m,n,t; do{ printf("输入矩阵行数，列数和非零元数目，用空格隔开n"); scanf("%d %d %d", &m, &n, &t); if(m< 0 || n< 0 || t< 0 || t >m*n){ printf("参数错误 n"); } }while(m< 0 || n< 0 || t< 0 || t >m*n); M->mu = m; M->nu = n; M->tu = t; printf("请按行优先输入三元组n"); int i,j,e,k; int p,q; for(k = 1; k<= t; k++){ do{ printf("输入第%d个非零元的行号列号值, 用空格隔开n",k); scanf("%d %d %d", &i, &j, &e); if(i<= 0 || j<= 0 || i >m || j >n|| e==0){ printf("参数错误n"); } }while(i<= 0 || j<= 0 || i >m || j >n|| e==0); for(p = 1; p<= k-1 && (i >M->data[p].i || (i == M->data[p].i && j >M->data[p].j)); p++); //找到此三元组插入的位置 for(q = k-1;q >= p; q--) M->data[q+1] = M->data[q]; //行序比它大的三元组依次向后移动 M->data[p].i = i; M->data[p].j = j; M->data[p].e = e; } int row,x; int num[MAXRC + 1]; for(row = 1; row<= M->mu; ++row) num[row] = 0; for(x = 1; x<= M->tu; ++x) ++num[M->data[x].i]; M->rpos[1] = 1; for(row = 2; row<=M->mu; ++row) M->rpos[row] = M->rpos[row-1] + num[row-1]; return 1; } int PrintSMatrix(RLSMatrix M){ int row,col,t = 1; for(row = 1; row<= M.mu; row++){

for(col = 1; col<= M.nu; col++){ if(M.data[t].i == row && M.data[t].j == col){ printf("%dt",M.data[t].e); t++; }else{ printf("0t"); } } printf("n"); } return 1; } int AddSMatrix(RLSMatrix M, RLSMatrix N, RLSMatrix *Q){ int arow; int p,q,s = 1; int tp,tq; if(M.mu != N.mu || M.nu != N.nu) return 0; Q->mu = M.mu; Q->nu = M.nu; for(arow = 1; arow<= M.mu; ++arow){ Q->rpos[arow] = Q->tu + 1; p = M.rpos[arow]; q = N.rpos[arow]; if(arow< M.mu){ tp = M.rpos[arow + 1]; tq = N.rpos[arow + 1]; } else{ tp = M.tu + 1; tq = N.tu + 1; } while(p< tp && q< tq){ if(M.data[p].j != N.data[q].j){ // 列号不等 if(M.data[p].j< N.data[q].j){ Q->data[s].i = arow; Q->data[s].j = M.data[p].j; Q->data[s].e = M.data[p].e; s++; p++; Q->tu++; }else{ Q->data[s].i = arow; Q->data[s].j = N.data[q].j; Q->data[s].e = N.data[q].e; s++; q++; Q->tu++; } }else{ // 列号相等 if(M.data[p].e + N.data[q].e != 0){ // 结果非零 Q->data[s].i = arow; Q->data[s].j = M.data[p].j; Q->data[s].e = M.data[p].e + N.data[q].e; s++; q++; p++; Q->tu++; }else{q++; p++;} } } while(p< tp){ Q->data[s].i = arow; Q->data[s].j = M.data[p].j; Q->data[s].e = M.data[p].e; p++; s++; Q->tu++; } while(q< tq){ Q->data[s].i = arow; Q->data[s].j = N.data[q].j; Q->data[s].e = N.data[q].e; q++; s++; Q->tu++; } } return 1; } int SubSMatrix(RLSMatrix M, RLSMatrix N, RLSMatrix *Q){ int arow; int p,q,s = 1; int tp,tq; if(M.mu != N.mu || M.nu != N.nu) return 0; Q->mu = M.mu; Q->nu = M.nu; for(arow = 1; arow<= M.mu; ++arow){ Q->rpos[arow] = Q->tu + 1; p = M.rpos[arow]; q = N.rpos[arow]; if(arow< M.mu){ tp = M.rpos[arow + 1]; tq = N.rpos[arow + 1]; } else{ tp = M.tu + 1; tq = N.tu + 1; } while(p< tp && q< tq){ if(M.data[p].j != N.data[q].j){ // 列号不等 if(M.data[p].j< N.data[q].j){ Q->data[s].i = arow; Q->data[s].j = M.data[p].j; Q->data[s].e = M.data[p].e; s++; p++; Q->tu++; }else{ Q->data[s].i = arow; Q->data[s].j = N.data[q].j; Q->data[s].e = - N.data[q].e; s++; q++; Q->tu++; } }else{ // 列号相等 if(M.data[p].e - N.data[q].e != 0){ Q->data[s].i = arow; Q->data[s].j = M.data[p].j; Q->data[s].e = M.data[p].e - N.data[q].e; s++; q++; p++; Q->tu++; }else{q++; p++;} } } while(p< tp){ Q->data[s].i = arow; Q->data[s].j = M.data[p].j; Q->data[s].e = M.data[p].e; p++; s++; Q->tu++; } while(q< tq){ Q->data[s].i = arow; Q->data[s].j = N.data[q].j; Q->data[s].e = - N.data[q].e; q++; s++; Q->tu++; } } return 1; } int MultSMatrix(RLSMatrix M, RLSMatrix N, RLSMatrix *Q){ // 求矩阵乘积Q=M×N，采用行逻辑链接储存表示 int arow,brow; int p,q,t,tp; int ccol; int ctemp[MAXRC + 1]; if(M.nu != N.mu) return 0; Q->mu = M.mu; Q->nu = N.nu; Q->tu = 0; // Q初始化 if(M.tu * N.tu != 0){ // Q是非零矩阵 for(arow = 1; arow<= M.mu; ++arow){ // 处理M的每一行 for(int i = 1; i<= N.nu; i++) ctemp[i] = 0; // 当前行各元素累加器清零 Q->rpos[arow] = Q->tu + 1; if(arow< M.mu) tp = M.rpos[arow + 1]; else{tp = M.tu + 1;} for(p = M.rpos[arow]; pnu; ++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 int main(){ int num; RLSMatrix M, N, Q; do{ printf("操作：1.矩阵相加 2.矩阵相减 3.矩阵相乘 4.退出n"); scanf("%d",&num); if(num == 1 || num == 2 || num == 3){ printf("请输入矩阵1n"); CreateSMatrix(&M); printf("请输入矩阵2n"); CreateSMatrix(&N); printf("两矩阵为：n"); PrintSMatrix(M); printf("n"); PrintSMatrix(N); switch(num){ case 1: { if(AddSMatrix(M,N,&Q)){ printf("结果:n"); PrintSMatrix(Q); } else {printf("参数错误n");} break; } case 2: { if(SubSMatrix(M,N,&Q)){ printf("结果:n"); PrintSMatrix(Q); } else {printf("参数错误n");} break; } case 3: { if(MultSMatrix(M,N,&Q)){ printf("结果：n"); PrintSMatrix(Q); } else {printf("参数错误n");} break; } default: break; } } }while(num == 1 || num == 2 || num == 3); return 1; }

crosmatrix.c

#include#include#define MAXSIZE 400 #define MAXRC 20 typedef struct OLNode{ int i,j; int e; struct OLNode *right, *down; }OLNode, *OLink; typedef struct { OLink *rhead, *chead; int mu, nu, tu; }CrossList; int CreateSMatrix_OL(CrossList *M){ if(M) free(M); int c; int m,n,t; int i,j,k,e; OLink p,q; do{ printf("输入矩阵行数，列数和非零元数目，用空格隔开n"); scanf("%d %d %d", &m, &n, &t); if(m< 0 || n< 0 || t< 0 || t >m*n){ printf("参数错误 n"); } }while(m< 0 || n< 0 || t< 0 || t >m*n); M->mu = m; M->nu = n; M->tu = t; if(!(M->rhead = (OLink*)malloc((m+1)*sizeof(OLink)))) exit(-2); if(!(M->chead = (OLink*)malloc((n+1)*sizeof(OLink)))) exit(-2); for(c = 1; c<= M->mu; c++) M->rhead[c]=NULL; for(c = 1; c<= M->nu; c++) M->chead[c]=NULL; for(k = 1; k<= t; k++){ do{ printf("输入第%d个非零元的行号列号值, 用空格隔开n",k); scanf("%d %d %d", &i, &j, &e); if(i<= 0 || j<= 0 || i >m || j >n|| e==0){ printf("参数错误n"); } }while(i<= 0 || j<= 0 || i >m || j >n|| e==0); if(!(p = (OLNode*)malloc(sizeof(OLNode)))) exit(-2); p->i = i; p->j = j; p ->e = e; if(M->rhead[i] == NULL || M->rhead[i]->j >j){ p->right = M->rhead[i]; M->rhead[i] = p; }else{ for(q = M->rhead[i]; (q->right) && (q->right->j< j); q = q->right); p->right = q->right; q->right = p; } if(M->chead[j] == NULL || M->chead[j]->i >i){ p->down = M->chead[j]; M->chead[j] = p; }else{ for(q = M->chead[j]; (q->down) && (q->down->i< i); q = q->down); p->down = q->down; q->down = p; } } return 1; } int PrintSMatrix_OL(CrossList M){ OLink p; int row,col; for(row = 1; row<= M.mu; row++){ if(M.rhead[row]){ p = M.rhead[row]; for(col = 1; col<= M.nu; col++){ if(p->i == row && p->j == col && p != NULL){ printf("%dt",p->e); if(p->right) p = p->right; }else{printf("0t");} } }else{for(col = 1; col<= M.nu; col++) printf("0t");} printf("n"); } return 1; } int AddSMatrix_OL(CrossList *A, CrossList *B){ OLink pa, pb, pre, p, hl[MAXRC + 1]; int i, j; if(A->mu != B->mu || A->nu != B->nu) return 0; for(j = 1; j<= A->nu; j++) hl[j] = A->chead[j]; for(i = 1; i<= A->mu; i++){ pa = A->rhead[i]; pb = B->rhead[i]; pre = NULL; while(pb){ if(!(p = (OLNode*)malloc(sizeof(OLNode)))) exit(-2); p->i = pb->i; p->j = pb->j; p->e = pb->e; if(pa == NULL || pa->j >pb->j){ if(pre == NULL) A->rhead[p->i] = p; else{pre->right = p; } p->right = pa; pre = p; if(A->chead[p->j] == NULL || A->chead[p->j]->i >p->i){ p->down = A->chead[p->j]; A->chead[p->j] = p; }else{ p->down = hl[p->j]->down; hl[p->j]->down = p; } hl[p->j] = p; pb = pb->right; A->tu++; }else if(pa && pa->j< pb->j){ pre = pa; pa = pa->right; }else if(pa->j == pb->j){ pa->e += pb->e; if(pa->e == 0){ if(pre == NULL) A->rhead[pa->i] = pa->right; else{pre->right = pa->right; } p = pa; pa = pa->right; if(A->chead[p->j] == p) A->chead[p->j] = hl[p->j] = p->down; else{hl[p->j]->down = p->down; } free(p); pb = pb->right; A->tu--; }else{pre = pa; pa = pa->right; pb = pb->right; } } } } return 1; } int SubSMatrix_OL(CrossList *A, CrossList *B){ OLink pa, pb, pre, p, hl[MAXRC + 1]; int i, j; if(A->mu != B->mu || A->nu != B->nu) return 0; for(j = 1; j<= A->nu; j++) hl[j] = A->chead[j]; for(i = 1; i<= A->mu; i++){ pa = A->rhead[i]; pb = B->rhead[i]; pre = NULL; while(pb){ if(!(p = (OLNode*)malloc(sizeof(OLNode)))) exit(-2); p->i = pb->i; p->j = pb->j; p->e = - pb->e; if(pa == NULL || pa->j >pb->j){ if(pre == NULL) A->rhead[p->i] = p; else{pre->right = p; } p->right = pa; pre = p; if(A->chead[p->j] == NULL || A->chead[p->j]->i >p->i){ p->down = A->chead[p->j]; A->chead[p->j] = p; }else{ p->down = hl[p->j]->down; hl[p->j]->down = p; } hl[p->j] = p; pb = pb->right; A->tu++; }else if(pa && pa->j< pb->j){ pre = pa; pa = pa->right; }else if(pa->j == pb->j){ pa->e -= pb->e; if(pa->e == 0){ if(pre == NULL) A->rhead[pa->i] = pa->right; else{pre->right = pa->right; } p = pa; pa = pa->right; if(A->chead[p->j] == p) A->chead[p->j] = hl[p->j] = p->down; else{hl[p->j]->down = p->down; } free(p); pb = pb->right; A->tu--; }else{pre = pa; pa = pa->right; pb = pb->right; } } } } return 1; } int MultSMatrix_OL(CrossList A, CrossList B, CrossList *C){ int i, j, e; OLink p, q, p1, rpre, cpre; if(A.nu != B.mu) return 0; C->mu = A.mu; C->nu = B.nu; C->tu = 0; if(!(C->rhead = (OLink*)malloc((C->mu+1)*sizeof(OLink)))) exit(-2); if(!(C->chead = (OLink*)malloc((C->nu+1)*sizeof(OLink)))) exit(-2); for(i = 1; i<= C->mu; i++) C->rhead[i] = NULL; for(j = 1; j<= C->nu; j++) C->chead[j] = NULL; for(i = 1; i<= C->mu; i++){ for(j = 1; j<= C->nu; j++){ p = A.rhead[i]; q = B.chead[j]; e = 0; while(p && q){ if(p->j >q->i){ q = q->down; }else if(p->j< q->i){ p = p->right; }else{ e += p->e * q->e; q = q->down; p = p->right; } } if(e){ C->tu++; if(!(p1 = (OLNode*)malloc(sizeof(OLNode)))) exit(-2); p1->i = i; p1->j = j; p1->e = e; p1->right = NULL; p1->down = NULL; // 行插入 if(C->rhead[i] == NULL) {C->rhead[i] = p1; rpre = p1;} else{rpre->right = p1; rpre = p1; } // 列插入 if(C->chead[j] == NULL) {C->chead[j] = p1; cpre = p1;} else{cpre->down = p1; cpre = p1; } } } } return 1; } int main(){ int num; CrossList M, N, Q; do{ printf("操作：1.矩阵相加 2.矩阵相减 3.矩阵相乘 4.退出n"); scanf("%d",&num); if(num == 1 || num == 2 || num == 3){ printf("请输入矩阵1n"); CreateSMatrix_OL(&M); printf("请输入矩阵2n"); CreateSMatrix_OL(&N); printf("两矩阵为：n"); PrintSMatrix_OL(M); printf("n"); PrintSMatrix_OL(N); switch(num){ case 1: { if(AddSMatrix_OL(&M, &N)){ printf("结果:n"); PrintSMatrix_OL(M); } else {printf("参数错误n");} break; } case 2: { if(SubSMatrix_OL(&M, &N)){ printf("结果:n"); PrintSMatrix_OL(M); } else {printf("参数错误n");} break; } case 3: { if(MultSMatrix_OL(M,N,&Q)){ printf("结果：n"); PrintSMatrix_OL(Q); } else {printf("参数错误n");} break; } default: break; } } }while(num == 1 || num == 2 || num == 3);

好了，本文到此结束，如果可以帮助到大家，还望关注本站哦！