稀疏矩陣的應(yīng)用

1、武 漢 工 程 大 學計算機科學與工程學院數(shù)據(jù)結(jié)構(gòu)實驗報告專業(yè)班級 實驗地點 學生學號 指導教師 學生姓名 實驗時間實驗項目實驗類別操作性（）驗證性（ ）設(shè)計性（ ）綜合性（Y ）其它（ ）實驗?zāi)康募耙螅?）掌握掌握稀疏矩陣的表示方法及其運算的實現(xiàn)；（2）實現(xiàn)稀疏矩陣在三元組、十字鏈表等表示下的各運算并分析其效率。成 績 評 定 表類 別評 分 標 準分值得分合 計上機表現(xiàn)積極出勤、遵守紀律認真完成實驗任務(wù)30分報告質(zhì)量程序代碼規(guī)范、功能正確填寫內(nèi)容完整、體現(xiàn)收獲70分說明： 評閱教師： 日 期： 年 月 日稀疏矩陣的應(yīng)用1、實驗?zāi)康模海?）掌握掌握稀疏矩陣的表示方法及其運算的實現(xiàn)；（2）實

2、現(xiàn)稀疏矩陣在三元組、十字鏈表等表示下的各運算并分析其效率。2、實驗內(nèi)容在mn 的矩陣中，有t個非零元。令= t/(m*n),稱矩陣的稀疏因子，常認為0.05時稱為稀疏矩陣。稀疏矩陣在工程中有著大量的應(yīng)用，不少工程問題都可以轉(zhuǎn)化為對稀疏矩陣的計算問題。用三元組表實現(xiàn)稀疏矩陣的轉(zhuǎn)置，用（順序取，直接存）方法。3、實驗說明：引入兩個數(shù)組作為輔助數(shù)據(jù)結(jié)構(gòu)： numnu：表示矩陣A中某列的非零元素的個數(shù)； cpotnu：初始值表示矩陣A中某列的第一個非零元素在B中的位置。 num與cpot遞推關(guān)系：cpot0=0；cpotcol=cpotcol-1+numcol-1； 1colnu1.實驗分析：在本次實

3、驗當中，需要注意一下幾個關(guān)鍵點：1. 設(shè)置轉(zhuǎn)置后矩陣B的行數(shù)、列數(shù)和非零元素的個數(shù)；2. 計算A中每一列的非零元素個數(shù)；3. 計算A中每一列的第一個非零元素在B中的下標；4. 依次取A中的每一個非零元素對應(yīng)的三元組；2.1 確定該元素在B中的下標pb；2.2 將該元素的行號列號交換后存入B中pb的位置；2.3 預置該元素所在列的下一個元素的存放位置；具體要定義如下若干個函數(shù)：void setup（）初始化非零元的個數(shù)void transition（）轉(zhuǎn)置函數(shù)void input（）輸入函數(shù)void print1()輸出函數(shù)void print2()輸出函數(shù)2.源程序代碼：#includeusi

4、ng namespace std;#include #define maxsize 50typedef int datatype;typedef struct int p,q;datatype x; List;typedef structint md,nd,td; tabletype;int n,m; /*稀疏矩陣的行數(shù)、列數(shù)*/ void input(datatype amaxsizemaxsize );void setup (datatype amaxsizemaxsize, List ta,tabletype *ta1 );void transition (tabletype *ta1,

5、 tabletype *tb1, List ta,List tb);void print1(datatype amaxsizemaxsize);void print2(List a,int nn);int main( ) datatype amaxsizemaxsize; /*稀疏矩陣*/List tamaxsize,tbmaxsize; /*三元組順序表*/tabletype *ta1,*tb1;if (ta1=(tabletype *)malloc(sizeof(tabletype)=NULL) cout申請空間錯誤！n;return 0; if (tb1=(tabletype *)mal

6、loc(sizeof(tabletype)=NULL) cout申請空間錯誤！n;return 0; input(a);setup(a,ta,ta1);transition(ta1, tb1, ta,tb);coutn原稀疏矩陣為：n;print1(a );couttd);couttd);return 1; /*輸入*/void input(datatype amaxsizemaxsize ) int i,j;coutn;coutm;for(i=0;in;i+)for(j=0;jaij;/*建立*/void setup (datatype amaxsizemaxsize, List ta, t

7、abletype *ta1) int i,j;ta1-td=0; /*初始化非零元素個數(shù)*/for(i=0; in;i+)for(j=0;jtd.p=i;tata1-td.q=j;tata1-td.x=aij;ta1-td+; ta1-md=n;ta1-nd=m; /*轉(zhuǎn)置*/void transition (tabletype *ta1, tabletype *tb1, List ta,List tb) int i,j,nn=0;tb1-md=ta1-nd;tb1-nd=ta1-md;tb1-td=ta1-td;if(ta1-td!=0)for (i=0;ind;i+) /*i 原矩陣的列下

8、標*/for(j=0;jtd;j+) /*j 原三元組順序表的下標*/ if(taj.q=i) /*尋找原矩陣中最小列下標*/ tbnn.p=taj.q;tbnn.q=taj.p;tbnn.x=taj.x;nn+; /*矩陣輸出*/void print1(datatype amaxsizemaxsize) int i,j;for(i=0; in;i+) for(j=0;jm;j+)coutaij ;coutn; /*三元組順序表輸出*/void print2(List a,int nn) int i;coutt行號t列號t元素值n;for(i=0; inn;i+)cout ai.p ai.q ai.x n; coutn;實 驗 內(nèi) 容3.測試用例：1,當輸入原稀疏矩陣為A33=2,0,3;1,0,4;0,0,1時程序運行結(jié)果如下：2.當輸入稀疏矩陣為A22=1,0;0,2時運行結(jié)果如下：實 驗 內(nèi) 容實 驗 總 結(jié)4.實驗總結(jié)：針對稀疏矩陣的壓縮存