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

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

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

3、； 1colnu1.實(shí)驗(yàn)分析：在本次實(shí)驗(yàn)當(dāng)中，需要注意一下幾個(gè)關(guān)鍵點(diǎn)：1. 設(shè)置轉(zhuǎn)置后矩陣B的行數(shù)、列數(shù)和非零元素的個(gè)數(shù)；2. 計(jì)算A中每一列的非零元素個(gè)數(shù)；3. 計(jì)算A中每一列的第一個(gè)非零元素在B中的下標(biāo)；4. 依次取A中的每一個(gè)非零元素對(duì)應(yīng)的三元組；2.1 確定該元素在B中的下標(biāo)pb；2.2 將該元素的行號(hào)列號(hào)交換后存入B中pb的位置；2.3 預(yù)置該元素所在列的下一個(gè)元素的存放位置；具體要定義如下若干個(gè)函數(shù)：void setup（）初始化非零元的個(gè)數(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<<"申請(qǐng)空間錯(cuò)誤！n"return 0; if (tb1=(tabletype *)malloc(sizeof(tabletype)=NULL) cout<<"申請(qǐng)空間錯(cuò)誤！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請(qǐng)輸入稀疏矩陣的行數(shù)"cin>>n;cout<<"n請(qǐng)輸入稀疏矩陣的列數(shù)"cin>>m;for(i=0;i<n;i+)for(j=0;j<m;j+) printf("n請(qǐng)輸入數(shù)據(jù)a%d%d=",i,j);cin>>aij

8、;/*建立*/void setup (datatype amaxsizemaxsize, List ta, tabletype *ta1) int i,j;ta1->td=0; /*初始化非零元素個(gè)數(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 原矩陣的列下標(biāo)*/for(j=0;j< ta1->td;j+) /*j 原三元組順序表的下標(biāo)*/ if(taj.q=i) /*尋找原矩陣中最小列下標(biāo)*/ 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行號(hào)t列號(hào)t元素值n"for(i=0; i<nn;i+)cout<<" "<<ai.p<<" "<<ai.q<<" "<<ai.x<<" "<<"n" cout<<"n"實(shí) 驗(yàn) 內(nèi) 容3.測(cè)試用例：1,當(dāng)輸入原稀疏矩陣為A33=2,0,3;1,0,4;0,0,1時(shí)程序運(yùn)行結(jié)果如下：2.當(dāng)輸入稀疏矩陣為A22=1,0;0,2時(shí)運(yùn)行結(jié)果如下：實(shí) 驗(yàn) 內(nèi)