十字鏈表實現(xiàn)稀疏矩陣的加法

1、實驗二 十字鏈表 一、實驗題目 以十字鏈表為儲存結(jié)構(gòu)，實現(xiàn)稀疏矩陣的求和運算。 二、問題描述1、 功能要求：根據(jù)用戶輸入的矩陣，實現(xiàn)稀疏矩陣的求和運算，并輸出結(jié)果。2、 輸入要求：矩陣的數(shù)據(jù)在程序運行的時候由用戶提供，先由用戶輸入稀疏矩陣的行數(shù)、列數(shù)和非零元個數(shù)。再根據(jù)非零元個數(shù)，輸入這些非零元，還需要用戶為這些非零元輸入行、列和非零元的值。這樣，一個稀疏矩陣就輸入完成。 若輸入3 3 2 則表示這個稀疏矩陣有3行3列2個非零元 然后用戶需要為這兩個非零元輸入行、列、非零元的值 如：1 1 22 2 1 表示第一個非零元行為1，列為1,，值為2；第二個非零元行為2，列為2，值為1。 此過程輸入

2、的稀疏矩陣為： 2 0 0 0 1 0 0 0 03、 輸出要求：輸出按矩陣輸出，按行列依次輸出，非零元則輸出非零元的值，不是非零元則輸出“0”。各元素之間用空格隔開。最后輸出完整的矩陣。 三、概要設(shè)計1稀疏矩陣的抽象數(shù)據(jù)類型定義如下：adt sparsematrix 數(shù)據(jù)對象： d=aij|i=1,2,3m,j=1,2,3n; aij屬于elemset,m和n分別是稀疏矩陣的行數(shù)和列數(shù)數(shù)據(jù)關(guān)系： r= row, col row=<aij,aij+1>|1<=i<=m,1<=j<=n-1col=<aij,ai+1j>|1<=i<=m-

3、1,1<=j<=n基本操作：createsmatrix(&m);/建立稀疏矩陣mdestroysmatrix(&m);/銷毀稀疏矩陣m；transposesmatrix(m);/求稀疏矩陣的轉(zhuǎn)置矩陣addsmatrix(&m,&n);/求稀疏矩陣m和n之和mulsmatrix(&m,&n);/求稀疏矩陣m和n之積adt sparsematrix2、 存儲結(jié)構(gòu)選擇采用十字鏈表存儲稀疏矩陣，它是稀疏矩陣鏈?zhǔn)奖硎镜囊环N較好的表示方法。在十字鏈表中，每一個非零矩陣元素存儲在一個結(jié)點內(nèi)。每一個節(jié)點除了存儲非零元素的三元組以外，還設(shè)置了right

4、和down兩個指針，分別指向同一行的下一個非零元素結(jié)點和同一列的下一個非零元結(jié)點。3、 其他函數(shù)1） 主函數(shù)main（）2） 作為友元函數(shù)的加法運算。4、 詳細設(shè)計用十字鏈表表示稀疏矩陣，需要定義結(jié)點類和鏈表類兩個類1、 結(jié)點類matrixnodetemplate<class type>class matrixnode friend class linkmatrix<type>friend istream&operator>>(istream&,linkmatrix<type>&); friend ostream&

5、operator<<(ostream&out, linkmatrix<type>&); friend linkmatrix<type> operator +(const linkmatrix<type> &a,const linkmatrix<type> &b);private:int row,col;matrixnode<type>*right,*down;uniontype data;matrixnode<type>*next;2、 鏈表類template<class

6、type>class linkmatrixprivate:matrixnode<type> *head;void insertincol(matrixnode<type>*p);void deleteincol(matrixnode<type>*p);public:friend istream&operator>>(istream&in,linkmatrix<type>&);friend ostream&operator<<(ostream&out,linkmatrix<

7、type>&);matrixnode<type>* head(int i);linkmatrix<type>&operator +=(const linkmatrix<type> &a);friend linkmatrix<type> operator +(const linkmatrix<type> &a,const linkmatrix<type> &b); ;3、 求頭結(jié)點函數(shù)template<class type> matrixnode<type>

8、;* linkmatrix<type>:head(int i) matrixnode<type>*a;a=head->next;for(int j=1;j<i;j+)a=a->next; return a;4、 將結(jié)點p插入p->col列中template<class type>void linkmatrix<type>:insertincol(matrixnode<type>*p)matrixnode<type>*pre,*ch=head(p->col);pre=ch;while(pre-&

9、gt;down!=ch&&pre->down->row<p->row)pre=pre->down;p->down=pre->down;pre->down=p;5、 在p->col列中刪除結(jié)點p，并釋放空間template<class type>void linkmatrix<type>:deleteincol(matrixnode<type>*p)matrixnode<type>*pre,*ch=head(p->col);pre=ch;while(pre->down

10、!=ch&&pre->down!=p)pre=pre->down;if(pre->down=p)pre->down=p->down;delete p;6、 重載>>函數(shù)template<class type>istream&operator>>(istream&in,linkmatrix<type>&a)int m,n,terms,s;matrixnode<type>*cp,*p,*q;cout<<"輸入矩陣的行數(shù)、列數(shù)、和非零元素個數(shù)&quo

11、t;<<endl;in>>m>>n>>terms;if(n>m)s=n;else s=m;a.head=new matrixnode<type>a.head->row=m;a.head->col=n;a.head->right=a.head->down=null;cp=new matrixnode<type>*s+1;cp0=a.head;int i;for(i=1;i<=s;i+)p=new matrixnode<type>p->row=p->col=0;p-&

12、gt;right=p->down=p;cpi=p;cpi-1->next=p;cps->next=a.head;for(i=1;i<=terms;i+)cout<<"輸入一個非零元三元組(row,col,value)"<<endl;p=new matrixnode<type>in>>p->row>>p->col>>p->data;q=cpp->row;while(q->right!=cpp->row&&(q->right-

13、>col<p->col)q=q->right;p->right=q->right;q->right=p;q=cpp->col;while(q->down!=cpp->row&&(q->down->col<p->col)q=q->down;p->down=q->down;q->down=p;deletecp;return in;7、 重載<<函數(shù)template<class type>ostream & operator<<(os

14、tream & out ,linkmatrix<type>& a)for(int i=1;i<=a.head->row;i+)matrixnode<type>*b=a.head(i);b=b->right;for(int j=1;j<=a.head->col;j+)if(b->row=i&&b->col=j)cout<<b->data<<' 'b=b->right;elsecout<<'0'<<'

15、'cout<<endl;return out; 8、 重載+=實現(xiàn)求和函數(shù)template<class type> /重載符合賦值運算符+=linkmatrix<type>&linkmatrix<type>:operator +=(const linkmatrix<type> &a)matrixnode<type> *pre,*pa,*h,*ah,*p,*tmp;if(head->col !=a.head->col|head->row !=a.head->row)/非同型矩陣

16、不可相加cout<<"the two matrice aren't isomorphic!"/throw domain_error("the two matrice aren't isomorphic!");h=head->next;ah=a.head->next; /h、ah指向當(dāng)前處理行的頭結(jié)點while(h !=head) /逐一處理各行pre=h; p=h->right; /p指向被加矩陣的當(dāng)前結(jié)點，pre指向其前驅(qū)pa=ah->right; /pa分別指向加矩陣的當(dāng)前結(jié)點while(pa !=

17、ah) /處理當(dāng)前行if(p !=h&&(p->col<pa->col) /若被加矩陣的列標(biāo)更小，則比較下一個pre=p; p=p->right;else if(p=h|p->col>pa->col) tmp=new matrixnode<type>(*pa) ;pre->right=tmp; /在行鏈表中插入pa復(fù)制結(jié)點tmptmp->right=p;insertincol(tmp); /在列表中插入tmppre=tmp; /當(dāng)前指針p的前驅(qū)變?yōu)閠mppa=pa->right;else /列標(biāo)相同，則做加

18、法p->data +=pa->data;if(!p->data) /和為0，則刪除之 （行、列都要刪除）tmp=p;p=p->right;pre->right=p;/在行鏈表中將tmp摘下deleteincol(tmp); /在列鏈表中將tmp刪除pre=p;p=p->right;pa=pa->right;h=h->next; ah=ah->next; /處理下一行return *this;9、 重載+template<class type> /重載加法運算符+linkmatrix<type> operator +(

19、const linkmatrix<type> &a,const linkmatrix<type> &b)linkmatrix<type> c(a); /復(fù)制構(gòu)造函數(shù)得到被加矩陣a的一個副本放在矩陣c中c+=b;return c;5、 調(diào)試與測試1、 編譯環(huán)境visual c+ 6.02、 main函數(shù)int main()linkmatrix<int>a,b,c;cin>>a;cout<<"a矩陣為：n"<<a<<endl;cin>>b;cout<

20、<"b矩陣為：n"<<b<<endl;c=a+b;cout<<"a+b=n"<<c<<endl;system("pause");return 0;3、 具體步驟按f5編譯，界面出現(xiàn)提示“請輸入行數(shù)、列數(shù)、非零元個數(shù)”。輸入3 3 3表示這個矩陣行數(shù)為3，列數(shù)為3，非零元個數(shù)為3，接著提示“請輸入一個非零元三元組<row,col,value>”。輸入1 1 1表示第一個三元組的行為1，列為1，值為1然后程序繼續(xù)提示“輸入一個非零元三元組<row,col,

21、value>”。按要求再依次輸入2 2 23 1 5則矩陣a輸入完成，程序按矩陣格式輸出矩陣a程序繼續(xù)提示“請輸入行數(shù)、列數(shù)、非零元個數(shù)”在按上述操作繼續(xù)輸入3 3 41 1 22 1 13 1 13 3 3為矩陣b輸入，完成后程序輸入矩陣b程序同時輸出a+b3、 結(jié)果分析程序提供輸入和輸出，根據(jù)輸入的矩陣a和矩陣b，a+b計算結(jié)果準(zhǔn)確無誤。6、 使用說明使用本程序簡單明了，只需根據(jù)提示為稀疏矩陣輸入，就可以計算出稀疏矩陣的和。附錄2： 十字鏈表實現(xiàn)稀疏矩陣相加源程序 軟件2班 201113040207#include<iostream>using namespace std

22、;template<class type>class matrixnode; template<class type>class linkmatrix;template<class type>istream &operator>>(istream &,linkmatrix<type>&);template<class type>ostream &operator<<(ostream &,linkmatrix<type>&);template<cl

23、ass type>linkmatrix<type> operator +(const linkmatrix<type> &a,const linkmatrix<type> &b);template<class type>class matrixnode friend class linkmatrix<type>friend istream&operator>>(istream&,linkmatrix<type>&); friend ostream&opera

24、tor<<(ostream&out, linkmatrix<type>&); friend linkmatrix<type> operator +(const linkmatrix<type> &a,const linkmatrix<type> &b);private:int row,col;matrixnode<type>*right,*down;uniontype data;matrixnode<type>*next;template<class type>cla

25、ss linkmatrixprivate:matrixnode<type> *head;void insertincol(matrixnode<type>*p);void deleteincol(matrixnode<type>*p);public:friend istream&operator>>(istream&in,linkmatrix<type>&);friend ostream&operator<<(ostream&out,linkmatrix<type>&am

26、p;);matrixnode<type>* head(int i);linkmatrix<type>&operator +=(const linkmatrix<type> &a);friend linkmatrix<type> operator +(const linkmatrix<type> &a,const linkmatrix<type> &b); ;int main()linkmatrix<int>a,b,c;cin>>a;cout<<"

27、a矩陣為：n"<<a<<endl;cin>>b;cout<<"b矩陣為：n"<<b<<endl;c=a+b;cout<<"a+b=n"<<c<<endl;system("pause");return 0;template<class type>istream&operator>>(istream&in,linkmatrix<type>&a)int m,n,te

28、rms,s;matrixnode<type>*cp,*p,*q;cout<<"輸入矩陣的行數(shù)、列數(shù)、和非零元素個數(shù)"<<endl;in>>m>>n>>terms;if(n>m)s=n;else s=m;a.head=new matrixnode<type>a.head->row=m;a.head->col=n;a.head->right=a.head->down=null;cp=new matrixnode<type>*s+1;cp0=a.head;

29、int i;for(i=1;i<=s;i+)p=new matrixnode<type>p->row=p->col=0;p->right=p->down=p;cpi=p;cpi-1->next=p;cps->next=a.head;for(i=1;i<=terms;i+)cout<<"輸入一個非零元三元組(row,col,value)"<<endl;p=new matrixnode<type>in>>p->row>>p->col>>

30、p->data;q=cpp->row;while(q->right!=cpp->row&&(q->right->col<p->col)q=q->right;p->right=q->right;q->right=p;q=cpp->col;while(q->down!=cpp->row&&(q->down->col<p->col)q=q->down;p->down=q->down;q->down=p;deletecp;return

31、 in;template<class type> matrixnode<type>* linkmatrix<type>:head(int i) matrixnode<type>*a;a=head->next;for(int j=1;j<i;j+)a=a->next; return a;template<class type>void linkmatrix<type>:insertincol(matrixnode<type>*p)matrixnode<type>*pre,*ch=he

32、ad(p->col);pre=ch;while(pre->down!=ch&&pre->down->row<p->row)pre=pre->down;p->down=pre->down;pre->down=p;template<class type>void linkmatrix<type>:deleteincol(matrixnode<type>*p)matrixnode<type>*pre,*ch=head(p->col);pre=ch;while(pre-&g

33、t;down!=ch&&pre->down!=p)pre=pre->down;if(pre->down=p)pre->down=p->down;delete p;/else throw invalid_arguement("no such a node to be deleted in deleteincol()");template<class type> /重載符合賦值運算符+=linkmatrix<type>&linkmatrix<type>:operator +=(const

34、linkmatrix<type> &a)matrixnode<type> *pre,*pa,*h,*ah,*p,*tmp;if(head->col !=a.head->col|head->row !=a.head->row)/非同型矩陣不可相加cout<<"the two matrice aren't isomorphic!"/throw domain_error("the two matrice aren't isomorphic!");h=head->next;ah=a.head->next; /h、ah指向當(dāng)前處理行的頭結(jié)點while(h !=head) /逐一處理各行pre=h; p=h->right; /p指向被加矩陣的當(dāng)前結(jié)點，pre指向其前驅(qū)pa=ah->right; /pa分別指向加矩陣的當(dāng)前結(jié)點whi