稀疏矩陣運算器設(shè)計

1、附錄2內(nèi)蒙古科技大學本科生課程設(shè)計論文題 目：稀疏矩陣運算器設(shè)計學生姓名：劉艷超學 號：1367159114專 業(yè)：軟件工程班 級：軟件13-1班指導教師：周李涌 2013年 1月5日內(nèi)蒙古科技大學課程設(shè)計任務(wù)書課程名稱數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計設(shè)計題目稀疏矩陣運算器設(shè)計指導教師周李涌時間2015.1.52015.1.9一、教學要求1. 掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計方法，具備初步的獨立分析和設(shè)計能力2. 初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計、程序編碼、測試等基本方法和技能3. 提高綜合運用所學的理論知識和方法獨立分析和解決問題的能力4. 訓練用系統(tǒng)的觀點和軟件開發(fā)一般規(guī)范進行軟件開發(fā)，培養(yǎng)軟件工作

2、者所應(yīng)具備的科學的工作方法和作風二、設(shè)計資料及參數(shù)每個學生在教師提供的課程設(shè)計題目中任意選擇一題，獨立完成，題目選定后不可更換。稀疏矩陣運算器設(shè)計以三元組結(jié)構(gòu)體類型表示稀疏矩陣非零元，在此基礎(chǔ)上完成對稀疏矩陣的轉(zhuǎn)置、相加和相乘操作。要求設(shè)計類（或類模板）來描述稀疏矩陣及其操作，包含必要的構(gòu)造函數(shù)和析構(gòu)函數(shù)，以及其他能夠完成如下功能的成員函數(shù)：v 輸入、輸出稀疏矩陣v 稀疏矩陣的轉(zhuǎn)置運算v 稀疏矩陣的相加運算v 稀疏矩陣的相乘運算 并設(shè)計主函數(shù)測試該類。三、設(shè)計要求及成果1. 分析課程設(shè)計題目的要求2. 寫出詳細設(shè)計說明3. 編寫程序代碼，調(diào)試程序使其能正確運行4. 設(shè)計完成的軟件要便于操作和使

3、用5. 設(shè)計完成后提交課程設(shè)計報告四、進度安排資料查閱與討論（1天）系統(tǒng)分析（2天）系統(tǒng)的開發(fā)與測試（5天）編寫課程設(shè)計說明書和驗收（2天）五、評分標準1. 根據(jù)平時上機考勤、表現(xiàn)和進度，教師將每天點名和檢查2. 根據(jù)課程設(shè)計完成情況，必須有可運行的軟件。3. 根據(jù)課程設(shè)計報告的質(zhì)量，如有雷同，則所有雷同的所有人均判為不及格。4. 根據(jù)答辯的情況，應(yīng)能夠以清晰的思路和準確、簡練的語言敘述自己的設(shè)計和回答教師的提問六、建議參考資料1數(shù)據(jù)結(jié)構(gòu) （C語言版）嚴蔚敏、吳偉民 主編 清華大學出版社 2004.112數(shù)據(jù)結(jié)構(gòu)課程設(shè)計案例精編（用C/C+描述），李建學 等 編著，清華大學出版社 2007.2

4、3.數(shù)據(jù)結(jié)構(gòu):用面向?qū)ο蠓椒ㄅcC+語言描述，殷人昆 主編， 清華大學出版社 2007.6目錄第1章 需求分析4第2章 總體設(shè)計4第3章 抽象數(shù)據(jù)類型定義53.1 Mlist 類 抽象數(shù)據(jù)類型的設(shè)計5第4章 詳細設(shè)計64.1 工程視圖64.2 類圖視圖64.3 函數(shù)的調(diào)用關(guān)系74.4 主程序流程圖74.5 主要算法的流程圖 84.5.1初始化稀疏矩陣：InitMlist(OLink &M, int mu, int nu, OLink *hd)84.5.2稀疏矩陣的插入：InsertMlist(int i, int j, int v, OLink *hd)94.5.4打印稀疏矩陣

5、：PrintMlist(OLink &M)114.5.5稀疏矩陣的和（差）：Add_SubMlist(OLink &M, OLink &N, int num)124.5.6稀疏矩陣乘積：MulMlist(OLink &M, Olink &N)144.5.7稀疏矩陣的轉(zhuǎn)置：TraMlist(OLink &M)15第5章 測試16第6章 總結(jié)19附錄：程序代碼20第1章 需求分析稀疏矩陣運算器設(shè)計以三元組結(jié)構(gòu)體類型表示稀疏矩陣非零元，在此基礎(chǔ)上完成對稀疏矩陣的轉(zhuǎn)置、相加和相乘操作。要求設(shè)計類（或類模板）來描述稀疏矩陣及其操作，包含必要的構(gòu)造函數(shù)和析構(gòu)

6、函數(shù)，以及其他能夠完成如下功能的成員函數(shù)：v 輸入、輸出稀疏矩陣v 稀疏矩陣的轉(zhuǎn)置運算v 稀疏矩陣的相加運算v 稀疏矩陣的相乘運算 并設(shè)計主函數(shù)測試該類。第2章 總體設(shè)計矩陣轉(zhuǎn)置矩陣相乘系統(tǒng)功能創(chuàng)建稀疏矩陣輸出稀疏矩陣矩陣運算矩陣求差矩陣求和第3章 抽象數(shù)據(jù)類型定義定義格式如下：3.1 Mlist 類 抽象數(shù)據(jù)類型的設(shè)計定義格式如下：Mlist類 抽象數(shù)據(jù)類型的設(shè)計class Mlistpublic: /構(gòu)造函數(shù)和析構(gòu)函數(shù)Mlist()Mlist()void Reback();void Tra(OLink &M);void Init(OLink &M, int mu, int

7、nu, OLink *hd); /初始化頭結(jié)點void Insert(int i, int j, int v, OLink *hd); /將值插入給定位置Status Creat(OLink &M, OLink *hd); /建立稀疏矩陣void Print(OLink &M); /打印稀疏矩陣Status Add_Sub(OLink &M, OLink &N, int num); /計算兩個稀疏矩陣的和與差Status Mul(OLink &M, OLink &N); /計算兩個稀疏矩陣的積;第4章 詳細設(shè)計4.1 工程視圖4.2 類圖視圖4.

8、3 函數(shù)的調(diào)用關(guān)系如下圖：4.4 主程序流程圖mainPrintMlistAdd_SubMlistCreatMListInitMlistMulMlistTraMlistCreatMListInsertMlistPrintMlist4.5 主要算法的流程圖4.5.1初始化稀疏矩陣：InitMlist(OLink &M, int mu, int nu, OLink *hd) int i,s OLink p開始結(jié)束i <= s給M開辟空間s = max(mu, nu)hds->v_next.next = M;M->row = mu M->col = nup->r

9、ow = 0;p->col = 0;p->right=p;p->down= p;hdi = p;hdi-1->v_next.next = p;i=i+1hd0 = M i = 1給p開辟空間YN4.5.2稀疏矩陣的插入：InsertMlist(int i, int j, int v, OLink *hd)OLink p, q開始結(jié)束給p開辟空間p->row=ip->col=j p->v_next.value = vq = q->rightq = hdi給q開辟空間q->right != hdi && (q->right

10、->col) < jq = hdjp->right= q->right;q->right = p;q->down != hdj && (q->down->col) < ip->down= q->down;q->down = p;q = q->downYYNN4.5.3構(gòu)造稀疏矩陣：CreatMList(OLink &M, OLink *hd)int i,j,m,n,t,sint k = 1ElemType v開始結(jié)束k <= t給hd開辟空間s = max(m, n)YN輸入m,n,t調(diào)

11、用初始化函數(shù)InitMlist(M, m, n, hd)調(diào)用插入函數(shù)InsertMlist(i, j, v, hd)K=k+1輸入i,j,v4.5.4打印稀疏矩陣：PrintMlist(OLink &M)int i=1int col,k=1,tOLink p，q,r開始結(jié)束p!=M&&M->row!=0&& M->col!=0給p開辟空間給q開辟空間給r開辟空間k=r->colq=p->rightr=pYNcol=M->colk=k+1p=M->v_next.nexti<=M->rowq!=pk<q-

12、>col-(r->col輸出0q=q->rightr=r->right輸出q->v_next.valuet<colt=k輸出0YNNYp=p->v_next.nexti=i+1輸出矩陣空 NYNYt=t+1調(diào)用PrintMlist(S)4.5.5稀疏矩陣的和（差）：Add_SubMlist(OLink &M, OLink &N, int num)2qm=pm&&qn!=pnInsertMlist(qn->row,qn->col,+/-qn->v_next.value,hd)qn = qn->rig

13、htNYqn!=pnYNqn=pn&&qm!=pmqm!=pmYNInsertMlist(qm->row,qm->col,qm->v_next.value, hd)qm = qm->right;YNpm = pm->v_next.next;pn = pn->v_next.next;結(jié)束調(diào)用PrintMlist(S)4.5.6稀疏矩陣乘積：MulMlist(OLink &M, Olink &N)qm = pm->rightpn = pn->v_next.nextqn = pn->down2pn = Npm=pm

14、->v_next.nextpn=rqn=pn->downYN34.5.7稀疏矩陣的轉(zhuǎn)置：TraMlist(OLink &M)第5章 測試程序的運行結(jié)果截圖:圖5.5.1主界面圖5.5.2 創(chuàng)建稀疏矩陣圖5.5.3 輸出稀疏矩陣圖5.5.4 兩矩陣求和圖5.5.5 兩矩陣做差圖5.5.6 矩陣的轉(zhuǎn)置第6章 總結(jié)總結(jié)：經(jīng)過十幾天的看書、查資料，在網(wǎng)上下載現(xiàn)成的代碼增減，互相整合模塊，并按照要求簡單的改寫成了要求的c+形式，當然，類的應(yīng)用還是很淺顯的那種。向很多人尋求幫助，丁煒，賀英杰等都給予了我非常大的幫助。程序基本完工了，基本實現(xiàn)了課程設(shè)計的基本要求和功能，以下是為這個程序做

15、的一些分析與總結(jié)：鏈表中常常遇到指針指向未知區(qū)域的問題，指針鏈表，是很多人。尤其是像我這樣的超大難題。還是要不斷加強這方面練習才好。主要問題出現(xiàn)在實現(xiàn)矩陣運算過程中，特別是乘法（數(shù)據(jù)機構(gòu)實驗曾經(jīng)做過稀疏矩陣的相加），行列相乘，相加，起初一直在判斷什么時候換行換列上糾結(jié)，以為有很多種情況，最后發(fā)現(xiàn)情況其實都可以歸結(jié)為2種：1、行或者列中沒有非零元了（即指針指向頭結(jié)點）并且第二個矩陣q->next還存在非空列沒有與循環(huán)中的行進行運算，即第一個矩陣原來行再一次從頭與第二個矩陣的后一列進行運算2、第二個矩陣沒有非空列了，即指針指向總頭結(jié)點了，那么第一個矩陣指向下一行，第二個矩陣從頭開始每一列都與

16、第一個矩陣的行做乘法運算最后把結(jié)果存入到新的矩陣中，并打印出來.通過此次的課程設(shè)計，充分到自己對知識點掌握的十分不牢固，自己對這真的理解還太膚淺，運用十分欠火候。充分意識到了自己與同學的差距。今后一定要戒驕戒躁，塌下心來，腳踏實地的學習專業(yè)課知識。附錄：程序代碼#include <iostream>#include <cstdio>#include <cstdlib>using namespace std;typedef int ElemType;typedef int Status;/非零項結(jié)構(gòu)體typedef struct OLNodeint row,

17、col; /非零元素的行和列的下標OLNode *right, *down; /非零元素所在行和列表的后繼鏈域unionElemType value; /非零元結(jié)點的值域OLNode *next; /頭結(jié)點的value域為空，便于查找每一行每一列，將這些頭結(jié)點連起來v_next;OLNode,*OLink;/juzhenlist類class Mlistpublic: /構(gòu)造函數(shù)和析構(gòu)函數(shù)Mlist()Mlist()void Reback();void Tra(OLink &M);void Init(OLink &M, int mu, int nu, OLink *hd); /初

18、始化頭結(jié)點void Insert(int i, int j, int v, OLink *hd); /將值插入給定位置Status Creat(OLink &M, OLink *hd); /建立稀疏矩陣void Print(OLink &M); /打印稀疏矩陣Status Add_Sub(OLink &M, OLink &N, int num); /計算兩個稀疏矩陣的和與差Status Mul(OLink &M, OLink &N); /計算兩個稀疏矩陣的積;/建立稀疏矩陣Status Mlist:Creat(OLink &M, OLin

19、k *hd)double w = 0;int i, j, m, n, t, s;ElemType v;cout << "n 分別輸入行數(shù)、列數(shù)、非零元個數(shù)： "cin >> m >> n >> t; /輸入行數(shù)、列數(shù)和非零元個數(shù)s = m > n?m : n;hd = (OLink*)malloc(s+1)*sizeof(OLNode*); Init(M, m, n, hd); /初始化頭結(jié)點cout << "n 輸入每個非零元的行、列及值：nn"for(int k = 1; k <

20、= t; k+) /輸入一個三元組，設(shè)置為intcout << " 第" << k << "個："cin >> i >> j >> v;Insert(i, j, v, hd); /在矩陣中插入元素; return 1;/初始化頭結(jié)點void Mlist:Init(OLink &M, int mu, int nu, OLink *hd)int i, s;OLink p;s = mu > nu?mu : nu;M = (OLink)malloc(sizeof(OLNode)

21、; /申請總頭結(jié)點M->row = mu; M->col = nu;hd0 = M;for(i = 1; i <= s; i+)p = (OLink)malloc(sizeof(OLNode); /申請第一個頭結(jié)點p->row = 0; p->col = 0;p->right = p; p->down= p; /由于是空鏈表，循環(huán)指向自己hdi = p;hdi-1->v_next.next = p; /把各行各列的頭結(jié)點連起來hds->v_next.next = M; /將頭結(jié)點形成循環(huán)鏈表/將值插入給定位置void Mlist:Inser

22、t(int i, int j, int v, OLink *hd)OLink p, q;p = (OLink)malloc(sizeof(OLNode);p->row = i; p->col = j; p->v_next.value = v;/以下是將*p插入行鏈表中去，且按列號有序q = (OLink)malloc(sizeof(OLNode);q = hdi;while(q->right != hdi && (q->right->col) < j) /按列號找位置q = q->right;p->right= q->

23、right; /插入q->right = p;/以下是將*p插入行鏈表中去，且按行號有序q = hdj;while(q->down!=hdj && (q->down->row) < i) /按行號找位置q = q->down;p->down= q->down; /插入q->down = p;/打印稀疏矩陣void Mlist:Print(OLink &M)OLink p, q, r;int col, k, t;int i = 1;p = (OLink)malloc(sizeof(OLNode);q = (OLink)

24、malloc(sizeof(OLNode);r = (OLink)malloc(sizeof(OLNode);col = M->col; /列數(shù)p = M->v_next.next;/p指向第一個結(jié)點if(p != M)while(i <= M->row)cout <<" "q = p->right; /q指向p的右邊元素，行遍歷r = p;while(q != p) /非零元存在for(k = 1; k < q->col-(r->col); k+) /非零元素與結(jié)點或非零元素之間的距離（0的個數(shù)）cout.set

25、f(ios:left, ios:adjustfield);cout.width(5);cout << "0"cout.setf(ios:left, ios:adjustfield);cout.width(5);cout <<q->v_next.value;q = q->right; /指向下一個非零元素r = r->right; /r指向q的前驅(qū)k = r->col;for(t = k; t<col; t+)cout.setf(ios:left, ios:adjustfield);cout.width(5);cout &

26、lt;< "0"cout << endl;p = p->v_next.next; /指向下一個結(jié)點i+;elsecout << "n 矩陣空，請創(chuàng)建!n"/計算兩個稀疏矩陣的和與差Status Mlist:Add_Sub(OLink &M, OLink &N, int num)OLink S, *hd;OLink pm, pn, qm, qn;int s;/兩個矩陣行列不等if(M->row != N->row | M->col != N->col)cout << &

27、quot; 兩矩陣行列數(shù)不等，！nn"return 0;/兩個矩陣行列相等elses = (M->row) > (M->col)?(M->row):(M->col);hd = (OLink*)malloc(s+1)*sizeof(OLink);Init(S, M->row, M->col, hd); /初始化和/差矩陣pm = (OLink)malloc(sizeof(OLNode);pn = (OLink)malloc(sizeof(OLNode);qm = (OLink)malloc(sizeof(OLNode);qn = (OLink)

28、malloc(sizeof(OLNode);pm = M->v_next.next;pn = N->v_next.next;while(pm != M && pn != N) /兩個矩陣都不空qm = pm->right; /qm,qn指向同一行的結(jié)點qn = pn->right;if(qm != pm && qn != pn) /兩個矩陣所指行都不空while(qm != pm && qn != pn)if(qm->col < qn->col) /兩個節(jié)點所在列不同Insert(qm->row,

29、qm->col, qm->v_next.value, hd);qm = qm->right;else if(qm->col > qn->col)if(num = 3)Insert(qn->row, qn->col, qn->v_next.value, hd);elseInsert(qn->row, qn->col, -(qn->v_next.value), hd);qn = qn->right;elseif(num = 3)if(qm->v_next.value+qn->v_next.value != 0

30、)Insert(qn->row, qn->col, (qn->v_next.value+qm->v_next.value), hd);elseif(qm->v_next.value)-(qn->v_next.value) != 0)Insert(qn->row, qn->col, (qm->v_next.value)-(qn->v_next.value), hd);qm = qm->right; qn = qn->right;/while/ifif(qm = pm && qn != pn) /其中有一個矩陣

31、所指行為空while(qn != pn)if(num = 3)Insert(qn->row, qn->col, qn->v_next.value, hd);elseInsert(qn->row, qn->col, -qn->v_next.value, hd);qn = qn->right;else if(qm != pm && qn = pn)while(qm != pm)Insert(qm->row, qm->col, qm->v_next.value, hd);qm = qm->right;pm = pm-&

32、gt;v_next.next; /指向下一行pn = pn->v_next.next;/whilePrint(S);return 1;/計算兩個稀疏矩陣的乘積Status Mlist:Mul(OLink &M, OLink &N)OLink S, *hd;OLink pm, pn, qm, qn, r;int s, sum, i, j; /i,j記錄插入的位置/若兩個矩陣行列不等if(M->col != N->row)cout << " 兩矩陣行列不符合條件，不可操作！nn"/兩個矩陣符合做乘法的條件elses = (M->

33、;row) > (N->col)?(M->row):(N->col);hd = (OLink*)malloc(s+1)*sizeof(OLink);Init(S, M->row, N->col, hd); /初始化積矩陣pm = (OLink)malloc(sizeof(OLNode);pn = (OLink)malloc(sizeof(OLNode);qm = (OLink)malloc(sizeof(OLNode);qn = (OLink)malloc(sizeof(OLNode);r = (OLink)malloc(sizeof(OLNode);pm

34、= M->v_next.next;pn = N->v_next.next;r = pn;if(pm != M && pn != N) /兩個矩陣都不空qm = pm->right; /qm,qn指向同一行的結(jié)點qn = pn->down;while(pm != M)sum = 0;qm = pm->right;while(qm != pm && qn != pn)if(qm->col = qn->row)i = qm->row; j = qn->col;sum += (qm->v_next.value)

35、*(qn->v_next.value);qm = qm->right;qn = qn->down;else if(qm->col > qn->row)qn = qn->down;elseqm = qm->right;/whileif (sum != 0)Insert(i, j, sum, hd);qm = pm->right;pn = pn->v_next.next;qn = pn->down;if (pn = N)pm = pm->v_next.next;pn = r;qn = pn->down;/while/if

36、Print(S);return 1;/稀疏矩陣的轉(zhuǎn)置void Mlist:Tra(OLink &M)OLink p, q, N, *hd;int s;s = (M->row) > (M->col)?(M->row):(M->col);hd = (OLink*)malloc(sizeof(OLink);Init(N, M->col, M->row, hd); /初始化轉(zhuǎn)置矩陣p = M->v_next.next;while(p != M)q = p->right;if(q != p)while(q != p)Insert(q->

37、col, q->row, q->v_next.value, hd);q = q->right;p = p->v_next.next;cout << "n 原矩陣的轉(zhuǎn)置為：n"Print(N);/返回void Mlist:Reback()char ch;ch = getchar();cout << " 按任意鍵返回."ch = getchar();int main()Mlist a;OLink M, N, *hdm, *hdn;int num;hdm = (OLink*)malloc(sizeof(OLNod

38、e*);hdn = (OLink*)malloc(sizeof(OLNode*);a.Init(M, 0, 0, hdm);a.Init(N, 0, 0, hdn);while(1)cout<<"nttt"cout<<"*nttt"cout<<"* 稀疏矩陣運算器 *nttt"cout<<"*nttt"cout<<"* 1.創(chuàng)建稀疏矩陣 *nttt"cout<<"*nttt"cout<<&qu

39、ot;* 2.打印稀疏矩陣 *nttt"cout<<"*nttt"cout<<"* 3.稀疏矩陣之和*nttt"cout<<"*nttt"cout<<"* 4.稀疏矩陣之差*nttt"cout<<"*nttt"cout<<"* 5.稀疏矩陣之積 *nttt"cout<<"*nttt"cout<<"* 6.稀疏矩陣轉(zhuǎn)置 *nttt"cout<<"*nttt" cout<<"* 7.退 出 *nttt"cout<<"*nttt"cout<<endl<<endl<<endl