本文格式為Word版，下載可任意編輯——數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告（十字鏈表實現(xiàn)稀疏矩陣的加法）

一、問題描述

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

1、功能要求：根據(jù)用戶輸入的矩陣，實現(xiàn)稀疏矩陣的求和運算，并輸出結(jié)果。

2、輸入要求：矩陣的數(shù)據(jù)在程序運行的時候由用戶提供，先由用戶輸入稀疏矩陣的行數(shù)、列數(shù)和非零元個數(shù)。再根據(jù)非零元個數(shù)，輸入這些非零元，還需要用戶為這些非零元輸入行、列和非零元的值。這樣，一個稀疏矩陣就輸入完成。若輸入

432

則表示這個稀疏矩陣有4行3列2個非零元

然后用戶需要為這兩個非零元輸入行、列、非零元的值如：

122411

表示第一個非零元行為1，列為2,，值為2；其次個非零元行為4，列為1，值為1。此過程輸入的稀疏矩陣為：

020000000100

3、輸出要求：輸出按矩陣輸出，按行列依次輸出，非零元則輸出非零元的值，不是非零元則輸出“0〞。各元素之間用空格隔開。最終輸出完整的矩陣。

二、概要設(shè)計

1．稀疏矩陣的抽象數(shù)據(jù)類型定義如下：??ADTSparseMatrix{??

數(shù)據(jù)對象：??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={|1classMatrixNode{

friendclassLinkMatrix;friendistreamfriendostream

friendLinkMatrixoperator+(constLinkMatrixprivate:introw,col;MatrixNode*right,*down;union{Typedata;MatrixNode*next;};};

2、鏈表類

templateclassLinkMatrix{private:MatrixNode*head;voidInsertInCol(MatrixNode*p);voidDeleteInCol(MatrixNode*p);public:

friendistreamfriendostreamMatrixNode*Head(inti);LinkMatrixfriendLinkMatrixoperator+(constLinkMatrix};

3、求頭結(jié)點函數(shù)

templateMatrixNode*LinkMatrix::Head(inti){

MatrixNode*a;a=head->next;for(intj=1;jnext;}returna;}

4、將結(jié)點p插入p->col列中

templatevoidLinkMatrix::InsertInCol(MatrixNode*p){MatrixNode*pre,*ch=Head(p->col);pre=ch;while(pre->down!=chp->down=pre->down;pre->down=p;}

5、在p->col列中刪除結(jié)點p，并釋放空間

templatevoidLinkMatrix::DeleteInCol(MatrixNode*p){MatrixNode*pre,*ch=Head(p->col);pre=ch;while(pre->down!=chif(pre->down==p){pre->down=p->down;deletep;}}

6、重載>>函數(shù)

templateistreamMatrixNode**cp,*p,*q;cout>m>>n>>terms;if(n>m)s=n;elses=m;a.head=newMatrixNode;a.head->row=m;a.head->col=n;a.head->right=a.head->down=NULL;cp=newMatrixNode*[s+1];cp[0]=a.head;inti;for(i=1;i;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;in>>p->row>>p->col>>p->data;q=cp[p->row];while((q->right!=cp[p->row]p->right=q->right;q->right=p;q=cp[p->col];while((q->down!=cp[p->row]p->down=q->down;q->down=p;}delete[]cp;returnin;}

7、重載

ostreamirow;i++){MatrixNode*b=a.Head(i);b=b->right;for(intj=1;jcol;j++){if(b->row==ib=b->right;}else{cout//重載符合賦值運算符+=

LinkMatrix

if(head->col!=a.head->col||head->row!=a.head->row)//非同型矩陣不可相加coutnext;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!=ah){//處理當(dāng)前行

if(p!=hp=p->right;}

elseif(p==h||p->col>pa->col){tmp=newMatrixNode(*pa);

pre->right=tmp;//在行鏈表中插入pa復(fù)制結(jié)點tmp

tmp->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，則刪除之（行、列都要刪除）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//重載加法運算符+

LinkMatrixoperator+(constLinkMatrix//復(fù)制構(gòu)造函數(shù)得到被加矩陣A的一個副本放在矩陣C中c+=b;returnc;}

五、測試與探討1、編譯環(huán)境VisualC++6.02、main函數(shù)intmain(){LinkMatrixa,b,c;cin>>a;cout>b;cout〞。

輸入

111

表示第一個三元組的行為1，列為1，值為1

然后程序繼續(xù)提醒“輸入一個非零元三元組〞。

按要求再依次輸入222315

則矩陣A輸入完成，程序按矩陣格式輸出矩陣A

程序繼續(xù)提醒“請輸入行數(shù)、列數(shù)、非零元個數(shù)〞在按上述操作繼續(xù)輸入334112211311333

為矩陣B輸入，完成后程序輸入矩陣B程序同時輸出A+B

3、結(jié)果分析

程序提供輸入和輸出，根據(jù)輸入的矩陣A和矩陣B，A+B計算結(jié)果確鑿無誤。

六、用戶手冊

使用本程序簡單明白，只需根據(jù)提醒為稀疏矩陣輸入，就可以計算出稀疏矩陣的和。

附錄：源代碼

(只含pro1.cpp)：

//pro1.cpp

#includeusingnamespacestd;

templateclassMatrixNode;templateclassLinkMatrix;

templateistreamtemplateostream

templateLinkMatrixoperator+(constLinkMatrix

templateclassMatrixNode{

friendclassLinkMatrix;friendistreamfriendostream

friendLinkMatrixoperator+(constLinkMatrixprivate:introw,col;MatrixNode*right,*down;union{Typedata;MatrixNode*next;};};

templateclassLinkMatrix{private:MatrixNode*head;voidInsertInCol(MatrixNode*p);voidDeleteInCol(MatrixNode*p);public:friendistreamfriendostreamMatrixNode*Head(inti);LinkMatrix

friendLinkMatrixoperator+(constLinkMatrix};

templateistreamMatrixNode**cp,*p,*q;cout>m>>n>>terms;if(n>m)s=n;elses=m;a.head=newMatrixNode;a.head->row=m;a.head->col=n;a.head->right=a.head->down=NULL;cp=newMatrixNode*[s+1];cp[0]=a.head;inti;for(i=1;i;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;in>>p->row>>p->col>>p->data;q=cp[p->row];while((q->right!=cp[p->row]p->right=q->right;q->right=p;q=cp[p->col];while((q->down!=cp[p->row]p->down=q->down;q->down=p;}delete[]cp;returnin;

}

templateMatrixNode*LinkMatrix::Head(inti){

MatrixNode*a;a=head->next;for(intj=1;jnext;}returna;}

templatevoidLinkMatrix::InsertInCol(MatrixNode*p){MatrixNode*pre,*ch=Head(p->col);pre=ch;while(pre->down!=chp->down=pre->down;pre->down=p;}

templatevoidLinkMatrix::DeleteInCol(MatrixNode*p){MatrixNode*pre,*ch=Head(p->col);pre=ch;while(pre->down!=chif(pre->down==p){pre->down=p->down;deletep;}//elsethrowinvalid_arguement(\}

template//重載符合賦值運算符+=

LinkMatrixif(head->col!=a.head->col||head->row!=a.head->row)//非同型矩陣不可相加coutnext;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!=ah){//處理當(dāng)前行if(p!=hp=p->right;}elseif(p==h||p->col>pa->col){//若加矩陣的列標(biāo)更小，則插入tmp=newMatrixNode(*pa);pre->right=tmp;//在行鏈表中插入pa復(fù)制結(jié)點tm