數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-基于十字鏈表的矩陣運(yùn)算

1、數(shù) 據(jù) 結(jié) 構(gòu)課 程 設(shè) 計(jì) 報(bào) 告日期: 年 月 日12200930 學(xué) 號(hào)班 級(jí)姓 名指 導(dǎo) 教 師2007級(jí)信息與計(jì)算科學(xué)題目：基于正交鏈表的矩陣運(yùn)算說 明本組成員名單：組長：本人承擔(dān)的課程設(shè)計(jì)的工作情況：程序的算法設(shè)計(jì)以及部分功能實(shí)現(xiàn)，后期程序調(diào)試、測試，主函數(shù)的設(shè)計(jì)。 目 錄1 任務(wù)概述31.1 問題描述31.2 編程的基本要求31.3 程序的主要功能31.4 編程語言及選擇的操作平臺(tái)32 概要設(shè)計(jì)42.1 數(shù)據(jù)結(jié)構(gòu)42.2 總體結(jié)構(gòu)43 詳細(xì)設(shè)計(jì)53.1 數(shù)據(jù)結(jié)構(gòu)中的函數(shù)63.2 主函數(shù)及其他函數(shù)74 調(diào)試分析94.1調(diào)試過程 94.2測試結(jié)果 94.2改進(jìn)設(shè)想 145 用戶手冊1

2、56 總結(jié)17參考文獻(xiàn)18附件 源程序代碼清單1921 任務(wù)概述1.1 問題描述應(yīng)用三元組和正交鏈表存儲(chǔ)稀疏矩陣，并實(shí)現(xiàn)稀疏矩陣的轉(zhuǎn)置、加法和乘法運(yùn)算。1.2 編程的基本要求1）應(yīng)用三元組和正交鏈表的數(shù)據(jù)結(jié)構(gòu)。2）矩陣運(yùn)算由正交鏈表類的成員函數(shù)實(shí)現(xiàn)，矩陣的輸入輸出由類的友元重載函數(shù)實(shí)現(xiàn)。3）主函數(shù)用于實(shí)現(xiàn)菜單和調(diào)用。1.3 程序的主要功能1. 按數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告格式所給出的框架撰寫。2. 具體內(nèi)容應(yīng)盡量包含文字?jǐn)⑹?、圖表（表格，框圖，流程圖，uml圖等）和程序代碼。3. 每個(gè)同學(xué)要提交電子文檔和一份打印稿。1.4 編程語言及選擇的操作平臺(tái)編程語言選用c+程序設(shè)計(jì)語言。程序開發(fā)平臺(tái)選用mcr

3、osoft visual studio 6.0的microsoft visual c+ 6.0開發(fā)環(huán)境。程序運(yùn)行在dos界面。2 概要設(shè)計(jì)2.1 數(shù)據(jù)結(jié)構(gòu)稀疏矩陣類（matrix）matrix- row : int- col : int- terms : int- termrp : int- headmode : node* - operator ( : istream, : matrix&) : istream - operator ( :ostream, :matrix) : ostream+ matrix(m ：int , n : int)+ matrix()+ matrix（t : m

4、atrix&）+ matrix()+ make empty() : void+ insert(m : int, n :int, p : float) : void+ pelete(m : int, n ：int) : void+ locate(i : int) : node+ transport() : matrix+ add(b :matrix) : matrix+ mul(b :matrix) : matrix+ operator = (t : matrix&) : matrix+ init (m :int,n :int :void)稀疏矩陣的節(jié)點(diǎn)類（node）node + matrix:

5、 class+ node()+ node( t : elemene*)+ down : node*+ right : node*+ head : boolean+ union2.2總體結(jié)構(gòu)說明：表達(dá)式i!=0 true,向下執(zhí)行，false 結(jié)束退出表達(dá)式i!=0輸入所要執(zhí)行的運(yùn)算（i）switch(i)結(jié)束dafaultcase 2case 1case 0開始case 33 詳細(xì)設(shè)計(jì)3.1 數(shù)據(jù)結(jié)構(gòu)中的函數(shù)（其中函數(shù)的實(shí)現(xiàn)請(qǐng)參看源代碼部分）1) 矩陣結(jié)點(diǎn)（matrix）中的函數(shù)：private:friend istream&operator(istream&,matrix&);friend

6、ostream&operatorcol; triple.row=t-row; triple.item=t-item; right=down=this; head=false;3.2 主函數(shù)及其他函數(shù)#includematrix.h#include void main() int i; matrix b,b1,b2,c; while(i!=0) cout -基于正交鏈表的稀疏矩陣的運(yùn)算-endlendl; cout 1.轉(zhuǎn)置 2.加法 3.乘法 0.退出程序 endlendl; couti; coutendl; switch(i) case 0: break; case 1: cout -稀疏矩

7、陣的轉(zhuǎn)置-nendl; cout請(qǐng)輸入矩陣：endlb;system(cls);cout原矩陣為：endl;coutbendl;cout轉(zhuǎn)置后為endl;coutb.transpose()endl;break; case 2: cout -稀疏矩陣的加法-nendl; cout請(qǐng)輸入矩陣1：endlb1; cout請(qǐng)輸入矩陣2：endlb2;system(cls);cout矩陣1為：endl; coutb1endl; cout矩陣2為：endl;coutb2endl;cout兩個(gè)矩陣之和為：endl;coutb1.add(b2)endl;break; case 3: cout -稀疏矩陣的乘法

8、-nendl;cout注意：輸入的矩陣必須滿足矩陣相乘的條件，并且按順序輸入(即1和2的順序)nendl; cout請(qǐng)輸入矩陣1：b1; cout請(qǐng)輸入矩陣2：b2; system(cls);cout矩陣1為:endl;coutb1endl;cout矩陣2為:endl;coutb2endl;cout兩個(gè)矩陣之積為：endl;coutb1.mul(b2)endl; break; default: break; if(i!=0) cout按任意繼續(xù).right!=t.locate(i) 開始時(shí)是while(current-right!=current)再者算法中有些小漏洞沒有考慮到，用斷點(diǎn)分析法，

9、找出漏洞，完善程序。感觸最深的是：斷點(diǎn)查錯(cuò)這功能太好！又快又貼近實(shí)際應(yīng)用！4.2 測試結(jié)果一、轉(zhuǎn)置的測試：二、加法的測試：（可以加）（不可以加）三、乘法的測試：（可以乘）（不可以乘）按0退出程序：4.3 改進(jìn)設(shè)想1）由于時(shí)間倉促，沒有將其調(diào)試成功后將類做成模版，導(dǎo)致只能輸入floate型數(shù)據(jù)， 改進(jìn)方案：將所有的類做成模版，將其屬下的floate類型的全改為 模版類型參數(shù)。2） 此程序顯的很繁瑣，但代碼數(shù)量來看，還沒有以三元組為存儲(chǔ)結(jié)構(gòu)的實(shí)現(xiàn)代碼簡單，可能是我們的算法不好！改進(jìn)方法：重新考慮算法，看是否可用數(shù)組加指針的方式實(shí)現(xiàn)，用數(shù)組可以簡化找頭指針的繁瑣過程，簡化循環(huán)的過程提高程序運(yùn)行效率！

10、但現(xiàn)在還不是很清楚！3）程序的效率為o（n*m）(n、m分別為行數(shù)與列數(shù)) 5 用戶手冊一、開啟程序，進(jìn)入程序的dos運(yùn)行界面。二、（說明：矩陣的值暫時(shí)只能輸入float型）n 1）出現(xiàn)此界面時(shí)按提示選擇所要選擇的運(yùn)算功能。例如選擇1：顯示如下 輸入所要轉(zhuǎn)置矩陣的行、列與非零元素個(gè)數(shù)，按enter確定，按提示依次輸入各非零元素的行、列及其數(shù)值，全部輸入完成后按enter確定，即可得到轉(zhuǎn)置后的矩陣。當(dāng)選擇2或3時(shí)：例如選擇2：按提示輸入所要執(zhí)行相加運(yùn)算的第一個(gè)矩陣的 輸入完成后繼續(xù)輸入第二個(gè)矩陣的行、列與非零元素值。輸完后按enter鍵確定顯示計(jì)算結(jié)果。 乘法的操作步驟與加法相似，可參考加法的執(zhí)

11、行。2）當(dāng)一次執(zhí)行結(jié)束后可按任意鍵返回到1）的界面，此時(shí)您可以重新選擇所要執(zhí)行的運(yùn)算。 4 調(diào)試分析6 總結(jié)總結(jié)1）此次課程設(shè)計(jì)過程中，真正的體驗(yàn)到，拿到一個(gè)問題，應(yīng)該先分析，將其的屬性，功能分析清楚后，再進(jìn)行細(xì)化，考慮其實(shí)現(xiàn)的具體的、有效的算法，有了整體的結(jié)構(gòu)框架后再上機(jī)！以前只要拿到題就直接打開電腦，想到什么就寫什么，沒整體思考，對(duì)小程序可以，大程序就會(huì)徹底崩潰。2）編程實(shí)質(zhì)就是問題的分析及其實(shí)現(xiàn)的算法，這兩方面解決了上機(jī)編程才會(huì)得心應(yīng)手，剩下的就是按算法些代碼了！3）確定一個(gè)好算法很難，一個(gè)人往往陷入死循環(huán)，思路受局限，找人討論很必要，編程時(shí)團(tuán)隊(duì)意識(shí)很重要，這不是一個(gè)人就能搞定的。沒人指

12、點(diǎn)迷津很難！4）設(shè)計(jì)過程中對(duì)所學(xué)到的知識(shí)感觸很深，書上的東西確是鉆之彌深。平時(shí)了解、理解的只是很淺的一部分。斷點(diǎn)查錯(cuò)很實(shí)用！調(diào)試程序比寫程序好受多！參考文獻(xiàn)1 殷人昆主編.數(shù)據(jù)結(jié)構(gòu)（第2版）北京：清華大學(xué)出版社，2007.2 田魯懷主編 數(shù)據(jù)結(jié)構(gòu)（c語言版） 電子工業(yè)出版社 2008年7月附件 源程序代碼清單#ifndef matrix_h#define matrix_h#include#includeenum booleanfalse,true;struct element int row,col;float item;class matrix;class node / 矩陣節(jié)點(diǎn)類的定義fr

13、iend class matrix;public:node():head(true) right=down=this; /建立附加頭結(jié)點(diǎn)node(element *t)/ 建立非零元素結(jié)點(diǎn)triple.col=t-col;triple.row=t-row;triple.item=t-item;right=down=this;head=false;node*down,*right;/行列鏈表指針boolean head;union element triple;node*next; /無名聯(lián)合;class matrix/稀疏矩陣的類定義friend istream&operator(istrea

14、m&,matrix&);friend ostream&operator=n?m:n;node *current;headnode=new node(&x);current=headnode-right=new node();for(int i=1;inext=new node();current=current-next;matrix:matrix():row(0),col(0),terms(0) /構(gòu)造函數(shù)的實(shí)現(xiàn)element x;x.row=row;x.col=col;x.item=0;matrix:matrix(matrix&t) /復(fù)制構(gòu)造函數(shù)的實(shí)現(xiàn)init(t.row,t.col);

15、node*current;for(int i=1;iright!=t.locate(i) /通過行遍歷逐個(gè)賦值current=current-right; insert(current-triple.row,current-triple.col,current-triple.item);void matrix:init(int m,int n) /矩陣初始化函數(shù)的實(shí)現(xiàn)row=m;col=n;terms=0;element x;x.row=m;x.col=n;x.item=0;headnode=new node(&x);node* current;if(m0&n0)temp=m=n?m:n;cu

16、rrent=new node();headnode-right=current;for(int i=1;inext=new node(); current=current-next;elsecout矩陣初始化錯(cuò)誤！right;for(int k=1;knext;return current;void matrix:insert(int m,int n,float p)/插入函數(shù)的實(shí)現(xiàn)element x;x.row=m;x.col=n;x.item=p;if(mrow&ncol)node *newnode=new node(&x),*current,*head;head=locate(m);/先

17、定位行的位置再尋找列插入current=head-right;if(current=head)current-right=newnode;newnode-right=current;elsewhile(current-triple.colright!=head)current=current-right;newnode-right=current-right;current-right=newnode; /完成插入head=locate(n); /先定位列再尋找行插入current=head-down;if(current=head)current-down=newnode;newnode-d

18、own=current;elsewhile(current-triple.rowdown!=head)current=current-down;newnode-down=current-down;current-down=newnode;terms+; /完成插入elsecout輸入的結(jié)點(diǎn)位置超出了范圍，請(qǐng)重新輸入！endl;void matrix:delete(int m,int n) /刪除特定結(jié)點(diǎn)元素實(shí)現(xiàn)if(m=row&nright;while(del-triple.col!=n)current=current-right;del=del-right;current-right=del

19、-right;delete del;elsecout找不到結(jié)點(diǎn)無法刪除!(istream &ist,matrix &b) /輸入函數(shù)重載的實(shí)現(xiàn)int m,n,m,n,t;float p;cout請(qǐng)輸入矩陣的行列和非零元素個(gè)數(shù)：mnt;b.init(m,n);if(t(m*n)cerr輸入的元素個(gè)數(shù)超過范圍endl;exit(1);elsecout請(qǐng)輸入各非零元素的行數(shù)列數(shù)和值endl;cout 行數(shù) 列數(shù) 值endl;for(int i=1;i=t;i+) /輸入元素結(jié)點(diǎn)并且插入矩陣cout【imnp;coutendl;b.insert(m,n,p); /插入結(jié)點(diǎn)return ist;ostr

20、eam &operator(ostream &ost,matrix &b) /輸出函數(shù)重載ost矩陣行數(shù)為：b.row ;ost列數(shù)為：b.col ;ost非零元素個(gè)數(shù)為b.termsendl;node *x;for(int i=1;i=b.temp;i+) /先確定各行頭結(jié)點(diǎn)的位置再遍歷各行，以輸出所有非零元素x=b.locate(i);for(int j=1;jright-head=true)break;elsex=x-right; ost第triple.row行第triple.col列元素是triple.itemrow=t.row;this-col=t.col;node *current

21、;for(int i=1;iright!=current)current=current-right; /通過行遍歷逐個(gè)賦值this-insert(current-triple.row,current-triple.col,current-triple.item);return *this;void matrix:makeempty() /清空矩陣的實(shí)現(xiàn)node*del,*current;for(int i=1;idown!=locate(i)del=current-down; /通過列的附加頭結(jié)點(diǎn)向下刪除結(jié)點(diǎn)current-down=del-down;delete del;matrix ma

22、trix:transpose() /矩陣轉(zhuǎn)置運(yùn)算的實(shí)現(xiàn)matrix b(this-col,this-row); /以原矩陣的行列和非零元素個(gè)數(shù)構(gòu)造一個(gè)新的矩陣node *current;for(int i=1;idown!=locate(i)current=current-down;b.insert(current-triple.col,current-triple.row,current-triple.item);return b;matrix matrix:add( matrix b) /矩陣加法的實(shí)現(xiàn)matrix c(b.row,b.col);if(this-row=b.row&this

23、-col=b.col)float j(0);node *p,*q;for(int i=1;iright!=locate(i)&q-right!=b.locate(i) /把加法分成三種情況即兩個(gè)矩陣該行都沒元素，有一個(gè)沒元素，和都有元素if(p-right-triple.colq-right-triple.col) /如果都有元素，就比較那個(gè)所在的列大些，先把列小些的插入（找不到與之匹配的元素了）q=q-right;c.insert(i,q-triple.col,q-triple.item);else if(p-right-triple.colright-triple.col)p=p-righ

24、t;c.insert(i,p-triple.col,p-triple.item);elsep=p-right;q=q-right;j=p-triple.item+q-triple.item;if(j!=0)c.insert(i,q-triple.col,j);if(p-right=locate(i) /把遍歷過程中漏掉的元素找齊while(q-right!=b.locate(i)q=q-right;c.insert(i,q-triple.col,q-triple.item);else if(q-right=b.locate(i)while(p-right!=locate(i)p=p-right

25、;c.insert(i,p-triple.col,p-triple.item);else /如果輸入有誤就給出提示cout行列不同,無法相加col=b.row)matrix c(this-row,b.col); /以a矩陣的行和b矩陣的列為行列建立稀疏矩陣float value;node *row_head,*col_head; /設(shè)兩個(gè)指針，一個(gè)充當(dāng)行頭指針，一個(gè)為列指針 for(int i=1;i=temp;i+) /先確定行，再求出c矩陣在該行各列的元素for(int j=1;jright!=locate(i) /假如行中還有元素不為零就找與之匹配的元素相乘row_head=row_he

26、ad-right;col_head=col_head-down;while(row_head-triple.col!=col_head-triple.row&col_head-down!=b.locate(j) /假如行列不相等而且對(duì)應(yīng)列還有元素，就繼續(xù)找匹配的元素否則判斷再循環(huán)if(row_head-triple.colcol_head-triple.row)col_head=col_head-down;else if(row_head-right=locate(i)col_head=col_head-down; /假如b矩陣該列元素比a矩陣該行元素多elserow_head=row_head-right; /則b中該列元素已經(jīng)無法找到能相乘元素則往下推直至跳出循環(huán)if(col_head-down!=b.locate(j)|col_head-triple.row=row_head-triple.col)value+=row_head-triple.item*col_head-triple.item;if(value!=0)c.insert(i,j,value);return c;elsematr