1、大學數據結構課程設計報告題目：稀疏矩陣實現與應用院（系）：計算機工程學院 學生姓名: 班級： 學號:起迄日期: 2011.6.20-2011.6.29指導教師: 指導教師評語： 成績： 簽名： 年 月 日20102011年度 第 2 學期 一、需求分析 1.問題描述：要求：實現三元組，十字鏈表下的稀疏矩陣的加、轉、乘的實現。 2.基本功能 實現三元組，十字鏈表下的轉置，乘法，加法運算。 3.輸入輸出 （1）設計函數建立稀疏矩陣，初始化值。（2）設計函數輸出稀疏矩陣的值。（3）構造函數進行兩個稀疏矩陣相加，輸出最終的稀疏矩陣。（4）構造函數進行兩個稀疏矩陣的相乘，輸出最終的稀疏矩陣。（5）構造函

2、數進行稀疏矩陣的轉置，并輸出結果。（6）退出系統。二、 概要設計1.設計思路：本實驗要求在三元組，十字鏈表下實現稀疏矩陣的加、轉、乘。首先要進行矩陣的初始化操作，定義三元組和十字鏈表的元素對象。寫出轉置，加法，乘法的操作函數。通過主函數調用實現在一個程序下進行矩陣的運算操作。 2.數據結構設計：抽象數據類型稀疏矩陣的定義如下：ADT SparseMatrix       數據對象：D=aij | i=1,2,m; j=1,2,.,n;aijElemset, m和n分別稱為矩陣的行數和列數。 數據關系：R=Row,Col

3、60;       Row=<ai,j , ai,j+1> | 1<=i<=m, 1<=j<=n-1 Col= <ai,j , ai+1,j> | 1<=i<=m-1, 1<=j<=n基本操作：      CreateSMatrix(&M)；         操作結果：創建稀疏矩陣M。  

4、    DestroySMatrix(&M)；         初始條件：稀疏矩陣M存在。 操作結果：銷毀稀疏矩陣M。      PrintSMatrix(M)；         初始條件：稀疏矩陣M存在。 操作結果：輸出稀疏矩陣M。      AddSMatrix(M，

5、N，&Q)；         初始條件：稀疏矩陣M與N的行數和列數對應相等 操作結果：求稀疏矩陣的和Q=M+N。      MultSMatrix(M，N，Q)；         初始條件：稀疏矩陣M的列數等于N的行數。 操作結果：求稀疏矩陣乘積Q=M*N。     TransposeSMatrix(M，T)；  

6、60;      初始條件：稀疏矩陣M存在。 操作結果：求稀疏矩陣M的轉置矩陣T。      ADT SparseMatrix 3.軟件結構設計：（1）主程序模塊：Void main（）初始化；do 接受命令；處理命令；while（“命令”=“退出”）；（2）稀疏矩陣模塊實現矩陣的相加bool AddSMatrix()；實現矩陣的相乘bool MultSMatrix()；實驗矩陣的轉置bool TransposeSMatrix()；（3）十字鏈表模塊 創建十字鏈表bool CreateSMatr

7、ix_OL(CrossList & M)； 輸出十字鏈表bool OutPutSMatrix_OL(CrossList T)；(4) 主程序模塊 稀疏矩陣模塊 十字鏈表模塊三、 詳細設計 1. 定義程序中所有用到的數據及其數據結構，及其基本操作的實現；typedef struct int i, j; int e; Triple; / 定義三元組的元素typedef struct Triple dataMAXSIZE + 1; int mu, nu, tu; TSMatrix; / 定義普通三元組對象typedef struct Triple dataMAXSIZE + 2; int r

8、posMAXROW + 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; / 系數矩陣的行數，列數，和非零元素個數 CrossList; / 定義十字鏈表對象結構體2主函數int

9、 main() int t; cout.fill('*'); cout << setw(80) << '*' cout.fill(' '); cout << setw(50) << "*歡迎使用矩陣運算程序*" << endl; /輸出頭菜單 cout.fill('*'); cout << setw(80) << '*' cout.fill(' '); cout << " 請

10、選擇要進行的操作：" << endl; cout << " 1:矩陣的轉置。" << endl; cout << " 2:矩陣的加法。" << endl; cout << " 3:矩陣的乘法。" << endl; cout << " 4:退出程序。" << endl;while(t)cout<<"請輸入您要進行的操作："<<endl;cin>>

11、t;switch(t)case 1:TransposeSMatrix(); /調用矩陣轉置函數break;case 2:AddSMatrix(); /調用矩陣相加函數break;case 3: MultSMatrix(); /調用矩陣相乘函數break;case 4:t=0;break;return 0;矩陣的轉置函數bool TransposeSMatrix() / 求矩陣的轉置矩陣 TSMatrix M, T; /定義預轉置的矩陣 InPutTSMatrix(M, 0); /輸入矩陣 int numMAXROW + 1; int cpotMAXROW + 1; / 構建輔助數組 int q

12、, 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; / 求出每一列中非零元素在三元組中出現的位置 for (p = 1; p <= M.tu; p+) int col = M.datap.

13、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 &

14、lt;= T.tu; col+) +numT.datacol.i; T.rpos1 = 1; for (int i = 2; i <= T.mu; i+) T.rposi = T.rposi - 1 + numi - 1; / 求取每一行中非零元素在三元組中出現的位置 return true;矩陣的乘法函數bool MultSMatrix() / 兩個矩陣相乘 RLSMatrix M, N, Q; / 構建三個帶“鏈接信息”的三元組表示的數組 InPutTSMatrix(M, 1); / 用普通三元組形式輸入數組 InPutTSMatrix(N, 1); Count(M); Count(

15、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; / 輔助數組 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;

16、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

17、 = 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 <= Q.nu; ccol+) / 對已經求出的累加器中的值壓縮到Q中 if (ctempccol) if (+Q.tu > MAXSIZE) return false; Q.dataQ.tu.e = ctempccol; Q.dataQ.tu.i = arow

18、; Q.dataQ.tu.j = ccol; OutPutSMatrix(Q); return true;矩陣的加法函數bool AddSMatrix() /矩陣的加法 CrossList M, N; / 創建兩個十字鏈表對象，并初始化 CreateSMatrix_OL(M); CreateSMatrix_OL(N); cout << "輸入的兩矩陣的和矩陣為：" << endl; OLink pa, pb, pre, hlMAXROW + 1; /定義輔助指針，pa，pb分別為M,N當前比較的元素，pre為pa的前驅元素 for (int x =

19、1; x <= M.nu; x+) hlx = M.cheadx; for (int k = 1; k <= M.mu; k+) / 對M的每一行進行操作 pa = M.rheadk; pb = N.rheadk; pre = NULL; while (pb) / 把N中此行的每個元素取出 OLink p; if (!(p = (OLink) malloc(sizeof (OLNode) exit(0); / 開辟新節點，存儲N中取出的元素 p->e = pb->e; p->i = pb->i; p->j = pb->j; if (NULL =

20、pa | pa->j > pb->j) / 當M此行已經檢查完或者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-&

21、gt;right; else if (NULL != pa) && pa->j < pb->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，則刪除此節點，同時改變此元素坐在行，列的前驅元素的相應值 if (NULL = pre) / 修改行前驅元素值 M.rheadpa->

22、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;創建

23、十字鏈表bool CreateSMatrix_OL(CrossList & M)/ 創建十字鏈表 int x, y, m; cout << "請輸入矩陣的行，列，及非零元素個數" << endl; cin >> 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) e

24、xit(0); for (x = 0; x <= M.mu; x+) M.rheadx = NULL; / 初始化各行，列頭指針，分別為NULL for (x = 0; x <= M.nu; x+) M.cheadx = NULL; cout << "請按三元組的格式輸入數組：" << endl; for (int i = 1; i <= M.tu; i+) cin >> x >> y >> m; / 按任意順序輸入非零元，（普通三元組形式輸入） OLink p, q; if (!(p = (OL

25、ink) malloc(sizeof (OLNode) exit(0); / 開辟新節點，用來存儲輸入的新元素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

26、= 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 < x); q = q->down); / 查找節點在列表中的插入位置 p->down = q->down; q->down = p; / 完成列插入 return true;十字鏈表的輸出bo

27、ol OutPutSMatrix_OL(CrossList T)/ 輸出十字鏈表，用普通數組形式輸出 for (int i = 1; i <= T.mu; i+) OLink p = T.rheadi; for (int j = 1; j <= T.nu; j+) if (p) && (j = p->j) cout << setw(3) << p->e; p = p->right; else cout << setw(3) << "0" cout << endl; re

28、turn true;3.主要函數的程序流程圖，實現設計中主程序和其他子模塊的算法，以流程圖的形式表示。 矩陣的相加流程圖 矩陣的相乘流程圖 矩陣轉置的流程圖 主函數流程圖4. 畫出函數之間的調用關系圖。 Main AddSMatrix TransposeSMatrix MultSMatrix CreateSMatrix_OL InPutTSMatrix OutPutSMatrix InPutTSMatrix OutPutSMatrix_OL 四、 調試分析 1.實際完成的情況說明（完成的功能，支持的數據類型等）；完成了稀疏矩陣的建立，初始化及輸出值的操作。 實現三元組，十字鏈表下的稀疏矩陣的加

29、法，乘法以及轉置運算。2.程序的性能分析，包括時空分析；能應對一般小的錯誤輸入，如果復雜則自動退出程序3.上機過程中出現的問題及其解決方案； 1.起始有錯誤,設定的變量名相同。經檢查，改正。2一些邏輯錯誤。經討論改正。運行出現部分語法錯誤修正4.程序中可以改進的地方說明；程序在運行中一旦出現矩陣數據格式錯誤如輸入漢字，則程序自動退出。需要重新啟動。更新程序對更多錯誤輸入情況的分析能力。5.程序中可以擴充的功能及設計實現假想。對退出操作的擴充在主菜單下，用戶輸入4回車選擇退出程序是，詢問是否真的退出系統，如果是，則即退出系統，否則顯示continue并且返回主菜單。為了方便由于誤按導致程序退出。

30、在退出時可以增加一段感謝使用本程序的結束語。五、測試結果系統運行主界面輸入需要執行的操作1矩陣的轉置輸入需要執行的操作2矩陣的加法輸入需要執行的操作3矩陣的乘法輸入錯誤操作時需要重新選擇退出操作六、用戶手冊1.本程序執行文件為：crosslist.exe2進入本系統之后，隨即顯示系統主菜單界面。用戶可在該界面下輸入各子菜單前對應的數字并按回車，執行相應子菜單命令3執行操作時，按要求輸入數字。彼此之間用空格隔開。4執行加法運算時，輸入的兩個矩陣的行必須相同，列數也必須相同。這是基本的矩陣運算常識。5.執行乘法運算時，第一個矩陣的行數和第二個矩陣的列數相同。6.當輸入錯誤時請嘗試退出程序重新運行。

31、請盡量遵守矩陣運算的規則輸入有效的運算。七、體會與自我評價 我選的上機題目是實現三元組，十字鏈表下的轉置，乘法，加法運算。對這個題目，我覺得有點難，因為我們數據結構這一部分并沒有講，可是選題必須是每人選擇一個不許選重。有點無奈吧，當作是考驗了。各種資料收集，各種代碼整合。各種錯誤。雖然上機的時間只有短短兩個星期，但從中學到了不少知識。數據結構可以說是計算機里一門基礎課程，對于以后的學習尤為重要。所以我們一定要把基礎學扎實，這兩周的上機幫我們重新鞏固基礎知識，提高了我們專業的動手實踐能力。在實踐的過程中我們應當有良好的規劃，每天完成一小部分。盡量減少操作的盲目性，提高我們學習的效率。有個總體的大

32、綱來逐步實現。我也曾經犯過這種錯誤。每個函數都做出來部分。結果都沒做完。所以計劃很重要在實驗中我們要培養自己獨立的思考能力和解決問題的能力。培養這種能力主要看我們對待這次實驗的態度。我們要把它當作以后工作時接的項目一樣認真對待。積極的朝著更好地一面發展不斷的完善程序。不能馬馬虎虎隨便應付一下。 通過這次實驗我也認識到了數據結構這門課程的重要性，以及C語言功能的強大。它可以令計算機執行各種你想要的操作。當然前提是你的技術水平。使我深刻的認識到要學好數據結構這門課程，為了以后打好堅實的基礎。提高自己的動手實踐能力，把所學的理論知識和實踐相結合。就像古人云，紙上得來終覺淺，得知此事要躬行。為了以后的

33、計算機道路。不斷的提高自身的專業素養。奮斗。 也希望在今后的學習生活中向老師學到更多的知識。不斷的充實自己。努力改正自己的壞毛病，做個奮發向上的大學生。源代碼：#include <iostream>#include <iomanip>using namespace std;const int MAXSIZE = 100; / 定義非零元素的對多個數const int MAXROW = 10; / 定義數組的行數的最大值 typedef struct int i, j; int e; Triple; / 定義三元組的元素typedef struct Triple data

34、MAXSIZE + 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 / 定義十字鏈表對象

35、結構體 OLink *rhead, *chead; int mu, nu, tu; / 系數矩陣的行數，列數，和非零元素個數 CrossList; / 定義十字鏈表對象結構體template <class P>bool InPutTSMatrix(P & T, int y) /輸入矩陣，按三元組格式輸入 cout << "輸入矩陣的行，列和非零元素個數:" << endl; cin >> T.mu >> T.nu >> T.tu; cout << "請輸出非零元素的位置和值

36、:" << endl; for (int k = 1; k <= T.tu; k+) cin >> T.datak.i >> T.datak.j >> T.datak.e; return true;template <class P>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 -

37、 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; / 構建輔助數組 int q, p, t; T.tu = M

38、.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; / 求出每一列中非零元素在三元組中出現的位置 for (p = 1; p <= M.tu; p+) int col = M.datap.j; q = cpotcol;

39、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+)

40、 +numT.datacol.i; T.rpos1 = 1; for (int i = 2; i <= T.mu; i+) T.rposi = T.rposi - 1 + numi - 1; / 求取每一行中非零元素在三元組中出現的位置 return true;bool MultSMatrix() / 兩個矩陣相乘 RLSMatrix M, N, Q; / 構建三個帶“鏈接信息”的三元組表示的數組 InPutTSMatrix(M, 1); / 用普通三元組形式輸入數組 InPutTSMatrix(N, 1); Count(M); Count(N); cout << "

41、;輸入的兩矩陣的乘矩陣為：" << endl; if (M.nu != N.mu) return false; Q.mu = M.mu; Q.nu = N.nu; Q.tu = 0; / Q初始化 int ctempMAXROW + 1; / 輔助數組 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+) / 當前行

42、各元素累加器清零 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

43、.rposbrow; q < t; q+) / 對找出的行當每個非零元素進行操作 ccol = N.dataq.j; ctempccol += M.datap.e * N.dataq.e; / 將乘得到對應值放在相應的元素累加器里面 for (ccol = 1; ccol <= Q.nu; ccol+) / 對已經求出的累加器中的值壓縮到Q中 if (ctempccol) if (+Q.tu > MAXSIZE) return false; Q.dataQ.tu.e = ctempccol; Q.dataQ.tu.i = arow; Q.dataQ.tu.j = ccol;

44、OutPutSMatrix(Q); return true;bool CreateSMatrix_OL(CrossList & M)/ 創建十字鏈表 int x, y, m; cout << "請輸入矩陣的行，列，及非零元素個數" << endl; cin >> M.mu >> M.nu >> M.tu; if (!(M.rhead = (OLink*) malloc(M.mu + 1) * sizeof (OLink) exit(0); if (!(M.chead = (OLink*) malloc(M.

45、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 << "請按三元組的格式輸入數組：" << endl; for (int i = 1; i <= M.tu; i+) cin >> x >> y >> m; / 按任意順序輸入非零元，（普通三元組形式輸入）

46、 OLink p, q; if (!(p = (OLink) malloc(sizeof (OLNode) exit(0); / 開辟新節點，用來存儲輸入的新元素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 > x) p->down = M.cheady; M.che