數據結構課程設計論文----稀疏矩陣的轉置

1、<p><b>　　數據結構</b></p><p><b>　　課 程 設 計</b></p><p>　題 目稀疏矩陣的轉置</p><p>　專 業(yè)網絡工程</p><p>　班 級09網絡工程</p><p>　姓 名</p&g

2、t;<p>　指導教師</p><p><b>　　課程設計任務書</b></p><p>　　題 目: 稀疏矩陣的轉置 </p><p><b>　　初始條件：</b></p><p>　?。?）稀疏矩陣采用三元組表示，

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

4、題描述</b></p><p>　　簡述題目要解決的問題是什么。</p><p><b>　　2. 設計</b></p><p>　　存儲結構設計、主要算法設計（用C語言或用框圖描述）、測試用例設計。</p><p><b>　　3. 調試報告</b></p><p&

5、gt;　　調試過程中遇到的問題是如何解決的；對設計和編碼的討論和分析。</p><p>　　4. 程序運行結果（包括對算法改進的設想）</p><p><b>　　5. 經驗與體會</b></p><p><b>　　6. 參考文獻</b></p><p><b>　　說明：</b&

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

7、p><p>　　指導教師簽名： </p><p><b>　　年 月 日</b></p><p><b>　　目錄</b></p><p>　　1．問題分析與任務定義1</p><p><b>　　2.結構設計1</b></

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

9、><p>　　5.3求矩陣的快速轉置3</p><p>　　6.系統(tǒng)運行結果5</p><p><b>　　7.經驗與體會5</b></p><p><b>　　8.參考文獻5</b></p><p><b>　　稀疏矩陣的轉置</b></p&

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

11、A。</p><p>　　1.2求出A的轉置矩陣D，輸出D。</p><p><b>　　測試數據：</b></p><p><b>　　2.結構設計</b></p><p>　　2.1.以“帶行邏輯鏈接信息”的三元組順序表表示稀疏矩陣。</p><p>　　2.2.稀疏矩陣

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

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

14、<p>　　3.3．在數組結構體中設置存放每行第一個非零元在其數組存儲結構單元的位置的存儲單元，若該行無非零元，則存為0</p><p><b>　　4.模塊劃分</b></p><p>　　4.1typedef struct存放各行第一個非零元在存儲數組中的位置，若該行無非零元，則其rpos[]值為零</p><p>　　4.2

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

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

17、p><b>　　{ </b></p><p>　　int i,j; /* 行下標,列下標 */ </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; /* 矩陣的行數、列數和非零元個數 */ </p><p>　　/* 各列第一個非零元的位置表rpos[0]未用 */ &l

19、t;/p><p>　　}rlsmatrix; </p><p><b>　　5.2創(chuàng)建稀疏矩陣</b></p><p>　　創(chuàng)建稀疏矩陣矩陣的行數，列數，和非零元素的個數并按行序順序輸入第%d個非零元素所在的行(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; /* 為以下比較順序做準備 */ </p><p>　　printf("請輸入矩陣的行數，列數，和非零元素的個數:"); </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("請按行序順序輸入第%d個非零元素所在的行(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) /*行或列的順序有錯*/ </p><p>　　{printf("行或列的順序有錯");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求矩陣的快速轉置 </p><p>　　cpos為存放每列的第一個非零元素的地址，temp為中間變量對cpos對初始化，判斷初值為0則為cpos賦值，然后進行轉置。&l

26、t;/p><p>　　void transposesmatrix(rlsmatrix M,rlsmatrix *T) </p><p>　　{ /* cpos存放每列的第一個非零元素的地址，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>　　/* 對cpos對初始化，初值為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++)/* 進行轉置 */ </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)運行結果</b></p><p>　　圖3矩陣A的轉置矩陣D</p><p><b>　　7.經驗與體會</b></p><p>　　通過

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

35、做完這個課程設計時，心里有種說不出來的高興，自己動手完成的設計有一種成就感，增強了自己的自信心，我相信在今后的學習中，我會保持這種良好的心情投入到各科的學習中，使我的成績不斷提高。</p><p><b>　　8.參考文獻</b></p><p>　　[1] 嚴蔚敏 吳偉名 編著，《數據結構》[M].，清華大學出版社， 2001年1月</p><

36、p>　　[2] 譚浩強 編著，《C程序設計》（第三版）[M].，清華大學出版社，2005年2月</p><p><b>　　課程設計成績評定表</b></p><p>　　班級：09網絡工程　 姓名：李敏龍　 學號：0908020108</p><p><b>　　指導教師簽名：</b></p>