塔里木大学信息工程学院课程设计
目录
前言................................................................ 1 正文................................................................ 1
1.课程设计的目的和任务 .......................................... 1 2.课程设计报告的要求 ............................................ 1 3.课程设计的内容 ................................................ 2 4.稀疏矩阵的十字链表存储 ........................................ 2 5.稀疏矩阵的加法思想 ............................................ 4 6.代码实现 ...................................................... 5 7.算法实现 ...................................................... 5 结论................................................................ 8 参考文献............................................................ 9 附录............................................................... 10
塔里木大学信息工程学院课程设计
前言
采用三元组顺序表存储稀疏矩阵，对于矩阵的加法、乘法等操作，非零元素的插入和删除将会产生大量的数据移动，这时顺序存储方法就十分不便。稀疏矩阵的链接存储结构称为十字链表，它具备链接存储的特点，因此，在非零元素的个数及位置都会发生变化的情况下，采用链式存储结构表示三元组的线性更为恰当。
正文
1.课程设计的目的和任务
(1) 使我我们进一步理解和掌握所学的程序的基本结构。 (2) 使我们初步掌握软件开发过程的各个方法和技能。 (3) 使我们参考有关资料，了解更多的程序设计知识。
(4) 使我们能进行一般软件开发，培养我们的能力并提高我们的知识。
2.课程设计报告的要求
(1)课程设计目的和任务，为了达到什么要求 (2)课程设计报告要求
(3)课程设计的内容，都包含了什么东西
(4)稀疏矩阵和十字链表的基本概念，稀疏矩阵是怎么用十字链表存储 (5)十字链表矩阵的加法 (6)代码实现 (7)算法检测
第1页，共15页
塔里木大学信息工程学院课程设计
3.课程设计的内容
(1)根据所学知识并自主查找相关资料 (2)进行算法设计与分析
(3)代码实现，组建并运行结果查看是否正确 (4)书写课程设计说明书
4.稀疏矩阵的十字链表存储
稀疏矩阵是零元素居多的矩阵，对于稀疏矩阵，人们无法给出确切的概念，只要非零元素的个数远远小于矩阵元素的总数，就可认为该矩阵是稀疏的。
十字链表有一个头指针hm，它指向的结点有五个域，如图1所示。row域存放总行数m，col域存放总列数n，down和right两个指针域空闲不用，next指针指向第一个行列表头结点。
rowcolnextmn 图1 总表点结点
有S个行列表头结点h[1]，h[2]，......h[s]。结点结构与总表头结点相同。Row和col域置0，next指向下一行列表头结点，right指向本行第一个非零元素结点，down指向本列第一个非零元素结点如图2所示。当最后一个行列表头结点的next域指向总表头结点的hm时，就形成循环链表，见图4的第一行。
第2页，共15页
塔里木大学信息工程学院课程设计
Nextoodown图2 行列表头结点
right
Nextoodown 图3 非零元素结点
right
?3?0?A??2??0??0
007?0?10??000?? 图4 稀疏矩阵
000?00?3??非零元素结点结构也有五个域，与其他结点域结构相似，只有next域为一变体域，可为val域存放非零元素的值，row和col存放行下标值和列下标值，right指向本行的下一个非零元素结点，down指向本列的下一个非零元素结点。稀疏矩阵中同一行的非零元素通过向右域right，链接成一个带头结点的循环链表。同一列的非零元素也通过向下域down。链接成一个带头结点的循环链表。因此，每一个非零元素即是第i行循环链表中的一个结点，又是第j列循环链表中的一个结点。这好比处于一个十字交叉路口上，故称这样的链表为十
第3页，共15页
塔里木大学信息工程学院课程设计
字链表。例如，对于如图4所示的5行4列的稀疏矩阵A的十字链表如图5所示。
如图5可见，每一列链表的表头结点只需要用一个链域，指向该列中第一个非零元素，而每一行链表的表头结点只需right链域，指向该行中第一个非零元素，恰好他们的row和col域又同时为0，故这两组的表头结点可以合用（即第i行链表和第j列链表共用一个表头结点）这些表头结点本身又可以通过val域相链接（注意：val域在表头结点中为next域，是指向下一个表头结点的链域），加上附加结点（由指针hm指示），又组成一个带表头结点的循环链。Hm所指结点为整个十字链表的表头结点，其row和col域的值分别为稀疏矩阵的行数和列数，hm为头指针。由此，只要给定hm指针值，便可取得整个稀疏矩阵的全部信息。
h[1]54h[2]0 h[3]0 h[4]0h[5]00hm00000h[1]00 11 3147h[2]00 23-1h[3]00 312h[4]00 h[5]00 54-3图5 稀疏矩阵A的十字链表
5.稀疏矩阵的加法思想
如果运用带行指针向量和带列指针向量的存储结构进行系数矩阵的加法运算，设M和N是两个加法矩阵，Q是和矩阵，也就是结果矩阵。M和N矩阵可以相加的前提条件是：M和N矩阵是一样的，也就是说行数和列数的个数相同，M和N相加的结果矩阵就是一个一样大小的矩阵。结果矩阵中每个行单链表也还是需要列号有序，它是对M和N中对应行单链表的按列号有序的合并结果。当M和N中相应的行单链表的两个结点分别是一样的行号
第4页，共15页
稀疏矩阵的十字链表加法
