數據結構課程設計(稀疏矩陣運算器)

1、課程設計報告*大學數據結構課程設計說明書題 目：稀疏矩陣運算器學生姓名：學 號：專 業(yè)：班 級：指導教師： 2013 年 7 月 24日稀疏矩陣運算器摘 要 摘要：設計一稀疏矩陣運算器。實現兩個矩陣的相加、相減和相乘的功能。用“帶行邏輯鏈接信息”的三元組順序表表示稀疏矩陣，實現兩個矩陣相加、相減和相乘的運算，采用分級的設計方法，分別設計出加、減、乘運算器的子程序，相加運算時只要依次存儲、掃描兩矩陣的行、列數，若行、列數相等，再取行、列下標相等的元素，相加后存入結果矩陣。相減運算與相加運算相同，同樣取行、列下標相等的元素，相減后存入結果矩陣。相乘運算要先判斷兩矩陣能否相乘。若能相乘，則取行、列號

2、相對應的元素進行相乘及相加，最后將對應元素存入結果矩陣中。通過實驗表明本程序能夠進行稀疏矩陣的相加，相減，相乘運算。具備矩陣的加、減、乘功能。關鍵詞：相加運算器；相減運算器；相乘運算器 數據結構課程設計任務書針對本課程設計，完成以下課程設計任務：1、 熟悉系統實現工具和上級環(huán)境。2、 根據課程設計任務，查閱相關資料。3、 針對所選課題完成以下工作：（1）、需求分析（2）、概要設計（3）、詳細設計（4）、編寫源程序（5）、靜態(tài)走查程序和上機調試程序4、書寫上述文檔和撰寫課程設計報告。目 錄稀疏矩陣運算器I摘 要II課程設計任務書III課程設計正文第一章 問題描述5第二章 需求分析6第三章 概要設

3、計9第四章 詳細設計19 4.1 函數說明10 4.2 算法分析19第五章 調試分析21第六章 測試結果23第七章 課程設計總結24參考文獻24附錄（程序清單）33第一章 問題描述一、問題描述：稀疏矩陣是指那些多數元素為零的矩陣，利用“稀疏”特點進行存儲和計算可以大大節(jié)省存儲空間，提高計算效率，實現一個能進行稀疏矩陣基本運算的運算器。二、基本要求：以“帶行邏輯鏈接信息”的三元組順序表表示稀疏矩陣，實現兩個矩陣相加、相減和相乘的運算。稀疏矩陣的輸入形式采用三元組表示，而運算結果的矩陣則以通常的陣列形式列出。第二章 需求分析1、運算器程序以用戶和計算機的對話方式執(zhí)行，數組的建立方式為邊輸入邊建立。

4、2、由題目要求可知：首先應輸入矩陣的行數、列數和非零個數，并判別給出的兩個矩陣的行、列數對于所要求作的運算是否相匹配。3、程序可以對三元組的輸入順序不加以限制；根據對矩陣的行列，三元組作直接插入排序，從而進行運算時,不會產生錯誤。4、在用三元組表示稀疏矩陣時，相加、相減和乘積所得結果矩陣應該另生成，為了算法方便，使用二維數組存放。程序在Visual C+ 6.0環(huán)境下設計。程序執(zhí)行的命令為：1.稀疏矩陣加法; 2.稀疏矩陣減法; 3.稀疏矩陣乘法; 第三章 概要設計1、三元組結構定義：typedef struct /三元組結構 int i,j; /矩陣行下標和列下標 int e; /值trip

5、le;2、稀疏矩陣結構定義：typedef struct/矩陣結構triple dataMAXSIZE+1; int m,n,t; /矩陣的行數、列數、非零元個數tripletable;3、兩個稀疏矩陣相加函數：Add (tripletable M，tripletable T)4、兩個稀疏矩陣相減函數：mut (tripletable M，tripletable T)5、兩個稀疏矩陣相乘函數：mul (tripletable M，tripletable T)6、主函數：void main( )初始化；switch 接受命令；選擇處理命令； 7、本程序有四個模塊，調用關系如下：主程序模塊矩陣輸入

6、模塊 矩陣運算模塊矩陣輸出模塊8、本程序的流程圖：開始選擇要執(zhí)行的操作作選擇3，進行矩陣乘法運算選擇1，進行矩陣加法運算 選擇2，進行矩陣減法運算輸入n個矩陣A的行數、列數、非零元個數輸出結果結束第四章 詳細設計4.1 函數說明：1、稀疏矩陣的三元組順序表存儲表示：typedef struct /三元組結構 int i,j; /行下標和列下標 int e; /值triple;2、稀疏矩陣存儲表示：typedef struct/ /矩陣結構triple dataMAXSIZE+1; int m,n,t; /矩陣的行數、列數、非零元個數tripletable;3、 主要函數：void Add( )

7、 ;void cut ( ); void mul( );int main( );4.2 算法分析：設計一個矩陣類實現矩陣的運算：class tripletable(包含矩陣的各種運算函數)。輸入矩陣（以三元組形式輸入非零元），輸出矩陣（陣列形式）。tripletable M;int m,n,t,i,j,e,k,c,d; int aMAXSIZEMAXSIZE; cout<<"輸入稀疏矩陣M的行數，列數和非零元個數："cin>>M.m>>M.n>>M.t;for(k=1;k<=M.t;k+)cout<<&quo

8、t;輸入第"<<k<<"個非零元素的行下標，列下標和值:"cin>>M.datak.i>>M.datak.j>>M.datak.e;for(k=1;k<=M.t;k+)aM.datak.iM.datak.j=M.datak.e;cout<<"矩陣M的行列形式為:"<<"n"for(c=1;c<=M.m;c+)for(d=1;d<=M.n;d+)cout<<acd<<" "cout&

9、lt;<endl;矩陣的加法：void Add()/矩陣相加tripletable M;tripletable T;int m,n,t,i,j,e,k,c,d; int aMAXSIZEMAXSIZE=0; /將二維數組初始化為零int bMAXSIZEMAXSIZE=0;int fMAXSIZEMAXSIZE=0;cout<<"輸入稀疏矩陣M的行數，列數和非零元個數："cin>>M.m>>M.n>>M.t;for(k=1;k<=M.t;k+)cout<<"輸入第"<<k

10、<<"個非零元素的行下標，列下標和值:"cin>>M.datak.i>>M.datak.j>>M.datak.e;cout<<"矩陣M的行列形式為:"<<"n"for(k=1;k<=M.t;k+)aM.datak.iM.datak.j=M.datak.e;for(c=1;c<=M.m;c+)for(d=1;d<=M.n;d+)cout<<acd<<" "cout<<endl;cout<

11、<"輸入稀疏矩陣T的行數，列數和非零元個數："cin>>T.m>>T.n>>T.t;if(M.m!=T.m|M.n!=T.n) /檢驗兩矩陣能否相加cout<<"兩矩陣行或列不相等，請重新進入系統輸入!"<<"n" return ;for(k=1;k<=T.t;k+)cout<<"輸入第"<<k<<"個非零元素的行下標，列下標和值:"cin>>T.datak.i>>

12、T.datak.j>>T.datak.e;cout<<"矩陣T的行列形式為:"<<"n"for(k=1;k<=T.t;k+)bT.datak.iT.datak.j=T.datak.e;for(c=1;c<=T.m;c+)for(d=1;d<=T.n;d+)cout<<bcd<<" "cout<<endl;for(c=1;c<=M.m;c+)for(d=1;d<=M.n;d+)fcd=acd+bcd; /兩矩陣行、列號相等的元素之和為結

13、果矩陣對應元素cout<<"兩矩陣相加后的行列形式為："<<endl;for(c=1;c<=M.m;c+)for(d=1;d<=M.n;d+)cout<<fcd<<" "cout<<endl;以上主要設計思想：此功能由函數Add( )實現，當用戶選擇該功能時系統即提示用戶初始化要進行加法的兩個矩陣的信息。然后檢測這兩個矩陣是否符合矩陣相加的規(guī)則，如果符合，進行加法。否則重新進入系統輸入數據。最后輸出結果。矩陣的減法：void cut()/矩陣相減tripletable M;tripl

14、etable T;int m,n,t,i,j,e,k,c,d; int aMAXSIZEMAXSIZE=0;int bMAXSIZEMAXSIZE=0;int fMAXSIZEMAXSIZE=0;cout<<"輸入稀疏矩陣M的行數，列數和非零元個數："cin>>M.m>>M.n>>M.t;for(k=1;k<=M.t;k+)cout<<"輸入第"<<k<<"個非零元素的行下標，列下標和值:"cin>>M.datak.i>>

15、M.datak.j>>M.datak.e;cout<<"矩陣M的行列形式為:"<<"n"for(k=1;k<=M.t;k+)aM.datak.iM.datak.j=M.datak.e;for(c=1;c<=M.m;c+)for(d=1;d<=M.n;d+)cout<<acd<<" "cout<<endl;cout<<"輸入稀疏矩陣T的行數，列數和非零元個數："cin>>T.m>>T.n>

16、;>T.t;if(M.m!=T.m|M.n!=T.n) /檢驗兩矩陣能否進行減法運算cout<<"兩矩陣行或列不相等，請重新進入系統輸入!"<<"n"return ;for(k=1;k<=T.t;k+)cout<<"輸入第"<<k<<"個非零元素的行下標，列下標和值:"cin>>T.datak.i>>T.datak.j>>T.datak.e;cout<<"矩陣T的行列形式為:"

17、<<"n"for(k=1;k<=T.t;k+)bT.datak.iT.datak.j=T.datak.e;for(c=1;c<=T.m;c+)for(d=1;d<=T.n;d+)cout<<bcd<<" "cout<<endl;for(c=1;c<=M.m;c+)for(d=1;d<=M.n;d+)fcd=acd-bcd; /兩矩陣行、列號相等的元素之差為結果矩陣對應元素cout<<"兩矩陣相減后的行列形式為："<<endl;for(

18、c=1;c<=M.m;c+)for(d=1;d<=M.n;d+)cout<<fcd<<" "cout<<endl;以上主要設計思想：此功能由函數cut( )實現，當用戶選擇該功能時系統即提示用戶初始化要進行減法的兩個矩陣的信息。然后檢測這兩個矩陣是否符合矩陣相減的規(guī)則，如果符合，進行減法運算。否則重新進入系統輸入數據。最后輸出結果。矩陣的乘法：void mul()/矩陣相乘tripletable M;tripletable T;int m,n,t,i,j,e,k,c,d; int aMAXSIZEMAXSIZE=0;int b

19、MAXSIZEMAXSIZE=0;int fMAXSIZEMAXSIZE=0;cout<<"輸入稀疏矩陣M的行數，列數和非零元個數："cin>>M.m>>M.n>>M.t;for(k=1;k<=M.t;k+)cout<<"輸入第"<<k<<"個非零元素的行下標，列下標和值:"cin>>M.datak.i>>M.datak.j>>M.datak.e;cout<<"矩陣M的行列形式為:&quo

20、t;<<"n"for(k=1;k<=M.t;k+)aM.datak.iM.datak.j=M.datak.e;for(c=1;c<=M.m;c+)for(d=1;d<=M.n;d+)cout<<acd<<" "cout<<endl;cout<<"輸入稀疏矩陣T的行數，列數和非零元個數："cin>>T.m>>T.n>>T.t;if(M.n!=T.m)cout<<"第一個矩陣的行和第二個矩陣的列不相等，請

21、重新進入系統輸入!"<<"n"/判斷兩個矩陣能否進行乘法運算return ;for(k=1;k<=T.t;k+)cout<<"輸入第"<<k<<"個非零元素的行下標，列下標和值:"cin>>T.datak.i>>T.datak.j>>T.datak.e;cout<<"矩陣T的行列形式為:"<<"n"for(k=1;k<=T.t;k+)bT.datak.iT.datak

22、.j=T.datak.e;for(c=1;c<=T.m;c+)for(d=1;d<=T.n;d+)cout<<bcd<<" "cout<<endl;for(c=1;c<=M.m;c+) /乘法的結果矩陣的元素為兩矩陣對應行、列元素依次相乘之和for(d=1;d<=M.n;d+)int g,x;int sum=0; for(g=1;g<=M.n;g+)x=acg*bgd;sum=sum+x;fcd=sum;cout<<"兩矩陣相乘后的行列形式為："<<endl;for

23、(c=1;c<=M.m;c+)for(d=1;d<=T.n;d+)cout<<fcd<<" "cout<<endl;以上主要設計思想為：此功能由函數mul( )實現。當用戶選擇該功能，系統提示輸入要進行相乘的兩個矩陣的詳細信息。然后檢測兩者是否可以相乘，如果不能，則重新進入系統輸入，最后得到結果。第五章 調試分析測試數據：（1）、矩陣的加法：矩陣M的行數、列數、非零個數：3、3、4；非零元素的三元組表示為：111,112,223,234；矩陣T的行數、列數、非零個數：3、3、4；非零元素的三元組表示為：125,216,227,

24、338;兩矩陣相加后的矩陣陣列形式為：1 7 0 6 10 4 0 0 8（2）、矩陣的減法：矩陣M的行數、列數、非零個數：3、3、4；非零元素的三元組表示為：111,112,223,234；矩陣T的行數、列數、非零個數：3、3、4；非零元素的三元組表示為：125,216,227,338;兩矩陣相加后的矩陣陣列形式為：1 -3 0 -6 -4 4 0 0 -8（3）、矩陣的乘法：矩陣M的行數、列數、非零個數：4、3、4；非零元素的三元組表示為：111,112,223,234；矩陣T的行數、列數、非零個數：3、4、4；非零元素的三元組表示為：125,216,227,338;兩矩陣相加后的矩陣陣列

25、形式為：12 19 0 0 18 21 32 0 0 0 0 0 0 0 0 0遇到的問題：二維數組的初始化問題；解決方法：利用int aMAXSIZEMAXSIZE=0;語句，很好的將數組aMAXSIZEMAXSIZE的所有元素都初始化為零。第六章 測試結果（1）、矩陣的加法：矩陣M的行數、列數、非零個數：3、3、4；非零元素的三元組表示為：111,112,223,234；矩陣T的行數、列數、非零個數：3、3、4；非零元素的三元組表示為：125,216,227,338;兩矩陣相加后的矩陣陣列形式為：1 7 0 6 10 4 0 0 8（2）、矩陣的減法：矩陣M的行數、列數、非零個數：3、3、

26、4；非零元素的三元組表示為：111,112,223,234；矩陣T的行數、列數、非零個數：3、3、4；非零元素的三元組表示為：125,216,227,338;兩矩陣相加后的矩陣陣列形式為：1 -3 0 -6 -4 4 0 0 -8（3）、矩陣的乘法：矩陣M的行數、列數、非零個數：4、3、4；非零元素的三元組表示為：111,112,223,234；矩陣T的行數、列數、非零個數：3、4、4；非零元素的三元組表示為：125,216,227,338;兩矩陣相加后的矩陣陣列形式為：12 19 0 0 18 21 32 0 0 0 0 0 0 0 0 0第七章 課程設計總結由于本程序要求實現用三元組的形式

27、對稀疏矩陣進行輸入，用陣列的形式對矩陣進行輸出，所以，一開始的想法構思存在困難。當發(fā)現運用二維數組進行矩陣輸出時，對二維數組的賦值又出現了問題，但最終運用數組初始賦值為零的方法解決了這個問題?？偟膩碚f，此程序的理解難度并不高，整個程序的算法思想也比較簡單，主要還是一些細節(jié)性問題需要去克服。通過此次課程設計，使我更加扎實的掌握了有關三元組表示稀疏矩陣方面的知識，在設計過程中雖然遇到了一些問題，但經過一次又一次的思考，一遍又一遍的檢查終于找出了原因所在，也暴露出了前期我在這方面的知識欠缺和經驗不足。 在課程設計過程中，不斷發(fā)現錯誤，不斷改正，不斷領悟，不斷獲取。最終的檢測調試環(huán)節(jié)，本身就是在踐行“

28、過而能改，善莫大焉”的知行觀。這次課程設計終于順利完成了，在設計中遇到了很多問題，最后在一些資料和書本的幫助下，終于游逆而解。參考文獻：1譚浩強著.C+程序設計（第二版）M.北京：清華大學出版社，2009.52嚴蔚敏、吳偉民 主編數據結構 （C語言版）M. 清華大學出版社 2004.11附錄（源代碼）：#include <iostream>using namespace std;#define MAXSIZE 100typedef struct /三元組結構 int i,j; /矩陣行下標和列下標 int e; /值triple;typedef struct/矩陣結構triple

29、dataMAXSIZE+1; int m,n,t; /矩陣的行數、列數、非零元個數tripletable;void Add()/矩陣相加tripletable M;tripletable T;int m,n,t,i,j,e,k,c,d; int aMAXSIZEMAXSIZE=0;int bMAXSIZEMAXSIZE=0;int fMAXSIZEMAXSIZE=0;cout<<"輸入稀疏矩陣M的行數，列數和非零元個數："cin>>M.m>>M.n>>M.t;for(k=1;k<=M.t;k+)cout<<&

30、quot;輸入第"<<k<<"個非零元素的行下標，列下標和值:"cin>>M.datak.i>>M.datak.j>>M.datak.e;cout<<"矩陣M的行列形式為:"<<"n"for(k=1;k<=M.t;k+)aM.datak.iM.datak.j=M.datak.e;for(c=1;c<=M.m;c+)for(d=1;d<=M.n;d+)cout<<acd<<" "co

31、ut<<endl;cout<<"輸入稀疏矩陣T的行數，列數和非零元個數："cin>>T.m>>T.n>>T.t;if(M.m!=T.m|M.n!=T.n)cout<<"兩矩陣行或列不相等，請重新進入系統輸入!"<<"n"return ;for(k=1;k<=T.t;k+)cout<<"輸入第"<<k<<"個非零元素的行下標，列下標和值:"cin>>T.data

32、k.i>>T.datak.j>>T.datak.e;cout<<"矩陣T的行列形式為:"<<"n"for(k=1;k<=T.t;k+)bT.datak.iT.datak.j=T.datak.e;for(c=1;c<=T.m;c+)for(d=1;d<=T.n;d+)cout<<bcd<<" "cout<<endl;for(c=1;c<=M.m;c+)for(d=1;d<=M.n;d+)fcd=acd+bcd;cout<

33、;<"兩矩陣相加后的行列形式為："<<endl;for(c=1;c<=M.m;c+)for(d=1;d<=M.n;d+)cout<<fcd<<" "cout<<endl;void cut()/矩陣相減tripletable M;tripletable T;int m,n,t,i,j,e,k,c,d; int aMAXSIZEMAXSIZE=0;int bMAXSIZEMAXSIZE=0;int fMAXSIZEMAXSIZE=0;cout<<"輸入稀疏矩陣M的行數，列

34、數和非零元個數："cin>>M.m>>M.n>>M.t;for(k=1;k<=M.t;k+)cout<<"輸入第"<<k<<"個非零元素的行下標，列下標和值:"cin>>M.datak.i>>M.datak.j>>M.datak.e;cout<<"矩陣M的行列形式為:"<<"n"for(k=1;k<=M.t;k+)aM.datak.iM.datak.j=M.dat

35、ak.e;for(c=1;c<=M.m;c+)for(d=1;d<=M.n;d+)cout<<acd<<" "cout<<endl;cout<<"輸入稀疏矩陣T的行數，列數和非零元個數："cin>>T.m>>T.n>>T.t;if(M.m!=T.m|M.n!=T.n)cout<<"兩矩陣行或列不相等，請重新進入系統輸入!"<<"n"return ;for(k=1;k<=T.t;k+)cout

36、<<"輸入第"<<k<<"個非零元素的行下標，列下標和值:"cin>>T.datak.i>>T.datak.j>>T.datak.e;cout<<"矩陣T的行列形式為:"<<"n"for(k=1;k<=T.t;k+)bT.datak.iT.datak.j=T.datak.e;for(c=1;c<=T.m;c+)for(d=1;d<=T.n;d+)cout<<bcd<<"

37、 "cout<<endl;for(c=1;c<=M.m;c+)for(d=1;d<=M.n;d+)fcd=acd-bcd;cout<<"兩矩陣相減后的行列形式為："<<endl;for(c=1;c<=M.m;c+)for(d=1;d<=M.n;d+)cout<<fcd<<" "cout<<endl;void mul()/矩陣相乘tripletable M;tripletable T;int m,n,t,i,j,e,k,c,d; int aMAXSIZ

38、EMAXSIZE=0;int bMAXSIZEMAXSIZE=0;int fMAXSIZEMAXSIZE=0;cout<<"輸入稀疏矩陣M的行數，列數和非零元個數："cin>>M.m>>M.n>>M.t;for(k=1;k<=M.t;k+)cout<<"輸入第"<<k<<"個非零元素的行下標，列下標和值:"cin>>M.datak.i>>M.datak.j>>M.datak.e;cout<<"矩陣M的行列形式為:"<<"n"for(k=1;k<=M.t;k+)aM.datak.iM.datak.j=M.datak.e;for(c=1;c<=M.m;c+)for(d=1;d<=M.n;d+)cout<<acd<<" "cout<<endl;cout<<