課程設(shè)計報告材料—稀疏矩陣地完全鏈表表示及其運算

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

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

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

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

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

6、=t;文案大全實用標準文檔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(請按任意次序輸入d個非零元的行列元素值:n,M.tu);for(k=0;km|jn)printf(你輸入的元素不在矩陣中請檢查重輸：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é)點處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é)點處p-down=M.che

8、adj;M.cheadj=p;else/尋找列表插入位置文案大全實用標準文檔(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當情前結(jié)點的列小于矩陣N當前結(jié)點的列(p=(OLink)malloc(sizeof(OLNode);/生成Q的結(jié)點if(!p)exit(OVERFLOW);Q.tu+;/非零元個數(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)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當前結(jié)點的列相同并且兩元素之和非零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;文案大全實用標準文檔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;文案大全實用標準文檔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;/將非零兀的值反號p=p-right;return(M);文案大全實用標準文檔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(你輸入的兩個距陣不能進行此操作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;文案大全實用標準文檔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;文案大全實用標準文檔)returnOK;)四、上機調(diào)試過程1 .調(diào)試過程中遇到的主要問題是如何解決的：由于代碼是仿照網(wǎng)上代碼參照而寫出來的,網(wǎng)上代碼是C+編寫的,所以局部代碼需要改寫成C語言,由于C+鉞們沒學過,所以還要通過查詢書籍和網(wǎng)絡(luò)了解C+詡言如何改寫成C語言,1、coutendl;語句等價于printf例：cout你輸入的是Select;等價于scanf(%d,&Select);其中Select是int型3、c語言中變量的定

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

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

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

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

22、OLink*rhead,*chead;/行、列表頭的頭節(jié)點intmu,nu,tu;/矩陣的行、列和非零元個數(shù));intCreate(CrossList&M)inti,j,k,m,n,t;ElemTypee;OLNode*p,*q;printf(請輸入稀疏距陣的行數(shù)列數(shù)非零元的個數(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(請按任意次序輸入d個非零元的行列元素值:n,M.tu);for(k=0;km|jn)printf(你輸入的元素不在矩陣中請檢查重輸：n);exit(OVERFLOW);)else文案大全實用標準文檔(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é)點處(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é)點處(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ù)組所需局部實用標準文檔)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當情前結(jié)點的列小于矩陣N當前結(jié)點的列p=(OLink)malloc(sizeof(OLNode);/生成Q的結(jié)點if(!p)exit(OVERFLOW);Q.tu+;/非零元個數(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當前結(jié)點的

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右移文案大全實用標準文檔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文案大全實用標準文

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+)(文案大全實用標準文檔p=M.rheadj;while(p)(p-e=-p-e;將非零兀的值反號p=p-right;)return(M);)intMult(CrossListM,CrossListN,CrossList&Q)(inti,j,e;OLinkq,p0,q0,q1,q2;if(M.nu!=N.mu)(printf(你輸入的兩個距陣不能進行此操作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