實驗報告----數(shù)據(jù)結構課程設計稀疏矩陣的應用

1、精選優(yōu)質(zhì)文檔-傾情為你奉上數(shù)學與計算機學院課程設計說明書課 程 名 稱: 數(shù) 據(jù) 結 構 課 程 設 計 課 程 代 碼: 題 目: 稀疏矩陣的應用 年級/專業(yè)/班: 2010級 軟件工程 2班 學 生 姓 名: 尹 龍 海 學 號: 1228 開 始 時 間: 2011 年 12 月 08 日完 成 時 間: 2011 年 12 月 16 日課程設計成績：學習態(tài)度及平時成績（30）技術水平與實際能力（20）創(chuàng)新（5） 說明書（計算書、圖紙、分析報告）撰寫質(zhì)量（45）總 分（100）指導教師簽名： 年 月 日數(shù)據(jù)結構課 程 設 計 任 務 書學院名稱： 數(shù)學與計算機學院 課程代碼：_ _專 業(yè)

2、： 軟件工程（Web方向） 年 級： 2010級2班 一、設計題目稀疏矩陣應用二、 主要內(nèi)容主要完成稀疏矩陣的加、轉(zhuǎn)、乘的實現(xiàn)。三、具體要求及應提交的材料以三元組、十字鏈表為存儲形式，分別實現(xiàn)兩個稀疏矩陣的加法運算、兩個稀疏矩陣的乘法運算，以及對任意稀疏矩陣的轉(zhuǎn)置運算。稀疏矩陣要求可為鍵盤錄入的任意矩陣。用C/C+語言編程實現(xiàn)上述內(nèi)容，對每個問題寫出一個算法實現(xiàn)，并按數(shù)學與計算機學院對課程設計說明書規(guī)范化要求，寫出課程設計說明書，并提交下列材料：1)課程設計說明書打印稿一份2)課程設計說明書電子稿一份；3)源程序電子文檔一份。四、主要技術路線提示注意合理地設計三元組及十字鏈表，結合稀疏矩陣的壓

3、縮存儲方式和特點，將每一功能模塊以函數(shù)形式分別實現(xiàn)。在此基礎上用C/C+實現(xiàn)其操作。五、進度安排按教學計劃規(guī)定，數(shù)據(jù)結構課程設計為2周，其進度及時間大致分配如下：序號設計內(nèi)容天數(shù)1分析問題，給出數(shù)學模型，選擇數(shù)據(jù)結構22設計算法，給出算法描述13給出源程序清單24編輯、編譯、調(diào)試源程序25編寫課程設計報告3總 計10六、推薦參考資料1 嚴蔚敏，吳偉民.數(shù)據(jù)結構.清華大學出版社出版。 2 嚴蔚敏，吳偉民. 數(shù)據(jù)結構題集(C語言版) .清華大學出版社.2003年5月。3 唐策善，李龍澎.數(shù)據(jù)結構(作C語言描述) .高等教育出版社.2001年9月4 朱戰(zhàn)立.數(shù)據(jù)結構(C+語言描述)（第二版本）.高等

4、出版社出版.2004年4月5 胡學鋼.數(shù)據(jù)結構(C語言版) .高等教育出版社.2004年8月6 徐孝凱 等著.數(shù)據(jù)結構（C語言描述）.清華大學出版社.2004指導教師 簽名日期 年 月 日系 主 任 審核日期 年 月 日目 錄 摘要5引言51 需求分析62 概要設計63詳細設計84調(diào)試分析155用戶使用說明156測試結果157結論19致謝20參考文獻21摘 要 本課程設計主要實現(xiàn)在三元組存儲結構與十字鏈表存儲結構下輸入稀疏矩陣，并對稀疏矩陣進行轉(zhuǎn)置，相加，相乘等操作，最后輸出運算后的結果?？紤]到難易程度，先用三元組實現(xiàn)稀疏矩陣的輸入，輸出，及其轉(zhuǎn)置，相加，相乘等操作的方法，再在十字鏈表下實現(xiàn)。

5、程序通過調(diào)試運行，結果與預期一樣，初步實現(xiàn)了設計目標。關鍵詞：程序設計；稀疏矩陣；三元組；十字鏈表引 言 1.1 課程設計任務本課程設計主要實現(xiàn)在三元組存儲結構與十字鏈表存儲結構下輸入稀疏矩陣，并對稀疏矩陣進行轉(zhuǎn)置，相加，相乘操作，最后輸出運算后的結果。稀疏矩陣采用三元組和十字鏈表表示，并在兩種不同的存儲結構下，求兩個稀疏矩陣A和B的和為矩陣C，并輸出C； 求出A的轉(zhuǎn)置為矩陣D，輸出D； 求兩個稀疏矩陣A和B的相乘為矩陣E，并輸出E。1.2 課程設計性質(zhì)數(shù)據(jù)結構課程設計是重要地實踐性教學環(huán)節(jié)。在進行了程序設計語言課和數(shù)據(jù)結構課程教學的基礎上，設計實現(xiàn)相關的數(shù)據(jù)結構經(jīng)典問題，有助于加深對數(shù)據(jù)結構

6、課程的認識。本課程設計是數(shù)據(jù)結構中的一個關于稀疏矩陣的算法的實現(xiàn)，包括在三元組和十字鏈表下存儲稀疏矩陣，并對輸入的稀疏矩陣進行轉(zhuǎn)置，相加，相乘等操作，最后把運算結果輸出。此課程設計要求對數(shù)組存儲結構和鏈表存儲結構非常熟悉，并能熟練使用它們。1.3課程設計目的其目的是讓我們在學習完C+、數(shù)據(jù)結構等課程基礎上，掌握多維數(shù)組的邏輯結構和存儲結構、掌握稀疏矩陣的壓縮存儲及轉(zhuǎn)置，相加，相乘等操作，并用不同的方法輸出結果，進一步掌握設計、實現(xiàn)較大系統(tǒng)的完整過程，包括系統(tǒng)分析、編碼設計、系統(tǒng)集成、以及調(diào)試分析，熟練掌握數(shù)據(jù)結構的選擇、設計、實現(xiàn)以及操作方法，為進一步的應用開發(fā)打好基礎。需求分析2.1設計函數(shù)

7、建立稀疏矩陣及初始化值和輸出稀疏矩陣的值本模塊要求設計函數(shù)建立稀疏矩陣并初始化，包括在三元組結構下和十字鏈表結構下。在創(chuàng)建稀疏矩陣時，需要設計兩個不同的函數(shù)分別在三元組和十字鏈表下創(chuàng)建稀疏矩陣，在輸入出現(xiàn)錯誤時，能夠?qū)﹀e誤進行判別處理，初始化稀疏矩陣都為空值。在設計輸出稀疏矩陣的值的函數(shù)時，也要針對兩種不同的情況，分別編制函數(shù)，才能準確的輸出稀疏矩陣。在對稀疏矩陣進行初始化時，只輸入非零元素的值和它所在的所在行及所在列。在對稀疏矩陣輸出時，以矩陣的完整形式輸出。2.2構造函數(shù)進行稀疏矩陣的轉(zhuǎn)置并輸出結果本模塊要求設計函數(shù)進行稀疏矩陣的轉(zhuǎn)置并輸出轉(zhuǎn)置后的結果。在編寫函數(shù)時，要先定義一個相應的結構

8、體變量用于存放轉(zhuǎn)置后的矩陣，最后把此矩陣輸出。2.3構造函數(shù)進行兩稀疏矩陣相加、減及相乘并輸出最終稀疏矩陣本模塊要求設計相加、減和相乘函數(shù)對兩個矩陣進行運算，并輸出最終的稀疏矩陣，定義相應的矩陣類型用于存放兩個矩陣操作后的結果矩陣，這個結果矩陣的行、列數(shù)需要綜合多方面情況來確定。這些函數(shù)也是整個程序的難點，需要靈活運用數(shù)組及指針的特點。2.4退出系統(tǒng)本模塊要求設置選項能隨時結束程序的運行，本程序中采用do-while循環(huán)。程序在計算機上顯示“提示信息”之后，由用戶在鍵盤上輸入演示程序中需要的相關信息及命令。概要設計3.1存儲結構設計三元組結構體定義: struct matint i;/非零元素

9、的行位置int j;/非零元素的列位置int v;/非零元素的值;class sqmatrixprivate:int m;/矩陣的行數(shù)int n;/矩陣的列數(shù)int t;/矩陣中非零元素的個數(shù)mat datamax;/三元組表int rposmax;/存儲矩陣中第max行以前所有非零元素的個數(shù)public:;十字鏈表結構體定義: typedef struct OLNode int i,j; /該非零元的行、列下標 int e; /非零元值 struct OLNode *right,*down; / 該非零元所在行表和列表的 后繼元素 OLNode,*OLink;/ 定義十字鏈表對象結構體typ

10、edef struct OLink *rhead,*chead; /OLink類型 結點數(shù)組 int a,b,c; / 系數(shù)矩陣的行數(shù)，列數(shù)，和非零元素個數(shù) CrossList;3.2系統(tǒng)功能設計本系統(tǒng)除了要完成分別在三元組存儲結構以及在十字鏈表下實現(xiàn)稀疏矩陣的初始化功能外還設置了4個子功能菜單。稀疏矩陣的建立及初始化在三元組存儲結構下，由函數(shù) void creat()實現(xiàn)，在十字鏈表存儲結構下，由函數(shù)void CreateSMatix_OL(CrossList &M)依據(jù)讀入的行數(shù)和列數(shù)以及非零元素的個數(shù)，分別設定每個非零元素的信息。4個子功能的設計描述如下。（1）稀疏矩陣的轉(zhuǎn)置：此

11、功能在三元組存儲結構下，有兩種方法：按行轉(zhuǎn)置和按列轉(zhuǎn)置，分別由函數(shù)sqmatrix transmatone()和sqmatrix transmattwo()實現(xiàn)，在十字鏈表存儲結構下，由函數(shù)void zhuanzhi( )實現(xiàn)。當用戶選擇該功能，系統(tǒng)提示用戶初始化一個矩陣，然后進行轉(zhuǎn)置，最終輸出結果。（2）稀疏矩陣的加法：此功能在三元組存儲結構下，由函數(shù)void add(sqmatrix a,sqmatrix b)實現(xiàn)，在十字鏈表存儲結構下，由函數(shù)void add()實現(xiàn)。當用戶選擇該功能，系統(tǒng)即提示用戶初始化要進行加法的兩個矩陣的信息。然后進行加法，最后輸出結果。（3）稀疏矩陣的乘法：此功能

12、在三元組存儲結構下，由函數(shù)void cheng(sqmatrix a,sqmatrix b)實現(xiàn)。在十字鏈表存儲結構下，由函數(shù)void chengfa()實現(xiàn)。當用戶選擇該功能，系統(tǒng)提示輸入要進行相乘的兩個矩陣的詳細信息。然后進行相乘，最后得到結果。（4）退出：即退出稀疏矩陣的應用系統(tǒng)，由switch語句實現(xiàn)。當用戶選擇相應序號，則退出該稀疏矩陣的應用系統(tǒng)。詳細設計4.1 數(shù)據(jù)類型定義三元組結構體定義:struct matint i;/非零元素的行位置int j;/非零元素的列位置int v;/非零元素的值; class sqmatrixprivate:int m;/矩陣的行數(shù)int n;/矩

13、陣的列數(shù)int t;/矩陣中非零元素的個數(shù)mat datamax;/三元組表int rposmax;/存儲矩陣中第max行以前所有非零元素的個數(shù)public: ; 十字鏈表結構體定義: typedef struct OLNode int i,j; /該非零元的行、列下標 int e; /非零元值 struct OLNode *right,*down; OLNode,*OLink; typedef struct OLink *rhead,*chead; /OLink類型 結點數(shù)組 int a,b,c; / 系數(shù)矩陣的行數(shù)，列數(shù)，和非零元素個數(shù) CrossList; 4.2系統(tǒng)主要子程序詳細設計A

14、. 主程序模塊設計： 采用一個do-while語句執(zhí)行各個功能的操作循環(huán)，并用switch語句控制選擇三元組或十字鏈表進行相關的操作，在采用的操作界面中，再用switch語句控制各功能的實現(xiàn)，主要代碼如下：docout<<endl;cout<<"n *稀疏矩陣應用*"<<endl<<endl;cout<<"n 請你選擇創(chuàng)建稀疏矩陣的方法 "<<endl;cout<<"n 1、用三元組創(chuàng)建稀疏矩陣"<<endl;cout<<&qu

15、ot;n 2、用十字鏈表創(chuàng)建稀疏矩陣"<<endl;cout<<"n 3、退出程序"<<endl<<endl;cout<<"請選擇："cin>>k; cout<<endl;switch(k)case 1: cout<<" 歡迎進入三元組操作矩陣系統(tǒng)"<<endl<<endl;switch(kk)case 1: 兩矩陣求和break;case 2: 兩矩陣相乘break;case 3: 矩陣按行轉(zhuǎn)置break

16、;case 4: 矩陣按行轉(zhuǎn)置break;case 5: 退出該程序break;cout<<endl; break;case 2: cout<<" 歡迎進入十字鏈表操作矩陣系統(tǒng)"<<endl<<endl;switch(kk) case 1: 兩矩陣求和break;case 2: 兩矩陣相乘break;case 3: 兩矩陣相減break;case 4: 矩陣轉(zhuǎn)置break;case 5: 退出該程序break;cout<<endl; break; while(k=1|k=2); cout<<endl;

17、return 0; B. 稀疏矩陣操作各子函數(shù)的定義：(1)建立與初始化稀疏矩陣： 采用三元組建立稀疏矩陣，輸入非零元素的行號、列號和值，關鍵代碼如下：cout<<"行號i 列號j 非零元素值v"<<endl;for(int p=0;p<t;p+) cout<<" "cin>>ii;datap.i=ii;cout<<" "cin>>jj;datap.j=jj;cout<<" "cin>>element;datap.

18、v=element; cout<<endl; 采用十字鏈表建立稀疏矩陣，輸入非零元素的行號、列號和值，給新結點申請空間，按列循環(huán)鏈表和行循環(huán)鏈表形式插入到十字鏈表中關鍵代碼如下：int x,y,m; cout<<"請輸入稀疏矩陣的行，列，及非零元素個數(shù)"<<endl; cin>>M.a>>M.b>>M.c; cout<<"請按三元組的格式輸入數(shù)組："<<endl; for(int i=1;i<=M.c;i+) cin>>x>>y&

19、gt;>m; cout<<endl; OLink p,q; p->i=x; p->j=y; p->e=m;if(M.rheadx=NULL|M.rheadx->j>y) p->right=M.rheadx; M.rheadx=p; else for(q=M.rheadx;(q->right)&&(q->right->j<y);q=q->right); p->right=q->right; q->right=p; if(M.cheady=NULL|M.cheady->i&g

20、t;x) p->down=M.cheady; M.cheady=p; elsefor(q=M.cheady;(q->down)&&(q->down->i<x);q=q->down); p->down=q->down; q->down=p; （2）輸出稀疏矩陣：用三元組輸出矩陣元素時，若稀疏矩陣所對應的元素在三元組中有該元素，則輸出三元組中的這個元素的值，否則，輸出零。其關鍵代碼如下：if(datap.i=i&&datap.j=j) isfound=true;foundindex=p; if(isfound=t

21、rue) cout<<setw(5)<<datafoundindex.v;elsecout<<setw(5)<<"0"用十字鏈表輸出矩陣元素時，若稀疏矩陣所對應的元素在十字鏈表中有該元素，則輸出三元組中的這個元素的值，同時指針指向下一個結點，否則，輸出零。其關鍵代碼如下： if(p)&&(j=p->j) cout<<p->e<<" " p=p->right; else cout<<"0"<<" &

22、quot; cout<<endl<<endl; （3）實現(xiàn)矩陣的轉(zhuǎn)置：用三元組和十字鏈表實現(xiàn)矩陣轉(zhuǎn)置，都采用元素所對應的行號變?yōu)樾戮仃嚨牧刑?，所對應的列號變?yōu)樾戮仃嚨男刑?，所對應的值不變，在這個過程中采用一個for循環(huán)使待轉(zhuǎn)置的元素所對應的列號較小者先轉(zhuǎn)置到新矩陣中，其關鍵代碼如下：b.m=n;b.n=m;b.t=t; if(t!=0) int q=0; for(int col=1;col<=n;col+)for(int p=0;p<t;p+)if(datap.j=col) b.dataq.j=datap.i;b.dataq.i=datap.j; b.dat

23、aq.v=datap.v;q+;cout<<endl<<endl; return b; （4）實現(xiàn)兩個矩陣的相加：采用三元組實現(xiàn)兩矩陣相加時，先判斷被加的兩矩陣所對應的位置是否有非零元素，若沒有或兩矩陣元素相加為零，則新三元組表中不進行任何操作，若只有一個為非零元素，則新三元組表中對應位置元素值就為該非零元素的值，若兩矩陣相同位置元素和k不為零，則新三元組表中對應應位置元素值就為k。其關鍵代碼如下：while(pa<=a.t&&pb<b.t) ka=(a.datapa.i-1)*n+a.datapa.j;kb=(b.datapb.i-1)*n

24、+b.datapb.j; if(ka<kb)pc+;datapc=a.datapa;pa+;else if(ka>kb)pc+;datapc=b.datapb;pb+;elses=a.datapa.v+b.datapb.v; if(s=0)pa+;pb+;elsepc+;datapc=a.datapa; datapc.v=s; pa+;pb+;while(pa<a.t)pc+;datapc=a.datapa;pa+;while(pb<b.t)pc+;datapc=b.datapb;pb+;t=pc+1; 采用十字鏈表實現(xiàn)兩矩陣相加時，和三元組實現(xiàn)兩矩陣相加類似，不同點就

25、是元素相加后轉(zhuǎn)向被加的兩個元素結點向下移動，新三元組的指針也向下移動其關鍵代碼如下： OLink pa,pb,pre ,hlMAXROW+1; for(int x=1;x<=M.b;x+) hlx=M.cheadx; for(int k=1;k<=M.a;k+) pa=M.rheadk; pb=N.rheadk; pre=NULL; while(pb) OLink p; p->e=pb->e; p->i=pb->i; p->j=pb->j; if(NULL=pa|pa->j>pb->j) if(NULL=pre) M.rhead

26、p->i=p; else pre->right=p; p->right=pa; pre=p; if(NULL=M.cheadp->j) M.cheadp->j=p; p->down=NULL; else p->down=hlp->j->down; hlp->j->down=p; hlp->j=p; pb=pb->right; else if(NULL!=pa)&&pa->j<pb->j) pre=pa; pa=pa->right; else if(pa->j=pb->

27、;j) pa->e += pb->e; if(!pa->e) if(NULL=pre) M.rheadpa->i=pa->right; else pre->right=pa->right; p=pa; pa=pa->right; if(M.cheadp->j=p) M.cheadp->j=hlp->j=p->down; else hlp->j->down=p->down; free(p); pb=pb->right; else pa=pa->right; pb=pb->right; sh

28、uchu(M); （5）實現(xiàn)兩個矩陣的相乘：三元組實現(xiàn)兩矩陣相乘和三元組實現(xiàn)兩矩陣相加類似，不同就是新矩陣非零元素所在行和列的值是兩矩陣所對應行元素與所對應列元素相乘后相加，其主要代碼如下： int ctempmax; t=0; m=a.m; n=a.n;if(a.t*b.t!=0) for(arow=1; arow<=a.m; arow+)for(ii=1; ii<=a.n; ii+) ctempii=0; rposarow=t;Mlim=arow<a.m?a.rposarow+1 : a.t+1; for( Mcol=a.rposarow; Mcol<Mlim; M

29、col+ ) Mj=a.dataMcol.j; Nlim = Mj<b.m ? b.rposMj+1 : b.t+1; for(Nrow=b.rposMj;Nrow<Nlim;Nrow+) ctempb.dataNrow.j += a.dataMcol.v * b.dataNrow.v; 十字鏈表實現(xiàn)矩陣相乘和十字鏈表實現(xiàn)矩陣相加類似，都要判斷相乘后是否為零，在操作時要注意指針的指向。其關鍵代碼如下：for(int x=1;x<=M.b;x+)hlx=M.cheadx; for(int k=1;k<=M.a;k+) pa=M.rheadk; pb=N.rheadk; p

30、re=NULL; while(pb) OLink p; p->e=pb->e; p->i=pb->i; p->j=pb->j; if(NULL=pa|pa->j>pb->j) if(NULL=pre) M.rheadp->i=p; else pre->right=p; p->right=pa; pre=p; if(NULL=M.cheadp->j) M.cheadp->j=p; p->down=NULL; else p->down=hlp->j->down; hlp->j->

31、down=p; hlp->j=p; pb=pb->right; else if(NULL!=pa)&&pa->j<pb->j) pre=pa; pa=pa->right; else if(pa->j=pb->j) pa->e *= pb->e; if(!pa->e) if(NULL=pre) M.rheadpa->i=pa->right; else pre->right=pa->right; p=pa; pa=pa->right; if(M.cheadp->j=p) M.che

32、adp->j=hlp->j=p->down; else hlp->j->down=p->down; free(p); pb=pb->right; else pa=pa->right; pb=pb->right; 調(diào)試分析 用C+語言寫代碼實現(xiàn)所要求的功能過程中，用三元組實現(xiàn)矩陣相乘，有一定的難度，我通過多次調(diào)試，系統(tǒng)始終提示出錯，通過參考網(wǎng)友的代碼和同學的提示，原來兩矩陣的第i行非零元素個數(shù)不一定等于另一矩陣的第i列非零元素個數(shù)，最后，我通過控制一矩陣的非零元素所在的i行、j列位置與另一個矩陣所對應的i列j行元素相乘，然后在相加。通過測試，

33、功能能夠?qū)崿F(xiàn)了；在用十字鏈表實現(xiàn)各功能時，由于指針很多，寫出的代碼最初基本上都是指針指向出錯，通過自己經(jīng)驗以及老師的指導、朋友的幫助，最后解決了各個問題。用戶使用說明該系統(tǒng)具有簡單、明了、使用等特點，能夠方便、準確的計算出矩陣的部分操作，適用于學校老師、同學對矩陣方面的研究。當使用該系統(tǒng)時，系統(tǒng)會給出相關的提示信息，用戶只需根據(jù)提示信息，即可完成系統(tǒng)提供的所有功能。測試結果7.1系統(tǒng)運行主界面系統(tǒng)運行主界面如圖7.1所示：圖7.1 主界面圖7.2 各子功能測試運行結果（1）稀疏矩陣的相加：在主菜單下，用戶輸入1回車，是用三元組對矩陣的操作，用戶再按1回車，根據(jù)屏幕提示操作，運行結果如圖7.2所示。 圖7.2 三元組創(chuàng)建并初始化矩陣在主菜單下，用戶輸入2回車，是用十字鏈表對矩陣的操作，根據(jù)屏幕提示操作，運行結果如圖7.3所示。圖7.3 十字鏈表創(chuàng)建并初始化矩陣（2）稀疏矩陣的轉(zhuǎn)置：用三元組創(chuàng)建稀疏矩陣后，用戶在三元組操作下輸入3或4回車，便顯示該矩陣的轉(zhuǎn)置矩陣，運行結果如圖7.4所示。 圖7.4 三元組稀疏矩陣轉(zhuǎn)置結果示意圖用十字鏈表創(chuàng)建稀疏矩陣后，用戶在十字鏈表操作下輸入4回車，便顯示該矩陣的轉(zhuǎn)置矩陣，運行結果如圖7.5所示。 圖7.5 十字鏈表稀疏矩陣轉(zhuǎn)置結果示意圖（3）稀疏矩陣的相乘：在三元組或十字鏈表操作下輸入2回車，按屏幕提示操作，運行結果如圖7.6所示。圖7.6 三