十字鏈表實現(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=|1=i=m,1=j=n-1Col=|1=i=m-1,1=j=n基本操作：CreateSMatrix(&M);/建立稀疏矩陣MDestroySMatrix(&M);/

3、銷毀稀疏矩陣M；TransposeSMatrix(M);/求稀疏矩陣的轉(zhuǎn)置矩陣AddSMatrix(&M,&N);/求稀疏矩陣M和N之和MulSMatrix(&M,&N);/求稀疏矩陣M和N之積ADT SparseMatrix2、 存儲結(jié)構(gòu)選擇采用十字鏈表存儲稀疏矩陣，它是稀疏矩陣鏈式表示的一種較好的表示方法。在十字鏈表中，每一個非零矩陣元素存儲在一個結(jié)點內(nèi)。每一個節(jié)點除了存儲非零元素的三元組以外，還設(shè)置了right和down兩個指針，分別指向同一行的下一個非零元素結(jié)點和同一列的下一個非零元結(jié)點。3、 其他函數(shù)1） 主函數(shù)main（）2） 作為友元函數(shù)的加法運算。4、 詳細設(shè)計用十字鏈表表示稀

4、疏矩陣，需要定義結(jié)點類和鏈表類兩個類1、 結(jié)點類MatrixNodetemplateclass MatrixNode friend class LinkMatrix;friend istream&operator(istream&,LinkMatrix&); friend ostream&operator(ostream&out, LinkMatrix&); friend LinkMatrix operator +(const LinkMatrix &a,const LinkMatrix &b);private:int row,col;MatrixNode*right,*down;unionT

5、ype data;MatrixNode*next;2、 鏈表類templateclass LinkMatrixprivate:MatrixNode *head;void InsertInCol(MatrixNode*p);void DeleteInCol(MatrixNode*p);public:friend istream&operator(istream&in,LinkMatrix&);friend ostream&operator(ostream&out,LinkMatrix&);MatrixNode* Head(int i);LinkMatrix&operator +=(const L

6、inkMatrix &a);friend LinkMatrix operator +(const LinkMatrix &a,const LinkMatrix &b); ;3、 求頭結(jié)點函數(shù)template MatrixNode* LinkMatrix:Head(int i) MatrixNode*a;a=head-next;for(int j=1;jnext; return a;4、 將結(jié)點p插入p-col列中templatevoid LinkMatrix:InsertInCol(MatrixNode*p)MatrixNode*pre,*ch=Head(p-col);pre=ch;while

7、(pre-down!=ch&pre-down-rowrow)pre=pre-down;p-down=pre-down;pre-down=p;5、 在p-col列中刪除結(jié)點p，并釋放空間templatevoid LinkMatrix:DeleteInCol(MatrixNode*p)MatrixNode*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;delete p;6、 重載函數(shù)templateistream&operator(istrea

8、m&in,LinkMatrix&a)int m,n,terms,s;MatrixNode*cp,*p,*q;cout輸入矩陣的行數(shù)、列數(shù)、和非零元素個數(shù)mnterms;if(nm)s=n;else s=m;a.head=new MatrixNode;a.head-row=m;a.head-col=n;a.head-right=a.head-down=NULL;cp=new MatrixNode*s+1;cp0=a.head;int i;for(i=1;i=s;i+)p=new MatrixNode;p-row=p-col=0;p-right=p-down=p;cpi=p;cpi-1-next=

9、p;cps-next=a.head;for(i=1;i=terms;i+)cout輸入一個非零元三元組(row,col,value)endl;p=new MatrixNode;inp-rowp-colp-data;q=cpp-row;while(q-right!=cpp-row&(q-right-colcol)q=q-right;p-right=q-right;q-right=p;q=cpp-col;while(q-down!=cpp-row&(q-down-colcol)q=q-down;p-down=q-down;q-down=p;deletecp;return in;7、 重載函數(shù)tem

10、plateostream & operator(ostream & out ,LinkMatrix& a)for(int i=1;irow;i+)MatrixNode*b=a.Head(i);b=b-right;for(int j=1;jcol;j+)if(b-row=i&b-col=j)coutdataright;elsecout0 ;coutendl;return out; 8、 重載+=實現(xiàn)求和函數(shù)template /重載符合賦值運算符+=LinkMatrix&LinkMatrix:operator +=(const LinkMatrix &a)MatrixNode *pre,*pa,*

11、h,*ah,*p,*tmp;if(head-col !=a.head-col|head-row !=a.head-row)/非同型矩陣不可相加coutnext;ah=a.head-next; /h、ah指向當前處理行的頭結(jié)點while(h !=head) /逐一處理各行pre=h; p=h-right; /p指向被加矩陣的當前結(jié)點，pre指向其前驅(qū)pa=ah-right; /pa分別指向加矩陣的當前結(jié)點while(pa !=ah) /處理當前行if(p !=h&(p-colcol) /若被加矩陣的列標更小，則比較下一個pre=p; p=p-right;else if(p=h|p-colpa-c

12、ol) tmp=new MatrixNode(*pa) ;pre-right=tmp; /在行鏈表中插入pa復制結(jié)點tmptmp-right=p;InsertInCol(tmp); /在列表中插入tmppre=tmp; /當前指針p的前驅(qū)變?yōu)閠mppa=pa-right;else /列標相同，則做加法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

13、-next; ah=ah-next; /處理下一行return *this;9、 重載+template /重載加法運算符+LinkMatrix operator +(const LinkMatrix &a,const LinkMatrix &b)LinkMatrix c(a); /復制構(gòu)造函數(shù)得到被加矩陣A的一個副本放在矩陣C中c+=b;return c;5、 調(diào)試與測試1、 編譯環(huán)境Visual C+ 6.02、 main函數(shù)int main()LinkMatrixa,b,c;cina;coutA矩陣為：nab;coutB矩陣為：nbendl;c=a+b;coutA+B=ncendl;sy

14、stem(pause);return 0;3、 具體步驟按F5編譯，界面出現(xiàn)提示“請輸入行數(shù)、列數(shù)、非零元個數(shù)”。輸入3 3 3表示這個矩陣行數(shù)為3，列數(shù)為3，非零元個數(shù)為3，接著提示“請輸入一個非零元三元組”。輸入1 1 1表示第一個三元組的行為1，列為1，值為1然后程序繼續(xù)提示“輸入一個非零元三元組”。按要求再依次輸入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ù)輸入的矩陣

15、A和矩陣B，A+B計算結(jié)果準確無誤。6、 使用說明使用本程序簡單明了，只需根據(jù)提示為稀疏矩陣輸入，就可以計算出稀疏矩陣的和。附錄2： 十字鏈表實現(xiàn)稀疏矩陣相加源程序 軟件3班 魏希 201005070301#includeusing namespace std;templateclass MatrixNode; templateclass LinkMatrix;templateistream &operator(istream &,LinkMatrix&);templateostream &operator(ostream &,LinkMatrix&);templateLinkMatrix o

16、perator +(const LinkMatrix &a,const LinkMatrix &b);templateclass MatrixNode friend class LinkMatrix;friend istream&operator(istream&,LinkMatrix&); friend ostream&operator(ostream&out, LinkMatrix&); friend LinkMatrix operator +(const LinkMatrix &a,const LinkMatrix &b);private:int row,col;MatrixNode*r

17、ight,*down;unionType data;MatrixNode*next;templateclass LinkMatrixprivate:MatrixNode *head;void InsertInCol(MatrixNode*p);void DeleteInCol(MatrixNode*p);public:friend istream&operator(istream&in,LinkMatrix&);friend ostream&operator(ostream&out,LinkMatrix&);MatrixNode* Head(int i);LinkMatrix&operator

18、 +=(const LinkMatrix &a);friend LinkMatrix operator +(const LinkMatrix &a,const LinkMatrix &b); ;int main()LinkMatrixa,b,c;cina;coutA矩陣為：nab;coutB矩陣為：nbendl;c=a+b;coutA+B=ncendl;system(pause);return 0;templateistream&operator(istream&in,LinkMatrix&a)int m,n,terms,s;MatrixNode*cp,*p,*q;cout輸入矩陣的行數(shù)、列數(shù)

19、、和非零元素個數(shù)mnterms;if(nm)s=n;else s=m;a.head=new MatrixNode;a.head-row=m;a.head-col=n;a.head-right=a.head-down=NULL;cp=new MatrixNode*s+1;cp0=a.head;int i;for(i=1;i=s;i+)p=new MatrixNode;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)en

20、dl;p=new MatrixNode;inp-rowp-colp-data;q=cpp-row;while(q-right!=cpp-row&(q-right-colcol)q=q-right;p-right=q-right;q-right=p;q=cpp-col;while(q-down!=cpp-row&(q-down-colcol)q=q-down;p-down=q-down;q-down=p;deletecp;return in;template MatrixNode* LinkMatrix:Head(int i) MatrixNode*a;a=head-next;for(int j

21、=1;jnext; return a;templatevoid LinkMatrix:InsertInCol(MatrixNode*p)MatrixNode*pre,*ch=Head(p-col);pre=ch;while(pre-down!=ch&pre-down-rowrow)pre=pre-down;p-down=pre-down;pre-down=p;templatevoid LinkMatrix:DeleteInCol(MatrixNode*p)MatrixNode*pre,*ch=Head(p-col);pre=ch;while(pre-down!=ch&pre-down!=p)p

22、re=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 /重載符合賦值運算符+=LinkMatrix&LinkMatrix:operator +=(const LinkMatrix &a)MatrixNode *pre,*pa,*h,*ah,*p,*tmp;if(head-col !=a.head-col|head-row !=a.head-row)/非同型矩陣不可相加coutnext;ah=a.head-next; /h、ah指向當前處理行的頭結(jié)點while(h !=head) /逐一處理各行pre=h; p=h-right; /p指向被加矩陣的當前結(jié)點，pre指向其前驅(qū)pa=ah-right; /pa分別指向加矩陣的當前結(jié)點while(pa !=ah) /處理當前行if(p !=