数据结构作业_稀疏矩阵运算器.doc

实习报告题目：稀疏矩阵运算器编译环境：Microsoft Visual Studio 2010功能实现：以三元组顺序表输入稀疏矩阵实现两个稀疏矩阵相加、相减和相乘的运算运算结果的矩阵以阵列形式列出以十字链表表示稀疏矩阵一、 需求分析1. 稀疏矩阵是指那些多数元素为零的矩阵，利用“稀疏”的特点进行存储和计算可以大大节省存储空间，提高计算效率。而本程序是以“带行逻辑链接信息”的三元顺序表表示稀疏矩阵，实现两个矩阵的相加、相减和相乘的运算。稀疏矩阵的输入形式采用三元组表示，而运算结果的矩阵则以通常的阵列形式列出。除此之外，程序还采用十字链表表示稀疏矩阵的。2. 程序的测试数据：二、 概要设计1. 本程序的基本算法设计：a) 首先输入矩阵的行数和列数，并判断给出的两个矩阵的行、列对于所要求的运算是否匹配。b) 对于三元组的输入顺序是按照行优先的限制进行矩阵输入的。2. 数据结构设计：typedef struct Nodeint i,j;/非零元素的行和列double e;/非零元素的值Node *right;/非零元素行表的后继Node *down;/非零元素列表的后继Node,*NLink;class CListprivate:NLink *rhead;/行的头指针NLink *dhead;/列的头指针int rNum;/行数int dNum;/列数public:CList();virtual CList();bool InsertNode(int i,int j,double e);bool CreateMatrix();void ShowMatrix();bool AddMatrix(CList &Matrix);bool SubMatrix(CList &Matrix);bool MultiMatrix(CList &Matrix,CList* &Result);三、 详细设计1. 主要操作函数的实现：(1) 插入函数：在已经初始化的稀疏矩阵中插入某个元素。bool CList:InsertNode(int i,int j,double e)Node *p,*q;if (irNum|jdNum|i0|j0)coutt Invalid row number! Insert Node Failed!endl;return TRUE;if (i=0)coutt End Inputting!endl;return TRUE;if (e=0)return TRUE;/创建矩阵元素p = new Node;if (!p)coutt Insert Node Error!i = i;p-j = j;p-e = e;/在行表中寻找插入位置if(rheadi=NULL|rheadi-jj)p-right = rheadi;rheadi=p;elseq = rheadi;while (q-right)&q-right-jright;p-right = q-right;q-right = p;/在列表中寻找插入位置if (dheadj=NULL|dheadj-ii)p-down = dheadj;dheadj = p;elseq =dheadj;while (q-down)&q-down-idown;p-down = q-down;q-down = p;return TRUE;(2) 矩阵创建函数：根据用户的输入，创建稀疏矩阵。bool CList:CreateMatrix()int m,n;int i,j;double e;coutm;coutendl;coutn;coutendl;rNum = m;dNum = n; rhead = new NLinkrNum+1;dhead = new NLinkdNum+1;for (i=0;irNum+1;i+)rheadi = NULL;for (i=0;idNum+1;i+)dheadi = NULL;coutije;coutendl;while (i!=0)InsertNode(i,j,e);coutije;coutendl;return TRUE;(3) 矩阵相加函数：实现两个稀疏矩阵的相加运算。bool CList:AddMatrix(CList &Matrix)if (Matrix.rNum!=rNum|Matrix.dNum!=dNum)coutError Matrix dimension!endl;return FALSE;Node *pa,*pb,*pre;NLink *h1 = new NLinkdNum+1;int i,j;for (i=1;i=rNum;i+)for (j=1;jjpb-j)Node *p = new Node;p-i = pb-i;p-j = pb-j;p-e = pb-e;/更新行指针if (pre=NULL)rheadp-i = p;elsepre-right = p;p-right = pa;pre = p;/更新列指针if (dheadp-j=NULL|dheadp-j-ip-i)p-down = dheadp-j;dheadp-j = p;else while(h1p-j-down&h1p-j-down-i i) h1p-j = h1p-j-down;if (h1p-j-down=NULL)h1p-j-down=p;elsep-down = h1p-j-down;h1p-j-down = p;pb = pb-right;else if (pa!=NULL&pa-jj)pre = pa;pa = pa-right;else if (pa-j=pb-j)pa-e += pb-e;if(pa-e=0)Node *p = new Node;/更新行指针if (pre=NULL)rheadpa-i = pa-right;elsepre-right=pa-right;p = pa;pa = pa-right;/更新列指针if (dheadp-j=p)dheadp-j = h1p-j=p-down;elsewhile(h1p-j-down&h1p-j-down-i != p-i)h1p-j = h1p-j-down;h1p-j-down = p-down;pb = pb-right;return TRUE;(4) 矩阵相减函数：实现两个稀疏矩阵的相减运算。bool CList:SubMatrix(CList &Matrix) /Subif (Matrix.rNum!=rNum|Matrix.dNum!=dNum)coutError Matrix dimension!endl;return FALSE;Node *pa,*pb,*pre;NLink *h1 = new NLinkdNum+1;int i,j;for (i=1;i=rNum;i+)for (j=1;jjpb-j)Node *p = new Node;p-i = pb-i;p-j = pb-j;p-e = -(pb-e);/更新行指针if (pre=NULL)rheadp-i = p;elsepre-right = p;p-right = pa;pre = p;/更新列指针if (dheadp-j=NULL|dheadp-j-ip-i)p-down = dheadp-j;dheadp-j = p;else while(h1p-j-down&h1p-j-down-i i) h1p-j = h1p-j-down;if (h1p-j-down=NULL)h1p-j-down=p;elsep-down = h1p-j-down;h1p-j-down = p;pb = pb-right;else if (pa!=NULL&pa-jj)pre = pa;pa = pa-right;else if (pa-j=pb-j)pa-e -= pb-e;if(pa-e=0)Node *p = new Node;/更新行指针if (pre=NULL)rheadpa-i = pa-right;elsepre-right=pa-right;p = pa;pa = pa-right;/更新列指针if (dheadp-j=p)dheadp-j = h1p-j=p-down;elsewhile(h1p-j-down&h1p-j-down-i != p-i)h1p-j = h1p-j-down;h1p-j-down = p-down;pb = pb-right;return TRUE;(5) 矩阵相乘函数：实现两个稀疏矩阵的相乘运算。bool CList:MultiMatrix(CList &Matrix,CList* &Result)int i,j;if (dNum!=Matrix.rNum)coutMatrix dimensions dont agree!rNum = rNum;Result-dNum =Matrix.dNum;Result-dhead = new NLinkMatrix.dNum+1;Result-rhead = new NLinkrNum+1;for (i=0;irheadi=NULL;for (i=0;idheadi=NULL;double* tmp = new doubleMatrix.dNum +1;Node *acur, *bcur;for (i=1;i=rNum;i+)for (j=1;jj;bcur=Matrix.rheadj;while (bcur)tmpbcur-j+=acur-e*bcur-e;bcur=bcur-right;acur=acur-right;for (j=1;jInsertNode(i, j, tmpj);delete tmp;return true;return TRUE;2. 主函数的实现：void main()char Operation;do coutOperation;coutendl;if (Operation = Q)break;if(Operation != + & Operation != - & Operation != *)continue;CList a;CList b;CList *c=NULL;coutPlease Enter Matrix A:endl;a.CreateMatrix();a.ShowMatrix();coutPlease Enter Matrix B:endl;b.CreateMatrix();coutB = endl;b.ShowMatrix();switch (Operation)case +:if (a.AddMatrix(b)coutendlA + B = endl;a.ShowMatrix();break;case -:if (a.SubMatrix(b)coutA - B = endl;a.ShowMatrix();break;case *:if (a.MultiMatrix(b,c)coutA * B = ShowMatrix();break; while