稀疏矩陣相乘課程設(shè)計(jì)報(bào)告

1、<p><b>　　課 程 設(shè) 計(jì)</b></p><p><b>　　目 錄</b></p><p><b>　　課程設(shè)計(jì)任務(wù)書1</b></p><p><b>　　1．問題描述2</b></p><p><b>　　1.

2、1問題描述2</b></p><p><b>　　1.2基本要求3</b></p><p><b>　　1.3測(cè)試數(shù)據(jù)3</b></p><p><b>　　2.實(shí)現(xiàn)分析3</b></p><p><b>　　3．程序設(shè)計(jì)3</b>&

3、lt;/p><p>　　3.1存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)3</p><p>　　3.1.1三元組表示稀疏矩陣3</p><p>　　3.1.2十字鏈表表示稀疏矩陣4</p><p>　　3.2主要算法設(shè)計(jì)5</p><p>　　3.2.1程序主要函數(shù)原型及功能5</p><p>　　3.2.2各函數(shù)的實(shí)

4、現(xiàn)6</p><p>　　3.2.3 程序流程圖11</p><p><b>　　4.調(diào)試報(bào)告11</b></p><p>　　4.1調(diào)試中的問題11</p><p>　　4.2設(shè)計(jì)分析12</p><p>　　5. 程序運(yùn)行結(jié)果12</p><p>　　6.經(jīng)

5、驗(yàn)和體會(huì)13</p><p><b>　　7.源程序14</b></p><p><b>　　參考文獻(xiàn)：22</b></p><p>　　本科生課程設(shè)計(jì)成績?cè)u(píng)定表23</p><p><b>　　課程設(shè)計(jì)任務(wù)書</b></p><p>　　學(xué)生姓

6、名： 馬良 專業(yè)班級(jí)： 計(jì)算機(jī)zy1301班 </p><p>　　指導(dǎo)教師： 楊克儉 工作單位： 計(jì)算機(jī)科學(xué)系 </p><p>　　題 目: 稀疏矩陣相乘 </p><p><b>　　初始條件：</b></p&g

7、t;<p>　　稀疏矩陣是指那些多數(shù)元素為零的矩陣。利用“稀疏”特點(diǎn)進(jìn)行存儲(chǔ)和計(jì)算可以大大節(jié)省存儲(chǔ)空間，提高計(jì)算效率。實(shí)現(xiàn)一個(gè)能進(jìn)行稀疏矩陣基本運(yùn)算的運(yùn)算器。</p><p>　　以“帶行邏輯鏈接信息”的三元組順序表表示稀疏矩陣</p><p>　　實(shí)現(xiàn)兩個(gè)矩陣相乘的運(yùn)算。</p><p>　　稀疏矩陣采用十字鏈表表示，而運(yùn)算結(jié)果的矩陣則以通常的陣列形

8、式列出。</p><p>　　測(cè)試用例見嚴(yán)蔚敏《數(shù)據(jù)結(jié)構(gòu)習(xí)題集(C語言版)》p136。</p><p>　　要求完成的主要任務(wù): （包括課內(nèi)實(shí)踐工作量及其技術(shù)要求，以及說明書撰寫等具體要求）</p><p>　　課內(nèi)實(shí)踐報(bào)告按學(xué)校規(guī)定格式用A4紙打?。〞鴮懀?，并應(yīng)包含如下內(nèi)容： </p><p><b>　　1. 問題描述</

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

10、　　調(diào)試過程中遇到的問題是如何解決的；對(duì)設(shè)計(jì)和編碼的討論和分析。</p><p>　　4. 經(jīng)驗(yàn)和體會(huì)（包括對(duì)算法改進(jìn)的設(shè)想）</p><p>　　5. 附源程序清單和運(yùn)行結(jié)果。源程序要加注釋。如果題目規(guī)定了測(cè)試數(shù)據(jù)，則運(yùn)行結(jié)果要包含這些測(cè)試數(shù)據(jù)和運(yùn)行輸出。</p><p><b>　　說明：</b></p><p>　

11、　1. 設(shè)計(jì)報(bào)告、程序不得相互抄襲和拷貝；若有雷同，則所有雷同者成績均為0分。</p><p>　　2. 凡拷貝往年任務(wù)書或課內(nèi)實(shí)踐充數(shù)者，成績一律無效，以0分記。</p><p><b>　　時(shí)間安排：</b></p><p>　　1．第16周完成，驗(yàn)收時(shí)間為12月26日（星期五）下午</p><p>　　2．驗(yàn)收地點(diǎn)

12、：實(shí)驗(yàn)中心</p><p>　　3．驗(yàn)收內(nèi)容：可執(zhí)行程序與源代碼、課內(nèi)實(shí)踐報(bào)告書。</p><p>　　指導(dǎo)教師簽名： 2014年11月4日</p><p>　　系主任（或責(zé)任教師）簽名： 年 月 日</p><p><b>　　課程設(shè)計(jì)報(bào)告書</b></p

13、><p><b>　　1．問題描述</b></p><p><b>　　1.1問題描述</b></p><p>　　稀疏矩陣是指那些多數(shù)元素為零的矩陣。利用“稀疏”特點(diǎn)進(jìn)行存儲(chǔ)和計(jì)算可以大大節(jié)省存儲(chǔ)空間，提高計(jì)算效率。實(shí)現(xiàn)一個(gè)能進(jìn)行稀疏矩陣基本運(yùn)算的運(yùn)算器。</p><p><b>　　1.2

14、基本要求</b></p><p>　　以“帶行邏輯鏈接信息”的三元組順序表表示稀疏矩陣，實(shí)現(xiàn)兩個(gè)矩陣相乘的運(yùn)算。稀疏矩陣采用十字鏈表表示，而運(yùn)算結(jié)果的矩陣則以通常的陣列形式列出。</p><p><b>　　1.3測(cè)試數(shù)據(jù)</b></p><p>　　測(cè)試用例：嚴(yán)蔚敏《數(shù)據(jù)結(jié)構(gòu)習(xí)題集(C語言版)》p136。</p>&

15、lt;p>　　4 -3 0 0 1 3 0 0 0 -6 0</p><p>　　0 0 0 8 0 4 2 0 8 0 0</p><p>　　0 0 1 0 0 * 0 1 0 = 0 1

16、 0</p><p>　　0 0 0 0 70 1 0 0 0 0 0</p><p><b>　　0 0 0</b></p><p><b>　　2.實(shí)現(xiàn)分析</b></p><p>　?。?） 根據(jù)題目要求，稀疏矩陣

17、采用三元組法順序輸入，十字鏈表表示。只存儲(chǔ)稀疏矩陣中極少的非零元素。</p><p>　　（2） 各元素按照在原來矩陣中的位置行優(yōu)先進(jìn)行存放。</p><p>　?。?） 在稀疏矩陣十字鏈表的表示中，每一行都是一個(gè)帶附加頭結(jié)點(diǎn)的循環(huán)行鏈表，每一列都是一個(gè)帶附加頭結(jié)點(diǎn)的循環(huán)列鏈表。</p><p>　?。?） 逐個(gè)尋找兩個(gè)矩陣中非零元的位置，第一個(gè)矩陣從第一行開始，第

18、二個(gè)矩陣從第一列開始，逐漸相乘相加，得到第三個(gè)矩陣。</p><p>　?。?） 如果矩陣中非零元素個(gè)數(shù)比矩陣元素個(gè)數(shù)多，返回錯(cuò)誤信息，程序結(jié)束。</p><p>　?。?） 若輸入成功，輸出三個(gè)矩陣。</p><p><b>　　3．程序設(shè)計(jì)</b></p><p><b>　　3.1存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)</b

19、></p><p>　　3.1.1三元組表示稀疏矩陣</p><p>　　只存儲(chǔ)在矩陣中極少數(shù)的非零元素，用<row,col,value>來唯一確定一個(gè)矩陣元素。在三元組數(shù)組中，各矩陣元素按在原矩陣中的位置，以行優(yōu)先的順序依次存放，另外還要存儲(chǔ)原矩陣的行數(shù)、列數(shù)和非零元素個(gè)數(shù)</p><p>　　struct Trituple</p>

20、<p>　　{ //三元組類Trituple</p><p>　　int row,col; //非零元素的行號(hào)、列號(hào)</p><p>　　float value; //非零元素的值</p><p>　　Trituple& operator=(Trituple &

21、;x)</p><p>　　{row=x.row;col=x.col;value=x.value;}</p><p>　　}; </p><p>　　3.1.2十字鏈表表示稀疏矩陣</p><p>　　在稀疏矩陣十字鏈表的表示中，每一行都是一個(gè)帶附加頭結(jié)點(diǎn)的循環(huán)行鏈表，每一列都是一個(gè)帶附加頭結(jié)點(diǎn)的循環(huán)列鏈表。所有的結(jié)點(diǎn)都是結(jié)點(diǎn)

22、類Node的對(duì)象。Node類有一個(gè)head域，用來區(qū)分該結(jié)點(diǎn)是附加頭結(jié)點(diǎn)還是非零元素結(jié)點(diǎn)。每個(gè)附加頭結(jié)點(diǎn)有三個(gè)域：d、r、next。第i個(gè)行鏈表和第i個(gè)列鏈表是一個(gè)附加頭結(jié)點(diǎn)，r域存放第i行第一個(gè)結(jié)點(diǎn)的地址，d域存放第i列第一個(gè)結(jié)點(diǎn)的地址， next域鏈接到第i+1個(gè)附加頭結(jié)點(diǎn)。每個(gè)非零元素結(jié)點(diǎn)有6個(gè)域：head，row，col，d，value。r是行鏈表指針，d是列鏈表指針。</p><p>　　struct

23、Trituple{ //三元組類Trituple</p><p>　　int row,col; //非零元素的行號(hào)、列號(hào)</p><p>　　float value; //非零元素的值</p><p>　　}; </p><p>　　class Node;<

24、/p><p>　　class SparseMatrix</p><p>　　{ //稀疏矩陣的類定義</p><p>　　friend ostream&operator<<(ostream&,SparseMatrix&);//友元函數(shù)：輸出流操作符重載</p><p>

25、;　　friend istream&operator>>(istream&,SparseMatrix&);//友元函數(shù)：輸入流操作符重載</p><p><b>　　public:</b></p><p>　　SparseMatrix(); //構(gòu)造函數(shù)</p><p>

26、　　SparseMatrix(int a,int b); //重載構(gòu)造函數(shù)</p><p>　　SparseMatrix(SparseMatrix& T); //復(fù)制構(gòu)造函數(shù)</p><p>　　~SparseMatrix(){makeEmpty();} //析構(gòu)函數(shù)</p><p>　　void In

27、it(int a,int b); //矩陣初始化函數(shù)</p><p>　　void makeEmpty(); //清空矩陣</p><p>　　void Insert(int a,int b,float c); //插入矩陣元素</p><p>　　Node *Locate(int i);

28、 //定位附加頭結(jié)點(diǎn)</p><p>　　SparseMatrix Cheng(SparseMatrix b); //兩個(gè)矩陣相乘</p><p>　　SparseMatrix &operator=( SparseMatrix &T); //重載賦值運(yùn)算符</p><p><

29、b>　　private:</b></p><p>　　int Row,Col,Terms,t; //矩陣的總行數(shù)，總列數(shù)，非零元素個(gè)數(shù)和普通變量；</p><p>　　Node*headNode; //稀疏矩陣的總表頭</p><p><b>　　};</b></p><

30、p>　　class Node</p><p>　　{ //矩陣結(jié)點(diǎn)類的定義</p><p>　　friend class SparseMatrix;</p><p><b>　　public:</b></p><p>　　Node():head(t

31、rue){ r=d=this;} //建立附加頭結(jié)點(diǎn)</p><p>　　Node(Trituple *t) //建立非零元素結(jié)點(diǎn)</p><p><b>　　{</b></p><p>　　triple.col=t->col;</p><p>　　triple.ro

32、w=t->row;</p><p>　　triple.value=t->value;</p><p><b>　　r=d=this;</b></p><p>　　head=false;</p><p><b>　　}</b></p><p>　　Node*d,*r

33、; //行列鏈表指針</p><p>　　bool head;</p><p>　　union{ Trituple triple; Node*next;}; </p><p><b>　　};</b></p><p><b>　　3.2主要算法設(shè)計(jì)<

34、/b></p><p>　　3.2.1程序主要函數(shù)原型及功能</p><p><b>　　首先定義兩個(gè)類：</b></p><p>　　class Node //矩陣結(jié)點(diǎn)類定義</p><p>　　class SparseMatrix //稀疏矩陣的類定義</p&g

35、t;<p>　　[2] 主要函數(shù)原型及功能：</p><p>　　void Init(int a,int b)</p><p>　　功能：主要完成初始化稀疏矩陣，采用三元組順序輸入，行優(yōu)先存放。并且判斷輸入是否符合常規(guī)，若不符合，返回錯(cuò)誤信息。 </p><p>　　void makeEmpty() </p><p>　　功能

36、：將矩陣清空，釋放存儲(chǔ)空間。用于析構(gòu)函數(shù)中。 </p><p>　　void Insert(int a,int b,float c) </p><p>　　功能：用于向矩陣中插入元素，分兩種情況：1）先定位列再尋找行；2）先定位行再尋找列。另外插入后要確定插入的位置是否符合矩陣的設(shè)置，如果不符合，返回錯(cuò)誤信息。</p><p>　　Node *Locate(int

37、i) </p><p>　　功能：對(duì)附加頭結(jié)點(diǎn)進(jìn)行定位。</p><p>　　SparseMatrix Cheng(SparseMatrix b)</p><p>　　功能：通過確定列頭指針遍歷實(shí)現(xiàn)稀疏矩陣的相乘，判斷是否符合常規(guī)，若不符合，返回錯(cuò)誤信息。</p><p>　　SparseMatrix &operator=( Spar

38、seMatrix &T);</p><p>　　功能：重載賦值運(yùn)算符。</p><p>　　void main()</p><p>　　功能：完成對(duì)函數(shù)的調(diào)用和與用戶的交互。</p><p>　　3.2.2各函數(shù)的實(shí)現(xiàn)</p><p>　　矩陣初始化函數(shù)的實(shí)現(xiàn)：</p><p>　　

39、三元組順序輸入，按照行優(yōu)先順序存儲(chǔ)</p><p>　　函數(shù)void SparseMatrix::Init(int a,int b)的實(shí)現(xiàn)：</p><p><b>　　清空矩陣的實(shí)現(xiàn) </b></p><p>　　函數(shù)void SparseMatrix::makeEmpty()的實(shí)現(xiàn)：</p><p><b&g

40、t;　　插入函數(shù)的實(shí)現(xiàn)</b></p><p>　　1）先定位列再尋找行；2）先定位行再尋找列。另外插入后要確定插入的位置是否符合矩陣的設(shè)置，如果不符合，返回錯(cuò)誤信息。</p><p>　　函數(shù)void SparseMatrix::Insert(int a,int b,float c)的實(shí)現(xiàn)：</p><p><b>　　定位附加頭結(jié)點(diǎn)實(shí)現(xiàn)&l

41、t;/b></p><p>　　函數(shù)Node* SparseMatrix::Locate(int i)的實(shí)現(xiàn)：</p><p><b>　　矩陣乘法的實(shí)現(xiàn)</b></p><p>　　函數(shù)SparseMatrix SparseMatrix::Cheng(SparseMatrix b)的實(shí)現(xiàn)：</p><p>　　重

42、載賦值運(yùn)算符函數(shù)的實(shí)現(xiàn)</p><p>　　函數(shù)SparseMatrix SparseMatrix::Cheng(SparseMatrix b)的實(shí)現(xiàn)：</p><p><b>　　主函數(shù)設(shè)計(jì)</b></p><p>　　3.2.3 程序流程圖</p><p><b>　　本次程序流程圖如下</b>

43、</p><p><b>　　4.調(diào)試報(bào)告</b></p><p><b>　　4.1調(diào)試中的問題</b></p><p>　　整個(gè)程序的算法沒有問題，不過在編程過程中出了許多格式和語法上的錯(cuò)誤。通過軟件的提示，一個(gè)個(gè)改正錯(cuò)誤。</p><p>　　在使用十字鏈表寫程序的過程中，由于各種指針和指針域

44、非常多，經(jīng)?；煜鱾€(gè)指針的指向，以至于整個(gè)程序運(yùn)行不了。后來我在紙上細(xì)細(xì)將頭結(jié)點(diǎn)和非零元素的指針域從頭分析了一邊，重寫了十字鏈表的部分實(shí)現(xiàn)，后又修改了幾處小錯(cuò)誤，終于完成了代碼的正確書寫。</p><p>　　在寫稀疏矩陣類定義時(shí)使用了有關(guān)結(jié)點(diǎn)類的指針，而結(jié)點(diǎn)類放在稀疏矩陣類后定義。在稀疏矩陣類定義前沒有聲明結(jié)點(diǎn)類，使程序?qū)懲旰笥袔讉€(gè)函數(shù)編譯出現(xiàn)問題。剛開始只修改函數(shù)，卻怎么也修改不了。過了一段時(shí)間之后才想起實(shí)際

45、的原因。于是將程序修改正確。</p><p><b>　　4.2設(shè)計(jì)分析</b></p><p>　　算法的時(shí)間復(fù)雜度為：O（Rows*Cols)。</p><p>　　有時(shí)矩陣的非零元素個(gè)數(shù)太多會(huì)導(dǎo)致程序崩潰。另外根據(jù)實(shí)際的矩陣情況，這次的設(shè)計(jì)沒有使用模板，而僅僅是使用float類型。個(gè)人感覺float類型已經(jīng)能夠滿足稀疏矩陣的使用要求。&l

46、t;/p><p>　　由于課程設(shè)計(jì)的要求，這次代碼只實(shí)現(xiàn)了稀疏矩陣的乘法，也可以加入加減法、轉(zhuǎn)置的運(yùn)算。同時(shí)可以在主函數(shù)中加入選擇菜單。</p><p><b>　　5. 程序運(yùn)行結(jié)果</b></p><p>　　經(jīng)過對(duì)程序錯(cuò)誤的修改后，程序執(zhí)行，經(jīng)過分析，程序運(yùn)行結(jié)果正確，滿足題目要求！運(yùn)行結(jié)果主要截圖如下：</p><p&g

47、t;<b>　　6.經(jīng)驗(yàn)和體會(huì)</b></p><p>　　這次的題目是稀疏矩陣的乘法。本來拿到這個(gè)題目的時(shí)候感覺應(yīng)該很簡單，因?yàn)殡m說這部分的內(nèi)容在課本上是不要求掌握的內(nèi)容，但畢竟課本上都有，如果不會(huì)的話可以參考一下課本上的代碼?？煽吹饺蝿?wù)書的時(shí)候才知道沒那么簡單。當(dāng)時(shí)我根本不知道什么是十字鏈表和“帶行邏輯鏈接信息”，百度后才失望的發(fā)現(xiàn)在課本上關(guān)于十字鏈表的介紹竟然只有半面。我只有在認(rèn)真學(xué)習(xí)

48、了三元組法乘法的實(shí)現(xiàn)了之后，在網(wǎng)上查找學(xué)習(xí)有關(guān)十字鏈表的知識(shí)學(xué)習(xí)?？墒鞘宙湵淼闹羔樣虿糠治疫€是迷迷糊糊的。于是我決定先試著寫一寫。就這樣，我慢慢的將整個(gè)程序磨了出來。感覺程序還是要先有一個(gè)整體規(guī)劃，然后一氣呵成比較好。就像這次，我在十字鏈表的指針那里有疑問，寫了一半就已經(jīng)很晚了，就決定第二天繼續(xù)寫。不過第二天再開始的時(shí)候，卻對(duì)前一天寫的程序有些許的陌生，思路也忘記了好多。下次一定要避免這種情況的發(fā)生。即使實(shí)在寫不完，也要先記下此時(shí)的思

49、路，以便第二天復(fù)習(xí)。</p><p>　　這次數(shù)據(jù)結(jié)構(gòu)課內(nèi)設(shè)計(jì)是我第一次完整的編寫這么長的程序，收獲特別多。相對(duì)于其他同學(xué)3、4頁的代碼，我的8頁代碼顯得特別多，不過一分耕耘一分收獲。我接下來還要好好研究一下數(shù)據(jù)結(jié)構(gòu)這門課，學(xué)無止境，繼續(xù)加油吧！</p><p><b>　　7.源程序</b></p><p>　　#include<ios

50、tream></p><p>　　#include<stdlib.h></p><p>　　using namespace std;</p><p>　　struct Trituple{ //三元組類Trituple</p><p>　　int row,col; //非零元素的行號(hào)、列

51、號(hào)</p><p>　　float value; //非零元素的值</p><p>　　}; </p><p>　　class Node;</p><p>　　class SparseMatrix</p><p>　　{ //稀疏矩陣的

52、類定義</p><p>　　friend ostream&operator<<(ostream&,SparseMatrix&);//友元函數(shù)：輸出流操作符重載</p><p>　　friend istream&operator>>(istream&,SparseMatrix&);//友元函數(shù)：輸入流操作符重載</

53、p><p><b>　　public:</b></p><p>　　SparseMatrix(); //構(gòu)造函數(shù)</p><p>　　SparseMatrix(int a,int b); //重載構(gòu)造函數(shù)</p><p>　　SparseMatrix(SparseM

54、atrix& T); //復(fù)制構(gòu)造函數(shù)</p><p>　　~SparseMatrix(){makeEmpty();} //析構(gòu)函數(shù)</p><p>　　void Init(int a,int b); //矩陣初始化函數(shù)</p><p>　　void makeEmpty();

55、 //清空矩陣</p><p>　　void Insert(int a,int b,float c); //插入矩陣元素</p><p>　　Node *Locate(int i); //定位附加頭結(jié)點(diǎn)</p><p>　　SparseMatrix Cheng(SparseMatrix b);

56、 //兩個(gè)矩陣相乘</p><p>　　SparseMatrix &operator=( SparseMatrix &T); //重載賦值運(yùn)算符</p><p><b>　　private:</b></p><p>　　int Row,Col,Terms,t; //矩陣的總行數(shù)，總列數(shù)，非零元素個(gè)數(shù)和普

57、通變量；</p><p>　　Node*headNode; //稀疏矩陣的總表頭</p><p><b>　　};</b></p><p>　　class Node</p><p>　　{ //矩陣結(jié)點(diǎn)類定義</p

58、><p>　　friend class SparseMatrix;</p><p><b>　　public:</b></p><p>　　Node():head(true){ r=d=this;} //建立附加頭結(jié)點(diǎn)</p><p>　　Node(Trituple *t) /

59、/建立非零元素結(jié)點(diǎn)</p><p><b>　　{</b></p><p>　　triple.col=t->col;</p><p>　　triple.row=t->row;</p><p>　　triple.value=t->value;</p><p><b>　　

60、r=d=this;</b></p><p>　　head=false;</p><p><b>　　}</b></p><p>　　Node*d,*r; //行列鏈表指針</p><p>　　bool head;</p><p>　　un

61、ion{ Trituple triple; Node*next;}; //聯(lián)合</p><p><b>　　};</b></p><p>　　SparseMatrix:: SparseMatrix():Row(0),Col(0),Terms(0)</p><p>　　{

62、 //構(gòu)造函數(shù)的實(shí)現(xiàn)</p><p>　　Trituple x;</p><p>　　x.row=Row;</p><p>　　x.col=Col;</p><p>　　x.value=0;</p><p><b>　　}</b></p><p>　　SparseMa

63、trix:: SparseMatrix(int a,int b):Row(a),Col(b) //重載構(gòu)造函數(shù)的實(shí)現(xiàn)</p><p><b>　　{</b></p><p>　　Trituple x;</p><p><b>　　x.row=a;</b></p><p><b>　

64、　x.col=b;</b></p><p>　　x.value=0;</p><p><b>　　Terms=0;</b></p><p>　　t=a>=b?a:b;</p><p>　　Node *current;</p><p>　　headNode=new Node(&am

65、p;x);</p><p>　　current=headNode->r=new Node();</p><p>　　for(int i=1;i<t;i++)</p><p><b>　　{</b></p><p>　　current->next=new Node();</p><p&

66、gt;　　current=current->next;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　SparseMatrix:: SparseMatrix(SparseMatrix&T) //復(fù)制構(gòu)造函數(shù)的實(shí)現(xiàn)</p

67、><p><b>　　{</b></p><p>　　Init(T.Row,T.Col);</p><p>　　Node*current;</p><p>　　for(int i=1;i<=t;i++)</p><p><b>　　{</b></p><

68、p>　　current=T.Locate(i); //定位行</p><p>　　while(current->r!=T.Locate(i))</p><p>　　{ //通過行遍歷逐個(gè)賦值</p><p>　　current=current->r; </p&g

69、t;<p>　　Insert(current->triple.row,current->triple.col,current->triple.value);</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b&

70、gt;</p><p>　　void SparseMatrix::Init(int a,int b) //矩陣初始化函數(shù)的實(shí)現(xiàn)</p><p><b>　　{</b></p><p><b>　　Row=a;</b></p><p><b>　　Col=b;<

71、;/b></p><p><b>　　Terms=0;</b></p><p>　　Trituple x;</p><p><b>　　x.row=a;</b></p><p><b>　　x.col=b;</b></p><p>　　x.valu

72、e=0;</p><p>　　headNode=new Node(&x);</p><p>　　Node *current; </p><p>　　if(a>0&&b>0)</p><p><b>　　{</b></p><p>　　t=a>=b?a:b;

73、</p><p>　　current=new Node();</p><p>　　headNode->r=current;</p><p>　　for(int i=1;i<t;i++)</p><p><b>　　{</b></p><p>　　current->next=new

74、 Node(); </p><p>　　current=current->next;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　else{cout<<"初始化錯(cuò)誤！"<<endl;}</

75、p><p><b>　　}</b></p><p>　　Node* SparseMatrix::Locate(int i) //定位附加頭結(jié)點(diǎn)實(shí)現(xiàn)</p><p><b>　　{</b></p><p>　　Node *current;</p>&l

76、t;p>　　current=headNode->r;</p><p>　　for(int j=1;j<i;j++)</p><p><b>　　{</b></p><p>　　current=current->next;</p><p><b>　　}</b></p&g

77、t;<p>　　return current;</p><p><b>　　}</b></p><p>　　void SparseMatrix::Insert(int a,int b,float c) //插入函數(shù)的實(shí)現(xiàn)</p><p><b>　　{</b></p><

78、p>　　Trituple x;</p><p>　　x.row=a;x.col=b;x.value=c;</p><p>　　if(a<=this->Row&&b<=this->Col)</p><p><b>　　{</b></p><p>　　Node *NewNode=

79、new Node(&x),*current,*head;</p><p>　　head=Locate(a); //先定位行再尋找列</p><p>　　current=head->r;</p><p>　　if(current==head)</p><p><b>　　{</b&

80、gt;</p><p>　　current->r=NewNode;</p><p>　　NewNode->r=current;</p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</

81、b></p><p>　　while(current->triple.col<b&&current->r!=head)</p><p><b>　　{</b></p><p>　　current=current->r; }</p><p>　　NewNode->r=cu

82、rrent->r;</p><p>　　current->r=NewNode;</p><p>　　} </p><p>　　head=Locate(b); //先定位列再尋找行</p><p>　　current

83、=head->d;</p><p>　　if(current==head)</p><p><b>　　{</b></p><p>　　current->d=NewNode;</p><p>　　NewNode->d=current;</p><p><b>　　}&l

84、t;/b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　while(current->triple.row<a&&current->d!=head)</p><p><b>　　{<

85、/b></p><p>　　current=current->d;</p><p><b>　　}</b></p><p>　　NewNode->d=current->d;</p><p>　　current->d=NewNode;</p><p><b>

86、　　}</b></p><p><b>　　Terms++;</b></p><p><b>　　} </b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　

87、　cout<<"結(jié)點(diǎn)位置非法，請(qǐng)重新輸入"<<endl;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　istream &operator>>(istream &in, SparseMatrix &

88、amp;b) //輸入函數(shù)重載</p><p><b>　　{</b></p><p>　　int R,C,m,n,S;float a;</p><p>　　cout<<"請(qǐng)輸入矩陣的行數(shù)、列數(shù)、非零元素個(gè)數(shù)："<<endl;</p><p>　　in>&

89、gt;R>>C>>S;</p><p>　　b.Init(R,C);</p><p>　　if(S>(R*C))</p><p><b>　　{</b></p><p>　　cerr<<"輸入元素個(gè)數(shù)超過設(shè)定"<<endl;</p>

90、<p><b>　　exit(1);</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　cout<<"請(qǐng)輸入各非零元素的

91、行數(shù)、列數(shù)、值"<<endl;</p><p>　　cout<<"行數(shù) 列數(shù) 值"<<endl;</p><p>　　for(int i=1;i<=S;i++) //輸入元素結(jié)點(diǎn)并且插入矩陣</p><p><b>　　{</b><

92、;/p><p>　　cout<<"["<<i<<"]:";</p><p>　　in>>m>>n>>a;</p><p>　　b.Insert(m,n,a); //插入結(jié)點(diǎn)</p><p><b

93、>　　}</b></p><p>　　return in;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　ostream &operator<<(ostream &out, SparseMatrix

94、&b) //輸出函數(shù)重載</p><p><b>　　{</b></p><p><b>　　Node *x;</b></p><p>　　for(int i=1;i<=b.t;i++) //先確定各行頭結(jié)點(diǎn)的位置再遍歷各行，以輸出所有非零元</p>&

95、lt;p><b>　　{</b></p><p>　　x=b.Locate(i);</p><p><b>　　x=x->r;</b></p><p>　　for(int j=1;j<=b.t;j++) </p><p><b>　　{</b></p

96、><p>　　if(x->head==false&&(x->triple.col==j))</p><p><b>　　{</b></p><p>　　cout.width(4);</p><p>　　out<<x->triple.value;</p><p&

97、gt;<b>　　x=x->r;</b></p><p><b>　　}</b></p><p>　　else if(x->head==true)</p><p><b>　　{</b></p><p>　　for(j;j<=b.t;j++){cout.wid

98、th(4);cout<<"0";}</p><p><b>　　break;</b></p><p><b>　　}</b></p><p>　　else{cout.width(4);cout<<"0";}</p><p><b

99、>　　}</b></p><p>　　cout<<endl;</p><p><b>　　}</b></p><p>　　return out;</p><p><b>　　}</b></p><p>　　SparseMatrix & S

100、parseMatrix::operator =( SparseMatrix &T) //重載賦值運(yùn)算符函數(shù)的實(shí)現(xiàn)</p><p><b>　　{</b></p><p>　　this->Row=T.Row;</p><p>　　this->Col=T.Col;</p><p>　　

101、Node *current;</p><p>　　for(int i=1;i<=t;i++)</p><p><b>　　{</b></p><p>　　current=T.Locate(i);</p><p>　　while(current->r!=current)</p><p>

102、<b>　　{</b></p><p>　　current=current->r; //通過行遍歷逐個(gè)賦值</p><p>　　this->Insert(current->triple.row,current->triple.col,current->triple.value);</p><p>

103、<b>　　}</b></p><p><b>　　}</b></p><p>　　return *this;</p><p><b>　　}</b></p><p>　　void SparseMatrix::makeEmpty() //清空矩陣的實(shí)

104、現(xiàn)</p><p><b>　　{</b></p><p>　　Node*del,*current;</p><p>　　for(int i=1;i<=t;i++)</p><p><b>　　{</b></p><p>　　current=Locate(i);

105、 //找到列的附加頭結(jié)點(diǎn)</p><p>　　while(current->d!=Locate(i))</p><p><b>　　{</b></p><p>　　del=current->d; //通過列的附加頭結(jié)點(diǎn)向下刪除結(jié)點(diǎn)</p><p>　　current-&

106、gt;d=del->d;</p><p>　　delete del;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　SparseMatrix Sparse

107、Matrix::Cheng(SparseMatrix b) //矩陣乘法的實(shí)現(xiàn)</p><p><b>　　{</b></p><p>　　if(this->Col==b.Row)</p><p><b>　　{</b></p><p>　　SparseMatrix C(thi

108、s->Row,b.Col); //以A矩陣的行和b矩陣的列為行列建立稀疏矩陣</p><p>　　float value;</p><p>　　Node *Row_head,*Col_head; //設(shè)兩個(gè)指針，一個(gè)充當(dāng)行頭指針，一個(gè)為列指針 </p><p>　　for(int i=1;i<=t;i++) //先確定

109、行，再求出C矩陣在該行各列的元素</p><p><b>　　{</b></p><p>　　for(int j=1;j<=t;j++) //通過確定列頭指針來實(shí)現(xiàn)遍歷相乘</p><p><b>　　{</b></p><p><b>　　value=0;</b>

110、</p><p>　　Row_head=Locate(i);</p><p>　　Col_head=b.Locate(j);</p><p>　　while(Row_head->r!=Locate(i)) </p><p>　　{ //假如行中還有元素不為零就找與之匹配的元素相乘</p>

111、<p>　　Row_head=Row_head->r;</p><p>　　Col_head=Col_head->d; while(Row_head->triple.col!=Col_head->triple.row&&Col_head->d!=b.Locate(j)) </p><p>　　{ //假如

112、行列不相等而且對(duì)應(yīng)列還有元素，就繼續(xù)找匹配的元素否則判斷再循環(huán)</p><p>　　if(Row_head->triple.col>Col_head->triple.row)</p><p>　　Col_head=Col_head->d;</p><p><b>　　else </b></p><p&

113、gt;<b>　　{</b></p><p>　　if(Row_head->r==Locate(i))</p><p>　　Col_head=Col_head->d;</p><p>　　//假如b矩陣該列元素比a矩陣該行元素多</p><p><b>　　else</b></p&

114、gt;<p>　　Row_head=Row_head->r; </p><p>　　//則b中該列元素已經(jīng)無法找到能相乘元素則往下推直至跳出循環(huán)</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　if(Col_head-&g

115、t;d!=b.Locate(j)||Col_head->triple.row==Row_head->triple.col)</p><p><b>　　{</b></p><p>　　value+=Row_head->triple.value*Col_head->triple.value;</p><p><b&g

116、t;　　}</b></p><p><b>　　}</b></p><p>　　if(value!=0)</p><p><b>　　{</b></p><p>　　C.Insert(i,j,value);</p><p><b>　　}</b&

117、gt;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　return C;</b></p><p><b>　　}</b></p><p><b>　　el

118、se</b></p><p><b>　　{</b></p><p>　　SparseMatrix C;</p><p>　　cerr<<"兩個(gè)矩陣不能相乘！"<<endl;</p><p><b>　　return C;</b></p&

119、gt;<p><b>　　}</b></p><p><b>　　}</b></p><p>　　void main()</p><p><b>　　{ </b></p><p>　　SparseMatrix A,B,C;</p><p>

120、　　cout<<"稀疏矩陣的乘法"<<endl;</p><p>　　cout<<"請(qǐng)輸入矩陣A："<<endl;</p><p><b>　　cin>>A;</b></p><p>　　cout<<"請(qǐng)輸入矩陣B：&quo

121、t;<<endl;</p><p><b>　　cin>>B; </b></p><p>　　cout<<"矩陣A為:"<<endl;</p><p>　　cout<<A<<endl;</p><p>　　cout<<

122、"矩陣B為:"<<endl;</p><p>　　cout<<B<<endl;</p><p>　　cout<<"兩個(gè)矩陣的乘積為："<<endl;</p><p>　　cout<<A.Cheng(B)<<endl;</p>&l