數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)論文----稀疏矩陣的轉(zhuǎn)置

1、<p><b>　　數(shù)據(jù)結(jié)構(gòu)</b></p><p><b>　　課 程 設(shè) 計(jì)</b></p><p>　題 目稀疏矩陣的轉(zhuǎn)置</p><p>　專 業(yè)網(wǎng)絡(luò)工程</p><p>　班 級(jí)09網(wǎng)絡(luò)工程</p><p>　姓 名</p&g

2、t;<p>　指導(dǎo)教師</p><p><b>　　課程設(shè)計(jì)任務(wù)書(shū)</b></p><p>　　題 目: 稀疏矩陣的轉(zhuǎn)置 </p><p><b>　　初始條件：</b></p><p>　?。?）稀疏矩陣采用三元組表示，

3、輸入一個(gè)稀疏矩陣A。</p><p>　　（2）求出A的轉(zhuǎn)置矩陣D，輸出D。</p><p><b>　　測(cè)試數(shù)據(jù)：</b></p><p>　　要求完成的主要任務(wù): </p><p>　　課程設(shè)計(jì)報(bào)告按學(xué)校規(guī)定格式用A4紙打印，并應(yīng)包含如下內(nèi)容： </p><p><b>　　1. 問(wèn)

4、題描述</b></p><p>　　簡(jiǎn)述題目要解決的問(wèn)題是什么。</p><p><b>　　2. 設(shè)計(jì)</b></p><p>　　存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)、主要算法設(shè)計(jì)（用C語(yǔ)言或用框圖描述）、測(cè)試用例設(shè)計(jì)。</p><p><b>　　3. 調(diào)試報(bào)告</b></p><p&

5、gt;　　調(diào)試過(guò)程中遇到的問(wèn)題是如何解決的；對(duì)設(shè)計(jì)和編碼的討論和分析。</p><p>　　4. 程序運(yùn)行結(jié)果（包括對(duì)算法改進(jìn)的設(shè)想）</p><p><b>　　5. 經(jīng)驗(yàn)與體會(huì)</b></p><p><b>　　6. 參考文獻(xiàn)</b></p><p><b>　　說(shuō)明：</b&

6、gt;</p><p>　　1. 設(shè)計(jì)報(bào)告、程序不得相互抄襲和拷貝；若有雷同，則所有雷同者成績(jī)均為0分。</p><p><b>　　時(shí)間安排：</b></p><p><b>　　1、第17周完成。</b></p><p>　　2、2011年6月28號(hào)提交打印版課程設(shè)計(jì)，源程序刻錄光盤。</

7、p><p>　　指導(dǎo)教師簽名： </p><p><b>　　年 月 日</b></p><p><b>　　目錄</b></p><p>　　1．問(wèn)題分析與任務(wù)定義1</p><p><b>　　2.結(jié)構(gòu)設(shè)計(jì)1</b></

8、p><p><b>　　3.算法思想1</b></p><p><b>　　4.模塊劃分2</b></p><p><b>　　5.算法實(shí)現(xiàn)2</b></p><p>　　5.1對(duì)矩陣進(jìn)行定義2</p><p>　　5.2創(chuàng)建稀疏矩陣2</p

9、><p>　　5.3求矩陣的快速轉(zhuǎn)置3</p><p>　　6.系統(tǒng)運(yùn)行結(jié)果5</p><p><b>　　7.經(jīng)驗(yàn)與體會(huì)5</b></p><p><b>　　8.參考文獻(xiàn)5</b></p><p><b>　　稀疏矩陣的轉(zhuǎn)置</b></p&

10、gt;<p>　　1．問(wèn)題分析與任務(wù)定義</p><p>　　稀疏矩陣是指那些多數(shù)元素為零的矩陣。利用“稀疏”特點(diǎn)進(jìn)行存儲(chǔ)和計(jì)算可以大大節(jié)省存儲(chǔ)空間，提高計(jì)算效率。實(shí)現(xiàn)一個(gè)能進(jìn)行稀疏矩陣基本運(yùn)算的運(yùn)算器。以“帶行邏輯鏈接信息”的三元組順序表表示稀疏矩陣，實(shí)現(xiàn)稀疏矩陣的轉(zhuǎn)置。求出稀疏矩陣A的轉(zhuǎn)置矩陣D，輸出D。</p><p>　　1.1稀疏矩陣采用三元組表示，輸入一個(gè)稀疏矩陣

11、A。</p><p>　　1.2求出A的轉(zhuǎn)置矩陣D，輸出D。</p><p><b>　　測(cè)試數(shù)據(jù)：</b></p><p><b>　　2.結(jié)構(gòu)設(shè)計(jì)</b></p><p>　　2.1.以“帶行邏輯鏈接信息”的三元組順序表表示稀疏矩陣。</p><p>　　2.2.稀疏矩陣

12、的輸入形式采用三元組表示，而運(yùn)算結(jié)果的矩陣則通常以陣列形式列出。</p><p>　　2.3.首先應(yīng)輸入矩陣的行數(shù)和列數(shù)，并判別給出的兩個(gè)矩陣的行、列數(shù)對(duì)于所要求作的運(yùn)算是否相匹配?？稍O(shè)矩陣的行數(shù)和列數(shù)均不超過(guò)20。</p><p>　　2.4.程序可以對(duì)三元組的輸入順序加以限制，例如，按行優(yōu)先。研究教材的算法，以便提高計(jì)算效率。</p><p>　　2.5.在用三

13、元組表示稀疏矩陣時(shí)，相加或相減所得結(jié)果矩陣應(yīng)該另生成，乘積矩陣也可用二維數(shù)組存放</p><p><b>　　3.算法思想</b></p><p>　　3.1．主函數(shù)設(shè)置循環(huán)和選擇語(yǔ)句進(jìn)行運(yùn)算循環(huán)和選擇，進(jìn)行稀疏矩陣的轉(zhuǎn)置和是否繼續(xù)運(yùn)算2個(gè)分支開(kāi)關(guān)進(jìn)行選擇。</p><p>　　3.2．設(shè)置函數(shù)分別實(shí)現(xiàn)稀疏矩陣的輸入，輸出。</p>

14、<p>　　3.3．在數(shù)組結(jié)構(gòu)體中設(shè)置存放每行第一個(gè)非零元在其數(shù)組存儲(chǔ)結(jié)構(gòu)單元的位置的存儲(chǔ)單元，若該行無(wú)非零元，則存為0</p><p><b>　　4.模塊劃分</b></p><p>　　4.1typedef struct存放各行第一個(gè)非零元在存儲(chǔ)數(shù)組中的位置，若該行無(wú)非零元，則其rpos[]值為零</p><p>　　4.2

15、 createsmatrix(rlsmatrix *M) 矩陣輸入函數(shù)，輸入各行非零元及其在矩陣中的行列數(shù)</p><p>　　4.3 FasttransposeRLSMatrix(RLSMatrix M,RLSMatrix *Q) 矩陣快速轉(zhuǎn)置</p><p><b>　　5.算法實(shí)現(xiàn)</b></p><p>　　5.1對(duì)矩陣進(jìn)行定義<

16、;/p><p>　　首先定義非零元個(gè)數(shù)的最大值和存放各行第一個(gè)非零元在存儲(chǔ)數(shù)組中的位置</p><p>　　#include<stdio.h> </p><p>　　#define MAXSIZE 100 /* 非零元個(gè)數(shù)的最大值 */ </p><p>　　typedef struct triple </p><

17、p><b>　　{ </b></p><p>　　int i,j; /* 行下標(biāo),列下標(biāo) */ </p><p>　　int e; /* 非零元素值 */ </p><p><b>　　}triple; </b></p><p>　　typedef struct tsmatrix </p

18、><p><b>　　{ </b></p><p>　　triple data[MAXSIZE+1]; /* 非零元三元組表,data[0]未用 */ </p><p>　　int mu,nu,tu; /* 矩陣的行數(shù)、列數(shù)和非零元個(gè)數(shù) */ </p><p>　　/* 各列第一個(gè)非零元的位置表rpos[0]未用 */ &l

19、t;/p><p>　　}rlsmatrix; </p><p><b>　　5.2創(chuàng)建稀疏矩陣</b></p><p>　　創(chuàng)建稀疏矩陣矩陣的行數(shù)，列數(shù)，和非零元素的個(gè)數(shù)并按行序順序輸入第%d個(gè)非零元素所在的行(1～%d),列(1～%d),元素值。</p><p>　　createsmatrix(rlsmatrix *M)

20、</p><p>　　{ /* 創(chuàng)建稀疏矩陣M */ </p><p>　　int e,i,m,n; </p><p>　　M->data[0].i=0; /* 為以下比較順序做準(zhǔn)備 */ </p><p>　　printf("請(qǐng)輸入矩陣的行數(shù)，列數(shù)，和非零元素的個(gè)數(shù):"); </p><p>

21、;　　scanf("%d",&M->mu);scanf("%d",&M->nu);scanf("%d",&M->tu); </p><p>　　for(i=1;i<=M->tu;i++) </p><p><b>　　{ </b></p>&

22、lt;p>　　printf("請(qǐng)按行序順序輸入第%d個(gè)非零元素所在的行(1～%d),列(1～%d),元素值：",i,M->mu,M->nu); </p><p>　　scanf("%d",&m);scanf("%d",&n);scanf("%d",&e); </p><p&

23、gt;　　if(m<1||m>M->mu||n<1||n>M->nu) /*行或列超出范圍 */ </p><p>　　{printf("行或列超出范圍");getch();exit();} </p><p>　　if(m<M->data[i-1].i||m==M->data[i-1].i&&n<

24、;=M->data[i-1].j) /*行或列的順序有錯(cuò)*/ </p><p>　　{printf("行或列的順序有錯(cuò)");getch();exit();} </p><p>　　M->data[i].i=m; </p><p>　　M->data[i].j=n; </p><p>　　M->dat

25、a[i].e=e; </p><p><b>　　} </b></p><p><b>　　} </b></p><p>　　5.3求矩陣的快速轉(zhuǎn)置 </p><p>　　cpos為存放每列的第一個(gè)非零元素的地址，temp為中間變量對(duì)cpos對(duì)初始化，判斷初值為0則為cpos賦值，然后進(jìn)行轉(zhuǎn)置。&l

26、t;/p><p>　　void transposesmatrix(rlsmatrix M,rlsmatrix *T) </p><p>　　{ /* cpos存放每列的第一個(gè)非零元素的地址，temp中間變量 */ </p><p>　　int i,m,*cpos,*temp,k=0; </p><p>　　T->mu=M.nu; </

27、p><p>　　T->nu=M.mu; </p><p>　　T->tu=M.tu; </p><p>　　cpos=(int *)malloc(M.mu*sizeof(int)); </p><p>　　if(cpos==NULL)exit(); </p><p>　　temp=(int *)malloc(M

28、.mu*sizeof(int)); </p><p>　　if(temp==NULL)exit(); </p><p>　　/* 對(duì)cpos對(duì)初始化，初值為0 */ </p><p>　　*(cpos+1)=0; </p><p>　　for(i=1;i<=M.nu;i++) </p><p><b>

29、　　{ </b></p><p>　　for(m=1;m<=M.tu;m++) </p><p><b>　　{ </b></p><p>　　if(M.data[m].j==i) </p><p><b>　　k++; </b></p><p><b

30、>　　} </b></p><p>　　temp[i]=k; </p><p>　　if(i==1&&k!=0) </p><p>　　*(cpos+i)=1;/* 為cpos賦值 */ </p><p><b>　　if(i>1) </b></p><p>

31、;　　*(cpos+i)=*(temp+i-1)+1; </p><p><b>　　} </b></p><p>　　free(temp); </p><p>　　for(i=1;i<=M.tu;i++)/* 進(jìn)行轉(zhuǎn)置 */ </p><p>　　{T->data[*(cpos+M.data[i].j)].

32、i=M.data[i].j; </p><p>　　T->data[*(cpos+M.data[i].j)].j=M.data[i].i; </p><p>　　T->data[*(cpos+M.data[i].j)].e=M.data[i].e; </p><p>　　(*(cpos+M.data[i].j))++;} </p><

33、p>　　free(cpos); </p><p><b>　　}</b></p><p><b>　　6.系統(tǒng)運(yùn)行結(jié)果</b></p><p>　　圖3矩陣A的轉(zhuǎn)置矩陣D</p><p><b>　　7.經(jīng)驗(yàn)與體會(huì)</b></p><p>　　通過(guò)

34、一周的課程設(shè)計(jì)使我對(duì)數(shù)據(jù)結(jié)構(gòu)有了更深的理解，對(duì)以前學(xué)習(xí)中不明白的，不理解的都有了進(jìn)一步的理解。在實(shí)際操作中遇到了很多困難，但通過(guò)找資料，請(qǐng)教同學(xué)和老師，使我的動(dòng)手能力和溝通能力都有了提高。在整個(gè)課程設(shè)計(jì)中總是在編寫(xiě)程序中發(fā)生錯(cuò)誤，有時(shí)會(huì)很沒(méi)耐性，但都被我一一克服了，編程一定要有耐心，同時(shí)還有認(rèn)真仔細(xì)，盡量保證不出現(xiàn)錯(cuò)誤。編程要有條理，不僅使自己要看懂 ，別人也能看懂，這樣有利于程序的改正。</p><p>　　在

35、做完這個(gè)課程設(shè)計(jì)時(shí)，心里有種說(shuō)不出來(lái)的高興，自己動(dòng)手完成的設(shè)計(jì)有一種成就感，增強(qiáng)了自己的自信心，我相信在今后的學(xué)習(xí)中，我會(huì)保持這種良好的心情投入到各科的學(xué)習(xí)中，使我的成績(jī)不斷提高。</p><p><b>　　8.參考文獻(xiàn)</b></p><p>　　[1] 嚴(yán)蔚敏 吳偉名 編著，《數(shù)據(jù)結(jié)構(gòu)》[M].，清華大學(xué)出版社， 2001年1月</p><

36、p>　　[2] 譚浩強(qiáng) 編著，《C程序設(shè)計(jì)》（第三版）[M].，清華大學(xué)出版社，2005年2月</p><p><b>　　課程設(shè)計(jì)成績(jī)?cè)u(píng)定表</b></p><p>　　班級(jí)：09網(wǎng)絡(luò)工程　 姓名：李敏龍　 學(xué)號(hào)：0908020108</p><p><b>　　指導(dǎo)教師簽名：</b></p>