魏偉實(shí)驗(yàn)報(bào)告

1、-魏偉-實(shí)驗(yàn)報(bào)告作者：日期:計(jì)算機(jī)科學(xué)與工程學(xué)院算法與數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告（五）專業(yè)班級(jí)2013級(jí)計(jì)算機(jī)工程專業(yè)02班實(shí)驗(yàn)地點(diǎn)40 3機(jī)房學(xué)生學(xué)號(hào)130512061 7指導(dǎo)教師蔡瓊學(xué)生姓名魏偉實(shí)驗(yàn)時(shí)間20 1 5-05 02實(shí)驗(yàn)項(xiàng)目稀疏矩陣的應(yīng)用實(shí)驗(yàn)類別基礎(chǔ)性（2）設(shè)計(jì)性（）綜合性（）其它（）實(shí) 驗(yàn) 目 的 及 要 求（1）掌握掌握稀疏矩陣的表示方法及其運(yùn)算的實(shí)現(xiàn)；（2）實(shí)現(xiàn)稀疏矩陣在二兀組、十子鏈表等表示下的各運(yùn)算并分析 其效率。成績(jī)?cè)u(píng)定表類另S評(píng)分標(biāo)準(zhǔn)分值得分合計(jì)上機(jī)表現(xiàn)積極出勤、遵守紀(jì)律 按要求完成設(shè)計(jì)任務(wù)30分程序與報(bào)告程序代碼規(guī)范、功能正確報(bào)告詳實(shí)完整、體現(xiàn)收獲70分說(shuō)明：評(píng)閱教師：蔡瓊

2、日期：2 0 15年.5 月 9 日實(shí)驗(yàn)內(nèi)容實(shí)驗(yàn)內(nèi)容在mK n的矩陣中,有t個(gè)非零元。令S = t/(m衣n),稱S矩陣的稀疏因子, 常認(rèn)為0.05時(shí)稱為稀疏矩陣。稀疏矩陣在工程中有著大量的應(yīng)用，不少工 程問(wèn)題都可以轉(zhuǎn)化為對(duì)稀疏矩陣的計(jì)算問(wèn)題。用三元組表實(shí)現(xiàn)稀疏矩陣的轉(zhuǎn)置， 用(順序取，直接存)方法。實(shí)驗(yàn)說(shuō)明：引入兩個(gè)數(shù)組作為輔助數(shù)據(jù)結(jié)構(gòu)：num nu :表示矩陣A中某列的非零元素的個(gè)數(shù)； cp ot nu:初始值表示矩陣A中某列的第一個(gè)非零元素在 B中的位置。?ium與c po t遞推關(guān)系:?cpot0=0 ;三元組表實(shí)現(xiàn)稀疏矩陣的轉(zhuǎn)置(順序取，直接存)算法偽代碼如下:1. 設(shè)置轉(zhuǎn)置后矩陣

3、B的行數(shù)、列數(shù)和非零元素的個(gè)數(shù)；2. 計(jì)算A中每一列的非零元素個(gè)數(shù)；3. 計(jì)算A中每一列的第一個(gè)非零元素在 B中的下標(biāo)；4. 依次取A中的每一個(gè)非零元素對(duì)應(yīng)的三元組；2.1確定該元素在 B中的下標(biāo)pb；2.2將該元素的行號(hào)列號(hào)交換后存入B中pb的位置；2.3預(yù)置該元素所在列的下一個(gè)元素的存放位置；存儲(chǔ)一個(gè)稀疏矩陣需要定義一個(gè)三元組和三元組順序表，三元組存儲(chǔ)稀疏矩陣中非零元素的行坐標(biāo)，列坐標(biāo)和元素值(規(guī)定行列下標(biāo)值從0開(kāi)始)，而三元 組順序表里則存儲(chǔ)稀疏矩陣的行數(shù)，列數(shù)和非零元素的個(gè)數(shù)及其數(shù)值。在實(shí)現(xiàn)矩陣轉(zhuǎn)置的函數(shù)中，定義一個(gè)新的三元組順序表用于存放轉(zhuǎn)置后的矩 陣，用A表示要轉(zhuǎn)置的稀疏矩陣，B表

4、示轉(zhuǎn)置后的矩陣，則E的行數(shù)等于 A的列 數(shù),列數(shù)等于A的行數(shù)，再?gòu)腁中定位到每個(gè)非零元素，將其行坐標(biāo)和列坐標(biāo)對(duì) 換后存入B中即實(shí)現(xiàn)了整個(gè)過(guò)程，最后輸出轉(zhuǎn)置后的矩陣。系統(tǒng)共設(shè)置了 8個(gè)子程序，各子程序的函數(shù)名及功能說(shuō)明如下。(1)C r eat eSMatrix( R L S Matrix &M ) / / 創(chuàng)建稀疏矩陣(2)v o id Destroy SMatri x (RLS Matrix &M)銷毀稀疏矩陣(3) vo i d Prin RLSMa tr ix (RL SMa trix M)遍歷稀疏矩陣(4) v oid prn t(RLSM at r ix A) /打印矩陣函數(shù),輸出以

5、陣列形式表示的矩陣(5) r a nsposeSMat rix(RLSMatri x M,R LSM a tri x & T) / 求稀疏矩陣的轉(zhuǎn) 置的一般算法(6)Fas tTranspos eS Matrix(RLSM a tr i x M , RLSMatri x &T) /快速轉(zhuǎn)置 算法(7) void sh owt i p ()/工作區(qū)函數(shù)，顯示程序菜單(8) vo i d main()主函數(shù)預(yù)期結(jié)果50 0 7010 010 0 0可以用三元組表示為：3 4 41 1 51 472 2 13 1 1源代碼# i nelude v s td i o. h#de f i ne M 5

6、0#defin e N 5 0#def i ne Max Si z e 125t yped ef s tructin t r;?i nt c;int d ; TupNode;t y pede f struct? n t rows;?n t cols;intnum s;?TupNode data Max S ize;TSMatrix;v o id Tra nM a t( TSMa trix a , TSM atr i x &b);v o i dGetMat(TSMa tr i x &a);voi d Pri M a t (TSMatr i x a );vo i d m ai n ()?TSMat

7、rix a,b;Get Ma t(a);?Tra n Ma t (a, b);pr intf(您輸入的矩陣的為:n);?riMat( a );printf(經(jīng)過(guò)轉(zhuǎn)置后得到的矩陣的為：n );Pri Mat (b);v o id Tr a nMa t (TSMa trix a, T SMatri x &b)i n t e;?D.r o ws=a. c ols ;?d. c ols = a.rows;b.num s =a.nu ms;?nt nN=0;i nt cp o tN = 0;for(i nt j= 0;ja .nu ms;j+)? a .dat a j.c +;?f or (int i

8、= 2;i=a.cols;i+)2pot i =cpot i-1 +ni- 1 ;f or( i =0; i a .n u ms;i+)? i nt col = a.d a t a i . c ;? e= cpo t col ; bdatae. c= a. data i .r;?.datae. r =a. dat a i . c; bdatae.d=a.da ta i .d;cp o tcol+;void Get M at(T SM atrix & a )?Drint f (請(qǐng)輸入稀疏矩陣中非零元素的個(gè)數(shù) n:);s canf (% d，&a .nu ms);printf(請(qǐng)依次輸入稀疏矩陣的

9、行數(shù)和列數(shù)：);sca nf( % d%d ，& a. r o ws,&a.col s);p ri n tf( 請(qǐng)按照三元組行、列、值的方式依次輸入該稀疏矩陣n );?or(int i=0； ia.n u ms ; i +)?c a n f(%d %d %d , &a.dat a i .r,& a .datai.c, &a.data i .d);void Pri M a t( TSMa tr i x a)? n t i;?pr i ntf (t%d 行t %d 列n ,a.ro w s, a. c o 1 s);?printf(” n);prin t f( t 行 t 列上值 n);f o r(i = 0; i a. n um s;i+ +)? printf( t % dt%dt% d n , a.da t a i . r,a.da t a i .c,a.da ta i .d);prin t f ( n);? ?實(shí)驗(yàn)內(nèi)