數(shù)據(jù)結(jié)構(gòu)稀疏矩陣運(yùn)算器課程設(shè)計(jì)

1、內(nèi)蒙古科技大學(xué)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)說明書題 目：稀疏矩陣運(yùn)算器設(shè)計(jì)學(xué)生姓名：學(xué) 號：專 業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)班 級：計(jì)09-1班指導(dǎo)教師：劉 月 峰 2011 年 6 月 24 日稀疏矩陣運(yùn)算器設(shè)計(jì)摘 要 摘要：設(shè)計(jì)一稀疏矩陣運(yùn)算器。實(shí)現(xiàn)轉(zhuǎn)置，相加，相乘的功能。用“帶行邏輯鏈接信息”的三元組順序表表示稀疏矩陣，實(shí)現(xiàn)兩個(gè)矩陣相轉(zhuǎn)置、相加和相乘的運(yùn)算，采用分級的設(shè)計(jì)方法，分別設(shè)計(jì)出轉(zhuǎn)置、加、乘運(yùn)算器的子程序，相加運(yùn)算時(shí)只要依次掃描兩矩陣的行號和列號，若相等則相加后存入結(jié)果矩陣，不等時(shí)則存入較小的。相減運(yùn)算與相加運(yùn)算相同，同樣比較兩矩陣的行號和列號，只是不等時(shí)，若第一個(gè)小，則存入第一個(gè)的元素，若第二個(gè)小

2、，則存入其相反數(shù)。相乘運(yùn)算要先判斷兩矩陣能否相乘。通過給頂?shù)男刑柡土刑栒页鲈仃噷?yīng)的元素值。當(dāng)在三元組表示中找到時(shí)返回其元素值，找不到時(shí)，說明該位置為0，因此返回0。然后利用該函數(shù)計(jì)算出C的行號i和列號j 處的元素值，若該值不為0，則存入矩陣，否則不存入。通過實(shí)驗(yàn)表明本程序能夠進(jìn)行稀疏矩陣的相加，相減，相乘運(yùn)算。具備矩陣的加、減、乘功能。關(guān)鍵詞：轉(zhuǎn)置運(yùn)算器；相加運(yùn)算器；相乘運(yùn)算器 目 錄稀疏矩陣運(yùn)算器設(shè)計(jì)I摘 要II第一章 需求分析1第二章 概要設(shè)計(jì)2第三章 設(shè)計(jì)步驟6 3.1 函數(shù)說明6 3.2 設(shè)計(jì)步驟7第四章 設(shè)計(jì)理論分析方法20 4.1 算法一：矩陣轉(zhuǎn)置20 4.2 算法二：矩陣加法

3、20 4.3 算法三：矩陣乘法21第五章 程序調(diào)試23第六章 心得體會25 參考文獻(xiàn)26 第一章 需求分析1 稀疏矩陣是指那些多數(shù)元素為零的矩陣。利用“稀疏”特點(diǎn)進(jìn)行存儲和計(jì)算可以大大節(jié)省存儲空間，提高計(jì)算效率。實(shí)現(xiàn)一個(gè)能進(jìn)行稀疏矩陣基本運(yùn)算的運(yùn)算器。2 以“帶行邏輯鏈接信息”的三元組順序表表示稀疏矩陣，實(shí)現(xiàn)矩陣轉(zhuǎn)置，求逆，實(shí)現(xiàn)兩個(gè)矩陣相加、相減和相乘的運(yùn)算。稀疏矩陣的輸入形式采用三元組表示，而運(yùn)算結(jié)果的矩陣則以通常的陣列形式列出。 3 演示程序以用戶和計(jì)算機(jī)的對話方式執(zhí)行，數(shù)組的建立方式為邊輸入邊建立。4 由題目要求可知：首先應(yīng)輸入矩陣的行數(shù)和列數(shù)，并判別給出的兩個(gè)矩陣的行、列數(shù)對于所要求作

4、的運(yùn)算是否相匹配。5 程序可以對三元組的輸入順序不加以限制；根據(jù)對矩陣的行列，三元組作直接插入排序，從而進(jìn)行運(yùn)算時(shí),不會產(chǎn)生錯(cuò)誤。6 在用三元組表示稀疏矩陣時(shí)，相加、乘積和相減所得結(jié)果矩陣應(yīng)該另生成；矩陣求逆時(shí)，為了算法方便，使用二維數(shù)組存放。7 程序在VC6.0環(huán)境下設(shè)計(jì)。程序執(zhí)行的命令為：1.稀疏矩陣轉(zhuǎn)置; 2.稀疏矩陣加法; ;3. 稀疏矩陣乘法; 4.退出的工作。第二章 概要設(shè)計(jì)1 抽象數(shù)據(jù)類型稀疏矩陣的定義如下：ADT SparseMatrix 數(shù)據(jù)對象：D=aij|i=1,2,m; j=1,2,n; aijElemSet, m和n分別為矩陣的行數(shù)和列數(shù) 數(shù)據(jù)關(guān)系：R=Row,Col

5、 Row=ai,j, ai,j+1| 1im, 1jn-1 Col = ai,j, ai+1,j| 1im-1, 1jn 基本操作：create(TSMatrix &TM)操作結(jié)果：創(chuàng)建稀疏矩陣矩陣TM LocateELem(TSMatrix M,int i,int j,int e)初始條件：稀疏矩陣M存在 操作結(jié)果：稀疏矩陣中是否存在非零元素Aij，若存在返回edisp(TSMatrix TM)初始條件：稀疏矩陣TM存在操作結(jié)果：通常形式輸出稀疏矩陣InsertSortMatrix(TSMatrix &TM) 初始條件：稀疏矩陣TM存在操作結(jié)果：根據(jù)對矩陣的行列，三元組TM作

6、直接插入排序TransposeSMatrix(TSMatrix M,TSMatrix &T)初始條件：稀疏矩陣M和T存在操作結(jié)果：求稀疏矩陣M轉(zhuǎn)置的稀疏矩陣TAddTSM(TSMatrix A,TSMatrix B,TSMatrix &C)初始條件：稀疏矩陣A，B和C存在 操作結(jié)果：稀疏矩陣的加法運(yùn)算:C=A+BSubTSM(TSMatrix A,TSMatrix B,TSMatrix &C)初始條件：稀疏矩陣A，B和C存在 操作結(jié)果：稀疏矩陣的減法運(yùn)算:C=A-BMultSMatrix(TSMatrix A,TSMatrix B,TSMatrix &C)初始條

7、件：稀疏矩陣A，B和C存在操作結(jié)果：稀疏矩陣的乘法運(yùn)算:C=A×B NiMatrix(TSMatrix &TM)初始條件：稀疏矩陣TM存在操作結(jié)果：稀疏矩陣求逆ADT SparseMatrix;2. 主程序：void main( )初始化；do 接受命令；選擇處理命令； while(命令！=“退出”)3. 本程序有四個(gè)模塊，調(diào)用關(guān)系如下：主程序模塊矩陣輸入模塊 矩陣運(yùn)算模塊矩陣輸出模塊 圖2.14 本程序的流程圖開始選擇要執(zhí)行的操作作選擇4，退出程序選擇2，進(jìn)行矩陣加法運(yùn)算選擇1，進(jìn)行矩陣轉(zhuǎn)置運(yùn)算選擇3，進(jìn)行矩陣乘法運(yùn)算 輸入n個(gè)矩陣A的行數(shù)、列數(shù)、非零元個(gè)數(shù)輸出結(jié)果結(jié)束 圖

8、2.2第3章 設(shè)計(jì)步驟3.1函數(shù)說明稀疏矩陣的三元組順序表存儲表示：typedef struct / 定義三元組的元素 int i,j; int v; Triple; class tripletable /設(shè)計(jì)類來描述稀疏矩陣及其操作public: aaa *pdata; triple datamaxsize; int rposmaxsize; tripletable();tripletable(); void convert() ;void add( ); void multi ( );private:int m ; int n ; int t ; int a ;主要函數(shù)： tripleta

9、ble(); tripletable(); void convert( ) ; void add( ); void multi ( ); void main( );3.2設(shè)計(jì)步驟：設(shè)計(jì)一個(gè)矩陣類實(shí)現(xiàn)矩陣的運(yùn)算：class tripletable(包含矩陣的各種運(yùn)算函數(shù))。輸入矩陣（以三元組形式輸入非零元） int k; tripletable A,B; cout<<"輸入稀疏矩陣A的行數(shù)，列數(shù)和非零元個(gè)數(shù)：" cin>>A.m>>A.n>>A.t; for(k=1;k<=A.t;k+) printf("輸入第%

10、d個(gè)非0元素的行數(shù)，列數(shù)和值:",k); cin>>A.datak.i>>A.datak.j>>A.datak.v; 輸出矩陣：int c100100=0; for(k=1;k<=B.t;k+) cB.datak.iB.datak.j=B.datak.v; cout<<"轉(zhuǎn)置（加法，乘法）結(jié)果為："<<endl; for(k=1;k<=B.n;k+) for(int l=1;l<=B.m;l+) cout<<ckl<<" " cout<&

11、lt;endl; 轉(zhuǎn)置矩陣：void tripletable:convert( ) /矩陣的轉(zhuǎn)置 int k; tripletable A,B; cout<<"輸入稀疏矩陣A的行數(shù)，列數(shù)和非零元個(gè)數(shù)：" cin>>A.m>>A.n>>A.t; for(k=1;k<=A.t;k+) printf("輸入第%d個(gè)非0元素的行數(shù)，列數(shù)和值:",k); cin>>A.datak.i>>A.datak.j>>A.datak.v; B.m=A.m;B.n=A.n;B.t=A.t

12、; if(B.t) int q=1,col; for(col=1;col<=A.n;+col) for(int p=1;p<=A.t;+p) if(A.datap.j=col) B.dataq.i=A.datap.j; B.dataq.j=A.datap.i; B.dataq.v=A.datap.v; +q; int shuru100100=0; for(k=1;k<=B.t;k+) shuruB.datak.jB.datak.i=B.datak.v; cout<<"輸入為："<<endl; for(k=1;k<=B.m;k+

13、) for(int l=1;l<=B.n;l+) cout<<shurukl<<" " cout<<endl; int result100100=0; for(k=1;k<=B.t;k+) resultB.datak.iB.datak.j=B.datak.v; cout<<"結(jié)果為："<<endl; for(k=1;k<=B.n;k+) for(int l=1;l<=B.m;l+) cout<<resultkl<<" " cou

14、t<<endl; 以上主要設(shè)計(jì)思想：通過三元組輸入一個(gè)矩陣A，為了找到A的每一列中所有非零元素，需要對其三元組表A.data從第一行起整個(gè)掃描一遍，由于A.data是以A的行序?yàn)橹餍騺泶娣琶總€(gè)非零元的，由此得到的恰是B.data的應(yīng)有的順序。加法矩陣：void tripletable:add( ) /矩陣的加法 int k; tripletable A,B; cout<<"輸入稀疏矩陣A的行數(shù)，列數(shù)和非零元個(gè)數(shù)：" cin>>A.m>>A.n>>A.t; for(k=1;k<=A.t;k+) printf(&

15、quot;輸入第%d個(gè)非0元素的行數(shù)，列數(shù)和值:",k); cin>>A.datak.i>>A.datak.j>>A.datak.v; cout<<"輸入稀疏矩陣B的行數(shù)，列數(shù)和非零元個(gè)數(shù)：" cin>>B.m>>B.n>>B.t; for(k=1;k<=B.t;k+) printf("輸入第%d個(gè)非0元素的行數(shù)，列數(shù)和值:",k); cin>>B.datak.i>>B.datak.j>>B.datak.v; if(A.

16、m!=B.m|A.n!=B.n) cout<<"輸入錯(cuò)誤：A與B的行數(shù)或列數(shù)不相同，請重新輸入"<<endl; return; int a100100=0; for(k=1;k<=A.t;k+) aA.datak.iA.datak.j=A.datak.v; cout<<"A輸入為："<<endl; for(k=1;k<=A.m;k+) for(int l=1;l<=A.n;l+) cout<<akl<<" " cout<<endl;

17、int b100100=0; for(k=1;k<=B.t;k+) bB.datak.iB.datak.j=B.datak.v; cout<<"B輸入為："<<endl; for(k=1;k<=B.m;k+) for(int l=1;l<=B.n;l+) cout<<bkl<<" " cout<<endl; int c100100=0; for(k=1;k<=A.m;k+) for(int l=1;l<=A.n;l+) ckl=akl+bkl; cout<&l

18、t;"加法結(jié)果C為："<<endl; for(k=1;k<=A.m;k+) for(int l=1;l<=A.n;l+) cout<<ckl<<" " cout<<endl; 以上主要設(shè)計(jì)思想：此功能由函數(shù)add( )實(shí)現(xiàn)，當(dāng)用戶選擇該功能時(shí)系統(tǒng)即提示用戶初始化要進(jìn)行加法的兩個(gè)矩陣的信息。然后檢測這兩個(gè)矩陣是否符合矩陣相加的規(guī)則，如果符合，進(jìn)行加法。否則重新輸入第二個(gè)矩陣來保證兩個(gè)矩陣可以相加。最后輸出結(jié)果。乘法矩陣：void tripletable:multi() /矩陣的乘法 int k;

19、tripletable A,B,C; cout<<"輸入稀疏矩陣A的行數(shù)，列數(shù)和非零元個(gè)數(shù)：" cin>>A.m>>A.n>>A.t; for(k=1;k<=A.t;k+) printf("輸入第%d個(gè)非0元素的行數(shù)，列數(shù)和值:",k); cin>>A.datak.i>>A.datak.j>>A.datak.v; int row=1; for(k=1;k<=A.t;k+) while(row<=A.datak.i) A.rposrow+=k; while

20、(row<=A.m)A.rposrow+=A.t+1; cout<<"輸入稀疏矩陣B的行數(shù)，列數(shù)和非零元個(gè)數(shù)：" cin>>B.m>>B.n>>B.t; for(k=1;k<=B.t;k+) printf("輸入第%d個(gè)非0元素的行數(shù)，列數(shù)和值:",k); cin>>B.datak.i>>B.datak.j>>B.datak.v; row=1; for(k=1;k<=B.t;k+) while(row<=B.datak.i) B.rposrow+=

21、k; while(row<=B.m)B.rposrow+=B.t+1; if(A.n!=B.m) cout<<"輸入錯(cuò)誤：A的列數(shù)不等于B的行數(shù)，請重新輸入"<<endl; return; C.m=A.m;C.n=B.n;C.t=0; int arow,p,q,ccol,t,tp; if(A.t*B.t!=0) for(arow=1;arow<=A.m;+arow) int ctempmaxsize=0; C.rposarow=C.t+1; if(arow<A.m)tp=A.rposarow+1; elsetp=A.t+1; for

22、(p=A.rposarow;p<tp;+p) int brow=A.datap.j; if(brow<B.m)t=B.rposbrow+1; elset=B.t+1; for(q=B.rposbrow;q<t;+q) ccol=B.dataq.j; ctempccol+=A.datap.v*B.dataq.v; for(ccol=1;ccol<=C.n;+ccol) if(ctempccol) if(+C.t>maxsize)return; C.dataC.t.i=arow; C.dataC.t.j=ccol; C.dataC.t.v=ctempccol; int

23、 a100100=0; for(k=1;k<=A.t;k+) aA.datak.iA.datak.j=A.datak.v; cout<<"A輸入為：" cout<<endl; for(k=1;k<=A.m;k+) for(int l=1;l<=A.n;l+) cout<<akl<<" " cout<<endl; int b100100=0; for(k=1;k<=B.t;k+) bB.datak.iB.datak.j=B.datak.v; cout<<&quo

24、t;B輸入為："<<endl; for(k=1;k<=B.m;k+) for(int l=1;l<=B.n;l+) cout<<bkl<<" " cout<<endl; int c100100=0; for(k=1;k<=C.t;k+) cC.datak.iC.datak.j=C.datak.v; cout<<"乘法結(jié)果C為："<<endl; for(k=1;k<=C.m;k+) for(int l=1;l<=C.n;l+) cout<&

25、lt;ckl<<" " cout<<endl; 以上主要設(shè)計(jì)思想為：此功能由函數(shù)multi( )實(shí)現(xiàn)。當(dāng)用戶選擇該功能，系統(tǒng)提示輸入要進(jìn)行相乘的兩個(gè)矩陣的詳細(xì)信息。然后檢測兩者是否可以相乘，如果不能，則重新初始化第二個(gè)矩陣。先對矩陣B進(jìn)行逐行處理，先求得累計(jì)求和的中間結(jié)果（C的每一行），然后再壓縮存儲到c.data中去，最后得到結(jié)果。 第四章 設(shè)計(jì)理論分析方法4.1 算法一：矩陣轉(zhuǎn)置轉(zhuǎn)置運(yùn)算時(shí)一種最簡單的矩陣運(yùn)算，對于一個(gè)m*n的矩陣M，他的轉(zhuǎn)置矩陣T是一個(gè)n*m的矩陣，且T（i，j）=M（j，i），1<=i<=n,1<=j<

26、=m。顯然，一個(gè)稀疏矩陣的轉(zhuǎn)置矩陣仍然是稀疏矩陣。(1)將矩陣的行列值相互交換;(2)將每個(gè)三元組中的i和j相互調(diào)換；（3）重排三元組之間的次序便可實(shí)現(xiàn)矩陣的轉(zhuǎn)置。 一般矩陣轉(zhuǎn)置算法為for(col=1;col<=nu;+col) for(row=1;row<=mu;+row)Tcolrow=Mrowcol;按照a.data中三元組的次序進(jìn)行轉(zhuǎn)置，并將轉(zhuǎn)置后的三元組置入b中恰當(dāng)?shù)奈恢?。在此，需要附設(shè)num和cpot兩個(gè)向量。Numcol表示矩陣M中第col列中非零元的個(gè)數(shù)，cpotcol指示M中第col列的第一個(gè)非零元在b.data中的恰當(dāng)位置。cpot1=1cpotcol=cpo

27、tcol-1+numcol-1 2<=col<=a.nu這就是快速轉(zhuǎn)置。4.2 算法二：矩陣加法 稀疏矩陣使用三元組存儲，則運(yùn)算時(shí)只需考慮非零元的值即可。兩個(gè)矩陣相加首先必須保證M.mu=N.mu&&M.nu=N.nu即同行同列的矩陣才能相加。 for(k=1;k<=M.tu;k+)for(i=1;i<=N.tu;i+)if(M.datak.i = N.datai.i && M.datak.j = N.datai.j) Q.datacount.e = M.datak.e + N.datai.e;flagi = true;如果非零元位置一樣就直接相加if(i>N.tu)Q.datacount.e = M.datak.e;如果沒有找到與M非零元位置一樣的元素就直接把M中的非零元賦值給矩陣Q。for(k=1;k<=N.tu;k+)if(!flagk)Q.datacount.e = N.datak.e;如果N中的元素沒有被查找，則直接把N中的非零元賦值給矩陣Q。4.3 算法三：矩陣乘法矩陣乘法采用“帶行鏈接信息”的三元組存儲。經(jīng)典算法如下：