稀疏矩阵运算器设计

1、附录2内蒙古科技大学本科生课程设计论文题 目：稀疏矩阵运算器设计学生姓名：刘艳超学 号：1367159114专 业：软件工程班 级：软件13-1班指导教师：周李涌 2013年 1月5日内蒙古科技大学课程设计任务书课程名称数据结构与算法课程设计设计题目稀疏矩阵运算器设计指导教师周李涌时间2015.1.52015.1.9一、教学要求1. 掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力2. 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能3. 提高综合运用所学的理论知识和方法独立分析和解决问题的能力4. 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作

2、者所应具备的科学的工作方法和作风二、设计资料及参数每个学生在教师提供的课程设计题目中任意选择一题，独立完成，题目选定后不可更换。稀疏矩阵运算器设计以三元组结构体类型表示稀疏矩阵非零元，在此基础上完成对稀疏矩阵的转置、相加和相乘操作。要求设计类（或类模板）来描述稀疏矩阵及其操作，包含必要的构造函数和析构函数，以及其他能够完成如下功能的成员函数：v 输入、输出稀疏矩阵v 稀疏矩阵的转置运算v 稀疏矩阵的相加运算v 稀疏矩阵的相乘运算 并设计主函数测试该类。三、设计要求及成果1. 分析课程设计题目的要求2. 写出详细设计说明3. 编写程序代码，调试程序使其能正确运行4. 设计完成的软件要便于操作和使

3、用5. 设计完成后提交课程设计报告四、进度安排资料查阅与讨论（1天）系统分析（2天）系统的开发与测试（5天）编写课程设计说明书和验收（2天）五、评分标准1. 根据平时上机考勤、表现和进度，教师将每天点名和检查2. 根据课程设计完成情况，必须有可运行的软件。3. 根据课程设计报告的质量，如有雷同，则所有雷同的所有人均判为不及格。4. 根据答辩的情况，应能够以清晰的思路和准确、简练的语言叙述自己的设计和回答教师的提问六、建议参考资料1数据结构 （C语言版）严蔚敏、吴伟民 主编 清华大学出版社 2004.112数据结构课程设计案例精编（用C/C+描述），李建学 等 编著，清华大学出版社 2007.2

4、3.数据结构:用面向对象方法与C+语言描述，殷人昆 主编， 清华大学出版社 2007.6目录第1章 需求分析4第2章 总体设计4第3章 抽象数据类型定义53.1 Mlist 类 抽象数据类型的设计5第4章 详细设计64.1 工程视图64.2 类图视图64.3 函数的调用关系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稀疏矩阵的转置：TraMlist(OLink &M)15第5章 测试16第6章 总结19附录：程序代码20第1章 需求分析稀疏矩阵运算器设计以三元组结构体类型表示稀疏矩阵非零元，在此基础上完成对稀疏矩阵的转置、相加和相乘操作。要求设计类（或类模板）来描述稀疏矩阵及其操作，包含必要的构造函数和析构

6、函数，以及其他能够完成如下功能的成员函数：v 输入、输出稀疏矩阵v 稀疏矩阵的转置运算v 稀疏矩阵的相加运算v 稀疏矩阵的相乘运算 并设计主函数测试该类。第2章 总体设计矩阵转置矩阵相乘系统功能创建稀疏矩阵输出稀疏矩阵矩阵运算矩阵求差矩阵求和第3章 抽象数据类型定义定义格式如下：3.1 Mlist 类 抽象数据类型的设计定义格式如下：Mlist类 抽象数据类型的设计class Mlistpublic: /构造函数和析构函数Mlist()Mlist()void Reback();void Tra(OLink &M);void Init(OLink &M, int mu, int

7、nu, OLink *hd); /初始化头结点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章 详细设计4.1 工程视图4.2 类图视图4.

8、3 函数的调用关系如下图：4.4 主程序流程图mainPrintMlistAdd_SubMlistCreatMListInitMlistMulMlistTraMlistCreatMListInsertMlistPrintMlist4.5 主要算法的流程图4.5.1初始化稀疏矩阵：InitMlist(OLink &M, int mu, int nu, OLink *hd) int i,s OLink p开始结束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开始结束给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构造稀疏矩阵：CreatMList(OLink &M, OLink *hd)int i,j,m,n,t,sint k = 1ElemType v开始结束k <= t给hd开辟空间s = max(m, n)YN输入m,n,t调

11、用初始化函数InitMlist(M, m, n, hd)调用插入函数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开始结束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调用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;结束调用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稀疏矩阵的转置：TraMlist(OLink &M)第5章 测试程序的运行结果截图:图5.5.1主界面图5.5.2 创建稀疏矩阵图5.5.3 输出稀疏矩阵图5.5.4 两矩阵求和图5.5.5 两矩阵做差图5.5.6 矩阵的转置第6章 总结总结：经过十几天的看书、查资料，在网上下载现成的代码增减，互相整合模块，并按照要求简单的改写成了要求的c+形式，当然，类的应用还是很浅显的那种。向很多人寻求帮助，丁炜，贺英杰等都给予了我非常大的帮助。程序基本完工了，基本实现了课程设计的基本要求和功能，以下是为这个程序做

15、的一些分析与总结：链表中常常遇到指针指向未知区域的问题，指针链表，是很多人。尤其是像我这样的超大难题。还是要不断加强这方面练习才好。主要问题出现在实现矩阵运算过程中，特别是乘法（数据机构实验曾经做过稀疏矩阵的相加），行列相乘，相加，起初一直在判断什么时候换行换列上纠结，以为有很多种情况，最后发现情况其实都可以归结为2种：1、行或者列中没有非零元了（即指针指向头结点）并且第二个矩阵q->next还存在非空列没有与循环中的行进行运算，即第一个矩阵原来行再一次从头与第二个矩阵的后一列进行运算2、第二个矩阵没有非空列了，即指针指向总头结点了，那么第一个矩阵指向下一行，第二个矩阵从头开始每一列都与

16、第一个矩阵的行做乘法运算最后把结果存入到新的矩阵中，并打印出来.通过此次的课程设计，充分到自己对知识点掌握的十分不牢固，自己对这真的理解还太肤浅，运用十分欠火候。充分意识到了自己与同学的差距。今后一定要戒骄戒躁，塌下心来，脚踏实地的学习专业课知识。附录：程序代码#include <iostream>#include <cstdio>#include <cstdlib>using namespace std;typedef int ElemType;typedef int Status;/非零项结构体typedef struct OLNodeint row,

17、col; /非零元素的行和列的下标OLNode *right, *down; /非零元素所在行和列表的后继链域unionElemType value; /非零元结点的值域OLNode *next; /头结点的value域为空，便于查找每一行每一列，将这些头结点连起来v_next;OLNode,*OLink;/juzhenlist类class Mlistpublic: /构造函数和析构函数Mlist()Mlist()void Reback();void Tra(OLink &M);void Init(OLink &M, int mu, int nu, OLink *hd); /初

18、始化头结点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 分别输入行数、列数、非零元个数： "cin >> m >> n >> t; /输入行数、列数和非零元个数s = m > n?m : n;hd = (OLink*)malloc(s+1)*sizeof(OLNode*); Init(M, m, n, hd); /初始化头结点cout << "n 输入每个非零元的行、列及值：nn"for(int k = 1; k <

20、= t; k+) /输入一个三元组，设置为intcout << " 第" << k << "个："cin >> i >> j >> v;Insert(i, j, v, hd); /在矩阵中插入元素; return 1;/初始化头结点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、; /申请总头结点M->row = mu; M->col = nu;hd0 = M;for(i = 1; i <= s; i+)p = (OLink)malloc(sizeof(OLNode); /申请第一个头结点p->row = 0; p->col = 0;p->right = p; p->down= p; /由于是空链表，循环指向自己hdi = p;hdi-1->v_next.next = p; /把各行各列的头结点连起来hds->v_next.next = M; /将头结点形成循环链表/将值插入给定位置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; /列数p = M->v_next.next;/p指向第一个结点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+) /非零元素与结点或非零元素之间的距离（0的个数）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的前驱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; /指向下一个结点i+;elsecout << "n 矩阵空，请创建!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; 两矩阵行列数不等，！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指向同一行的结点qn = pn->right;if(qm != pm && qn != pn) /两个矩阵所指行都不空while(qm != pm && qn != pn)if(qm->col < qn->col) /两个节点所在列不同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指向同一行的结点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;/稀疏矩阵的转置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); /初始化转置矩阵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 原矩阵的转置为：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.创建稀疏矩阵 *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.稀疏矩阵转置 *nttt"cout<<"*nttt" cout<<"* 7.退 出 *nttt"cout<<"*nttt"cout<<endl<<endl<<endl