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

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數(shù)：22 大?。?54.50KB 人氣指數(shù)：12 舉報 版權(quán)申訴

已閱讀1頁，還剩21頁未讀，繼續(xù)免費(fèi)閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

1、　　課程設(shè)計報告　　課程名稱《數(shù)據(jù)結(jié)構(gòu)》 　　課題名稱稀疏矩陣實(shí)現(xiàn)與應(yīng)用 　　專業(yè) 計算機(jī)科學(xué)與技術(shù) 　　班級

2、　　學(xué)號　　姓名 　　聯(lián)系方式 　　指導(dǎo)教師　　20 11 年 12 月 25 日　　目

3、錄　　1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計任務(wù)書１　　1.1、題目-------------------------------------------------------------------------------------------------１　　1.2、要求--------------

4、-----------------------------------------------------------------------------------１　　2、總體設(shè)計 -------------------------------------------------------------------------------------------------１</p&g

5、t;　　2.1、功能模塊設(shè)計--------------------------------------------------------------------------------------1　　2.2、所有功能模塊的流程圖-----------------------------------------------------------------------

6、---2　　3、詳細(xì)設(shè)計----------------------------------------------------------------------------------------------------3　　3.1、程序中所采用的數(shù)據(jù)結(jié)構(gòu)及存儲結(jié)構(gòu)的說明----------------------------------------

7、-----10　　3.2、算法的設(shè)計思想----------------------------------------------------------------------------------10　　3.3、稀疏矩陣各種運(yùn)算的性質(zhì)變換-------------------------------------------------------

8、---------10　　4、調(diào)試與測試：--------------------------------------------------------------------------------------------10　　4.1、調(diào)試方法與步驟： ------------------------------------------------

9、-----------------------------10　　4.2、測試結(jié)果的分析與討論：----------------------------------------------------------------------11　　5、時間復(fù)雜度的分析：---------------------------------------------

10、--------------------------------------12　　6、源程序清單和執(zhí)行結(jié)果--------------------------------------------------------------------------------12　　7、C程序設(shè)計總結(jié)-------------------------------

11、----------------------------------------------------------20　　8、致謝--------------------------------------------------------------------------------------------------------20　　9、參考

12、文獻(xiàn)--------------------------------------------------------------------------------------------------20　　1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計任務(wù)書　　1.1、題目　　實(shí)現(xiàn)三元組，十字鏈表下

13、的稀疏矩陣的加、轉(zhuǎn)、乘的實(shí)現(xiàn)。　　1.2、要求　　(1).設(shè)計函數(shù)建立稀疏矩陣，初始化值；　　(2).設(shè)計函數(shù)輸出稀疏矩陣的值；　　(3).構(gòu)造函數(shù)進(jìn)行兩個稀疏矩陣相加，輸出最終的稀疏矩陣；

14、　(4).構(gòu)造函數(shù)進(jìn)行兩個稀疏矩陣相減，輸出最終的稀疏矩陣；　　(5).構(gòu)造函數(shù)進(jìn)行稀疏矩陣的轉(zhuǎn)置，并輸出結(jié)果；　　(6).退出系統(tǒng)。　　2、總體設(shè)計　　2.1、功能模塊設(shè)計

15、　　2.2、所有功能模塊的流程圖　　3、詳細(xì)設(shè)計　　1. 定義程序中所有用到的數(shù)據(jù)及其數(shù)據(jù)結(jié)構(gòu)，及其基本操作的實(shí)現(xiàn)；　　typedef struct {　　int i, j;&

16、lt;/p>　　int e;　　} Triple; // 定義三元組的元素　　typedef struct {　　Triple data[MAXSIZE + 1];　　int mu, nu, tu;<

17、/p>　　} TSMatrix; // 定義普通三元組對象　　typedef struct {　　Triple data[MAXSIZE + 2];　　int rpos[MAXROW + 1]；　　int mu, nu, tu;</p&g

18、t;　　} RLSMatrix; // 定義帶鏈接信息的三元組對象　　typedef struct OLNode { // 定義十字鏈表元素　　int i, j;　　int e;<p&g

19、t;　　struct OLNode *right, *down; // 該非零元所在行表和列表的后繼元素　　} OLNode, *OLink; // 定義十字鏈表元素　　typedef struct { // 定義十字鏈表對象結(jié)構(gòu)體　　OLink *rhead, *chead;<

20、;p>　　int mu, nu, tu; // 系數(shù)矩陣的行數(shù)，列數(shù)，和非零元素個數(shù)　　} CrossList; // 定義十字鏈表對象結(jié)構(gòu)體　　2．主函數(shù)　　int main()　　{</b&

21、gt;　　int t;　　cout.fill('*');　　cout << setw(80) << '*';　　cout.fill(' ');

22、　　cout << setw(50) << "***歡迎使用矩陣運(yùn)算程序***" << endl; //輸出頭菜單　　cout.fill('*');　　cout << setw(80) << '*';

23、　　cout.fill(' ');　　cout << " 請選擇要進(jìn)行的操作：" << endl;　　cout << " 1:矩陣的轉(zhuǎn)置。" <&

24、lt; endl;　　cout << " 2:矩陣的加法。" << endl;　　cout << " 3:矩陣的乘法。" << endl;<p&g

25、t;　　cout << " 4:退出程序。" << endl;　　while(t)　　{　　cout<<"請輸入您要進(jìn)行的操作

26、："<<endl;　　cin>>t;　　switch(t)　　{　　case 1:&l

27、t;/p>　　TransposeSMatrix(); //調(diào)用矩陣轉(zhuǎn)置函數(shù)　　break;　　case 2:　　AddSMatrix(); //調(diào)用矩陣相加函數(shù)<

28、b>　　break;　　case 3: 　　MultSMatrix(); //調(diào)用矩陣相乘函數(shù)　　break;　　case 4:&l

29、t;/p>　　t=0;　　break;　　}　　}　　return 0;&

30、lt;/b>　　}　　矩陣的轉(zhuǎn)置函數(shù)　　bool TransposeSMatrix() // 求矩陣的轉(zhuǎn)置矩陣　　{<p&

31、gt;　　TSMatrix M, T; //定義預(yù)轉(zhuǎn)置的矩陣　　InPutTSMatrix(M, 0); //輸入矩陣　　int num[MAXROW + 1];　　int cpot[MAXROW + 1]; // 構(gòu)建輔助數(shù)組　　int q, p, t;</p

32、>　　T.tu = M.tu;　　T.mu = M.nu;　　T.nu = M.mu;　　if (T.tu) 　　{　　for (int col = 1; col

33、<= M.nu; col++) num[col] = 0;　　for (t = 1; t <= M.tu; t++) ++num[M.data[t].j];　　cpot[1] = 1;　　for (int i = 2; i <= M.nu; i++) cpot[i] = cpot[i - 1]

34、+ num[i - 1]; // 求出每一列中非零元素在三元組中出現(xiàn)的位置　　for (p = 1; p <= M.tu; p++) 　　{　　int col = M.data[p].j;　　q = cpot[col];&l

35、t;/p>　　T.data[q].i = M.data[p].j;　　T.data[q].j = M.data[p].i;　　T.data[q].e = M.data[p].e;　　++cpot[col];　　}</b&

36、gt;　　}　　cout << "輸入矩陣的轉(zhuǎn)置矩陣為" << endl;　　OutPutSMatrix(T);　　return true;<

37、b>　　}　　bool Count(RLSMatrix &T) {　　int num[MAXROW + 1];　　for (int row = 1; row <= T.mu; row++) num[row] = 0;　　for (i

38、nt col = 1; col <= T.tu; col++) ++num[T.data[col].i];　　T.rpos[1] = 1;　　for (int i = 2; i <= T.mu; i++) T.rpos[i] = T.rpos[i - 1] + num[i - 1]; // 求取每一行中非零元素在三元組中出現(xiàn)的位置</p

39、>　　return true;　　}　　矩陣的乘法函數(shù)　　bool MultSMatrix() // 兩個矩陣相乘　　{</

40、p>　　RLSMatrix M, N, Q; // 構(gòu)建三個帶“鏈接信息”的三元組表示的數(shù)組　　InPutTSMatrix(M, 1); // 用普通三元組形式輸入數(shù)組　　InPutTSMatrix(N, 1);　　Count(M);</p

41、>　　Count(N);　　cout << "輸入的兩矩陣的乘矩陣為：" << endl;　　if (M.nu != N.mu) return false;　　Q.mu = M.mu;

42、　　Q.nu = N.nu;　　Q.tu = 0; // Q初始化　　int ctemp[MAXROW + 1]; // 輔助數(shù)組　　int arow, tp, p, brow, t, q, ccol;　　if (M.tu * N.tu

43、) // Q是非零矩陣　　{　　for (arow = 1; arow <= M.mu; arow++) 　　{　　///memset(ctemp,0,N.nu);

44、　　for (int x = 1; x <= N.nu; x++) // 當(dāng)前行各元素累加器清零　　ctemp[x] = 0;　　Q.rpos[arow] = Q.tu + 1; // 當(dāng)前行的首個非零元素在三元組中的位置為此行前所有非零元素+1　　if (arow < M.mu)

45、 tp = M.rpos[arow + 1];　　else tp = M.tu + 1;　　for (p = M.rpos[arow]; p < tp; p++) // 對當(dāng)前行每個非零元素進(jìn)行操作　　{ 　　brow =

46、M.data[p].j; // 在N中找到i值也操作元素的j值相等的行　　if (brow < N.mu) t = N.rpos[brow + 1];　　else t = N.tu + 1;　　for (q = N.rpos[brow]; q < t; q++) // 對找出的行當(dāng)每個非零元素進(jìn)行

47、操作　　{ 　　ccol = N.data[q].j;　　ctemp[ccol] += M.data[p].e * N.data[q].e; // 將乘得到對應(yīng)值放在相應(yīng)的元素累加器里面　　}

48、;　　}　　for (ccol = 1; ccol <= Q.nu; ccol++) // 對已經(jīng)求出的累加器中的值壓縮到Q中　　if (ctemp[ccol]) 　　{</p&g

49、t;　　if (++Q.tu > MAXSIZE) return false;　　Q.data[Q.tu].e = ctemp[ccol];　　Q.data[Q.tu].i = arow;　　Q.data[Q.tu].j = ccol;<

50、b>　　}　　}　　}　　OutPutSMatrix(Q);　　return true;　　}</b&g

51、t;　　矩陣的加法函數(shù)　　bool AddSMatrix() //矩陣的加法　　{　　CrossList M, N; // 創(chuàng)建兩個十字鏈表對象，并初始化

52、;　　CreateSMatrix_OL(M);　　CreateSMatrix_OL(N);　　cout << "輸入的兩矩陣的和矩陣為：" << endl;　　OLink pa, pb, pre, hl[MAXROW + 1]; //定義輔助指針，pa，pb分別為M,N

53、當(dāng)前比較的元素，pre為pa的前驅(qū)元素　　for (int x = 1; x <= M.nu; x++) hl[x] = M.chead[x];　　for (int k = 1; k <= M.mu; k++) // 對M的每一行進(jìn)行操作　　{

54、;　　pa = M.rhead[k];　　pb = N.rhead[k];　　pre = NULL;　　while (pb) // 把N中此行的每個元素取出　　{ <

55、;b>　　OLink p;　　if (!(p = (OLink) malloc(sizeof (OLNode)))) exit(0); // 開辟新節(jié)點(diǎn)，存儲N中取出的元素　　p->e = pb->e;　　p->i = pb->i;<

56、;p>　　p->j = pb->j;　　if (NULL == pa || pa->j > pb->j) // 當(dāng)M此行已經(jīng)檢查完或者pb因該放在pa前面　　{ 　　if (NULL == pre)

57、;　　M.rhead[p->i] = p;　　else　　pre->right = p;　　p->right = pa;　　pre = p;<p&g

58、t;　　if (NULL == M.chead[p->j]) // 進(jìn)行列插入　　{　　M.chead[p->j] = p;　　p->down = NULL;　　} </

59、p>　　else 　　{　　p->down = hl[p->j]->down;　　hl[p->j]->down = p;

60、　　}　　hl[p->j] = p;　　pb = pb->right;　　} 　　else　　if ((NULL != p

61、a) && pa->j < pb->j) // 如果此時的pb元素因該放在pa后面，則取以后的pa再來比較　　{ 　　pre = pa;　　pa = pa->right;&

62、lt;p>　　} 　　else　　if (pa->j == pb->j) // 如果pa，pb位于同一個位置上，則將值相加　　{ 　　pa-

63、>e += pb->e;　　if (!pa->e) 　　{ // 如果相加后的和為0，則刪除此節(jié)點(diǎn)，同時改變此元素坐在行，列的前驅(qū)元素的相應(yīng)值　　if (NULL == pre) // 修改行前驅(qū)元素值　　M.rhead[pa->i] = pa-&

64、gt;right;　　else　　pre->right = pa->right;　　p = pa;　　pa = pa->right;

65、if (M.chead[p->j] == p) M.chead[p->j] = hl[p->j] = p->down; // 修改列前驅(qū)元素值　　else　　hl[p->j]->down = p->down;　　fr

66、ee(p);　　pb = pb->right;　　} 　　else 　　{　　pa = p

67、a->right;　　pb = pb->right;　　}　　}　　}　　}</

68、b>　　OutPutSMatrix_OL(M);　　return true;　　}　　創(chuàng)建十字鏈表　　bool CreateSMatrix_OL(C

69、rossList & M)// 創(chuàng)建十字鏈表　　{　　int x, y, m;　　cout << "請輸入矩陣的行，列，及非零元素個數(shù)" << endl;　　cin >&g

70、t; 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

71、(0);　　for (x = 0; x <= M.mu; x++)　　M.rhead[x] = NULL; // 初始化各行，列頭指針，分別為NULL　　for (x = 0; x <= M.nu; x++)　　M.chead[x] = NULL;</p

72、>　　cout << "請按三元組的格式輸入數(shù)組：" << endl;　　for (int i = 1; i <= M.tu; i++) 　　{　　cin >> x >> y

73、 >> m; // 按任意順序輸入非零元，（普通三元組形式輸入）　　OLink p, q;　　if (!(p = (OLink) malloc(sizeof (OLNode)))) exit(0); // 開辟新節(jié)點(diǎn)，用來存儲輸入的新元素　　p->i = x;</b&g

74、t;　　p->j = y;　　p->e = m;　　if (M.rhead[x] == NULL || M.rhead[x]->j > y) 　　{<

75、;/b>　　p->right = M.rhead[x];　　M.rhead[x] = p;　　} 　　else 　　{<

76、;/b>　　for (q = M.rhead[x]; (q->right) && (q->right->j < y); q = q->right); // 查找節(jié)點(diǎn)在行表中的插入位置　　p->right = q->right;　　q->ri

77、ght = p; // 完成行插入　　}　　if (M.chead[y] == NULL || M.chead[y]->i > x) 　　{　　p->down = M.che

78、ad[y];　　M.chead[y] = p;　　}　　else　　{　　for (q = M.chead[y];

79、(q->down) && (q->down->i < x); q = q->down); // 查找節(jié)點(diǎn)在列表中的插入位置　　p->down = q->down;　　q->down = p; // 完成列插入　　}</b&g

80、t;　　}　　return true;　　}　　十字鏈表的輸出　　bool OutPutSMatrix_OL(Cro

81、ssList T)// 輸出十字鏈表，用普通數(shù)組形式輸出　　{ 　　for (int i = 1; i <= T.mu; i++) 　　{　　OLink p = T.rhead[i];&l

82、t;/p>　　for (int j = 1; j <= T.nu; j++) 　　{　　if ((p) && (j == p->j))　　{

83、　　cout << setw(3) << p->e;　　p = p->right;　　} else　　cout << setw(3) << "0";<

84、;b>　　}　　cout << endl;　　}　　return true;　　}　　3.1、程序中所采用的數(shù)據(jù)結(jié)構(gòu)

85、的說明　　ADT SparseMatrix{ 數(shù)據(jù)對象：D={aij | i=1,2,…,m; j=1,2,..,n;　　aij∈Elemset, m和n分別稱為矩陣的行數(shù)和列數(shù)。} 數(shù)據(jù)關(guān)系：R={Row,Col} &#

86、160; 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}基本操作： CreateSMatr

87、ix(&M)；操作結(jié)果：創(chuàng)建稀疏矩陣M。 DestroySMatrix(&M)；初始條件：稀疏矩陣M存在。操作結(jié)果：銷毀稀疏矩陣M。 &#

88、160; PrintSMatrix(M)；初始條件：稀疏矩陣M存在。操作結(jié)果：輸出稀疏矩陣M。 AddSMatrix(M，N，&Q)； &

89、#160; 初始條件：稀疏矩陣M與N的行數(shù)和列數(shù)對應(yīng)相等操作結(jié)果：求稀疏矩陣的和Q=M+N。 MultSMatrix(M，N，＆Q)；初始條件：稀疏矩陣M的列數(shù)等于N的行數(shù)。操作結(jié)果：求稀疏矩陣乘積Q=M*N。 &#

90、160;TransposeSMatrix(M，＆T)；初始條件：稀疏矩陣M存在。操作結(jié)果：求稀疏矩陣M的轉(zhuǎn)置矩陣T。 }ADT SparseMatrix　　3.2、算法的設(shè)計思想　　本實(shí)驗(yàn)要求在三元組，十字鏈表下

91、實(shí)現(xiàn)稀疏矩陣的加、轉(zhuǎn)、乘。首先要進(jìn)行矩陣的初始化操作，定義三元組和十字鏈表的元素對象。寫出轉(zhuǎn)置，加法，乘法的操作函數(shù)。通過主函數(shù)調(diào)用實(shí)現(xiàn)在一個程序下進(jìn)行矩陣的運(yùn)算操作。　　3.3、稀疏矩陣各種運(yùn)算的性質(zhì)變換　　a)加法運(yùn)算　　兩個稀疏矩陣的加和矩陣仍然是稀疏矩陣</p

92、>　　b）乘法運(yùn)算　　兩個稀疏矩陣的乘積矩陣不是稀疏矩陣　　c）轉(zhuǎn)置運(yùn)算　　一個稀疏矩陣的轉(zhuǎn)置矩陣仍然是稀疏矩陣　　4、調(diào)試與測試：

93、;　　4.1、調(diào)試方法與步驟：　　實(shí)際完成的情況說明（完成的功能，支持的數(shù)據(jù)類型等）；　　完成了稀疏矩陣的建立，初始化及輸出值的操作。　　實(shí)現(xiàn)三元組，十字鏈表下的稀疏矩陣的加法，乘法以及轉(zhuǎn)置運(yùn)算。　　2.程序的性能分析，包括時空分

94、析；　　能應(yīng)對一般小的錯誤輸入，如果復(fù)雜則自動退出程序。　　3.上機(jī)過程中出現(xiàn)的問題及其解決方案；　　1.起始有錯誤,設(shè)定的變量名相同。經(jīng)檢查，改正。　　2．一些邏輯錯誤。經(jīng)討論改正。運(yùn)行出現(xiàn)部分語法錯誤修正　　4.程序中可以改進(jìn)

95、的地方說明；　　程序在運(yùn)行中一旦出現(xiàn)矩陣數(shù)據(jù)格式錯誤如輸入漢字，則程序自動退出。需要重新啟動。更新程序?qū)Ω噱e誤輸入情況的分析能力。　　5.程序中可以擴(kuò)充的功能及設(shè)計實(shí)現(xiàn)假想。　　對退出操作的擴(kuò)充　　在主菜單下，用戶輸入4回車選擇退出

96、程序是，詢問是否真的退出系統(tǒng)，如果是，則即退出系統(tǒng)，否則顯示……continue……并且返回主菜單。為了方便由于誤按導(dǎo)致程序退出。　　在退出時可以增加一段感謝使用本程序的結(jié)束語。　　4.2、測試結(jié)果的分析與討論：　　系統(tǒng)運(yùn)行主界面

97、輸入需要執(zhí)行的操作1矩陣的轉(zhuǎn)置　　輸入需要執(zhí)行的操作2矩陣的加法　　輸入需要執(zhí)行的操作3矩陣的乘法　　輸入錯誤操作時需要重新選擇　　退出操作　　5、時間復(fù)雜度的分析：&

98、lt;p>　　a)加法運(yùn)算　　由于兩矩陣行列相等，故時間復(fù)雜度為O（行*列）　　b）乘法運(yùn)算　　設(shè)M是m1*n1矩陣，N是m2*n2矩陣，則時間復(fù)雜度是O（m1*n1*n2）

99、;　　c）轉(zhuǎn)置運(yùn)算　　時間復(fù)雜度和原矩陣的列數(shù)及非零元的個數(shù)的乘積成正比，即O（mu*nu）　　源程序清單和執(zhí)行結(jié)果　　#include <iostream>　　#include <iomanip><

100、;p>　　using namespace std;　　const int MAXSIZE = 100; // 定義非零元素的對多個數(shù)　　const int MAXROW = 10; // 定義數(shù)組的行數(shù)的最大值　　typedef struct {

101、　int i, j;　　int e;　　} Triple; // 定義三元組的元素　　typedef struct {　　Triple data[MAXSIZE + 1];

102、　　int mu, nu, tu;　　} TSMatrix; // 定義普通三元組對象　　typedef struct {　　Triple data[MAXSIZE + 2];　　int rpos[MAXROW + 1];　　in

103、t mu, nu, tu;　　} RLSMatrix; // 定義帶鏈接信息的三元組對象　　typedef struct OLNode { // 定義十字鏈表元素　　int i, j;　　int e;</b&g

104、t;　　struct OLNode *right, *down; // 該非零元所在行表和列表的后繼元素　　} OLNode, *OLink; // 定義十字鏈表元素　　typedef struct { // 定義十字鏈表對象結(jié)構(gòu)體　　OLink *rhead, *

105、chead;　　int mu, nu, tu; // 系數(shù)矩陣的行數(shù)，列數(shù)，和非零元素個數(shù)　　} CrossList; // 定義十字鏈表對象結(jié)構(gòu)體　　template <class P>　　bool InPutTSMatrix(P & T,

106、int y) { //輸入矩陣，按三元組格式輸入　　cout << "輸入矩陣的行，列和非零元素個數(shù):" << endl;　　cin >> T.mu >> T.nu >> T.tu;　　cout << "請輸出非

107、零元素的位置和值:" << endl;　　for (int k = 1; k <= T.tu; k++)　　cin >> T.data[k].i >> T.data[k].j >> T.data[k].e;　　return true;</p&g

108、t;　　}　　template <class P>　　bool OutPutSMatrix(P T) {　　int m, n, k = 1;　　for (m = 0; m < T.mu; m++

109、) {　　for (n = 0; n < T.nu; n++) {　　if ((T.data[k].i - 1) == m && (T.data[k].j - 1) == n) {　　cout.width(4);　　cout << T.d

110、ata[k++].e;　　} else {　　cout.width(4);　　cout << "0";　　}<b&g

111、t;　　}　　cout << endl;　　}　　return true;　　}// 輸出矩陣，按標(biāo)準(zhǔn)格式輸出　　bool TransposeSMatrix()

112、 // 求矩陣的轉(zhuǎn)置矩陣　　{　　TSMatrix M, T; //定義預(yù)轉(zhuǎn)置的矩陣　　InPutTSMatrix(M, 0); //輸入矩陣　　int num[MAXROW + 1];　　i

113、nt cpot[MAXROW + 1]; // 構(gòu)建輔助數(shù)組　　int q, p, t;　　T.tu = M.tu;　　T.mu = M.nu;　　T.nu = M.mu;　　if (T.tu) <

114、;p>　　{　　for (int col = 1; col <= M.nu; col++) num[col] = 0;　　for (t = 1; t <= M.tu; t++) ++num[M.data[t].j];　　cpot[1] = 1;</p&

115、gt;　　for (int i = 2; i <= M.nu; i++) cpot[i] = cpot[i - 1] + num[i - 1]; // 求出每一列中非零元素在三元組中出現(xiàn)的位置　　for (p = 1; p <= M.tu; p++) 　　{

116、　　int col = M.data[p].j;　　q = cpot[col];　　T.data[q].i = M.data[p].j;　　T.data[q].j = M.data[p].i;　　T.data[q].e = M.data[p].e;&l

117、t;/p>　　++cpot[col];　　}　　}　　cout << "輸入矩陣的轉(zhuǎn)置矩陣為" << endl;　　OutP

118、utSMatrix(T);　　return true;　　}　　bool Count(RLSMatrix &T) {　　int num[MAXROW + 1];　　for (int r

119、ow = 1; row <= T.mu; row++) num[row] = 0;　　for (int col = 1; col <= T.tu; col++) ++num[T.data[col].i];　　T.rpos[1] = 1;　　for (int i = 2; i <= T.mu; i

120、++) T.rpos[i] = T.rpos[i - 1] + num[i - 1]; // 求取每一行中非零元素在三元組中出現(xiàn)的位置　　return true;　　}　　bool MultSMatrix() // 兩個矩陣相乘<

121、;b>　　{　　RLSMatrix M, N, Q; // 構(gòu)建三個帶“鏈接信息”的三元組表示的數(shù)組　　InPutTSMatrix(M, 1); // 用普通三元組形式輸入數(shù)組　　InPutTSMatrix(N, 1);　　C

122、ount(M);　　Count(N);　　cout << "輸入的兩矩陣的乘矩陣為：" << endl;　　if (M.nu != N.mu) return false;

123、　　Q.mu = M.mu;　　Q.nu = N.nu;　　Q.tu = 0; // Q初始化　　int ctemp[MAXROW + 1]; // 輔助數(shù)組　　int arow, tp, p, brow, t, q, ccol;&l

124、t;p>　　if (M.tu * N.tu) // Q是非零矩陣　　{　　for (arow = 1; arow <= M.mu; arow++) 　　{　　///memset(ct

125、emp,0,N.nu);　　for (int x = 1; x <= N.nu; x++) // 當(dāng)前行各元素累加器清零　　ctemp[x] = 0;　　Q.rpos[arow] = Q.tu + 1; // 當(dāng)前行的首個非零元素在三元組中的位置為此行前所有非零元素+1<p&

126、gt;　　if (arow < M.mu) tp = M.rpos[arow + 1];　　else tp = M.tu + 1;　　for (p = M.rpos[arow]; p < tp; p++) // 對當(dāng)前行每個非零元素進(jìn)行操作　　{ </p

127、>　　brow = M.data[p].j; // 在N中找到i值也操作元素的j值相等的行　　if (brow < N.mu) t = N.rpos[brow + 1];　　else t = N.tu + 1;　　for (q = N.rpos[brow]; q < t;

128、 q++) // 對找出的行當(dāng)每個非零元素進(jìn)行操作　　{ 　　ccol = N.data[q].j;　　ctemp[ccol] += M.data[p].e * N.data[q].e; // 將乘得到對應(yīng)值放在相應(yīng)的元素累加器里面<p&

129、gt;　　}　　}　　for (ccol = 1; ccol <= Q.nu; ccol++) // 對已經(jīng)求出的累加器中的值壓縮到Q中　　if (ctemp[ccol]) <b&

130、gt;　　{　　if (++Q.tu > MAXSIZE) return false;　　Q.data[Q.tu].e = ctemp[ccol];　　Q.data[Q.tu].i = arow;　　Q.data[Q.tu].j = ccol;&

131、lt;/p>　　}　　}　　}　　OutPutSMatrix(Q);　　return true;<p

132、>　　}　　bool CreateSMatrix_OL(CrossList & M)// 創(chuàng)建十字鏈表　　{　　int x, y, m;　　cout << "

133、;請輸入矩陣的行，列，及非零元素個數(shù)" << endl;　　cin >> M.mu >> M.nu >> M.tu;　　if (!(M.rhead = (OLink*) malloc((M.mu + 1) * sizeof (OLink)))) exit(0);<p&

134、gt;　　if (!(M.chead = (OLink*) malloc((M.nu + 1) * sizeof (OLink)))) exit(0);　　for (x = 0; x <= M.mu; x++)　　M.rhead[x] = NULL; // 初始化各行，列頭指針，分別為NULL　　for (

135、x = 0; x <= M.nu; x++)　　M.chead[x] = NULL;　　cout << "請按三元組的格式輸入數(shù)組：" << endl;　　for (int i = 1; i <= M.tu; i++) <p&g

136、t;　　{　　cin >> x >> y >> m; // 按任意順序輸入非零元，（普通三元組形式輸入）　　OLink p, q;　　if (!(p = (OLink) malloc(sizeof (OLNode)))) exit(0);

137、 // 開辟新節(jié)點(diǎn)，用來存儲輸入的新元素　　p->i = x;　　p->j = y;　　p->e = m;　　if (M.rhead[x]

138、== NULL || M.rhead[x]->j > y) 　　{　　p->right = M.rhead[x];　　M.rhead[x] = p;　　}

139、　　else 　　{　　for (q = M.rhead[x]; (q->right) && (q->right->j < y); q = q->right); // 查找節(jié)點(diǎn)在行表中的插入位置</p&g

眾賞文庫> 全部分類> 畢業(yè)設(shè)計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

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

文檔簡介

溫馨提示

最新文檔

評論

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

文檔簡介

溫馨提示

最新文檔

評論

免費(fèi)下載