DataStructure And Algo

Java中的数据架构和叠加

数据结构是用于组织，处理，检索和存储数据的专门格式。有几种基本和高级的数据结构类型，旨在安排数据以适合特定目的。数据结构使用户可以轻松以适当的方式访问和处理所需的数据。最重要的是，数据结构构成了信息的组织，以便机器和人类可以更好地理解信息。

---

数据结构

数据结构是在计算机中组织和存储数据的一种专业方法，以使我们可以更有效地对存储数据进行操作。数据结构在计算机科学和软件工程领域具有广泛而多样的使用范围。数据结构几乎都用于开发的每个程序或软件系统中。此外，数据结构属于计算机科学和软件工程的基本面。在软件工程面试问题方面，这是一个关键主题。因此，作为开发人员，我们必须对数据结构有很好的了解。

DSA问题解决方案

1。数组

数组是固定大小的结构，可以容纳相同数据类型的项目。它可以是整数的数组，一系列浮点数，字符串或什至数组数组（例如二维数组）。数组是索引的，这意味着可以随机访问。

阵列操作

• 遍历：浏览元素并打印它们。
• 搜索：搜索数组中的元素。您可以通过其值或其索引搜索元素
• 更新：在给定索引处更新现有元素的值

将元素插入数组并从数组中删除元素，因为数组的大小固定，因此无法立即完成。如果要将元素插入数组，首先，您必须创建一个具有增加尺寸的新数组（当前尺寸 + 1），复制现有元素并添加新元素。删除的尺寸较小的新数组也是如此。

数组的应用

• 用作构建其他数据结构的构建块，例如数组列表，堆，哈希表，向量和矩阵。
• 用于不同分类算法，例如插入排序，快速排序，气泡排序和合并排序。

2。链接列表

链接列表是一个顺序结构，由线性顺序的一系列项目组成，彼此相互链接。因此，您必须顺序访问数据，并且不可能随机访问。链接列表提供了动态集的简单而灵活的表示。

• 链接列表中的元素称为节点。
• 每个节点都包含一个键和指针，指向其后继节点，称为下一个。
• 名为Head的属性指向链接列表的第一个元素。
• 链接列表的最后一个元素称为尾巴。

以下是可用的各种链接列表。

• 单独链接的列表- 项目的遍历只能沿向前方向完成。
• 双重链接列表- 项目的遍历可以在前进和向后进行。节点由一个称为上述的其他指针组成，指向上一个节点。
• 循环链接列表- 链接列表，头部的前一个指针指向尾部的前一个指针以及尾部指向头部的下一个指针。

链接列表操作

• 搜索：通过简单的线性搜索在给定的链接列表中找到带有键k的第一个元素，并返回指向此元素的指针
• 插入：插入链接列表的键。可以通过3种不同的方式进行插入；在列表的开头插入，在列表的末尾插入，然后插入列表中间。
• 删除：从给定的链接列表中删除元素x。您不能单步删除节点。可以通过3种不同的方式进行删除；从列表的开头删除，从列表的末尾删除，然后从列表的中间删除。

链接列表的应用

• 用于编译器设计中的符号表管理。
• 用于使用Alt + Tab在程序之间切换（使用循环链接列表实施）。

3。堆栈

堆栈是LIFO （最后一次 - 最终可以访问的元素）结构，通常可以在许多编程语言中找到。该结构被称为“堆栈”，因为它类似于现实世界中的堆栈 - 一堆板块。

堆栈操作

• 推：将元素插入堆栈顶部。
• pop：删除最高元素并返回。
• 窥视：返回堆栈的顶部元素而不删除堆栈。
• ISEMPTY ：检查堆栈是否为空。
• ISFULL ：检查堆栈是否已满。

堆栈的应用

用于表达评估（例如：用于解析和评估数学表达式的分流码算法）。用于在递归编程中实现功能调用。

4。队列

队列是FIFO （首先是首先 - 首先可以访问该元素的结构）结构通常可以在许多编程语言中找到。该结构被称为“队列”，因为它类似于现实世界的队列 - 在队列中等待的人。

队列操作

• 入选：将元素插入队列的末端。
• Dequeue ：从队列的开头删除元素。

队列的应用

用于管理多线程中的线程。用于实施排队系统（例如：优先级排队）。

5。哈希表

哈希表是一个数据结构，该数据结构存储具有与每个键关联的键的值。此外，如果我们知道与该值相关的密钥，它可以有效地支持查找。因此，无论数据大小如何，它都非常有效地插入和搜索。

直接地址在存储在表中时，使用值和键之间的一对一映射。但是，当有大量键值对时，这种方法存在问题。该表将有很多记录，并且鉴于在典型计算机上可用的内存，可能是不切实际的，甚至不可能被存储。为了避免此问题，我们使用哈希表。

哈希功能

一个名为Hash函数（H）的特殊函数用于克服直接寻址时上述问题。在直接访问中，具有键K的值存储在插槽k中。使用哈希函数，我们计算每个值所在的表（插槽）的索引。使用哈希函数计算的给定键计算的值称为哈希值，该值指示了该值映射的表的索引。

• H：哈希功能
• K：应该确定哈希值的关键
• M：哈希表的大小（可用的插槽数）。不接近2个确切功率的主要值是M的不错选择。

哈希表的应用

• 用于实现数据库索引。
• 用于实现关联阵列。
• 用于实现“设置”数据结构。

6。树

树是一个分层结构，其中数据由分层组织并链接在一起。该结构与链接列表不同，而在链接列表中，项目以线性顺序链接。在过去的几十年中，已经开发了各种各样的树木，以适应某些应用并满足某些限制。一些示例包括二进制搜索树，B树，Treap，红黑树，Splay Tree，Avl树和N- Ary树。

二进制搜索树

顾名思义，二进制搜索树（BST）是一个二进制树，其中数据以层次结构组织。该数据结构以排序顺序存储值。二进制搜索树中的每个节点都包含以下属性。

1。键：存储在节点中的值。

2。左：指向左孩子的指针。

3。右：指向合适的孩子的指针。

4。P：指向父节点的指针。

二进制搜索树展示了将其与其他树区分开的独特属性。该属性被称为** binary-search-Tree属性**。

树木的应用

• 二进制树：用于实现表达解析器和表达求解器。
• 二进制搜索树：用于数据不断输入和离开的许多搜索应用程序中。
• 堆： JVM（Java Virtual Machine）用于存储Java对象。
• Treaps：用于无线网络。

7。堆

堆是二进制树的特殊情况，在该二进制树上，将父节点与孩子的价值观进行比较，并得到相应的安排。

堆可有2种类型。

• 最小堆- 父母的钥匙小于或等于其子女的钥匙。这称为Min-Heap属性。根部将包含堆的最小值。
• Max Heap-父母的钥匙大于或等于其子女的钥匙。这称为Max-Heap属性。根部将包含堆的最大值。

堆的应用

• 用于Hepsort算法。
• 用于实现优先级的队列，因为可以根据可以使用数组实现堆的堆属性来订购优先级值。
• 可以在O（log n）时间内使用堆实现队列功能。
• 用于在给定数组中找到最小（或最大）的kᵗʰ最小值（或最大）。

8。图

图由一组有限的顶点或节点组成，以及连接这些顶点的一组边缘。

图的顺序是图中的顶点数。图的大小是图中的边数。

如果两个节点通过相同的边缘相互连接，则据说它们相邻。

定向图

如果图形G的所有边缘都有一个指示启动顶点和端顶点是什么的方向，则据说图形是一个有向图。我们说（u，v）是来自或留下顶点u的事件，是事件发生的，或者进入或进入顶点诉自动弹：从顶点到自身的边缘。

无向图

如果图形G。它可以在两个顶点之间以两种方式进行。

如果顶点未连接到图中的任何其他节点，则据说它是隔离的。

图的应用

• 用于代表社交媒体网络。每个用户都是顶点，当用户连接时，他们会创建一个边缘。
• 用于用搜索引擎表示网页和链接。 Internet上的网页通过超链接相互链接。每个页面都是顶点，两个页面之间的超链接是一个边缘。用于Google中的页面排名。
• 用于表示GPS中的位置和路线。位置是顶点，连接位置的路线是边缘。用于计算两个位置之间的最短路线。

9。特里

Trie是一种类似树状的信息检索数据结构，该数据结构存储字母的字母。它也被称为数字树或radix树或前缀树。

Trie是一种有效的信息检索数据结构。使用Trie，搜索复杂性可以达到最佳限制（密钥长度）。如果我们将钥匙存储在二进制搜索树中，则平衡的BST需要与M * log N成比例的时间，其中M是最大的字符串长度，而N是树中的键数。使用Trie，我们可以在O（M）时间中搜索键。

Trie的类型

1。标准Trie ：这是一个像数据结构一样有序的树。

• 每个节点，但词根都标有一个字符。
• 节点的孩子按字母顺序排序。
• 从外部节点到根的路径产生S的字符串。
• 每个密钥或单词的最后一个节点用于标记单词或节点的结尾。

2。压缩的Trie ：用于实现空间优化。压缩的Trie是标准Trie的高级版本。

• 淋巴结至少2个轮胎
• 它包括分组，重新组合字符的钥匙。
• 在执行插入操作时，可能需要将已经分组的字符解开。
• 在执行删除操作时，可能需要重新分组已经分组的字符。
• 通过标准尝试通过压缩冗余节点的链条获得。

3。后缀Trie ：后缀Trie是压缩Trie的高级版本。

• 后缀轮胎是用于文本的所有后缀的压缩三角。
• 后缀轮胎是一种可容纳一个供应的数据结构，可存储一个允许快速回答多种查询的字符串。

Trie的应用

使用Trie，我们可以在O（L）时间中插入并找到字符串，其中L代表单个单词的长度。这显然比BST快。这也比哈希的速度快，因为它的实现方式。我们不需要计算任何哈希功能。 Trie的另一个优点是，我们可以轻松地按字母顺序打印所有单词，而Hashhing不容易就可以。

1. 自动完成
2. 拼写检查器
3. 最长的前缀匹配
4. 浏览器历史记录

10。动态编程

动态编程是一种将问题分解为子问题的技术，并为将来的目的保存结果，因此我们不需要再次计算结果。优化子问题以优化整体解决方案被称为最佳亚基属性。动态编程的主要用途是解决优化问题。在这里，优化问题意味着当我们试图找出问题的最小解决方案或最大解决方案时。动态编程确保如果存在解决方案，可以找到问题的最佳解决方案。

时间复杂性

时间复杂性算法O（1）在数组中查找特定元素，例如：print（my_array [97]），无论数组的大小如何，都可以直接查找一个元素，只需一个操作即可。 （顺便说一句，这并不是真正的算法，但是它可以帮助我们了解时间复杂性的工作方式。）

o（n）找到最低值。该算法必须在具有n个值的数组中进行N操作以找到最低值，因为该算法必须一次比较每个值。

O（n 2）气泡排序，选择排序和插入排序是此时间复杂性的算法。在这些算法的页面上解释了其时间复杂性的原因。

大数据集大大减慢了这些算法。随着n仅从100个值增加到200个值，操作数量可以增加30000！

o（n log n）QuickSort算法平均比上述三种排序算法要快，而O（n log n）是平均值，而不是最差的情况。 QuickSort最糟糕的情况也是O（n 2），但这是使QuickSort变得如此有趣的平均时间。稍后我们将了解QuickSort。

参考来自此链接-Sourav Saini？