《数据结构（C语言版）》稀疏矩阵的三元组表示
清华大学计算机系列教材 累计发行超400万册
严蔚敏 吴伟民 编著
数据结构（C语言版）
以下是本人对该紫皮书第五章数组与广义表中5.3节矩阵的压缩存储的之三元表压缩存储的代码实现，由于我们学校没有讲压缩矩阵的十字链表（即行逻辑连接的顺序表）所以本人就不写这方面的代码了，重点放在树和图，这是数据结构的核心
（貌似专栏把我缩进吃了，懒得加了，另外建议用visual studio编译，会帮你自动调整缩进）
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
//三元组实现稀疏矩阵的表示和转置
#define MAXSIZE 100//假设非零元个数的最大值为100
typedef int ElemType;
typedef int Status;
typedef struct
{
int i, j;//该非零元的行下标和列下表
ElemType e;
}Triple;
typedef struct
{
Triple data[MAXSIZE + 1];//非零元三元组表，data[0]未用
int mu, nu, tu;//矩阵的行数、列数、非零元个数
}TSMatrix;
//注意，此三元组是以行序存储的，即先存储完第一行的所有元素，再存储第二行的所有元素
Status CreatSMatrix(TSMatrix& M);//创建稀疏矩阵
void PrintSMatrix(TSMatrix M);//打印稀疏矩阵
Status TransposeSMatrix(TSMatrix M, TSMatrix& T);//一般的求矩阵转置的方法
Status FastTransposeSMatrix(TSMatrix M, TSMatrix& T);//快速求矩阵转置
int num[20] = { 0 };
int cpot[20] = { 0 };
int main()
{
TSMatrix M, T1, T2;
CreatSMatrix(M);
printf("稀疏矩阵存储成功\n");
printf("你存储的稀疏矩阵如下：\n");
PrintSMatrix(M);
TransposeSMatrix(M, T1);
printf("使用课本上算法5.1得到了如下转置矩阵：\n");
PrintSMatrix(T1);
FastTransposeSMatrix(M, T2);
printf("使用课本上算法5.2得到了如下转置矩阵：\n");
PrintSMatrix(T2);
return 0;
}
Status CreatSMatrix(TSMatrix& M)//创建稀疏矩阵
{
int row, col, number;
printf("请输入稀疏矩阵的行数、列数和非零元个数:");
while (scanf("%d%d%d", &row, &col, &number) != 3)
{
while (getchar() != '\n');
printf("非法输入，请重试！\n");
}
M = { {0},row,col,number };
printf("请依次输入矩阵中的非零元所在行标、列标、数值:\n");
int i, j, e;
int count = 1;
while (count <= number && scanf("%d%d%d", &i, &j, &e) == 3)
{
M.data[count].i = i;
M.data[count].j = j;
M.data[count].e = e;
count++;
}
return OK;
}
void PrintSMatrix(TSMatrix M)//打印稀疏矩阵
{
int p = 1;
for (int i = 1; i <= M.mu; i++)
{
for (int j = 1; j <= M.nu; j++)
{
if (i == M.data[p].i && j == M.data[p].j)
{
printf("%-3d", M.data[p].e);
p++;
}
else
{
printf("0 ");
}
}
printf("\n");
}
}
Status TransposeSMatrix(TSMatrix M, TSMatrix& T)//一般的求矩阵转置的方法
/*
主要思路：按照M的列序进行转置
为了找到M的每一列中的所有非零元素，需要对其三元组表从第一行起全部扫描一遍
由于M是以行序为主序存储每个非零元的，转置之后刚好是T的列序，
因此从上往下扫描刚好是T应有的顺序
*/
/*如果非零元的个数tu与mu×nu同数量级，则时间复杂度为O(mu×nu²)*/
{
T.mu = M.nu;
T.nu = M.mu;
T.tu = M.tu;
if (T.tu)
{
int q = 1;
for (int col = 1; col <= M.nu; col++)//先扫描M的第一列，也就是j=1的情形
{
for (int 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)//快速求矩阵转置
{
T.mu = M.nu;
T.nu = M.mu;
T.tu = M.tu;
if (T.tu)
{
for (int t = 1; t <= M.tu; t++)
{
num[M.data[t].j]++;
}
cpot[1] = 1;
//求col列中第一个非零元在b.data中的序号
for (int col = 2; col <= M.nu; col++)
{
cpot[col] = cpot[col - 1] + num[col - 1];
}
for (int p = 1; p <= M.tu; p++)
{
int col = M.data[p].j;
int 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]++;
}
}
return OK;
}
