4.2.1 矩陣的數(shù)組表示
【數(shù)據(jù)結(jié)構(gòu)】數(shù)組和字符串（一）：矩陣的數(shù)組表示
4.2.2 特殊矩陣的壓縮存儲(chǔ)
??矩陣是以按行優(yōu)先次序?qū)⑺芯仃囋卮娣旁谝粋€(gè)一維數(shù)組中。但是對(duì)于特殊矩陣，如對(duì)稱矩陣、三角矩陣、對(duì)角矩陣和稀疏矩陣等, 如果用這種方式存儲(chǔ)，會(huì)出現(xiàn)大量存儲(chǔ)空間存放重復(fù)信息或零元素的情況，這樣會(huì)造成很大的空間浪費(fèi)。為節(jié)約存儲(chǔ)空間和算法（程序）運(yùn)行時(shí)間，通常會(huì)采用壓縮存儲(chǔ)的方法。
- 對(duì)角矩陣：指除了主對(duì)角線以外的元素都為零的矩陣，即對(duì) 任意 i ≠ j (1≤ i , j ≤n)，都有M(i, j)=0。由于只有主對(duì)角線上有非零元素，只需存儲(chǔ)主對(duì)角線上的元素即可。
- 三角矩陣：指上三角或下三角的元素都為零的矩陣。同樣地，只需存儲(chǔ)其中一部分非零元素，可以節(jié)省存儲(chǔ)空間。
- 對(duì)稱矩陣：指矩陣中的元素關(guān)于主對(duì)角線對(duì)稱的矩陣。由于對(duì)稱矩陣的非零元素有一定的規(guī)律，可以只存儲(chǔ)其中一部分元素，從而減少存儲(chǔ)空間。
- 稀疏矩陣：指大部分元素為零的矩陣。傳統(tǒng)的按行優(yōu)先次序存儲(chǔ)方法會(huì)浪費(fèi)大量空間來(lái)存儲(chǔ)零元素，因此采用壓縮存儲(chǔ)的方法更為合適。常見的壓縮存儲(chǔ)方法有：壓縮稠密行（CSR）、壓縮稠密列（CSC）、坐標(biāo)列表（COO）等。
a. 對(duì)角矩陣的壓縮存儲(chǔ)
【數(shù)據(jù)結(jié)構(gòu)】數(shù)組和字符串（二）：特殊矩陣的壓縮存儲(chǔ)：對(duì)角矩陣——一維數(shù)組
b~c. 三角、對(duì)稱矩陣的壓縮存儲(chǔ)
【數(shù)據(jù)結(jié)構(gòu)】數(shù)組和字符串（三）：特殊矩陣的壓縮存儲(chǔ)：三角矩陣、對(duì)稱矩陣——一維數(shù)組
d. 稀疏矩陣的壓縮存儲(chǔ)——三元組表
??對(duì)于稀疏矩陣的壓縮存儲(chǔ)，由于非零元素的個(gè)數(shù)遠(yuǎn)小于零元素的個(gè)數(shù)，并且非零元素的分布沒有規(guī)律，無(wú)法簡(jiǎn)單地利用一維數(shù)組和映射公式來(lái)實(shí)現(xiàn)壓縮存儲(chǔ)。針對(duì)稀疏矩陣，通常采用特定的數(shù)據(jù)結(jié)構(gòu)來(lái)進(jìn)行壓縮存儲(chǔ)，以減少存儲(chǔ)空間的占用。
??一種常見的稀疏矩陣壓縮存儲(chǔ)方法是使用"三元組"表示法，也稱為COO（Coordinate）格式，只存儲(chǔ)非零元素的值以及它們的行列坐標(biāo)。通過使用三元組（Triplet）來(lái)表示非零元素的位置和值，每個(gè)三元組包含三個(gè)信息：非零元素的行索引、非零元素的列索引以及非零元素的值。
結(jié)構(gòu)體
typedef struct {
int row;
int col;
int value;
} Triple;
typedef struct {
Triple data[MAX_SIZE];
int rows;
int cols;
int length;
} TripletTable;
??定義了兩個(gè)結(jié)構(gòu)體：Triple 和 TripletTable。
-
Triple結(jié)構(gòu)體表示稀疏矩陣的非零元素，包含三個(gè)字段：row表示行號(hào)，col表示列號(hào)，value表示元素的值。 -
TripletTable結(jié)構(gòu)體用于存儲(chǔ)稀疏矩陣的數(shù)據(jù)，包含一個(gè)data數(shù)組用于存儲(chǔ)非零元素的Triple結(jié)構(gòu)體，以及rows、cols和length字段分別表示矩陣的行數(shù)、列數(shù)和非零元素的數(shù)量。
初始化
void initTable(TripletTable* table, int rows, int cols) {
table->rows = rows;
table->cols = cols;
table->length = 0;
}
?? initTable 函數(shù)用于初始化 TripletTable 結(jié)構(gòu)體，指定矩陣的行數(shù)和列數(shù)，并將 length 字段置為 0。
元素設(shè)置
void insertElement(TripletTable* table, int row, int col, int value) {
if (table->length >= MAX_SIZE) {
printf("Table is full. Cannot insert more elements.\n");
return;
}
Triple* element = &(table->data[table->length]);
element->row = row;
element->col = col;
element->value = value;
table->length++;
}
??insertElement 函數(shù)用于向稀疏矩陣中插入一個(gè)元素，傳入?yún)?shù)為行號(hào)、列號(hào)和元素的值。
- 函數(shù)首先檢查當(dāng)前非零元素的數(shù)量是否已達(dá)到上限
MAX_SIZE- 如果達(dá)到上限則輸出錯(cuò)誤信息并返回。
- 否則，將新元素插入到
data數(shù)組的末尾，并更新length字段。
打印矩陣
void displayTable(TripletTable* table) {
int matrix[table->rows][table->cols];
for (int i = 0; i < table->rows; i++) {
for (int j = 0; j < table->cols; j++) {
matrix[i][j] = 0;
}
}
printf("Row\tColumn\tValue\n");
for (int i = 0; i < table->length; i++) {
Triple* element = &(table->data[i]);
printf("%d\t%d\t%d\n", element->row, element->col, element->value);
matrix[element->row][element->col] = element->value;
}
printf("Matrix:\n");
for (int i = 0; i < table->rows; i++) {
for (int j = 0; j < table->cols; j++) {
printf("%d\t", matrix[i][j]);
}
printf("\n");
}
}
??displayTable 函數(shù)用于顯示稀疏矩陣的內(nèi)容：文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-743221.html
- 創(chuàng)建一個(gè)與稀疏矩陣相同大小的二維數(shù)組
matrix，并將其所有元素初始化為 0； - 遍歷
data數(shù)組中的非零元素，輸出每個(gè)元素的行號(hào)、列號(hào)和值，并將相應(yīng)位置的matrix數(shù)組元素更新為對(duì)應(yīng)的值； - 輸出整個(gè)矩陣的內(nèi)容。
主函數(shù)
int main() {
TripletTable table;
initTable(&table, 3, 3);
insertElement(&table, 0, 0, 1);
insertElement(&table, 0, 1, 2);
insertElement(&table, 1, 1, 3);
insertElement(&table, 2, 2, 4);
displayTable(&table);
return 0;
}
- 創(chuàng)建一個(gè)
TripletTable結(jié)構(gòu)體table，并使用initTable函數(shù)初始化它，指定矩陣的行數(shù)和列數(shù)為3。 - 調(diào)用
insertElement函數(shù)向table中插入四個(gè)非零元素，分別位于 (0, 0)、(0, 1)、(1, 1) 和 (2, 2) 位置。 - 通過調(diào)用
displayTable函數(shù)，打印出稀疏矩陣的內(nèi)容和對(duì)應(yīng)的完整矩陣表示。
輸出結(jié)果
文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-743221.html
代碼整合
#include <stdio.h>
#define MAX_SIZE 10
typedef struct {
int row;
int col;
int value;
} Triple;
typedef struct {
Triple data[MAX_SIZE];
int rows;
int cols;
int length;
} TripletTable;
void initTable(TripletTable* table, int rows, int cols) {
table->rows = rows;
table->cols = cols;
table->length = 0;
}
void insertElement(TripletTable* table, int row, int col, int value) {
if (table->length >= MAX_SIZE) {
printf("Table is full. Cannot insert more elements.\n");
return;
}
Triple* element = &(table->data[table->length]);
element->row = row;
element->col = col;
element->value = value;
table->length++;
}
void displayTable(TripletTable* table) {
int matrix[table->rows][table->cols];
for (int i = 0; i < table->rows; i++) {
for (int j = 0; j < table->cols; j++) {
matrix[i][j] = 0;
}
}
printf("Row\tColumn\tValue\n");
for (int i = 0; i < table->length; i++) {
Triple* element = &(table->data[i]);
printf("%d\t%d\t%d\n", element->row, element->col, element->value);
matrix[element->row][element->col] = element->value;
}
printf("Matrix:\n");
for (int i = 0; i < table->rows; i++) {
for (int j = 0; j < table->cols; j++) {
printf("%d\t", matrix[i][j]);
}
printf("\n");
}
}
int main() {
TripletTable table;
initTable(&table, 3, 3);
insertElement(&table, 0, 0, 1);
insertElement(&table, 0, 1, 2);
insertElement(&table, 1, 1, 3);
insertElement(&table, 2, 2, 4);
displayTable(&table);
return 0;
}
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】數(shù)組和字符串（四）：特殊矩陣的壓縮存儲(chǔ)：稀疏矩陣——三元組表的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
