稀疏矩陣相關(guān)操作的實(shí)現(xiàn)

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)設(shè)計(jì)說明書稀疏矩陣相關(guān)操作的實(shí)現(xiàn)學(xué)生姓名 張美燕 學(xué) 號 1118014066 班 級 計(jì)本1102班 成 績 指導(dǎo)教師 曹陽 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院2013年9月22日 課程設(shè)計(jì)任務(wù)書20132014學(xué)年第一學(xué)期課程設(shè)計(jì)名稱： 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 課程設(shè)計(jì)題目： 稀疏矩陣相關(guān)操作的實(shí)現(xiàn) 完 成 期 限：自 2013年 9月9日至 2013年 9月 22日共 2 周設(shè)計(jì)內(nèi)容：1.任務(wù)說明用C/C+編寫一個(gè)程序?qū)崿F(xiàn)稀疏矩陣相關(guān)操作。2.要求1）闡述設(shè)計(jì)思想，畫出流程圖。2）主要功能： （1）輸入相關(guān)數(shù)據(jù)建立稀疏矩陣； （2）實(shí)現(xiàn)稀疏矩陣轉(zhuǎn)置； （3）實(shí)現(xiàn)兩個(gè)稀疏矩陣相乘。3）從時(shí)間、

2、空間對算法分析；4）較好的界面設(shè)計(jì)；5）編寫課程設(shè)計(jì)報(bào)告。指導(dǎo)教師：曹陽 教研室負(fù)責(zé)人：曹陽課程設(shè)計(jì)評閱評語： 指導(dǎo)教師簽名： 年 月 日摘 要假設(shè)在m*n的矩陣中，有t個(gè)元素不為零。令a=t/（m*n），稱a為矩陣的稀疏因子，通常認(rèn)為a=0.05時(shí)稱為稀疏矩陣。設(shè)計(jì)了一個(gè)稀疏矩陣相關(guān)操作實(shí)現(xiàn)的軟件，具有實(shí)現(xiàn)矩陣轉(zhuǎn)置和實(shí)現(xiàn)兩個(gè)矩陣相乘的功能。采用三元組順序表法來實(shí)現(xiàn)稀疏矩陣的存儲(chǔ)，操作軟件采用VC+6.0作為軟件開發(fā)的環(huán)境。界面清晰易懂，操作簡單易學(xué)，便于為用戶所接受。關(guān)鍵詞：稀疏矩陣；三元組；VC+6.0；轉(zhuǎn)置；函數(shù)目 錄1 課題描述.12 算法描述.23程序源代碼.4 程序調(diào)試與測試.11

3、5 結(jié)果分析.146 總結(jié).15 參考文獻(xiàn).161 課題描述 設(shè)計(jì)了一個(gè)稀疏矩陣相關(guān)操作實(shí)現(xiàn)的軟件。稀疏矩陣是指假設(shè)在m*n的矩陣中，有t個(gè)元素不為零。令a=t/（m*n），稱a為矩陣的稀疏因子，通常認(rèn)為a=0.05時(shí)稱為稀疏矩陣。軟件具有實(shí)現(xiàn)矩陣轉(zhuǎn)置和實(shí)現(xiàn)兩個(gè)矩相乘的功能，采用三元組順序表法來實(shí)現(xiàn)稀疏矩陣的存儲(chǔ)。操作軟件采用VC+6.0作為軟件開發(fā)的環(huán)境。2 算法描述1) 算法思想 利用稀疏矩陣的非零元少的特點(diǎn)，采用三元組順序表進(jìn)行壓縮存儲(chǔ)。實(shí)現(xiàn)轉(zhuǎn)置是將矩陣的行列值相互交換，將每個(gè)三元組中的i和j相互調(diào)換，重排三元組之間的次序即可實(shí)現(xiàn)矩陣的轉(zhuǎn)置。兩個(gè)矩陣相乘是對于M中每個(gè)元素M.datap(

4、p=1,2,.M.tu)，找到N中所有滿足條件M.datap.j=N.dataq.i的元素N.dataq，求得M.datap.v和N.dataq.v的乘積，乘積矩陣Q中每個(gè)元素的值是個(gè)累積和，為了便于操作，應(yīng)對每個(gè)元素設(shè)一累積和的變量，其初值為零，然后掃描數(shù)組M，求得相應(yīng)元素的乘積并累加到適當(dāng)?shù)那罄塾?jì)的變量上。測試矩陣M、N如圖2-1所示： M N 0 2 0 0 0 5 0 1 2 0 0 3 圖2-1 測試矩陣 2） 算法流程圖 主函數(shù)流程圖如圖2-2所示： 開始調(diào)用菜單函數(shù)輸入mm?調(diào)用Print()調(diào)用轉(zhuǎn)置函數(shù)調(diào)用相乘函數(shù)有誤 1 2 3 4 default 轉(zhuǎn)下頁調(diào)用Print()調(diào)

5、用Print() 結(jié)束 接上頁 圖 2-2 主函數(shù)流程圖稀疏矩陣轉(zhuǎn)置流程圖如圖2-3所示：Col=M.nu?Numcol=0+Col t=1開始T.mu=M.nuT.nu=M.muT.tu=M.tuT.tu=0?Col=1是 否否 是 接下頁 接上頁t=M.tu?否 +t+numM.datat.j 是Cpot1=1Col=2Col=M.nu?否 +Col 是 Cpotcol=Cpotcol-1+numcol-1 P=1P=M.tu?否 +p 是Col=M.datap.j;q=Cpotcol;T.dataq.i=M.datap.j;T.dataq.j=M.datap.i;T.dataq.e=M.

6、datap.e;+Cpotcol; 結(jié)束 圖 2-3 矩陣轉(zhuǎn)置流程圖矩陣相乘流程圖如圖2-4所示：3程序源代碼#include#define MAXSIZE 100typedef structint i,j; int e;Triple;typedef structTriple dataMAXSIZE+1; int mu,nu,tu;TSMatrix;int GreatSMatrix(TSMatrix &M)int MaMAXSIZE/2MAXSIZE/2; int i,j;M.tu=0;printf(請輸入矩陣的行、列數(shù)（中間用逗號隔開）：);scanf(%d,%d,&M.mu,&M.nu);

7、printf(請輸入數(shù)據(jù):);for(i=1;i=M.mu;i+)for(j=1;j=M.nu;j+)scanf(%d,&Maij);for(i=1;i=M.mu;i+)for(j=1;j0.05) return 0;return 1;int FastTransposeSMatrix(TSMatrix M,TSMatrix &T)/轉(zhuǎn)置int p,q,col,t,numMAXSIZE+1,cpotMAXSIZE+1;T.mu=M.nu; T.nu=M.mu; T.tu=M.tu;if(T.tu)for(col=1;col=M.nu;+col)numcol=0;for(t=1;t=M.tu;+t

8、)+numM.datat.j;cpot1=1;for(col=2;col=M.nu;+col)cpotcol=cpotcol-1+numcol-1;for(p=1;p=M.tu;+p)col=M.datap.j; q=cpotcol; T.dataq.i=M.datap.j; T.dataq.j=M.datap.i; T.dataq.e=M.datap.e; +cpotcol;return 1;void print(TSMatrix M)/顯示int i,j,k=1;printf(該稀疏矩陣為n);for(i=1;i=M.mu;i+)for(j=1;j=M.nu;j+)if(i=M.datak

9、.i&j=M.datak.j) printf(%3d ,M.datak.e);+k;else printf(%3d ,0);printf(n);printf(矩陣中存儲(chǔ)的數(shù)據(jù)為: );for(i=1;i=M.tu;+i)printf(%d,%d,%d),M.datai.i,M.datai.j,M.datai.e);if(iM.tu) printf(,);printf(n);int MultSMatrix(TSMatrix M,TSMatrix N,TSMatrix &Q)int i,j,k=1,q=1;int MaMAXSIZE/2MAXSIZE/2=0;int NaMAXSIZE/2MAXS

10、IZE/2=0;int QaMAXSIZE/2MAXSIZE/2;if(M.nu!=N.mu)printf(這兩個(gè)矩陣不能相乘!n);return 0; Q.mu=M.mu; Q.nu=N.nu; Q.tu=0;for(i=1;i=MAXSIZE/2;i+)for(j=1;j=MAXSIZE/2;j+)if(i=M.datak.i&j=M.datak.j) Maij=M.datak.e;+k;/else Maij=0; if(i=N.dataq.i&j=N.dataq.j) Naij=N.dataq.e;+q;/else Naij=0;for(i=1;i=M.mu;+i)for(j=1;j=N

11、.nu;+j)Qaij=0;for(k=1;k=M.nu;+k)Qaij+=Maik*Nakj;for(i=1;i=Q.mu;i+)for(j=1;j=Q.nu;j+)if(Qaij!=0) Q.tu+;Q.dataQ.tu.i=i;Q.dataQ.tu.j=j;Q.dataQ.tu.e=Qaij;return 1;void caidan()printf(、創(chuàng)建矩陣n);printf(、矩陣轉(zhuǎn)置n);printf(、矩陣相乘n);printf(、退出n);void main()TSMatrix M,N,P,Q;int m;M.tu=0;caidan();while(1)printf(請選擇：)

12、;fflush(stdin);scanf(%d,&m);switch(m)case 1:if(GreatSMatrix(M)=0) printf(該矩陣不是稀疏矩陣！n); break; printf(已成功創(chuàng)建矩陣！n);print(M);break;case 2:if(M.tu=0) printf(矩陣不存在！n); break; FastTransposeSMatrix(M,N);printf(轉(zhuǎn)置矩陣為：n);print(N);break;case 3:if(M.tu=0) GreatSMatrix(M);GreatSMatrix(P);MultSMatrix(M,P,Q);print

13、f(相乘后的矩陣為：n);print(Q);break;case 4:return;default:printf(輸入有誤，請重新輸入：);4 調(diào)試與測試1）運(yùn)行初始界面如圖4-1所示： 圖4-1 初始界面2）選擇1，創(chuàng)建矩陣M，運(yùn)行界面如圖4-2所示：圖4-2 M矩陣創(chuàng)建界面2） 選擇2，實(shí)現(xiàn)矩陣M的轉(zhuǎn)置，運(yùn)行界面如圖4-3所示：圖4-3 M矩陣轉(zhuǎn)置界面3） 選擇3，實(shí)現(xiàn)矩陣M和矩陣N的相乘，運(yùn)行界面如圖4-4所示： 圖4-4 M*N矩陣界面4） 選擇4，程序結(jié)束退出，運(yùn)行界面如圖4-5所示： 圖4-5 退出程序界面 5 結(jié)果分析 在輸入的過程中，如果輸入的不是稀疏矩陣，則系統(tǒng)就會(huì)提示：該矩陣不是稀疏矩陣！則需要重新輸入。在選擇兩個(gè)矩陣相乘時(shí)，有一個(gè)輸入的不是稀疏矩陣，系統(tǒng)會(huì)提示：該矩陣不能相乘！不滿足兩矩陣相乘條件是也會(huì)提示：該矩陣不能相乘！ 6 總結(jié) 設(shè)計(jì)了一個(gè)稀疏矩陣相關(guān)操作實(shí)現(xiàn)的軟件。軟件具有實(shí)現(xiàn)矩陣轉(zhuǎn)置和實(shí)現(xiàn)兩個(gè)矩相乘的功能， 利用稀疏矩陣的非零元少的特點(diǎn)，采用三元組順序表進(jìn)行壓縮存儲(chǔ)。操作軟件采用VC+6.0作為軟件開發(fā)的環(huán)境。在運(yùn)行調(diào)試過程中，出現(xiàn)了個(gè)各種問題，對于函數(shù)調(diào)用不夠運(yùn)用熟悉，對于相乘矩陣實(shí)現(xiàn)過程不夠了解，編程的過程同樣是對這些知識的再一次學(xué)習(xí)和加深印象，更多的由于很