基本概念
在學習線性代數的時候,經常用到矩陣。在C語言中,表示矩陣的最直覺形式就是二維數組。然而在實際應用中,很多高階矩陣中的非零元素非常少,這個時候如果繼續使用二維數組存儲,那麼就會浪費很多存儲空間。
在資料結構中,我們用三元組存儲稀疏矩陣。三元組定義為(i,v,j),這三個值一次表示矩陣的行、列、值。
![](https://img.laitimes.com/img/_0nNw4CM6IyYiwiM6ICdiwiI0NXYFhGd192UvwVe0lmdhJ3ZvwFM38CXlZHbvN3cpR2Lc1TPB10QGtWUCpEMJ9CXsxWam9CXwADNvwVZ6l2c052bm9CXUJDT1wkNhVzLcRnbvZ2Lc1TPRVmdSdlW5x2RkZXUYpVd1kmYr50MZV3YyI2cKJDT29GRjBjUIF2LcRHelR3LcJzLctmch1mclRXY39DM0ETNxITNwIDNyQDM0EDMy8CX0Vmbu4GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.jpg)
有了基本的概念之後,就可以定義資料結構了
定義一個結構體,來表示三元組的基本屬性
typedef struct
{
int row, col;
int e;
}Triple;
然後再定義一個存儲容器,用來存放三元組的
為了簡單起見,我們用數組來實作,并定義最大存儲單元MAXSIZE為100
typedef struct
{
Triple data[MAXSIZE];
Int m,n,len;
}TSMatrix;
//(TSMatrix表示 Triple Sparse Matrix)
實作矩陣的轉置
實作用三元組表示的矩陣的轉置,可以直接把行列互換,然後再執行按行序為主的排序過程。為了避免重新排序引起的元素移動,可以采用列序遞增轉置法。
具體做法,就是周遊列的下表值,從列數低的值到列數高的值,依次添加到緩存三元組中。很顯然,這是一個雙重for循環結構,内層循環實作周遊整個表,尋找合适的列。外層循環,則記錄要尋找的列數。
//實作轉置
void TransposeTSMatrix(TSMatrix A, TSMatrix* B)
{
int i,j,k;
B->m = A.n;
B->n = A.m;
B->len = A.len;
j=0;
for( k=0; k<A.len; ++k)
{
for( i=0; i<A.len; ++i)
{
if(A.data[i].col == k)
{
B->data[j].row = A.data[i].col;
B->data[j].col = A.data[i].row;
B->data[j].e = A.data[i].e;
++j;
}
}
}
}
有了上面的基礎,就可以寫一個帶有測試驅動的函數
完整代碼
#include <stdio.h>
#define MAXSIZE 100
//三元組的定義
typedef struct
{
int row, col;//表示行列
int e; //表示值
}Triple;
//三元組容器的定義
typedef struct
{
Triple data[MAXSIZE];
int m,n,len;
}TSMatrix;
//實作轉置
void TransposeTSMatrix(TSMatrix A, TSMatrix* B)
{
int i,j,k;
B->m = A.n;
B->n = A.m;
B->len = A.len;
j=0;
for( k=0; k<A.len; ++k)
{
for( i=0; i<A.len; ++i)
{
if(A.data[i].col == k)
{
B->data[j].row = A.data[i].col;
B->data[j].col = A.data[i].row;
B->data[j].e = A.data[i].e;
++j;
}
}
}
}
//測試驅動函數
int main()
{
//将輸入重定向到根目錄下的data.txt
freopen("data.txt", "r", stdin);
TSMatrix A,B;
int i,j,e;
int k=0;
printf("請輸入三元組:");
while(scanf("%d%d%d", &i, &j, &e)!=EOF)
{
A.data[k].row = i-1;
A.data[k].col = j-1;
A.data[k].e = e;
A.len = ++k;
}
printf("\n原始三元組為:\n");
for(i=0; i<A.len; ++i )
{
printf("%3d%3d%3d\n", A.data[i].row+1, A.data[i].col+1, A.data[i].e);
}
printf("\n轉置後:\n");
TransposeTSMatrix(A, &B);
for(i=0; i<B.len; ++i )
{
printf("%3d%3d%3d\n", B.data[i].row+1, B.data[i].col+1, B.data[i].e);
}
return 0;
}
程式截圖