數(shù)據(jù)結(jié)構(gòu)課程設(shè)計稀疏矩陣實現(xiàn)與應(yīng)用

1、安徽省巢湖學(xué)院計算機(jī)與信息工程學(xué)院課程設(shè)計報告課程名稱 數(shù)據(jù)結(jié)構(gòu) 課題名稱 稀疏矩陣實現(xiàn)與應(yīng)用 專業(yè) 計算機(jī)科學(xué)與技術(shù) 班級 學(xué)號姓名 聯(lián)系方式 指導(dǎo)教師20 11 年 12 月 25 日目 錄1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計任務(wù)書1.1、題目-1.2、要求-2、總體設(shè)計 -2.1、功能模塊設(shè)計-12.2、所有功能模塊的流程圖-23、詳細(xì)設(shè)計-33.1、程序中所采用的數(shù)據(jù)結(jié)構(gòu)及存儲結(jié)構(gòu)的說明-103.2、算法的設(shè)計思想-103.3、稀疏矩陣各種運算的性質(zhì)變換-104、調(diào)試與測試：-104.1、調(diào)試方法與步驟： -104.2、測試結(jié)果的分析與討論：-115、時間復(fù)雜度的分析：-126、源程序清單和執(zhí)行結(jié)果-

2、127、c程序設(shè)計總結(jié)-208、致謝-209、參考文獻(xiàn)-201、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計任務(wù)書1.1、題目 實現(xiàn)三元組，十字鏈表下的稀疏矩陣的加、轉(zhuǎn)、乘的實現(xiàn)。1.2、要求 (1).設(shè)計函數(shù)建立稀疏矩陣，初始化值； (2).設(shè)計函數(shù)輸出稀疏矩陣的值； (3).構(gòu)造函數(shù)進(jìn)行兩個稀疏矩陣相加，輸出最終的稀疏矩陣； (4).構(gòu)造函數(shù)進(jìn)行兩個稀疏矩陣相減，輸出最終的稀疏矩陣； (5).構(gòu)造函數(shù)進(jìn)行稀疏矩陣的轉(zhuǎn)置，并輸出結(jié)果； (6).退出系統(tǒng)。2、總體設(shè)計2.1、功能模塊設(shè)計輸入矩陣1矩陣相加輸入矩陣2計算結(jié)果矩陣相減輸入矩陣1輸入矩陣2計算結(jié)果矩陣轉(zhuǎn)置輸入矩陣計算結(jié)果退出2.2、所有功能模塊的流程圖3、詳細(xì)

3、設(shè)計1. 定義程序中所有用到的數(shù)據(jù)及其數(shù)據(jù)結(jié)構(gòu)，及其基本操作的實現(xiàn)；typedef struct int i, j; int e; triple; / 定義三元組的元素typedef struct triple datamaxsize + 1; int mu, nu, tu; tsmatrix; / 定義普通三元組對象typedef struct triple datamaxsize + 2; int rposmaxrow + 1； int mu, nu, tu; rlsmatrix; / 定義帶鏈接信息的三元組對象typedef struct olnode / 定義十字鏈表元素 int i,

4、 j; int e; struct olnode *right, *down; / 該非零元所在行表和列表的后繼元素 olnode, *olink; / 定義十字鏈表元素typedef struct / 定義十字鏈表對象結(jié)構(gòu)體 olink *rhead, *chead; int mu, nu, tu; / 系數(shù)矩陣的行數(shù)，列數(shù)，和非零元素個數(shù) crosslist; / 定義十字鏈表對象結(jié)構(gòu)體2主函數(shù)int main() int t; cout.fill(*); cout setw(80) *; cout.fill( ); cout setw(50) *歡迎使用矩陣運算程序* endl; /輸出

5、頭菜單 cout.fill(*); cout setw(80) *; cout.fill( ); cout 請選擇要進(jìn)行的操作： endl; cout 1:矩陣的轉(zhuǎn)置。 endl; cout 2:矩陣的加法。 endl; cout 3:矩陣的乘法。 endl; cout 4:退出程序。 endl;while(t)cout請輸入您要進(jìn)行的操作：t;switch(t)case 1:transposesmatrix(); /調(diào)用矩陣轉(zhuǎn)置函數(shù)break;case 2:addsmatrix(); /調(diào)用矩陣相加函數(shù)break;case 3: multsmatrix(); /調(diào)用矩陣相乘函數(shù)break;c

6、ase 4:t=0;break;return 0;矩陣的轉(zhuǎn)置函數(shù)bool transposesmatrix() / 求矩陣的轉(zhuǎn)置矩陣 tsmatrix m, t; /定義預(yù)轉(zhuǎn)置的矩陣 inputtsmatrix(m, 0); /輸入矩陣 int nummaxrow + 1; int cpotmaxrow + 1; / 構(gòu)建輔助數(shù)組 int q, p, t; t.tu = m.tu; t.mu = m.nu; t.nu = m.mu; if (t.tu) for (int col = 1; col = m.nu; col+) numcol = 0; for (t = 1; t = m.tu; t

7、+) +numm.datat.j; cpot1 = 1; for (int i = 2; i = m.nu; i+) cpoti = cpoti - 1 + numi - 1; / 求出每一列中非零元素在三元組中出現(xiàn)的位置 for (p = 1; p = m.tu; p+) int col = m.datap.j; q = cpotcol; t.dataq.i = m.datap.j; t.dataq.j = m.datap.i; t.dataq.e = m.datap.e; +cpotcol; cout 輸入矩陣的轉(zhuǎn)置矩陣為 endl; outputsmatrix(t); return tr

8、ue;bool count(rlsmatrix &t) int nummaxrow + 1; for (int row = 1; row = t.mu; row+) numrow = 0; for (int col = 1; col = t.tu; col+) +numt.datacol.i; t.rpos1 = 1; for (int i = 2; i = t.mu; i+) t.rposi = t.rposi - 1 + numi - 1; / 求取每一行中非零元素在三元組中出現(xiàn)的位置 return true;矩陣的乘法函數(shù)bool multsmatrix() / 兩個矩陣相乘 rlsma

9、trix m, n, q; / 構(gòu)建三個帶“鏈接信息”的三元組表示的數(shù)組 inputtsmatrix(m, 1); / 用普通三元組形式輸入數(shù)組 inputtsmatrix(n, 1); count(m); count(n); cout 輸入的兩矩陣的乘矩陣為： endl; if (m.nu != n.mu) return false; q.mu = m.mu; q.nu = n.nu; q.tu = 0; / q初始化 int ctempmaxrow + 1; / 輔助數(shù)組 int arow, tp, p, brow, t, q, ccol; if (m.tu * n.tu) / q是非零矩

10、陣 for (arow = 1; arow = m.mu; arow+) /memset(ctemp,0,n.nu); for (int x = 1; x = n.nu; x+) / 當(dāng)前行各元素累加器清零 ctempx = 0; q.rposarow = q.tu + 1; / 當(dāng)前行的首個非零元素在三元組中的位置為此行前所有非零元素+1 if (arow m.mu) tp = m.rposarow + 1; else tp = m.tu + 1; for (p = m.rposarow; p tp; p+) / 對當(dāng)前行每個非零元素進(jìn)行操作 brow = m.datap.j; / 在n中找

11、到i值也操作元素的j值相等的行 if (brow n.mu) t = n.rposbrow + 1; else t = n.tu + 1; for (q = n.rposbrow; q t; q+) / 對找出的行當(dāng)每個非零元素進(jìn)行操作 ccol = n.dataq.j; ctempccol += m.datap.e * n.dataq.e; / 將乘得到對應(yīng)值放在相應(yīng)的元素累加器里面 for (ccol = 1; ccol maxsize) return false; q.dataq.tu.e = ctempccol; q.dataq.tu.i = arow; q.dataq.tu.j =

12、ccol; outputsmatrix(q); return true;矩陣的加法函數(shù)bool addsmatrix() /矩陣的加法 crosslist m, n; / 創(chuàng)建兩個十字鏈表對象，并初始化 createsmatrix_ol(m); createsmatrix_ol(n); cout 輸入的兩矩陣的和矩陣為： endl; olink pa, pb, pre, hlmaxrow + 1; /定義輔助指針，pa，pb分別為m,n當(dāng)前比較的元素，pre為pa的前驅(qū)元素 for (int x = 1; x = m.nu; x+) hlx = m.cheadx; for (int k = 1

13、; k e = pb-e; p-i = pb-i; p-j = pb-j; if (null = pa | pa-j pb-j) / 當(dāng)m此行已經(jīng)檢查完或者pb因該放在pa前面 if (null = pre) m.rheadp-i = p; else pre-right = p; p-right = pa; pre = p; if (null = m.cheadp-j) / 進(jìn)行列插入 m.cheadp-j = p; p-down = null; else p-down = hlp-j-down; hlp-j-down = p; hlp-j = p; pb = pb-right; else i

14、f (null != pa) & pa-j j) / 如果此時的pb元素因該放在pa后面，則取以后的pa再來比較 pre = pa; pa = pa-right; else if (pa-j = pb-j) / 如果pa，pb位于同一個位置上，則將值相加 pa-e += pb-e; if (!pa-e) / 如果相加后的和為0，則刪除此節(jié)點，同時改變此元素坐在行，列的前驅(qū)元素的相應(yīng)值 if (null = pre) / 修改行前驅(qū)元素值 m.rheadpa-i = pa-right; else pre-right = pa-right; p = pa; pa = pa-right; if (m

15、.cheadp-j = p) m.cheadp-j = hlp-j = p-down; / 修改列前驅(qū)元素值 else hlp-j-down = p-down; free(p); pb = pb-right; else pa = pa-right; pb = pb-right; outputsmatrix_ol(m); return true;創(chuàng)建十字鏈表bool createsmatrix_ol(crosslist & m)/ 創(chuàng)建十字鏈表 int x, y, m; cout 請輸入矩陣的行，列，及非零元素個數(shù) m.mu m.nu m.tu; if (!(m.rhead = (olink*)

16、 malloc(m.mu + 1) * sizeof (olink) exit(0); if (!(m.chead = (olink*) malloc(m.nu + 1) * sizeof (olink) exit(0); for (x = 0; x = m.mu; x+) m.rheadx = null; / 初始化各行，列頭指針，分別為null for (x = 0; x = m.nu; x+) m.cheadx = null; cout 請按三元組的格式輸入數(shù)組： endl; for (int i = 1; i x y m; / 按任意順序輸入非零元，（普通三元組形式輸入） olink

17、p, q; if (!(p = (olink) malloc(sizeof (olnode) exit(0); / 開辟新節(jié)點，用來存儲輸入的新元素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 right); / 查找節(jié)點在行表中的插入位置 p-right = q-right; q-right = p; / 完成行插入 if (m.cheady = nul

18、l | m.cheady-i x) p-down = m.cheady; m.cheady = p; else for (q = m.cheady; (q-down) & (q-down-i down); / 查找節(jié)點在列表中的插入位置 p-down = q-down; q-down = p; / 完成列插入 return true;十字鏈表的輸出bool outputsmatrix_ol(crosslist t)/ 輸出十字鏈表，用普通數(shù)組形式輸出 for (int i = 1; i = t.mu; i+) olink p = t.rheadi; for (int j = 1; j j) c

19、out setw(3) e; p = p-right; else cout setw(3) 0; cout endl; return true;3.1、程序中所采用的數(shù)據(jù)結(jié)構(gòu)的說明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,colrow= | 1=i=m, 1=j=n-1 col= | 1=i=m-1, 1=j=n基本操作：createsmatrix(&m)； 操作結(jié)果：創(chuàng)建稀疏矩陣m。destroysmatrix(&m)； 初始條件：稀疏矩陣m存在。 操作結(jié)果：

20、銷毀稀疏矩陣m。printsmatrix(m)； 初始條件：稀疏矩陣m存在。 操作結(jié)果：輸出稀疏矩陣m。addsmatrix(m，n，&q)； 初始條件：稀疏矩陣m與n的行數(shù)和列數(shù)對應(yīng)相等 操作結(jié)果：求稀疏矩陣的和q=m+n。multsmatrix(m，n，q)； 初始條件：稀疏矩陣m的列數(shù)等于n的行數(shù)。 操作結(jié)果：求稀疏矩陣乘積q=m*n。 transposesmatrix(m，t)； 初始條件：稀疏矩陣m存在。 操作結(jié)果：求稀疏矩陣m的轉(zhuǎn)置矩陣t。 adt sparsematrix3.2、算法的設(shè)計思想本實驗要求在三元組，十字鏈表下實現(xiàn)稀疏 矩陣的加、轉(zhuǎn)、乘。首先要進(jìn)行矩陣的初始化操作，定

21、義三元組和十字鏈表的元素對象。寫出轉(zhuǎn)置，加法，乘法的操作函數(shù)。通過主函數(shù)調(diào)用實現(xiàn)在一個程序下進(jìn)行矩陣的運算操作。3.3、稀疏矩陣各種運算的性質(zhì)變換a)加法運算兩個稀疏矩陣的加和矩陣仍然是稀疏矩陣b）乘法運算兩個稀疏矩陣的乘積矩陣不是稀疏矩陣c）轉(zhuǎn)置運算一個稀疏矩陣的轉(zhuǎn)置矩陣仍然是稀疏矩陣4、調(diào)試與測試：4.1、調(diào)試方法與步驟：1. 實際完成的情況說明（完成的功能，支持的數(shù)據(jù)類型等）； 完成了稀疏矩陣的建立，初始化及輸出值的操作。 實現(xiàn)三元組，十字鏈表下的稀疏矩陣的加法，乘法以及轉(zhuǎn)置運算。2.程序的性能分析，包括時空分析；能應(yīng)對一般小的錯誤輸入，如果復(fù)雜則自動退出程序。3.上機(jī)過程中出現(xiàn)的問題及

22、其解決方案； 1.起始有錯誤,設(shè)定的變量名相同。經(jīng)檢查，改正。2一些邏輯錯誤。經(jīng)討論改正。運行出現(xiàn)部分語法錯誤修正4.程序中可以改進(jìn)的地方說明；程序在運行中一旦出現(xiàn)矩陣數(shù)據(jù)格式錯誤如輸入漢字，則程序自動退出。需要重新啟動。更新程序?qū)Ω噱e誤輸入情況的分析能力。5.程序中可以擴(kuò)充的功能及設(shè)計實現(xiàn)假想。對退出操作的擴(kuò)充在主菜單下，用戶輸入4回車選擇退出程序是，詢問是否真的退出系統(tǒng)，如果是，則即退出系統(tǒng)，否則顯示continue并且返回主菜單。為了方便由于誤按導(dǎo)致程序退出。在退出時可以增加一段感謝使用本程序的結(jié)束語。4.2、測試結(jié)果的分析與討論：系統(tǒng)運行主界面輸入需要執(zhí)行的操作1矩陣的轉(zhuǎn)置輸入需要執(zhí)

23、行的操作2矩陣的加法輸入需要執(zhí)行的操作3矩陣的乘法輸入錯誤操作時需要重新選擇退出操作5、時間復(fù)雜度的分析：a)加法運算由于兩矩陣行列相等，故時間復(fù)雜度為o（行*列）b）乘法運算設(shè)m是m1*n1矩陣，n是m2*n2矩陣，則時間復(fù)雜度是o（m1*n1*n2）c）轉(zhuǎn)置運算時間復(fù)雜度和原矩陣的列數(shù)及非零元的個數(shù)的乘積成正比，即o（mu*nu）6、 源程序清單和執(zhí)行結(jié)果#include #include using namespace std;const int maxsize = 100; / 定義非零元素的對多個數(shù)const int maxrow = 10; / 定義數(shù)組的行數(shù)的最大值 typede

24、f struct int i, j; int e; triple; / 定義三元組的元素typedef struct triple datamaxsize + 1; int mu, nu, tu; tsmatrix; / 定義普通三元組對象typedef struct triple datamaxsize + 2; int rposmaxrow + 1; int mu, nu, tu; rlsmatrix; / 定義帶鏈接信息的三元組對象typedef struct olnode / 定義十字鏈表元素 int i, j; int e; struct olnode *right, *down;

25、/ 該非零元所在行表和列表的后繼元素 olnode, *olink; / 定義十字鏈表元素typedef struct / 定義十字鏈表對象結(jié)構(gòu)體 olink *rhead, *chead; int mu, nu, tu; / 系數(shù)矩陣的行數(shù)，列數(shù)，和非零元素個數(shù) crosslist; / 定義十字鏈表對象結(jié)構(gòu)體template bool inputtsmatrix(p & t, int y) /輸入矩陣，按三元組格式輸入 cout 輸入矩陣的行，列和非零元素個數(shù): t.mu t.nu t.tu; cout 請輸出非零元素的位置和值: endl; for (int k = 1; k t.dat

26、ak.i t.datak.j t.datak.e; return true;template bool outputsmatrix(p t) int m, n, k = 1; for (m = 0; m t.mu; m+) for (n = 0; n t.nu; n+) if (t.datak.i - 1) = m & (t.datak.j - 1) = n) cout.width(4); cout t.datak+.e; else cout.width(4); cout 0; cout endl; return true;/ 輸出矩陣，按標(biāo)準(zhǔn)格式輸出bool transposesmatrix

27、() / 求矩陣的轉(zhuǎn)置矩陣 tsmatrix m, t; /定義預(yù)轉(zhuǎn)置的矩陣 inputtsmatrix(m, 0); /輸入矩陣 int nummaxrow + 1; int cpotmaxrow + 1; / 構(gòu)建輔助數(shù)組 int q, p, t; t.tu = m.tu; t.mu = m.nu; t.nu = m.mu; if (t.tu) for (int col = 1; col = m.nu; col+) numcol = 0; for (t = 1; t = m.tu; t+) +numm.datat.j; cpot1 = 1; for (int i = 2; i = m.nu

28、; i+) cpoti = cpoti - 1 + numi - 1; / 求出每一列中非零元素在三元組中出現(xiàn)的位置 for (p = 1; p = m.tu; p+) int col = m.datap.j; q = cpotcol; t.dataq.i = m.datap.j; t.dataq.j = m.datap.i; t.dataq.e = m.datap.e; +cpotcol; cout 輸入矩陣的轉(zhuǎn)置矩陣為 endl; outputsmatrix(t); return true;bool count(rlsmatrix &t) int nummaxrow + 1; for (i

29、nt row = 1; row = t.mu; row+) numrow = 0; for (int col = 1; col = t.tu; col+) +numt.datacol.i; t.rpos1 = 1; for (int i = 2; i = t.mu; i+) t.rposi = t.rposi - 1 + numi - 1; / 求取每一行中非零元素在三元組中出現(xiàn)的位置 return true;bool multsmatrix() / 兩個矩陣相乘 rlsmatrix m, n, q; / 構(gòu)建三個帶“鏈接信息”的三元組表示的數(shù)組 inputtsmatrix(m, 1); /

30、用普通三元組形式輸入數(shù)組 inputtsmatrix(n, 1); count(m); count(n); cout 輸入的兩矩陣的乘矩陣為： endl; if (m.nu != n.mu) return false; q.mu = m.mu; q.nu = n.nu; q.tu = 0; / q初始化 int ctempmaxrow + 1; / 輔助數(shù)組 int arow, tp, p, brow, t, q, ccol; if (m.tu * n.tu) / q是非零矩陣 for (arow = 1; arow = m.mu; arow+) /memset(ctemp,0,n.nu);

31、for (int x = 1; x = n.nu; x+) / 當(dāng)前行各元素累加器清零 ctempx = 0; q.rposarow = q.tu + 1; / 當(dāng)前行的首個非零元素在三元組中的位置為此行前所有非零元素+1 if (arow m.mu) tp = m.rposarow + 1; else tp = m.tu + 1; for (p = m.rposarow; p tp; p+) / 對當(dāng)前行每個非零元素進(jìn)行操作 brow = m.datap.j; / 在n中找到i值也操作元素的j值相等的行 if (brow n.mu) t = n.rposbrow + 1; else t =

32、n.tu + 1; for (q = n.rposbrow; q t; q+) / 對找出的行當(dāng)每個非零元素進(jìn)行操作 ccol = n.dataq.j; ctempccol += m.datap.e * n.dataq.e; / 將乘得到對應(yīng)值放在相應(yīng)的元素累加器里面 for (ccol = 1; ccol maxsize) return false; q.dataq.tu.e = ctempccol; q.dataq.tu.i = arow; q.dataq.tu.j = ccol; outputsmatrix(q); return true;bool createsmatrix_ol(cr

33、osslist & m)/ 創(chuàng)建十字鏈表 int x, y, m; cout 請輸入矩陣的行，列，及非零元素個數(shù) m.mu m.nu m.tu; if (!(m.rhead = (olink*) malloc(m.mu + 1) * sizeof (olink) exit(0); if (!(m.chead = (olink*) malloc(m.nu + 1) * sizeof (olink) exit(0); for (x = 0; x = m.mu; x+) m.rheadx = null; / 初始化各行，列頭指針，分別為null for (x = 0; x = m.nu; x+) m.cheadx = null; cout 請按三元組的格式輸入數(shù)組： endl; for (int i = 1; i x y m; / 按任意順序輸入非零元，（普通三元組形式輸入） olink p, q; if (!(p = (olink) malloc(sizeof (olnode) exit(0); / 開辟新節(jié)點，用來存儲輸入的新元素p-i = x; p-j = y; p-e = m; if (m.rheadx = null | m.rheadx-j y) p-right = m.rheadx; m.rhea