版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
本文格式為Word版,下載可任意編輯——數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告(十字鏈表實(shí)現(xiàn)稀疏矩陣的加法)
一、問(wèn)題描述
十字鏈表實(shí)現(xiàn)稀疏矩陣的加法
1、功能要求:根據(jù)用戶輸入的矩陣,實(shí)現(xiàn)稀疏矩陣的求和運(yùn)算,并輸出結(jié)果。
2、輸入要求:矩陣的數(shù)據(jù)在程序運(yùn)行的時(shí)候由用戶提供,先由用戶輸入稀疏矩陣的行數(shù)、列數(shù)和非零元個(gè)數(shù)。再根據(jù)非零元個(gè)數(shù),輸入這些非零元,還需要用戶為這些非零元輸入行、列和非零元的值。這樣,一個(gè)稀疏矩陣就輸入完成。若輸入
432
則表示這個(gè)稀疏矩陣有4行3列2個(gè)非零元
然后用戶需要為這兩個(gè)非零元輸入行、列、非零元的值如:
122411
表示第一個(gè)非零元行為1,列為2,,值為2;其次個(gè)非零元行為4,列為1,值為1。此過(guò)程輸入的稀疏矩陣為:
020000000100
3、輸出要求:輸出按矩陣輸出,按行列依次輸出,非零元?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={|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é)點(diǎn)函數(shù)
templateMatrixNode*LinkMatrix::Head(inti){
MatrixNode*a;a=head->next;for(intj=1;jnext;}returna;}
4、將結(jié)點(diǎn)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é)點(diǎn)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//重載符合賦值運(yùn)算符+=
LinkMatrix
if(head->col!=a.head->col||head->row!=a.head->row)//非同型矩陣不可相加coutnext;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!=hp=p->right;}
elseif(p==h||p->col>pa->col){tmp=newMatrixNode(*pa);
pre->right=tmp;//在行鏈表中插入pa復(fù)制結(jié)點(diǎn)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,則刪除之(行、列都要?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;}
9、重載+
template//重載加法運(yùn)算符+
LinkMatrixoperator+(constLinkMatrix//復(fù)制構(gòu)造函數(shù)得到被加矩陣A的一個(gè)副本放在矩陣C中c+=b;returnc;}
五、測(cè)試與探討1、編譯環(huán)境VisualC++6.02、main函數(shù)intmain(){LinkMatrixa,b,c;cin>>a;cout>b;cout〞。
輸入
111
表示第一個(gè)三元組的行為1,列為1,值為1
然后程序繼續(xù)提醒“輸入一個(gè)非零元三元組〞。
按要求再依次輸入222315
則矩陣A輸入完成,程序按矩陣格式輸出矩陣A
程序繼續(xù)提醒“請(qǐng)輸入行數(shù)、列數(shù)、非零元個(gè)數(shù)〞在按上述操作繼續(xù)輸入334112211311333
為矩陣B輸入,完成后程序輸入矩陣B程序同時(shí)輸出A+B
3、結(jié)果分析
程序提供輸入和輸出,根據(jù)輸入的矩陣A和矩陣B,A+B計(jì)算結(jié)果確鑿無(wú)誤。
六、用戶手冊(cè)
使用本程序簡(jiǎn)單明白,只需根據(jù)提醒為稀疏矩陣輸入,就可以計(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//重載符合賦值運(yùn)算符+=
LinkMatrixif(head->col!=a.head->col||head->row!=a.head->row)//非同型矩陣不可相加coutnext;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!=hp=p->right;}elseif(p==h||p->col>pa->col){//若加矩陣的列標(biāo)更小,則插入tmp=newMatrixNode(*pa);pre->right=tmp;//在行鏈表中插入pa復(fù)制結(jié)點(diǎn)tm
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 電商平臺(tái)的社交媒體營(yíng)銷培訓(xùn)內(nèi)容策劃
- 新質(zhì)生產(chǎn)力對(duì)旅游業(yè)發(fā)展的促進(jìn)作用
- 商標(biāo)評(píng)估與交易行業(yè)消費(fèi)者群體特征分析
- 自動(dòng)駕駛與機(jī)器學(xué)習(xí)行業(yè)消費(fèi)者群體特征分析
- 2023年張掖市高臺(tái)縣引進(jìn)筆試真題
- 2023年瀘州市江陽(yáng)區(qū)衛(wèi)生事業(yè)單位考核招聘工作人員考試試題及答案
- 2023年福建三鋼集團(tuán)三明本部招聘考試試題及答案
- 2023年大邑縣考核招聘事業(yè)單位筆試真題
- 2024年遼源客運(yùn)從業(yè)資格模擬考試
- 2024年安慶客運(yùn)資格證模擬考試題
- Unit 2 Different families 第四課時(shí)(教學(xué)設(shè)計(jì))-2024-2025學(xué)年人教PEP版(2024)英語(yǔ)三年級(jí)上冊(cè)
- 【生物】第二章認(rèn)識(shí)細(xì)胞作業(yè)設(shè)計(jì)2024-2025學(xué)年人教版生物七年級(jí)上冊(cè)
- 2024年軍隊(duì)文職真題
- 部編本人教版《道德與法治》七年級(jí)上冊(cè)第一單元測(cè)試題(含答案)
- 心肺復(fù)蘇技能操作考核表
- 八年級(jí)物理上冊(cè) 第一章 走進(jìn)實(shí)驗(yàn)室 1.1走進(jìn)實(shí)驗(yàn)室:學(xué)習(xí)科學(xué)探究教學(xué)設(shè)計(jì) (新版)教科版
- 2024秋季開(kāi)學(xué)第一課巴黎奧運(yùn)會(huì)主題班會(huì)
- 中心靜脈壓的監(jiān)測(cè)(CVP)
- 2024時(shí)事政治試題庫(kù)(附含答案)
- 2024-2030年中國(guó)松香(CAS 8050-09-7)行業(yè)市場(chǎng)發(fā)展趨勢(shì)與前景展望戰(zhàn)略分析報(bào)告
- 2024兒童青少年抑郁治療與康復(fù)痛點(diǎn)調(diào)研報(bào)告 -基于患者家長(zhǎng)群體的調(diào)研
評(píng)論
0/150
提交評(píng)論