清華大學(xué)計(jì)算機(jī)系列教材? ?累計(jì)發(fā)行超400萬(wàn)冊(cè)

嚴(yán)蔚敏 吳偉民 編著

數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）?

以下是本人對(duì)該紫皮書(shū)第五章數(shù)組與廣義表中5.3節(jié)矩陣的壓縮存儲(chǔ)的之三元表壓縮存儲(chǔ)的代碼實(shí)現(xiàn)，由于我們學(xué)校沒(méi)有講壓縮矩陣的十字鏈表（即行邏輯連接的順序表）所以本人就不寫(xiě)這方面的代碼了，重點(diǎn)放在樹(shù)和圖，這是數(shù)據(jù)結(jié)構(gòu)的核心

（貌似專欄把我縮進(jìn)吃了，懶得加了，另外建議用visual studio編譯，會(huì)幫你自動(dòng)調(diào)整縮進(jìn)）?

#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

//三元組實(shí)現(xiàn)稀疏矩陣的表示和轉(zhuǎn)置

#define MAXSIZE 100//假設(shè)非零元個(gè)數(shù)的最大值為100

typedef int ElemType;

typedef int Status;

typedef struct

{

int i, j;//該非零元的行下標(biāo)和列下表

ElemType e;

}Triple;

typedef struct

{

Triple data[MAXSIZE + 1];//非零元三元組表，data[0]未用

int mu, nu, tu;//矩陣的行數(shù)、列數(shù)、非零元個(gè)數(shù)

}TSMatrix;

//注意，此三元組是以行序存儲(chǔ)的，即先存儲(chǔ)完第一行的所有元素，再存儲(chǔ)第二行的所有元素

Status CreatSMatrix(TSMatrix& M);//創(chuàng)建稀疏矩陣

void PrintSMatrix(TSMatrix M);//打印稀疏矩陣

Status TransposeSMatrix(TSMatrix M, TSMatrix& T);//一般的求矩陣轉(zhuǎn)置的方法

Status FastTransposeSMatrix(TSMatrix M, TSMatrix& T);//快速求矩陣轉(zhuǎn)置

int num[20] = { 0 };

int cpot[20] = { 0 };

int main()

{

TSMatrix M, T1, T2;

CreatSMatrix(M);

printf("稀疏矩陣存儲(chǔ)成功\n");

printf("你存儲(chǔ)的稀疏矩陣如下：\n");

PrintSMatrix(M);

TransposeSMatrix(M, T1);

printf("使用課本上算法5.1得到了如下轉(zhuǎn)置矩陣：\n");

PrintSMatrix(T1);

FastTransposeSMatrix(M, T2);

printf("使用課本上算法5.2得到了如下轉(zhuǎn)置矩陣：\n");

PrintSMatrix(T2);

return 0;

}

Status CreatSMatrix(TSMatrix& M)//創(chuàng)建稀疏矩陣

{

int row, col, number;

printf("請(qǐng)輸入稀疏矩陣的行數(shù)、列數(shù)和非零元個(gè)數(shù):");

while (scanf("%d%d%d", &row, &col, &number) != 3)

{

while (getchar() != '\n');

printf("非法輸入，請(qǐng)重試！\n");

}

M = { {0},row,col,number };

printf("請(qǐng)依次輸入矩陣中的非零元所在行標(biāo)、列標(biāo)、數(shù)值:\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)//一般的求矩陣轉(zhuǎn)置的方法

/*

主要思路：按照M的列序進(jìn)行轉(zhuǎn)置

為了找到M的每一列中的所有非零元素，需要對(duì)其三元組表從第一行起全部掃描一遍

由于M是以行序?yàn)橹餍虼鎯?chǔ)每個(gè)非零元的，轉(zhuǎn)置之后剛好是T的列序，

因此從上往下掃描剛好是T應(yīng)有的順序

*/

/*如果非零元的個(gè)數(shù)tu與mu×nu同數(shù)量級(jí)，則時(shí)間復(fù)雜度為O(mu×nu2)*/

{

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)//快速求矩陣轉(zhuǎn)置

{

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列中第一個(gè)非零元在b.data中的序號(hào)

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;

}