课程设计报告 十字链表

题目：（矩阵的加法运算问题）采用十字链表表示稀疏矩阵，并实现矩阵的加法运算。要求：要检查有关运算的条件，并对错误的条件产生报警。 一、问题分析和任务定义

本程序要求采用十字链表表示稀疏矩阵，并实现矩阵的加法运算，同时对错误的运算条件产生警报。

实现上述功能需要完成的关键问题有： 1、如何用十字链表表示一个稀疏矩阵。

2、如何对采用十字链表表示的两稀疏矩阵进行相加。 本程序中的稀疏矩阵采用十字链表表示，当6阶矩阵中的元素全为0时，十字链表为空，即十字链表中的所有表头指针结点都为空，其存储形式如图1所示（旁边数字表示对应指针数组的下标）。

列表头指针结点 C->chead[ ] 0 4 1 3 5 2 ∧ ∧ ∧ ∧ ∧ ∧ C->rhead[ ]

行 ＜ 0 表 头＜ 1 指 针 ＜ 2 结 点 ＜ 3 ＜ 4

＜ 5 图1 表示一个6阶稀疏矩阵元素全为0的十字链表

当一个6阶稀疏矩阵中有一个非0元素时（假设数值为5，行号为0，列号为0），则只需在上面的十字链表中相应的行链表和列链表中插入该非0元素结点，结果如图2所示。

由上得出，用十字链表表示一个含多个非0元素的稀疏矩阵时，即是将其中的非0元素依次插入一个空十字链表中，最后得到的就是表示该稀疏矩阵的十字链表。两稀疏矩阵相加时，将对应位置的相加后结果结点插入一个空十字链表中，最后得到的就是表示两稀疏矩阵相加后得到的稀疏矩阵的十字链表。 二、数据结构的选择和概要设计

本程序中的稀疏矩阵采用十字链表存储，现定义十字链表的数据类型： 在十字链表中，每一个非0元素用一个结点表示，结点中除了描述非0元素所在的行号i、列号j和数值data外，还有两个指针域：行指针域rptr和列指针域cptr。行指针域rptr 用来指向本行中的下一个非0元素，列指针域cptr用来指向本列中的下一个非0元素。结点结构如图3所示，结点类型描述如下： typedef struct node{

int i,j,data; //行、列、数值 node *rptr,*cptr; //行指针、列指针 }Lnode;

列表头指针结点

C->chead[ ] 0 2 4 1 3 5

∧ ∧ ∧ ∧ ∧ ∧ C->rhead[ ]

行 ＜ 0 0 5 0

表 ∧ ∧

头＜ 1

指

针

＜ 2

结

点 ＜ 3

＜

4 ＜ 5

图2 插入非0元素后的十字链表

i j data

cptr rptr 图3 十字链表的结点结构

由上可知，属于同一行的所有非0元素链接在一起（存储在一个单链表），属于同一列的所有非0元素链接在一起，因此为每一个行链表和列链表分别增加一个表头指针结点，十字链表的类型定义如下： typedef struct{ int m,n; //行数、列数 Lnode *rhead[M],*chead[N]; //行、列表头指针数组

}Crosslist; 若定义变量： Crosslist *C;

则一个十字链表由一个C指针唯一确定。 为实现上述功能：①建立两个十字链表存储两个稀疏矩阵。②判断该两个稀疏矩阵是否满足相加条件。若满足，将两稀疏矩阵相加并输出相加后的结果；否则进入选择菜单，重新输入矩阵或者退出程序。若选择重新输入矩阵，则继续执行上面的①②。

程序流程框图如图4所示。

main( ) 调用创建十字链表函数 存储矩阵A 重 新 输 调用创建十字链表函数 入 B 存储矩阵 矩 阵

N 判断是否满足相加 菜单选择 条件

Y 调用矩阵相加函数 退 出 程 序 调用输出函数，将相加 后的结果输出 结束

图4 流程框图

三、详细设计和编码

本程序主要实现两稀疏矩阵的相加，因此首先依次创建两个空十字链表，将输入的两稀疏矩阵的非0元素依次插入相应的空十字链表。

在利用十字链表存储稀疏矩阵时，由用户输入的稀疏矩阵的行（m）、列数（n）来确定十字链表的行与列表头指针数组的大小（Lnode *rhead[m],*chead[n]）。当用户输入一个稀疏矩阵后，由元素的输入顺序序号来求出该元素在矩阵中所在的行号和列号，并将非0元素插入十字链表中(在此用指针C确定一个十字链表，方便后面说明)：

for(k=0;km*C->n;k++){ scanf(\ a=k/C->m; //求行号

b=k%C->m; //求列号

if(d!=0){ } //将非0元素插入十字链表中 }

将非0元素的所有信息生成相应的结点L（结点结构如图3所示），并根据其行号和列号将该结点插入相应的行链表和列链表中。将该结点插入相应的行链表中时，首先查找到插入位置：如果相应的行链表为空，或者当前结点的列号比该行链表中第一个结点的列号小，则将该结点作为首元素结点插入到该行链表中：

bool done;

done= (C->rhead[L->i]==NULL||L->jrhead[L->i]->j); if(done){

L->rptr=C->rhead[L->i]; C->rhead[L->i]=L; }

否则，查找该行链表中的各结点的列号，将该结点按列号的顺序插入到该行链表中。 else{

p=C->rhead[L->i]; q=p->rptr;

while(q!=NULL){ if(L->jj) break; p=q; q=p->rptr; } p->rptr=L; L->rptr=q; }

将该结点插入相应的列链表中时，方法同上：如果相应的列链表为空，或者当前结点的行号比该列链表中第一个结点的行号小，则将该结点作为首元素结点插入到该列链表中；否则，查找该列链表中的各结点的行号，将该结点按行号的顺序插入到该列链表中。

两稀疏矩阵相加时，首先根据表示两稀疏矩阵的十字链表（用指针A和B表示）中的行号和列号信息来判断该两稀疏矩阵是否满足相加条件，若满足，进行相加运算;否则，进入选择菜单：重新输入矩阵和退出。

满足相加条件时（即两稀疏矩阵同行同列），逐个比较两个稀疏矩阵对应行a的行链表A-> rhead[a]与B-> rhead[a]上的每个结点*pl和*ql：

由于两矩阵同行，且行链表有多个，因此用一个for循环来控制两指针指向属于同行的行链表并实现逐行比较相加。

for(a=0;am;a++){ pl=A->rhead[a]; ql=B->rhead[a]; } 初始化指针pl和ql后，逐个比较行链表A->rhead[a]与B->rhead[a]上的每一个结点，直到两行链表中的所有非0元素结点均比较完毕：

⑴当A->rhead[a]与B->rhead[a]都为空时，若本行不是最后一行，则继续比较下一行。 ⑵当A->rhead[a]与B->rhead[a]都不为空时，比较结点*p1与结点*ql的列号：

①若结点*p1的列号等于结点*ql的列号，则将结点*p1的值与结点*ql的值相加，如果

相加的结果不等于0，则将结果信息生成的结点插入到一个新十字链表C中，方法同存储稀疏矩阵时向十字链表中插入非0元素结点，并修改指针pl和ql，将其指向下一个结点。如果相加的结果等于0，只需将指针pl和ql指向本身结点指向的下一个结点。

pl=pl->rptr; ql=ql->rptr;

②若结点*p1的列号小于结点*ql的列号，则直接将结点*p1插入到十字链表C中（方法同上），并修改指针p1，将其指向下一个结点。

③若结点*p1的列号大于结点*ql的列号，则直接将结点*ql插入到十字链表C中（方法同上），并修改指针ql，将其指向下一个结点。

⑶当A->rhead[a]与B->rhead[a]其中一个为空时，若结点*p1为空，则将结点*ql及其后面连接的所有结点插入十字链表C中。若结点*ql为空，则将结点*p1及其后面连接的所有结点插入十字链表C中。 四、上机调试

1、错误分析及改正：在本程序中将两矩阵进行逐行相加时，如输入的两个矩阵中有属于同一行的元素为2 3 1 2和4 0 0 0，运行程序后得到的相加结果为6 0 0 0，而正确的结果应该为6 3 1 2。程序中将上面两行元素进行相加时，首先分别从值为2的结点和值为4的结点的列号开始进行比较，由于这两个结点同行同列，所以将相加的结果插入一个十字链表中，然后它们下一个结点的列号。但由上可知，值为4的结点没有下一个结点，而原来程序中没有对这种情况的处理，直接比较下一行，因此导致相加结果为6 0 0 0。出现上述情况后，对原来程序进行改进，增加处理此种特殊情况，增加代码如下：

while(pl!=NULL){ //A矩阵中该行链表中的结点未比较完

x=pl; pl=pl->rptr; C=Insertlist(x,C); } while(ql!=NULL){ //B矩阵中该行链表中的结点未比较完 x=ql; ql=ql->rptr; C=Insertlist(x,C); }

2、时间、空间性能分析(以下出现的m表示一个矩阵的行数，n表示一个矩阵的列数)：本程序需要三个十字链表来存储进行相加的两稀疏矩阵和相加后的结果矩阵，每个十字链表都有行、列表头指针数组，所以最好情况下需要3*（m+n）个表头指针结点，最坏情况下需要3*(m+n)个表头指针结点和3*（m*n）链表结点。在成功申请十字链表内存空间后，都先需要对其行、列表头指针结点进行初始化，因此初始化的时间性能为O(m+n)。将稀疏矩阵存入十字链表中和将两矩阵进行相加过程都是对每个元素进行判断插入，所以最好情况下，两稀疏矩阵的元素都为0，此时只需判断，不需要进行插入操作。最坏情况下，两稀疏矩阵的元素都不为0，此时时间性能为O(m*n)。 五、测试结果及其分析

本文来源：https://www.bwwdw.com/article/fxoa.html