#include <stdio.h>
#include <stdlib.h>
#define ok 1
#define error 0
#define MAXSIZE 100
typedef int ElemType;
typedef struct
{
int col, row; // 行下标,列下标
ElemType value; // 非零元素值
}Term;
typedef struct
{
Term table[MAXSIZE + 1]; // 非零元三元组表,table[0]未用
int m, n, t; // 矩阵的行数、列数和非零元个数
}SparseMatrix;
// 创建稀疏矩阵M
int CreateSparseMatrix(SparseMatrix *M)
{
int i, m, n;
ElemType e;
int k;
printf("请输入矩阵的行数, 列数, 非零元素个数：（以逗号隔开）\n");
scanf("%d,%d,%d", &(*M).m, &(*M).n, &(*M).t);
(*M).table[0].col = 0; // 输出稀疏矩阵M
for (i = 1; i <= (*M).t; i++)
{
do
{
printf("请按行序输入第 %d 个非零元素的行( 1 ～ %d )," "列 ( 1 ～ %d ),元素值：(以逗号隔开)\n", i, (*M).m, (*M).n);
scanf("%d,%d,%d", &m, &n, &e);
k = 0;
// 输出稀疏矩阵M
if (m < 1 || m >(*M).m || n < 1 || n >(*M).n)
k = ok;
// 输出稀疏矩阵M
if (m < (*M).table[i - 1].col || m == (*M).table[i - 1].col && n <= (*M).table[i - 1].row)
k = ok;
} while (k);
(*M).table[i].col = m; //行下标
(*M).table[i].row = n; //列下标
(*M).table[i].value = e; //该下标所对应的值
}
return ok;
}
// 销毁稀疏矩阵M，所有元素置空
void DestroySparseMatrix(SparseMatrix *M)
{
(*M).m = 0;
(*M).n = 0;
(*M).t = 0;
}
// 输出稀疏矩阵M 三元组表
void OutputSparseMatrix(SparseMatrix M)
{
int i;
printf("\n %d 行, %d 列， %d 个非零元素。\n", M.m, M.n, M.t);
printf("======================\n");
printf("%4s %4s %8s\n", "i", "j", "e");
printf("======================\n");
for (i = 1; i <= M.t; i++)
printf("%4d %4d %8d\n", M.table[i].col, M.table[i].row, M.table[i].value);
printf("======================\n");
}
// 输出稀疏矩阵M
void outSparseMatrix(SparseMatrix M)
{
printf("======================\n");
int i = 1;
for (int j = 1; j <= M.m; j++){ //行
for (int k = 1; k <= M.n; k++){ //列
if (j == M.table[i].col&&k == M.table[i].row){
printf("%4d", M.table[i].value);
i++;
if (k == M.n)
printf("\n");
}
else if (k == M.n){
printf("%4d", error);
printf("\n");
}
else
printf("%4d", error);
}
}
printf("======================\n");
}
//稀疏矩阵的转置
int transposeSparseMatrix(SparseMatrix M, SparseMatrix *T)
{
int p, q, col;
(*T).m = M.n;
(*T).n = M.m;
(*T).t = M.t;
if ((*T).t)
{
q = 1;
for (col = 1; col <= M.n; ++col) //先将列转换成行
for (p = 1; p <= M.t; ++p) //再将行转换成列
if (M.table[p].row == col)
{
(*T).table[q].col = M.table[p].row;
(*T).table[q].row = M.table[p].col;
(*T).table[q].value = M.table[p].value;
++q;
}
}
return ok;
}
//快速求稀疏矩阵M的转置矩阵
int FasttransposeSMatrix(SparseMatrix M, SparseMatrix *T)
{
int p, q, t, col, *num, *cpot;
num = (int *)malloc((M.n + 1)*sizeof(int)); // 生成数组（[0]不用）
cpot = (int *)malloc((M.n + 1)*sizeof(int)); // 生成数组（[0]不用）
(*T).m = M.n;
(*T).n = M.m;
(*T).t = M.t;
if ((*T).t)
{
for (col = 1; col <= M.n; ++col)
num[col] = 0; // 设初值
for (t = 1; t <= M.t; ++t) // 求M中每一列含非零元素个数
++num[M.table[t].row];
cpot[1] = 1;
//求第col列中第一个非零元在(*T).data中的序号
for (col = 2; col <= M.n; ++col)
cpot[col] = cpot[col - 1] + num[col - 1];
for (p = 1; p <= M.t; ++p)
{
col = M.table[p].row;
q = cpot[col];
(*T).table[q].col = M.table[p].row;
(*T).table[q].row = M.table[p].col;
(*T).table[q].value = M.table[p].value;
++cpot[col];
}
}
free(num);
free(cpot);
return 1;
}
//由稀疏矩阵M复制得到T
int CopySparseMatrix(SparseMatrix M, SparseMatrix *T){
(*T) = M;
return 1;
}
int comp(int c1, int c2){
int i;
if (c1 < c2)
i = 1;
else if (c1 == c2)
i = 0;
else
i = -1;
return i;
}
//稀疏矩阵的加法：Q=M+N
int AddSparseMatrix(SparseMatrix M, SparseMatrix N, SparseMatrix *Q){
Term *Mp, *Me, *Np, *Ne, *Qh, *Qe;
if (M.m != N.m)
return 0;
if (M.n != N.n)
return 0;
(*Q).m = M.m;
(*Q).n = M.n;
Mp = &M.table[1]; // Mp的初值指向矩阵M的非零元素首地址
Np = &N.table[1]; // Np的初值指向矩阵N的非零元素首地址
Me = &M.table[M.t]; // Me指向矩阵M的非零元素尾地址
Ne = &N.table[N.t]; // Me指向矩阵M的非零元素尾地址
Qh = Qe = (*Q).table;// Qh、Qe的初值指向矩阵Q的非零元素首地址的前一地址
while (Mp <= Me&&Np <= Ne){
Qe++;
int t = comp(Mp->col, Np->col);
switch (t)
{
case 1:
*Qe = *Mp;
Mp++;
break;
case 0:
*Qe = *Mp;
Qe->value = Mp->value + Np->value;
if (!Qe->value) // 元素值为0，不存入压缩矩阵
Qe--;
Mp++;
Np++;
break;
case -1:
*Qe = *Np;
Np++;
}
}
while (Mp <= Me){
Qe++;
*Qe = *Np;
*Qe = *Np;
Np++;
}
while (Mp <= Me){
Qe++;
*Qe = *Mp;
Mp++;
}
(*Q).t = Qe - Qh; // 矩阵Q的非零元素个数
return 1;
}
//求稀疏矩阵的乘积Q=M*N
int MultSparseMatrix(SparseMatrix M, SparseMatrix N, SparseMatrix &Q){
int *ctemp;
ctemp = (int *)malloc((M.n + 1)*sizeof(int)); // 生成数组（[0]不用）
if (M.n != N.m)
return 0;
Q.m = M.m;
Q.n = N.n;
Q.t = 0;
if (M.t*M.t != 0){ //Q是非零矩阵
for (int row = 1; row < M.n; row++){
ctemp[row] = 0;
}
}
return 1;
}
int main()
{
SparseMatrix A, C;
SparseMatrix B,D;
CreateSparseMatrix(&A);
printf("\n行三元组表A：\n");
OutputSparseMatrix(A);
printf("\n稀疏矩阵A为：\n");
outSparseMatrix(A);
printf("\n\n");
printf("行三元组表C为 ：(A的转置): \n");
transposeSparseMatrix(A, &C);
OutputSparseMatrix(C);
printf("\n转置后稀疏矩阵C为：\n");
outSparseMatrix(C);
CopySparseMatrix(A, &B);
printf("\n行三元组表B：\n");
OutputSparseMatrix(B);
printf("\n稀疏矩阵B为：\n");
outSparseMatrix(B);
AddSparseMatrix(A, B, &D);
printf("\n行三元组表D：\n");
OutputSparseMatrix(B);
printf("\n稀疏矩阵D为：\n");
outSparseMatrix(B);
DestroySparseMatrix(&C);
return error;
}
