稀疏矩陣相乘課程設(shè)計報告馬良

1、學(xué) 號： 34課 程 設(shè) 計題 目稀疏矩陣相乘學(xué) 院計算機科學(xué)與技術(shù)專 業(yè)計算機科學(xué)與技術(shù)卓越工程師班 級計算機zy1301姓 名馬良指導(dǎo)教師楊克儉2014年12月25日目 錄課程設(shè)計任務(wù)書11問題描述21.1問題描述21.2基本要求31.3測試數(shù)據(jù)32.實現(xiàn)分析33程序設(shè)計33.1存儲結(jié)構(gòu)設(shè)計33.1.1三元組表示稀疏矩陣33.1.2十字鏈表表示稀疏矩陣43.2主要算法設(shè)計53.2.1程序主要函數(shù)原型及功能53.2.2各函數(shù)的實現(xiàn)63.2.3 程序流程圖114.調(diào)試報告114.1調(diào)試中的問題114.2設(shè)計分析125. 程序運行結(jié)果126.經(jīng)驗和體會137.源程序14參考文獻：22本科生課程設(shè)

2、計成績評定表23課程設(shè)計任務(wù)書學(xué)生姓名： 馬良 專業(yè)班級： 計算機zy1301班 指導(dǎo)教師： 楊克儉 工作單位： 計算機科學(xué)系 題 目: 稀疏矩陣相乘 初始條件： 稀疏矩陣是指那些多數(shù)元素為零的矩陣。利用“稀疏”特點進行存儲和計算可以大大節(jié)省存儲空間，提高計算效率。實現(xiàn)一個能進行稀疏矩陣基本運算的運算器。（1） 以“帶行邏輯鏈接信息”的三元組順序表表示稀疏矩陣（2） 實現(xiàn)兩個矩陣相乘的運算。（3） 稀疏矩陣采用十字鏈表表示，而運算結(jié)果的矩陣則以通常的陣列形式列出。（4） 測試用例見嚴(yán)蔚敏數(shù)據(jù)結(jié)構(gòu)習(xí)題集(C語言版)p136。要求完成的主要任務(wù): （包括課內(nèi)實踐工作量及其技術(shù)要求，以及說明書撰寫等

3、具體要求）課內(nèi)實踐報告按學(xué)校規(guī)定格式用A4紙打?。〞鴮懀?，并應(yīng)包含如下內(nèi)容： 1. 問題描述簡述題目要解決的問題是什么。2. 設(shè)計存儲結(jié)構(gòu)設(shè)計、主要算法設(shè)計（用類C/C+語言或用框圖描述）、測試用例設(shè)計；3. 調(diào)試報告調(diào)試過程中遇到的問題是如何解決的；對設(shè)計和編碼的討論和分析。4. 經(jīng)驗和體會（包括對算法改進的設(shè)想）5. 附源程序清單和運行結(jié)果。源程序要加注釋。如果題目規(guī)定了測試數(shù)據(jù)，則運行結(jié)果要包含這些測試數(shù)據(jù)和運行輸出。說明：1. 設(shè)計報告、程序不得相互抄襲和拷貝；若有雷同，則所有雷同者成績均為0分。2. 凡拷貝往年任務(wù)書或課內(nèi)實踐充數(shù)者，成績一律無效，以0分記。時間安排：1第16周完成，

4、驗收時間為12月26日（星期五）下午2驗收地點：實驗中心3驗收內(nèi)容：可執(zhí)行程序與源代碼、課內(nèi)實踐報告書。指導(dǎo)教師簽名： 2014年11月4日系主任（或責(zé)任教師）簽名： 年 月 日課程設(shè)計報告書1問題描述1.1問題描述稀疏矩陣是指那些多數(shù)元素為零的矩陣。利用“稀疏”特點進行存儲和計算可以大大節(jié)省存儲空間，提高計算效率。實現(xiàn)一個能進行稀疏矩陣基本運算的運算器。1.2基本要求以“帶行邏輯鏈接信息”的三元組順序表表示稀疏矩陣，實現(xiàn)兩個矩陣相乘的運算。稀疏矩陣采用十字鏈表表示，而運算結(jié)果的矩陣則以通常的陣列形式列出。1.3測試數(shù)據(jù)測試用例：嚴(yán)蔚敏數(shù)據(jù)結(jié)構(gòu)習(xí)題集(C語言版)p136。4 -3 0 0 1

5、3 0 0 0 -6 00 0 0 8 0 4 2 0 8 0 00 0 1 0 0 * 0 1 0 = 0 1 00 0 0 0 70 1 0 0 0 0 0 0 0 02.實現(xiàn)分析（1） 根據(jù)題目要求，稀疏矩陣采用三元組法順序輸入，十字鏈表表示。只存儲稀疏矩陣中極少的非零元素。（2） 各元素按照在原來矩陣中的位置行優(yōu)先進行存放。（3） 在稀疏矩陣十字鏈表的表示中，每一行都是一個帶附加頭結(jié)點的循環(huán)行鏈表，每一列都是一個帶附加頭結(jié)點的循環(huán)列鏈表。（4） 逐個尋找兩個矩陣中非零元的位置，第一個矩陣從第一行開始，第二個矩陣從第一列開始，逐漸相乘相加，得到第三個矩陣。（5） 如果矩陣中非零元素個數(shù)比

6、矩陣元素個數(shù)多，返回錯誤信息，程序結(jié)束。（6） 若輸入成功，輸出三個矩陣。3程序設(shè)計3.1存儲結(jié)構(gòu)設(shè)計3.1.1三元組表示稀疏矩陣只存儲在矩陣中極少數(shù)的非零元素，用來唯一確定一個矩陣元素。在三元組數(shù)組中，各矩陣元素按在原矩陣中的位置，以行優(yōu)先的順序依次存放，另外還要存儲原矩陣的行數(shù)、列數(shù)和非零元素個數(shù)struct Trituple /三元組類Trituple int row,col; /非零元素的行號、列號float value; /非零元素的值Trituple& operator=(Trituple &x) row=x.row;col=x.col;value=x.value; 3.1.2十字

7、鏈表表示稀疏矩陣在稀疏矩陣十字鏈表的表示中，每一行都是一個帶附加頭結(jié)點的循環(huán)行鏈表，每一列都是一個帶附加頭結(jié)點的循環(huán)列鏈表。所有的結(jié)點都是結(jié)點類Node的對象。Node類有一個head域，用來區(qū)分該結(jié)點是附加頭結(jié)點還是非零元素結(jié)點。每個附加頭結(jié)點有三個域：d、r、next。第i個行鏈表和第i個列鏈表是一個附加頭結(jié)點，r域存放第i行第一個結(jié)點的地址，d域存放第i列第一個結(jié)點的地址， next域鏈接到第i+1個附加頭結(jié)點。每個非零元素結(jié)點有6個域：head，row，col，d，value。r是行鏈表指針，d是列鏈表指針。struct Trituple /三元組類Trituple int row,c

8、ol; /非零元素的行號、列號float value; /非零元素的值; class Node;class SparseMatrix /稀疏矩陣的類定義friend ostream&operator(istream&,SparseMatrix&);/友元函數(shù)：輸入流操作符重載public:SparseMatrix(); /構(gòu)造函數(shù)SparseMatrix(int a,int b); /重載構(gòu)造函數(shù)SparseMatrix(SparseMatrix& T); /復(fù)制構(gòu)造函數(shù)SparseMatrix()makeEmpty(); /析構(gòu)函數(shù)void Init(int a,int b); /矩陣初始化

9、函數(shù)void makeEmpty(); /清空矩陣void Insert(int a,int b,float c); /插入矩陣元素Node *Locate(int i); /定位附加頭結(jié)點SparseMatrix Cheng(SparseMatrix b); /兩個矩陣相乘SparseMatrix &operator=( SparseMatrix &T); /重載賦值運算符private:int Row,Col,Terms,t; /矩陣的總行數(shù)，總列數(shù)，非零元素個數(shù)和普通變量；Node*headNode; /稀疏矩陣的總表頭;class Node /矩陣結(jié)點類的定義friend class

10、SparseMatrix;public:Node():head(true) r=d=this; /建立附加頭結(jié)點Node(Trituple *t) /建立非零元素結(jié)點triple.col=t-col;triple.row=t-row;triple.value=t-value;r=d=this;head=false;Node*d,*r; /行列鏈表指針bool head;union Trituple triple; Node*next; ;3.2主要算法設(shè)計3.2.1程序主要函數(shù)原型及功能1 首先定義兩個類：class Node /矩陣結(jié)點類定義class SparseMatrix /稀疏矩陣的

11、類定義2 主要函數(shù)原型及功能：void Init(int a,int b)功能：主要完成初始化稀疏矩陣，采用三元組順序輸入，行優(yōu)先存放。并且判斷輸入是否符合常規(guī)，若不符合，返回錯誤信息。 void makeEmpty() 功能：將矩陣清空，釋放存儲空間。用于析構(gòu)函數(shù)中。 void Insert(int a,int b,float c) 功能：用于向矩陣中插入元素，分兩種情況：1）先定位列再尋找行；2）先定位行再尋找列。另外插入后要確定插入的位置是否符合矩陣的設(shè)置，如果不符合，返回錯誤信息。Node *Locate(int i) 功能：對附加頭結(jié)點進行定位。SparseMatrix Cheng(

12、SparseMatrix b)功能：通過確定列頭指針遍歷實現(xiàn)稀疏矩陣的相乘，判斷是否符合常規(guī)，若不符合，返回錯誤信息。SparseMatrix &operator=( SparseMatrix &T);功能：重載賦值運算符。void main()功能：完成對函數(shù)的調(diào)用和與用戶的交互。3.2.2各函數(shù)的實現(xiàn)（1） 矩陣初始化函數(shù)的實現(xiàn)： 三元組順序輸入，按照行優(yōu)先順序存儲 函數(shù)void SparseMatrix:Init(int a,int b)的實現(xiàn)：void SparseMatrix:Init(int a,int b) /矩陣初始化函數(shù)的實現(xiàn)Row=a;Col=b;Terms=0;Tritu

13、ple x;x.row=a;x.col=b;x.value=0;headNode=new Node(&x);Node *current; if(a0&b0)t=a=b?a:b;current=new Node();headNode-r=current; for(int i=1;inext=new Node(); current=current-next;elsecout初始化錯誤！endl;（2） 清空矩陣的實現(xiàn) 函數(shù)void SparseMatrix:makeEmpty()的實現(xiàn)：void SparseMatrix:makeEmpty() /清空矩陣的實現(xiàn)Node*del,*current;

14、for(int i=1;id!=Locate(i)del=current-d; /通過列的附加頭結(jié)點向下刪除結(jié)點current-d=del-d;delete del;（3） 插入函數(shù)的實現(xiàn) 1）先定位列再尋找行；2）先定位行再尋找列。另外插入后要確定插入的位置是否符合矩陣的設(shè)置，如果不符合，返回錯誤信息。 函數(shù)void SparseMatrix:Insert(int a,int b,float c)的實現(xiàn)：void SparseMatrix:Insert(int a,int b,float c) /插入函數(shù)的實現(xiàn)Trituple x;x.row=a;x.col=b;x.value=c;if(a

15、Row&bCol)Node *NewNode=new Node(&x),*current,*head;head=Locate(a); /先定位行再尋找列current=head-r;if(current=head)current-r=NewNode;NewNode-r=current;elsewhile(current-triple.colr!=head)current=current-r; NewNode-r=current-r;current-r=NewNode; head=Locate(b); /先定位列再尋找行current=head-d;if(current=head)current

16、-d=NewNode;NewNode-d=current;elsewhile(current-triple.rowd!=head)current=current-d;NewNode-d=current-d;current-d=NewNode;Terms+; elsecout結(jié)點位置非法，請重新輸入r;for(int j=1;jnext;return current;（5） 矩陣乘法的實現(xiàn) 函數(shù)SparseMatrix SparseMatrix:Cheng(SparseMatrix b)的實現(xiàn)：SparseMatrix SparseMatrix:Cheng(SparseMatrix b) /矩陣

17、乘法的實現(xiàn)if(this-Col=b.Row)SparseMatrix C(this-Row,b.Col); /以A矩陣的行和b矩陣的列為行列建立稀疏矩陣float value;Node *Row_head,*Col_head; /設(shè)兩個指針，一個充當(dāng)行頭指針，一個為列指針 for(int i=1;i=t;i+) /先確定行，再求出C矩陣在該行各列的元素for(int j=1;jr!=Locate(i) /假如行中還有元素不為零就找與之匹配的元素相乘Row_head=Row_head-r;Col_head=Col_head-d; while(Row_head-triple.col!=Col_h

18、ead-triple.row&Col_head-d!=b.Locate(j) /假如行列不相等而且對應(yīng)列還有元素，就繼續(xù)找匹配的元素否則判斷再循環(huán)if(Row_head-triple.colCol_head-triple.row)Col_head=Col_head-d;else if(Row_head-r=Locate(i)Col_head=Col_head-d; /假如b矩陣該列元素比a矩陣該行元素多elseRow_head=Row_head-r; /則b中該列元素已經(jīng)無法找到能相乘元素則往下推直至跳出循環(huán)if(Col_head-d!=b.Locate(j)|Col_head-triple.

19、row=Row_head-triple.col)value+=Row_head-triple.value*Col_head-triple.value;if(value!=0)C.Insert(i,j,value);return C;elseSparseMatrix C;cerr兩個矩陣不能相乘！Row=T.Row;this-Col=T.Col;Node *current;for(int i=1;ir!=current)current=current-r; /通過行遍歷逐個賦值this-Insert(current-triple.row,current-triple.col,current-tr

20、iple.value);return *this;（7） 主函數(shù)設(shè)計void main() SparseMatrix A,B,C;cout稀疏矩陣的乘法endl;cout請輸入矩陣A：A;cout請輸入矩陣B：B; cout矩陣A為:endl;coutAendl;cout矩陣B為:endl;coutBendl;cout兩個矩陣的乘積為：endl;coutA.Cheng(B)endl;開始進行矩陣乘法運算并包含必要的判斷輸入矩陣的行數(shù)、列數(shù)、非零元個數(shù)，非零元行號、列號、值輸出三個矩陣結(jié)束3.2.3 程序流程圖本次程序流程圖如下4.調(diào)試報告4.1調(diào)試中的問題 整個程序的算法沒有問題，不過在編程過

21、程中出了許多格式和語法上的錯誤。通過軟件的提示，一個個改正錯誤。 在使用十字鏈表寫程序的過程中，由于各種指針和指針域非常多，經(jīng)?；煜鱾€指針的指向，以至于整個程序運行不了。后來我在紙上細(xì)細(xì)將頭結(jié)點和非零元素的指針域從頭分析了一邊，重寫了十字鏈表的部分實現(xiàn)，后又修改了幾處小錯誤，終于完成了代碼的正確書寫。 在寫稀疏矩陣類定義時使用了有關(guān)結(jié)點類的指針，而結(jié)點類放在稀疏矩陣類后定義。在稀疏矩陣類定義前沒有聲明結(jié)點類，使程序?qū)懲旰笥袔讉€函數(shù)編譯出現(xiàn)問題。剛開始只修改函數(shù)，卻怎么也修改不了。過了一段時間之后才想起實際的原因。于是將程序修改正確。4.2設(shè)計分析算法的時間復(fù)雜度為：O（Rows*Cols)。

22、有時矩陣的非零元素個數(shù)太多會導(dǎo)致程序崩潰。另外根據(jù)實際的矩陣情況，這次的設(shè)計沒有使用模板，而僅僅是使用float類型。個人感覺float類型已經(jīng)能夠滿足稀疏矩陣的使用要求。由于課程設(shè)計的要求，這次代碼只實現(xiàn)了稀疏矩陣的乘法，也可以加入加減法、轉(zhuǎn)置的運算。同時可以在主函數(shù)中加入選擇菜單。5. 程序運行結(jié)果經(jīng)過對程序錯誤的修改后，程序執(zhí)行，經(jīng)過分析，程序運行結(jié)果正確，滿足題目要求！運行結(jié)果主要截圖如下：6.經(jīng)驗和體會這次的題目是稀疏矩陣的乘法。本來拿到這個題目的時候感覺應(yīng)該很簡單，因為雖說這部分的內(nèi)容在課本上是不要求掌握的內(nèi)容，但畢竟課本上都有，如果不會的話可以參考一下課本上的代碼。可看到任務(wù)書的

23、時候才知道沒那么簡單。當(dāng)時我根本不知道什么是十字鏈表和“帶行邏輯鏈接信息”，百度后才失望的發(fā)現(xiàn)在課本上關(guān)于十字鏈表的介紹竟然只有半面。我只有在認(rèn)真學(xué)習(xí)了三元組法乘法的實現(xiàn)了之后，在網(wǎng)上查找學(xué)習(xí)有關(guān)十字鏈表的知識學(xué)習(xí)?？墒鞘宙湵淼闹羔樣虿糠治疫€是迷迷糊糊的。于是我決定先試著寫一寫。就這樣，我慢慢的將整個程序磨了出來。感覺程序還是要先有一個整體規(guī)劃，然后一氣呵成比較好。就像這次，我在十字鏈表的指針那里有疑問，寫了一半就已經(jīng)很晚了，就決定第二天繼續(xù)寫。不過第二天再開始的時候，卻對前一天寫的程序有些許的陌生，思路也忘記了好多。下次一定要避免這種情況的發(fā)生。即使實在寫不完，也要先記下此時的思路，以便第

24、二天復(fù)習(xí)。這次數(shù)據(jù)結(jié)構(gòu)課內(nèi)設(shè)計是我第一次完整的編寫這么長的程序，收獲特別多。相對于其他同學(xué)3、4頁的代碼，我的8頁代碼顯得特別多，不過一分耕耘一分收獲。我接下來還要好好研究一下數(shù)據(jù)結(jié)構(gòu)這門課，學(xué)無止境，繼續(xù)加油吧！7.源程序#include#includeusing namespace std;struct Trituple /三元組類Trituple int row,col; /非零元素的行號、列號float value; /非零元素的值; class Node;class SparseMatrix /稀疏矩陣的類定義friend ostream&operator(istream&,Spar

25、seMatrix&);/友元函數(shù)：輸入流操作符重載public:SparseMatrix(); /構(gòu)造函數(shù)SparseMatrix(int a,int b); /重載構(gòu)造函數(shù)SparseMatrix(SparseMatrix& T); /復(fù)制構(gòu)造函數(shù)SparseMatrix()makeEmpty(); /析構(gòu)函數(shù)void Init(int a,int b); /矩陣初始化函數(shù)void makeEmpty(); /清空矩陣void Insert(int a,int b,float c); /插入矩陣元素Node *Locate(int i); /定位附加頭結(jié)點SparseMatrix Cheng

26、(SparseMatrix b); /兩個矩陣相乘SparseMatrix &operator=( SparseMatrix &T); /重載賦值運算符private:int Row,Col,Terms,t; /矩陣的總行數(shù)，總列數(shù)，非零元素個數(shù)和普通變量；Node*headNode; /稀疏矩陣的總表頭;class Node /矩陣結(jié)點類定義friend class SparseMatrix;public:Node():head(true) r=d=this; /建立附加頭結(jié)點Node(Trituple *t) /建立非零元素結(jié)點triple.col=t-col;triple.row=t-r

27、ow;triple.value=t-value;r=d=this;head=false;Node*d,*r; /行列鏈表指針bool head;union Trituple triple; Node*next; /聯(lián)合;SparseMatrix: SparseMatrix():Row(0),Col(0),Terms(0) /構(gòu)造函數(shù)的實現(xiàn)Trituple x;x.row=Row;x.col=Col;x.value=0;SparseMatrix: SparseMatrix(int a,int b):Row(a),Col(b) /重載構(gòu)造函數(shù)的實現(xiàn)Trituple x;x.row=a;x.col=

28、b;x.value=0;Terms=0;t=a=b?a:b;Node *current;headNode=new Node(&x);current=headNode-r=new Node();for(int i=1;inext=new Node();current=current-next;SparseMatrix: SparseMatrix(SparseMatrix&T) /復(fù)制構(gòu)造函數(shù)的實現(xiàn)Init(T.Row,T.Col);Node*current;for(int i=1;ir!=T.Locate(i) /通過行遍歷逐個賦值current=current-r; Insert(curren

29、t-triple.row,current-triple.col,current-triple.value);void SparseMatrix:Init(int a,int b) /矩陣初始化函數(shù)的實現(xiàn)Row=a;Col=b;Terms=0;Trituple x;x.row=a;x.col=b;x.value=0;headNode=new Node(&x);Node *current; if(a0&b0)t=a=b?a:b;current=new Node();headNode-r=current; for(int i=1;inext=new Node(); current=current-n

30、ext;elsecout初始化錯誤！r;for(int j=1;jnext;return current;void SparseMatrix:Insert(int a,int b,float c) /插入函數(shù)的實現(xiàn)Trituple x;x.row=a;x.col=b;x.value=c;if(aRow&bCol)Node *NewNode=new Node(&x),*current,*head;head=Locate(a); /先定位行再尋找列current=head-r;if(current=head)current-r=NewNode;NewNode-r=current;elsewhile

31、(current-triple.colr!=head)current=current-r; NewNode-r=current-r;current-r=NewNode; head=Locate(b); /先定位列再尋找行current=head-d;if(current=head)current-d=NewNode;NewNode-d=current;elsewhile(current-triple.rowd!=head)current=current-d;NewNode-d=current-d;current-d=NewNode;Terms+; elsecout結(jié)點位置非法，請重新輸入(is

32、tream &in, SparseMatrix &b) /輸入函數(shù)重載int R,C,m,n,S;float a;cout請輸入矩陣的行數(shù)、列數(shù)、非零元素個數(shù)：RCS;b.Init(R,C);if(S(R*C)cerr輸入元素個數(shù)超過設(shè)定endl;exit(1);elsecout請輸入各非零元素的行數(shù)、列數(shù)、值endl;cout行數(shù) 列數(shù) 值endl;for(int i=1;i=S;i+) /輸入元素結(jié)點并且插入矩陣coutimna;b.Insert(m,n,a); /插入結(jié)點return in;ostream &operator(ostream &out, SparseMatrix &b)

33、/輸出函數(shù)重載Node *x;for(int i=1;ir;for(int j=1;jhead=false&(x-triple.col=j)cout.width(4);outtriple.value;x=x-r;else if(x-head=true)for(j;j=b.t;j+)cout.width(4);cout0;break;elsecout.width(4);cout0;coutRow=T.Row;this-Col=T.Col;Node *current;for(int i=1;ir!=current)current=current-r; /通過行遍歷逐個賦值this-Insert(c

34、urrent-triple.row,current-triple.col,current-triple.value);return *this;void SparseMatrix:makeEmpty() /清空矩陣的實現(xiàn)Node*del,*current;for(int i=1;id!=Locate(i)del=current-d; /通過列的附加頭結(jié)點向下刪除結(jié)點current-d=del-d;delete del;SparseMatrix SparseMatrix:Cheng(SparseMatrix b) /矩陣乘法的實現(xiàn)if(this-Col=b.Row)SparseMatrix C(this-Row,b.Col); /以A矩陣的行