數(shù)據(jù)結(jié)構稀疏矩陣的三元組表存儲方法學習教案

1、會計學1數(shù)據(jù)結(jié)構稀疏矩陣的三元組表存儲數(shù)據(jù)結(jié)構稀疏矩陣的三元組表存儲(cn ch)方法方法第一頁，共21頁。一、什么一、什么(shn me)是稀疏矩陣是稀疏矩陣(sparse matrix) 如果矩陣如果矩陣(j zhn)M中的大多中的大多數(shù)元素均為零元素，則稱矩陣數(shù)元素均為零元素，則稱矩陣(j zhn)M為稀疏矩陣為稀疏矩陣(j zhn) 。一般地，當非零元素個數(shù)只占矩陣一般地，當非零元素個數(shù)只占矩陣(j zhn)元素總數(shù)的元素總數(shù)的25%30%,或或低于這個百分數(shù)時，我們稱這樣的低于這個百分數(shù)時，我們稱這樣的矩陣矩陣(j zhn)為稀疏矩陣為稀疏矩陣(j zhn)。第1頁/共21頁第二頁，

2、共21頁。 0 12 9 0 0 0 0 0 0 0 0 0 0 0-3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 015 0 0 -7 0 0 0M=例如例如(lr)：一、什么是稀疏一、什么是稀疏(xsh)矩陣矩陣(sparse matrix) 如果矩陣如果矩陣M中的大多數(shù)元素中的大多數(shù)元素(yun s)均為零元素均為零元素(yun s)，則稱矩陣，則稱矩陣M為稀疏矩陣。為稀疏矩陣。第2頁/共21頁第三頁，共21頁。 用一個三元組（用一個三元組（tupel3）存放矩陣）存放矩陣(j zhn)中的一個非零元素的行號、列號及該中的一個非零元素的行號、列號及

3、該非零元素的值。非零元素的值。 一個三元組的形式為：一個三元組的形式為：（i , j, e） 一般情況下，一個稀疏一般情況下，一個稀疏(xsh)矩陣中有若干矩陣中有若干個非零元素，所以要用一個個非零元素，所以要用一個“三元組線性表三元組線性表”來來存放一個稀疏存放一個稀疏(xsh)矩陣。矩陣。1.中心思想：僅存儲矩陣中的非零元素中心思想：僅存儲矩陣中的非零元素第3頁/共21頁第四頁，共21頁。2.用順序存儲結(jié)構用順序存儲結(jié)構(jigu)存放三元組存放三元組線性表線性表M=原矩陣原矩陣(j zhn):存放存放(cnfng)形式形式: （按行順序（按行順序存放存放(cnfng)）data p i

4、j edata 1 1 2 12data 2 1 3 9data 3 3 1 -3data 4 3 6 14data 5 4 3 24data 6 5 2 18data 7 6 1 15data 8 6 4 -7 0 12 9 0 0 0 0 0 0 0 0 0 0 0-3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 015 0 0 -7 0 0 0mu=6 nu=7 tu=8注意：注意：為了保存矩陣的行數(shù)、列數(shù)為了保存矩陣的行數(shù)、列數(shù)和非零元素個數(shù)，還需增設和非零元素個數(shù)，還需增設三個量：三個量：mu nu tu第4頁/共21頁第五頁，共21頁。3.三元

5、組線性表的數(shù)據(jù)類型描述三元組線性表的數(shù)據(jù)類型描述(mio sh)#define MAXSIZE 12500 /非零元素(yun s)個數(shù)的最大值typedef struct int i, j; ElemType e; Triple;typedef struct Triple data MAXSIZE+1; /三元組表，data0不用(byng) int mu , nu , tu ; /矩陣的行數(shù)、列數(shù)、非0元素個數(shù)TSMatrix /sparseness(稀疏)TSMatrix M ； 第5頁/共21頁第六頁，共21頁。用變量用變量 a 存放存放(cnfng)矩陣矩陣 M 的形式如下：的形式如

6、下： a . data p i j e a .data 1 1 2 12 a .data 2 1 3 9 a .data 3 3 1 -3 a .data 4 3 6 14 a .data 5 4 3 24 a .data 6 5 2 18 a .data 7 6 1 15 a .data 8 6 4 -7 a. mu=6 a. nu=7 a. tu=8注意：注意： 引用引用(ynyng)i ,j ,(ynyng)i ,j ,e e 時的格式應為：時的格式應為： a .data a .data p .i p .i a .data a .data p .j p .j a .data a .dat

7、a p .e p .e例如例如 x=ax=adata6.jdata6.j 則則 x=2 x=2第6頁/共21頁第七頁，共21頁。三、實現(xiàn)矩陣的運算三、實現(xiàn)矩陣的運算(yn sun):矩矩陣轉(zhuǎn)置陣轉(zhuǎn)置1.實例實例(shl):求矩陣求矩陣M的轉(zhuǎn)置矩陣的轉(zhuǎn)置矩陣N:第7頁/共21頁第八頁，共21頁。三、實現(xiàn)三、實現(xiàn)(shxin)矩陣的運算矩陣的運算:矩矩陣轉(zhuǎn)置陣轉(zhuǎn)置1.實例實例(shl):求矩陣求矩陣M的轉(zhuǎn)置矩陣的轉(zhuǎn)置矩陣N: 0 12 9 0 0 0 0 0 0 0 0 0 0 0 -3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 015 0 0 -7 0 0

8、 0 M= 0 0 -3 0 0 15 12 0 0 0 18 0 9 0 0 24 0 0 0 0 0 0 0 -7 0 0 0 0 0 0 0 0 14 0 0 0 0 0 0 0 0 0 N=求解求解(qi ji)注意注意:用變量用變量a和和 b分別存放矩陣分別存放矩陣M和和N (TSMatrix a, TSMatrix b),即即要從已知變量要從已知變量a來求得變量來求得變量b的值。的值。第8頁/共21頁第九頁，共21頁。也既要完成也既要完成(wn chng)如下求解工如下求解工作：作： a . data p i j e a .data 1 1 2 12 a .data 2 1 3 9

9、 a .data 3 3 1 -3 a .data 4 3 6 14 a .data 5 4 3 24 a .data 6 5 2 18 a .data 7 6 1 15 a .data 8 6 4 -7 a. mu=6 a. nu=7 a. tu=8 b . data q i j e b .data 1 1 3 -3 b .data 2 1 6 15 b .data 3 2 1 12 b .data 4 2 5 18 b .data 5 3 1 9 b .data 6 3 4 24 b .data 7 4 6 -7 b .data 8 6 3 14 b. mu=7 b. nu=6 b. tu

10、=8求解求解(qi ji)第9頁/共21頁第十頁，共21頁。2.求解求解(qi ji)步驟分析：步驟分析：p=1:8, q的值的值=1,2 a . data p i j e a .data 1 1 2 12 a .data 2 1 3 9 a .data 3 3 -3 a .data 4 3 6 14 a .data 5 4 3 24 a .data 6 5 2 18 a .data 7 6 15 a .data 8 6 4 -7 a. mu=6 a. nu=7 a. tu=8 b . data q i j e b .data 1 b .data 2 b .data 3 b .data 4 b

11、 .data 5 b .data 6 b .data 7 b .data 8 求得求得1Col=1注注:p=1:8,尋找尋找(xnzho) j=col 的的a.data p1 1 3 -3 1 6 15第10頁/共21頁第十一頁，共21頁。2.求解求解(qi ji)步驟分析：步驟分析：p=1:8, q的值的值=3,4 a . data p i j e a .data 1 1 12 a .data 2 1 3 9 a .data 3 3 1 -3 a .data 4 3 6 14 a .data 5 4 3 24 a .data 6 5 18 a .data 7 6 1 15 a .data 8

12、 6 4 -7 a. mu=6 a. nu=7 a. tu=8 b . data q i j e b .data 1 1 3 -3 b .data 2 1 6 15 b .data 3 b .data 4 b .data 5 b .data 6 b .data 7 b .data 8 求得求得22注注:p=1:8,尋找尋找(xnzho) j=col 的的a.data pCol=2 2 1 12 2 5 18第11頁/共21頁第十二頁，共21頁。2.求解步驟求解步驟(bzhu)分析：分析：p=1:8, q的值的值=5,6 a . data p i j e a .data 1 1 2 12 a .

13、data 2 1 9 a .data 3 3 1 -3 a .data 4 3 6 14 a .data 5 4 24 a .data 6 5 2 18 a .data 7 6 1 15 a .data 8 6 4 -7 a. mu=6 a. nu=7 a. tu=8 b . data q i j e b .data 1 1 3 -3 b .data 2 1 6 15 b .data 3 2 1 12 b .data 4 2 5 18 b .data 5 b .data 6 b .data 7 b .data 8 求得求得33Col=3注注:p=1:8,尋找尋找(xnzho) j=col 的的

14、a.data p 3 1 9 3 4 24第12頁/共21頁第十三頁，共21頁。2.求解求解(qi ji)步驟分析：步驟分析：p=1:8, q的值的值=7 a . data p i j e a .data 1 1 2 12 a .data 2 1 3 9 a .data 3 3 1 -3 a .data 4 3 6 14 a .data 5 4 3 24 a .data 6 5 2 18 a .data 7 6 1 15 a .data 8 6 -7 a. mu=6 a. nu=7 a. tu=8 b . data q i j e b .data 1 1 3 -3 b .data 2 1 6

15、15 b .data 3 2 1 12 b .data 4 2 5 18 b .data 5 3 1 9 b .data 6 3 4 24 b .data 7 b .data 8 求得求得Col=4注注:p=1:8,尋找尋找(xnzho) j=col 的的a.data p4 4 6 -7 第13頁/共21頁第十四頁，共21頁。2.求解求解(qi ji)步驟分析：步驟分析：p=1:8, q的值的值=7 a . data p i j e a .data 1 1 2 12 a .data 2 1 3 9 a .data 3 3 1 -3 a .data 4 3 6 14 a .data 5 4 3

16、24 a .data 6 5 2 18 a .data 7 6 1 15 a .data 8 6 4 -7 a. mu=6 a. nu=7 a. tu=8 b . data q i j e b .data 1 1 3 -3 b .data 2 1 6 15 b .data 3 2 1 12 b .data 4 2 5 18 b .data 5 3 1 9 b .data 6 3 4 24 b .data 7 4 6 -7 b .data 8 求得求得Col=5注注:p=1:8,尋找尋找(xnzho) j=col 的的a.data p無無!第14頁/共21頁第十五頁，共21頁。2.求解步驟求解步

17、驟(bzhu)分析：分析：p=1:8, q的值的值=8 a . data p i j e a .data 1 1 2 12 a .data 2 1 3 9 a .data 3 3 1 -3 a .data 4 3 14 a .data 5 4 3 24 a .data 6 5 2 18 a .data 7 6 1 15 a .data 8 6 4 -7 a. mu=6 a. nu=7 a. tu=8 b . data q i j e b .data 1 1 3 -3 b .data 2 1 6 15 b .data 3 2 1 12 b .data 4 2 5 18 b .data 5 3 1

18、 9 b .data 6 3 4 24 b .data 7 4 6 -7 b .data 8 求得求得Col=6注注:p=1:8,尋找尋找(xnzho) j=col 的的a.data p6 6 3 14 第15頁/共21頁第十六頁，共21頁。2.求解步驟求解步驟(bzhu)分析：分析：p=1:8, q的值的值=8 a . data p i j e a .data 1 1 2 12 a .data 2 1 3 9 a .data 3 3 1 -3 a .data 4 3 6 14 a .data 5 4 3 24 a .data 6 5 2 18 a .data 7 6 1 15 a .data

19、 8 6 4 -7 a. mu=6 a. nu=7 a. tu=8 b . data q i j e b .data 1 1 3 -3 b .data 2 1 6 15 b .data 3 2 1 12 b .data 4 2 5 18 b .data 5 3 1 9 b .data 6 3 4 24 b .data 7 4 6 -7 b .data 8 6 3 14 求得求得Col=7注注:p=1:8,尋找尋找(xnzho) j=col 的的a.data p無無!第16頁/共21頁第十七頁，共21頁。2.求解求解(qi ji)步驟分析：步驟分析： a . data p i j e a .data 1 1 2 12 a .data 2 1 3 9 a .data 3 3 1 -3 a .data 4 3 6 14 a .data 5 4 3 24 a .data 6 5 2 18 a .data 7 6 1 15 a .data 8 6 4 -7 a. mu=6 a. nu=7 a. tu=8 b . data q i j e b .data 1 1 3 -3 b .data 2 1 6 15 b .