熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

多維數組-矩陣的壓縮存儲- 稀疏矩陣(一)

2013-11-15 15:45:23  來源: 數據結構 

  稀疏矩陣

  設矩陣A mn 中有s個非零元素若s遠遠小於矩陣元素的總數(即s<

  1、稀疏矩陣的壓縮存儲

  為了節省存儲單元,可只存儲非零元素。由於非零元素的分布一般是沒有規律的,因此在存儲非零元素的同時,還必須存儲非零

  元素所在的行號、列號,才能迅速確定一個非零元素是矩陣中的哪一個元素。稀疏矩陣的壓縮存儲會失去隨機存取功能。

  其中每一個非零元素所在的行號、列號和值組成一個三元組(i,j,a ij ),並由此三元組惟一確定。

  稀疏矩陣進行壓縮存儲通常有兩類方法:順序存儲和鏈式存儲。鏈式存儲方法【參見參考書目】。

  2、三元組表

  將表示稀疏矩陣的非零元素的三元組按行優先(或列優先)的順序排列(跳過零元素),並依次存放在向量中,這種稀疏矩陣的順序

  存儲結構稱為三元組表。

  注意:

  以下的討論中,均假定三元組是按行優先順序排列的。

  【例】下圖(a)所示的稀疏矩陣A的三元組表表示見圖(b)

  

  (1)三元組表的類型說明

  為了運算方便,將矩陣的總行數、總列數及非零元素的總數均作為三元組表的屬性進行描述。tw.WINGwIT.coM其類型描述為:

  #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

  即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),它正比於行數和列數的乘積。

  由於非零元素個數一般遠遠大於行數,因此上述稀疏矩陣轉置算法的時間大於通常的轉置算法的時間。


From:http://tw.wingwit.com/Article/program/sjjg/201311/23897.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.