1、課程名稱:開課學(xué)期:課程名稱:開課學(xué)期:班級:指導(dǎo)老師:實(shí)驗(yàn)題目：學(xué)號：姓名：成績評定教師簽名嘉應(yīng)學(xué)院計(jì)算機(jī)學(xué)院實(shí)驗(yàn)報(bào)告數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)2017-2018學(xué)年第2學(xué)期稀疏矩陣運(yùn)算器上機(jī)時(shí)間:【實(shí)驗(yàn)?zāi)康摹可钊胙芯繑?shù)組的存儲表示和實(shí)現(xiàn)技術(shù)，熟悉廣義表存儲結(jié)構(gòu)的特性?！拘枰治觥肯∈杈仃囀侵改切┒鄶?shù)元素為零的矩陣。利用“稀疏”特點(diǎn)進(jìn)行存儲和計(jì)算可以大大節(jié)省存儲空間，提高計(jì)算效率。實(shí)現(xiàn)一個(gè)能進(jìn)行稀疏矩陣基本運(yùn)算的運(yùn)算器。要求以帶“行邏輯鏈接信息”的三元組順序表存儲稀疏矩陣，實(shí)現(xiàn)兩矩陣的相加、相減、相乘等運(yùn)算。輸入以三元組表示，輸出以通常的陣列形式列出?！拒浖脚_】Windows2000,VisualC

2、+6.0或WINTC【概要設(shè)計(jì)】ADTArray數(shù)據(jù)對象：D=aij|0WiWbll,0WjWb2l數(shù)據(jù)關(guān)系：R=ROW,COLROW=|0WiWbl-2,0WjWb2lCOL=l0WiWbll,0WjWb22基本操作：CreateSMatrix(&M);操作結(jié)果:創(chuàng)建稀疏矩陣M.PrintSMatrix(M);初始化條件：稀疏矩陣M存在.操作結(jié)果:輸出稀疏矩陣M.AddSMatrix(M,N,&Q);初始化條件：稀疏矩陣M與N的行數(shù)和列數(shù)對應(yīng)相等.操作結(jié)果:求稀疏矩陣的和Q=M+N.SubSMatrix(MzN,&Q);初始化條件：稀疏矩陣M與N的行數(shù)和列數(shù)對應(yīng)相等.操作結(jié)果:求稀疏矩陣的差

3、Q=M-N.MultSMatrix(M,N,&Q);初始化條件：稀疏矩陣M的列數(shù)等于N的行數(shù).操作結(jié)果:求稀疏矩陣的乘積Q=M*N.ADTArray【主程序模塊】：voidmainO初始化；do接受命令；處理命令；while(命令!=“退出”)；)功能模塊調(diào)用#系圖】主程序模塊U二創(chuàng)建稀疏矩陣模塊typedefstructintrow;行數(shù)intcol;列數(shù)intv;非零元素值triplenode;typedefstructtriplenodedatamaxsize+l;非零元三元組introwtabmaxrow+1;各行第一個(gè)非零元的位置表intmu,nu,tu;矩陣的行數(shù)、列數(shù)和非零元個(gè)數(shù)

4、/rtripletable;voidcreat(rtripletable&A)創(chuàng)建稀疏矩陣voidprint(rtripletableA)輸出稀疏矩陣intaddsmatrix(rtripletableM,rtripletableN)矩陣相加intsubsmatrix(rtripletableM,rtripletableN)稀疏矩陣相減voidmultsmatrix(rtripletableM,rtripletableN,rtripletable&Q)稀疏矩陣相乘【調(diào)試分析】1、由于開始對順序存儲的知識還不熟識，在三元組的存儲和運(yùn)用會導(dǎo)致算法低效。2、做到存儲的時(shí)候，開始時(shí)不知道怎樣存儲三元組

5、，和不知如何去運(yùn)用它的行數(shù)，列數(shù)，非零元素。3、在使用選擇和循環(huán)時(shí)，有時(shí)因?yàn)樽约旱拇中模蜒h(huán)的條件弄錯(cuò)了。4、做本程序用到了數(shù)組的知識，有時(shí)一有不懂的東西又只能打開書來看。5、開始時(shí)沒有把矩陣的加法和減法的情況考慮全面，導(dǎo)致輸出的時(shí)候會出現(xiàn)簡單的錯(cuò)誤。【用戶手冊】1、本程序的運(yùn)行環(huán)境為Windowsme下的MicrosofeVC+6.0,執(zhí)行文件為：xishujuzhen.cppo2、進(jìn)入演示程序后即顯示文本方式的用戶界面:I*稀疏矩陣運(yùn)算I*稀疏矩陣運(yùn)算*A、輸入矩陣1B、輸入矩陣2C、矩陣相加D、矩陣相減E、矩陣相乘F、退出本系統(tǒng)請選擇所需要的操作功能(A,B,C,D,E,F)：3、進(jìn)入

6、界面后，只要選擇數(shù)字命令按“回車鍵”就行。4、接受其他命令后即執(zhí)行相應(yīng)的操作和相應(yīng)的結(jié)果。*歡迎使用稀疏矩陣算*IA、輸入矩陣1TOC o 1-5 h zIB、輸入矩陣2|IC、矩陣相加|ID、矩陣相減|IE、矩陣相乘|IF、退出本系統(tǒng)|請選擇所需要的操作功能(A,B,C,D,E,F):A1請輸入矩陣的行數(shù)和列數(shù)：行數(shù)期數(shù):2酢零兀素不數(shù),1請按行,列和道的形式輸入該矩陣的非零元.并以全零為結(jié)束標(biāo)記!123請選擇所需要的操作功能(A,B,C,D,E,F);B請輸入矩陣的行數(shù)和列數(shù)：行數(shù)：1列數(shù)：2罪零元素個(gè)數(shù)：1請按行，列和值的形式瑜入該矩陣的非零元.并以全零為結(jié)束標(biāo)記!1212請選擇所需要的

7、操作功能(A.B.C.D.E.F)：請選擇所需要的操作功能(A.R.C.D.E.F):C加法結(jié)果為：|04|請選擇所需要的操作功能(A,B,C,D,E,F)：D減法結(jié)果為：1021完整代碼如下：#include#include#include#definemaxsize100#definemaxrow100#defineOK1#defineERROR-1typedefstructintrow;行數(shù)intcol;列數(shù)intv;非零元素值triplenode;typedefstructtriplenodedatamaxsize+l;非零元三元組introwtabmaxrow+1;各行第一個(gè)非零元的

8、位置表intmu,nu,tu;矩陣的行數(shù)、列數(shù)和非零元個(gè)數(shù)Jrtripletable;voidcreat(rtripletable&A)創(chuàng)建稀疏矩陣(intk=l/sum=l,loop/p/t;intnummaxrow+l;請輸入矩陣的行數(shù)和列數(shù):“endl;cout行數(shù):;cinA.mu;cout”歹ij數(shù)：；cinA.nu;cout非零元素個(gè)數(shù):;cinA.tu;cout“請按行，列和值的形式輸入該矩陣的非零元.并以全零為結(jié)束標(biāo)記!”endl;for(loop=l;loop=A.tu;loop+)(cinA.dataloop.rowA.dataloop.colA.dataloop.v;輸入

9、三元組的行數(shù)，列數(shù)和非零元素值)for(p=l;p=A.mu;p+)nump=O;/A三元組每一列的非零元素個(gè)數(shù)for(t=l;t=A.tu;t+)+numA.datat.row;求A中每一列含非零元個(gè)數(shù)A.rowtabl=l;求第P列中第一個(gè)非零元在A.data中的序號for(t=2;t=A.mu;t+)A.rowtabt=A.rowtabt-l+numt-l;return;)voidprint(rtripletableA)輸出稀疏矩陣(intresultmaxrow+lmaxrow+l;定義一個(gè)二維數(shù)組intIoopl,loop2;for(loopl=l;loopl=A.mu;loopl+

10、)for(loop2=l;loop2=A.nu;loop2+)resultlooplloop2=0;初始化為0for(loopl=l;loopl=A.tu;loopl+)resultA.dataloopl.rowA.dataloopl.col=A.dataloopl.v;for(loopl=l;loopl=A.mu;loopl+)(coutT;for(loop2=l;loop2=A.nu;loop2+)coutresultlooplloop2,;輸出所做運(yùn)算的結(jié)果cout|,endl;intaddsmatrix(rtripletableM,rtripletableN)矩陣相加(if(M.mu!

11、=N.mu)行數(shù)相等才能相加coutcc出錯(cuò)rtripletableQ;Q.mu=M.mu;Q.nu=N.nu;intp,q,k;p=l;q=l;k=l;while(p=M.tu&q=N.tu)兩個(gè)稀疏矩陣存在(if(M.datap.row=N.dataq.row)兩個(gè)稀疏矩陣的行數(shù)相等(if(M.datap.col=N.dataq.col)兩個(gè)稀疏矩陣的列數(shù)相等if(M.datap.v+N.dataq.v!=O)兩個(gè)稀疏矩陣相加的結(jié)果不為0(Q.datak.row=M.datap.row;Q.datak.col=M.datap.col;Q.datak.v=M.datap.v+N.dataq.

12、v;+k;)+q;+p;)elseif(M.datap.colN.dataq.col)第一個(gè)稀疏矩陣列數(shù)小于第二個(gè)稀疏矩陣列數(shù)(Q.datak=M.datap;把M中的所有信息都賦給Q+p;+k;)else第一個(gè)稀疏矩陣列數(shù)大于第二個(gè)稀疏矩陣的列數(shù)(Q.datak=N.dataq;+q;+k;)elseif(M.datap.rowN.dataq.row)第一個(gè)稀疏矩陣行列數(shù)小于第二個(gè)稀疏矩陣行數(shù)(Q.datak=M.datap;+p;+k;)else第一個(gè)稀疏矩陣行列數(shù)小于第二個(gè)稀疏矩陣行數(shù)(Q.datak=N.dataq;+q;+k;)while(p=M.tu)只有M并且符合條件(Q.dat

13、ak=M.datap;+p;+k;)while(q=N.tu)只有N并且符合條件(Q.datak=N.dataq;+q;+k;)Q.tu=k-1;cout加法結(jié)果為:endl;print(Q);調(diào)用print()returnOK;intsubsmatrix(rtripletableM,rtripletableN)稀疏矩陣相減(if(M.mu!=N.mu)行數(shù)相等才能相加出錯(cuò);rtripletableQ;Q.mu=M.mu;Q.nu=N.nu;intp,q,k;p=l;q=l;k=l;while(p=M.tu&q=N.tu)兩個(gè)稀疏矩陣存在(if(M.datap.row=N.dataq.row)

14、兩個(gè)稀疏矩陣的行數(shù)相等(if(M.datap.col=N.dataq.col)兩個(gè)稀疏矩陣的列數(shù)相等(if(M.datap.v-N.dataq.v!=O)兩個(gè)稀疏矩陣相減的結(jié)果不為0Q.datak.row=M.datap.row;Q.datak.col=M.datap.col;Q.datak.v=M.datap.v-N.dataq.v;+k;)+q；+p；)if(M.datap.colN.dataq.col)第一個(gè)稀疏矩陣列數(shù)大于第二個(gè)稀疏矩陣的列Q.datak.row=N.dataq.row;Q.datak.col=N.dataq.col;Q.datak.v=-N.dataq.v;+q;+k

15、;)if(M.datap.rowN.dataq.row)第一個(gè)稀疏矩陣行列數(shù)大于第二個(gè)稀疏矩陣行數(shù)(Q.datak.row=N.dataq.row;Q.datak.col=N.dataq.col;Q.datak.v=-N.dataqJ.v;+q;+k;)while(p=M.tu)只有M并且符合條件(Q.datak=M.datap;+p;+k;)while(q=N.tu)只有N并且符合條件(Q.datak.row=N.dataq.row;Q.datak.col=N.dataq.col;Q.datak.v=-N.dataq.v;+q;+k;)Q.tu=k-1;cout減法結(jié)果為:endl;prin

16、t(Q);調(diào)用print()returnOK;voidmultsmatrix(rtripletableM,rtripletableN,rtripletable&Q)稀疏矩陣相乘(intarow,brow;intp,q,tp,t;intccol;intctempmaxrow+l;定義累加器if(M.nu!=N.mu)return;Q.mu=M.mu;Q.nu=N.nu;Q.tu=O;Q初始化if(M.tuN.tu!=O)Q是非零矩陣for(arow=l;arow=M.mu;arow+)處理M的每一行(for(p=l;p=Q.nu;p+)處理M的每一列ctempp=O;當(dāng)前行各元素累加器清零Q.r

17、owtabarow=Q.tu+l;if(arowM.mu)tp=M.rowtabarow+l;elsetp=M.tu+l;for(p=M.rowtabarow;ptp;+p)對當(dāng)前行中每一個(gè)非零元(brow=M.datap.col;找到對應(yīng)元N中的行號if(browN.nu)t=N.rowtabbrow+1;elset=N.tu+l;for(q=N.rowtabbrow;qt;+q)(ccol=N.dataq.col;乘枳元素在Q中列數(shù)ctempccol+=M.datap.v*N.dataq.v;)求得Q中第crow(=arow)行的非零元for(ccol=l;ccolmaxsize)return;Q.dataQ.tu.row=arow;行數(shù)Q.dataQ.tu.col=ccol;歹U數(shù)Q.dataQ.tu.v=ctempccol;累加非零元素值)cout乘法結(jié)果為:endl;print(Q);調(diào)用print()voidmain()charchoice;rtripletableA,B,Q;coutn;coutcc3*11歡迎使用稀疏矩陣運(yùn)算器*In;coutI=InM;coutn|A、輸入矩陣1|n;coutn|B、輸入矩陣2|n;coutn|C、矩陣相加|n;coutn|D、矩陣