數(shù)據(jù)結(jié)構(gòu)與課程設(shè)計(jì)---稀疏矩陣

1、<p>　　實(shí)驗(yàn)課程名稱(chēng) 數(shù)據(jù)結(jié)構(gòu)與課程設(shè)計(jì) </p><p>　　專(zhuān) 業(yè) 班 級(jí) 10級(jí)計(jì)科（2）班 </p><p>　　學(xué) 生 姓 名 </p><p>　　學(xué) 號(hào) </

2、p><p>　　指 導(dǎo) 教 師 </p><p>　　2012 至 2013學(xué)年第 1 學(xué)期第 4 至 5 周</p><p><b>　　目錄</b></p><p><b>　　1 概述1</b></p><p><

3、b>　　1 系統(tǒng)分析1</b></p><p>　　2.1設(shè)計(jì)函數(shù)建立稀疏矩陣及初始化值和輸出稀疏矩陣的值1</p><p>　　2.2造函數(shù)并輸出最終稀疏矩陣1</p><p><b>　　3 概要設(shè)計(jì)1</b></p><p>　　3.1存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)1</p><p&g

4、t;　　3.2系統(tǒng)功能設(shè)計(jì)1</p><p><b>　　4 詳細(xì)設(shè)計(jì)2</b></p><p>　　4.1 稀疏矩陣的存儲(chǔ)2</p><p>　　4.2 稀疏矩陣的加法2</p><p><b>　　5 程序代碼4</b></p><p><b>　　6

5、 運(yùn)行與測(cè)試7</b></p><p><b>　　7 總結(jié)與心得7</b></p><p><b>　　8 參考文獻(xiàn)7</b></p><p><b>　　1 概述</b></p><p>　　掌握稀疏矩陣的加法運(yùn)算，稀疏矩陣的存儲(chǔ)方法，每一個(gè)元素可能有多個(gè)

6、直接前驅(qū)和多個(gè)直接后繼。一般情況下都是采用順序存儲(chǔ)方法來(lái)表示數(shù)組，但有時(shí)在實(shí)際應(yīng)用中，一般的順序存儲(chǔ)方法已經(jīng)不太實(shí)用。有時(shí)候用普通存儲(chǔ)方法就會(huì)造成很大的空間浪費(fèi)。為了節(jié)省存儲(chǔ)單元，用壓縮方法只存儲(chǔ)非零元素。</p><p><b>　　2 系統(tǒng)分析</b></p><p>　　2.1設(shè)計(jì)函數(shù)建立稀疏矩陣及初始化值和輸出稀疏矩陣的值 </p><p&

7、gt;　　本模塊要求設(shè)計(jì)函數(shù)建立稀疏矩陣并初始化。在創(chuàng)建稀疏矩陣時(shí)需要設(shè)計(jì)稀疏矩陣的加法和存儲(chǔ)方法，出現(xiàn)錯(cuò)誤時(shí)能夠?qū)﹀e(cuò)誤進(jìn)行判別處理初始化稀疏矩陣都為空值。在設(shè)計(jì)輸出稀疏矩陣的值的函數(shù)時(shí)也要針對(duì)兩種不同的情況分別編制函數(shù)才能準(zhǔn)確的輸出稀疏矩陣。在對(duì)稀疏矩陣進(jìn)行初始化時(shí)只輸入非零元素的值和它所在的所在行及所在列。在對(duì)稀疏矩陣輸出時(shí)以矩陣的完整形式輸出。 </p><p>　　2.2造函數(shù)并輸出最終稀疏矩陣 <

8、;/p><p>　　本模塊要求設(shè)計(jì)加法函數(shù)對(duì)兩個(gè)矩陣進(jìn)行運(yùn)算并輸出最終的稀疏矩陣，操作后的結(jié)果矩陣的行、列數(shù)需要綜合多方面情況來(lái)確定。這些函數(shù)也是整個(gè)程序的難點(diǎn)需要靈活運(yùn)用數(shù)組及指針的特點(diǎn)。</p><p><b>　　3 概要設(shè)計(jì)</b></p><p><b>　　3.1存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)</b></p><

9、p>　　以一維數(shù)組順序存放非零元素的行號(hào)、列號(hào)和數(shù)值，行號(hào)-1作為結(jié)束標(biāo)志。稀疏矩陣的存儲(chǔ)類(lèi)似于建立順序存儲(chǔ)稀疏矩陣的三元組表。假設(shè)A為一個(gè)稀疏矩陣，B為一個(gè)存儲(chǔ)對(duì)應(yīng)于A矩陣生成的數(shù)組。用一個(gè)二重循環(huán)來(lái)判斷每個(gè)矩陣元素是否為零，若不為零，則將其行、列下標(biāo)及其值存入到一維數(shù)組B中對(duì)應(yīng)的元素中。</p><p>　　3.2系統(tǒng)功能設(shè)計(jì) </p><p>　　設(shè)計(jì)稀疏矩陣的加法算法，假設(shè)兩

10、個(gè)稀疏矩陣A和B，它們均為m行n列，分別存放在數(shù)組A和B中，編寫(xiě)矩陣的加法實(shí)現(xiàn)C=A+B的算法，C矩陣存放在數(shù)組C中。根據(jù)設(shè)計(jì)要求，首先要將一個(gè)稀疏矩陣對(duì)應(yīng)存儲(chǔ)到一個(gè)一維數(shù)組中，然后在進(jìn)行矩陣加法時(shí)依次掃描矩陣A和B的行列值，并以行優(yōu)先，當(dāng)行列相同時(shí)，將第三個(gè)元素值相加的和以及行列號(hào)三個(gè)元素存入結(jié)果數(shù)組C中；不相同時(shí)，將A或B的三個(gè)元素直接存入結(jié)果數(shù)組中。</p><p><b>　　4 詳細(xì)設(shè)計(jì)<

11、;/b></p><p>　　4.1 稀疏矩陣的存儲(chǔ)</p><p>　　void(CreateMatrix(int A[m][n],int B[50])) //轉(zhuǎn)儲(chǔ)稀疏矩陣的算法</p><p>　　{ int i,j,k=0;</p><p>　　for(i=0;i<m;i++) </p><p>

12、　　for(j=0;j<n;j++) </p><p>　　if(A[i][j]!=0) {</p><p>　　B[k]=i;k++;</p><p>　　B[k]=j;k++;</p><p>　　B[k]=A[i][j];k++;</p><p><b>　　}</b></p&

13、gt;<p>　　B[k]=-1; //非零元素存儲(chǔ)結(jié)束</p><p><b>　　}</b></p><p>　　4.2 稀疏矩陣的加法</p><p>　　void MatrixAdd(int A[max],int B[max],int C[max])</p><p><b>　　

14、{</b></p><p>　　int i=0,j=0,k=0;</p><p>　　while(A[i]!=-1 && B[j]!=-1) </p><p><b>　　{</b></p><p>　　if(A[i]==B[j]) //行相等</p><p>&

15、lt;b>　　{</b></p><p>　　if(A[i+1]==B[j+1]) //列相等</p><p><b>　　{</b></p><p>　　C[k]=A[i];</p><p>　　C[k+1]=A[i+1];</p><p>　　C[k+2]=A[i+2]-B

16、[j+2];</p><p><b>　　k=k+3;</b></p><p><b>　　i=i+3;</b></p><p><b>　　j=j+3;</b></p><p><b>　　}</b></p><p>　　else

17、 if(A[i+1]<B[j+1]) </p><p>　　{ //B的列小于A的列，將A的三個(gè)元素直接存入C中</p><p>　　C[k]=A[i];</p><p>　　C[k+1]=A[i+1];</p><p>　　C[k+2]=A[i+2];</p><p><b>　　k=k+3;&l

18、t;/b></p><p><b>　　i=i+3;</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p>　　{ //B的列小于A的列，將B的三個(gè)元素直接存入C中</p><p>　　C[

19、k]=B[j];</p><p>　　C[k+1]=B[j+1];</p><p>　　C[k+2]=B[j+2];</p><p><b>　　k=k+3;</b></p><p><b>　　j=j+3;</b></p><p><b>　　}</b>

20、;</p><p><b>　　}</b></p><p>　　else if(A[i]<B[j])</p><p>　　{ //A的行小于B的行，將A的三個(gè)元素直接存入C中</p><p>　　C[k]=A[i];</p><p>　　C[k+1]=A[i+1];</p>

21、<p>　　C[k+2]=A[i+2];</p><p><b>　　k=k+3;</b></p><p><b>　　i=i+3;</b></p><p><b>　　}</b></p><p><b>　　else</b></p>

22、<p>　　{ //B的行小于A的行，將B的三個(gè)元素直接存入C中</p><p>　　C[k]=B[j];</p><p>　　C[k+1]=B[j+1];</p><p>　　C[k+2]=B[j+2];</p><p><b>　　k=k+3;</b></p><p><

23、b>　　j=j+3;</b></p><p><b>　　}</b></p><p><b>　　} //循環(huán)結(jié)束</b></p><p>　　if(A[i]==-1)</p><p>　　while(B[j]!=-1)</p><p>　　{ //A結(jié)束

24、B還有元素，將B的所有元素直接存入C中</p><p>　　C[k]=B[j];</p><p>　　C[k+1]=B[j+1];</p><p>　　C[k+2]=B[j+2];</p><p><b>　　k=k+3;</b></p><p><b>　　j=j+3;</b&g

25、t;</p><p><b>　　}</b></p><p><b>　　else</b></p><p>　　while(A[i]!=-1)</p><p>　　{ //B結(jié)束A還有元素，將A的所有元素直接存入C中</p><p>　　C[k]=A[i];</p&g

26、t;<p>　　C[k+1]=A[i+1];</p><p>　　C[k+2]=A[i+2];</p><p><b>　　k=k+3;</b></p><p><b>　　i=i+3;</b></p><p><b>　　}</b></p><

27、;p><b>　　C[k]=-1;</b></p><p><b>　　}</b></p><p><b>　　5 程序代碼</b></p><p>　　#include<stdio.h></p><p>　　#define m 3 //用戶可根據(jù)需要定義

28、原始矩陣行數(shù)</p><p>　　#define n 3 //定義原始矩陣</p><p>　　#define max 50</p><p>　　void(CreateMatrix(int A[m][n],int B[50])) //轉(zhuǎn)儲(chǔ)稀疏矩陣的算法</p><p>　　{ int i,j,k=0;</p><p&

29、gt;　　for(i=0;i<m;i++) </p><p>　　for(j=0;j<n;j++) </p><p>　　if(A[i][j]!=0) {</p><p>　　B[k]=i;k++;</p><p>　　B[k]=j;k++;</p><p>　　B[k]=A[i][j];k++;<

30、;/p><p><b>　　}</b></p><p>　　B[k]=-1; //非零元素存儲(chǔ)結(jié)束</p><p><b>　　}</b></p><p>　　void MatrixAdd(int A[max],int B[max],int C[max])</p><p&g

31、t;<b>　　{</b></p><p>　　int i=0,j=0,k=0;</p><p>　　while(A[i]!=-1 && B[j]!=-1) </p><p><b>　　{</b></p><p>　　if(A[i]==B[j]) //行相等</p>

32、;<p><b>　　{</b></p><p>　　if(A[i+1]==B[j+1]) //列相等</p><p><b>　　{</b></p><p>　　C[k]=A[i];</p><p>　　C[k+1]=A[i+1];</p><p>　　C[

33、k+2]=A[i+2]-B[j+2];</p><p><b>　　k=k+3;</b></p><p><b>　　i=i+3;</b></p><p><b>　　j=j+3;</b></p><p><b>　　}</b></p>&l

34、t;p>　　else if(A[i+1]<B[j+1]) </p><p>　　{ //B的列小于A的列，將A的三個(gè)元素直接存入C中</p><p>　　C[k]=A[i];</p><p>　　C[k+1]=A[i+1];</p><p>　　C[k+2]=A[i+2];</p><p><b&

35、gt;　　k=k+3;</b></p><p><b>　　i=i+3;</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p>　　{ //B的列小于A的列，將B的三個(gè)元素直接存入C中</p>

36、<p>　　C[k]=B[j];</p><p>　　C[k+1]=B[j+1];</p><p>　　C[k+2]=B[j+2];</p><p><b>　　k=k+3;</b></p><p><b>　　j=j+3;</b></p><p><b>

37、;　　}</b></p><p><b>　　}</b></p><p>　　else if(A[i]<B[j])</p><p>　　{ //A的行小于B的行，將A的三個(gè)元素直接存入C中</p><p>　　C[k]=A[i];</p><p>　　C[k+1]=A[i+1]

38、;</p><p>　　C[k+2]=A[i+2];</p><p><b>　　k=k+3;</b></p><p><b>　　i=i+3;</b></p><p><b>　　}</b></p><p><b>　　else</b&

39、gt;</p><p>　　{ //B的行小于A的行，將B的三個(gè)元素直接存入C中</p><p>　　C[k]=B[j];</p><p>　　C[k+1]=B[j+1];</p><p>　　C[k+2]=B[j+2];</p><p><b>　　k=k+3;</b></p>

40、<p><b>　　j=j+3;</b></p><p><b>　　}</b></p><p><b>　　} //循環(huán)結(jié)束</b></p><p>　　if(A[i]==-1)</p><p>　　while(B[j]!=-1)</p><p

41、>　　{ //A結(jié)束B(niǎo)還有元素，將B的所有元素直接存入C中</p><p>　　C[k]=B[j];</p><p>　　C[k+1]=B[j+1];</p><p>　　C[k+2]=B[j+2];</p><p><b>　　k=k+3;</b></p><p><b>　　j

42、=j+3;</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p>　　while(A[i]!=-1)</p><p>　　{ //B結(jié)束A還有元素，將A的所有元素直接存入C中</p><p>　　C[k]=

43、A[i];</p><p>　　C[k+1]=A[i+1];</p><p>　　C[k+2]=A[i+2];</p><p><b>　　k=k+3;</b></p><p><b>　　i=i+3;</b></p><p><b>　　}</b>&l

44、t;/p><p><b>　　C[k]=-1;</b></p><p><b>　　}</b></p><p>　　void main()</p><p><b>　　{</b></p><p>　　int E[m][n],F[m][n],A[max],B[

45、max],C[max];</p><p>　　int i,j,k;</p><p>　　for(i=0;i<m;i++) //輸入E矩陣的所有元素</p><p>　　for(j=0;j<n;j++)</p><p>　　scanf("%d",&E[i][j]);</p><p&g

46、t;　　for(i=0;i<m;i++) //輸入F元素的所有元素</p><p>　　for(j=0;j<n;j++)</p><p>　　scanf("%d",&F[i][j]);</p><p>　　CreateMatrix(E,A); //E矩陣的非零元素存儲(chǔ)到一維數(shù)組A中</p><p>

47、　　CreateMatrix(F,B); //F矩陣的非零元素存儲(chǔ)到一維數(shù)組B中</p><p>　　MatrixAdd(A,B,C); //A,B相加存入C中</p><p>　　i=0;j=0;k=0;</p><p>　　printf("A數(shù)組內(nèi)容如下：\n");</p><p>　　while(A[i]!=-

48、1)</p><p>　　{ //輸出A中內(nèi)容</p><p>　　printf("%5d,%5d,%5d\n",A[i],A[i+1],A[i+2]);</p><p><b>　　i=i+3;</b></p><p><b>　　}</b></p><

49、p>　　printf("B數(shù)組內(nèi)容如下：\n");</p><p>　　while(B[j]!=-1)</p><p>　　{ //輸出B中內(nèi)容</p><p>　　printf("%5d,%5d,%5d\n",B[j],B[j+1],B[j+2]);</p><p><b>　　j=

50、j+3;</b></p><p><b>　　}</b></p><p>　　printf("C數(shù)組內(nèi)容如下：\n");</p><p>　　while(C[k]!=-1)</p><p>　　{ //輸出C中內(nèi)容</p><p>　　printf("

51、%5d,%5d,%5d\n",C[k],C[k+1],C[k+2]);</p><p><b>　　k=k+3;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　6 運(yùn)行與測(cè)試</b&

52、gt;</p><p><b>　　7 總結(jié)與心得</b></p><p>　　在本次實(shí)驗(yàn)中遇到了很多問(wèn)題，一開(kāi)始的時(shí)候程序有很多錯(cuò)誤，花了很多時(shí)間才調(diào)試成功。慢慢的把一些錯(cuò)誤找出來(lái)并改正了。我認(rèn)為學(xué)習(xí)最重要的是發(fā)現(xiàn)問(wèn)題，解決問(wèn)題。自己解決不了的和同學(xué)一起解決，這樣才能學(xué)到更多東西。本次試驗(yàn)讓我對(duì)稀疏矩陣的認(rèn)識(shí)進(jìn)一步加深了。</p><p>&