前言

資料結構，一門資料處理的藝術，精巧的結構在一個又一個演算法下發揮著他們無與倫比的高效和精密之美，在為資訊技術打下堅實地基的同時，也令無數開發者和探索者為之著迷，

也因如此，它作為博主大二上學期最重要的必修課出現了，由于大家對于上學期C++系列博文的支持，我打算將這門課的筆記也寫作系列博文，既用于整理、消化，也用于同各位交流、展示資料結構的美，

此系列文章，將會分成兩條主線，一條“資料結構基礎”，一條“資料結構拓展”，“資料結構基礎”主要以記錄課上內容為主，“拓展”則是以課上內容為基礎的更加高深的資料結構或相關應用知識，

歡迎關注博主，一起交流、學習、進步，往期的文章將會放在文末，

這一節，我們來討論一個常用的數學工具——矩陣，尤其是它的存盤結構

不管我們承認與否，矩陣就是一種資料組織的結構，他有自己獨特的運算規律和邏輯結構，

從資料結構學科來說，我們關心各種資料結構的邏輯結構和存盤結構，矩陣的邏輯結構，屬于線性代數學的內容，在這里不需要贅述，所以，作為資料結構學的內容，我們更關心矩陣的存盤結構，也就是以何種方式，將人類可識別的矩陣放置在計算機中，并允許他們進行運算，

陣列

其實說來，我們來看看矩陣的樣子：
[ a 11 a 12 a 13 a 21 a 22 a 23 a 31 a 32 a 33 ] \begin{bmatrix} a_{11}&a_{12} &a_{13} \\ a_{21}&a_{22} &a_{23} \\ a_{31}&a_{32} &a_{33} \end{bmatrix} ???a11?a21?a31??a12?a22?a32??a13?a23?a33?????
這個方方正正的結構，有著確定的行數和列數，總是能夠讓我們能夠不由自主的對應一種基本的資料結構——陣列，不僅是陣列，而且是二維陣列，

一個矩陣有兩個維度，行和列，可以分別對應二維陣列中的兩個維度，更進一步的，假設一個矩陣,他有 n n n行 m m m列，第 i i i行 j j j列元素為 a i j a_{ij} aij?,那么使用二維陣列可表示為a[i][j]

這樣，一個矩陣就可以裝進一個二維陣列中，這就是最樸素的“矩陣的陣串列示”
在這里插入圖片描述
不過，二者還是存在一些不那么相互兼容的地方，比如較為突出的：在高級語言中，陣列的下標是從0開始計數的，而矩陣的下標則是從1開始計數的，不過好在陣列的兼容性更強，只要將空間多開一些，就可以解決這個問題，所以無傷大雅，

來舉個例子：

示例一，讀入一個n行m列的整數矩陣，計算矩陣中元素的和并輸出該矩陣

int a[N + 1][M + 1];//未滿足矩陣從1開始計數，陣列范圍要開大一些，至少多一，建議再多開一些
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	
	for(int i = 1;i <= n;i++){//先行后列讀入矩陣中元素
		for(int j = 1;j <= m;j++){
			scanf("%d",&a[i][j]);
			sum += a[i][j];
		}
	}
	printf("%d",sum);
	int sum = 0;
	for(int i = 1;i <= n;i++){//先行后列遍歷矩陣中元素，列印并計算加和
		for(int j = 1;j <= m;j++){
			printf("%-2d",a[i][j]);
		}
		printf("\n");
	}
}

運行結果如下
在這里插入圖片描述

三元組表

用陣列存盤矩陣很香，香就香在他太簡潔了，但香也有香的代價，那就是陣列的空間問題，尤其是當矩陣的規模非常大且內容非常稀疏，存在大面積的0，這時候，使用陣列存盤矩陣的問題就顯現出來了，

就像是偌大的操場，整整齊齊的排列著 100 × 100 = 10000 100\times 100 = 10000 100×100=10000個座位，但是來參加活動的同學只有寥寥數人（ ≤ 100 \leq100 ≤100），，，

這時如果我們是管理人員，要記錄每個同學坐在那個位置，最好的方法不是畫一張 100 × 100 100\times 100 100×100的表格然后填寫學生姓名，而是將它們的姓名寫在一起，同時在后面跟著寫上他們座位的坐標，
在這里插入圖片描述

對于稀疏矩陣的存盤方式，采取的方法正是像記錄學生姓名一樣，只不過矩陣元素是整數而非字串，但是不論如何，都可以使用如下三元組表示一個元素：
( v a l , r o w , c o l ) 即 ( 值 , 行 , 列 ) (val,row,col)\\ 即\\ (值,行,列) (val,row,col)即(值,行,列)
將矩陣中所有的非零元素按照上述形式放在一個線性表中，就成為了矩陣的一種壓縮表示——三元組表

舉個例子：

給定兩個n行m列的矩陣，輸出他們相加矩陣的三元素表，元素順序任意

int a[N][3],sizeA = 0;//矩陣A
int b[N][3],sizeB = 0;//矩陣B
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i = 1;i <= n;i++){//讀入矩陣A并轉化為三元組表
		for(int j = 1,x;j <= m;j++){
			scanf("%d",&x);
			if(x != 0){
				a[sizeA][0] = x;
				a[sizeA][1] = i;
				a[sizeA][2] = j;
				sizeA++;
			}
		}
	}
	for(int i = 1;i <= n;i++){//讀入矩陣B并轉化為三元組表
		for(int j = 1,x;j <= m;j++){
			scanf("%d",&x);
			if(x != 0){
				b[sizeB][0] = x;
				b[sizeB][1] = i;
				b[sizeB][2] = j;
				sizeB++;
			}
		}
	}
	for(int i = 0;i < sizeB;i++){//將矩陣B加到矩陣A上
		for(int j = 0;j < sizeA;j++){
			if(b[i][2] == a[j][2] && b[i][1] == a[j][1]){//如果位置匹配，相加并執行下個元素
				a[j][0] += b[i][0];
				break;
			}
			if(j == sizeA - 1){//如果列舉完A中最后一個也沒匹配到，則說明A中該位置為0，應該在三元組中新加入元素
				a[sizeA][0] = b[i][0];
				a[sizeA][1] = b[i][1];
				a[sizeA][2] = b[i][2];
				sizeA++;
				break;
			}
		}
	}
	for(int i = 0;i < sizeA;i++){
		printf("%-3d%-3d%-3d\n",a[i][0],a[i][1],a[i][2]);
	}
}

運行結果如下：
在這里插入圖片描述
（這個示例的編碼方式上存在許多可以優化的地方，有些步驟寫的冗余是為了更好地演示三元組表）

另外，上面的三元組表實作方式是順序表，也就是陣列，但在上文中我們提到過存放他的可以是線性表，也就是說除了陣列，我們也可以使用鏈表來完成對三元組表的存盤，從而更加便于對三元組表中元素的增刪，

十字鏈表

在上文中，提到了稀疏矩陣面臨的問題，就是定長的陣列中存在著大量多余的元素，對于這樣的情景，在討論線性表的時候，就使用了鏈表來代替順序表也就是陣列，

在這里，我們仍然可以復刻這個思想，使用鏈表來代替二維陣列，可是，傳統的鏈表只有一維，不能很好地表示二維的陣列，

如果將元素都穿成一串進行存盤，那么不能快速的遍歷某一行或某一列全部的元素，

如果將元素按照行進行鏈表存盤，那么訪問某一列的元素又成為了問題，

所以為了解決這個問題，更好地存盤且便于訪問，我們有必要對鏈表結點進行修改，

在之前，每個鏈表只有一個維度的指標，最多也就是前驅后繼都做記錄，現在，我們在結點中多加入一個維度的指標，讓結點既可以訪問同行的后繼，也可以訪問同列的后繼，
在這里插入圖片描述
同時給每行和每列增設頭結點，將鏈表約定為單向回圈鏈表，

按照這樣的約定，如下矩陣：

[ 0 7 0 0 0 5 0 1 0 0 0 0 15 0 0 0 0 0 3 0 ] \begin{bmatrix} 0 &7 &0 &0 &0 \\ 5 &0 &1 &0 &0 \\ 0 &0 &15 &0 &0 \\ 0 &0 &0 &3 &0 \end{bmatrix} ?????0500?7000?01150?0003?0000??????
表示成為十字鏈表就是：
在這里插入圖片描述
看著挺不錯，接著就來用代碼實作這個結構，首先，需要定義結點結構和哨兵結點類

class Node{//結點結構體
	int value;//結點值
	int col;//列下標
	int row;//行下標
	Node * right;//右方元素，即行后繼
	Node * down;//下方元素，即列后繼
};

很顯然，十字鏈表包含很多相關內容，不妨定義一個類來封裝十字鏈表表示的矩陣，這樣可以將結點類定義成為十字鏈表的內部類來增強封裝性，

class LinkedMatrix{//十字鏈表實作的矩陣類
private:
	class Node{//結點結構體
	public:
		int value;//結點值
		int col;//列下標
		int row;//行下標
		Node * right;//右方元素，即行后繼
		Node * down;//下方元素，即列后繼
	};
	Node ** rows;//行哨兵結點
	Node ** cols;//列哨兵結點
	int col;//列數
	int row;//行數
}

初始化鏈表的構造方法：

	LinkedMatrix(int n,int m){
		row = n;
		col = m;
		//創建行列哨兵結點陣列，矩陣下標從1開始，不要忘記了
		rows = new Node *[n + 1];
		cols = new Node *[m + 1];
		//初始化行哨兵結點
		for(int i = 1;i <= row;i++){
			rows[i] = new Node();
			rows[i]->right = rows[i];//回圈鏈表初始化
			rows[i]->down = NULL;
			rows[i]->row = 0;//行下標默認置零
		}
		//初始化列哨兵結點
		for(int i = 1;i <= col;i++){
			cols[i] = new Node();
			cols[i]->down = cols[i];//回圈鏈表初始化
			cols[i]->right = NULL;
			cols[i]->col = 0;//列下標默認置零
		}
	}

接著再創造兩個公共方法：添加和查詢

public:
bool add(int val,int r,int c){//插入一個元素
		if(c <= 0 || r <= 0 || c > col || r > row){
			return false;
		}
		//創建并初始化結點
		Node * node = new Node();
		node->value = val;
		node->col = c;
		node->row = r;
		//將該元素插入行
		node->right = rows[r]->right;
		rows[r]->right = node;
		//將該元素插入列
		node->down = cols[c]->down;
		cols[c]->down = node;
	}
	int get(int r,int c){//獲取r行c列的元素值
		//遍歷c列元素，尋找是否有r行元素（也可以遍歷行，尋找列）
		Node * node= cols[c]->down;
		while(node != cols[c]){
			if(node->row == r){
				return node->value;
			}
			node = node->down;
		}
		return 0;//如果沒有找到，則該元素為0
	}

完整的類定義如下：

class LinkedMatrix{//十字鏈表實作的矩陣類
private:
	class Node{//結點結構體
	public:
		int value;//結點值
		int col;//列下標
		int row;//行下標
		Node * right;//右方元素，即行后繼
		Node * down;//下方元素，即列后繼
	};
	Node ** rows;//行哨兵結點
	Node ** cols;//列哨兵結點
	int col;//列數
	int row;//行數
public:
	LinkedMatrix(int n,int m){
		row = n;
		col = m;
		//創建行列哨兵結點陣列，矩陣下標從1開始，不要忘記了
		rows = new Node *[n + 1];
		cols = new Node *[m + 1];
		//初始化行哨兵結點
		for(int i = 1;i <= row;i++){
			rows[i] = new Node();
			rows[i]->right = rows[i];//回圈鏈表初始化
			rows[i]->down = NULL;
			rows[i]->row = 0;//行下標默認置零
		}
		//初始化列哨兵結點
		for(int i = 1;i <= col;i++){
			cols[i] = new Node();
			cols[i]->down = cols[i];//回圈鏈表初始化
			cols[i]->right = NULL;
			cols[i]->col = 0;//列下標默認置零
		}
	}
bool add(int val,int r,int c){//插入一個元素
		if(c <= 0 || r <= 0 || c > col || r > row){
			return false;
		}
		//創建并初始化結點
		Node * node = new Node();
		node->value = val;
		node->col = c;
		node->row = r;
		//將該元素插入行
		node->right = rows[r]->right;
		rows[r]->right = node;
		//將該元素插入列
		node->down = cols[c]->down;
		cols[c]->down = node;
	}
	int get(int r,int c){//獲取r行c列的元素值
		//遍歷c列元素，尋找是否有r行元素（也可以遍歷行，尋找列）
		Node * node= cols[c]->down;
		while(node != cols[c]){
			if(node->row == r){
				return node->value;
			}
			node = node->down;
		}
		return 0;//如果沒有找到，則該元素為0
	}
};

封裝好了十字鏈表類，下面就用一個示例來小試牛刀：

輸入格式：
第一行兩個整數n,m表示矩陣行數和列數
第二行一個整數k，表示矩陣中非零元素數量
接下來k行，每行三個元素v,r,c表示一個非零元素的三元組
接下來一行，一個整數q表示有q個詢問
接下來q行，每行兩個整數r,c，詢問r行c列元素值
輸出格式：
輸出共有q行，本別是每個詢問的答案

主函式代碼如下：

int main(){
	int n,m;
	cin >> n >> m;
	LinkedMatrix * lm = new LinkedMatrix(n,m);
	int k;
	cin >> k;
	int v,c,r;
	for(int i = 0;i < k;i++){
		cin >> v >> r >> c;
		lm->add(v,r,c);
	}
	cin >> k;
	for(int i = 0;i < k;i++){
		cin >> r >> c;
		cout << lm->get(r,c) << endl;
	}
}

將下圖矩陣作為樣例：
[ 0 7 0 0 0 5 0 1 0 0 0 0 15 0 0 0 0 0 3 0 ] \begin{bmatrix} 0 &7 &0 &0 &0 \\ 5 &0 &1 &0 &0 \\ 0 &0 &15 &0 &0 \\ 0 &0 &0 &3 &0 \end{bmatrix} ?????0500?7000?01150?0003?0000??????
運行程式，結果如下：
在這里插入圖片描述

往期博客

【資料結構基礎】資料結構基礎概念
【資料結構基礎】線性資料結構——線性表概念及陣列的封裝
【資料結構基礎】線性資料結構——三種鏈表的總結及封裝
【資料結構基礎】線性資料結構——堆疊和佇列的總結及封裝(C和java)
【演算法與資料結構基礎】模式匹配問題與KMP演算法
【資料結構與演算法基礎】二叉樹與其遍歷序列的互化附代碼實作（C和java）
【資料結構與演算法拓展】單調佇列原理及代碼實作
【資料結構基礎】圖的存盤結構
【資料結構與演算法基礎】并查集原理、封裝實作及例題決議（C和java）
【資料結構與演算法拓展】二叉堆原理、實作與例題（C和java）
【資料結構與演算法基礎】哈夫曼樹與哈夫曼編碼(C++)
【資料結構與演算法基礎】最短路徑問題
【資料結構與演算法基礎】堆排序原理及實作
【資料結構與演算法基礎】最小生成樹演算法原理及實作
【資料結構基礎】圖的遍歷方法與應用

參考資料：

《資料結構》（劉大有，楊博等編著）
《演算法導論》（托馬斯·科爾曼等編著）
《圖解資料結構——使用Java》（胡昭民著）
OI WiKi

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/230400.html

標籤：其他

上一篇：競賽生的十條“軍規”

下一篇：你不是編程挺厲害的嗎？這都做不出來 | 碩士寫給自己：努力應該適可而止

【資料結構基礎】矩陣的存盤結構，陣列，三元組表及十字鏈表

前言

歡迎關注博主，一起交流、學習、進步，往期的文章將會放在文末，

陣列

三元組表

十字鏈表

往期博客

參考資料：