资源描述：
《_数据结构课程设计-实现两稀疏矩阵地相加.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、数据结构课程设计-实现两稀疏矩阵的相加《数据结构》课程设计报告学号姓名赵立兵班级软1042班指导教师安徽工业大学计算机学院2012年6月目录设计一矩阵的运算????????????????????????????????02设计二迷宫求解??????????????????????????????????11设计三学生成绩查询系统??????????????????????????21设计四构造n个城市连接的最小生成树????????????28设计一矩阵的运算一、问题描述采用十字链表表示稀疏矩阵,并实现矩阵的加法运算,要求:要检查有关运算的条件,并对错误的条件产生报
2、警。二、设计思路本程序需要实现两稀疏矩阵的相加,如果用一般的数组存储矩阵,然后进行相加会很简单,但是当用十字链表表示稀疏矩阵并进行相加时,这时无疑就增加了难度。本程序通过手动输入两个任意大小的矩阵(两矩阵的大小需要一样)并输入相应位置的数值,当输入的两个矩阵的行数和列数不一样时,给出提醒输入错误。当两矩阵一样时,分别通过调用十字链表函数,建立十字链表分别存储两矩阵中数值的相关信息。在进行矩阵相加时,先比较两矩阵在相应的同一行或列是否同时有数值。要是都有数值时,再进行比较此行或列中的同一位置是否有数,有数则进行计算并将结果插入矩阵C的十字链表中,无数时则分别插入矩阵C的
3、十字链表的相应位置。要是两矩阵在同一行或列不是同时有值,则将相应有数值的行或列直接插入C矩阵。三、数据结构定义本程序中考虑的内容就是矩阵中的数的十字链表相加,通过十字链表节省存储空间,并且也减少了计算量。在该方法中稀疏矩阵的每个非零元素可用一个包含5个域的结点表示结点结构信息如下图所示:除了表示非零元素所在行、列和值的三元组问题外,还增加了两个链域:指向本行中下一个非零元素行指针域cptr和指向本列的下一个非零元素列指针域rptr。typedefstructlnodeinti,j;//行坐标i,列坐标jstructlnode*cptr,*rptr;//*cptr指向本
4、行下一个元素,*rptr指向本列下一个元素unionstructlnode*next;//指向下一行datatypev;//存储稀疏矩阵该位置的数值uval;link;系统功能模块介绍五、程序清单#include#include#defines45typedefintdatatype;typedefstructlnodeinti,j;structlnode*cptr,*rptr;unionstructlnode*next;datatypev;uval;link;intflag0;link*creatlinkmat/*建立稀疏矩阵的函数,返回十字链表头指针*/link*
5、p,*q,*head,*cp[s];inti,j,k,m,n,t,s;datatypev;printf"行、列、非零元素个数空格分隔:";scanf"%d%d%d",&m,&n,&t;/*输入行、列,非零元素个数*/ifmnsm;elsesn;headlink*mallocsizeoflink;/*建立十字链表头结点*/head-im;head-jn;cp[0]head;/*cp[]是指针数组,分别指向头结点和行、列表头结点*/fori1;is;i++/*建立头结点循环链表*/plink*mallocsizeoflink;p-i0;p-j0;p-rptrp;p-cpt
6、rp;cp[i]p;cp[i-1]-uval.nextp;cp[s]-uval.nexthead;printf"请输各个元素的行号、列号、值空格分隔:";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-c
7、ptr;q-cptrp;returnhead;voidinsertinti,intj,intv,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列链表
