_数据结构课程设计-实现两稀疏矩阵的相加.doc

数据结构课程设计-实现两稀疏矩阵的相加 8 设计一 矩阵的运算 一、问题描述 采用十字链表表示稀疏矩阵,并实现矩阵的加法运算, 要求:要检查有关运算的条件,并对错误的条件产生报警。 二、 设计思路 本程序需要实现两稀疏矩阵的相加,如果用一般的数组存储矩阵,然后进行相加会很简单,但是当用十字链表表示稀疏矩阵并进行相加时,这时无疑就增加了难度。本程序通过手动输入两个任意大小的矩阵(两矩阵的大小需要一样)并输入相应位置的数值,当输入的两个矩阵的行数和列数不一样时,给出提醒输入错误。当两矩阵一样时,分别通过调用十字链表函数,建立十字链表分别存储两矩阵中数值的相关信息。在进行矩阵相加时,先比较两矩阵在相应的同一行或列是否同时有数值。要是都有数值时,再进行比较此行或列中的同一位置是否有数,有数则进行计算并将结果插入矩阵C的十字链表中,无数时则分别插入矩阵C的十字链表的相应位置。要是两矩阵在同一行或列不是同时有值,则将相应有数值的行或列直接插入C矩阵。 三、 数据结构定义 本程序中考虑的内容就是矩阵中的数的十字链表相加,通过十字链表节省存储空间,并且也减少了计算量。在该方法中稀疏矩阵的每个非零元素可用一个包含5个域的结点表示结点结构信息如下图所示: 除了表示非零元素所在行、列和值的三元组问题外,还增加了两个链域:指向本行中下一个非零元素行指针域cptr和指向本列的下一个非零元素列指针域rptr。 typedef struct lnode int i,j;//行坐标i,列坐标j struct lnode *cptr,*rptr; // *cptr指向本行下一个元素,*rptr指向本列下一个元素 union struct lnode *next; //指向下一行 datatype v;//存储稀疏矩阵该位置的数值uval; link; 系统功能模块介绍 五、 程序清单 #include #include #define s 45 typedef int datatype; typedef struct lnode int i,j; struct lnode *cptr,*rptr; union struct lnode *next; datatype v;uval; link; int flag0; link *creatlinkmat /*建立稀疏矩阵的函数,返回十字链表头指针*/ link *p,*q,*head,*cp[s]; int i,j,k,m,n,t,s; datatype v; printf行、列、非零元素个数空格分隔:; scanf%d %d %d,m,n,t; /*输入行、列,非零元素个数*/ ifmnsm; else sn; headlink *mallocsizeoflink; /*建立十字链表头结点*/ head-im;head-jn; cp[0]head; /*cp[]是指针数组,分别指向头结点和行、列表头结点*/ fori1;is;i++ /*建立头结点循环链表*/ plink *mallocsizeoflink; p-i0;p-j0; p-rptrp;p-cptrp; cp[i]p; cp[i-1]-uval.nextp; cp[s]-uval.nexthead;printf请输各个元素的行号、列号、值空格分隔:\n; fork1;kt;k++ printf 第%d个元素:,k; scanf%d %d %d,i,j,v; plink *mallocsizeoflink; p-ii; p-jj; p-uval.vv; qcp[i]; whileq-rptr!cp[i]q-rptr-jj -rptr;p-rptrq-rptr;q-rptrp;qcp[j]; whileq-cptr!cp[j]q-cptr-ii -cptr; p-cptrq-cptr; q-cptrp; return head; void insertint i,int j,int v,link *cp[] /*插入结点函数*/ link *p,*q; plink *mallocsizeoflink; p-ii;p-jj;p-uval.vv; /*以下是经*p结点插入第i行链表中 */qcp[i]; whileq-rptr!cp[i]q-rptr-jj -rptr; /*在第i行中找第一个列号大于j的结点*q-rptr*/ /*找不到时,*q是该行表上的尾结点*/ p-rptrq-rptr; q-rptrp;/* *p插入在*q之后 */ /*以下是将结点插入第j列链表中*/ qcp[j];//取第j列表头结点 whileq-cptr!cp[j]q-cptr-ii -cptr ; /*在第j行中找第一个