数据结构和算法

数据结构和算法是计算机科学中最重要的概念之一。如果您不熟悉计算机科学或编程，本文将为您提供有关数据结构和算法的概述。这也是Landscape系列的第二集。

image

1.数据结构

数据结构是指数据的组织和操作方式。它试图找到提高数据访问效率的方法。在处理数据结构时，我们不仅关注一个数据，而且关注不同的数据集以及它们如何以有组织的方式相互关联。

数组：数组是一种基于索引的数据结构，这意味着每个元素都由索引引用。数组包含相同的数据类型元素。

image

链表：链表是一系列节点，其中每个节点都连接到其后的节点。这形成了数据存储的链接。它由数据元素和对下一条记录的引用组成。

image

树：树是由边连接的节点的集合。每个节点指向许多节点。树表示分层图形形式。

image

二叉树：二叉树有1或2个子节点。它可以具有最少的零个节点，这在节点具有NULL值时发生。

image

二进制搜索树：二叉搜索树（BST）是二叉树。左子树包含其键小于节点键值的节点，而右子树包含其键大于或等于节点键值的节点。此外，两个子树也是二叉搜索树。二叉搜索树可以有效地检索数据。

image

矩阵：矩阵是一个双维数组。它使用两个索引行和列来存储数据。

image

图：图包含一组节点和边。节点也称为顶点。边缘用于连接节点。节点用于存储和检索数据。

image

栈：栈是LIFO数据结构，其中只能访问顶层元素。数据通过推送添加，并通过pop顶部删除。

image

队列：队列是FIFO数据结构。在该结构中，在一端插入新元件，从另一端移除现有元件。

image

Max-Heap：堆是基于树的数据结构，其中树的所有节点都按特定顺序排列。最大堆是二叉树。它是完整的。存储在每个节点中的数据项大于或等于存储在其子节点中的数据项。

image

Min-Heap： Min-heap是一个二叉树。它是完整的。存储在每个节点中的数据小于存储在其子节点中的数据项。

image

Trie(前缀树或字典树)： Trie是一棵树。在trie中，每个节点（根节点除外）存储一个字符或一个数字。通过将trie从根节点向下遍历到特定节点n，可以形成字符或数字的公共前缀，其也由特里结构的其他分支共享。

image

** 后缀树（Suffix tree）：**后缀trie是包含给定文本的所有后缀的trie。后缀特里允许特别快速地实现许多重要的字符串操作。

image

2. Java集合

Java集合框架是作为核心java的一部分包含的集合类型集。它提供了可以直接用于操作数据结构的API或方法，例如数组，链接列表，栈，队列，集合和映射。如果掌握了java集合，它将为您节省大量时间并有助于解决复杂问题。

ArrayList： ArrayList类是List接口的可调整大小的数组实现。它实现所有可选的列表操作并允许所有元素。

image

向量：向量与ArrayList非常相似，但Vector是同步且缓慢的。它是一个遗留类，现在它可以与集合兼容。

String： String类用于创建和操作字符串。

image

LinkedList： LinkedList类是List和Deque接口的双向链表实现。LinkedList将其数据存储为元素列表，并且每个元素都链接到其上一个和下一个元素。

image

HashMap： HashMap是一个实现Map接口的集合类。它需要一个哈希函数并使用hashCode（）和equals（）方法，以便分别在集合中放入和检索元素。

image

Hashtable： Hashtable类与HashMap类似。它实现了Dictionary。Hashtable提供其键的枚举。它不允许null作为键或值。请注意，由于HashMap是在稍后创建的，因此它是Hashtable的高级版本和改进版。Hashtable是同步的，速度较慢。HashMap比Hashtable更受欢迎。

TreeMap： TreeMap实现了SortedMap接口。它按其键的升序排序。操作的复杂性是O（logn）。

image

LinkedHashMap： LinkedHashMap保持插入顺序。复杂性与HashMap O（1）相同。

image.png

HashSet： HashSet类实现Set接口。不允许重复值。它的元素没有订购。HashSet中允许使用NULL元素。

image

TreeSet： TreeSet使用树结构实现。TreeSet中的元素已排序。操作的复杂性是O（logn）。

image

LinkedHashSet： LinkedHashSet维护插入顺序。元素按照它们添加到Set中的相同顺序进行排序。复杂性与HashSet O（1）相同。

image

Stack： Stack类扩展了Vector类，有五个操作来支持LIFO（后进先出）。Stack内部有一个指针：TOP，它指的是Stack元素的顶部。

image

PriorityQueue： PriorityQueue类是Queue的实现，每个元素都具有与之关联的优先级。优先级队列的元素根据其自然顺序排序，或者由队列构建时提供的比较器排序。

image

3.算法

算法是一种定义明确的过程，允许计算机解决问题。有很多算法。在这里，我列出了计算机科学中一些广泛使用的算法：排序，搜索，重复编程和动态编程。

排序：排序是一种算法，由一系列指令组成，这些指令将数组作为输入，对数组执行指定的操作，有时称为列表，并输出排序的数组。简单的排序算法是冒泡排序，选择排序和插入排序。

冒泡排序：这是最简单的排序算法。我们从数组的开头开始，如果第一个元素大于第二个元素，则交换前两个元素。然后我们转到下一对，依此类推，不断扫描数组，直到它被排序。O（n 2）平均值和最差值。

image

选择排序：这是最直观的，不一定有效。使用线性扫描找到最小元素并将其移动到前面（使用前面元素交换它）。然后找到第二个最小的并移动它，再次进行线性扫描。继续这样做，直到所有元素都到位。适合小文件。O（n 2）平均值和最差值。

image

插入排序：它通过逐个移动元素对数组进行排序。每次迭代都会从输入数据中删除一个元素，并将其插入正在排序的列表中的正确位置。它对于较小的数据集是有效的，但对于较大的列表而言效率非常低。它比Selection Sort和Bubble Sort算法更好。O（n 2）平均值和最差值。

image

搜索：搜索是基于密钥查找内容。有线性搜索和二进制搜索。

线性搜索：线性搜索是一种在列表中查找目标值的方法。它按顺序检查列表中每个元素的目标值，直到找到匹配项或者直到搜索完所有元素为止。

image

二进制搜索：二进制搜索是一种有效的算法，用于从有序的项目列表中查找项目。它的工作原理是反复将列表中可能包含该项目的部分分成两半; 直到你将可能的位置缩小到一个。复杂性从O（n）减少到O（logn）。

image

递归：递归是一种函数或算法自称的计算机编程技术。它应包括具有终止条件的步骤。当条件满足时，每个重复的其余部分从最后一个被调用到第一个重复处理。通过递归解决的最着名的问题是因子数。

阶乘数：数n的阶乘是所有小于或等于n的正非零数的乘积。n的阶乘由n！表示。

image

动态编程：动态编程是一种解决复杂问题的方法，可以将其分解为更简单的子问题集合，只需解决一次子问题，并存储其解决方案。下次出现相同的子问题时，可以查找先前计算的解，从而节省计算时间，但代价是存储空间的适度支出。着名的动态编程问题是Fibonacci数。

斐波纳契数：它们是一系列数字，其中每个数字（斐波纳契数）是前两个数字的总和。最简单的是系列1,1,2,3,5,8等。

image

划分和征服：分而治之算法通过递归地将问题分解为相同或相关类型的两个或更多个子问题来工作，直到这些子问题变得足够简单直接解决。使用分而治之的着名问题是合并排序和快速排序。

合并排序：将数组分成两半，对每一半进行排序，然后将它们合并在一起。这些半部分中的每一部分都应用了相同的排序算法。最终，它合并了两个单元素数组。O（nlogn）平均值和最差值。

image

快速排序：选取一个随机元素并对数组进行分区，所有小于分区元素的数字都会出现在大于它的所有元素之前。如果我们在元素周围重复分区数组，那么数组最终将被排序。但由于分区元素不能保证为中位数，因此我们的排序可能非常慢。O（nlogn）平均值，O（n 2）最差。

image

贪婪：贪婪算法做出的选择似乎是当时最好的选择，即做出本地最优选择，希望这种选择能够带来全局最优解决方案。贪婪算法解决的着名问题是霍夫曼编码。

霍夫曼编码：霍夫曼编码是一种无损数据压缩算法。其思想是为输入字符分配可变长度代码，分配代码的长度基于相应字符的频率。

image

更多 观看“数据结构和算法的风景”（YouTube）视频！

原文：https://www.lavivienpost.com/data-structures-and-algorithms/ 作者： La Vivien