每个程序员必知！必须掌握的8种数据结构
每个程序员必知！必须掌握的8种数据结构
数据结构是一种特定的计算机组织与存储数据的技术，它使得我们能够更高效地对数据进行操作。这种技术在计算机科学与软件工程领域中应用广泛，且种类繁多。
众多已开发的程序与软件系统普遍采用了数据结构这一概念。同时，数据结构构成了计算机科学与软件工程领域的基础理论。在软件工程面试中，这一议题往往占据核心位置。鉴于此，对于开发者而言，对数据结构的深入理解至关重要。
本文将对我将简要阐述的八个程序员必备的常用数据结构进行概述。
1. 数组（）
数组是一种具有固定规模的集合，能够存放具有相同数据类型的多个元素。它包括整数数组、浮点数数组、字符串数组，甚至可以包含数组自身的数组，如二维数组。数组具有索引功能，这使得我们能够实现对其元素的随机访问。
数组运算
数组容量固定，故无法直接向其添加或移除元素。若需向数组中添加元素基本数据结构，需先构建一个比原数组多一个位置的全新数组，接着将原数组中的所有元素复制至新数组，并将新增元素加入其中。删除元素时，亦需采取类似步骤，创建一个容量减少的新数组，并将原数组中除被删除元素外的所有元素复制至新数组。
数组的应用
2. 链表（ Lists）
链表是一种基于线性顺序的排列结构，它由若干个项目按照顺序相互连接而成。这就意味着在处理数据时，我们必须遵循一定的顺序进行访问，而无法像在数组中那样进行随机的读取。链接列表则能够以简洁和灵活的方式，实现对动态集合的有效表示。
让我们考虑以下有关链表的术语。
以下是可用的各种类型的链接列表。
链表操作
链表的应用
3. 堆栈（）
堆栈是一种遵循LIFO原则（即后进先出，最后放入的元素最先被访问）的数据结构，这种结构在众多编程语言中普遍存在。之所以被称为“堆栈”，是因为其运作原理与现实生活中的堆叠盘子极为相似。
堆栈操作
下面给出了可以在堆栈上执行的 2 个基本操作。
此外基本数据结构，还为堆栈提供了以下附加函数以检查其状态。
栈的应用
4. 队列（）
队列是一种遵循FIFO（即先进先出，即最先放置的元素将最先被访问）原则的结构，这种结构在众多编程语言中均有广泛应用。之所以将其称为“队列”，是因为其运作方式与现实生活中的排队场景颇为相似——人们通常会在队列中依次等待。
队列操作
下面给出了可以在队列上执行的 2 个基本操作。
队列的应用
5. 哈希表（Hash ）
哈希表是一种专门用于存储带有相应键值的数据结构，每个存储的值都与其对应的键紧密相连。除此之外，只要我们掌握了与值对应的键，就能高效地实现数据的查找。因此，不论数据量的大小，无论是插入还是搜索，都能展现出极高的效率。
直接寻址法在存储时，通过值与键的对应关系进行记录。然而，当键值对数量庞大时，这种方法的弊端显现。表的大小将急剧膨胀，记录数量众多，加之常规计算机内存的局限性，这种存储方式可能既不现实，甚至根本无法实现。为此，我们转而采用哈希表来规避这一难题。
哈希函数
称为散列函数（h）的特殊函数用于克服直接寻址中的上述问题。
在直接访问过程中，键k对应的值被保存在槽k里。借助哈希函数，我们可以计算出每个值应归属的表（即槽）的具体位置。这个由哈希函数计算出的对应于特定键的值，我们称之为哈希值，它明确指出了该值应映射至的表索引。
h(k) = k % m
以哈希函数h(k) = k % 20为基准每个程序员必知！必须掌握的8种数据结构，该函数的参数为键k，而哈希表的总容量为20。面对一组特定的键，我们需要计算每个键对应的哈希值每个程序员必知！必须掌握的8种数据结构，进而确定它们在哈希表中的具体索引位置。下面展示了这些键、它们对应的哈希值以及它们在哈希表中的索引。
观察上述两个示例，我们发现，若哈希函数对多个键值产生相同的索引，便会产生所谓的索引冲突。对此，我们可以通过挑选恰当的哈希函数h，并运用链表链接和开放寻址等方法来有效处理这些冲突。
哈希表的应用
6. 树（Trees）
树木构成了一个层级化的架构基本数据结构，其中的信息依照层级顺序排列并相互连接。这种组织形式与链表相异，链表中的元素则是按照一条直线顺序相连的。
在程序应用领域，为了满足特定需求并应对各种限制条件，研究人员已经设计并实现了多种树木结构。其中，二叉搜索树、B树、treap、红黑树、splay树、AVL树以及n叉树等都是典型的代表。
二叉搜索树
二叉搜索树，简称BST，正如其名所示，是一种二叉树形式，其数据按照层级结构进行排列。这种数据结构中的数值是按照一定的排序规则进行存储的。
二叉搜索树中的每个节点都包含以下属性。
节点内保存的数据被称为键值。指向其左侧子节点的引用称作左指针。指向其右侧子节点的引用称作右指针。指向其父节点的引用称为父指针。
二叉搜索树独树一帜，它所拥有的特性被称作二叉搜索树特性。
令x为二叉搜索树中的一个节点。
树的应用
7. 堆（Heaps）
堆作为一种特殊的二叉树结构，其特点在于父节点会与子节点的数值进行对比，并据此进行有序排列。
让我们探究堆的表示方法。堆可以通过树形结构和数组形式来展现。接下来的两张图将具体展示如何用二叉树和数组来具体表示二叉堆。
堆可以有两种类型
最小堆中，每个父节点的键值都不超过其子节点的键值，这一特性被称为最小堆性质。因此，堆的根节点将存储整个堆中的最小值。而在最大堆中，父节点的键值总是大于或等于其子节点的键值，这一特性称为最大堆性质。因此，最大堆的根节点将包含堆中的最大值。
堆的应用
8.图表（）
图由一组有限的顶点或节点以及一组连接这些顶点的边组成。
图的阶数是图中顶点的数量。图的大小是图中边的数量。
如果两个节点通过同一条边相互连接，则称它们是相邻的。
有向图
若图G中的每一条边均标明了其起点和终点的指向，那么这样的图G便被定义为有向图。
我们谈论的(u, v)这一对顶点，指的是光线从顶点u射入或离开，同时亦是从顶点v射入或进入。
自循环：从顶点到自身的边。
无向图
若图G中所有边均不具备方向性，那么该图便被定义为无向图。在这种图中，顶点间的移动是可逆的，即可以在两个顶点之间进行双向通行。
若一个顶点与图中其他节点无任何连线，那么该顶点便被视为孤立。
图的应用
总结
众多数据结构实际上均源自上述结构的演变，它们是每位程序员必须精通的技能，无论是在日常工作中还是在求职面试中，这些知识都是不可或缺的储备。
