




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)
文檔簡介
1、 稀疏矩陣的壓縮存儲稀疏矩陣的壓縮存儲 三元組表三元組表一、什么是稀疏矩陣一、什么是稀疏矩陣(sparse matrix) 如果矩陣如果矩陣M中的大多數(shù)元素均中的大多數(shù)元素均為零元素,則稱矩陣為零元素,則稱矩陣M為稀疏矩為稀疏矩陣陣 。一般地,當(dāng)非零元素個數(shù)。一般地,當(dāng)非零元素個數(shù)只占矩陣元素總數(shù)的只占矩陣元素總數(shù)的25%30%,或低于這個百分?jǐn)?shù)時,我們稱這樣或低于這個百分?jǐn)?shù)時,我們稱這樣的矩陣為稀疏矩陣。的矩陣為稀疏矩陣。 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
2、0 0M=例如:例如:一、什么是稀疏矩陣一、什么是稀疏矩陣(sparse matrix) 如果矩陣如果矩陣M中的大多數(shù)元素均中的大多數(shù)元素均為零元素,則稱矩陣為零元素,則稱矩陣M為稀疏矩陣。為稀疏矩陣。 用一個三元組(用一個三元組(tupel3)存放矩陣中的存放矩陣中的一個非零元素的行號、列號及該非零元素一個非零元素的行號、列號及該非零元素的值。的值。 一個三元組的形式為:(一個三元組的形式為:(i , j, e) 一般情況下,一個稀疏矩陣中有若干個一般情況下,一個稀疏矩陣中有若干個非零元素,所以要用一個非零元素,所以要用一個“三元組線性表三元組線性表”來存放一個稀疏矩陣。來存放一個稀疏矩陣。
3、1.中心思想:僅存儲矩陣中的非零元素中心思想:僅存儲矩陣中的非零元素2.用順序存儲結(jié)構(gòu)存放三元組線性表用順序存儲結(jié)構(gòu)存放三元組線性表M=原矩陣原矩陣:存放形式存放形式: (按行順序存放)(按行順序存放)data p i 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
4、0 0 0mu=6 nu=7 tu=8注意:注意:為了保存矩陣的行數(shù)、列為了保存矩陣的行數(shù)、列數(shù)和非零元素個數(shù),還需數(shù)和非零元素個數(shù),還需增設(shè)三個量:增設(shè)三個量:mu nu tu3.三元組線性表的數(shù)據(jù)類型描述三元組線性表的數(shù)據(jù)類型描述#define MAXSIZE 12500 /非零元素個數(shù)的最大值typedef struct int i, j; ElemType e; Triple;typedef struct Triple data MAXSIZE+1; /三元組表,data0不用 int mu , nu , tu ; /矩陣的行數(shù)、列數(shù)、非0元素個數(shù)TSMatrix /sparsenes
5、s(稀疏)TSMatrix M ; 用變量用變量 a 存放矩陣存放矩陣 M 的形式如下:的形式如下: 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注意:注意: 引用引用i ,j ,e i ,j ,e 時的格式應(yīng)為:時的格式應(yīng)為: a .data p .ia .data p .i a .data
6、 p .j a .data p .j a .data p .e a .data p .e例如例如 x= x=a adata6.jdata6.j 則則 x=2x=2三、實(shí)現(xiàn)矩陣的運(yùn)算三、實(shí)現(xiàn)矩陣的運(yùn)算:矩陣轉(zhuǎn)置矩陣轉(zhuǎn)置1.實(shí)例實(shí)例:求矩陣求矩陣M的轉(zhuǎn)置矩陣的轉(zhuǎn)置矩陣N:三、實(shí)現(xiàn)矩陣的運(yùn)算三、實(shí)現(xiàn)矩陣的運(yùn)算:矩陣轉(zhuǎn)置矩陣轉(zhuǎn)置1.實(shí)例實(shí)例:求矩陣求矩陣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 0 M= 0 0 -3 0 0 15 12 0
7、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=求解求解注意注意:用變量用變量a和和 b分別存放矩陣分別存放矩陣M和和N (TSMatrix a, TSMatrix b),即要從已知變量即要從已知變量a來求得變量來求得變量b的的值。值。也既要完成如下求解工作:也既要完成如下求解工作: 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 .dat
8、a 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=8求解求解2.求解步驟分析:求解步驟分析:p=1:8, q的值的值=1,2 a . data p i j e a
9、.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 .data 5 b .data 6 b .data 7 b .data 8 求得求得1Col=1注注:p=1:8,尋找尋找 j=col 的的a.data p1 1 3 -3 1
10、 6 152.求解步驟分析:求解步驟分析: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 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
11、 b .data 7 b .data 8 求得求得22注注:p=1:8,尋找尋找 j=col 的的a.data pCol=2 2 1 12 2 5 182.求解步驟分析:求解步驟分析:p=1:8, q的值的值=5,6 a . data p i j e a .data 1 1 2 12 a .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
12、.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,尋找尋找 j=col 的的a.data p 3 1 9 3 4 242.求解步驟分析:求解步驟分析: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
13、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 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,尋找尋找 j=col 的的a.data p4 4 6 -7 2.求解步驟分析:求解步驟分析:p=1:8, q的值的值=7 a . data p i j e a
14、 .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 .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
15、 8 求得求得Col=5注注:p=1:8,尋找尋找 j=col 的的a.data p無無!2.求解步驟分析:求解步驟分析: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
16、 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=6注注:p=1:8,尋找尋找 j=col 的的a.data p6 6 3 14 2.求解步驟分析:求解步驟分析: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
17、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 求得求得Col=7注注:p=1:8,尋找尋找 j=col 的的a.data p無無!2.求解步驟分析:求解步驟分析: a . data p i j e a .data 1 1 2 12 a .da
18、ta 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 .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=83.算法描述算法描述status TransposeSMatrix(TSMatrix a, TSMatrix *b) (*b).mu=a.nu; (*b).nu=a.mu; (*b).tu=a.tu; if (*b).tu) q= 1; for (col= 1 ; col= a.nu ; + + col) for (p= 1 ; p= a.tu ; + +p) if (a.datap .j = =col) b.dataq.i=a.datap .j; b.dataq.j=a.d
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 【正版授權(quán)】 ISO 13317-5:2025 EN Determination of particle size distribution by gravitational liquid sedimentation methods - Part 5: Photosedimentation techniques
- 2025年度人工智能產(chǎn)業(yè)擔(dān)保合作協(xié)議書
- 2025年度餐飲企業(yè)代理記賬與食品安全管理合同
- 2025年度電信設(shè)備采購與維護(hù)服務(wù)合同范本
- 2025年度廠房租賃合同履約監(jiān)督管理服務(wù)合同
- 2025年度二手房無證房產(chǎn)買賣合同風(fēng)險防范條款
- 2025年度工業(yè)用地場地租賃及設(shè)備安裝合同
- 2025年服裝、鞋帽加工機(jī)械項(xiàng)目合作計劃書
- 2025年電能表標(biāo)準(zhǔn)校驗(yàn)裝置項(xiàng)目建議書
- 幼兒園學(xué)期計劃五彩斑斕燦爛生活
- 機(jī)動車商業(yè)保險條款(2020版)
- 2024年全國高考甲卷語文真題試卷含答案
- 2024-2025學(xué)年福建省龍巖市五縣第一次中考科目教學(xué)質(zhì)量檢測試題化學(xué)試題含解析
- 《大小比較》(說課課件)二年級下冊數(shù)學(xué)西師大版
- AQ/T 1089-2020 煤礦加固煤巖體用高分子材料(正式版)
- 幼兒園故事繪本《賣火柴的小女孩兒》課件
- 張五常子女和婚姻合約中的產(chǎn)權(quán)執(zhí)行問題
- 妊娠期高血壓疾病試題
- 醫(yī)院多重耐藥菌感染管理規(guī)范
- 《公平競爭審查條例》微課
- 《肺部疾病 案例分析-原發(fā)性肺癌》課件
評論
0/150
提交評論