1、 稀疏矩陣相乘1問題描述1.1稀疏矩陣的三元組及十字鏈表表示（1) 稀疏矩陣及其三元組表示行（row)列（col)值（value)00322106152111131517423-6535396403975228稀疏矩陣（2）稀疏矩陣的十字鏈表表示1.2基本要求（1） 以“帶行邏輯鏈接信息”的三元組表示稀疏矩陣；（2） 輸入矩陣用三元組順序輸入；（2）稀疏矩陣采用十字鏈表表示；（3）實現(xiàn)兩個矩陣相乘的運算，而運算結(jié)果的矩陣則以通常的陣列形式列出。2設計思路2.1存儲結(jié)構設計2.1.1三元組表示稀疏矩陣只存儲矩陣中極少的非零元素，采用<row,col,value>來唯一地確定每一個非零

2、元素，其中row、col、value分別表示非零元素在矩陣中的的行下標、列下表和值。各數(shù)組元素的三元組按在原矩陣中的位置以行優(yōu)先的順序依次存放。struct triple /三元組結(jié)構定義 int row, col; /非零元素行號,列號 Float value; /非零元素的值 triple& operator=(triple &x) row=x.row;col=x.col;value=x.value;2.1.2十字鏈表表示稀疏矩陣struct element int row,col;float value;class Matrix;class node / 矩陣節(jié)點類的定義

3、friend class Matrix;public:node():head(true) right=down=this; /建立附加頭結(jié)點node(element *t) / 建立非零元素結(jié)點triple.col=t->col;triple.row=t->row;triple.value=t->value;right=down=this;head=false;node*down,*right;/行列鏈表指針bool head;union element triple;node*next; /無名聯(lián)合;class Matrix/稀疏矩陣的類定義friend istream&a

4、mp;operator>>(istream&,Matrix&); friend ostream&operator<<(ostream&,Matrix&);private:int Row,Col,Terms,temp; /矩陣的總行數(shù)，總列數(shù)，和非零元素個數(shù)和臨時變量；node*headnode; /稀疏矩陣的總表頭public:Matrix(int m,int n); /重載構造函數(shù)Matrix(); /對矩陣進行構造Matrix(Matrix& T); /復制構造函數(shù)Matrix()makeEmpty(); /析構函數(shù)v

5、oid Init(int m,int n); /初始化函數(shù)，又來初始化無參構造函數(shù)構造的矩陣void makeEmpty(); /清空矩陣void Insert(int m,int n,float p); /插入矩陣元素node *Locate(int i); /定位附加頭結(jié)點Matrix Mul(Matrix b); /兩個矩陣相乘Matrix &operator=(Matrix &T); /重載賦值號;在稀疏矩陣的十字鏈表表示中，矩陣的的每一行設置為一個帶附加頭結(jié)點的循環(huán)行鏈表，每一列也設置為一個帶附加頭結(jié)點的循環(huán)列鏈表。鏈表中的結(jié)點都屬于類node的對象，這個類包含一個域

6、head,它用于區(qū)分改結(jié)點是附加頭結(jié)點還是鏈表中的非零元素結(jié)點；head=true,表示該結(jié)點是附加頭結(jié)點；head=false,表示該結(jié)點是矩陣中的非零元素結(jié)點。每一個附加頭結(jié)點還有三個域：down、right、next。第i個行鏈表和第i個列鏈表共用一個附加頭結(jié)點，在它的right域存放第i行鏈表最前端的第一個結(jié)點的地址，在它的down域存放第i列鏈表的最前端第一個結(jié)點的地址，通過next域鏈接到第i+1個附加頭結(jié)點。每一個非零元素結(jié)點包含六個域：head,row,col,down,right，value。Down存放列鏈表指針，right存放行鏈表指針。整個稀疏矩陣定義為類Matrix的

7、一個對象，*headnode給出整個附加頭結(jié)點鏈表的附加頭結(jié)點的地址。headnextdownrightheadrowcoldownvalueright 非零元素結(jié)點 附加頭結(jié)點 非零元素結(jié)點2.2主要算法基于三元組及十字鏈表的稀疏矩陣乘法Matrix Matrix:Mul( Matrix b) /矩陣乘法的實現(xiàn) if(this->Col=b.Row) Matrix C(this->Row,b.Col); /以A矩陣的行和b矩陣的列為行列建立稀疏矩陣 float value; node *Row_head,*Col_head; /設兩個指針，一個充當行頭指針，一個為列指針 for(

8、int i=1;i<=temp;i+) /先確定行，再求出C矩陣在該行各列的元素 for(int j=1;j<=temp;j+) /通過確定列頭指針來實現(xiàn)遍歷相乘 value=0; Row_head=Locate(i); Col_head=b.Locate(j); while(Row_head->right!=Locate(i) /假如行中還有元素不為零就找與之匹配的元素相 Row_head=Row_head->right; Col_head=Col_head->down; while(Row_head->triple.col!=Col_head->t

9、riple.row &&Col_head->down!=b.Locate(j) /假如行列不相等而且對應列還有元素，就繼續(xù)找匹配的元素否則判斷再環(huán) if(Row_head->triple.col>Col_head->triple.row) Col_head=Col_head->down; else if(Row_head->right=Locate(i) Col_head=Col_head->down;/假如b矩陣該列元素比a矩陣該行元素 else Row_head=Row_head->right; /則b中該列元素已經(jīng)無法找到能

10、相乘元素則往下推直至跳出循環(huán) if(Col_head->down!=b.Locate(j)|Col_head->triple.row=Row_head->triple.col) value+=Row_head->triple.value*Col_head->triple.value;if(value!=0) C.Insert(i,j,value) return C; else Matrix C; cerr<<"輸入的兩個矩陣不符規(guī)則，不能相乘！"<<endl; return C; 2.3測試用例3調(diào)試分析3.1調(diào)試過程（

11、1）編譯時程序中沒有語法錯誤，但是格式及語句的書寫錯誤叫多，按照編譯錯誤提示一次改正錯誤，直至編譯正確。（2）運行程序。以三元組的形式，即輸入矩陣的行數(shù)、列數(shù)、非零元素個數(shù)和各非零元素的行、列、值，輸入兩個稀疏矩陣，輸出了兩個矩陣及它們的乘積。（3）問題：輸出的矩陣不符合要求，形成的陣列中只有非零元素，零元素都沒有輸出。說明友元輸入函數(shù)有問題，將元函數(shù)改為下面的函數(shù)后能正確輸出矩陣陣列。ostream &operator<<(ostream &out,Matrix &b) /輸出函數(shù) node *x; for(int i=1;i<=b.temp;i+)

12、 /先確定各行頭結(jié)點的位置再遍歷各行，以輸出所有非零元 x=b.Locate(i); x=x->right; for(int j=1;j<=b.temp;j+) if(x->head=false&&(x->triple.col=j) cout.width(4); out<<x->triple.value; x=x->right; else if(x->head=true) for(j;j<=b.temp;j+)cout.width(4);cout<<"0"break; elsecout.

13、width(4);cout<<"0" cout<<endl; return out;3.2設計分析（1）此程序中乘法算法的時間復雜度為O（Rows*Cols)。（2）此程序沒有將類做成模版，導致只能輸入floate型的值。 改進方案：將所有的類做成模版，將其屬下的floate類型的全改為模版類型參數(shù)<T>。（3） 此程序顯的很繁鎖，算法比較復雜（4） 此程序只有稀疏矩陣的乘法，可以加入其他的矩陣運算來完善運算，也可以再主程序中設計選擇菜單，實現(xiàn)多種運算。（5） 改進算法：重新考慮算法，看是否可用數(shù)組加指針的方式實現(xiàn)，用數(shù)組可以簡化找頭指針

14、的繁瑣過程，簡化循環(huán)的過程提高程序運行效率！4經(jīng)驗與體會 我的題目是實現(xiàn)三元組，十字鏈表下乘法，運算。看到這個題目的時候，我一片茫然，因為我們數(shù)據(jù)結(jié)構這一部分并沒有講，我根本就不知道十字鏈表是什么。于是我趕緊看書，可是書上對十字鏈表的將就知識一筆帶過，更不要指望在書上找到相關代碼了。于是我先學習了三元組數(shù)組的乘法算法，在這個基礎上，我在網(wǎng)上收集各種資料收集和算法。然后不斷調(diào)試，不斷改進程序，最終正確結(jié)果終于運行出來了。我覺得自己的數(shù)據(jù)結(jié)構學得不好，但是數(shù)據(jù)結(jié)構可以說是計算機里一門基礎課程，對于以后的學習尤為重要。所以我們一定要把基礎學扎實，這次的課內(nèi)實踐幫我重新鞏固基礎知識，也學了很多新知識，

15、提高了我的專業(yè)的動手實踐能力，也提高了我的對數(shù)據(jù)結(jié)構的學習興趣。此次課程設計過程中，我真正的體驗到，拿到一個問題，應該先分析，將其的屬性，功能分析清楚后，再進行細化，考慮其實現(xiàn)的具體的、有效的算法，有了整體的結(jié)構框架后再上機！以前只要拿到題就直接打開電腦，想到什么就寫什么，沒整體思考，對小程序可以，大程序就會徹底崩潰。編程實質(zhì)就是問題的分析及其實現(xiàn)的算法，這兩方面解決了上機編程才會得心應手，剩下的就是按算法些代碼了！確定一個好算法很難，一個人往往陷入死循環(huán)，思路受局限，找人討論很必要，編程時團隊意識很重要，這不是一個人就能搞定的。在實踐的過程中我每天完成一小部分。盡量減少操作的盲目性，提高我們

16、學習的效率。有個總體的大綱來逐步實現(xiàn)。我也曾經(jīng)犯過這種錯誤。每個函數(shù)都做出來部分，結(jié)果都沒做完。所以我們要養(yǎng)成有良好的時間規(guī)劃的習慣，只有一步一步的進行，我們才能完成得更好。同時在實驗中我們要培養(yǎng)自己獨立的思考能力和解決問題的能力，不能太過依賴于同學和網(wǎng)絡，我們應該要有自己的想法，培養(yǎng)自己的編程思維。實踐能力對我們今后的發(fā)展也是至關重要的，我們只有擁有很好地實踐能力，才有機會再編程這個領域有所發(fā)展。子啊編程的過程中，我們應該積極的朝著更好地一面發(fā)展不斷的完善程序，不能馬馬虎虎隨便應付一下。 就像古人云，紙上得來終覺淺，得知此事要躬行。為了以后的計算機道路，我們應該不斷的提高自身的專業(yè)素養(yǎng)。5附

17、錄5.1程序#include<iostream.h>#include<stdlib.h>struct element int row,col;float value;class Matrix;class node / 矩陣節(jié)點類的定義friend class Matrix;public:node():head(true) right=down=this; /建立附加頭結(jié)點node(element *t) / 建立非零元素結(jié)點triple.col=t->col;triple.row=t->row;triple.value=t->value;right=d

18、own=this;head=false;node*down,*right;/行列鏈表指針bool head;union element triple;node*next; /無名聯(lián)合;class Matrix/稀疏矩陣的類定義friend istream&operator>>(istream&,Matrix&); friend ostream&operator<<(ostream&,Matrix&);private:int Row,Col,Terms,temp; /矩陣的總行數(shù)，總列數(shù)，和非零元素個數(shù)和臨時變量；node*

19、headnode; /稀疏矩陣的總表頭public:Matrix(int m,int n); /重載構造函數(shù)Matrix(); /對矩陣進行構造Matrix(Matrix& T); /拷貝構造函數(shù)Matrix()makeEmpty(); /析構函數(shù)void Init(int m,int n); /初始化函數(shù)，又來初始化無參構造函數(shù)構造的矩陣void makeEmpty(); /清空矩陣void Insert(int m,int n,float p); /插入矩陣元素node *Locate(int i); /定位附加頭結(jié)點Matrix Mul(Matrix b); /兩個矩陣相乘Mat

20、rix &operator=(Matrix &T); /重載賦值號;Matrix:Matrix(int m,int n):Row(m),Col(n) /重載構造函數(shù)的實現(xiàn)element x;x.row=m;x.col=n;x.value=0;Terms=0;temp=m>=n?m:n;node *current;headnode=new node(&x);current=headnode->right=new node();for(int i=1;i<temp;i+)current->next=new node();current=current

21、->next;Matrix:Matrix():Row(0),Col(0),Terms(0) /構造函數(shù)的實現(xiàn)element x;x.row=Row;x.col=Col;x.value=0;Matrix:Matrix(Matrix&T) /復制構造函數(shù)的實現(xiàn)Init(T.Row,T.Col);node*current;for(int i=1;i<=temp;i+)current=T.Locate(i); /定位行while(current->right!=T.Locate(i) /通過行遍歷逐個賦值current=current->right; Insert(cu

22、rrent->triple.row,current->triple.col,current->triple.value);void Matrix:Init(int m,int n) /矩陣初始化函數(shù)的實現(xiàn)Row=m;Col=n;Terms=0;element x;x.row=m;x.col=n;x.value=0;headnode=new node(&x);node *current; if(m>0&&n>0)temp=m>=n?m:n;current=new node();headnode->right=current; fo

23、r(int i=1;i<temp;i+)current->next=new node(); current=current->next;elsecout<<"矩陣初始化錯誤！"<<endl;node* Matrix:Locate(int i)/定位附加頭結(jié)點實現(xiàn)node *current;current=headnode->right;for(int k=1;k<i;k+)current=current->next;return current;void Matrix:Insert(int m,int n,floa

24、t p)/插入函數(shù)的實現(xiàn)element x;x.row=m;x.col=n;x.value=p;if(m<=this->Row&&n<=this->Col)node *Newnode=new node(&x),*current,*head;head=Locate(m);/先定位行的位置再尋找列插入current=head->right;if(current=head)current->right=Newnode;Newnode->right=current;elsewhile(current->triple.col<

25、n&&current->right!=head)current=current->right;Newnode->right=current->right;current->right=Newnode; /完成插入head=Locate(n); /先定位列再尋找行插入current=head->down;if(current=head)current->down=Newnode;Newnode->down=current;elsewhile(current->triple.row<m&&current-&

26、gt;down!=head)current=current->down;Newnode->down=current->down;current->down=Newnode;Terms+; /完成插入elsecout<<"輸入的結(jié)點位置超出了范圍，請重新輸入！"<<endl;istream &operator>>(istream &in,Matrix &b) /輸入函數(shù)重載的實現(xiàn)int M,N,m,n,T;float p;cout<<"請輸入矩陣的行列和非零元素個數(shù)：&q

27、uot;<<endl;in>>M>>N>>T;b.Init(M,N);if(T>(M*N)cerr<<"輸入的元素個數(shù)超過范圍"<<endl;exit(1);elsecout<<"請輸入各非零元素的行數(shù)列數(shù)和值"<<endl;cout<<"行數(shù) 列數(shù) 值"<<endl;for(int i=1;i<=T;i+) /輸入元素結(jié)點并且插入矩陣cout<<""<<i&l

28、t;<":"in>>m>>n>>p;b.Insert(m,n,p); /插入結(jié)點return in;ostream &operator<<(ostream &out,Matrix &b) /輸出函數(shù)重載node *x;for(int i=1;i<=b.Row;i+) /先確定各行頭結(jié)點的位置再遍歷各行，以輸出所有非零元x=b.Locate(i);x=x->right;for(int j=1;j<=b.Col;j+) if(x->head=false&&(x-

29、>triple.col=j)cout.width(4);out<<x->triple.value;x=x->right;else if(x->head=true)for(j;j<=b.Col;j+)cout.width(4);cout<<"0"break;elsecout.width(4);cout<<"0"cout<<endl;return out;Matrix & Matrix:operator =(Matrix &T) /重載賦值號函數(shù)的實現(xiàn)this-&g

30、t;Row=T.Row;this->Col=T.Col;node *current;for(int i=1;i<=temp;i+)current=T.Locate(i);while(current->right!=current)current=current->right; /通過行遍歷逐個賦值this->Insert(current->triple.row,current->triple.col,current->triple.value);return *this;void Matrix:makeEmpty() /清空矩陣的實現(xiàn)node*d

31、el,*current;for(int i=1;i<=temp;i+)current=Locate(i); /找到列的附加頭結(jié)點while(current->down!=Locate(i)del=current->down; /通過列的附加頭結(jié)點向下刪除結(jié)點current->down=del->down;delete del;Matrix Matrix:Mul( Matrix b) /矩陣乘法的實現(xiàn)if(this->Col=b.Row)Matrix C(this->Row,b.Col); /以A矩陣的行和b矩陣的列為行列建立稀疏矩陣float value;node *Row_head,*Col_head; /設兩個指針，一個充當行頭指針，一個為列指針 for(int i=1;i<=temp;i+) /先確定行，再求出C矩陣在該行各列的元素for(int j=1;j<=temp;j+) /通過確定列頭指針來實現(xiàn)遍歷相乘value=0;Row_head=Locate(i); Col_head=b.Locate(j);while(Row_head->right!=Locate(i) /假如行中還有元素不為零就找與之匹配的元素相乘Row_head=Row_head->rig