《数据结构（C语言版）》稀疏矩阵的三元组表示
清华大学计算机系列教材累计发行超400万册
严蔚敏吴伟民编著
数据结构（C语言版）
以下是本人对该紫皮书第五章数组与广义表中5.3节矩阵的压缩存储的之三元表压缩存储的代码实现，由于我们学校没有讲压缩矩阵的十字链表（即行逻辑连接的顺序表）所以本人就不写这方面的代码了，重点放在树和图，这是数据结构的核心
（貌似专栏把我缩进吃了，懒得加了，另外建议用visualstudio编译，会帮你自动调整缩进）
#define_CRT_SECURE_NO_WARNINGS1
#include
#include
#defineTRUE1
#defineFALSE0
#defineOK1
#defineERROR0
#defineINFEASIBLE-1
#defineOVERFLOW-2
//三元组实现稀疏矩阵的表示和转置
#defineMAXSIZE100//假设非零元个数的最大值为100
typedefintElemType;
typedefintStatus;
typedefstruct
{
inti,j;//该非零元的行下标和列下表
ElemTypee;
}Triple;
Tripledata[MAXSIZE+1];//非零元三元组表，data[0]未用
intmu,nu,tu;//矩阵的行数、列数、非零元个数
}TSMatrix;
//注意，此三元组是以行序存储的，即先存储完第一行的所有元素，再存储第二行的所有元素
StatusCreatSMatrix(TSMatrix&M);//创建稀疏矩阵
voidPrintSMatrix(TSMatrixM);//打印稀疏矩阵
StatusTransposeSMatrix(TSMatrixM,TSMatrix&T);//一般的求矩阵转置的方法
StatusFastTransposeSMatrix(TSMatrixM,TSMatrix&T);//快速求矩阵转置
intnum[20]={0};
intcpot[20]={0};
intmain()
TSMatrixM,T1,T2;
CreatSMatrix(M);
PrintSMatrix(M);
TransposeSMatrix(M,T1);
PrintSMatrix(T1);
FastTransposeSMatrix(M,T2);
PrintSMatrix(T2);
return0;
}
StatusCreatSMatrix(TSMatrix&M)//创建稀疏矩阵
introw,col,number;
M={{0},row,col,number};
inti,j,e;
intcount=1;
M.data[count].i=i;
M.data[count].j=j;
M.data[count].e=e;
count++;
returnOK;
voidPrintSMatrix(TSMatrixM)//打印稀疏矩阵
intp=1;
for(inti=1;i<=M.mu;i++)
for(intj=1;j<=M.nu;j++)
if(i==M.data[p].i&&j==M.data[p].j)
p++;
else
StatusTransposeSMatrix(TSMatrixM,TSMatrix&T)//一般的求矩阵转置的方法
/*
主要思路：按照M的列序进行转置
为了找到M的每一列中的所有非零元素，需要对其三元组表从第一行起全部扫描一遍
由于M是以行序为主序存储每个非零元的，转置之后刚好是T的列序，
因此从上往下扫描刚好是T应有的顺序
*/
T.mu=M.nu;
T.nu=M.mu;
T.tu=M.tu;
if(T.tu)
intq=1;
for(intcol=1;col<=M.nu;col++)//先扫描M的第一列，也就是j=1的情形
for(intp=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++;
StatusFastTransposeSMatrix(TSMatrixM,TSMatrix&T)//快速求矩阵转置