数据结构课程设计(十字链表)

中南民族大学

数据结构呈设计报告

姓名：康宇

年级：

学号：

专业：计算机科学与技术

指导老师：宋中LD

2022年4月15日

1

实习报告：十字链表

实习报告

题目：设计一个用十字链表实现稀疏矩阵相加的程序

班级：计科一班姓名：康宇学号：完成日期：

一、需求分析、

十字链表分析：

当矩阵的非零元个数和位置在操作过程中变化较大时，就不宜采用顺序存储结

构来表示三元组的线性表。例如，在作“将矩阵加到矩阵上”的操作时，由于

非零元的插入或者删除将会引起中元素的挪移。为此，对这种类型的矩阵，

采

用脸是存储结构表示三元组的线性表更为恰当。

、测试数据：

两个矩阵的规模以及非零元个数都是由用户自己确定，然后有读者输入具体的

非零元位置与数据域，然后输出用户输入的两个矩阵后，再把相加的矩阵输出。

、实现提示：

在链表中，每一个非零元可用一个含个域的结点表示，其中和这三个域

分别表示该非零元所在的行和列和非零元的值，向右域用以链接同一行中下

一个非零元，向下域用以链接同一列中下一个非零元。同一行的非零元通过

域链接成一个线性链表，同一列的非零元通过域链接成一个线性链表，

每一个非零元既是某个行链表中的一个结点，又是某个列链表中的一个结点，整

个矩阵构成为了一个十字交叉的链表，故称这样的存储结构为十字链表，可用两

个分别存储行链表的头指针和列链表的头指针的一维数组表示之。

二、概要设计

元素类型栈：

结点类型

2

行列

数据域

行和列的后继域

创建一个总的头结点

行列链表头指针

稀疏矩阵的行数，列数和非零元个数

本程序包括四个模块：

）主程序：

构建矩阵

构建矩阵

调用输出函数输出

调用输出函数输出

实现矩阵相加，结果放到中

调用输出函数输出相加后的矩阵

）矩阵构建函数：

行数列数非零元个数

动态创建个结点长的行链表指针；

动态创建个结点长的列链表指针；

初始化创建的行列链表指针：

输入非零结点

生成结点；

对应的行头结点为空头结点列元素大于结点

插入结点；

寻觅在行表中的位置；

完成行插入；

对应的列头结点为空头结点行元素大于结点

插入结点；

3

寻觅在列表中的位置;

完成列插入；

）矩阵输出函数：

行列值

行的头结点；

结点不空

指针下移；

释放

）矩阵相加函数：

指示所指结点的前驱结点

动态创建标记列结点的指针

指针只想对应的列头结点；

每行挨次处理

标记矩阵的结点

标记矩阵的结点

的结点不空

对应的结点为空的列结点的列结点

创建所指结点的复制新结点

初始化

为空

4

始终指向的前驱结点

对应的列头结点不空对应的列头结点在结点之后

改变列结点；

寻觅该插入的位置;

插入该结点；

对应的结点不空且的列结点的列结点

与指针皆后移一位；

矩阵，两节点位置相等

数据域为

为空

直接删除该零元;

利于释放

指针下移

寻觅列方向合适的位置；

把零结点从链表中删除，不改变原有的数据结构;

释放

指针下移

三、详细设计

5

十字链表

行歹I」

行和列的后继域

行列链表头指针

稀疏矩阵的行数，列数和非零元个数

创建稀疏矩阵采用十字链表存储表示

输入数据错误！！

各行列链表初始化为空链表

6

请输入非零元:

生成结点

寻觅在行表中的插入位置

完成行插入

寻觅在列表中的插入位置

完成列插入

输入数据错误！！

7

行歹IJ值

指示所指结点的前驱结点

每行挨次处理

标记矩阵的结点

标记矩阵的结点

情况一

创建所指结点的复制新结点

始终指向的前驱结点

改变列方向

8

情况二

情况三

利于释放

改变列方向

9

请输入矩阵的行数，列数和非零元个数:

构建矩阵

请输入矩阵的行数，列数和非零元个数:

构建矩阵

矩阵为：

矩阵为：

实现矩阵相加，结果放到中

矩阵相加后为：

四、调试分析

本次作业还是有一定的难度的，核心算法在于怎样把一个数据元分别插入行链表和列

链表中，并且还要插在合适的位置，确保是按正确的顺序插入的，便于查找，遍历，计算。

还有一个难点就是：把矩阵加到矩阵上，有多种情况要考虑，多种边界要注意，特别是：

两个矩阵对应的数据域相加后为零，还要把这个零元给删除，并且要不破坏原有的数据结构。

本程序模块简洁，在函数里得到充分体现，两个矩阵生成函数

与，还有一个矩阵相加函数；

用户可灵便控制矩阵的规模大小以及非零元个数，本程序具有一定的普遍性。

五、用户手册

本程序运行环境为操作系统，执行文件为：十字链表

进入演示程序后显示的界面：

Tj'D:\VC6.0\VC++6.0中SJ®\MicrosoftVisualStuc

请输入矩隹Q的行数，列数和非零元个数:

六、测试结果

10

二一T

目

主11

目100

主15

月200

主22

月-200

入

主

一23

二

目200

主

入

二33

R二

二500

主

入

二43

月C'

二100

主

入

月O

元列数和非零元个数:334

主

二

入

二1

月

二

二

元100

主

入

二22

0二

E.

一200

元

主

二

人i23

月

二

二300

主

元

入

0二I32

E二

、400

■3"D:\VC6.0\VC++6.0^3a£\MicrosoftVisualStudio\MyProjects\+^i^\De

矩阵A为：

I行列值

11100

15200

2