數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告--稀疏矩陣運算器

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數(shù)：15 大小：172.00KB 人氣指數(shù)：12 舉報 版權(quán)申訴

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告--稀疏矩陣運算器_第1頁

已閱讀1頁，還剩14頁未讀，繼續(xù)免費閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進行舉報或認領(lǐng)

文檔簡介

1、　　數(shù)據(jù)結(jié)構(gòu)　　課程設(shè)計報告　　題目：稀疏矩陣運算器 　　院系：計算機科學(xué)系 　　專業(yè)班級：10計算機科學(xué)與技術(shù)（網(wǎng)絡(luò)工程）<

2、;p>　　學(xué) 號： 　　學(xué)生姓名： 　　指導(dǎo)教師： 　　2011年12月23 日　　目錄：　　1、分析問題和

3、確定解決方案 ………………………… 3 　　1.1問題描述 …………………………… 3 　　1.2 輸入的形式和輸入值的范圍 …………………… 3　　1.3 輸出的形式 ……………………………… 3　　1.4 程序所能達到的功

4、能 …………………………… 3　　1.5 測試數(shù)據(jù) ……………………………… 3　　1.6 確定解決方案 ……………………………… 4　　1.7所有抽象數(shù)據(jù)類型的定義 …………………………… 4　　2、詳細設(shè)計

5、 …………………………… 5　　2.1稀疏矩陣加法運算思路 …………………………… 5　　2.2稀疏矩陣減法運算思路 ……………………………… 7　　2.3稀疏矩陣乘法運算思路……………………………… 9　　2.4創(chuàng)建稀疏矩陣 …………………

6、…………… 11　　3、系統(tǒng)調(diào)試與測試 …………………………… 12　　3.1程序的菜單界面 ……………………………… 12　　3.2 實現(xiàn)加法運算 ……………………………… 12　　3.3 實現(xiàn)減法運算 …………………

7、…………… 13　　3.4實現(xiàn)乘法運算 ……………………………… 14　　4、結(jié)果分析 …………………………………… 15　　4.1、算法的時空分析 ……………………………… 15　　4.2、經(jīng)驗和體會 ………………

8、……………… 15　　5、參考文獻 ……………………………… 15　　1、分析問題和確定解決方案　　1.1問題描述　　稀疏矩陣是指那些多數(shù)元素為零的矩陣。利用“稀疏”特點進行存儲和計算可以大大節(jié)省存儲空間，提高

9、計算效率。實現(xiàn)一個能進行稀疏矩陣基本運算的運算器。用三元組實現(xiàn)稀疏矩陣的相加、相減，相乘；　　1.2輸入的形式和輸入值的范圍　　以三元組的形式輸入，首先應(yīng)輸入矩陣的行數(shù)和列數(shù)，并判別給出的兩個矩陣的行、列數(shù)對于所要求作的運算是否相匹配?？稍O(shè)矩陣的行數(shù)和列數(shù)均不超過20；　　例如：輸入的三元組為：((1,1,10)

10、,(2,3,9),(3,1,-1))其對應(yīng)的稀疏矩陣為：　　1.3 輸出的形式　　運算結(jié)果的矩陣以通常的陣列形式輸出；　　1.4程序所能達到的功能　　該程序可以實現(xiàn)以三元組形式輸入兩個矩陣，求出兩個矩陣的和、差、積；并可根據(jù)輸入的矩陣

11、的行列數(shù)不同判別是否可以進行相加、減、乘，并重新輸入正確的矩陣；　　1.5測試數(shù)據(jù)　　測試的數(shù)據(jù)及其結(jié)果如下：　　矩陣M 矩陣N 矩陣Q　　加法：</

12、p>　　+ = 　　減法：　　- = 　　乘法：　　X = <

13、;/p>　　1.6 確定解決方案　　進入運算器界面后選擇要實行的操作，按1實現(xiàn)矩陣相加，調(diào)用函數(shù)AddSMatrix，若輸入的兩個矩陣行列數(shù)不相等，則提示輸入錯誤，重新輸入矩陣進行加法運算；按2實現(xiàn)矩陣相乘，若輸入的第一矩陣的列數(shù)不等于第二個矩陣的行數(shù)，則提示輸入錯誤，重新輸入矩陣進行乘法運算；按3實現(xiàn)矩陣相減，若輸入的兩個矩陣行列數(shù)不相等，則提示輸入錯誤，重新輸入矩

14、陣進行減法運算；按4退出程序 　　以加法為例實現(xiàn)運算過程，如下：(稀疏矩陣的和為Q)　　第一個稀疏矩陣M的三元組為（（1,1,10）,(2,3,9),(3,1,-1)）　　第二個稀疏矩陣N的三元組為（（2,3,-1）,（3,1,1）,（3,3,-3））　　M的第一個三元

15、組（1,1,10）與N的第一個三元組（2,3,-1）比較，因行數(shù)1<2則Q得到第一個三元組（1,1,10）；M的第二個三元組與N的第一個三元組比較，因?qū)?yīng)行列數(shù)相等則9+（-1）=8，次行列數(shù)就是Q的行列數(shù)即得到Q的第二個三元組為（2,3,8）;M第三個三元組(3,1,-1)）與N的第二個三元組進行比較，因?qū)?yīng)行列數(shù)相等，且1+（-1）=0，則不進行相加；而此時只有 N的第三個三元組（3,3,-3）符合條件，則Q得到第三個三元組（

16、3,3,-3）；最終結(jié)果為　　(（1,1,10）,(2,3,8）,(3,3,-3）)　　1.7所有抽象數(shù)據(jù)類型的定義　　以順序存儲結(jié)構(gòu)來表示三元組表，則可得到稀疏矩陣的一種壓縮存儲方式——三元組順序表。　　/* 稀疏矩陣的三元組順序表存儲表示 */

17、　　#define MAXSIZE 1000 //假設(shè)非零元個數(shù)的最大值為1000　　typedef struct　　{int i,j; //該非零元的行下標和列下標　　ElemType e; //該非零元數(shù)值　　} Triple;

18、　　typedef struct　　{ Triple data[MAXSIZE+1]; // 非零三元組表，data[0]未用　　int mu,nu,tu; //矩陣的行數(shù)(<20)、列數(shù)(<20)和非零元個數(shù)　　} TS

19、Matrix;　　在此，data域中表示非零元得三元組是以行序為主序順序排列的，這樣有利于進行某些矩陣運算。　　抽象數(shù)據(jù)類型稀疏矩陣的定義如下：　　ADT SparseMatrix{　　數(shù)據(jù)對象:D={aij|i=1,2,3,…，m;j=1,2,…，n;

20、;　　Aij(-ElemSet,m和n分別稱為矩陣的行數(shù)和列數(shù)}　　數(shù)據(jù)關(guān)系：R={Row,Col}　　基本操作：　　CreateSMatrix(&M);　　操作結(jié)果：創(chuàng)建稀疏矩陣M。

21、　　PrintSMatrix(M);　　初始條件：稀疏矩陣M存在。　　操作結(jié)果：輸出稀疏矩陣M。　　AddSMatrix(M,N,&Q);　　初始條件：稀疏矩陣M和N的的行數(shù)和列數(shù)對應(yīng)相等。　　操作結(jié)

22、果：求稀疏矩陣的和Q=Ｍ＋Ｎ。　　SubSMatrix(M,N,&Q);　　初始條件：稀疏矩陣M和N的的行數(shù)和列數(shù)對應(yīng)相等。　　操作結(jié)果：求稀疏矩陣的差Q=M-N。　　MultSMatrix(M,N,&Q);　　初

23、始條件：稀疏矩陣M的列數(shù)等于N的行數(shù)。　　操作結(jié)果：求稀疏矩陣的積Q=M X N。　　}ADT SpareMatrix　　此流程表示的是主程序的流程以及各程序模塊之間的層次(調(diào)用)關(guān)系。　　2、詳細設(shè)計<

24、p>　　2.1稀疏矩陣的加法運算思路　　比較滿足條件(行數(shù)及列數(shù)都相同的兩個矩陣)的兩個稀疏矩陣中不為0的元素的行數(shù)及列數(shù)（即i與j），將i與j都相等的前后兩個元素值e相加，保持i,j不變儲存在新的三元組中，不等的則分別儲存在此新三元組中。最后得到的這個新三元組表就是兩個矩陣的和矩陣的三元組表。其算法如下：　　Status AddSMatrix(T

25、SMatrix M, TSMatrix N, TSMatrix &Q)　　{ 　　if(M.mu==N.mu&&M.nu==N.nu) //行數(shù),列數(shù)相等才能相加　　{

26、;　　Q.mu=M.mu;　　Q.nu=N.nu;　　int p,q,k;　　p=1;　　q=1;　　k=1;<

27、;/p>　　while(p<=M.tu&&q<=N.tu) //兩個稀疏矩陣存在　　{　　if(M.data[p].i==N.data[q].i)//兩個稀疏矩陣的行數(shù)相等　　{&

28、lt;/p>　　if(M.data[p].j==N.data[q].j) //兩個稀疏矩陣的列數(shù)相等　　{　　if(M.data[p].e+N.data[q].e!=0) //兩個稀疏矩陣相加的結(jié)果不為0（三元組表）　　{

29、　　Q.data[k].i=M.data[p].i;　　Q.data[k].j=M.data[p].j;　　Q.data[k].e=M.data[p].e+N.data[q].e;　　++k;

30、　　}　　++q;　　++p;　　}　　else if(M.data[p].j<N.data

31、[q].j) 　　//第一個稀疏矩陣列數(shù)小于第二個稀疏矩陣列數(shù)　　{　　Q.data[k]=M.data[p]; 　　//把M中的所有信息都賦給Q　　++p;</

32、b>　　++k;　　}　　else 　　//第一個稀疏矩陣列數(shù)大于第二個稀疏矩陣的列數(shù)　　{

33、　　Q.data[k]=N.data[q];　　++q;　　++k;　　}

34、}　　else if(M.data[p].i<N.data[q].i) 　　//第一個稀疏矩陣行列數(shù)小于第二個稀疏矩陣行數(shù)　　{　　Q.data[k]=M.data[p];<p

35、>　　++p;　　++k;　　}　　else 　　//第一個稀疏矩陣行列數(shù)小于第二個稀疏矩陣行數(shù)</p&g

36、t;　　{　　Q.data[k]=N.data[q];　　++q;　　++k;　　}</p&

37、gt;　　}　　while(p<=M.tu) //只有M并且符合條件　　{　　Q.data[k]=M.data[p];　　++p;

38、;　　++k;　　}　　while(q<=N.tu) //只有N并且符合條件　　{　　Q.data[k]=N

39、.data[q];　　++q;　　++k;　　}　　Q.tu=k-1;　　pr

40、intf("\t\t*** *** 兩個矩陣的加法結(jié)果為 *** ***\n");　　return OK;　　}　　else 　　{<

41、;/p>　　printf("兩個矩陣行,列數(shù)不等，出錯了\n");　　CreateSMatrix(M);　　printf("第一個矩陣為:\n");　　PrintSMatrix(M);　　CreateSM

42、atrix(N);　　printf("第二個矩陣為:\n");　　PrintSMatrix(N);　　printf("\n"); 　　AddSMatrix(M,N,Q);

43、　} 　　}　　2.2稀疏矩陣相減的算法思路　　此思路與稀疏矩陣相加的算法思路相同，其算法如下：　　Status SubtMatrix(TSMatrix M, TSMatrix N,TSMatrix &Q

44、)　　{　　if(M.mu==N.mu && M.nu==N.nu) //行數(shù)，列數(shù)相等才能相減　　{　　Q.mu=M.mu;

45、　　Q.nu=N.nu;　　int p,q,k;　　p=1; //M的第p個三元組　　q=1; //N的第q個三元組　　k=1; //Q的第k個三元組　　while(p<=M.tu&&q<=N.t

46、u) //兩個稀疏矩陣存在　　{　　if(M.data[p].i==N.data[q].i) //兩個稀疏矩陣的行數(shù)相等　　{　　if(M.data[p].j==N.data[q].j)//

47、兩個稀疏矩陣的列數(shù)相等　　{　　if(M.data[p].e-N.data[q].e!=0) 　　//兩個稀疏矩陣相減的結(jié)果不為0　　{　　Q.dat

48、a[k].i=M.data[p].i;　　Q.data[k].j=M.data[p].j;　　Q.data[k].e=M.data[p].e-N.data[q].e;　　++k;　　}</p

49、>　　++q;　　++p;　　}　　else if(M.data[p].j<N.data[q].j) 　　//第一個稀疏矩

50、陣列數(shù)小于第二個稀疏矩陣的列數(shù)　　{ 　　Q.data[k]=M.data[p];　　++p;　　++k;<

51、b>　　}　　else if(M.data[p].j>N.data[q].j)//第一個稀疏矩陣列數(shù)大于第二個稀疏矩陣的列　　{　　Q.data[k].i=N.data[q].i;　　Q.data[k]

52、.j=N.data[q].j;　　Q.data[k].e=-N.data[q].e; //即0-N.data[q].e　　++q;　　++k;　　}</

53、p>　　}　　else if(M.data[p].i<N.data[q].i)//第一個稀疏矩陣行列數(shù)小于第二個稀疏矩陣行數(shù)　　{　　Q.data[k]=M.data[p]; //整個三元組進行復(fù)制&

54、lt;/p>　　++p;　　++k;　　}　　if(M.data[p].i>N.data[q].i)//第一個稀疏矩陣行列數(shù)大于第二個稀疏矩陣行數(shù)

55、　　{　　Q.data[k].i=N.data[q].i;　　Q.data[k].j=N.data[q].j;　　Q.data[k].e=-N.data[q].e; //即0-N.data[q].e<b&g

56、t;　　++q;　　++k;　　}　　}　　while(p<=M.tu) //只有M并且符合條件<p

57、>　　{　　Q.data[k]=M.data[p];　　++p;　　++k;　　}<

58、p>　　while(q<=N.tu) //只有N并且符合條件　　{　　Q.data[k].i=N.data[q].i;　　Q.data[k].j=N.data[q].j;　　Q.data[k].e=-N.data[q].

59、e;　　++q;　　++k;　　}　　Q.tu=k-1;　　printf(&q

60、uot;\t\t*** *** 兩個矩陣的相減結(jié)果為 *** ***\n");　　return OK;　　}　　else　　{

61、;　　printf("兩個矩陣行列數(shù)不等，不能相減，請重新輸入\n");　　CreateSMatrix(M);　　printf("第一個矩陣為:\n");　　PrintSMatrix(M);　　CreateSM

62、atrix(N);　　printf("第二個矩陣為:\n");　　PrintSMatrix(N);　　printf("\n");　　SubtMatrix(M,N,Q);

63、}　　}　　2.3稀疏矩陣相乘的算法思路　　兩個相乘的矩陣為M與N，對M中每個元素M.data[p](p=1,2,…,M.tu),找到N中所有滿足條件M.data[p].j=N.data[q].i的元素N.data[q]，求得M.data[p].v和N.d

64、ata[q].v的乘積，又T(i,j)=∑M(i,k)×N(k,j),乘積矩陣T中每個元素的值是個累計和，這個乘積M.data[p].v×N.data[q].v只是T[i][j]中的一部分。為便于操作，應(yīng)對每個元素設(shè)一累計和的變量，其初值是零，然后掃描數(shù)組M，求得相應(yīng)元素的乘積并累加到適當?shù)那罄塾嫼偷淖兞可?。由于T中元素的行號和M中元素的行號一致，又M中元素排列是以M的行序為主序的，由此可對T進行逐行處理，先求得累計

65、求和的中間結(jié)果（T的一行），然后再壓縮存儲到Q.data中去，其算法如下：　　Status MultSMatrix(TSMatrix M, TSMatrix N, TSMatrix &Q)　　{　　int k1,k2,k3,m;<p&g

66、t;　　Q.mu=M.mu;　　Q.nu=N.nu;　　Q.tu=0;　　if(M.nu==N.mu)　　//第一個矩陣的列數(shù)不等于第二個矩陣的行數(shù)才可以相乘　　{</

67、b>　　for(k1=1;k1<=M.tu;k1++)　　for(k2=1;k2<=N.tu;k2++)　　{　　if(M.data[k1].j==N.data[k2].i)

68、　　//第一個矩陣的列數(shù)不等于第二個矩陣的行數(shù)時相乘　　{　　m=M.data[k1].e*N.data[k2].e;　　if(Q.tu==0)　　//Q中還未有一個非零元時，賦予第一個非零元 <p&g

69、t;　　{　　Q.data[1].e=m;　　Q.data[1].i=M.data[k1].i;　　Q.data[1].j=N.data[k2].j;　　Q.tu++; &

70、lt;p>　　}　　else　　{　　for(k3=1;k3<=Q.tu;k3++)　　{</p&g

71、t;　　if(Q.data[k3].i==M.data[k1].i&&Q.data[k3].j==N.data[k2].j)　　//Q的行等于M的行，Q的列等于N的列時相加　　{　　Q.data[k3].e+=m;//對各個數(shù)相加<

72、/p>　　break;　　}　　}　　if(k3==Q.tu+1) //相加完后成為Q中的三元組　　{</

73、b>　　Q.data[k3].e=m;　　Q.data[k3].i=M.data[k1].i; 　　Q.data[k3].j=N.data[k2].j;　　Q.tu++;

74、;　　}　　}　　}　　}　　printf("\t\t*** *** 兩個矩陣相乘結(jié)果為 *** ***\n");&

75、lt;/p>　　return OK;　　}　　else　　{　　printf("第一個矩陣的列數(shù)不等于第二個矩陣的行

76、數(shù)\n");　　printf("不能相乘，請重新輸入\n");　　CreateSMatrix(M);　　printf("第一個矩陣為:\n");　　PrintSMatrix(M);

77、　　CreateSMatrix(N);　　printf("第二個矩陣為:\n");　　printSMatrix(N);　　printf("\n");　　MultSMatrix(M,N,Q);

78、　　} 　　}　　2.4創(chuàng)建稀疏矩陣　　以三元組表的形式輸入創(chuàng)建稀疏矩陣　　其算法如下：　　St

79、atus CreateSMatrix(TSMatrix &M)　　{　　printf("\t\t*** *** 請輸入您的稀疏矩陣 *** *** \n\n"); 　　do{<

80、;p>　　printf("\t*** *** 請輸入矩陣的行數(shù)，列數(shù)，非零元素個數(shù) *** ***\n");　　printf(" ");　　scanf("%d%d%d",&M.mu,&M.nu,&M.tu);

81、if((M.mu<0||M.mu>20)||(M.nu<0||M.nu>20)||((M.tu/(M.mu*M.nu))>0.05)||((M.tu>M.mu*M.nu)||M.tu>MAXSIZE))　　printf("\n 不滿足，請重新輸入!!\n");　　}while((M.mu<

82、;0||M.mu>20)||(M.nu<0||M.nu>20)||((M.tu/(M.mu*M.nu))>0.05)||((M.tu>M.mu*M.nu)||M.tu>MAXSIZE));　　for(int k=1;k<=M.tu;k++)　　{<

83、;p>　　do{　　printf("\t*** *** 請輸入非零元素的行數(shù)i，列數(shù)j，數(shù)值v *** ***\n");　　printf(" ");scanf("%d%d%d",&M.da

84、ta[k].i,&M.data[k].j,&M.data[k].e); if((M.data[k].i<0||M.data[k].i>M.mu)||(M.data[k].j<0||M.data[k].j>M.nu)||(M.data[k].e==0))　　printf("\n 不滿足，請重新輸入!\n");

85、　　} while((M.data[k].i<0||M.data[k].i>M.mu)||(M.data[k].j<0||M.data[k].j>M.nu)||(M.data[k].e==0));　　}　　return OK;<

86、b>　　}　　3、系統(tǒng)調(diào)試與測試　　3.1程序的菜單界面如下：　　3.2實現(xiàn)加法運算：　　3.3實現(xiàn)減法運算：　　3.4實現(xiàn)乘法運算：<

87、p>　　當在調(diào)試程序過程中遇到有錯誤的時候，先試著進行調(diào)試，找出不應(yīng)該有得小錯誤，同時參照課本的算法思路對錯誤的語句進行分析，也上網(wǎng)找百度查詢，以得到無錯誤的程序，更重要的是與小組成員進行討論，體現(xiàn)了我們的合作精神。　　4、結(jié)果分析　　4.1 時間復(fù)雜度的分析<b

88、>　　a）加法運算　　由于兩矩陣行列相等，故時間復(fù)雜度為O（行*列）　　b) 減法運算　　由于兩矩陣行列相等，故時間復(fù)雜度為O（行*列）　　c）乘法運算

89、;　　設(shè)M是m1*n1矩陣，N是m2*n2矩陣，則時間復(fù)雜度是O（m1*n1*n2）　　4.2 心得體會　　雖然一直以來我不怎么喜歡數(shù)據(jù)結(jié)構(gòu)這門課，但是它已經(jīng)是我的一門課程，我就必須學(xué)好它，曾經(jīng)在編程上遇到過很多困難，編了一學(xué)期的程序，有時會因為編出作業(yè)題目而又高興幾天，有時會因編不出程序而失落

90、幾天，總之，我喜歡編程的過程，包括與同學(xué)交流，上網(wǎng)百度，從中學(xué)到了很多。　　此次的課程設(shè)計更讓我們意識到了數(shù)據(jù)結(jié)構(gòu)的高深，與小組成員的討論讓我們學(xué)到了更多關(guān)于數(shù)據(jù)結(jié)構(gòu)的知識，這是一次團隊合作的收獲成果。　　5、參考文獻　　1、《數(shù)據(jù)結(jié)構(gòu)》（c語言描述），嚴蔚敏編著，清華大學(xué)出

眾賞文庫> 全部分類> 畢業(yè)設(shè)計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負責(zé)。
6. 下載文件中如有侵權(quán)或不適當內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告--稀疏矩陣運算器

文檔簡介

溫馨提示

最新文檔

評論

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告--稀疏矩陣運算器

文檔簡介

溫馨提示

最新文檔

評論

免費下載