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

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

3、設計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 rposMAXROW + 1； int mu, nu, tu; RLSMatrix; / 定義帶鏈接信息的三元組對象typedef struct OLNode / 定義十字鏈表元素 int i,

4、 j; int e; struct OLNode *right, *down; / 該非零元所在行表和列表的后繼元素 OLNode, *OLink; / 定義十字鏈表元素typedef struct / 定義十字鏈表對象結構體 OLink *rhead, *chead; int mu, nu, tu; / 系數矩陣的行數，列數，和非零元素個數 CrossList; / 定義十字鏈表對象結構體2主函數int main() int t; cout.fill('*'); cout << setw(80) << '*' cout.fill(

5、9; '); cout << setw(50) << "*歡迎使用矩陣運算程序*" << endl; /輸出頭菜單 cout.fill('*'); cout << setw(80) << '*' cout.fill(' '); cout << " 請選擇要進行的操作：" << endl; cout << " 1:矩陣的轉置。" << endl; cout <<

6、" 2:矩陣的加法。" << endl; cout << " 3:矩陣的乘法。" << endl; cout << " 4:退出程序。" << endl;while(t)cout<<"請輸入您要進行的操作："<<endl;cin>>t;switch(t)case 1:TransposeSMatrix(); /調用矩陣轉置函數break;case 2:AddSMatrix(); /調用矩陣相加函數break;case 3:

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

8、 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; T.dataq.i = M.datap.j; T.dataq.j = M.datap.i; T.dataq.e = M.datap.e; +cpotcol; c

9、out << "輸入矩陣的轉置矩陣為" << 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.rpo

10、si - 1 + numi - 1; / 求取每一行中非零元素在三元組中出現的位置 return true;矩陣的乘法函數bool MultSMatrix() / 兩個矩陣相乘 RLSMatrix M, N, Q; / 構建三個帶“鏈接信息”的三元組表示的數組 InPutTSMatrix(M, 1); / 用普通三元組形式輸入數組 InPutTSMatrix(N, 1); Count(M); Count(N); cout << "輸入的兩矩陣的乘矩陣為：" << endl; if (M.nu != N.mu) return false; Q.mu =

11、 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+) / 當前行各元素累加器清零 ctempx = 0; Q.rposarow = Q.tu + 1; / 當前行的首個非零元素在三元組中的位置為此行前所有非零元

12、素+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 +

13、= 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; OutPutSMatrix(Q); return true;矩陣的加法函數bool AddSMatrix() /矩陣的加法 CrossList M

14、, N; / 創建兩個十字鏈表對象，并初始化 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 <= M.mu; k+) / 對M的每一行進行操作 pa = M.rhead

15、k; 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 = pa | pa->j > pb->j) / 當M此行已經檢查完或者pb因該放在pa前面 if (NULL = pre) M.rheadp->i = p; else pr

16、e->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 < pb->j) / 如果此時的pb元素因該放在pa后面，則取以后的pa再來比

17、較 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->i = pa->right; else pre->right = pa->right; p = pa; pa = pa->right; if (M.cheadp->

18、;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;創建十字鏈表bool CreateSMatrix_OL(CrossList & M)/ 創建十字鏈表 int x, y, m; cout << "請輸入矩陣的行，列，

19、及非零元素個數" << 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) exit(0); for (x = 0; x <= M.mu; x+) M.rheadx = NULL; / 初始化各行，列頭指針，分別為NULL for (x = 0; x <=

20、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 = (OLink) malloc(sizeof (OLNode) exit(0); / 開辟新節點，用來存儲輸入的新元素p->i = x; p->j = y; p->e = m; if

21、 (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

22、= 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;十字鏈表的輸出bool OutPutSMatrix_OL(CrossList T)/ 輸出十字鏈表，用普通數組形式輸出 for (int i = 1; i <= T.mu; i+) OLink p = T

23、.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; return true;3.1、程序中所采用的數據結構的說明ADT SparseMatrix       數據對象：D=aij | i=

24、1,2,m; j=1,2,.,n;aijElemset, m和n分別稱為矩陣的行數和列數。 數據關系：R=Row,Col        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)；  

25、;       操作結果：創建稀疏矩陣M。      DestroySMatrix(&M)；         初始條件：稀疏矩陣M存在。 操作結果：銷毀稀疏矩陣M。      PrintSMatrix(M)；         初始條件：稀疏矩

26、陣M存在。 操作結果：輸出稀疏矩陣M。      AddSMatrix(M，N，&Q)；         初始條件：稀疏矩陣M與N的行數和列數對應相等 操作結果：求稀疏矩陣的和Q=M+N。      MultSMatrix(M，N，Q)；         初始條件：稀疏矩陣M的列數等于N的行數。 操作結果：求稀

27、疏矩陣乘積Q=M*N。     TransposeSMatrix(M，T)；         初始條件：稀疏矩陣M存在。 操作結果：求稀疏矩陣M的轉置矩陣T。     ADT SparseMatrix3.2、算法的設計思想本實驗要求在三元組，十字鏈表下實現稀疏 矩陣的加、轉、乘。首先要進行矩陣的初始化操作，定義三元組和十字鏈表的元素對象。寫出轉置，加法，乘法的操作函數。通過主函數調用實現在一個程序下進行矩陣的運算操作。3.3、稀疏矩陣各種運算的性

28、質變換a)加法運算兩個稀疏矩陣的加和矩陣仍然是稀疏矩陣b）乘法運算兩個稀疏矩陣的乘積矩陣不是稀疏矩陣c）轉置運算一個稀疏矩陣的轉置矩陣仍然是稀疏矩陣4、調試與測試：4.1、調試方法與步驟：1. 實際完成的情況說明（完成的功能，支持的數據類型等）； 完成了稀疏矩陣的建立，初始化及輸出值的操作。 實現三元組，十字鏈表下的稀疏矩陣的加法，乘法以及轉置運算。2.程序的性能分析，包括時空分析；能應對一般小的錯誤輸入，如果復雜則自動退出程序。3.上機過程中出現的問題及其解決方案； 1.起始有錯誤,設定的變量名相同。經檢查，改正。2一些邏輯錯誤。經討論改正。運行出現部分語法錯誤修正4.程序中可以改進的地方說

29、明；程序在運行中一旦出現矩陣數據格式錯誤如輸入漢字，則程序自動退出。需要重新啟動。更新程序對更多錯誤輸入情況的分析能力。5.程序中可以擴充的功能及設計實現假想。對退出操作的擴充在主菜單下，用戶輸入4回車選擇退出程序是，詢問是否真的退出系統，如果是，則即退出系統，否則顯示continue并且返回主菜單。為了方便由于誤按導致程序退出。在退出時可以增加一段感謝使用本程序的結束語。4.2、測試結果的分析與討論：系統運行主界面輸入需要執行的操作1矩陣的轉置輸入需要執行的操作2矩陣的加法輸入需要執行的操作3矩陣的乘法輸入錯誤操作時需要重新選擇退出操作5、時間復雜度的分析：a)加法運算由于兩矩陣行列相等，故

30、時間復雜度為O（行*列）b）乘法運算設M是m1*n1矩陣，N是m2*n2矩陣，則時間復雜度是O（m1*n1*n2）c）轉置運算時間復雜度和原矩陣的列數及非零元的個數的乘積成正比，即O（mu*nu）6、 源程序清單和執行結果#include <iostream>#include <iomanip>using namespace std;const int MAXSIZE = 100; / 定義非零元素的對多個數const int MAXROW = 10; / 定義數組的行數的最大值 typedef struct int i, j; int e; Triple; / 定義三

31、元組的元素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; / 定義

32、十字鏈表元素typedef struct / 定義十字鏈表對象結構體 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; c

33、out << "請輸出非零元素的位置和值:" << 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 -

34、 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;

35、 / 構建輔助數組 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; / 求出每一列中非零元素在三元組中出現的位置 for (p = 1; p <= M.tu; p+) int

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

37、 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; / 求取每一行中非零元素在三元組中出現的位置 return true;bool MultSMatrix() / 兩個矩陣相乘 RLSMatrix M, N, Q; / 構建三個帶“鏈接信息”的三元組表示的數組 InPutTSMatrix(M, 1); / 用普通三元組形式輸入數組 InPutTSMatrix(N, 1); Count(M)

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

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

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

41、i = arow; Q.dataQ.tu.j = ccol; 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

42、(!(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 << "請按三元組的格式輸入數組：" << endl; for (int i = 1; i <= M.tu; i+) cin >> x >> y >&

43、gt; m; / 按任意順序輸入非零元，（普通三元組形式輸入） 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.