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

./實(shí)驗(yàn)二十字鏈表一、實(shí)驗(yàn)題目以十字鏈表為儲(chǔ)存結(jié)構(gòu),實(shí)現(xiàn)稀疏矩陣的求和運(yùn)算。二、問(wèn)題描述功能要求：根據(jù)用戶輸入的矩陣,實(shí)現(xiàn)稀疏矩陣的求和運(yùn)算,并輸出結(jié)果。輸入要求：矩陣的數(shù)據(jù)在程序運(yùn)行的時(shí)候由用戶提供,先由用戶輸入稀疏矩陣的行數(shù)、列數(shù)和非零元個(gè)數(shù)。再根據(jù)非零元個(gè)數(shù),輸入這些非零元,還需要用戶為這些非零元輸入行、列和非零元的值。這樣,一個(gè)稀疏矩陣就輸入完成。若輸入332則表示這個(gè)稀疏矩陣有3行3列2個(gè)非零元然后用戶需要為這兩個(gè)非零元輸入行、列、非零元的值如：112221表示第一個(gè)非零元行為1,列為1,,值為2；第二個(gè)非零元行為2,列為2,值為1。此過(guò)程輸入的稀疏矩陣為：200010000輸出要求：輸出按矩陣輸出,按行列依次輸出,非零元?jiǎng)t輸出非零元的值,不是非零元?jiǎng)t輸出"0"。各元素之間用空格隔開(kāi)。最后輸出完整的矩陣。三、概要設(shè)計(jì)1．稀疏矩陣的抽象數(shù)據(jù)類型定義如下：

ADTSparseMatrix{

數(shù)據(jù)對(duì)象：

D={aij|i=1,2,3……m,j=1,2,3……n;aij屬于ElemSet,m和n分別是稀疏矩陣的行數(shù)和列數(shù)}數(shù)據(jù)關(guān)系：R={Row,Col}Row={<aij,aij+1>|1<=i<=m,1<=j<=n-1}Col={<aij,ai+1j>|1<=i<=m-1,1<=j<=n}基本操作：CreateSMatrix<&M>;//建立稀疏矩陣MDestroySMatrix<&M>;//銷(xiāo)毀稀疏矩陣M；TransposeSMatrix<M>;//求稀疏矩陣的轉(zhuǎn)置矩陣AddSMatrix<&M,&N>;//求稀疏矩陣M和N之和MulSMatrix<&M,&N>;//求稀疏矩陣M和N之積}ADTSparseMatrix存儲(chǔ)結(jié)構(gòu)選擇采用十字鏈表存儲(chǔ)稀疏矩陣,它是稀疏矩陣鏈?zhǔn)奖硎镜囊环N較好的表示方法。在十字鏈表中,每一個(gè)非零矩陣元素存儲(chǔ)在一個(gè)結(jié)點(diǎn)。每一個(gè)節(jié)點(diǎn)除了存儲(chǔ)非零元素的三元組以外,還設(shè)置了right和down兩個(gè)指針,分別指向同一行的下一個(gè)非零元素結(jié)點(diǎn)和同一列的下一個(gè)非零元結(jié)點(diǎn)。其他函數(shù)主函數(shù)main〔作為友元函數(shù)的加法運(yùn)算。詳細(xì)設(shè)計(jì)用十字鏈表表示稀疏矩陣,需要定義結(jié)點(diǎn)類和鏈表類兩個(gè)類結(jié)點(diǎn)類MatrixNodetemplate<classType>classMatrixNode{friendclassLinkMatrix<Type>; friendistream&operator>><istream&,LinkMatrix<Type>&>;friendostream&operator<<<ostream&out,LinkMatrix<Type>&>;friendLinkMatrix<Type>operator+<constLinkMatrix<Type>&a,constLinkMatrix<Type>&b>; private: introw,col; MatrixNode<Type>*right,*down; union{ Typedata; MatrixNode<Type>*next; };};鏈表類template<classType>classLinkMatrix{ private: MatrixNode<Type>*head; voidInsertInCol<MatrixNode<Type>*p>; voidDeleteInCol<MatrixNode<Type>*p>; public: friendistream&operator>><istream&in,LinkMatrix<Type>&>; friendostream&operator<<<ostream&out,LinkMatrix<Type>&>; MatrixNode<Type>*Head<inti>; LinkMatrix<Type>&operator+=<constLinkMatrix<Type>&a>; friendLinkMatrix<Type>operator+<constLinkMatrix<Type>&a,constLinkMatrix<Type>&b>;};求頭結(jié)點(diǎn)函數(shù)template<classType>MatrixNode<Type>*LinkMatrix<Type>::Head<inti>{MatrixNode<Type>*a; a=head->next; for<intj=1;j<i;j++> { a=a->next; } returna;}將結(jié)點(diǎn)p插入p->col列中template<classType>voidLinkMatrix<Type>::InsertInCol<MatrixNode<Type>*p>{ MatrixNode<Type>*pre,*ch=Head<p->col>; pre=ch; while<pre->down!=ch&&pre->down->row<p->row>pre=pre->down; p->down=pre->down; pre->down=p;}在p->col列中刪除結(jié)點(diǎn)p,并釋放空間template<classType>voidLinkMatrix<Type>::DeleteInCol<MatrixNode<Type>*p>{ MatrixNode<Type>*pre,*ch=Head<p->col>; pre=ch; while<pre->down!=ch&&pre->down!=p>pre=pre->down; if<pre->down==p> { pre->down=p->down; deletep; }}重載>>函數(shù)template<classType> istream&operator>><istream&in,LinkMatrix<Type>&a>{ intm,n,terms,s; MatrixNode<Type>**cp,*p,*q; cout<<"輸入矩陣的行數(shù)、列數(shù)、和非零元素個(gè)數(shù)"<<endl; in>>m>>n>>terms; if<n>m>s=n;elses=m; a.head=newMatrixNode<Type>; a.head->row=m; a.head->col=n; a.head->right=a.head->down=NULL; cp=newMatrixNode<Type>*[s+1]; cp[0]=a.head; inti; for<i=1;i<=s;i++> { p=newMatrixNode<Type>; p->row=p->col=0; p->right=p->down=p; cp[i]=p;cp[i-1]->next=p; } cp[s]->next=a.head; for<i=1;i<=terms;i++> { cout<<"輸入一個(gè)非零元三元組<row,col,value>"<<endl; p=newMatrixNode<Type>; in>>p->row>>p->col>>p->data; q=cp[p->row]; while<<q->right!=cp[p->row]&&<q->right->col<p->col>>>q=q->right; p->right=q->right; q->right=p; q=cp[p->col]; while<<q->down!=cp[p->row]&&<q->down->col<p->col>>>q=q->down; p->down=q->down; q->down=p; } delete[]cp; returnin;}重載<<函數(shù)template<classType>ostream&operator<<<ostream&out,LinkMatrix<Type>&a>{ for<inti=1;i<=a.head->row;i++> { MatrixNode<Type>*b=a.Head<i>; b=b->right; for<intj=1;j<=a.head->col;j++> { if<b->row==i&&b->col==j> { cout<<b->data<<''; b=b->right; } else { cout<<'0'<<''; } } cout<<endl; } returnout;}重載+=實(shí)現(xiàn)求和函數(shù)template<classType>//重載符合賦值運(yùn)算符+=LinkMatrix<Type>&LinkMatrix<Type>::operator+=<constLinkMatrix<Type>&a>{MatrixNode<Type>*pre,*pa,*h,*ah,*p,*tmp;if<head->col!=a.head->col||head->row!=a.head->row>//非同型矩陣不可相加cout<<"Thetwomatricearen'tisomorphic!";//throwdomain_error<"Thetwomatricearen'tisomorphic!">;h=head->next;ah=a.head->next;//h、ah指向當(dāng)前處理行的頭結(jié)點(diǎn)while<h!=head>{//逐一處理各行pre=h;p=h->right;//p指向被加矩陣的當(dāng)前結(jié)點(diǎn),pre指向其前驅(qū)pa=ah->right;//pa分別指向加矩陣的當(dāng)前結(jié)點(diǎn)while<pa!=ah>{//處理當(dāng)前行if<p!=h&&<p->col<pa->col>>{//若被加矩陣的列標(biāo)更小,則比較下一個(gè)pre=p;p=p->right;}elseif<p==h||p->col>pa->col>{tmp=newMatrixNode<Type><*pa>;pre->right=tmp;//在行鏈表中插入pa復(fù)制結(jié)點(diǎn)tmptmp->right=p;InsertInCol<tmp>;//在列表中插入tmppre=tmp;//當(dāng)前指針p的前驅(qū)變?yōu)閠mppa=pa->right;}else{//列標(biāo)相同,則做加法p->data+=pa->data;if<!p->data>{//和為0,則刪除之〔行、列都要?jiǎng)h除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;}重載+template<classType>//重載加法運(yùn)算符+LinkMatrix<Type>operator+<constLinkMatrix<Type>&a,constLinkMatrix<Type>&b>{LinkMatrix<Type>c<a>;//復(fù)制構(gòu)造函數(shù)得到被加矩陣A的一個(gè)副本放在矩陣C中c+=b;returnc;}調(diào)試與測(cè)試編譯環(huán)境VisualC++6.0main函數(shù)intmain<>{ LinkMatrix<int>a,b,c; cin>>a; cout<<"A矩陣為：\n"<<a<<endl; cin>>b; cout<<"B矩陣為：\n"<<b<<endl; c=a+b; cout<<"A+B=\n"<<c<<endl; system<"pause">; return0;}具體步驟按F5編譯,界面出現(xiàn)提示"請(qǐng)輸入行數(shù)、列數(shù)、非零元個(gè)數(shù)"。輸入333表示這個(gè)矩陣行數(shù)為3,列數(shù)為3,非零元個(gè)數(shù)為3,接著提示"請(qǐng)輸入一個(gè)非零元三元組<row,col,value>"。輸入111表示第一個(gè)三元組的行為1,列為1,值為1然后程序繼續(xù)提示"輸入一個(gè)非零元三元組<row,col,value>"。按要求再依次輸入222315則矩陣A輸入完成,程序按矩陣格式輸出矩陣A程序繼續(xù)提示"請(qǐng)輸入行數(shù)、列數(shù)、非零元個(gè)數(shù)"在按上述操作繼續(xù)輸入334112211311333為矩陣B輸入,完成后程序輸入矩陣B程序同時(shí)輸出A+B結(jié)果分析程序提供輸入和輸出,根據(jù)輸入的矩陣A和矩陣B,A+B計(jì)算結(jié)果準(zhǔn)確無(wú)誤。使用說(shuō)明使用本程序簡(jiǎn)單明了,只需根據(jù)提示為稀疏矩陣輸入,就可以計(jì)算出稀疏矩陣的和。附錄2：十字鏈表實(shí)現(xiàn)稀疏矩陣相加源程序軟件2班7#include<iostream>usingnamespacestd;template<classType>classMatrixNode;template<classType>classLinkMatrix;template<classType>istream&operator>><istream&,LinkMatrix<Type>&>;template<classType>ostream&operator<<<ostream&,LinkMatrix<Type>&>;template<classType>LinkMatrix<Type>operator+<constLinkMatrix<Type>&a,constLinkMatrix<Type>&b>;template<classType>classMatrixNode{friendclassLinkMatrix<Type>; friendistream&operator>><istream&,LinkMatrix<Type>&>;friendostream&operator<<<ostream&out,LinkMatrix<Type>&>;friendLinkMatrix<Type>operator+<constLinkMatrix<Type>&a,constLinkMatrix<Type>&b>; private: introw,col; MatrixNode<Type>*right,*down; union{ Typedata; MatrixNode<Type>*next; };};template<classType>classLinkMatrix{ private: MatrixNode<Type>*head; voidInsertInCol<MatrixNode<Type>*p>; voidDeleteInCol<MatrixNode<Type>*p>; public: friendistream&operator>><istream&in,LinkMatrix<Type>&>; friendostream&operator<<<ostream&out,LinkMatrix<Type>&>; MatrixNode<Type>*Head<inti>; LinkMatrix<Type>&operator+=<constLinkMatrix<Type>&a>; friendLinkMatrix<Type>operator+<constLinkMatrix<Type>&a,constLinkMatrix<Type>&b>;};intmain<>{ LinkMatrix<int>a,b,c; cin>>a; cout<<"A矩陣為：\n"<<a<<endl; cin>>b; cout<<"B矩陣為：\n"<<b<<endl; c=a+b; cout<<"A+B=\n"<<c<<endl; system<"pause">; return0;}template<classType> istream&operator>><istream&in,LinkMatrix<Type>&a>{ intm,n,terms,s; MatrixNode<Type>**cp,*p,*q; cout<<"輸入矩陣的行數(shù)、列數(shù)、和非零元素個(gè)數(shù)"<<endl; in>>m>>n>>terms; if<n>m>s=n;elses=m; a.head=newMatrixNode<Type>; a.head->row=m; a.head->col=n; a.head->right=a.head->down=NULL; cp=newMatrixNode<Type>*[s+1]; cp[0]=a.head; inti; for<i=1;i<=s;i++> { p=newMatrixNode<Type>; p->row=p->col=0; p->right=p->down=p; cp[i]=p;cp[i-1]->next=p; } cp[s]->next=a.head; for<i=1;i<=terms;i++> { cout<<"輸入一個(gè)非零元三元組<row,col,value>"<<endl; p=newMatrixNode<Type>; in>>p->row>>p->col>>p->data; q=cp[p->row]; while<<q->right!=cp[p->row]&&<q->right->col<p->col>>>q=q->right; p->right=q->right; q->right=p; q=cp[p->col]; while<<q->down!=cp[p->row]&&<q->down->col<p->col>>>q=q->down; p->down=q->down; q->down=p; } delete[]cp; returnin;}template<classType>MatrixNode<Type>*LinkMatrix<Type>::Head<inti>{MatrixNode<Type>*a; a=head->next; for<intj=1;j<i;j++> { a=a->next; } returna;}template<classType>voidLinkMatrix<Type>::InsertInCol<MatrixNode<Type>*p>{ MatrixNode<Type>*pre,*ch=Head<p->col>; pre=ch; while<pre->down!=ch&&pre->down->row<p->row>pre=pre->down; p->down=pre->down; pre->down=p;}template<classType>voidLinkMatrix<Type>::DeleteInCol<MatrixNode<Type>*p>{ MatrixNode<Type>*pre,*ch=Head<p->col>; pre=ch; while<pre->down!=ch&&pre->down!=p>pre=pre->down; if<pre->down==p> { pre->down=p->down; deletep; } //elsethrowinvalid_arguement<"NosuchaNodetobedeletedinDeleteInCol<>">;}template<classType>//重載符合賦值運(yùn)算符+=LinkMatrix<Type>&LinkMatrix<Type>::operator+=<constLinkMatrix<Type>&a>{MatrixNode<Type>*pre,*pa,*h,*ah,*p,*tmp;if<head->col!=a.head->col||head->row!=a.head->row>//非同型矩陣不可相加cout<<"Thetwomatricearen'tisomorphic!";//throwdomain_error<"Thetwomatricearen'tisomorphic!">;h=head->next;ah=a.head->next;//h、ah指向當(dāng)前處理行的頭結(jié)點(diǎn)while<h!=head>{//逐一處理各行pre=h;p=h->right;//p指向被加矩陣的當(dāng)前結(jié)點(diǎn),pre指向其前驅(qū)pa=ah->right;//pa分別指向加矩陣的當(dāng)前結(jié)點(diǎn)while<pa!=ah>{//處理當(dāng)前行if<p!