⑴ 矩陣的壓縮存儲例子
稀疏矩陣壓縮存儲
一般來講，零元素多到了一定程度並且沒有規律分布的矩陣叫做稀疏矩陣。對稀疏矩陣的壓縮存儲必須充分考慮以下三個問題：
① 盡可能減少或者不存儲零元素以節省空間，降低空間復雜度。
② 盡可能快地實現數據元素的存儲位置與原有位置之間的轉換。
③ 盡可能不與零元素進行運算，以降低時間復雜度。
稀疏矩陣的壓縮存儲有三種最常見的方法，分別是三元組順序表、行邏輯鏈接順序表和十字鏈表。
⑵ 矩陣的壓縮存儲
可以看出，我們僅需聲明一個長度為(1+n)n/2的一維數組array即可，剩餘的都是重復的元素。
假設一維數組存儲的是下三角部分，並且我們現在找的a[i][j]也是在下三角，則：
寫成完整的公式，如下所示
此時我們可以聲明一個長度為(1 + n) * n / 2 + 1的一維數組來存儲這個三角矩陣，+1是增加一個存儲常數的空間。
線代里的對角矩陣，除對角線外，其餘元素都是0：
我們這里說的是非零元素都集中在對角線上下若干條對角線的對角矩陣。
n階對角矩陣的存儲有些困難，假設a條對角線是非0元，則一維數組array的大小為：
給定 i j，找對應的 k
如何壓縮？我們只需要存儲非0元即可，我們可以定義一個結構體：
進行壓縮後的存儲方式：
第一行表明原矩陣是5 * 5，並且有3個非0元
⑶ 多維數組-矩陣的壓縮存儲- 稀疏矩陣（一）
稀疏矩陣
設矩陣A mn 中有s個非零元素 若s遠遠小於矩陣元素的總數(即s< <m×n)，則稱a為稀疏矩陣。 p=""> </m×n)，則稱a為稀疏矩陣。>
1、稀疏矩陣的壓縮存儲
為了節省存儲單元，可只存儲非零元素。由於非零元素的分布一般是沒有規律的，因此在存儲非零元素的同時，還必須存儲非零
元素所在的行號、列號，才能迅速確定一個非零元素是矩陣中的哪一個元素。稀疏矩陣的壓縮存儲會失去隨機存取功能。
其中每一個非零元素所在的行號、列號和值組成一個三元組(i，j，a ij )，並由此三元組惟一確定。
稀疏矩陣進行壓縮存儲通常有兩類方法：順序存儲和鏈式存儲。鏈式存儲方法【參見參考書目】。
2、三元組表
將表示稀疏矩陣的非零元素的三元組按行優先(或列優先)的順序排列(跳過零元素)，並依次存放在向量中，這種稀疏矩陣的順序
存儲結構稱為三元組表。
注意：
以下的討論中，均假定三元組是按行優先順序排列的。
【例】下圖(a)所示的稀疏矩陣A的三元組表表示見圖(b)
(1)三元組表的類型說明
為了運算方便，將矩陣的總行數、總列數及非零元素的總數均作為三元組表的屬性進行描述。.WINGwIT.其類型描述為：
#define MaxSize 10000 //由用戶定義
typedef int DataType; //由用戶定義
typedef struct { //三元組
int i，j;//非零元的行、列號
DataType v; //非零元的值
}TriTupleNode;
typedef struct{ //三元組表
TriTupleNode data[MaxSize]; //三元組表空間
int m,n，t; //矩陣的行數、列數及非零元個數
}TriTupleTable;
(2) 壓縮存儲結構上矩陣的轉置運算
一個m×n的矩陣A，它的轉置矩陣B是一個n×m的矩陣，且：
A[i][j]=B[j][i]，0≤i <m，0≤j<n， p=""> </m，0≤j<n，>
即A的行是B的列，A的列是B的行。
【例】下圖中的B和上圖中的A互為轉置矩陣。
①三元組表表示的矩陣轉置的思想方法
第一步：根據A矩陣的行數、列數和非零元總數確定B矩陣的列數、行數和非零元總數。
第二步：當三元組表非空(A矩陣的非零元不為0)時，根據A矩陣三元組表的結點空間data(以下簡稱為三元組表)，將A的三
元組表a->data置換為B的三元組表b->data。
②三元組表的轉置
方法一:簡單地交換a->data中i和j中的內容，得到按列優先順序存儲倒b->data;再將b->data重排成按行優先順序的三元組表。
方法二:由於A的列是B的行，因此，按a->data的列序轉置，所得到的轉置矩陣B的三元組表b->data必定是按行優先存放的。
按這種方法設計的演算法，其基本思想是：對A中的每一列col(0≤col≤a->n-1)，通過從頭至尾掃描三元組表a->data，找出所有
列號等於col的那些三元組，將它們的行號和列號互換後依次放人b->data中，即可得到B的按行優先的壓縮存貯表示。具體實現參見
【 動畫演示 】
③具體演算法：
void TransMatrix(TriTupleTable *b，TriTupleTable *a)
{//*a，*b是矩陣A、B的三元組表表示，求A轉置為B
int p，q，col;
b->m=a->n; b->n=a->m; //A和B的行列總數互換
b->t=a->t; //非零元總數
if(b->t<=0)
Error("A=0"); //A中無非零元，退出
q=0;
for(col=0;coln;col++) //對A的每一列
for(p=0;pt;p++) //掃描A的三元組表
if(a->data[p].j==col){ //找列號為col的三元組
b->data[q).i=a->data[p].j;
b->data[q].j=a->data[p].i;
b->data[q].v=a->data[p].v;
q++;
}
} //TransMatrix
④演算法分析
該演算法的時間主要耗費在col和p的二重循環上：
若A的列數為n，非零元素個數t，則執行時間為O(n×t)，即與A的列數和非零元素個數的乘積成正比。
通常用二維數組表示矩陣時，其轉置演算法的執行時間是O(m×n)，它正比於行數和列數的乘積。
由於非零元素個數一般遠遠大於行數，因此上述稀疏矩陣轉置演算法的時間大於通常的轉置演算法的時間。
lishixin/Article/program/sjjg/201311/23897
⑷ 特殊矩陣的壓縮存儲：上三角、對稱、下三角存儲，有三個問題。求大俠們解答~親一個~這個圖能看清嗎
1.k=n*(n+1)/2的原因是：對於三角矩陣，從1到N的總和是這么多，也就是說整個矩陣有這么多元素。另外正三角陣對應正方形。
對稱矩陣滿足A的轉置也就是自身的特點，元素上，a[i,j] = a[j,i]。實際上的存儲可以利用三角陣。所以老實說我對於他對稱陣演算法為什麼少一個元素也有疑惑。
可能是三角陣可以對應不等長的矩陣，所以造成了k值不一樣。
2.上三角陣，存在的元素是滿足[1<= j <=n, i >= j]的關系[這里用i表橫坐標j表縱坐標]，如果是長3寬4的當然不能和長4寬3的相提並論，試著畫畫就明白了。
3.對稱陣不會出現像三角陣那樣有一小角還是其他數字的情況。這個其他數字就是(6+1)-1=6。
4.壓縮存儲，只是將部分符合條件的矩陣減少一部分的存儲空間。老實說我也感覺不很有用，除非他處理的數據本身必然具備此類特點。
5.固定的，多試幾次自己記下來然後找找就好。如果沒記錯的話，在矩陣上畫畫就可以看出來。
6.stdlib.h是標準的輸入輸出庫，最為常用，至少裡麵包括了scanf等函數，只要你需要printf你就不能扔掉它。否則會出現函數未定義的問題。畢竟語言本身不提供函數類庫，類庫需要另行引用。
⑸ 什麼是壓縮矩陣
在這里分開來給你解釋
矩陣是許多科學計算、工程數學尤其是數值分析中經常研究的對象，矩陣也就是二維數組,所以它可以採用順
序存儲是來存儲其中的元素。但有時矩陣的階數很高，同時在矩陣中游很多值相同的元素，或大多數元素的值為
零，這時再採用嚴格的順序存儲顯然是很浪費空間的，因為存儲零元素或許多值相同的元素是沒有意義的，因此為
了節省存儲空間，對這類矩陣通常採用壓縮存儲。
壓縮存儲：為多個值相同的元素值分配一個存儲空間，對零元素不分配存儲空間。
特殊矩陣：各個元素的分布有一定規律
系數矩陣：矩陣中多數元素值為零。
⑹ 上三角矩陣的壓縮存儲原則是怎樣的
上三角矩陣的壓縮存儲原則：對於三角矩陣，從1到N的總和是這么多，也就是說整個矩陣有這么多元素。另外正三角陣對應正方形。
經常出現一些階數很高的矩陣，同時在矩陣中非零元素呈某種規律分布或者矩陣中有大量的零元素，若仍然用常規方法存儲，可能存儲重復的非零元素或零元素，這將造成存儲空間的大量浪費。因此對這類矩陣進行壓縮存儲，從而合理地利用存儲空間。
簡正模式：
矩陣在物理學中的另一類泛應用是描述線性耦合調和系統。這類系統的運動方程可以用矩陣的形式來表示，即用一個質量矩陣乘以一個廣義速度來給出運動項，用力矩陣乘以位移向量來刻畫相互作用。求系統的解的最優方法是將矩陣的特徵向量求出（通過對角化等方式）。
稱為系統的簡正模式。這種求解方式在研究分子內部動力學模式時十分重要：系統內部由化學鍵結合的原子的振動可以表示成簡正振動模式的疊加。描述力學振動或電路振盪時，也需要使用簡正模式求解。
⑺ 怎樣壓縮矩陣元素的存儲空間
AC
稀疏矩陣(SparseMatrix):是矩陣中的一種特殊情況,其非零元素的個數遠小於零元素的個數.
壓縮存儲:為多個值相同的元素只分配一個存儲空間;對0元素不分配空間.目的是節省大量存儲空間.
當使用三元組順序表（又稱有序的雙下標法）壓縮存儲稀疏矩陣時,對矩陣中的每個非零元素用三個域分別表示其所在的行號,列號和元素值.它的特點是,非零元在表中按行序有序存儲,因此便於進行依行順序處理的矩陣運算.當矩陣中的非0元素少於1/3時即可節省存儲空間.
⑻ 數據結構-特殊矩陣的壓縮存儲
本文介紹對稱矩陣、三角矩陣、對角矩陣和稀疏矩陣的壓縮存儲方法。
在一個n階矩陣A中，若元素滿足aij=aji,0<=i,j<=n-1，則稱矩陣A為對稱矩陣。
按行優先順序將這些元素存放在一個一維數組s[n(n+1)/2]中，元素aij在s中對應的下標為k：
以主對角線劃分，三角矩陣分為上三角和下三角兩種，上三角矩陣的下三角所有元素均為常數c，下三角矩陣正好相反。
按行優先順序將三角矩陣存放在一維數組s[n(n+1)/2+1]，其中常數c存放在數組的最後一個分量中。
上三角矩陣元素aij在s中對應的下標為k：
下三角矩陣元素aij在s中對應的下標為k：
對角矩陣是指矩陣中所有的非零元素集中在以主對角線為中心的帶狀區域中。一個k對角矩陣（k為奇數）A滿足若|i-j|>(k-1)/2則元素aij=0。
將三對角矩陣A中的非零元素按行優先順序存放到數組s[3n-2]中，在三對角矩陣A中，除第一行和最後一行只有兩個非零元素外，其他每行中均有三個非零元素。三對角矩陣中的元素aij在s中對應的下標為 k=3×i-1+j-(i-1)=2×i+j .
設矩陣Amn中有s個非零元素，若s遠遠小於矩陣元素的總數，即s<<mxn，則稱A為稀疏矩陣。
對於稀疏矩陣的壓縮存儲方法通常有兩種，分別是三元組順序表和十字鏈表。
1. 三元組順序表
每個元素是一個結構體，包括該元素在矩陣中的行數、列數和數值，所有元素存在一個向量vector中，並同時記錄矩陣的行數、列數及非零元素個數等信息。
2. 十字鏈表
為了克服順序表中對非零元素插入和刪除操作帶來的不便，採用鏈接存儲結構存儲稀疏矩陣。
十字鏈表將每個元素存儲為一個結構體，除了包括元素的行號、列號、數值外，還包括一個向右指針域用於指向同一行中的下一個非零元素和一個向下指針域用於指向同一列中的下一個非零元素。所有結構體通過兩個一維指針數組分別存儲各個行鏈表的頭指針和各個列鏈表的頭指針組織成一個整體。
目標是將每個元素的行號列號交換，並按照新的行列號按序存放。關鍵在於如何高效地進行按序存放。
方法一：樸素轉置演算法
按照原列號分別從頭至尾掃描，依次放入新的矩陣中。對於一個m行n列且非零元素個數為t的稀疏矩陣而言，該演算法的時間復雜度為O(t×n)。
方法二：快速轉置演算法
採用一個數組cnum[cols]記錄每一列中的元素個數，一個數組cpot[cols]記錄每一列的第一個非零元素在轉置矩陣順序表中的下標。cnum和cpot各採用一次遍歷得到，其中cpot[0]=0，cpot[col]=cpot[col-1]+cnum[col-1]。