【愚公系列】软考中级-软件设计师 016-数据结构（数组、矩阵和广义表）

🏆 作者简介，愚公搬代码
🏆《头衔》：华为云特约编辑，华为云云享专家，华为开发者专家，华为产品云测专家，CSDN博客专家，CSDN商业化专家，阿里云专家博主，阿里云签约作者，腾讯云优秀博主，腾讯云内容共创官，掘金优秀博主，51CTO博客专家等。
🏆《近期荣誉》：2023年华为云十佳博主，2022年CSDN博客之星TOP2，2022年华为云十佳博主等。
🏆《博客内容》：.NET、Java、Python、Go、Node、前端、IOS、Android、鸿蒙、Linux、物联网、网络安全、大数据、人工智能、U3D游戏、小程序等相关领域知识。
🏆🎉欢迎 👍点赞✍评论⭐收藏

文章目录

• 🚀前言
• 🚀一、数组、矩阵和广义表
• • 🔎1.数组结构
  • • 🦋1.1 数组的表示
    • 🦋1.2 数组存储地址
  • 🔎2.矩阵结构
  • 🔎3.广义表
• 🚀感谢：给读者的一封信

🚀前言

数组（Array）是一种用于存储多个相同类型的元素的数据结构。它可以被看作是一个容器，其中的元素按照一定的顺序排列，并且可以通过索引访问。数组的长度是固定的，一旦定义后，就不能再改变。

矩阵（Matrix）是一个具有行和列的二维数组。它是由一组具有相同元素类型的数据按照行和列的方式排列组成的。矩阵广泛应用于数学和计算机科学中，用于表示和处理各种数据。

广义表（Generalized List），也称为链表（List），是一种可以包含其他列表或元素的数据结构。它可以是空表，也可以是一个元素加上一个广义表的形式。广义表可以是线性的，即只包含元素，也可以是嵌套的，即包含其他广义表。广义表提供了更灵活的数据组织方式，可以用于处理各种复杂的数据结构。

🚀一、数组、矩阵和广义表

🔎1.数组结构

🦋1.1 数组的表示

数组的特点使得它非常适合用于存储和操作大量数据。由于数组在内存中是连续存储的，所以可以通过下标直接访问数组中的元素，而不需要像链表那样遍历整个结构。这样可以提高访问元素的效率。

另外，由于数组的元素类型相同且结构一致，可以利用数组的特性进行高效的数据处理和计算。例如，可以通过循环遍历数组中的元素进行逐个计算或操作。

数组的下标关系具有上下界的约束，可以有效地控制数组的访问和操作。通过下标，可以直接定位数组中的元素，而不需要进行复杂的查找操作。

虽然数组的长度是固定的，不支持插入和删除运算，但是可以通过重新分配内存空间来实现对数组的扩展或缩小。这样可以灵活地管理数组的大小。

假设有一个3行2列的数组：

[[1, 2],  
 [3, 4],  
 [5, 6]]

行向量形式表示时，将每一行都排列在一行中：

[1, 2, 3, 4, 5, 6]

列向量形式表示时，将每一列都排列在一列中：

[1, 3, 5, 2, 4, 6]

行向量形式将数组按照行的方式展开成一行，而列向量形式将数组按照列的方式展开成一列。这样的表示方式有时可以方便进行矩阵运算和数据处理。

🦋1.2 数组存储地址

数组在内存中是连续存储的，因此数组名本身就可以看作是存储数组首元素地址的指针。当我们定义一个数组时，编译器会分配一段连续的内存空间来存储数组元素，并将数组名指向该内存空间的首地址。

例如，假设我们定义了一个int类型的数组arr：

int arr[5] = {1, 2, 3, 4, 5};

在内存中，该数组的元素将被连续存储，如下所示：

地址        内容
1000        1
1004        2
1008        3
1012        4
1016        5

数组名arr在这种情况下可以看作是存储地址1000的指针。我们可以通过使用指针来访问数组元素，例如，访问arr的第一个元素可以使用arr或者arr[0]，访问第二个元素可以使用(arr+1)或者arr[1]，以此类推。

🔎2.矩阵结构

矩阵是一种常见的数据结构，它由行和列组成的二维数组。矩阵可以用于表示和处理多种类型的数据，如数值、图像、文本等。

在计算机科学中，矩阵通常用于表示图形图像和图像处理算法。例如，图像可以表示为一个矩阵，其中每个元素表示一个像素的颜色值。通过对矩阵进行操作，可以实现图像的旋转、缩放、滤波等处理。

矩阵结构在数值计算和科学计算中也非常重要。矩阵可以用于表示线性方程组、矩阵乘法、求特征值和特征向量等数学运算。通过矩阵运算，可以解决线性方程组、最小二乘拟合、最优化等问题。

在编程中，矩阵通常用二维数组来表示。可以使用索引访问矩阵中的元素，并且可以使用循环遍历矩阵中的所有元素。还可以定义各种操作来处理矩阵，如矩阵相加、相乘等。

以下是一些常见的矩阵结构分类：

1. 方阵和非方阵：方阵是行数和列数相等的矩阵，即n x n的矩阵。非方阵则是行数和列数不相等的矩阵。

2. 稀疏矩阵和稠密矩阵：稀疏矩阵是指其中绝大多数元素为0的矩阵。而稠密矩阵则是指其中绝大多数元素不为0的矩阵。

3. 对称矩阵和非对称矩阵：对称矩阵是指以主对角线为对称轴对称的矩阵，即A[i][j] = A[j][i]。非对称矩阵则是指不满足对称性质的矩阵。

4. 上三角矩阵和下三角矩阵：上三角矩阵是指主对角线以下的元素全为0的矩阵，即A[i][j] = 0，当i > j。下三角矩阵则是指主对角线以上的元素全为0的矩阵，即A[i][j] = 0，当i < j。

5. 对角矩阵和非对角矩阵：对角矩阵是指主对角线以外的元素全为0的矩阵。非对角矩阵则是指至少有一个主对角线以外的元素不为0的矩阵。

三元组结构是一种常用的存储矩阵的方式，它将矩阵中的每个非零元素存储为一个三元组，包括该元素的行索引、列索引和值。

通常情况下，三元组结构中的元素按矩阵的行优先的方式进行存储，即先按行遍历矩阵，再按列遍历。因此，三元组结构的存储方式会将矩阵中的非零元素按照行的顺序排列，并保持它们在矩阵中的相对位置不变。

以一个4×5的矩阵为例：

1 0 0 2 0
0 0 3 0 4
0 5 0 0 0
6 0 0 7 8

用三元组结构进行存储的结果为：

(0, 0, 1)
(0, 3, 2)
(1, 2, 3)
(1, 4, 4)
(2, 1, 5)
(3, 0, 6)
(3, 3, 7)
(3, 4, 8)

其中，每个三元组表示一个非零元素的行索引、列索引和值。

🔎3.广义表

广义表是一种扩展的线性表，它可以存储不同数据类型的元素，包括原子元素和子表元素。

在广义表中，原子元素指的是不可再分的基本元素，例如整数、字符、布尔值等。子表元素则是指广义表中的另一个广义表，也就是说广义表可以嵌套存储。

广义表的存储结构通常可以使用链表或数组实现。如果使用链表实现，每个节点的数据域可以存储原子元素或指向子表的指针；如果使用数组实现，通常需要预先确定广义表的最大深度，并为每个元素分配固定大小的空间。

广义表的操作包括创建、插入、删除、修改、遍历等。递归是广义表操作的常用方法，可以通过递归遍历广义表的每个元素，从而实现各种操作。

广义表在实际应用中有广泛的用途，例如在编程语言解析中，可以使用广义表来表示语法树；在图形学中，可以使用广义表来表示复杂的图形结构；在人工智能中，可以使用广义表来表示知识库等。

广义表一般记为：

LS代表广义表的表名，αi代表广义表的元素，可以是表（子表）或者数据元素（原子）。n代表广义表的长度，即最外层包含的元素个数，当n=0时，广义表为空表。递归定义的重数是广义表的深度，即定义中所包含括号的个数（单边括号的个数），原子的深度为0，空表的深度为1。

head()和tail()是广义表的两个基本操作。head()用于取得广义表的第一个元素，无论是子表还是原子；tail()用于取得广义表中除了第一个元素之外的所有元素构成的表。需要注意的是，如果广义表是空表或只包含一个元素，则tail()操作返回一个空表。

🚀感谢：给读者的一封信

亲爱的读者，

我在这篇文章中投入了大量的心血和时间，希望为您提供有价值的内容。这篇文章包含了深入的研究和个人经验，我相信这些信息对您非常有帮助。

如果您觉得这篇文章对您有所帮助，我诚恳地请求您考虑赞赏1元钱的支持。这个金额不会对您的财务状况造成负担，但它会对我继续创作高质量的内容产生积极的影响。

我之所以写这篇文章，是因为我热爱分享有用的知识和见解。您的支持将帮助我继续这个使命，也鼓励我花更多的时间和精力创作更多有价值的内容。

如果您愿意支持我的创作，请扫描下面二维码，您的支持将不胜感激。同时，如果您有任何反馈或建议，也欢迎与我分享。

再次感谢您的阅读和支持！

最诚挚的问候， “愚公搬代码”