《数据结构课程设计基于十字链表的矩阵运算.doc》由会员分享，可在线阅读，更多相关《数据结构课程设计基于十字链表的矩阵运算.doc（36页珍藏版）》请在三一办公上搜索。
1、数 据 结 构课 程 设 计 报 告日期: 年 月 日12200930 学 号班 级姓 名指 导 教 师2007级信息与计算科学题目：基于正交链表的矩阵运算说 明本组成员名单：组长：本人承担的课程设计的工作情况：程序的算法设计以及部分功能实现，后期程序调试、测试，主函数的设计。 目 录1 任务概述31.1 问题描述31.2 编程的基本要求31.3 程序的主要功能31.4 编程语言及选择的操作平台32 概要设计42.1 数据结构42.2 总体结构43 详细设计53.1 数据结构中的函数63.2 主函数及其他函数74 调试分析94.1调试过程 94.2测试结果 94.2改进设想 145 用户手册1
2、56 总结17参考文献18附件 源程序代码清单191 任务概述1.1 问题描述应用三元组和正交链表存储稀疏矩阵，并实现稀疏矩阵的转置、加法和乘法运算。1.2 编程的基本要求1）应用三元组和正交链表的数据结构。2）矩阵运算由正交链表类的成员函数实现，矩阵的输入输出由类的友元重载函数实现。3）主函数用于实现菜单和调用。1.3 程序的主要功能1. 按数据结构课程设计报告格式所给出的框架撰写。2. 具体内容应尽量包含文字叙述、图表（表格，框图，流程图，UML图等）和程序代码。3. 每个同学要提交电子文档和一份打印稿。1.4 编程语言及选择的操作平台编程语言选用C+程序设计语言。程序开发平台选用Mcro
3、soft Visual Studio 6.0的Microsoft Visual C+ 6.0开发环境。程序运行在DOS界面。2 概要设计2.1 数据结构稀疏矩阵类（matrix）matrix- Row : int- Col : int- Terms : int- termrp : int- headmode : node* - operator ( : istream, : matrix&) : istream - operator ( :ostream, :matrix) : ostream+ matrix(m ：int , n : int)+ matrix()+ matrix（T : ma
4、trix&）+ matrix()+ make Empty() : void+ Insert(m : int, n :int, p : float) : void+ pelete(m : int, n ：int) : void+ Locate(i : int) : node+ transport() : matrix+ Add(b :matrix) : matrix+ Mul(b :matrix) : matrix+ operator = (T : matrix&) : matrix+ Init (m :int,n :int :void)稀疏矩阵的节点类（node）node + matrix:
5、class+ node()+ node( t : elemene*)+ down : node*+ right : node*+ head : boolean+ union2.2总体结构说明：表达式i!=0 True,向下执行，False 结束退出表达式i!=0输入所要执行的运算（i）Switch(i)结束dafaultCase 2Case 1Case 0开始Case 33 详细设计3.1 数据结构中的函数（其中函数的实现请参看源代码部分）1) 矩阵结点（matrix）中的函数：Private:friend istream&operator(istream&,matrix&);friend o
6、stream&operatorcol; triple.row=t-row; triple.item=t-item; right=down=this; head=FALSE;3.2 主函数及其他函数#includematrix.h#include void main() int i; matrix B,B1,B2,C; while(i!=0) cout -基于正交链表的稀疏矩阵的运算-endlendl; cout 1.转置 2.加法 3.乘法 0.退出程序 endlendl; couti; coutendl; switch(i) case 0: break; case 1: cout -稀疏矩阵
7、的转置-nendl; cout请输入矩阵：endlB;system(cls);cout原矩阵为：endl;coutBendl;cout转置后为endl;coutB.transpose()endl;break; case 2: cout -稀疏矩阵的加法-nendl; cout请输入矩阵1：endlB1; cout请输入矩阵2：endlB2;system(cls);cout矩阵1为：endl; coutB1endl; cout矩阵2为：endl;coutB2endl;cout两个矩阵之和为：endl;coutB1.Add(B2)endl;break; case 3: cout -稀疏矩阵的乘法-
8、nendl;cout注意：输入的矩阵必须满足矩阵相乘的条件，并且按顺序输入(即1和2的顺序)nendl; cout请输入矩阵1：B1; cout请输入矩阵2：B2; system(cls);cout矩阵1为:endl;coutB1endl;cout矩阵2为:endl;coutB2endl;cout两个矩阵之积为：endl;coutB1.Mul(B2)endl; break; default: break; if(i!=0) cout按任意继续.right!=T.Locate(i) 开始时是while(current-right!=current)再者算法中有些小漏洞没有考虑到，用断点分析法，找
9、出漏洞，完善程序。感触最深的是：断点查错这功能太好！又快又贴近实际应用！4.2 测试结果一、转置的测试：二、加法的测试：（可以加）（不可以加）三、乘法的测试：（可以乘）（不可以乘）按0退出程序：4.3 改进设想1）由于时间仓促，没有将其调试成功后将类做成模版，导致只能输入floate型数据， 改进方案：将所有的类做成模版，将其属下的floate类型的全改为 模版类型参数。2） 此程序显的很繁琐，但代码数量来看，还没有以三元组为存储结构的实现代码简单，可能是我们的算法不好！改进方法：重新考虑算法，看是否可用数组加指针的方式实现，用数组可以简化找头指针的繁琐过程，简化循环的过程提高程序运行效率！但
10、现在还不是很清楚！3）程序的效率为O（n*m）(n、m分别为行数与列数) 5 用户手册一、开启程序，进入程序的DOS运行界面。二、（说明：矩阵的值暂时只能输入float型）n 1）出现此界面时按提示选择所要选择的运算功能。例如选择1：显示如下 输入所要转置矩阵的行、列与非零元素个数，按Enter确定，按提示依次输入各非零元素的行、列及其数值，全部输入完成后按Enter确定，即可得到转置后的矩阵。当选择2或3时：例如选择2：按提示输入所要执行相加运算的第一个矩阵的 输入完成后继续输入第二个矩阵的行、列与非零元素值。输完后按Enter键确定显示计算结果。 乘法的操作步骤与加法相似，可参考加法的执行
11、。2）当一次执行结束后可按任意键返回到1）的界面，此时您可以重新选择所要执行的运算。 4 调试分析6 总结总结1）此次课程设计过程中，真正的体验到，拿到一个问题，应该先分析，将其的属性，功能分析清楚后，再进行细化，考虑其实现的具体的、有效的算法，有了整体的结构框架后再上机！以前只要拿到题就直接打开电脑，想到什么就写什么，没整体思考，对小程序可以，大程序就会彻底崩溃。2）编程实质就是问题的分析及其实现的算法，这两方面解决了上机编程才会得心应手，剩下的就是按算法些代码了！3）确定一个好算法很难，一个人往往陷入死循环，思路受局限，找人讨论很必要，编程时团队意识很重要，这不是一个人就能搞定的。没人指点
12、迷津很难！4）设计过程中对所学到的知识感触很深，书上的东西确是钻之弥深。平时了解、理解的只是很浅的一部分。断点查错很实用！调试程序比写程序好受多！参考文献1 殷人昆主编.数据结构（第2版）北京：清华大学出版社，2007.2 田鲁怀主编 数据结构（C语言版） 电子工业出版社 2008年7月附件 源程序代码清单#ifndef MATRIX_H#define MATRIX_H#include#includeenum booleanFALSE,TRUE;struct element int row,col;float item;class matrix;class node / 矩阵节点类的定义fri
13、end class matrix;public:node():head(TRUE) right=down=this; /建立附加头结点node(element *t)/ 建立非零元素结点triple.col=t-col;triple.row=t-row;triple.item=t-item;right=down=this;head=FALSE;node*down,*right;/行列链表指针boolean head;union element triple;node*next; /无名联合;class matrix/稀疏矩阵的类定义friend istream&operator(istream
14、&,matrix&);friend ostream&operator=n?m:n;node *current;headnode=new node(&x);current=headnode-right=new node();for(int i=1;inext=new node();current=current-next;matrix:matrix():Row(0),Col(0),Terms(0) /构造函数的实现element x;x.row=Row;x.col=Col;x.item=0;matrix:matrix(matrix&T) /复制构造函数的实现Init(T.Row,T.Col);n
15、ode*current;for(int i=1;iright!=T.Locate(i) /通过行遍历逐个赋值current=current-right; Insert(current-triple.row,current-triple.col,current-triple.item);void matrix:Init(int m,int n) /矩阵初始化函数的实现Row=m;Col=n;Terms=0;element x;x.row=m;x.col=n;x.item=0;headnode=new node(&x);node* current;if(m0&n0)temp=m=n?m:n;cur
16、rent=new node();headnode-right=current;for(int i=1;inext=new node(); current=current-next;elsecout矩阵初始化错误！right;for(int k=1;knext;return current;void matrix:Insert(int m,int n,float p)/插入函数的实现element x;x.row=m;x.col=n;x.item=p;if(mRow&nCol)node *Newnode=new node(&x),*current,*head;head=Locate(m);/先定
17、位行的位置再寻找列插入current=head-right;if(current=head)current-right=Newnode;Newnode-right=current;elsewhile(current-triple.colright!=head)current=current-right;Newnode-right=current-right;current-right=Newnode; /完成插入head=Locate(n); /先定位列再寻找行插入current=head-down;if(current=head)current-down=Newnode;Newnode-do
18、wn=current;elsewhile(current-triple.rowdown!=head)current=current-down;Newnode-down=current-down;current-down=Newnode;Terms+; /完成插入elsecout输入的结点位置超出了范围，请重新输入！endl;void matrix:Delete(int m,int n) /删除特定结点元素实现if(m=Row&nright;while(del-triple.col!=n)current=current-right;del=del-right;current-right=del-
19、right;delete del;elsecout找不到结点无法删除!(istream &ist,matrix &b) /输入函数重载的实现int M,N,m,n,T;float p;cout请输入矩阵的行列和非零元素个数：MNT;b.Init(M,N);if(T(M*N)cerr输入的元素个数超过范围endl;exit(1);elsecout请输入各非零元素的行数列数和值endl;cout 行数 列数 值endl;for(int i=1;i=T;i+) /输入元素结点并且插入矩阵cout【imnp;coutendl;b.Insert(m,n,p); /插入结点return ist;ostre
20、am &operator(ostream &ost,matrix &b) /输出函数重载ost矩阵行数为：b.Row ;ost列数为：b.Col ;ost非零元素个数为b.Termsendl;node *x;for(int i=1;i=b.temp;i+) /先确定各行头结点的位置再遍历各行，以输出所有非零元素x=b.Locate(i);for(int j=1;jright-head=TRUE)break;elsex=x-right; ost第triple.row行第triple.col列元素是triple.itemRow=T.Row;this-Col=T.Col;node *current;
21、for(int i=1;iright!=current)current=current-right; /通过行遍历逐个赋值this-Insert(current-triple.row,current-triple.col,current-triple.item);return *this;void matrix:makeEmpty() /清空矩阵的实现node*del,*current;for(int i=1;idown!=Locate(i)del=current-down; /通过列的附加头结点向下删除结点current-down=del-down;delete del;matrix mat
22、rix:transpose() /矩阵转置运算的实现matrix B(this-Col,this-Row); /以原矩阵的行列和非零元素个数构造一个新的矩阵node *current;for(int i=1;idown!=Locate(i)current=current-down;B.Insert(current-triple.col,current-triple.row,current-triple.item);return B;matrix matrix:Add( matrix b) /矩阵加法的实现matrix C(b.Row,b.Col);if(this-Row=b.Row&this-
23、Col=b.Col)float j(0);node *p,*q;for(int i=1;iright!=Locate(i)&q-right!=b.Locate(i) /把加法分成三种情况即两个矩阵该行都没元素，有一个没元素，和都有元素if(p-right-triple.colq-right-triple.col) /如果都有元素，就比较那个所在的列大些，先把列小些的插入（找不到与之匹配的元素了）q=q-right;C.Insert(i,q-triple.col,q-triple.item);else if(p-right-triple.colright-triple.col)p=p-right
24、;C.Insert(i,p-triple.col,p-triple.item);elsep=p-right;q=q-right;j=p-triple.item+q-triple.item;if(j!=0)C.Insert(i,q-triple.col,j);if(p-right=Locate(i) /把遍历过程中漏掉的元素找齐while(q-right!=b.Locate(i)q=q-right;C.Insert(i,q-triple.col,q-triple.item);else if(q-right=b.Locate(i)while(p-right!=Locate(i)p=p-right;
25、C.Insert(i,p-triple.col,p-triple.item);else /如果输入有误就给出提示cout行列不同,无法相加Col=b.Row)matrix C(this-Row,b.Col); /以A矩阵的行和b矩阵的列为行列建立稀疏矩阵float value;node *Row_head,*Col_head; /设两个指针，一个充当行头指针，一个为列指针 for(int i=1;i=temp;i+) /先确定行，再求出C矩阵在该行各列的元素for(int j=1;jright!=Locate(i) /假如行中还有元素不为零就找与之匹配的元素相乘Row_head=Row_hea
26、d-right;Col_head=Col_head-down;while(Row_head-triple.col!=Col_head-triple.row&Col_head-down!=b.Locate(j) /假如行列不相等而且对应列还有元素，就继续找匹配的元素否则判断再循环if(Row_head-triple.colCol_head-triple.row)Col_head=Col_head-down;else if(Row_head-right=Locate(i)Col_head=Col_head-down; /假如b矩阵该列元素比a矩阵该行元素多elseRow_head=Row_head-right; /则b中该列元素已经无法找到能相乘元素则往下推直至跳出循环if(Col_head-down!=b.Locate(j)|Col_head-triple.row=Row_head-triple.col)value+=Row_head-triple.item*Col_head-triple.item;if(value!=0)C.Insert(i,j,value);return C;elsematrix C;cerr输入的两个矩阵不符规则，不能
