矩陣的壓縮存儲（随機稀疏矩陣的建立和輸出）

實際應用中會有很多利用高階矩陣的問題，有的高階矩陣已達到幾十萬階，幾千億個元素。然而，多數的高階矩陣中包含了大量的數值為零的元素，需要對這類矩陣進行壓縮存儲。因為合理的壓縮存儲不僅能有效地節省存儲空間，而且可以避免進行大量的零值元素參加的運算。壓縮存儲即為多個相同的非零元素隻配置設定一個存儲空間，對零元素不配置設定空間。

對于矩陣分為兩類，假若值相同的元素或者零元素在矩陣中的分布有一定的規律，則稱它為特殊形狀矩陣；否則稱為随機稀疏矩陣。

未必所有的矩陣都可以壓縮，要看其是否具備以上壓縮條件

特殊形狀矩陣的存儲表示

特殊形狀矩陣主要指的是三角形矩陣（方陣的上或下三角全為零）和帶狀矩陣（隻有主對角線附近的若幹條對角線含有非零元）。

對于對稱矩陣的壓縮，隻保留主對角線上和主對角線以下的資料元素，這樣存儲可以将存儲規模減少至原來一半。實作以B[n(n+1)/2] (按行序為主序)存放對稱矩陣的下三角（包括對角線）中的元素，其中B[k]存放aij，可以得到 i , j 與 k 之間的轉換公式。如圖：

矩陣的壓縮存儲（随機稀疏矩陣的建立和輸出）

同樣的方式可以用來解決三角形矩陣的存儲壓縮問題。

另一類特殊矩陣是帶狀矩陣，該種矩陣的所有資料元素都集中在以主對角線為中心的三條對角線上。其餘位置為0，是以可以将其壓縮到一維數組B[3n-2]之中.其中範圍條件是 | i - j | <= 1;

下标轉換公式為： k = 2i + j - 3 ;如下圖：

矩陣的壓縮存儲（随機稀疏矩陣的建立和輸出）

随機稀疏矩陣的壓縮存儲

在 m * n 的矩陣中，有 t 個非零元素，則稱 t / ( m * n) 表示矩陣的稀疏因子，通常認為稀疏因子不超過0.05的矩陣為稀疏矩陣。表示矩陣中的非零元素很少，0元素很多。存儲這樣的稀疏矩陣，可以定義一個新的資料結構名為三元組。三元組中的資料為矩陣中某個資料的行列下标和本身的資料值。用這三個資料可以唯一确定矩陣中某個資料元素。是以可以按行為主序将矩陣中的資料一次轉成三元組。對于所有的三元組，有着不同的存儲方法。

1.三元組順序表

将所有的三元組以順序存儲結構存放線上性表中，則可以得到稀疏矩陣的一種存儲壓縮表示方法，稱為三元組順序表。

//-------稀疏矩陣的三元組順序表存儲表示--------
const int MAXSIZE = 1000;   //假設非零元的個數最大值為1000

typedef struct {
	int i, j;     //該非零元的行下标和列下标
	int e;        //該非零元的元素值
}Triple;
typedef struct {
	Triple data[MAXSIZE + 1];      //非零元三元組表,data[0]未用
	int mu, nu, tu;                //非零元的行數，列數和個數
}TSMatrix;

下面通過對稀疏矩陣的建立輸出（包括以矩陣形式輸出和以三元組表形式輸出）以及通過矩陣M求其轉置矩陣T等的操作來檢驗該種壓縮方法的可操作性。

以下為稀疏矩陣的建立和輸出

#include<stdio.h>
//-------稀疏矩陣的三元組順序表存儲表示--------
const int MAXSIZE = 1000;   //假設非零元的個數最大值為1000

typedef struct {
	int i, j;     //該非零元的行下标和列下标
	int e;        //該非零元的元素值
}Triple;
typedef struct {
	Triple data[MAXSIZE + 1];      //非零元三元組表,data[0]未用
	int mu, nu, tu;                //非零元的行數，列數和個數
}TSMatrix;

int CreateSMatrix(TSMatrix &M)
{ // 建立稀疏矩陣M
	int i, m, n;       //這裡的 i 表示循環變量；m n 用于記錄使用者輸入的非零元素的位置
	int e;        //用于接收輸入的資料元素
	int k;        //k 用于判斷輸入的非零元素是否合理
	printf("請輸入矩陣的行數,列數,非零元素數：\n");
	scanf("%d", &M.mu);
	scanf("%d", &M.nu);
	scanf("%d", &M.tu);
	if (M.tu > MAXSIZE)    //非零數大于最大範圍，傳回0；
		return 0;

	M.data[0].i = 0;    //為後面的順序比較進行鋪墊
	// 不能些下面的三行代碼，因為後面判斷輸入非零值順序時需要利用最初的data[0]中的資料
	//M.data[0].i = M.mu;    //三元組表的第一個元素data[0]用于存儲基本資訊 M.data[0].i 表示矩陣的行數
	//M.data[0].j = M.nu;    //M.data[0].j 表示矩陣的列數
	//M.data[0].e = M.tu;    //M.data[0].e 表示矩陣中非零元的個數
	for (i = 1; i <= M.tu; i++)
	{
		do
		{
			printf("請按行序順序輸入第%d個非零元素所在的行(1～%d),列(1～%d),元素值:\n", i, M.mu, M.nu);
			scanf("%d", &m);
			scanf("%d", &n);
			scanf("%d", &e);
			k = 0;
			if (m<1 || m>M.mu || n<1 || n>M.nu) // 行或列超出範圍
			{
				printf("行或列超出範圍！\n");
				k = 1;
			}     
			//如果輸入的行數小于上一次輸入的行數 或者 輸入的行數等于上次輸入的行數但是輸入的列數小于上次輸入的列數
			if (m < M.data[i - 1].i || m == M.data[i - 1].i&&n <= M.data[i - 1].j) // 行或列的順序有錯
			{
				printf("行或列的順序有錯！\n");
				k = 1;
			}
		} while (k);
		M.data[i].i = m;
		M.data[i].j = n;
		M.data[i].e = e;
	}
	return 1;
}

void PrintSMatrix1(TSMatrix M)
{ // 按矩陣形式輸出M
	int i, j, k = 1;
	Triple *p = M.data;
	printf("矩陣形式輸出如下：\n");
	p++; // p指向第1個非零元素
	for (i = 1; i <= M.mu; i++)
	{
	for (j = 1; j <= M.nu; j++)
	if (k <= M.tu&&p->i == i && p->j == j) // p指向非零元，且p所指元素為目前處理元素
	{
	printf("%3d",p->e); // 輸出p所指元素的值
	p++; // p指向下一個元素
	k++; // 計數器+1
	}
	else // p所指元素不是目前處理元素
	printf("%3d",0); // 輸出0
	printf("\n");
	}
}

void PrintSMatrix(TSMatrix M)
{ // 輸出稀疏矩陣M
	int i;
	printf("稀疏矩陣的基本資訊為：%d行%d列%d個非零元素 輸出結果如下\n", M.mu, M.nu, M.tu);
	printf("行  列  元素值\n");
	for (i = 1; i <= M.tu; i++)
		printf("%2d%4d%6d\n", M.data[i].i, M.data[i].j, M.data[i].e);
}

void main()
{
	TSMatrix M;
	CreateSMatrix(M);
	PrintSMatrix1(M);
	PrintSMatrix(M);
}

對于建立稀疏矩陣時，就是循環輸入每一個三元組的各項數值。不過要注意的是，三元組表M的第一個資料 M.data[0] 不能用來存放矩陣的行數列數非零元素數等基本資訊，因為後面輸入時，要通過M.data[0]的各項進行比較，如果輸入數值後，會導緻後面的比較順序出錯。建立稀疏矩陣的流程根建立連結清單相似，都是在主函數中先 TSMatrix M; 定義三位組表變量，再調用建立函數對其逐個指派。

以下為由矩陣M求其轉置矩陣T的操作

矩陣的壓縮存儲（随機稀疏矩陣的建立和輸出）

兩種轉置的方法，一種是在M表裡按照列的順序開始掃描，然後将行列之互換在插入到T表之中。例如，在M表裡先掃描得到（3，1，-3），互換後得到（1，3，-3），将其插入到T表之中。然後再繼續掃描得到（6，1，15），互換後得到（1，6，15），繼續将其插入到T表之中。同理，掃描列數為2,3,4.....等等。最後全部插入後完成轉置。這樣思路簡單但是效率不高。是以，衍生出一種效率更高的算法，隻用一次掃描。

矩陣的壓縮存儲（随機稀疏矩陣的建立和輸出）

快速轉置：先求的M矩陣中每列有多少個非零元素，然後在轉換時就可以直接将對應的三元組插入到T中相應的位置。

#include<stdio.h>
//-------稀疏矩陣的三元組順序表存儲表示--------
const int MAXSIZE = 1000;   //假設非零元的個數最大值為1000

typedef struct {
	int i, j;     //該非零元的行下标和列下标
	int e;        //該非零元的元素值
}Triple;
typedef struct {
	Triple data[MAXSIZE + 1];      //非零元三元組表,data[0]未用
	int mu, nu, tu;                //非零元的行數，列數和個數
}TSMatrix;

int CreateSMatrix(TSMatrix &M)
{ // 建立稀疏矩陣M
	int i, m, n;       //這裡的 i 表示循環變量；m n 用于記錄使用者輸入的非零元素的位置
	int e;        //用于接收輸入的資料元素
	int k;        //k 用于判斷輸入的非零元素是否合理
	printf("請輸入矩陣的行數,列數,非零元素數：\n");
	scanf("%d", &M.mu);
	scanf("%d", &M.nu);
	scanf("%d", &M.tu);
	if (M.tu > MAXSIZE)    //非零數大于最大範圍，傳回0；
		return 0;

	M.data[0].i = 0;    //為後面的順序比較進行鋪墊
	// 不能些下面的三行代碼，因為後面判斷輸入非零值順序時需要利用最初的data[0]中的資料
	//M.data[0].i = M.mu;    //三元組表的第一個元素data[0]用于存儲基本資訊 M.data[0].i 表示矩陣的行數
	//M.data[0].j = M.nu;    //M.data[0].j 表示矩陣的列數
	//M.data[0].e = M.tu;    //M.data[0].e 表示矩陣中非零元的個數
	for (i = 1; i <= M.tu; i++)
	{
		do
		{
			printf("請按行序順序輸入第%d個非零元素所在的行(1～%d),列(1～%d),元素值:\n", i, M.mu, M.nu);
			scanf("%d", &m);
			scanf("%d", &n);
			scanf("%d", &e);
			k = 0;
			if (m<1 || m>M.mu || n<1 || n>M.nu) // 行或列超出範圍
			{
				printf("行或列超出範圍！\n");
				k = 1;
			}     
			//如果輸入的行數小于上一次輸入的行數 或者 輸入的行數等于上次輸入的行數但是輸入的列數小于上次輸入的列數
			if (m < M.data[i - 1].i || m == M.data[i - 1].i&&n <= M.data[i - 1].j) // 行或列的順序有錯
			{
				printf("行或列的順序有錯！\n");
				k = 1;
			}
		} while (k);
		M.data[i].i = m;
		M.data[i].j = n;
		M.data[i].e = e;
	}
	return 1;
}

void PrintSMatrix1(TSMatrix M)
{ // 按矩陣形式輸出M
	int i, j, k = 1;
	Triple *p = M.data;
	printf("矩陣形式輸出如下：\n");
	p++; // p指向第1個非零元素
	for (i = 1; i <= M.mu; i++)
	{
	for (j = 1; j <= M.nu; j++)
	if (k <= M.tu&&p->i == i && p->j == j) // p指向非零元，且p所指元素為目前處理元素
	{
	printf("%3d",p->e); // 輸出p所指元素的值
	p++; // p指向下一個元素
	k++; // 計數器+1
	}
	else // p所指元素不是目前處理元素
	printf("%3d",0); // 輸出0
	printf("\n");
	}
}

void PrintSMatrix(TSMatrix M)
{ // 輸出稀疏矩陣M
	int i;
	printf("稀疏矩陣的基本資訊為：%d行%d列%d個非零元素 輸出結果如下\n", M.mu, M.nu, M.tu);
	printf("行  列  元素值\n");
	for (i = 1; i <= M.tu; i++)
		printf("%2d%4d%6d\n", M.data[i].i, M.data[i].j, M.data[i].e);
}

const int MAXMN = 100;  //矩陣行或列的最大值為 maxmn + 1
int num[MAXMN], rpos[MAXMN];       //分别用來存放M中每一列的非零元素數量，和每一列中第一個非零元在T中的起始位置
void createRpos(TSMatrix M)
{
	//求M中每一列的第一個非零元在T.data 中的起始序号
	int col;        //用來表示列的序号
	int t;       //循環變量 用于周遊M的三元組表
	for (col = 1; col <= M.nu; col++)
		num[col] = 0;      //先給數組清零
	for (t = 1; t <= M.tu; t++)
		num[M.data[t].j]++;    //通過周遊求得每一列的非零元個數
	rpos[1] = 1;    //M中第一列的第一個非零元在T中的位置肯定是1
	for (col = 2; col <= M.nu; col++)  
		rpos[col] = rpos[col - 1] + num[col - 1];   //第i列的第一個非零元素的位置是第 i-1 列第一個元素位置加上第 i-1 列元素個數
}

int FastTransposeSMatrix(TSMatrix M, TSMatrix &T)
{
	//采用三元組順序表存儲表示，求稀疏矩陣M的轉置矩陣T
	int p, q;   //p用于表示M表中的第幾行，q表示對應的位置（即轉置後T表的第幾行）
	int col;
	T.mu = M.nu;
	T.nu = M.mu;
	T.tu = M.tu;
	if (T.tu)    //如果非零元素個數不為零，則開始轉置
	{
		createRpos(M);
		for (p = 1; p <= M.tu; p++)   //轉置矩陣元素
		{
			col = M.data[p].j;    //讀取M的三元組表中第一個三元組 data 的列數
			q = rpos[col];       //T中第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;
			rpos[col]++;      //同一行的下一個非零元素的位置應增1
		}
	}
	return 1;
}

void main()
{
	TSMatrix M, T;
	CreateSMatrix(M);
	PrintSMatrix1(M);
	PrintSMatrix(M);
	printf("轉置矩陣為：\n");
	FastTransposeSMatrix(M, T);
	PrintSMatrix1(T);

}

2，十字連結清單

當矩陣中非零元個數發生變化時，由于三元組表的順序存儲不便于新資料的插入和删除，是以改用鍊式存儲方法。

建立一個包含5個域的結點，包含 i , j , e ,三個域用來表示其所在的行列數即其本身的元素值，再加上兩個指針域，rnext指向同一行中下一個非零元結點，cnext指向同一列中下一個非零元結點。這樣同一行的非零元可以通過rnext指針形成一個線性連結清單，同一列的非零元素也可以通過cnext指針形成一個線性連結清單。整個矩陣構成一個十字交叉的連結清單。

十字連結清單的類型描述如下：

typedef struct OLNode {
	int i, j;  //該元的行和列下标
	int e;     //該元本身的元素值
	struct OLNode *rnext, *cnext;  //該元所在行表和清單的後繼指針
}OLNode,*OLink;

typedef struct {
	OLink *rhead, *chead;    //行和列連結清單頭指針向量基址在建立存儲結構時配置設定
	int m, n, t;            //稀疏矩陣的行數，列數和非零元素數
}CrossList;

本筆記所依據的教材為嚴薇敏版的《資料結構及應用算法教程》

部分圖檔來源于華中師範大學雲課堂

所有代碼在Visual Studio 2017上均可正常運作

如有錯誤歡迎指出

矩陣的壓縮存儲（随機稀疏矩陣的建立和輸出）

特殊形狀矩陣的存儲表示

随機稀疏矩陣的壓縮存儲

繼續閱讀

Codeforces 1417 D. Make Them Equal(思維+構造)

查找算法之二分查找查找算法之二分查找

查找算法學習之二分查找（Python版本）——BinarySearch

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

Command Network(POJ 3164)---定根最小樹形圖模闆題題目描述輸入格式輸出格式輸入樣例輸出樣例分析源程式

開源低帶寬語音編解碼器

241 Different Ways to Add Parentheses（C代碼版）

【趨高機器視覺】機器視覺技術原了解析及解決方案

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制規程及特點4． CSMA/CD協定5． CSMA/CD的優點6．結束語

極大似然法(ML)與最大期望法(EM)

C++ 第十五周報告1--《冒泡法排序》

筆試面試題目：滑動視窗(二)

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

hdu7108哈希