課程設(shè)計---稀疏矩陣應(yīng)用

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

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

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

文檔簡介

1、　　數(shù)學(xué)與計算機學(xué)院　　課程設(shè)計說明書　　課程名稱: 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 　　課程代碼: 8404181 　　題目:

2、稀疏矩陣應(yīng)用 　　年級/專業(yè)/班: 　　學(xué) 生姓名: 　　學(xué)　　號: 　　開始時間: 2011 年 06 月 13 日&l

3、t;/p>　　完成時間: 2011 年 06 月 21 日　　課程設(shè)計成績：　　指導(dǎo)教師簽名：年月日　　目錄<

4、p>　　1 引言1　　1.1 問題的提出1　　1.2國內(nèi)外研究的現(xiàn)狀1　　1.3任務(wù)與分析 1　　2 程序的主要功能1　　2.1三元組的轉(zhuǎn)置1&l

5、t;p>　　2.2三元組的加法1　　2.3三元組的減法1　　2.4三元組的乘法2　　2.5十字鏈表的轉(zhuǎn)置2　　2.6十字鏈表的加法2　　2.7十字鏈表的減法2　　2.8十

6、字鏈表的乘法2　　3程序運行平臺3　　4總體設(shè)計3　　5程序類的說明4　　6 模塊分析5

7、　　6.1 三元組的轉(zhuǎn)置5　　6.2 三元組減法6　　6.3三元組的減法9　　6.4三元組的乘法12　　6.5 十字鏈表的轉(zhuǎn)置14　　6.6 十字鏈表的加法15<p&g

8、t;　　6.7十字鏈表的減法18　　6.8十字鏈表的乘法22　　7 系統(tǒng)測試25　　7.1三元組的轉(zhuǎn)置25　　7.2 三元組的加法26　　7.3 三元組的減法26

9、;　　7.4 三元組的乘法27　　7.5 十字鏈表的轉(zhuǎn)置27　　7.6十字鏈表的加法28　　7.7 十字鏈表的減法28　　7.8 十字鏈表的乘法29　　7.9 總結(jié)29</

10、b>　　8結(jié)論29　　參考文獻29　　摘要 　　隨著計算機的普及，一句話引出題目…（小四楷體_GB2312），分析了三元組和十字鏈表的存儲和各

11、種運算的實現(xiàn)，利用C語言編程實現(xiàn)了稀疏矩陣的運算系統(tǒng)，該系統(tǒng)具有三元組十字鏈表存儲下的稀疏矩陣轉(zhuǎn)置、加法、減法、乘法的功能。　　關(guān)鍵詞：稀疏矩陣;計算機; 運算器　　1 引言 　　1.1 問題的提出 　　矩陣是很多科學(xué)與工程計算問

12、題中研究的數(shù)學(xué)對象。因此，我們感興趣的不是矩陣本身，而是如何存儲矩陣的元，從而使矩陣的各種運算能有效地進行。　　通常，用高級語言編制程序時，都是用二維數(shù)組來存儲矩陣元，有的程序設(shè)計語言中還提供了各種矩陣運算，用戶使用時很方便。　　然而，在數(shù)值分析中，經(jīng)常出現(xiàn)一些階數(shù)很高的矩陣，同時在矩陣中有許多值相同的元素或者是零元素，有時為了節(jié)省存儲空間，可以對這類矩

13、陣進行壓縮存儲。所謂壓縮存儲，就是指：為多個值相同的元只分配一個存儲空間；對零元不分配空間。　　1.2國內(nèi)外研究的現(xiàn)狀 　　目前已經(jīng)可以用于人臉識別、子空間方法預(yù)處理技術(shù)稀疏近似逆按模最小特征值修正矩陣廣義極小殘余方法等方面。　　1.3任務(wù)與分析 　　（1）給出算法并編

14、程實現(xiàn)；　?。?）任給實例并演示求解結(jié)果；　　（3）給出時間復(fù)雜度分析；　?。?）結(jié)合所完成題目，分析總結(jié)各算法所使用的算法設(shè)計技術(shù)，以及相應(yīng)技術(shù)的基本思想。　　2 程序的主要功能<b&

15、gt;　　2.1三元組的轉(zhuǎn)置　　將一個按三元組存儲的稀疏矩陣進行轉(zhuǎn)置。　　2.2三元組的加法　　將兩個按三元組存儲的稀疏矩陣進行相加并得出結(jié)果。　　2.3三元組的減法</

16、p>　　將兩個按三元組存儲的稀疏矩陣進行相減并得出結(jié)果。　　2.4三元組的乘法　　將兩個按三元組存儲的稀疏矩陣進行相乘并得出結(jié)果。　　2.5十字鏈表的轉(zhuǎn)置　　將一個按十字鏈表存儲的稀疏矩陣進行轉(zhuǎn)置。<

17、/p>　　2.6十字鏈表的加法　　將兩個按十字鏈表存儲的稀疏矩陣進行相加并得出結(jié)果。　　2.7十字鏈表的減法　　將兩個按十字鏈表存儲的稀疏矩陣進行相加并得出結(jié)果。　　2.8十字鏈表的乘法　　將兩個按十字

18、鏈表存儲的稀疏矩陣進行相加并得出結(jié)果。　　3程序運行平臺　　VC++6.0。編譯，鏈接，執(zhí)行。　　4總體設(shè)計　　圖4.1 系統(tǒng)總體框架圖

19、　　5程序類的說明　　OLNode結(jié)構(gòu)聲明　　typedef struct OLNode　　{　　int i,j;

20、　int e;　　struct OLNode *right,*down;　　}OLNode,*OLink;　　Crosslist結(jié)構(gòu)的聲明　　typedef struct 　　{</b&

21、gt;　　int mu,nu,tu;　　OLink *rhead,*chead;　　}CrossList;　　Triple結(jié)構(gòu)的聲明　　typedef struct　　{

22、　　int i,j;　　int e;　　}Triple;　　TSMatrix結(jié)構(gòu)的聲明　　typ

23、edef struct　　{　　Triple data[maxsize];　　int rpos[maxsize+1]; 　　int nu,mu,tu;　　}TSMatrix;

24、;　　6 模塊分析　　6.1 三元組的轉(zhuǎn)置　　將一個按三元組存儲的稀疏矩陣進行轉(zhuǎn)置（非快速轉(zhuǎn)置）。　　void TransposeSMatrix(TSMatrix M,TSMatrix &T)//三元組的轉(zhuǎn)置<p&g

25、t;　　{　　T.nu=M.mu;　　T.mu=M.nu;　　T.tu=M.tu;　　int q=1;　　for(int col=1;col<=M.

26、nu;col++)　　for(int p=1;p<=M.tu;p++)　　if(M.data[p].j==col)　　{　　T.data[q].i=M.data[p].j;　　T.dat

27、a[q].j=M.data[p].i;　　T.data[q].e=M.data[p].e;　　q++;　　}　　}

28、　int Compare(int a1,int b1,int a2,int b2)　　{　　if(a1>a2)return 1;　　else if(a1<a2)　　return -1;<p&g

29、t;　　else if(b1>b2)　　return 1;　　if(b1<b2)　　return -1;　　else<

30、;p>　　return 0;　　}　　6.2 三元組減法　　用戶再輸入一個稀疏矩陣，系統(tǒng)將兩個矩陣進行加運算并得出結(jié)果。　　void AddTMatix

31、(TSMatrix M,TSMatrix T,TSMatrix &S)//三元組相加　　{　　S.mu=M.mu>T.mu?M.mu:T.mu;　　S.nu=M.nu>T.nu?M.nu:T.nu;

32、;　　S.tu=0;　　int ce;　　int q=1;int mcount=1,tcount=1;　　while(mcount<=M.tu&&tcount<=T.tu)<b&g

33、t;　　{　　switch(Compare(M.data[mcount].i,M.data[mcount].j,T.data[tcount].i,T.data[tcount].j))　　{　　case -1: <

34、/p>　　S.data[q].e=M.data[mcount].e;　　S.data[q].i=M.data[mcount].i;　　S.data[q].j=M.data[mcount].j;　　q++;

35、　mcount++; 　　break;　　case 1: 　　S.data[q].e=T.data[tcount].e;　　S.data[q].i=T.data[tcount].i;</p&

36、gt;　　S.data[q].j=T.data[tcount].j;　　q++;　　tcount++; 　　break;　　case 0: </b&g

37、t;　　ce=M.data[mcount].e+T.data[tcount].e;　　if(ce)　　{　　S.data[q].e=ce;　　S.data

38、[q].i=M.data[mcount].i;　　S.data[q].j=M.data[mcount].j;　　q++;　　mcount++;　　tcount++;</b&

39、gt;　　}　　else　　{　　mcount++;　　tc

40、ount++;　　}　　break;　　}　　}　　whi

41、le(mcount<=M.tu)　　{　　S.data[q].e=M.data[mcount].e;　　S.data[q].i=M.data[mcount].i;　　S.data[q].j=M.data[mcount].j;&l

42、t;/p>　　q++;　　mcount++;　　}　　while(tcount<=M.tu)　　{<

43、/b>　　S.data[q].e=T.data[tcount].e;　　S.data[q].i=T.data[tcount].i;　　S.data[q].j=T.data[tcount].j;　　q++;

44、　　tcount++; 　　}　　S.tu=q-1;　　}…　　6.3三元組的減法

45、　　用戶再輸入一個稀疏矩陣，系統(tǒng)將兩個矩陣進行加運、減算并得出結(jié)果。　　void jianTMatix(TSMatrix M,TSMatrix T,TSMatrix &S)//三元組相減　　{　　S.mu=M.mu>T.mu?M.mu:T.

46、mu;　　S.nu=M.nu>T.nu?M.nu:T.nu;　　S.tu=0;　　int ce;　　int q=1;int mcount=1,tcount=1;<

47、;p>　　while(mcount<=M.tu&&tcount<=T.tu)　　{　　switch(Compare(M.data[mcount].i,M.data[mcount].j,T.data[tcount].i,T.data[tcount].j))<

48、;p>　　{　　case -1: 　　S.data[q].e=M.data[mcount].e;　　S.data[q].i=M.data[mcount].i;　　S.data[q].j=M.

49、data[mcount].j;　　q++;　　mcount++; 　　break;　　case 1: 　　S.dat

50、a[q].e=-T.data[tcount].e;　　S.data[q].i=T.data[tcount].i;　　S.data[q].j=T.data[tcount].j;　　q++;　　tcount++;

51、　　break;　　case 0: 　　ce=M.data[mcount].e-T.data[tcount].e;　　if(ce)<b

52、>　　{　　S.data[q].e=ce;　　S.data[q].i=M.data[mcount].i;　　S.data[q].j=M.data[mcount].j;　　q++;<

53、;p>　　mcount++;　　tcount++;　　}　　else　　{&

54、lt;/p>　　mcount++;　　tcount++;　　}　　break;<b&g

55、t;　　}　　}　　while(mcount<=M.tu)　　{　　S.data[q].e=M.data[mcount].e;

56、　S.data[q].i=M.data[mcount].i;　　S.data[q].j=M.data[mcount].j;　　q++;　　mcount++;　　}</b&g

57、t;　　while(tcount<=M.tu)　　{　　S.data[q].e=-T.data[tcount].e;　　S.data[q].i=T.data[tcount].i;　　S.

58、data[q].j=T.data[tcount].j;　　q++;　　tcount++; 　　}　　S.tu=q-1;

59、;　　}　　6.4三元組的乘法　　用戶再輸入一個稀疏矩陣，系統(tǒng)將其進行乘法運算并得出結(jié)果。　　int MultSMatrix(TSMatrix M, TSMatrix N, TSMatrix &Q) //三元組相乘</p&

60、gt;　　{　　int arow,brow,ccol,i,t,ctemp[100],p,q,tp;　　if(M.nu != N.mu) 　　return 0;　　Q.mu=M

61、.mu;　　Q.nu =N.nu;　　Q.tu =0;　　if(M.tu*N.tu!=0)　　{　　for(arow=1;arow<=M.mu;++

62、arow)　　{　　for(i=0;i<=N.nu;++i) 　　ctemp[i]=0;　　Q.rpos[arow]=Q.tu+1;　　if(arow<M.mu) </p&g

63、t;　　tp=M.rpos[arow+1];　　else 　　tp=M.tu+1;　　for(p=M.rpos[arow];p<tp;++p)　　{

64、　　brow=M.data[p].j; 　　if(brow<N.mu) 　　t=N.rpos[brow+1];　　else 　　t=N.tu+1;

65、　　for(q=N.rpos[brow];q<t ++q)　　{　　ccol=N.data[q].j; 　　ctemp[ccol]+=M.data[p].e*N.data[q].e;　　}&

66、lt;/b>　　}　　for(ccol=1;ccol<=Q.nu;++ccol) 　　{　　if(ctemp[ccol])

67、　{　　if(++(Q.tu)>maxsize) 　　return 1;　　Q.data[Q.tu].i=arow,Q.data[Q.tu].j=ccol,Q.data[Q.tu].e=ctemp[ccol]; <p&g

68、t;　　} 　　}　　} 　　}　　return 1;&l

69、t;p>　　}　　6.5 十字鏈表的轉(zhuǎn)置　　void TurnSMatrix_OL(CrossList &M) //十字鏈表轉(zhuǎn)置　　{　　int col,row;</p&g

70、t;　　OLink p,q;　　for(col=1;col<=M.mu;col++)　　{　　q=p=M.rhead[col];　　while(q)

71、　　{　　row=p->i;　　p->i=p->j;　　p->j=row;　　q=p->right;<

72、;/p>　　p->right=p->down;　　p->down=q;　　}　　}　　}

73、　　6.6 十字鏈表的加法　　int SMatrix_ADD(CrossList *A,CrossList *B) //十字鏈表相加　　{　　OLNode *pa,*pb,*pre,*p,*cp[100];　　i

74、nt i,j,t;　　t=A->tu+B->tu;　　for(j=1;j<=A->nu;j++)　　cp[j]=A->chead[j];　　for(i=1;i<=A->mu;i++)<

75、;b>　　{　　pa=A->rhead[i];　　pb=B->rhead[i];　　pre=NULL;　　while(pb)<p

76、>　　{　　if(pa==NULL||pa->j>pb->j)　　{　　p=(OLink)malloc(sizeof(OLNode));　　if(!pre

77、)　　A->rhead[i]=p;　　else　　pre->right=p;　　p->right=pa;　　pre=p;</b&g

78、t;　　p->i=i;　　p->j=pb->j;　　p->e=pb->e;　　if(!A->chead[p->j])　　{</

79、b>　　A->chead[p->j]=cp[p->j]=p;　　p->down=NULL;　　}　　else

80、;　　{　　cp[p->j]->down=p;　　cp[p->j]=p;　　}　　pb=pb->right;　　}</b&g

81、t;　　else if(pa->j<pb->j)　　{　　pre=pa;　　pa=pa->right;　　}&l

82、t;/b>　　else if(pa->e+pb->e)　　{　　t--;　　pa->e+=pb->e;

83、pre=pa;　　pa=pa->right;　　pb=pb->right;　　}　　else　　{ &l

84、t;/b>　　t=t-2;　　if(!pre)　　A->rhead[i]=pa->right;　　else<p

85、>　　pre->right=pa->right;　　p=pa;　　pa=pa->right;　　if(A->chead[p->j]==p)　　A->chead[p->j]=cp[p-&g

86、t;j]=p->down;　　else 　　cp[p->j]->down=p->down;　　free(p);　　pb=pb->right;&

87、lt;p>　　}　　}　　}　　A->mu=A->mu>B->mu?A->mu:B->mu;　　A->nu=A

88、->nu>B->nu?A->nu:B->nu;　　return 1;　　}　　6.7十字鏈表的減法　　int SMatrix_jian(CrossList *A,Cr

89、ossList *B) //十字鏈表相減　　{　　OLNode *pa,*pb,*pre,*p,*cp[100];　　int i,j,t;　　t=A->tu+B->tu;　　f

90、or(j=1;j<=A->nu;j++)　　cp[j]=A->chead[j];　　for(i=1;i<=A->mu;i++)　　{　　pa=A->rhead[i];<

91、p>　　pb=B->rhead[i];　　pre=NULL;　　while(pb)　　{　　if(pa==NULL||pa->j>pb

92、->j)　　{　　p=(OLink)malloc(sizeof(OLNode));　　if(!pre)　　A->rhead[i]=p;<

93、b>　　else　　pre->right=p;　　p->right=pa;　　pre=p;　　p->i=i;

94、　p->j=pb->j;　　p->e=-pb->e;　　if(!A->chead[p->j])　　{　　A->chead[p->j]=cp[p->j]=p;

95、　　p->down=NULL;　　}　　else　　{　　cp[p->j]->down=p;<

96、;p>　　cp[p->j]=p;　　}　　pb=pb->right;　　}　　else if(pa->j<pb->j)

97、　　{　　pre=pa;　　pa=pa->right;　　}　　else if(pa->e-pb->e)<p&

98、gt;　　{　　t--;　　pa->e-=pb->e;　　pre=pa;　　pa=pa->right;<p&g

99、t;　　pb=pb->right;　　}　　else　　{ 　　t=t-2;<p&g

100、t;　　if(!pre)　　A->rhead[i]=pa->right;　　else　　pre->right=pa->right;　　p=pa;</

101、b>　　pa=pa->right;　　if(A->chead[p->j]==p)　　A->chead[p->j]=cp[p->j]=p->down;　　else

102、　　cp[p->j]->down=p->down;　　free(p);　　pb=pb->right;　　}　　}&l

103、t;/p>　　}　　A->mu=A->mu>B->mu?A->mu:B->mu;　　A->nu=A->nu>B->nu?A->nu:B->nu;　　retur

104、n 1;　　}　　6.8十字鏈表的乘法　　int MultSMatrix_OL(CrossList M, CrossList N, CrossList &Q) //十字鏈表相乘　　{&l

105、t;/b>　　int i, j, e; 　　OLink p0, q0, p, pl, pla; 　　if(M.nu!=N.mu)//檢查稀疏矩陣M的列數(shù)和N的行數(shù)是否對應(yīng)相等　　{　　p

106、rintf( "稀疏矩陣A的列數(shù)和B的行數(shù)不相等，不能相乘。\n" );　　return 0; 　　}　　Q.mu=M.mu;　　Q.nu=N.nu;

107、Q.tu=0;　　if(!(Q.rhead=(OLink*)malloc((Q.mu+1)*sizeof(OLink))))　　exit(-2);　　if(!(Q.chead=(OLink*)malloc((Q.nu+1)*sizeof(OLink))))

108、 　　exit(-2);　　for(i=1;i<=Q.mu;i++)　　Q.rhead[i] = NULL;　　for(i=1;i<=Q.nu;i++) 　　Q.chead[i]=

109、NULL;　　for(i=1;i<=Q.mu;i++) //相乘　　for(j=1;j<=Q.nu;j++)　　{　　p0 = M.rhead[i];　　q0 = N.c

110、head[j];　　e = 0;　　while(p0&&q0)//M第i行和N第j列有元素　　{　　if( p0->j > q0->i)

111、　　q0 = q0->down; //M的列大于N的行，則N的列指針后移　　else if(p0->j < q0->i) 　　p0 = p0->right;//M的列小于N的行，則M的行指針右移　　else //M的行等于N的列<p&g

112、t;　　{　　e += p0->e * q0->e; //乘積累加　　q0 = q0->down, p0 = p0->right;//移動指針　　}　　}

113、　　if(e)//乘積不為0　　{　　if(!(p = (OLink)malloc(sizeof(OLNode)))) 　　exit(-2);<p

114、>　　Q.tu++;//非零元素增加　　p->i=i;　　p->j=j;　　p->e=e;　　p->right=NULL;<

115、;/p>　　p->down=NULL;//賦值，指針后移，將p插入十字鏈表行插入　　if(Q.rhead[i]==NULL) //若p為該行的第1個結(jié)點　　Q.rhead[i]=p =p; //p插在該行的表頭且pl指向p(該行的最后一個結(jié)點)　　else

116、　　pl->right=p,pl=p; //插在pl所指結(jié)點之后，pl右移列插入　　if(Q.chead[j] == NULL) //若p為該列的第一個結(jié)點　　Q.chead[j] = p; //該列的表頭指向p　　else

117、　　{　　//插在列表尾　　pla = Q.chead[j];//pla指向j行的第1個結(jié)點　　while(pla->down)

118、　　pla = pla->down;//pla指向j行最后一個結(jié)點　　pla->down = p; 　　}　　}　　}&l

119、t;p>　　return 1;　　}　　7 系統(tǒng)測試　　首先進入VC++6.0，打開“稀疏矩陣應(yīng)用.cpp”，編譯后執(zhí)行文件，按系統(tǒng)提示操作。<b

120、>　　7.1三元組的轉(zhuǎn)置　　三元組的轉(zhuǎn)置，實現(xiàn)。　　7.2 三元組的加法　　三元組的加法，實現(xiàn)。　　7.3 三元組的減法　　三元組的減法，實現(xiàn)。　　7.4 三元組

121、的乘法　　三元組的乘法，實現(xiàn)。　　7.5 十字鏈表的轉(zhuǎn)置　　十字鏈表的轉(zhuǎn)置，實現(xiàn)。　　7.6十字鏈表的加法　　十字鏈表的加法，實現(xiàn)。　　7.7 十字鏈表的減法<

122、;p>　　十字鏈表的減法，實現(xiàn)。　　7.8 十字鏈表的乘法　　十字鏈表的乘法，實現(xiàn)。　　7.9總結(jié)　　通過上述測試，本系統(tǒng)實現(xiàn)了三元組和十字鏈表的轉(zhuǎn)置、加、減、乘功能，且實現(xiàn)各個功能的時間復(fù)雜度均為 n平方。

123、　　8結(jié)論　　通過上述測試，本系統(tǒng)用C語言在VC++6.0的平臺上進行編程，實現(xiàn)了三元組和十字鏈表的轉(zhuǎn)置、加、減、乘功能。　　在進行稀疏矩陣的相加時，用十字鏈表更方便；進行相乘時，用三元組更方便。　　參考文獻<

眾賞文庫> 全部分類> 畢業(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)或不適當(dāng)內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

課程設(shè)計---稀疏矩陣應(yīng)用

文檔簡介

溫馨提示

最新文檔

評論

課程設(shè)計---稀疏矩陣應(yīng)用

文檔簡介

溫馨提示

最新文檔

評論

免費下載