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

1、精選優(yōu)質(zhì)文檔-傾情為你奉上武 漢 工 程 大 學計算機科學與工程學院數(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)康模海?）掌握掌握稀疏矩陣的表示方

2、法及其運算的實現(xiàn)；（2）實現(xiàn)稀疏矩陣在三元組、十字鏈表等表示下的各運算并分析其效率。2、實驗內(nèi)容在m×n 的矩陣中，有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

3、； 1colnu1.實驗分析：在本次實驗當中，需要注意一下幾個關(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 預(yù)置該元素所在列的下一個元素的存放位置；具體要定義如下若干個函數(shù)：void setup（）初始化非零元的個數(shù)void transition（）轉(zhuǎn)置函數(shù)void input（）輸入函數(shù)void print1()輸出函數(shù)void print2()輸出函數(shù)

4、2.源程序代碼：#include<iostream>using namespace std;#include <malloc.h>#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 t

5、a,tabletype *ta1 );void transition (tabletype *ta1, 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)=NU

6、LL) cout<<"申請空間錯誤！n"return 0; if (tb1=(tabletype *)malloc(sizeof(tabletype)=NULL) cout<<"申請空間錯誤！n"return 0; input(a);setup(a,ta,ta1);transition(ta1, tb1, ta,tb);cout<<"n原稀疏矩陣為：n"print1(a );cout<<"n原三元組順序表為：n"print2(ta,ta1->td);cout&l

7、t;<"n轉(zhuǎn)置后的三元組順序表：n"print2(tb, tb1->td);return 1; /*輸入*/void input(datatype amaxsizemaxsize ) int i,j;cout<<"n請輸入稀疏矩陣的行數(shù)"cin>>n;cout<<"n請輸入稀疏矩陣的列數(shù)"cin>>m;for(i=0;i<n;i+)for(j=0;j<m;j+) printf("n請輸入數(shù)據(jù)a%d%d=",i,j);cin>>aij

8、;/*建立*/void setup (datatype amaxsizemaxsize, List ta, tabletype *ta1) int i,j;ta1->td=0; /*初始化非零元素個數(shù)*/for(i=0; i<n;i+)for(j=0;j<m;j+)if (aij!=0) tata1->td.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

9、, 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;i<ta1->nd;i+) /*i 原矩陣的列下標*/for(j=0;j< ta1->td;j+) /*j 原三元組順序表的下標*/ if(taj.q=i) /*尋找原矩陣中最小列下標*/ tbnn.p=taj.q;tbnn.q=taj.p;tbnn.x=taj.x;nn+; /*矩陣輸出*/void print1(datat

10、ype amaxsizemaxsize) int i,j;for(i=0; i<n;i+) for(j=0;j<m;j+)cout<<aij<<" "cout<<"n" /*三元組順序表輸出*/void print2(List a,int nn) int i;cout<<"t行號t列號t元素值n"for(i=0; i<nn;i+)cout<<" "<<ai.p<<" "<<ai.q<<" "<<ai.x<<" "<<"n" cout<<"n"實 驗 內(nèi) 容3.測試用例：1,當輸入原稀疏矩陣為A33=2,0,3;1,0,4;0,0,1時程序運行結(jié)果如下：2.當輸入稀疏矩陣為A22=1,0;0,2時運行結(jié)果如下：實 驗 內(nèi)