在介紹矩陣的壓縮存儲前，我們需要明確一個概念：對于特殊矩陣，比如對稱矩陣，稀疏矩陣，上（下）三角矩陣，在數據結構中相同的數據元素只存儲一個。 @[TOC]

三元組順序表

稀疏矩陣由于其自身的稀疏特性，通過壓縮可以大大節省稀疏矩陣的內存代價。具體操作是：將非零元素所在的行、列以及它的值構成一個三元組（i，j，v），然后再按某種規律存儲這些三元組，這種方法可以節約存儲空間 。 如下圖所示為一個稀疏矩陣，我們應該怎么樣存儲呢？

若對其進行壓縮存儲，我們可以將一個非零數組元素的三元看成一個單位存入一維數組，具體如下所示。比如（1,1,1）代表第一行第一列的元素值為1。注意，這里我們只存儲非零值。

具體代碼如下： #include<stdio.h> #include <stdlib.h> #include <time.h> #define NUMBER 3//三元組結構體 typedef struct {//行標r，列標cint r,c;//元素值int data; }triple; //矩陣的結構表示 typedef struct {//存儲該矩陣中所有非0元素的三元組triple data[NUMBER];//row和column分別記錄矩陣的行數和列數，num記錄矩陣中所有的非0元素的個數int row,column,num; }TSMatrix; //輸出存儲的稀疏矩陣 void print(TSMatrix M); int main() {int i;srand((unsigned)time(NULL));TSMatrix M;M.row=3;M.column=3;M.num=3;//初始化矩陣for(i=0;i<M.num;i++){//隨機數范圍[1,3]M.data[i].r=rand()%M.num+1;M.data[i].c=rand()%M.num+1;M.data[i].data=rand()%10;}print(M);return 0; } void print(TSMatrix M){for(int i=1;i<=M.row;i++){for(int j=1;j<=M.column;j++){int value =0;for(int k=0;k<M.num;k++){//遍歷時的r,c行列值和實際存儲row,column行列值的比較，相同的話就說明有非零元素,打印存儲的非0值if(i == M.data[k].r && j == M.data[k].c){printf("%d ",M.data[k].data);value =1;break;}}if(value == 0)printf("0 ");}printf("n");} }

行邏輯鏈接的順序表

使用三元組順序表存儲稀疏矩陣，我們每次訪問其中一個元素都要遍歷整個矩陣，效率比較低。我們可以使用一個一維數組來存儲每行第一個非零元素在一維數組中的位置，這樣就可以提升訪問效率。這樣的表就叫做行邏輯鏈接的順序表。 下圖為一個稀疏矩陣，當使用行邏輯鏈接的順序表對其進行壓縮存儲時，需要做以下兩個工作：

1.將矩陣中的非 0 元素采用三元組的形式存儲到一維數組 data 中：

2.使用數組 rpos 記錄矩陣中每行第一個非 0 元素在一維數組中的存儲位置。

通過以上兩步操作，即實現了使用行邏輯鏈接的順序表存儲稀疏矩陣。 此時，如果想從行邏輯鏈接的順序表中提取元素，則可以借助 rpos 數組提高遍歷數組的效率。 例如，提取圖 1 稀疏矩陣中的元素 2 的過程如下： 由 rpos 數組可知，第一行首個非 0 元素位于data[1]，因此在遍歷此行時，可以直接從第 data[1] 的位置開始，一直遍歷到下一行首個非 0 元素所在的位置（data[3]）之前； 同樣遍歷第二行時，由 rpos 數組可知，此行首個非 0 元素位于 data[3]，因此可以直接從第 data[3] 開始，一直遍歷到下一行首個非 0 元素所在的位置（data[4]）之前；遍歷第三行時，由 rpos 數組可知，此行首個非 0 元素位于 data[4]，由于這是矩陣的最后一行，因此一直遍歷到 rpos 數組結束即可（也就是 data[tu]，tu 指的是矩陣非 0 元素的總個數）。 具體代碼如下 #include <stdio.h> #include <stdlib.h> #include <time.h> #define MAXSIZE 12500 #define MAXRC 100 typedef struct {//行，列int r,c;//元素值int e; }Triple;typedef struct {//矩陣中元素的個數Triple data[MAXSIZE];//每行第一個非零元素在data數組中的位置int rpos[MAXRC];//行數，列數，元素個數int row,column,number; }RLSMatrix; //矩陣的輸出函數 void print(RLSMatrix M){for(int i=1;i<=M.row;i++){for(int j=1;j<=M.column;j++){int value=0;if(i+1 <=M.row){for(int k=M.rpos[i];k<M.rpos[i+1];k++){if(i == M.data[k].r && j == M.data[k].c){printf("%d ",M.data[k].e);value=1;break;}}if(value==0){printf("0 ");}}else{for(int k=M.rpos[i];k<=M.number;k++){if(i == M.data[k].r && j == M.data[k].c){printf("%d ",M.data[k].e);value=1;break;}}if(value==0){printf("0 ");}}}printf("n");} } int main() {int i;//srand((unsigned)time(NULL));RLSMatrix M;//矩陣的大小M.number = 4;M.row = 3;M.column = 4;//每一行首個非零元素在一維數組中的位置M.rpos[1] = 1;M.rpos[2] = 3;M.rpos[3] = 4;M.data[1].e = 3;M.data[1].r = 1;M.data[1].c = 2;M.data[2].e = 5;M.data[2].r = 1;M.data[2].c = 4;M.data[3].e = 1;M.data[3].r = 2;M.data[3].c = 3;M.data[4].e = 2;M.data[4].r = 3;M.data[4].c = 1;//輸出矩陣print(M);return 0; }

十字鏈表法

關于十字鏈表法，具體可看下圖。我們把矩陣的每一行每一列分別看成一個鏈表，然后將每一行和每一列的鏈表的第一個元素存放在一個數組中。這個數組就叫行鏈表的頭指針數組，列鏈表的頭指針數組。當我們訪問矩陣的時候，就可以從行/列頭指針數組中取出對應的指針，就可以訪問這一行或者這一列的元素了。

鏈表中節點的結構應如下圖。所以，除了定義三元組的行，列，數值外，我們還需要定義指向行的指針，指向列的指針。最后還需要定義一個存放行/列鏈表頭結點的數組專門存放各行各列的頭結點。具體代碼如下。

typedef struct CLNode {//矩陣三元組i代表行 j代表列 e代表當前位置的數據int r, c, data; //指針域 行指針 列指針struct CLNode *prow, *pcolumn; }CLNode, *CLink; typedef struct {//行和列鏈表頭數組 CLink rhead[] 這樣寫也可以。寫成指針是為了方便動態分配內存CLink *rhead, *chead; //矩陣的行數,列數和非零元的個數int rows, columns, num; }CrossList;

下面我們將要根據用戶輸入的行數，列數，非零元素的值，來創建矩陣。

//注意檢查用戶的輸入do { flag = 1; printf("輸入矩陣的行數、列數和非0元素個數：");scanf("%d%d%d",&m,&n,&t);if (m<0 || n<0 || t<0 || t>m*n) flag = 0; }while (!flag); M.rows = m;M.columns = n;M.num = t;

用戶輸入合法的情況下我們要創建并初始化存放行列鏈表頭的數組。

//因為下標從1開始，所以頭結點指針多分配一個內存if (!(M.rhead = (CLink*)malloc((m + 1) * sizeof(CLink))) || !(M.chead = (CLink*)malloc((n + 1) * sizeof(CLink)))){printf("初始化矩陣失敗rn");exit(0);}// 初始化行頭指針向量;各行鏈表為空鏈表 for (r = 1; r <= m; r++){M.rhead[r] = NULL;}// 初始化列頭指針向量;各列鏈表為空鏈表 for (c = 1; c <= n; c++){M.chead[c] = NULL;}

存放行列鏈表頭的數組準備好了，接下來我們就要創建數據節點了。根據用戶輸入的行號，列好，數值創建節點。這里同樣要檢查用戶的輸入。

for (scanf("%d%d%d", &r,&c,&data); ((r<=0)||(c<=0)); scanf("%d%d%d", &r,&c,&data)) {if (!(p = (CLNode*)malloc(sizeof(CLNode)))){printf("初始化三元組失敗");exit(0);}p->r = r;p->c = c;p->data= data; }

當創建好一個節點之后，我們就要放到行或者列的正確的位置。根據輸入的行號列號確定插入的位置。那么應該怎樣去插入？分兩種情況 1、當這一行中沒有結點的時候，那么我們直接插入 2、當這一行中有結點的時候我們插入到正確的位置 對于第一個問題，因為之前已經對頭結點數組進行了初始化NULL，所以直接根據NULL==M->rhead[i]就可以判斷一行中有沒有節點。 對于第二個問題，當行中有節點的時候，無非是插入到某個節點之前或者某個節點之后。什么時候插入到節點前？什么時候插入到節點后呢？ 1.插入節點前：當我們要插入的節點的列號小于已經存在的節點的列號，這個時候就要插入到這個節點之前了。 2.插入節點后：當我們要插入的節點的列號大于已經存在的節點的列號，這個時候就要插入到這個節點之后了。 對于第一種情況，代碼如下。

//p為準備插入的節點，要插入到M.rhead[r]之前。if (NULL == M.rhead[r] || M.rhead[r]->c> c){p->prow = M.rhead[r];//M.rhead[r]要始終指向行的第一個節點M.rhead[r] = p;}

對于第二種情況，我們要插入的節點插入到已有節點的后面，那么，已有將要插入節點的列號必定大于已有節點的列號。我們只要找到一個節點比我們將要插入節點的列號大的節點就好，然后插入到這個節點的前面。如果現有的結點沒有一個結點列號是大于要插入的節點的列號的，那么我們就應該插入到最后一個結點之后！

//我們要找到一個比q節點大的節點。在這個節點之前插入for (q = M.rhead[r]; (q->prow) && q->prow->c < c; q = q->prow);p->prow = q->prow;q->prow = p;

對于列的插入同樣如此，就不一一分析了，下面給出具體代碼。

//鏈接到列的指定位置if (NULL == M.chead[c] || M.chead[c]->r> r){p->pcolumn = M.chead[c];M.chead[c] = p;}else{for (q = M.chead[c]; (q->pcolumn) && q->pcolumn->r < r; q = q->pcolumn);p->pcolumn = q->pcolumn;q->pcolumn = p;}

打印矩陣 對于十字鏈表矩陣的打印，我們每次從行/列頭結點數組中取出每一行或者每一列的第一個節點依次往下訪問就可以了，和普通的鏈表訪問沒有區別。如果對鏈表不熟悉的可以參考這篇文章史上最全單鏈表的增刪改查反轉等操作匯總以及5種排序算法(C語言)

void PrintClist(CrossList M) {for (int i = 1; i <= M.num; i++){if (NULL != M.chead[i]){CLink p = M.chead[i];while (NULL != p){printf("%dt%dt%dn",p->r, p->c, p->data);p = p->pcolumn;}}} }

完整代碼如下：

/** @Description: 十字鏈表存儲壓縮矩陣* @Version: V1.0* @Autor: Carlos* @Date: 2020-05-26 16:43:48* @LastEditors: Carlos* @LastEditTime: 2020-05-28 14:40:19*/ #include<stdio.h> #include<stdlib.h> typedef struct CLNode {//矩陣三元組i代表行 j代表列 e代表當前位置的數據int r, c, data; //指針域 行指針 列指針struct CLNode *prow, *pcolumn; }CLNode, *CLink; typedef struct {//行和列鏈表頭指針CLink *rhead, *chead; //矩陣的行數,列數和非零元的個數int rows, columns, num; }CrossList; CrossList InitClist(CrossList M) {CLNode *p,*q;int r,c,data;int m, n, t;int flag;// printf("輸入矩陣的行數、列數和非0元素個數：");// scanf("%d%d%d",&m,&n,&t);do { flag = 1; printf("輸入矩陣的行數、列數和非0元素個數：");scanf("%d%d%d",&m,&n,&t);if (m<0 || n<0 || t<0 ) flag = 0; }while (!flag); M.rows = m;M.columns = n;M.num = t;//因為下標從1開始，所以頭結點指針多分配一個內存if (!(M.rhead = (CLink*)malloc((m + 1) * sizeof(CLink))) || !(M.chead = (CLink*)malloc((n + 1) * sizeof(CLink)))){printf("初始化矩陣失敗rn");exit(0);}// 初始化行頭指針向量;各行鏈表為空鏈表 for (r = 1; r <= m; r++){M.rhead[r] = NULL;}// 初始化列頭指針向量;各列鏈表為空鏈表 for (c = 1; c <= n; c++){M.chead[c] = NULL;} //行數列數不為0 for (scanf("%d%d%d", &r,&c,&data); ((r<=0)||(c<=0)); scanf("%d%d%d", &r,&c,&data)) {if (!(p = (CLNode*)malloc(sizeof(CLNode)))){printf("初始化三元組失敗");exit(0);}p->r = r;p->c = c;p->data= data;//鏈接到行的指定位置。 if (NULL == M.rhead[r] || M.rhead[r]->c> c){p->prow = M.rhead[r];M.rhead[r] = p;}else{for (q = M.rhead[r]; (q->prow) && q->prow->c < c; q = q->prow);p->prow = q->prow;q->prow = p;} //鏈接到列的指定位置if (NULL == M.chead[c] || M.chead[c]->r> r){p->pcolumn = M.chead[c];M.chead[c] = p;}else{for (q = M.chead[c]; (q->pcolumn) && q->pcolumn->r < r; q = q->pcolumn);p->pcolumn = q->pcolumn;q->pcolumn = p;} }return M; }void PrintClist(CrossList M) {for (int i = 1; i <= M.num; i++){if (NULL != M.chead[i]){CLink p = M.chead[i];while (NULL != p){printf("%dt%dt%dn",p->r, p->c, p->data);p = p->pcolumn;}}} } int main() {CrossList M;M.rhead = NULL;M.chead = NULL;M = InitClist(M);PrintClist(M);return 0; }

文中代碼均已測試，有任何意見或者建議均可聯系我。歡迎學習交流！ 如果覺得寫的不錯，請點個贊再走，謝謝！ 如遇到排版錯亂的問題或者有任何疑問、建議，可以在“我的主頁”找到我的聯系方式和我的博客鏈接。

總結

以上是生活随笔為你收集整理的pytorch统计矩阵非0的个数_矩阵的三种存储方式---三元组法 行逻辑链接法 十字链表法...的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。