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

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

3、稀疏矩陣的行數(shù)、列數(shù)和非零元個數(shù)。再根據(jù)非零元個數(shù)，輸入這些非零元，還需要用戶為這些非零元輸入行、列和非零元的值。這樣，一個稀疏矩陣就輸入完成。3、用單鏈表存儲非零元素的結(jié)點(diǎn)信息，并且將之用矩陣的形式打印出來二、概要設(shè)計(jì)1、構(gòu)造體的定義typedef int ElemType;struct OLNode int i,j; /非零元所在行、列 ElemType e;/非零元值 OLNode *right,*down;typedef OLNode *OLink;struct CrossList OLink *rhead,*chead;/行、列表頭的頭節(jié)點(diǎn) int mu,nu,tu;/矩陣的行、列和

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

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

6、u=t; M.rhead=(OLink*)malloc(m+1)*sizeof(OLink); if(!M.rhead) e*it(OVERFLOW); M.chead=(OLink*)malloc(n+1)*sizeof(OLink); if(!M.chead) e*it(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(你輸入的元素不在矩陣中請

7、檢查重輸:n); e*it(OVERFLOW); else p=(OLNode*)malloc(sizeof(OLNode); if(!p) e*it(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插入

8、該列第一節(jié)點(diǎn)處 p-down=M.cheadj; M.cheadj=p; else/尋找列表插入位置 for(q=M.cheadj;q-down&q-down-idown); p-down=q-down;/完成列插入 q-down=p; return OK;int Print(CrossList M) int i,j,k; OLink p; int array100100; 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

9、-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; else coutarrayijjj)/矩陣M當(dāng)情前結(jié)點(diǎn)的列小于矩陣N當(dāng)前結(jié)點(diǎn)的列 p=(OLink)malloc(sizeof(OLNode);/生成Q的結(jié)點(diǎn) if(!p) e*it(OVERFLOW); Q.tu+; /非零元個數(shù)1 p-i=i; /賦值 p-j=pm-j; p-e=pm-e; p-right=NULL; pm=pm-right; /pm右移 else if(pm-jpn-j) p

10、=(OLink)malloc(sizeof(OLNode); if(!p) e*it(OVERFLOW); Q.tu+; p-i=i; p-j=pn-j; p-e=pn-e; p-right=NULL; pn=pn-right; else if(pm-e+pn-e)/M,N當(dāng)前結(jié)點(diǎn)的列一樣并且兩元素之和非零 p=(OLink)malloc(sizeof(OLNode); if(!p) e*it(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右移 e

11、lse/兩元素相加為零 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=colp-j=p; else colp-j-down=p;/完成列插入 colp-j=colp-j-down; while(pm)/將矩陣M該行的剩余元素插入矩陣Q p=(OLink)malloc(sizeof(OLNode); if(!p) e*it(OVERFLOW); Q.tu+; p-i=i;

12、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 colp-j-down=p; colp-j=colp-j-down; while(pn)/將矩陣N該行的剩余元素插入矩陣Q p=(OLink)malloc(sizeof(OLNode); if(!p) e*it(OVERFLOW); Q.tu+; p-i=i; p-j=pn-j; p-e

13、=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-j-down; for(k=0;k!=Q.nu;k+) if(colk) colk-down=NULL; free(col); return OK;CrossList Negative(CrossList M) OLink p; for(int j=0;j!=

14、M.mu;j+) p=M.rheadj; while(p) p-e=-p-e;/將非零元的值反號 p=p-right; return (M); int Mult(CrossList M,CrossList N,CrossList &Q) int i,j,e;OLink q,p0,q0,q1,q2; if(M.nu!=N.mu) printf(你輸入的兩個距陣不能進(jìn)展此操作n); e*it(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)

15、 e*it(OVERFLOW); Q.chead=(OLink*)malloc(Q.nu+1)*sizeof(OLink); if(!Q.chead) e*it(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.rheadi; q0=N.cheadj; e=0; while(p0&q0) if(q0-ij) q0=q0-down;/列后移 else if(q0-ip0-j)

16、p0=p0-right;/行后移 else e=e+p0-e*q0-e;/乘積累加 q0=q0-down; p0=p0-right;/行列后移 if(e)/e不為零則插入Q Q.tu+; q=(OLink)malloc(sizeof(OLNode); if(!q) e*it(OVERFLOW); q-i=i; q-j=j; q-e=e; q-right=NULL; q-down=NULL; if(!Q.rheadi) Q.rheadi=q1=q; else q1=q1-right=q; if(!Q.cheadj) Q.cheadj=q; else q2=Q.cheadj; while(q2-d

17、own) q2=q2-down; q2-down=q; return OK; 四、上機(jī)調(diào)試過程1.調(diào)試過程中遇到的主要問題是如何解決的：由于代碼是仿照網(wǎng)上代碼參照而寫出來的，網(wǎng)上代碼是c+編寫的，所以局部代碼需要改寫成C語言，由于C+我們沒學(xué)過，所以還要通過查詢書籍和網(wǎng)絡(luò)了解C+語言如何改寫成C語言，1、cout endl;語句等價(jià)于printf 例：cout你輸入的是Select;等價(jià)于scanf(%d,&Select); 其中Select是int型 3、c語言中變量的定義必須在函數(shù)的首部：像這種的要把int j;提出來 2.對設(shè)計(jì)和編碼的回憶討論和分析：在設(shè)計(jì)方面，主要就是算法思想的設(shè)計(jì)，

18、以及具體函數(shù)的設(shè)計(jì)運(yùn)行。在這方面，主要的算法設(shè)計(jì)思想倒不是特別的難想，主要是具體函數(shù)例如加法的函數(shù)的具體設(shè)計(jì)比擬繁瑣，消耗了較多時間。而在編碼方面，由于c語言的學(xué)習(xí)還是在大一下學(xué)期，所以對于相關(guān)知識已經(jīng)有所遺忘，所以在編碼的過程遇到了不少問題需要查閱書籍，尤其涉及到具體代碼的編寫，更是花費(fèi)了不少時間來修正調(diào)試。五、測試結(jié)果及其分析 1、改良設(shè)想：對于運(yùn)算的界面可以更加精巧有條理性一些；除此以外，可以給運(yùn)算設(shè)計(jì)一個選擇界面，用戶可以選擇進(jìn)展計(jì)算和退出；由于局部代碼是參考網(wǎng)上案列c+編碼的，我想把它改成C語言代碼，丹改正來后，他總是報(bào)錯，調(diào)試也找不來原因，null指沒有聲明，但在頭文件stdio.

19、h中已有null值得申明，最后自定義個null值得聲明，還是不行，所以導(dǎo)致我的局部代碼有些不理解，這好似一局部遺憾，希望通過以后的學(xué)習(xí)和學(xué)習(xí)中明白這些原因。 2、經(jīng)歷和體會：十字鏈表作為存儲構(gòu)造表示隨機(jī)稀疏矩陣，進(jìn)展兩矩陣的相加運(yùn)算，所以首先要定義一個十字鏈表作為存儲構(gòu)造。僅有此還是不夠的，還需要定義指針來指向鏈表中的元素。在開場的時候，老是得不到想象中的結(jié)果，通過幾次的檢查才發(fā)現(xiàn)問題出在對矩陣中的元素指向沒有弄清楚，所以即使是相位置上的元素也沒有處理好它們的相加問題。這個實(shí)驗(yàn)從最初的設(shè)計(jì)到完成，出現(xiàn)了很多錯誤，通過最終的修正發(fā)現(xiàn)，其實(shí)犯的都是小錯誤，都是些指針的問題。因?yàn)橹羔樖俏冶葦M薄弱的環(huán)

20、節(jié)。我發(fā)現(xiàn)了這些問題，所以我就要進(jìn)展彌補(bǔ)、查缺補(bǔ)漏。通過這次課程設(shè)計(jì)，敦促我將過去學(xué)習(xí)過的知識進(jìn)展了溫習(xí)，知識只有多穩(wěn)固，才能真正的理解與領(lǐng)悟。用戶使用說明按提示進(jìn)展相關(guān)操作。1、先運(yùn)行出來：出現(xiàn)主界面 2、先選擇你將要運(yùn)算的功能，列如1、相加，然后輸入你第一個稀疏矩陣的行、列、非零元的個數(shù)，接著輸入非零元素的行、列和值；輸入第二個稀疏矩陣的行、列、非零元的個數(shù)，接著輸入非零元素的行、列和值；3、輸入完成后，點(diǎn)擊回車，它會顯示出你所輸入的第一個稀疏矩陣、第二個稀疏矩陣，以及它們相加后得到的稀疏矩陣。源程序#include#include#include#include#define OK 1#

21、define ERROR 0#define OVERFLOW -2typedef int ElemType;struct OLNode int i,j; /非零元所在行、列 ElemType e;/非零元值 OLNode *right,*down;typedef OLNode *OLink;struct CrossList OLink *rhead,*chead;/行、列表頭的頭節(jié)點(diǎn) int mu,nu,tu;/矩陣的行、列和非零元個數(shù);int Create(CrossList &M) int i,j,k,m,n,t; ElemType e; OLNode *p,*q; printf(請輸入稀

22、疏距陣的行數(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) e*it(OVERFLOW); M.chead=(OLink*)malloc(n+1)*sizeof(OLink); if(!M.chead) e*it(OVERFLOW); for(k=0;k!=m;k+)/初始化行頭指針 M.rheadk=NULL; for(k=0;k!=n;k+)/初始化列頭指針 M.cheadk=NULL; printf(請按任

23、意次序輸入%d個非零元的行列元素值:n,M.tu); for(k=0;km|jn) printf(你輸入的元素不在矩陣中請檢查重輸:n); e*it(OVERFLOW); else p=(OLNode*)malloc(sizeof(OLNode); if(!p) e*it(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-righ

24、t=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;/完成列插入 q-down=p; return OK;int Print(CrossList M) int i,j,k; OLink p; int array100100; for(i=0;i!=M.mu;i+) for(j=0;j!=M.nu;j+) arrayij=0;

25、/初始化數(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; else coutarrayijjj)/矩陣M當(dāng)情前結(jié)點(diǎn)的列小于矩陣N當(dāng)前結(jié)點(diǎn)的列 p=(OLink)malloc(sizeof(OLNode);/生成Q的結(jié)點(diǎn) if(!p) e*it(OVERFLOW); Q.tu+; /非零元個數(shù)1 p-i=i; /賦值 p-j=pm-j; p

26、-e=pm-e; p-right=NULL; pm=pm-right; /pm右移 else if(pm-jpn-j) p=(OLink)malloc(sizeof(OLNode); if(!p) e*it(OVERFLOW); Q.tu+; p-i=i; p-j=pn-j; p-e=pn-e; p-right=NULL; pn=pn-right; else if(pm-e+pn-e)/M,N當(dāng)前結(jié)點(diǎn)的列一樣并且兩元素之和非零 p=(OLink)malloc(sizeof(OLNode); if(!p) e*it(OVERFLOW); Q.tu+; p-i=i; p-j=pn-j; p-e=p

27、m-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=colp-j=p; else colp-j-down=p;/完成列插入 colp-j=colp-j-down; while(pm)/將矩陣M該行的剩余元素插入矩陣Q p=(OLink

28、)malloc(sizeof(OLNode); if(!p) e*it(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 colp-j-down=p; colp-j=colp-j-down; while(pn)/將矩陣N該行的剩余元素插入矩陣Q p=(OLink)malloc(sizeo

29、f(OLNode); if(!p) e*it(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-j-down; for(k=0;k!=Q.nu;k+) if(colk) colk-down=NULL; free(col); retur

30、n OK;CrossList Negative(CrossList M) OLink p; for(int j=0;j!=M.mu;j+) p=M.rheadj; while(p) p-e=-p-e;/將非零元的值反號 p=p-right; return (M); int Mult(CrossList M,CrossList N,CrossList &Q) int i,j,e; OLink q,p0,q0,q1,q2; if(M.nu!=N.mu) printf(你輸入的兩個距陣不能進(jìn)展此操作n); e*it(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) e*it(OVERFLOW); Q.chead=(OLink*)malloc(Q.nu+1)*sizeof(OLink); if(!Q.chead) e*it(OVERFLOW); for(i=0;i!=Q.mu;i+)/初始化行 Q.rheadi=NULL; for(i