矩阵的加减法

合肥学院计算机科学与技术系课程设计报告20082009 学年第二学期课程 数据结构与算法课程设计名称矩阵的加法运算问题学生姓名杨扬学号0704032039专业班级07网络工程(2)指导教师张贯虹 屠菁 2009年6月题目：（矩阵的加法运算问题）设计程序完成如下要求：采用十字链表表示稀疏矩阵，并实现矩阵的加法运算。要求：要检查有关运算的条件，并对错误的条件产生报警。一、问题分析和任务定义此程序需要完成如下要求：使用十字链表存储结构存储稀疏矩阵并实现两个矩阵的相加运算。实现本程序需要解决一下几个问题：1、如何用一个十字链表来表示稀疏矩阵。2、十字链表如何创建。3、如何实现稀疏矩阵的加法运算。4、对错误的条件产生警报。5、如何把矩阵输出。本问题的关键和难点在于编写算法实现两个稀疏矩阵的相加运算使得相加后的矩阵仍然是稀疏矩阵。在链表中，每个非0元素可用一个含有五个域的结点表示： ijvcptrrptr 图1 十字链表结点结构 其中：i , j ,v 三个域分别表示该元素所在的行、列和非0元素的值。行指针域 rptr 用以链接同一行中下一个非0元素；列指针域 cptr 用以链接同一列中下一个非0元素。存储时，每个非0元既是某个行链表中的一个结点，又是某个列链表中的一个结点；整个矩阵构成了一个十字交叉的链表,如下图： rhead Mchead 图2 稀疏矩阵的十字链表存储示例 可用两个分别存储行链表Mrhead和列链表Mchead的头指针的一维数组表示十字链表。使用十字链表建立稀疏矩阵后就是矩阵相加的运算问题。对于稀疏矩阵来说，其存储结构决定了它不可以按照普通矩阵的加法来运算。对于两个稀疏矩阵A、B相加，每个位置（i，j）上的和只可能有三种情况：aij+bij、aij（bij=0）、bij (aij =0)。可以将稀疏矩阵Bm*n加到稀疏矩阵Am*n上，若aij+bij不等于0，则只需改变aij的值；若aij+bij等于0，则应从十字链表A中删除aij对应的结点;若和值为bij，则只需在十字链表A中添加一个结点。为实现该过程可以从矩阵的第一行逐行进行。二、数据结构的选择和概要设计十字链表使用的是链接存储的方式。其结点类型为olnode，每个结点中除了描述非0元素所在的行号i、列号j、及非0元素的值v以外，还有两个指针域；行指针域rptr和列指针域cptr。行指针域 rptr 用以链接同一行中下一个非0元素；列指针域 cptr 用以链接同一列中下一个非0元素。在十字链表用以olnode类型的一维指针数组rheadm和cheadn来表示所有的行链表和列链表。这两个指针数组及稀疏矩阵中非零元素个数t一起构成crosslist类型。为了实现两个矩阵相加的功能需要创建十字链表M，然后用M来存储矩阵A和矩阵B。判断A、B两个矩阵是否满足相加条件，如果可以相加则逐个比较两个矩阵对应i的行链表A-rheadi与B-rheadi上的每一个结点*a和*b：若两个结点的列号相同（a-j=b-j），则将它们值域中的内容相加（a-=a-v+b-v）；若它们的和a-v等于0，则将结点*a从行链表A-rheadi及相应的列链表中删除。若行链表B-rheadi上结点*b的列号小于行链表A-rheadi上结点*a的列号，则将结点*b插到行链表Arheadi上结点*a之前。根据结点*b的列号将其插入到十字链表A合适的列链表中。若行链表B-rheadi上结点*b的列号大于行链表A-rheadi上结点*a的列号，则令a=a-rptr，并重复以上步骤直到对应的链表比较完毕。另外，为便于插入与删除结点，还应设立一些辅助指针；在A的行链表上设置一个pre指针，使其指向*a的前驱结点；在A的每一个列链表上设置一个指针acolj，它的初始值与列链表的头指针相同，即acolj= A-rheadi。另外题目要求要检查有关运算的条件，并对错误的条件产生报警。这里判断矩阵是否可以相加的条件，需要用到线性代数中矩阵能够相加的条件即：两个待加的矩阵具有相同的行数和列数。因此可已在矩阵执行相加函数前调用判断函数经行判断，符合相加条件则执行相加算法；不符合则提示出错并提供修改的操作。三、详细设计和编码、本程序十字链表的建立和相加算法为设计的核心内容。十字链表创建的过程可描述如下：首先申请一个存放crosslist类型的数据所需要的存储空间。这包括存放各行链表列链表首元素结点地址的行、列指针数组的空间，以及存放稀疏矩阵的非0元素个数所需的存储空间。M=(crosslist *)malloc(sizeof(crosslist);接下来，分别给M-m、M-n、 M-t、M- rheadK、 M- rheadN赋值：scanf(%d%d%d,&(M-m),&(M-n),&(M-t);for(i=0;im;i+)M-rheadi=NULL;for(i=0;in;i+)M-cheadi=NULL;然后，输入所有的非0元素的三元组，生成相应的结点，并根据其行号将该结点插入到相应的行链表中：p=(olnode *)malloc(sizeof(olnode);scanf(%d%d%d,&(p-i),&(p-j),&(p-v);如果该行链表为空，或者当前结点的列号比该行链表中第一个结点的列号小，则将该结点作为首元素结点插入到该行链表中。if(M-rheadp-i=NULL)|(M-rheadp-i-j)(p-j)p-rptr=M-rheadp-i;M-rheadp-i=p;否则，查找该行链表中的各结点的列号，将该结点按列号的顺序插入到该行链表中。elseu=M-rheadp-i;q=M-rheadp-i-rptr;while(q!=NULL)if(q-jp-j)break;u=q;q=q-rptr;p-rptr=q;u-rptr=p;将该结点插入到相应的列链表中。如果该列链表为空，或者当前结点的行号比该列链表中第一个结点的行号小，则将该结点作为首元素结点插入到该列链表中。if(M-cheadp-j=NULL|M-cheadp-j-ip-i)p-cptr=M-cheadp-j;M-cheadp-j=p;否则，查找该列链表中的各结点的行号，将该结点按行号的顺序插入到该列链表中。elseu=M-cheadp-j;q=M-cheadp-j-cptr;while(q!=NULL)if(q-ip-i)break;u=q;q=q-cptr;p-cptr=q;u-cptr=p; 用十字链表存储矩阵只是为矩阵的相加提供了可操作的条件，接下来便是执行矩阵的加法算法实现两矩阵的相加。令a和b分别指向A和B的第一行链表：a=A-rheadi;b=B-rheadi;pre=NULL;并且初始化指针acol for(i=1;in;i+)acoli=A-cheadi;逐个比较行链表A-rheadi与B-rheadi上的每一个结点*a和*b，直到链表B-rheadi中所有非0元素结点均比较完毕。若链表A-rheadi已比较完毕，或者结点*b的列号小于结点*a的列号，则在链表A-rheadi中插入一个*b的复制结点：if(a=NULL|a-jb-j)if(pre=NULL)A-rheadi=p;else pre-rptr=p;p-rptr=a;pre=p; 同时，结点*p也应插入到相应的列链表中。P-j是*p结点的列号，应将它插入到列链表A-cheadp-j中。i是*p结点的行号，应从acolp-j开始查找*p结点在列链表A-cheadp-j中的前驱结点，并将*p结点插入到相应位置：if(A-cheadp-j=NULL|A-cheadp-j-ii)p-cptr=A-cheadp-j;A-cheadp-j=p;elseif(acolp-j!=NULL)while(acolp-j-cptr!=NULL&acolp-j-cptr-ij=acolp-j-cptr;p-cptr=acolp-j-cptr;acolp-j-cptr=p; else acolp-j=p; acolp-j=p;若结点*b的列号大于结点*a的列号，则在链表A-rheadi中查找列号大于*b的列号的结点的前驱结点，并插入一个*b的复制结点*p；即若*a的后继结点的列号大于*b的列号，则将*p插入到*a后：while(a!=NULL&a-jj)pre=a;a=a-rptr; pre-rptr=p;p-rptr=a;pre=p;同时，结点*p也应插入到相应的列链表中。若结点*b的列号等于结点*a的列号，将*b结点的值加到*a结点上：if(a!=NULL&a-j=b-j)a-v=a-v+b-v;此时若a-v!=0，则无需其它操作；否则，在十字链表A中删除该结点。在行链表中删除该结点：if(pre=NULL)A-rheadi=a-rptr;else pre-rptr=a-rptr;p=a;a=a-rptr同时，在列链表A-cheadp-j中删除该结点：if(A-cheadp-j=p)A-cheadp-j=p-cptr;acolp-j=p-cptr; elsewhile(acolp-j-cptr!=p)acolp-j=acolp-j-cptr;acolp-j-cptr=p-cptr; free(p);若本行不是最后一行，则令a和b指向下一行行链表的首元素结点，重复上述算法；否则，结束算法。四、上机调试1、语法错误及修改：本程序使用到的变量很多即有循环控制变量又有矩阵元素下标、矩阵非零元素个数等。故在编程时出现了多次变量使用不当和未事先声明的错误，经过编译器的提示修改后更正。另外程序中使用的指针也较为复杂，时常有指针指向的空间不存在或者从空的地址里提取数据等情况，在修改了编译器里提示的简单错误并加入对指针判断是否为空的语句后程序得以运行。2、逻辑问题修改和调整：程序调试无误后运行程序，进入测试数据阶段。输入数据时出现程序出错突然终止运行的情况。检查数据是否输入有误，发现数据输入无误。更换其它数据输入仍然出现上述情况。分析原因，可能是创建十字链表的算法出错，找到创建十字链表的源代码带入数据进行手工运行。在调试中发现，用于表示矩阵的行列链表一维数组首元素均以0开始，而矩阵中的各元素下标均以1开始，这样便产生了输入时程序内部的混乱。这样的错误属于算法错误在语法上检查不出来。修改方法，将行列链表一维数组首元素均以1开始与矩阵中的各元素下标保持一致。再次运行程序，顺利的建立了以十字链表为存储结构的稀疏矩阵。但是当运行矩阵相加时又出现了程序突然终止的情况。有了上次调试的经验分析原因，又是算法的逻辑问题出现了错误且出错的地方为十字链表相加的算法函数。因为十字链表相加函数十分复杂，带入数据手工运行工作量太大，而且编程时是按照参考书上的算法描述来写的程序因此，在算法上不太可能又严重的错误。出错的原因可能在某些局部地方出错，例如指针的地址，循环的结束，判断的条件等地方出错。输入数据利用编译器自带的调试功能进行调试，找到出错的位置，再分析错误的原因。经多次输入不同的数据调试后发现在判断结点*a和*b的列号是否相同时，没有对结点*a地址是否为空时进行判断，若果*a地址为空，则这条判断语句就出错无法运行，最终导致程序出错。加入判断*a地址为空的语句及为空时程序执行下面的语句的语句后，使得矩阵相加输出正确的结果。另外发现两个矩阵的某行首元素经过相加后得到的数值为零时，程序将首链表结点删除而导致该行后面的运算出现了错误。经过认真分析算法后加入了判断首地址在相加后是否变为空的语句后，问题得以解决。3、时间，空间性能分析：本程序的空间复杂度主要用于存放十字链表结点的空间和十字链表中行链表和列链表的一维数组的空间。故空间复杂度O(2t+2i+2j)，其中t为稀疏矩阵中非零元素个数，i为稀疏矩阵的行数，j为稀疏矩阵的列数。由于使用十字链表作为存储结构，这样相对于用普通的二维数组来存储矩阵的方法节省了大量的空间。另外相加后的矩阵是在A矩阵基础上得到的未开辟新的存储空间，这样又节省了空间。本程序的时间性主要在于建立十字链表的算法时间复杂度和矩阵相加算法的时间复杂度。建立十字链表的算法时间复杂度为O(t*x)，其中t为稀疏矩阵中非零元素个数，x为稀疏矩阵中行数和列数较大的值。矩阵相加算法的时间复杂度主要耗费在对十字链表A、B进行逐行扫描上，循环次数主要取决于矩阵A、B中非零元素的个数A-t和B-t。因此，算法的时间复杂度为O(A-t+B-t)。五、用户使用说明运行程序后进入菜单界面，本程序提供了如下操作：1-运行程序、2-数据清零、3-使用说明、4-退出程序。输入阿拉伯数字选择对应的功能。选择1则进入矩阵相加模块，首先输入矩阵A的行数、列数、非零元素个数，行数、列数、非零元素个数以空格隔开；然后输入矩阵各元素的行标、列表、数值，行标、列表、数值以空格隔开，按回车键输入下个元素；再输入矩阵B，输入的方法同上；最后按回车键查看相加结果。选择2将程序中所申请的空间释放，数值清零，便于下次运行程序。选择3查看使用说明，这里不再赘述。选择4则退出程序。六、测试结果测试数据：矩阵A： 0 1 0 2 0 -1 1 2 3矩阵B： 0 0 2 -1 0 1 0 -2 0矩阵C=A+B： 0 1 2 1 0 0 1 0 3测试结果截图如下：图3程序运行一以下演示程序对错误条件产生报警的截图：图4程序运行二七、参考文献【1】. 王昆仑，李红。数据结构与算法.北京：铁道工业出版社，2007年6月第一版八、附录#include #include using namespace std;#define K 50 /预设稀疏矩阵的行数#define N 50 /预设稀疏矩阵的列数#define NULL 0typedef struct node int i,j,v; /元素的行标、列标、值域struct node *rptr,*cptr;/行指针域、列指针域olnode; /结点类型typedef struct olnode *rheadK,*cheadN;/一维数组存放行链表及列链表的首地址int m,n,t; /矩阵的行数、列数、非零元素个数crosslist; /十字链表类型crosslist *creatcross()/创建空十字链表crosslist *M;/声明变量M=(crosslist *)malloc(sizeof(crosslist);/为十字链表申请空间coutM-mM-nM-t;while(M-t(M-m*M-n) /判断矩阵是否符合要求cout不符合相加条件!endlM-mM-nM-t;return M; /返回空十字链表地址crosslist *creatcross2(crosslist *M)/为十字链表赋值存放稀疏矩阵olnode *p,*q,*u; /申请元素结点类型的变量int i,h;for(i=1;im;i+)/行链表置空M-rheadi=NULL;for(i=1;in;i+)M-cheadi=NULL;/列链表置空for(h=1;ht;h+)/给十字链表中元素赋值p=(olnode *)malloc(sizeof(olnode);/申请结点类型的空间赋值给cout第hp-ip-jp-v;while(p-iM-m|p-jM-n)/判断输入是否符合要求cout*重新输入第hp-ip-jp-v;if(M-rheadp-i=NULL)|(M-rheadp-i-j)(p-j)/当该元素所在的行首地址为空或当前结点的列号比该列行链表中第一个结点的行号小p-rptr=M-rheadp-i;/将该结点作为首元素结点插入到该行链表中M-rheadp-i=p;else /否则，查找该行链表中的个结点的列号，将该结点按列号的顺序插入到该行链表中u=M-rheadp-i;q=M-rheadp-i-rptr;while(q!=NULL) /指针后移找到比待插入结点列号大的元素地址if(q-jp-j)break;u=q;q=q-rptr;p-rptr=q;/插入结点u-rptr=p;if(M-cheadp-j=NULL)|(M-cheadp-j-i)(p-i)/根据列号将该结点插入到相应的列链表中p-cptr=M-cheadp-j;M-cheadp-j=p;elseu=M-cheadp-j;q=M-cheadp-j-cptr;while(q!=NULL)if(q-ip-i)break;u=q;q=q-cptr;p-cptr=q;u-cptr=p;return M;/返回十字链表首地址crosslist *matrixpuls(crosslist *A,crosslist *B) /矩阵相加函数olnode *a,*b,*p,*pre,*acolN; /结点类型的指针变量，*a为A矩阵中的结点，*b为B矩阵中的结点，*pre是指向*a的前驱结点int i;for(i=1;in;i+)/在矩阵A的每一个列链表上设置一个指针acoli，它的初始值与列链表的头指针相同acoli=A-cheadi;for(i=1;im;i+)a=A-rheadi; /将第i行的首地址赋给ab=B-rheadi; /将第i行的首地址赋给bpre=NULL; while(b!=NULL) /当结点b的地址不为空时执行下面循环if(a!=NULL&a-j=b-j)/如果两结点列号相同a-v=a-v+b-v; /将a、b结点的值域相加并赋给aif(a-v=0) /若相加后为值为0if(pre=NULL) /a的前驱为空时A-rheadi=a-rptr;/将a结点删除else pre-rptr=a-rptr;/否则，将a的前驱后移一位p=a;/p指向被删除的结点a=a-rptr;/a后移一位if(A-cheadp-j=p)/p指向的结点为所在列的首元素时A-cheadp-j=p-cptr;/将p从列链表中删除acolp-j=p-cptr;else /否则，找到p所在列链表的前驱结点while(acolp-j-cptr!=p)acolp-j=acolp-j-cptr;acolp-j-cptr=p-cptr;/将p从列链表中删除free(p);/释放p指向结点的空间else /若相加后为值不为0pre=a;/pre指向aa=a-rptr;/a后移一位else /如果两结点列号不相同p=(olnode *)malloc(sizeof(olnode);/为p申请空间并将b结点复制给pp-i=b-i;p-j=b-j;p-v=b-v;if(a=NULL|a-jb-j)/若a地址为空或列号大于b的列号if(pre=NULL) /a的前驱为空时 A-rheadi=p;/将p插入到该行头结点之前else pre-rptr=p; /否则，将p插到a结点之前p-rptr=a; pre=p; /a的前驱变为p结点else /否则，找到列标大于b结点的a结点while(a!=NULL&a-jj)pre=a;a=a-rptr;if(a=NULL|a-jb-j)/若a地址为空或列号大于b的列号 pre-rptr=p;/将p插到a结点之前 p-rptr=a; pre=p;/a的前驱变为p结点else/否则两结点列号相同 a-v=a-v+b-v;/将两节点数值相加赋给a if(a-v=0)/若相加后为值为0 if(pre=NULL)/a的前驱为空时 A-rheadi=a-rptr;/将a结点删除 else pre-rptr=a-rptr;/否则，将a的前驱后移一位 p=a;/p指向被删除的结点 a=a-rptr;/a后移一位 if(A-cheadp-j=p)/p指向的结点为所在列的首元素时 A-cheadp-j=p-cptr;/将p从列链表中删除acolp-j=p-cptr;else /否则，找到p所在列链表的前驱结点 while(acolp-j-cptr!=p) acolp-j=acolp-j-cptr; acolp-j-cptr=p-cptr;/将p从列链表中删除free(p);/释放p指向结点的空间 else /若相加后为值不为0 pre=a;/pre指向a a=a-rptr;/a后移一位break;if(A-cheadp-j=NULL|A-cheadp-j-ii)/若p结点所在的列首地址为空或p的行标比首节点的行标小p-cptr=A-cheadp-j;/将p插到首结点之前A-cheadp-j=p;/该列的首地址为变pelse /否则，当若p结点所在的列首地址不为空时if(acolp-j!=NULL)while(acolp-j-cptr!=NULL&acolp-j-cptr-ij=acolp-j-cptr;p-cptr=acolp-j-cptr;/将p插到该结点之前acolp-j-cptr=p;else /当若p结点所在的列首地址为空时acolp-j=p;/将p结点作为该列首元素acolp-j=p;/将p结点作为该列首元素b=b-rptr;/b结点向后移一位return A;/返回十字链表首地址int panduan(crosslist *A,crosslist *B)/判断矩阵是否符合相加条件if(A-m=B-m&A-n=B-n)return 0;/符合返回0else return 1;/不符合返回1void main()/主函数crosslist *A,*B,*C;olnode *p;int i,Y;char r;while(Y!=4)/菜单coutendl;coutendl;couttt*欢迎使用矩阵相加程序*endl;coutendl; coutendl; coutendl;coutendl; couttt 1-运 行 程 序endl;couttt 2-数 据 清 零endl;couttt 3-使 用 说 明endl; couttt 4-退 出 程 序endl;coutendl;coutendl;coutendl;coutendl;couttt*endl;cout;cinY;switch(Y)case 1: /矩阵相加模块cout输入矩阵A:endl;A=creatcross(); /建立矩阵A creatcross2(A); /输入A中元素cout输入矩阵B:endl;B=creatcross(); /建立矩阵Bwhile(panduan(A,B)/判断是否符合相加条件cout不符合相加条件!endlr;if(r=A) /修改矩阵Afree(A);A=creatcross();if(r=B) /修改矩阵Bfree(B);B=creatcross(); creatcross2(B); /输入矩阵B中元素C=matrixpuls(A,B);/调用矩阵相加函数cout输出矩阵C=A+B:endl;/输出相加后的矩阵for(i=1;im;i+)p=C-rheadi;if(p!=NULL)docouti,j,v;p=p-rptr;while(p!=NULL);coutendl;break;case 2: /矩阵A、B地址清零模块free(A);free(B);break;case 3: /使用说明模块cout首先输入矩阵A的行数、列数、非零元素个数，行数、列数、非零endl; cout元素个数以空格隔开；然后输入矩阵各元素的行标、列表、数值，endl;cout行标、列表、数值以空格隔开，按回车键输入下个元素；再输入矩endl; cout阵B，输入的方法同上；最后按回车键查看相加结果。endl;break;case 4: /结束程序模块cout谢谢使用;break;