課程設(shè)計(jì)報(bào)告材料—稀疏矩陣地完全鏈表表示及其運(yùn)算

1、實(shí)用標(biāo)準(zhǔn)文檔合肥學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系課程設(shè)計(jì)報(bào)告20222022學(xué)年第2學(xué)期課程數(shù)據(jù)結(jié)構(gòu)與算法稀疏矩陣的完全鏈表表示及其運(yùn)算課程設(shè)計(jì)名稱學(xué)生姓名學(xué)號(hào)專業(yè)班級(jí)13軟件工程2班指導(dǎo)教師陳老師2015年1月文案大全實(shí)用標(biāo)準(zhǔn)文檔稀疏矩陣的完全鏈表表示及其運(yùn)算【問題描述】稀疏矩陣的每個(gè)結(jié)點(diǎn)包含down,right,row,col和value五個(gè)域.用單獨(dú)一個(gè)結(jié)點(diǎn)表示一個(gè)非零項(xiàng),并將所有結(jié)點(diǎn)連接在一起,形成兩個(gè)循環(huán)鏈表.使得第一個(gè)表即行表,把所有結(jié)點(diǎn)根據(jù)行序同一行內(nèi)按列序用right域鏈接起來.使得第二個(gè)表即列表,把所有結(jié)點(diǎn)根據(jù)列序同一列內(nèi)按行序用down鏈接起來.這兩個(gè)表共用一個(gè)頭結(jié)點(diǎn).另外,增加一個(gè)

2、包含矩陣維數(shù)的結(jié)點(diǎn).稀疏矩陣的這種存儲(chǔ)表示稱為完全鏈表表式.實(shí)現(xiàn)一個(gè)完全鏈表系統(tǒng)進(jìn)行稀疏矩陣運(yùn)算,并分析以下操作函數(shù)的計(jì)算時(shí)間和額外存儲(chǔ)空間的開銷.【設(shè)計(jì)目的】熟悉和掌握稀疏矩陣的完全鏈表表示；能夠建立并運(yùn)用這種存儲(chǔ)結(jié)構(gòu)【根本要求】建立一個(gè)用戶友好、菜單式系統(tǒng)進(jìn)行以下操作,并使用合當(dāng)?shù)臏y(cè)試數(shù)據(jù)測(cè)試該系統(tǒng).讀取一個(gè)稀疏矩陣建立其完全鏈表表示輸出一個(gè)稀疏矩陣的內(nèi)容刪除一個(gè)稀疏矩陣兩個(gè)稀疏矩陣相加兩個(gè)稀疏矩陣相減兩個(gè)稀疏矩陣相乘稀疏矩陣的轉(zhuǎn)置【實(shí)現(xiàn)提示鏈表上的操作.二、數(shù)據(jù)結(jié)構(gòu)的選擇和概要設(shè)計(jì)一、問題分析1、功能要求：根據(jù)用戶輸入的矩陣,實(shí)現(xiàn)稀疏矩陣的求和運(yùn)算,并輸出結(jié)果.2、輸入要求：矩陣的數(shù)據(jù)在

3、程序運(yùn)行的時(shí)候由用戶提供,先由用戶輸入稀疏矩陣的行數(shù)、列數(shù)和非零元個(gè)數(shù).再根據(jù)非零元個(gè)數(shù),輸入這些非零元,還需要用戶為這些非零元輸入行、列和非零元的值.這樣,一個(gè)稀疏矩陣就輸入完成.3、用單鏈表存儲(chǔ)非零元素的結(jié)點(diǎn)信息,并且將之用矩陣的形式打印出來二、概要設(shè)計(jì)1、結(jié)構(gòu)體的定義typedefintElemType;structOLNodeinti,j;/非零元所在行、歹ElemTypee;/非零元值 OLNode*right,*down;typedefOLNode*OLink;structCrossListOLink*rhead,*chead;/行、列表頭的頭節(jié)點(diǎn)intmu,nu,tu;/矩陣的行

4、、列和非零元個(gè)數(shù)文案大全實(shí)用標(biāo)準(zhǔn)文檔);2、存儲(chǔ)結(jié)構(gòu)選擇采用十字鏈表存儲(chǔ)稀疏矩陣,它是稀疏矩陣鏈?zhǔn)奖硎镜囊环N較好的表示方法.在十字鏈表中,每一個(gè)非零矩陣元素存儲(chǔ)在一個(gè)結(jié)點(diǎn)內(nèi).每一個(gè)節(jié)點(diǎn)除了存儲(chǔ)非零元素的三元組以外,還設(shè)置了right 和down 兩個(gè)指針,分別指向同一行的下一個(gè)非零元素結(jié)點(diǎn)和同一列的下一個(gè)非零元的結(jié)點(diǎn).3、主函數(shù)主函數(shù)包括相加、相減、相乘的各個(gè)子函數(shù).4、菜單具有選擇功能的用戶友好、菜單式系統(tǒng),可以選擇相應(yīng)的功能來處理輸入的數(shù)據(jù).三、詳細(xì)設(shè)計(jì)和編碼1.設(shè)計(jì)表示(2)算法思想稀疏矩陣的每個(gè)結(jié)點(diǎn)包含down,right,row,col和value五個(gè)域.用單獨(dú)一個(gè)結(jié)點(diǎn)表示一個(gè)非零項(xiàng)

5、,并將所有結(jié)點(diǎn)連接在一起,形成兩個(gè)循環(huán)鏈表.使得第一個(gè)表即行表,把所有結(jié)點(diǎn)根據(jù)行序(同一行內(nèi)按列序)用right域鏈接起來.使得第二個(gè)表即列表,把所有結(jié)點(diǎn)根據(jù)列序(同一列內(nèi)按行序)用down鏈接起來.這兩個(gè)表共用一個(gè)頭結(jié)點(diǎn).另外,增加一個(gè)包含矩陣維數(shù)的結(jié)點(diǎn).稀疏矩陣的這種存儲(chǔ)表示稱為完全鏈表表式.(3)主要編碼intCreate(CrossList&M)inti,j,k,m,n,t;ElemTypee;OLNode*p,*q;printf(請(qǐng)輸入稀疏距陣的行數(shù)列數(shù)非零元的個(gè)數(shù)：);scanf(%d%d%d,&m,&n,&t);M.mu=m;M.nu=n;M.tu

6、=t;文案大全實(shí)用標(biāo)準(zhǔn)文檔M.rhead=(OLink*)malloc(m+1)*sizeof(OLink);if(!M.rhead)exit(OVERFLOW);M.chead=(OLink*)malloc(n+1)*sizeof(OLink);if(!M.chead)exit(OVERFLOW);for(k=0;k!=m;k+)初始化行頭指針M.rheadk=NULL;for(k=0;k!=n;k+)初始化列頭指針M.cheadk=NULL;printf(請(qǐng)按任意次序輸入d個(gè)非零元的行列元素值:n,M.tu);for(k=0;km|jn)printf(你輸入的元素不在矩陣中請(qǐng)檢查重輸：n)

7、;exit(OVERFLOW);elsep=(OLNode*)malloc(sizeof(OLNode);if(!p)exit(OVERFLOW);p-i=i;P-j=j;p-e=e;if(M.rheadi=NULL|M.rheadi-jj)/p插入該行第一節(jié)點(diǎn)處p-right=M.rheadi;M.rheadi=p;else/尋找行表插入位置for(q=M.rheadi;q-right&q-right-jright);p-right=q-right;/完成行插入q-right=p;if(M.cheadj=NULL|M.cheadj-ii)/p插入該列第一節(jié)點(diǎn)處p-down=M.che

8、adj;M.cheadj=p;else/尋找列表插入位置文案大全實(shí)用標(biāo)準(zhǔn)文檔(for(q=M.cheadj;q-down&q-down-idown);p-down=q-down;/完成歹U插入q-down=p;returnOK;intPrint(CrossListM)(returnOK;inti,j,k;OLinkp;intarray100100;for(i=0;i!=M.mu;i+)(for(j=0;j!=M.nu;j+)(arrayij=0;/for(k=0;k!=M.nu;k+)(p=M.cheadk;while(p)(arrayp-ip-j=p-e;/p=p-down;for(

9、i=0;i!=M.mu;i+)(for(j=0;j!=M.nu;j+)(if(j=M.nu-1)coutarrayijendl;elsecoutarrayijjj)/矩陣M當(dāng)情前結(jié)點(diǎn)的列小于矩陣N當(dāng)前結(jié)點(diǎn)的列(p=(OLink)malloc(sizeof(OLNode);/生成Q的結(jié)點(diǎn)if(!p)exit(OVERFLOW);Q.tu+;/非零元個(gè)數(shù)+1p-i=i;/賦值p-j=pm-j;p-e=pm-e;p-right=NULL;pm=pm-right;/pm右移elseif(pm-jpn-j)(文案大全實(shí)用標(biāo)準(zhǔn)文檔p=(OLink)malloc(sizeof(OLNode);if(!p)e

10、xit(OVERFLOW);Q.tu+;p-i=i;p-j=pn-j;p-e=pn-e;p-right=NULL;pn=pn-right;elseif(pm-e+pn-e)/M,N當(dāng)前結(jié)點(diǎn)的列相同并且兩元素之和非零p=(OLink)malloc(sizeof(OLNode);if(!p)exit(OVERFLOW);Q.tu+;p-i=i;p-j=pn-j;p-e=pm-e+pn-e;p-right=NULL;pm=pm-right;/pm右移pn=pn-right;pn右移else/兩元素相加為零pm=pm-right;pn=pn-right;continue;if(Q.rheadi=NUL

11、L)Q.rheadi=pq=p;elsepq-right=p;/完成行插入pq=pq-right;if(Q.cheadp-j=NULL)Q.cheadp-j=colp-j=p;elsecolp-j-down=p;/完成列插入colp-j=colp-j-down;文案大全實(shí)用標(biāo)準(zhǔn)文檔while(pm)/將矩陣M該行的剩余元素插入矩陣Q(p=(OLink)malloc(sizeof(OLNode);if(!p)exit(OVERFLOW);Q.tu+;p-i=i;p-j=pm-j;p-e=pm-e;p-right=NULL;pm=pm-right;if(Q.rheadi=NULL)Q.rheadi

12、=pq=p;else(pq-right=p;pq=pq-right;if(Q.cheadp-j=NULL)Q.cheadp-j=colp-j=p;else(colp-j-down=p;colp-j=colp-j-down;while(pn)/將矩陣N該行的剩余元素插入矩陣Q(p=(OLink)malloc(sizeof(OLNode);if(!p)exit(OVERFLOW);Q.tu+;p-i=i;p-j=pn-j;p-e=pn-e;p-right=NULL;pn=pn-right;if(Q.rheadi=NULL)Q.rheadi=pq=p;else(pq-right=p;pq=pq-ri

13、ght;文案大全實(shí)用標(biāo)準(zhǔn)文檔if(Q.cheadp-j=NULL)Q.cheadp-j=colp-j=p;elsecolp-j-down=p;colp-j=colp-j-down;for(k=0;k!=Q.nu;k+)if(colk)colk-down=NULL;free(col);returnOK;CrossListNegative(CrossListM)OLinkp;for(intj=0;j!=M.mu;j+)p=M.rheadj;while(p)p-e=-p-e;/將非零兀的值反號(hào)p=p-right;return(M);文案大全實(shí)用標(biāo)準(zhǔn)文檔r.utdfiLueityintyudytrut

14、ruuyyuiileny.trAtr.utdfiLueityintyudytrutruuyyuiileny.trAtIUIrt,rt,i ii i 【I Ii iiuiui iu u尊k k匕m m廿yuyu _ii_iii iKM保輸入的是h-essanykeytocontinueh-essanykeytocontinueintMult(CrossListM,CrossListN,CrossList&Q)(inti,j,e;OLinkq,p0,q0,q1,q2;if(M.nu!=N.mu)(printf(你輸入的兩個(gè)距陣不能進(jìn)行此操作n);exit(OVERFLOW);else(Q.

15、mu=M.mu;Q.nu=N.nu;Q.tu=0;Q.rhead=(OLink*)malloc(Q.mu+1)*sizeof(OLink);if(!Q.rhead)exit(OVERFLOW);Q.chead=(OLink*)malloc(Q.nu+1)*sizeof(OLink);if(!Q.chead)exit(OVERFLOW);for(i=0;i!=Q.mu;i+)/初始化行Q.rheadi=NULL;文案大全實(shí)用標(biāo)準(zhǔn)文檔for(i=0;i!=Q.nu;i+)初始化列Q.cheadi=NULL;for(i=0;i!=Q.mu;i+)for(j=0;j!=Q.nu;j+)p0=M.rhe

16、adi;q0=N.cheadj;e=0;while(p0&q0)if(q0-ij)q0=q0-down;/列后移elseif(q0-ip0-j)p0=p0-right;行后移elsee=e+p0-e*q0-e;/乘積累加q0=q0-down;p0=p0-right;/行列后移if(e)/e不為零那么插入QQ.tu+;q=(OLink)malloc(sizeof(OLNode);if(!q)exit(OVERFLOW);q-i=i;q-j=j;q-e=e;q-right=NULL;q-down=NULL;if(!Q.rheadi)Q.rheadi=q1=q;elseq1=q1-right

17、=q;if(!Q.cheadj)Q.cheadj=q;elseq2=Q.cheadj;while(q2-down)q2=q2-down;q2-down=q;文案大全實(shí)用標(biāo)準(zhǔn)文檔)returnOK;)四、上機(jī)調(diào)試過程1 .調(diào)試過程中遇到的主要問題是如何解決的：由于代碼是仿照網(wǎng)上代碼參照而寫出來的,網(wǎng)上代碼是C+編寫的,所以局部代碼需要改寫成C語言,由于C+鉞們沒學(xué)過,所以還要通過查詢書籍和網(wǎng)絡(luò)了解C+詡言如何改寫成C語言,1、coutendl;語句等價(jià)于printf例：cout你輸入的是Select;等價(jià)于scanf(%d,&Select);其中Select是int型3、c語言中變量的定

18、義必須在函數(shù)的首部：for(int尸1六;Mmu：J+W像這種的要把intj;提出來2.對(duì)設(shè)計(jì)和編碼的回憶討論和分析：在設(shè)計(jì)方面,主要就是算法思想的設(shè)計(jì),以及具體函數(shù)的設(shè)計(jì)運(yùn)行.在這方面,主要的算法設(shè)計(jì)思想倒不是特別的難想,主要是具體函數(shù)例如加法的函數(shù)的具體設(shè)計(jì))數(shù)非零元的個(gè)零元的行列元潸醯搦款鬣褊歌嗡02021111禰缺的是2 2以P1 1：6 6干果是31310 0比擬繁瑣,消耗了較多時(shí)間.而在編碼方面,由于c語言的學(xué)習(xí)還是在大一下學(xué)期,所以對(duì)于相關(guān)知識(shí)已經(jīng)有所遺忘,所以在編碼的過程遇到了不少問題需要查閱書籍,文案大全實(shí)用標(biāo)準(zhǔn)文檔尤其涉及到具體代碼的編寫,更是花費(fèi)了不少時(shí)間來修正調(diào)試.五、

19、測(cè)試結(jié)果及其分析1、改良設(shè)想：對(duì)于運(yùn)算的界面可以更加精美有條理性一些；除此以外,可以給運(yùn)算設(shè)計(jì)一個(gè)選擇界面,用戶可以選擇進(jìn)行計(jì)算和退出；由于局部代碼是參考網(wǎng)上案列C+編碼的,我想把它改成C語言代碼,丹改正來后,他總是報(bào)錯(cuò),調(diào)試也找不來原因,null指沒有聲明,但在頭文件stdio.h中已有null值得申明,最后自定義個(gè)null值得聲明,還是不行,所以導(dǎo)致我的局部代碼有些不理解,這好似一局部遺憾,希望通過以后的學(xué)習(xí)和學(xué)習(xí)中明白這些原因.2、經(jīng)驗(yàn)和體會(huì)：十字鏈表作為存儲(chǔ)結(jié)構(gòu)表示隨機(jī)稀疏矩陣,進(jìn)行兩矩陣的相加運(yùn)算,所以首先要定義一個(gè)十字鏈表作為存儲(chǔ)結(jié)構(gòu).僅有此還是不夠的,還需要定義指針來指向鏈表中的

20、元素.在開始的時(shí)候,老是得不到想象中的結(jié)果,通過幾次的檢查才發(fā)現(xiàn)問題出在對(duì)矩陣中的元素指向沒有弄清楚,所以即使是相位置上的元素也沒有處理好它們的相加問題.這個(gè)實(shí)驗(yàn)從最初的設(shè)計(jì)到完成,出現(xiàn)了很多錯(cuò)誤,通過最終的修正發(fā)現(xiàn),其實(shí)犯的都是小錯(cuò)誤,都是些指針的問題.由于指針是我比擬薄弱的環(huán)節(jié).我發(fā)現(xiàn)了這些問題,所以我就要進(jìn)行彌補(bǔ)、查缺補(bǔ)漏.通過這次課程設(shè)計(jì),敦促我將過去學(xué)習(xí)過的知識(shí)進(jìn)行了溫習(xí),知識(shí)只有多穩(wěn)固,才能真正的理解與領(lǐng)悟.六、用戶使用說明按提示進(jìn)行相關(guān)操作.3、先運(yùn)行出來：出現(xiàn)主界面2、先選擇你將要運(yùn)算的功能,列如1、相加,然后輸入你第一個(gè)稀疏矩陣的行、歹 h 非零元的個(gè)數(shù),接著輸入非零元素的行

21、、列和值；輸入第二個(gè)稀疏矩陣的行、歹 h 非零元的個(gè)數(shù),接著輸入非零元素的行、列和值；3、輸入完成后,點(diǎn)擊回車,它會(huì)顯示出你所輸入的第一個(gè)稀疏矩陣、第二個(gè)稀疏矩陣,以及它們相加后得到的稀疏矩陣.源程序#include#include#include#include#defineOK1#defineERROR0#defineOVERFLOW-2typedefintElemType;structOLNode文案大全實(shí)用標(biāo)準(zhǔn)文檔inti,j;/非零元所在行、列ElemTypee;/非零元值OLNode*right,*down;)；typedefOLNode*OLink;structCrossList

22、OLink*rhead,*chead;/行、列表頭的頭節(jié)點(diǎn)intmu,nu,tu;/矩陣的行、列和非零元個(gè)數(shù));intCreate(CrossList&M)inti,j,k,m,n,t;ElemTypee;OLNode*p,*q;printf(請(qǐng)輸入稀疏距陣的行數(shù)列數(shù)非零元的個(gè)數(shù)：);scanf(%d%d%d,&m,&n,&t);M.mu=m;M.nu=n;M.tu=t;M.rhead=(OLink*)malloc(m+1)*sizeof(OLink);if(!M.rhead)exit(OVERFLOW);M.chead=(OLink*)malloc(n+1)*

23、sizeof(OLink);if(!M.chead)exit(OVERFLOW);for(k=0;k!=m;k+)/初始化行頭指針M.rheadk=NULL;for(k=0;k!=n;k+)/初始化列頭指針M.cheadk=NULL;printf(請(qǐng)按任意次序輸入d個(gè)非零元的行列元素值:n,M.tu);for(k=0;km|jn)printf(你輸入的元素不在矩陣中請(qǐng)檢查重輸：n);exit(OVERFLOW);)else文案大全實(shí)用標(biāo)準(zhǔn)文檔(p=(OLNode*)malloc(sizeof(OLNode);if(!p)exit(OVERFLOW);p-i=i；P-j=j;p-e=e;if(M

24、.rheadi=NULL|M.rheadi-jj)/p插入該行第一節(jié)點(diǎn)處(p-right=M.rheadi;M.rheadi=p;else/尋找行表插入位置(for(q=M.rheadi;q-right&q-right-jright);p-right=q-right;/完成行插入q-right=p;if(M.cheadj=NULL|M.cheadj-ii)/p插入該列第一節(jié)點(diǎn)處(p-down=M.cheadj;M.cheadj=p;else/尋找列表插入位置(for(q=M.cheadj;q-down&q-down-idown);p-down=q-down;/完成歹U插入q-d

25、own=p;returnOK;intPrint(CrossListM)(inti,j,k;OLinkp;intarray100100;for(i=0;i!=M.mu;i+)(for(j=0;j!=M.nu;j+)(文案大全arrayij=0;/初始化數(shù)組所需局部實(shí)用標(biāo)準(zhǔn)文檔)for(k=0;k!=M.nu;k+)(p=M.cheadk;while(p)(arrayp-ip-j=p-e;將非零元存入數(shù)組中p=p-down;)for(i=0;i!=M.mu;i+)(for(j=0;j!=M.nu;j+)(if(j=M.nu-1)coutarrayijendl;elsecoutarrayijjj)/

26、矩B$M當(dāng)情前結(jié)點(diǎn)的列小于矩陣N當(dāng)前結(jié)點(diǎn)的列p=(OLink)malloc(sizeof(OLNode);/生成Q的結(jié)點(diǎn)if(!p)exit(OVERFLOW);Q.tu+;/非零元個(gè)數(shù)+1p-i=i;/賦值p-j=pm-j;p-e=pm-e;p-right=NULL;pm=pm-right;pm右移elseif(pm-jpn-j)p=(OLink)malloc(sizeof(OLNode);if(!p)exit(OVERFLOW);Q.tu+;p-i=i;p-j=pn-j;p-e=pn-e;p-right=NULL;pn=pn-right;elseif(pm-e+pn-e)/M,N當(dāng)前結(jié)點(diǎn)的

27、列相同并且兩元素之和非零p=(OLink)malloc(sizeof(OLNode);if(!p)exit(OVERFLOW);Q.tu+;p-i=i;p-j=pn-j;p-e=pm-e+pn-e;p-right=NULL;pm=pm-right;/pm右移文案大全實(shí)用標(biāo)準(zhǔn)文檔pn=pn-right;/pn右移)else/兩元素相加為零(pm=pm-right;pn=pn-right;continue;)if(Q.rheadi=NULL)Q.rheadi=pq=p;else(pq-right=p;/完成行插入pq=pq-right;)if(Q.cheadp-j=NULL)Q.cheadp-j=

28、colp-j=p;else(colp-j-down=p;/完成列插入colp-j=colp-j-down;)while(pm)/將矩陣M該行的剩余元素插入矩陣Q(p=(OLink)malloc(sizeof(OLNode);if(!p)exit(OVERFLOW);Q.tu+;p-i=i;p-j=pm-j;p-e=pm-e;p-right=NULL;pm=pm-right;if(Q.rheadi=NULL)Q.rheadi=pq=p;else(pq-right=p;pq=pq-right;)if(Q.cheadp-j=NULL)Q.cheadp-j=colp-j=p;else文案大全實(shí)用標(biāo)準(zhǔn)文

29、檔(colp-j-down=p;colp-j=colp-j-down;)while(pn)/將矩陣N該行的剩余元素插入矩陣Q(p=(OLink)malloc(sizeof(OLNode);if(!p)exit(OVERFLOW);Q.tu+;p-i=i;p-j=pn-j;p-e=pn-e;p-right=NULL;pn=pn-right;if(Q.rheadi=NULL)Q.rheadi=pq=p;else(pq-right=p;pq=pq-right;)if(Q.cheadp-j=NULL)Q.cheadp-j=colp-j=p;else(colp-j-down=p;colp-j=colp-

30、j-down;)for(k=0;k!=Q.nu;k+)if(colk)colk-down=NULL;free(col);returnOK;)CrossListNegative(CrossListM)(OLinkp;for(intj=0;j!=M.mu;j+)(文案大全實(shí)用標(biāo)準(zhǔn)文檔p=M.rheadj;while(p)(p-e=-p-e;將非零兀的值反號(hào)p=p-right;)return(M);)intMult(CrossListM,CrossListN,CrossList&Q)(inti,j,e;OLinkq,p0,q0,q1,q2;if(M.nu!=N.mu)(printf(你輸入的兩個(gè)距陣不能進(jìn)行此操作n);exit(OVERFLOW);)else(Q.mu=M.mu;Q.nu=N.nu;Q.tu=0;Q.rhead=(OLink*)malloc(Q.mu+1)*sizeof(OLink);if(!Q.rhead)exit(OVERFLOW);Q.chead=(OLink*)malloc(Q.nu+1)*sizeof(OLink);if(!Q.chead)exit(OVERFLO