對矩陣壓縮存儲是為了
❶ 對稀疏矩陣壓縮存儲的目的是什麼 A 便於進行矩陣預算 B 便於輸入和輸出C節省存儲空間 D降低運算世間復雜度
對稀疏矩陣壓縮存儲的目的是:C節省存儲空間和D降低預算時間復雜度,如果是單選題,那麼應該選C節省存儲空間。
矩陣中非零元素的個數遠遠小於矩陣元素的總數,並且非零元素的分布沒有規律,則稱該矩陣為稀疏矩陣(sparse matrix);與之相區別的是,如果非零元素的分布存在規律(如上三角矩陣、下三角矩陣、對角矩陣),則稱該矩陣為特殊矩陣。
稀疏矩陣的計算速度更快,因為M AT L A B只對非零元素進行操作,這是稀疏矩陣的一個突出的優點.假設矩陣A,B中的矩陣一樣.計算2*A需要一百萬次的浮點運算,而計算2*B只需要2 0 0 0次浮點運算.因為M AT L A B不能自動創建稀疏矩陣,所以要用特殊的命令來得到稀疏矩陣.
對於一個用二維數組存儲的稀疏矩陣Amn,如果假設存儲每個數組元素需要L個位元組,那麼存儲整個矩陣需要m*n*L個位元組.但是,這些存儲空間的大部分存放的是0元素,從而造成大量的空間浪費.為了節省存儲空間,可以只存儲其中的非0元素.
❷ 稀疏矩陣的壓縮存儲思想
為了節省存儲空間並且加快處理速度,需要對這類矩陣進行壓縮存儲,壓縮存儲的原則是:不重復存儲相同元素;不存儲零值元素。稀疏矩陣,有三元組表示法、帶輔助行向量的二元組表示法(也即行邏輯鏈表的順序表),十字鏈表表示法等。演算法基本思想:num[col]:第col列的非零元素個數;cpot[col]:第col列第一個非零元在b.data中的恰當位置;在轉置過程中,指示該列下一個非零元在b.data中的位置。
❸ 多維數組-矩陣的壓縮存儲- 稀疏矩陣(一)
稀疏矩陣
設矩陣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
❹ 矩陣的壓縮存儲是什麼
二維數組在形式上是矩陣,因此一般用二維數組來存儲矩陣。在不壓縮存儲的情況下,矩陣採用按行優先或按列優先方式存儲,佔用的存儲單元數等於矩陣的元素個數。在實際應用中,經常出現一些階數很高的矩陣,同時在矩陣中非零元素呈某種規律分布或者矩陣中有大量的零元素,若仍然用常規方法存儲,可能存儲重復的非零元素或零元素,這將造成存儲空間的大量浪費。因此對這類矩陣進行壓縮存儲,從而合理地利用存儲空間。
為了節省存儲空間,可以利用特殊矩陣的規律,對它們進行壓縮存儲,也就是說為多個值相同的元素只分配一個存儲單元,對零元素不分配空間。適合壓縮存儲的矩陣一般是值相同的元素或者零元素在矩陣中分布有一定規律的特殊矩陣和稀疏矩陣。常見的特殊矩陣有對稱矩陣、三角矩陣和對角矩陣。
❺ 稀疏矩陣採用壓縮存儲的目的主要是什麼
節省存儲空間。
根據網路查詢,對稀疏矩陣進行壓縮存儲目的是節芹高省存儲空間。存儲矩陣的一般方法是採用二維數組。
矩族哪陣壓縮由於稀疏矩陣中非零元素較少,零元素較多,因此可以採用只存儲非零元素的方法嫌穗尺來進行壓縮存儲。
❻ 對稀疏矩陣進行壓縮存儲的目的是什麼
對稀疏矩陣進行壓縮存儲目的是節省存儲空間。
存儲矩陣的一般方法是採用二維數組,其優點是可以隨機地訪問每一個元素,因而能夠較容易地實現矩陣的各種運算。
但對於稀疏矩陣而言,若用二維數組來表示,會重復存儲了很多個0了,浪費空間,而且要花費時間來進行零元素的無效計算。所以必須考慮對稀疏矩陣進行壓縮存儲。
(6)對矩陣壓縮存儲是為了擴展閱讀
優點
稀疏矩陣的計算速度更快,因為MATLAB只對非零元素進行操作,這是稀疏矩陣的一個突出的優點。假設矩陣A,B中的矩陣一樣,計算2*A需要一百萬次的浮點運算,而計算2*B只需要2000次浮點運算。
因為MATLAB不能自動創建稀疏矩陣,所以要用特殊的命令來得到稀疏矩陣。算術和邏輯運算都適用於稀疏矩陣。對於一個用二維數組存儲的稀疏矩陣Amn,如果假設存儲每個數組元素需要L個位元組,那麼存儲整個矩陣需要m*n*L個位元組。