數(shù)據(jù)結構課程設計之稀疏矩陣實現(xiàn)與應用1.doc

數(shù)據(jù)結構課程設計報告題目：十字鏈表成為存儲結構，實現(xiàn)稀疏矩陣的求和運算學生姓名:張旋班級:軟件三班 學號:201213040304指導教師: 吳小平 一、需求分析 1.問題描述：要求：十字鏈表下的稀疏矩陣的加、轉、乘的實現(xiàn)。 2.基本功能 實現(xiàn)十字鏈表下的轉置，乘法，加法運算。 3.輸入輸出 （1）設計函數(shù)建立稀疏矩陣，初始化值。（2）設計函數(shù)輸出稀疏矩陣的值。（3）構造函數(shù)進行兩個稀疏矩陣相加，輸出最終的稀疏矩陣。（4）構造函數(shù)進行兩個稀疏矩陣的相乘，輸出最終的稀疏矩陣。（5）構造函數(shù)進行稀疏矩陣的轉置，并輸出結果。（6）退出系統(tǒng)。二、 概要設計1.設計思路：本實驗要求在三元組，十字鏈表下實現(xiàn)稀疏矩陣的加、轉、乘。首先要進行矩陣的初始化操作，定義三元組和十字鏈表的元素對象。寫出轉置，加法，乘法的操作函數(shù)。通過主函數(shù)調用實現(xiàn)在一個程序下進行矩陣的運算操作。 2.數(shù)據(jù)結構設計：抽象數(shù)據(jù)類型稀疏矩陣的定義如下：ADT SparseMatrix 數(shù)據(jù)對象：D=aij | i=1,2,m; j=1,2,.,n;aijElemset, m和n分別稱為矩陣的行數(shù)和列數(shù)。數(shù)據(jù)關系：R=Row,ColRow= | 1=i=m, 1=j=n-1 Col= | 1=i=m-1, 1=j=n基本操作：CreateSMatrix(&M)； 操作結果：創(chuàng)建稀疏矩陣M。DestroySMatrix(&M)； 初始條件：稀疏矩陣M存在。 操作結果：銷毀稀疏矩陣M。PrintSMatrix(M)； 初始條件：稀疏矩陣M存在。 操作結果：輸出稀疏矩陣M。AddSMatrix(M，N，&Q)； 初始條件：稀疏矩陣M與N的行數(shù)和列數(shù)對應相等 操作結果：求稀疏矩陣的和Q=M+N。MultSMatrix(M，N，Q)； 初始條件：稀疏矩陣M的列數(shù)等于N的行數(shù)。 操作結果：求稀疏矩陣乘積Q=M*N。 TransposeSMatrix(M，T)； 初始條件：稀疏矩陣M存在。 操作結果：求稀疏矩陣M的轉置矩陣T。 ADT SparseMatrix 3.軟件結構設計：（1）主程序模塊：Void main（）初始化；do 接受命令；處理命令；while（“命令”=“退出”）；（2）稀疏矩陣模塊實現(xiàn)矩陣的相加bool AddSMatrix()；實現(xiàn)矩陣的相乘bool MultSMatrix()；實驗矩陣的轉置bool TransposeSMatrix()；（3）十字鏈表模塊 創(chuàng)建十字鏈表bool CreateSMatrix_OL(CrossList & M)； 輸出十字鏈表bool OutPutSMatrix_OL(CrossList T)；(4) 主程序模塊 稀疏矩陣模塊 十字鏈表模塊三、 詳細設計 1. 定義程序中所有用到的數(shù)據(jù)及其數(shù)據(jù)結構，及其基本操作的實現(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, j; int e; struct OLNode *right, *down; / 該非零元所在行表和列表的后繼元素 OLNode, *OLink; / 定義十字鏈表元素typedef struct / 定義十字鏈表對象結構體 OLink *rhead, *chead; int mu, nu, tu; / 系數(shù)矩陣的行數(shù)，列數(shù)，和非零元素個數(shù) CrossList; / 定義十字鏈表對象結構體2主函數(shù)int main() int t; cout.fill(*); cout setw(80) *; cout.fill( ); cout setw(50) *歡迎使用矩陣運算程序* endl; /輸出頭菜單 cout.fill(*); cout setw(80) *; cout.fill( ); cout 請選擇要進行的操作： endl; cout 1:矩陣的轉置。 endl; cout 2:矩陣的加法。 endl; cout 3:矩陣的乘法。 endl; cout 4:退出程序。 endl;while(t)cout請輸入您要進行的操作：t;switch(t)case 1:TransposeSMatrix(); /調用矩陣轉置函數(shù)break;case 2:AddSMatrix(); /調用矩陣相加函數(shù)break;case 3: MultSMatrix(); /調用矩陣相乘函數(shù)break;case 4:t=0;break;return 0;矩陣的轉置函數(shù)bool TransposeSMatrix() / 求矩陣的轉置矩陣 TSMatrix M, T; /定義預轉置的矩陣 InPutTSMatrix(M, 0); /輸入矩陣 int numMAXROW + 1; int cpotMAXROW + 1; / 構建輔助數(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; 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 輸入矩陣的轉置矩陣為 endl; OutPutSMatrix(T); return true;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() / 兩個矩陣相乘 RLSMatrix M, N, Q; / 構建三個帶“鏈接信息”的三元組表示的數(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是非零矩陣 for (arow = 1; arow = M.mu; arow+) /memset(ctemp,0,N.nu); for (int x = 1; x = N.nu; x+) / 當前行各元素累加器清零 ctempx = 0; Q.rposarow = Q.tu + 1; / 當前行的首個非零元素在三元組中的位置為此行前所有非零元素+1 if (arow M.mu) tp = M.rposarow + 1; else tp = M.tu + 1; for (p = M.rposarow; p tp; p+) / 對當前行每個非零元素進行操作 brow = M.datap.j; / 在N中找到i值也操作元素的j值相等的行 if (brow N.mu) t = N.rposbrow + 1; else t = N.tu + 1; for (q = N.rposbrow; q t; q+) / 對找出的行當每個非零元素進行操作 ccol = N.dataq.j; ctempccol += M.datap.e * N.dataq.e; / 將乘得到對應值放在相應的元素累加器里面 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;矩陣的加法函數(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當前比較的元素，pre為pa的前驅元素 for (int x = 1; x = M.nu; x+) hlx = M.cheadx; for (int k = 1; k e = pb-e; p-i = pb-i; p-j = pb-j; if (NULL = pa | pa-j pb-j) / 當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) / 進行列插入 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 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é)點，同時改變此元素坐在行，列的前驅元素的相應值 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; 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*) 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.rheadx = p; else for (q = M.rheadx; (q-right) & (q-right-j right); / 查找節(jié)點在行表中的插入位置 p-right = q-right; q-right = p; / 完成行插入 if (M.cheady = NULL | 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) cout setw(3) e; p = p-right; else cout setw(3) 0; cout endl; return true;3.主要函數(shù)的程序流程圖，實現(xiàn)設計中主程序和其他子模塊的算法，以流程圖的形式表示。 矩陣的相加流程圖 矩陣的相乘流程圖 矩陣轉置的流程圖 主函數(shù)流程圖4. 畫出函數(shù)之間的調用關系圖。 Main AddSMatrix TransposeSMatrix MultSMatrix CreateSMatrix_OL InPutTSMatrix OutPutSMatrix InPutTSMatrix OutPutSMatrix_OL 四、 調試分析 1.實際完成的情況說明（完成的功能，支持的數(shù)據(jù)類型等）；完成了稀疏矩陣的建立，初始化及輸出值的操作。 實現(xiàn)三元組，十字鏈表下的稀疏矩陣的加法，乘法以及轉置運算。2.程序的性能分析，包括時空分析；能應對一般小的錯誤輸入，如果復雜則自動退出程序3.上機過程中出現(xiàn)的問題及其解決方案； 1.起始有錯誤,設定的變量名相同。經(jīng)檢查，改正。2一些邏輯錯誤。經(jīng)討論改正。運行出現(xiàn)部分語法錯誤修正4.程序中可以改進的地方說明；程序在運行中一旦出現(xiàn)矩陣數(shù)據(jù)格式錯誤如輸入漢字，則程序自動退出。需要重新啟動。更新程序對更多錯誤輸入情況的分析能力。5.程序中可以擴充的功能及設計實現(xiàn)假想。對退出操作的擴充在主菜單下，用戶輸入4回車選擇退出程序是，詢問是否真的退出系統(tǒng)，如果是，則即退出系統(tǒng)，否則顯示continue并且返回主菜單。為了方便由于誤按導致程序退出。在退出時可以增加一段感謝使用本程序的結束語。五、測試結果系統(tǒng)運行主界面輸入需要執(zhí)行的操作1矩陣的轉置輸入需要執(zhí)行的操作2矩陣的加法輸入需要執(zhí)行的操作3矩陣的乘法輸入錯誤操作時需要重新選擇退出操作六、用戶手冊1.本程序執(zhí)行文件為：crosslist.exe2進入本系統(tǒng)之后，隨即顯示系統(tǒng)主菜單界面。用戶可在該界面下輸入各子菜單前對應的數(shù)字并按回車，執(zhí)行相應子菜單命令3執(zhí)行操作時，按要求輸入數(shù)字。彼此之間用空格隔開。4執(zhí)行加法運算時，輸入的兩個矩陣的行必須相同，列數(shù)也必須相同。這是基本的矩陣運算常識。5.執(zhí)行乘法運算時，第一個矩陣的行數(shù)和第二個矩陣的列數(shù)相同。6.當輸入錯誤時請嘗試退出程序重新運行。請盡量遵守矩陣運算的規(guī)則輸入有效的運算。七、體會與自我評價 我選的上機題目是實現(xiàn)三元組，十字鏈表下的轉置，乘法，加法運算。對這個題目，我覺得有點難，因為我們數(shù)據(jù)結構這一部分并沒有講，可是選題必須是每人選擇一個不許選重。有點無奈吧，當作是考驗了。各種資料收集，各種代碼整合。各種錯誤。雖然上機的時間只有短短兩個星期，但從中學到了不少知識。數(shù)據(jù)結構可以說是計算機里一門基礎課程，對于以后的學習尤為重要。所以我們一定要把基礎學扎實，這兩周的上機幫我們重新鞏固基礎知識，提高了我們專業(yè)的動手實踐能力。在實踐的過程中我們應當有良好的規(guī)劃，每天完成一小部分。盡量減少操作的盲目性，提高我們學習的效率。有個總體的大綱來逐步實現(xiàn)。我也曾經(jīng)犯過這種錯誤。每個函數(shù)都做出來部分。結果都沒做完。所以計劃很重要在實驗中我們要培養(yǎng)自己獨立的思考能力和解決問題的能力。培養(yǎng)這種能力主要看我們對待這次實驗的態(tài)度。我們要把它當作以后工作時接的項目一樣認真對待。積極的朝著更好地一面發(fā)展不斷的完善程序。不能馬馬虎虎隨便應付一下。 通過這次實驗我也認識到了數(shù)據(jù)結構這門課程的重要性，以及C語言功能的強大。它可以令計算機執(zhí)行各種你想要的操作。當然前提是你的技術水平。使我深刻的認識到要學好數(shù)據(jù)結構這門課程，為了以后打好堅實的基礎。提高自己的動手實踐能力，把所學的理論知識和實踐相結合。就像古人云，紙上得來終覺淺，得知此事要躬行。為了以后的計算機道路。不斷的提高自身的專業(yè)素養(yǎng)。奮斗。 也希望在今后的學習生活中向老師學到更多的知識。不斷的充實自己。努力改正自己的壞毛病，做個奮發(fā)向上的大學生。源代碼：#include #include using namespace std;const int MAXSIZE = 100; / 定義非零元素的對多個數(shù)const int MAXROW = 10; / 定義數(shù)組的行數(shù)的最大值 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, j; int e; struct OLNode *right, *down; / 該非零元所在行表和列表的后繼元素 OLNode, *OLink; / 定義十字鏈表元素typedef struct / 定義十字鏈表對象結構體 OLink *rhead, *chead; int mu, nu, tu; / 系數(shù)矩陣的行數(shù)，列數(shù)，和非零元素個數(shù) CrossList; / 定義十字鏈表對象結構體template bool InPutTSMatrix(P & T, int y) /輸入矩陣，按三元組格式輸入 cout 輸入矩陣的行，列和非零元素個數(shù): T.mu T.nu T.tu; cout 請輸出非零元素的位置和值: endl; for (int k = 1; k T.datak.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;/ 輸出矩陣，按標準格式輸出bool TransposeSMatrix() / 求矩陣的轉置矩陣 TSMatrix M, T; /定義預轉置的矩陣 InPutTSMatrix(M, 0); /輸入矩陣 int numMAXROW + 1; int cpotMAXROW + 1; / 構建輔助數(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; 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 輸入矩陣的轉置矩陣為 endl; OutPutSMatrix(T); return true;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;bool MultSMatrix() / 兩個矩陣相乘 RLSMatrix M, N, Q; / 構建三個帶“鏈接信息”的三元組表示的數(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是非零矩陣 for (arow = 1; arow = M.mu; arow+) /memset(ctemp,0,N.nu); for (int x = 1; x = N.nu; x+) / 當前行各元素累加器清零 ctempx = 0; Q.rposarow = Q.tu + 1; / 當前行的首個非零元素在三元組中的位置為此行前所有非零元素+1 if (arow M.mu) tp = M.rposarow + 1; else tp = M.tu + 1; for (p = M.rposarow; p tp; p+) / 對當前行每個非零元素進行操作 brow = M.datap.j; / 在N中找到i值也操作元素的j值相等的行 if (brow N.mu) t = N.rposbrow + 1; else t = N.tu + 1; for (q = N.rposbrow; q t; q+) / 對找出的行當每個非零元素進行操作 ccol = N.dataq.j; ctempccol += M.datap.e * N.dataq.e; / 將乘得到對應值放在相應的元素累加器里面 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(CrossList & 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.rheadx = p; else for (q = M.rheadx; (q-right) & (q-right-j right); / 查找節(jié)點在行表中的插入位置 p-righ