软考——（2）数据结构

淡淡的烟草味﹌ 2022-08-12 07:59 186阅读 0赞

数据结构，英文名字叫做Data Structure。说到数据结构，先要说一下数据是什么。数据的含义十分广泛，它并不仅仅指文字记录，它还可以是语音、图像、符号、视频等等。

我们可以读取这些数据，那么这些数据在计算机中又是如何存储和组织的呢，这就是我们要说的数据结构。

![SouthEast][]

上面的思维导图是按照数据结构的分类及处理画的，其实二者并不是孤立的。在查找和排序中，也可以看到线性、树、图的影子。也就是在数据结构的逻辑存储结构中进行查找和排序等的运算，它们都是紧密结合在一起的。

1）线性

一个一个的元素线性的排列，如下图：

![Center][]

这种结构的存储方式有两种：顺序存储和链表存储。

顺序存储：

![Center 1][]

和上面的线性逻辑结构一样，顺序存储中一个个元素有序的排列着。

链表存储：

![Center 2][]

链表存储中有一条“链”将一个个的元素连接起来，而每个元素的位置可以不邻接。

2）树

![Center 3][]

跟现实生活中的树一样，树形结构有且有一个根结点。树的相关术语很多，但都很容易理解，比如：结点的度，树的度，叶子，层次等等。

由于树的结构十分复杂，我们通常研究的最多的是二叉树。但要注意的是，二叉树并不是树的特殊形式。对比上下两张图片，树中的结点的最大度数没有限制，但二叉树结点的最大度数为2.在树中，结点没有左右之分；而二叉树有区分。

![Center 4][]

树的存储结构类似于索引存储结构。

3）图

与二叉树相比，树的结构要复杂一些，而图就比树更要复杂了。

![Center 5][]

图中的任何两个结点都可以相邻接。与图类似的存储结构是散列表，即哈希。

了解了这三个简单的逻辑结构，数据结构就算有了一个初步的认识了，对于之后的算法、查找、排序等，就比较轻松了。

对于刚接触数据结构的人来说，通常会有这么一个疑问，为什么要学数据结构，它跟算法又有什么关系呢？

瑞士计算机科学家Niklaus Wirth于1976年出版的一本书的书名叫做“程序设计 = 算法 \+ 数据结构”，这句经典名言就体现了数据结构的重要性。数据结构，以及让我们十分头疼的算法并不是一门教你编程的课，它们可以脱离任何的计算机程序设计语言，而只需要从抽象意义上去概括描述。

打一个很形象的比喻：程序设计就像盖房子，数据结构是砖、瓦，而算法则是设计图纸。你若想盖房子首先必须要有原材料（数据结构），但这些原材料并不能自动地盖起你想要的房子，你必须按照设计图纸（算法）一砖一瓦地去砌，这样你才能拥有你想要的房子。我们今天要说的数据结构正是程序设计这座大厦的基础，只有打好了基础，才有资格谈设计、谈构架。

[SouthEast]: /images/20220810/9b6cad771d0d47ed97bd18cd3e208b78.png
[Center]: /images/20220810/c27e3960f8f8402cbe525560b1700a7c.png
[Center 1]: /images/20220810/aac54568b88c42758eaa935bcaa7c579.png
[Center 2]: /images/20220810/8b829a0eb26d424482e25cf15c74ab37.png
[Center 3]: /images/20220810/fa3151d2253e45d3bd008a7732e45667.png
[Center 4]: /images/20220810/e0a096f77e834616829141e31967f91c.png
[Center 5]: /images/20220810/e221e0e0b1474a8585134ee25b9589e1.png