矩阵的加减法.doc
14页
合肥学院计算机科学与技术系课程设计报告2008～2009 学年第二学期课程 数据结构与算法课程设计名称矩阵的加法运算问题学生姓名杨扬学号0704032039专业班级07网络工程(2)指导教师张贯虹 屠菁 2009年6月题目：（矩阵的加法运算问题）设计程序完成如下要求：采用十字链表表示稀疏矩阵，并实现矩阵的加法运算要求：要检查有关运算的条件，并对错误的条件产生报警一、问题分析和任务定义此程序需要完成如下要求：使用十字链表存储结构存储稀疏矩阵并实现两个矩阵的相加运算实现本程序需要解决一下几个问题：1、如何用一个十字链表来表示稀疏矩阵2、十字链表如何创建3、如何实现稀疏矩阵的加法运算4、对错误的条件产生警报5、如何把矩阵输出本问题的关键和难点在于编写算法实现两个稀疏矩阵的相加运算使得相加后的矩阵仍然是稀疏矩阵在链表中，每个非0元素可用一个含有五个域的结点表示： ijvcptrrptr 图1 十字链表结点结构 其中：i , j ,v 三个域分别表示该元素所在的行、列和非0元素的值。
行指针域 rptr 用以链接同一行中下一个非0元素；列指针域 cptr 用以链接同一列中下一个非0元素存储时，每个非0元既是某个行链表中的一个结点，又是某个列链表中的一个结点；整个矩阵构成了一个十字交叉的链表,如下图： ∧∧∧∧∧∧ Ｍ－＞rhead[ ] M－＞chead[ ] 图2 稀疏矩阵的十字链表存储示例 可用两个分别存储行链表M－＞rhead[]和列链表M－＞chead[]的头指针的一维数组表示十字链表。
使用十字链表建立稀疏矩阵后就是矩阵相加的运算问题对于稀疏矩阵来说，其存储结构决定了它不可以按照普通矩阵的加法来运算对于两个稀疏矩阵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类型的一维指针数组rhead[m]和chead[n]来表示所有的行链表和列链表这两个指针数组及稀疏矩阵中非零元素个数t一起构成crosslist类型为了实现两个矩阵相加的功能需要创建十字链表M，然后用M来存储矩阵A和矩阵B。
判断A、B两个矩阵是否满足相加条件，如果可以相加则逐个比较两个矩阵对应i的行链表A->rhead[i]与B->rhead[i]上的每一个结点*a和*b：若两个结点的列号相同（a->j=b->j），则将它们值域中的内容相加（a->=a->v+b->v）；若它们的和a->v等于0，则将结点*a从行链表A->rhead[i]及相应的列链表中删除若行链表B->rhead[i]上结点*b的列号小于行链表A->rhead[i]上结点*a的列号，则将结点*b插到行链表A>rhead[i]上结点*a之前根据结点*b的列号将其插入到十字链表A合适的列链表中若行链表B->rhead[i]上结点*b的列号大于行链表A->rhead[i]上结点*a的列号，则令a=a->rptr，并重复以上步骤直到对应的链表比较完毕另外，为便于插入与删除结点，还应设立一些辅助指针；在A的行链表上设置一个pre指针，使其指向*a的前驱结点；在A的每一个列链表上设置一个指针acol[j]，它的初始值与列链表的头指针相同，即acol[j]= A->rhead[i]另外题目要求要检查有关运算的条件，并对错误的条件产生报警这里判断矩阵是否可以相加的条件，需要用到线性代数中矩阵能够相加的条件即：两个待加的矩阵具有相同的行数和列数。
因此可已在矩阵执行相加函数前调用判断函数经行判断，符合相加条件则执行相加算法；不符合则提示出错并提供修改的操作三、详细设计和编码、本程序十字链表的建立和相加算法为设计的核心内容十字链表创建的过程可描述如下：首先申请一个存放crosslist类型的数据所需要的存储空间这包括存放各行链表列链表首元素结点地址的行、列指针数组的空间，以及存放稀疏矩阵的非0元素个数所需的存储空间 M=(crosslist *)malloc(sizeof(crosslist));接下来，分别给M->m、M->n、 M->t、M-> rhead[K]、 M-> rhead[N]赋值： scanf("%d%d%d",&(M->m),&(M->n),&(M->t)); for(i=0;i
if((M->rhead[p->i]==NULL)||((M->rhead[p->i]->j)>(p->j))){ p->rptr=M->rhead[p->i]; M->rhead[p->i]=p;}否则，查找该行链表中的各结点的列号。
