数据结构课程设计-基于十字链表的矩阵运算.doc

数 据 结 构课 程 设 计 报 告日期: 年 月 日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 用户手册156 总结17参考文献18附件 源程序代码清单1921 任务概述1.1 问题描述应用三元组和正交链表存储稀疏矩阵，并实现稀疏矩阵的转置、加法和乘法运算。1.2 编程的基本要求1）应用三元组和正交链表的数据结构。2）矩阵运算由正交链表类的成员函数实现，矩阵的输入输出由类的友元重载函数实现。3）主函数用于实现菜单和调用。1.3 程序的主要功能1. 按数据结构课程设计报告格式所给出的框架撰写。2. 具体内容应尽量包含文字叙述、图表（表格，框图，流程图，uml图等）和程序代码。3. 每个同学要提交电子文档和一份打印稿。1.4 编程语言及选择的操作平台编程语言选用c+程序设计语言。程序开发平台选用mcrosoft 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 : matrix&）+ 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: 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 ostream&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 -稀疏矩阵的转置-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 -稀疏矩阵的乘法-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)再者算法中有些小漏洞没有考虑到，用断点分析法，找出漏洞，完善程序。感触最深的是：断点查错这功能太好！又快又贴近实际应用！4.2 测试结果一、转置的测试：二、加法的测试：（可以加）（不可以加）三、乘法的测试：（可以乘）（不可以乘）按0退出程序：4.3 改进设想1）由于时间仓促，没有将其调试成功后将类做成模版，导致只能输入floate型数据， 改进方案：将所有的类做成模版，将其属下的floate类型的全改为 模版类型参数。2） 此程序显的很繁琐，但代码数量来看，还没有以三元组为存储结构的实现代码简单，可能是我们的算法不好！改进方法：重新考虑算法，看是否可用数组加指针的方式实现，用数组可以简化找头指针的繁琐过程，简化循环的过程提高程序运行效率！但现在还不是很清楚！3）程序的效率为o（n*m）(n、m分别为行数与列数) 5 用户手册一、开启程序，进入程序的dos运行界面。二、（说明：矩阵的值暂时只能输入float型）n 1）出现此界面时按提示选择所要选择的运算功能。例如选择1：显示如下 输入所要转置矩阵的行、列与非零元素个数，按enter确定，按提示依次输入各非零元素的行、列及其数值，全部输入完成后按enter确定，即可得到转置后的矩阵。当选择2或3时：例如选择2：按提示输入所要执行相加运算的第一个矩阵的 输入完成后继续输入第二个矩阵的行、列与非零元素值。输完后按enter键确定显示计算结果。 乘法的操作步骤与加法相似，可参考加法的执行。2）当一次执行结束后可按任意键返回到1）的界面，此时您可以重新选择所要执行的运算。 4 调试分析6 总结总结1）此次课程设计过程中，真正的体验到，拿到一个问题，应该先分析，将其的属性，功能分析清楚后，再进行细化，考虑其实现的具体的、有效的算法，有了整体的结构框架后再上机！以前只要拿到题就直接打开电脑，想到什么就写什么，没整体思考，对小程序可以，大程序就会彻底崩溃。2）编程实质就是问题的分析及其实现的算法，这两方面解决了上机编程才会得心应手，剩下的就是按算法些代码了！3）确定一个好算法很难，一个人往往陷入死循环，思路受局限，找人讨论很必要，编程时团队意识很重要，这不是一个人就能搞定的。没人指点迷津很难！4）设计过程中对所学到的知识感触很深，书上的东西确是钻之弥深。平时了解、理解的只是很浅的一部分。断点查错很实用！调试程序比写程序好受多！参考文献1 殷人昆主编.数据结构（第2版）北京：清华大学出版社，2007.2 田鲁怀主编 数据结构（c语言版） 电子工业出版社 2008年7月/itedu/200707/129101.html/xshf12345/archive/2008/11/17/3319383.aspx/babyrauljoey/blog/item/10739623038f1f4cad34de9b.html/program/programs/clanguage/cjg/program_53729.html/u2/85184/showart_1662531.html/z/q136781974.htm/soft/sort014/sort046/sort0220/down-125593.html附件 源程序代码清单#ifndef matrix_h#define matrix_h#include#includeenum booleanfalse,true;struct element int row,col;float item;class matrix;class node / 矩阵节点类的定义friend 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&,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);node*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;current=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);/先定位行的位置再寻找列插入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-down=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-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;ostream &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;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 matrix: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-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;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;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_head-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!