DSA - 快速指南
Data Structures & Algorithms - Overview
数据结构是一种组织数据以便有效使用数据的系统方法。 以下术语是数据结构的基础术语。
Interface - 每个数据结构都有一个接口。 Interface表示数据结构支持的操作集。 接口仅提供支持的操作列表，它们可以接受的参数类型以及返回这些操作的类型。
Implementation - 实现提供数据结构的内部表示。 实现还提供了数据结构操作中使用的算法的定义。
数据结构的特征
Correctness - 数据结构实现应正确实现其接口。
Time Complexity - 数据结构的运行时间或操作的执行时间必须尽可能小。
Space Complexity - 数据结构操作的内存使用应尽可能少。
需要数据结构
随着应用程序越来越复杂且数据越来越丰富，应用程序现在面临三个常见问题。
Data Search - 考虑一个商店的100万（10 6 ）件商品的库存。 如果应用程序要搜索项目，则每次减慢搜索速度时，它必须搜索100万（10 6 ）个项目中的项目。 随着数据的增长，搜索速度会变慢。
Processor speed - 处理器速度虽然非常高，但如果数据增长到数十亿条记录，则会受到限制。
Multiple requests - 由于成千上万的用户可以在Web服务器上同时搜索数据，因此即使快速服务器在搜索数据时也会失败。
为了解决上述问题，数据结构得以解决。 可以在数据结构中组织数据，使得可以不需要搜索所有项目，并且几乎可以立即搜索所需数据。
执行时间案例
有三种情况通常用于以相对方式比较各种数据结构的执行时间。
Worst Case - 这是特定数据结构操作占用最多时间的情况。 如果操作的最坏情况时间是ƒ（n），那么此操作将不会超过ƒ（n）时间，其中ƒ（n）表示n的函数。
Average Case - 这是描述数据结构操作的平均执行时间的方案。 如果操作在执行中花费ƒ（n）时间，那么m次操作将花费mƒ（n）时间。
Best Case - 这是描述数据结构操作的最少可能执行时间的场景。 如果操作在执行中花费ƒ（n）时间，则实际操作可能花费时间作为最大的随机数作为f（n）。
基本术语 (Basic Terminology)
Data - 数据是值或值集。
Data Item - 数据项是指单个值单位。
Group Items - 分为子项目的数据项称为组项目。
Elementary Items - 不能分割的数据项称为基本项目。
Attribute and Entity - 实体是包含某些属性或属性的实体，可以为其指定值。
Entity Set - 类似属性的实体形成实体集。
Field - Field是表示实体属性的单个基本信息单元。
Record - 记录是给定实体的字段值的集合。
File - 文件是给定实体集中实体的记录的集合。
Data Structures - Environment Setup
Try it Option Online
您真的不需要设置自己的环境来开始学习C编程语言。 原因很简单，我们已经在线设置了C编程环境，这样您就可以在进行理论工作的同时在线编译和执行所有可用的示例。 这使您对正在阅读的内容充满信心，并使用不同的选项检查结果。 随意修改任何示例并在线执行。
使用示例代码框右上角的“ Try it选项， Try it以下示例 -
#include <stdio.h>
int main(){
/* My first program in C */
printf("Hello, World! \n");
return 0;
}
对于本教程中给出的大多数示例，您将找到Try it选项，因此只需使用它并享受您的学习。
本地环境设置 (Local Environment Setup)
如果您仍然愿意为C编程语言设置环境，则需要在计算机上使用以下两个工具:（a）文本编辑器和（b）C编译器。
文本编辑器
这将用于键入您的程序。 少数编辑器的示例包括Windows Notepad，OS Edit命令，Brief，Epsilon，EMACS和vim或vi。
文本编辑器的名称和版本可能因操作系统而异。 例如，Notepad将在Windows上使用，vim或vi可以在Windows以及Linux或UNIX上使用。
使用编辑器创建的文件称为源文件，包含程序源代码。 C程序的源文件通常以扩展名“ .c ”命名。
在开始编程之前，请确保您有一个文本编辑器，并且您有足够的经验编写计算机程序，将其保存在文件中，编译并最终执行。
C编译器
源文件中编写的源代码是程序的可读源代码。 它需要被“编译”，变成机器语言，这样你的CPU才能按照给定的指令实际执行程序。
这个C编程语言编译器将用于将源代码编译成最终的可执行程序。 我们假设您具有编程语言编译器的基本知识。
最常用和免费的编译器是GNU C/C ++编译器。 否则，如果您有相应的操作系统（OS），则可以使用HP或Solaris编译器。
以下部分将指导您如何在各种OS上安装GNU C/C ++编译器。 我们一起提到C/C ++，因为GNU GCC编译器适用于C和C ++编程语言。
在UNIX/Linux上安装
如果您使用的是Linux or UNIX ，请通过从命令行输入以下命令来检查系统上是否安装了GCC -
$ gcc -v
如果您的计算机上安装了GNU编译器，那么它应该打印如下消息 -
Using built-in specs.
Target: i386-redhat-linux
Configured with: ../configure --prefix = /usr .......
Thread model: posix
gcc version 4.1.2 20080704 (Red Hat 4.1.2-46)
如果未安装GCC，则必须使用https://gcc.gnu.org/install/提供的详细说明自行安装。
本教程是基于Linux编写的，所有给出的示例都是在Linux系统的Cent OS风格上编译的。
在Mac OS上安装
如果您使用的是Mac OS X，获取GCC的最简单方法是从Apple网站下载Xcode开发环境，并按照简单的安装说明进行操作。 一旦你有Xcode设置，你就可以使用GNU编译器来实现C/C ++。
Xcode目前可在developer.apple.com/technologies/tools/
Installation on Windows
要在Windows上安装GCC，您需要安装MinGW。 要安装MinGW，请访问MinGW主页www.mingw.org ，然后点击MinGW下载页面的链接。 下载最新版本的MinGW安装程序，该程序应命名为MinGW-“version”.exe。
在安装MinWG时，至少必须安装gcc-core，gcc-g ++，binutils和MinGW运行时，但您可能希望安装更多。
将MinGW安装的bin子目录添加到PATH环境变量中，以便您可以通过简单名称在命令行上指定这些工具。
安装完成后，您将能够从Windows命令行运行gcc，g ++，ar，ranlib，dlltool和其他几个GNU工具。
Data Structures - Algorithms Basics
算法是一个逐步的过程，它定义了一组指令，这些指令按特定顺序执行以获得所需的输出。 算法通常独立于底层语言创建，即算法可以用一种以上的编程语言实现。
从数据结构的角度来看，以下是一些重要的算法类别 -
Search - 搜索数据结构中的项目的算法。
Sort - Sort特定顺序对项目进行Sort算法。
Insert - 在数据结构中插入项的算法。
Update - 更新数据结构中现有项目的算法。
Delete - 从数据结构中删除现有项目的算法。
算法的特征
并非所有过程都可以称为算法。 算法应具有以下特征 -
Unambiguous - 算法应清晰明确。 它的每个步骤（或阶段）及其输入/输出应该是清楚的，并且必须只有一个含义。
Input - 算法应具有0个或更多明确定义的输入。
Output - 算法应具有1个或多个明确定义的输出，并且应与所需的输出匹配。
Finiteness - 算法必须在有限数量的步骤之后终止。
Feasibility - 利用现有资源应该可行。
Independent - 算法应具有逐步指导，这应该独立于任何编程代码。
如何编写算法？
编写算法没有明确定义的标准。 相反，它是问题和资源依赖的。 永远不会编写算法来支持特定的编程代码。
我们知道所有编程语言都共享基本代码结构，如循环（do，for，while），流控制（if-else）等。这些常用结构可用于编写算法。
我们以逐步的方式编写算法，但情况并非总是如此。 算法编写是一个过程，在问题域定义明确后执行。 也就是说，我们应该知道我们正在设计解决方案的问题域。
例子 (Example)
让我们尝试通过一个例子学习算法编写。
Problem - 设计一个算法来添加两个数字并显示结果。
<b class="notranslate">Step 1</b> − START
<b class="notranslate">Step 2</b> − declare three integers <b class="notranslate">a</b>, <b class="notranslate">b</b> & <b class="notranslate">c</b>
<b class="notranslate">Step 3</b> − define values of <b class="notranslate">a</b> & <b class="notranslate">b</b>
<b class="notranslate">Step 4</b> − add values of <b class="notranslate">a</b> & <b class="notranslate">b</b>
<b class="notranslate">Step 5</b> − store output of <u>step 4</u> to <b class="notranslate">c</b>
<b class="notranslate">Step 6</b> − print <b class="notranslate">c</b>
<b class="notranslate">Step 7</b> − STOP
算法告诉程序员如何编写程序代码。 或者，算法可以写成 -
<b class="notranslate">Step 1</b> − START ADD
<b class="notranslate">Step 2</b> − get values of <b class="notranslate">a</b> & <b class="notranslate">b</b>
<b class="notranslate">Step 3</b> − c ← a + b
<b class="notranslate">Step 4</b> − display c
<b class="notranslate">Step 5</b> − STOP
在算法的设计和分析中，通常使用第二种方法来描述算法。 它使分析人员可以轻松分析算法，忽略所有不需要的定义。 他可以观察正在使用的操作以及流程如何流动。
编写step numbers是可选的。
我们设计了一种算法来获得给定问题的解决方案。 问题可以通过多种方式解决。
因此，可以针对给定问题导出许多解算法。 下一步是分析那些提出的解决方案算法并实施最合适的解决方案。
算法分析
算法的效率可以在实现之前和实现之后的两个不同阶段进行分析。 他们是以下 -
A Priori Analysis - 这是对算法的理论分析。 通过假设所有其他因素（例如，处理器速度）是恒定的并且对实现没有影响来测量算法的效率。
A Posterior Analysis - 这是一种算法的实证分析。 所选算法使用编程语言实现。 然后在目标计算机上执行此操作。 在此分析中，收集了所需的运行时间和空间等实际统计数据。
我们将学习a priori算法分析。 算法分析处理所涉及的各种操作的执行或运行时间。 操作的运行时间可以定义为每个操作执行的计算机指令的数量。
算法复杂度
假设X是算法， n是输入数据的大小，算法X使用的时间和空间是决定X效率的两个主要因素。
Time Factor - 时间是通过计算关键操作的数量来测量的，例如排序算法中的比较。
Space Factor - 通过计算算法所需的最大内存空间来测量空间。
算法f(n)的复杂性给出算法所需的运行时间和/或存储空间，以n为输入数据的大小。
空间复杂性
算法的空间复杂度表示算法在其生命周期中所需的存储空间量。 算法所需的空间等于以下两个组件的总和 -
固定部分，是存储某些数据和变量所需的空间，与问题的大小无关。 例如，使用的简单变量和常量，程序大小等。
变量部分是变量所需的空间，其大小取决于问题的大小。 例如，动态内存分配，递归堆栈空间等。
任何算法P的空间复杂度S（P）是S（P）= C + SP（I），其中C是固定部分，S（I）是算法的可变部分，它取决于实例特征I.是一个试图解释这个概念的简单例子 -
Algorithm: SUM(A, B)
Step 1 - START
Step 2 - C ← A + B + 10
Step 3 - Stop
这里我们有三个变量A，B和C以及一个常数。 因此，S（P）= 1 + 3.现在，空间取决于给定变量和常量类型的数据类型，并且它将相应地相乘。
时间复杂度 (Time Complexity)
算法的时间复杂度表示算法运行完成所需的时间量。 时间要求可以定义为数值函数T（n），其中T（n）可以作为步数来测量，条件是每个步骤消耗恒定的时间。
例如，添加两个n位整数需要n步。 因此，总计算时间是T（n）= c * n，其中c是添加两个比特所花费的时间。 在这里，我们观察到T（n）随着输入大小的增加而线性增长。
Data Structures - Asymptotic Analysis
算法的渐近分析是指定义其运行时性能的数学边界/框架。 使用渐近分析，我们可以很好地得出算法的最佳情况，平均情况和最坏情况。
渐近分析是输入约束，即，如果算法没有输入，则结论是在恒定时间内工作。 除了“输入”之外，所有其他因素都被认为是不变的。
渐近分析是指以数学计算单位计算任何操作的运行时间。 例如，一个操作的运行时间计算为f （n），并且可以用于另一个操作，其计算为g （n 2 ）。 这意味着第一操作运行时间将随着n的增加而线性增加，并且当n增加时第二操作的运行时间将指数地增加。 类似地，如果n非常小，则两个操作的运行时间几乎相同。
通常，算法所需的时间分为三种类型 -
Best Case - 程序执行所需的最短时间。
Average Case - 程序执行所需的平均时间。
Worst Case - 程序执行所需的Worst Case长时间。
渐近符号
以下是计算算法运行时间复杂度的常用渐近符号。
- Ο符号
- Ω表示法
- θ表示法
大哦符号，Ο
符号Ο（n）是表示算法运行时间上限的正式方式。 它测量最坏情况下的时间复杂度或算法可能需要完成的最长时间。
例如，对于函数f (n)
Ο(<i>f</i>(n)) = { <i>g</i>(n) : there exists c > 0 and n<sub>0</sub> such that <i>f</i>(n) ≤ c.<i>g</i>(n) for all n > n<sub>0</sub>. }
Omega表示法，Ω
符号Ω（n）是表示算法运行时间下限的正式方式。 它测量最佳案例时间复杂度或算法可能需要完成的最佳时间量。
例如，对于函数f (n)
Ω(<i>f</i>(n)) ≥ { <i>g</i>(n) : there exists c > 0 and n<sub>0</sub> such that <i>g</i>(n) ≤ c.<i>f</i>(n) for all n > n<sub>0</sub>. }
Theta Notation，θ
符号θ（n）是表示算法运行时间的下限和上限的形式方式。 它表示如下 -
θ(<i>f</i>(n)) = { <i>g</i>(n) if and only if <i>g</i>(n) = Ο(<i>f</i>(n)) and <i>g</i>(n) = Ω(<i>f</i>(n)) for all n > n<sub>0</sub>. }
常见的渐近符号
以下列出了一些常见的渐近符号 -
| constant | − | Ο(1) |
| logarithmic | − | Ο（log n） |
| linear | − | Ο(n) |
| n log n | − | Ο（n log n） |
| quadratic | − | Ο(n 2 ) |
| cubic | − | Ο(n 3 ) |
| polynomial | − | n Ο(1) |
| exponential | − | 2 Ο(n) |
Data Structures - Greedy Algorithms
设计算法以实现给定问题的最佳解决方案。 在贪婪算法方法中，决策是从给定的解决方案域做出的。 由于贪婪，选择了似乎提供最佳解决方案的最接近的解决方案。
贪心算法试图找到一个本地化的最优解决方案，最终可能导致全局优化的解决方案。 但是，通常贪婪算法不提供全局优化的解决方案。
计数硬币
这个问题是通过选择最不可能的硬币来计算到期望的值，并且贪婪的方法迫使算法选择最大可能的硬币。 如果我们提供₹1,2,5和10的硬币，我们被要求计算₹18，那么贪婪程序将是 -
1 - 选择一个₹10硬币，剩余计数为8
2 - 然后选择一个₹5硬币，剩余计数为3
3 - 然后选择一个₹2硬币，剩余计数为1
4 - 最后，选择一个₹1个硬币可以解决问题
虽然，它似乎工作正常，但这个数量我们只需要选择4个硬币。 但是，如果我们稍微改变问题，那么相同的方法可能无法产生相同的最佳结果。
对于货币系统，我们有硬币值为1,7,10的值，计算值为18的硬币绝对是最佳的，但对于15的计数，它可能会使用超过必要的硬币。 例如，贪婪的方法将使用10 + 1 + 1 + 1 + 1 + 1，总共6个硬币。 而只使用3个硬币（7 + 7 + 1）就可以解决同样的问题
因此，我们可以得出结论，贪婪的方法选择了一个立即优化的解决方案，并且可能在全局优化成为主要问题的地方失败。
例子 (Examples)
大多数网络算法都使用贪婪的方法。 以下是其中一些列表 -
- Travelling Salesman Problem
- Prim的最小生成树算法
- Kruskal的最小生成树算法
- Dijkstra的最小生成树算法
- 图 - 地图着色
- 图 - 顶点覆盖
- 背包问题
- Job Scheduling Problem
有许多类似的问题使用贪婪的方法来找到最佳解决方案。
Data Structures - Divide and Conquer
在分而治之的方法中，手头的问题被分成较小的子问题，然后每个问题都独立解决。 当我们继续将子问题划分为更小的子问题时，我们最终可能会达到无法进行更多划分的阶段。 解决那些“原子”最小可能的子问题（分数）。 最后合并所有子问题的解决方案以获得原始问题的解决方案。
从广义上讲，我们可以通过三个步骤来理解divide-and-conquer方法。
Divide/Break
此步骤涉及将问题分解为更小的子问题。 子问题应该代表原始问题的一部分。 此步骤通常采用递归方法来划分问题，直到子问题不再可被整除为止。 在这个阶段，子问题本质上是原子的，但仍然代表了实际问题的某些部分。
Conquer/Solve
这一步收到了许多较小的子问题需要解决。 通常，在这个层面上，问题被认为是自己“解决”的。
Merge/Combine
当解决较小的子问题时，该阶段递归地组合它们直到它们形成原始问题的解决方案。 这种算法方法递归地工作并且征服和合并步骤的工作如此接近以至于它们看起来像一个。
例子 (Examples)
以下计算机算法基于divide-and-conquer编程方法 -
- 合并排序
- 快速排序
- Binary Search
- Strassen的矩阵乘法
- 最近的一对（点）
有多种方法可以解决任何计算机问题，但所提到的是分而治之的方法的一个很好的例子。
Data Structures - Dynamic Programming
动态编程方法类似于将问题分解为更小但更小的子问题的分而治之。 但不同的是，分而治之，这些子问题并没有独立解决。 相反，记住这些较小子问题的结果并用于类似或重叠的子问题。
动态编程用于我们遇到问题的地方，可以将其划分为类似的子问题，以便可以重复使用它们的结果。 大多数情况下，这些算法用于优化。 在解决现有子问题之前，动态算法将尝试检查先前解决的子问题的结果。 结合子问题的解决方案以实现最佳解决方案。
所以我们可以说 -
该问题应该能够分成较小的重叠子问题。
通过使用较小子问题的最佳解决方案可以实现最佳解决方案。
动态算法使用Memoization。
比较(Comparison)
与解决局部优化的贪婪算法相反，动态算法被激励用于问题的整体优化。
与分而治之的算法相比，其中解决方案被组合以实现整体解决方案，动态算法使用较小子问题的输出，然后尝试优化更大的子问题。 动态算法使用Memoization来记住已经解决的子问题的输出。
例子 (Example)
使用动态编程方法可以解决以下计算机问题 -
- 斐波纳契数系列
- 背包问题
- Tower of Hanoi
- 由Floyd-Warshall完成的所有最短路径
- Shortest path by Dijkstra
- Project scheduling
动态编程可以自上而下和自下而上的方式使用。 当然，大多数情况下，参考之前的解决方案输出比CPU周期重新计算更便宜。
Data Structures & Algorithm Basic Concepts
本章介绍与数据结构相关的基本术语。
数据定义
数据定义定义具有以下特征的特定数据。
Atomic - 定义应该定义一个单一的概念。
Traceable - 定义应该能够映射到某些数据元素。
Accurate - 定义应该是明确的。
Clear and Concise - 定义应该是可以理解的。
数据对象
数据对象表示具有数据的对象。
数据类型
数据类型是对诸如整数，字符串等各种类型的数据进行分类的一种方式，其确定可以与相应类型的数据一起使用的值，可以对相应类型的数据执行的操作的类型。 有两种数据类型 -
- 内置数据类型
- 派生数据类型
内置数据类型
语言具有内置支持的那些数据类型称为内置数据类型。 例如，大多数语言提供以下内置数据类型。
- Integers
- Boolean (true, false)
- Floating (Decimal numbers)
- Character and Strings
派生数据类型
那些可以以一种或另一种方式实现的独立于实现的数据类型称为派生数据类型。 这些数据类型通常由主数据类型或内置数据类型以及相关操作的组合构建。 例如 -
- List
- Array
- Stack
- Queue
基本操作 (Basic Operations)
数据结构中的数据由某些操作处理。 所选择的特定数据结构很大程度上取决于需要对数据结构执行的操作的频率。
- Traversing
- Searching
- Insertion
- Deletion
- Sorting
- Merging
Data Structures and Algorithms - Arrays
Array是一个容器，可以容纳固定数量的项目，这些项目应该是相同的类型。 大多数数据结构都使用数组来实现其算法。 以下是理解Array概念的重要术语。
Element - 存储在数组中的每个项称为元素。
Index - 数组中元素的每个位置都有一个数字索引，用于标识元素。
数组表示
可以使用不同语言以各种方式声明数组。 为了说明，我们采取C数组声明。
可以使用不同语言以各种方式声明数组。 为了说明，我们采取C数组声明。
根据以上说明，以下是要考虑的重点。
索引从0开始。
数组长度为10，这意味着它可以存储10个元素。
可以通过索引访问每个元素。 例如，我们可以将索引6处的元素提取为9。
基本操作 (Basic Operations)
以下是数组支持的基本操作。
Traverse - 逐个打印所有数组元素。
Insertion - 在给定索引处添加元素。
Deletion - 删除给定索引处的元素。
Search - 使用给定索引或值搜索元素。
Update - 更新给定索引处的元素。
在C中，当使用size初始化数组时，它会按以下顺序为其元素分配默认值。
| 数据类型 | 默认值 |
|---|---|
| bool | false |
| char | 0 |
| int | 0 |
| float | 0.0 |
| double | 0.0f |
| void | |
| wchar_t | 0 |
插入操作 (Insertion Operation)
插入操作是将一个或多个数据元素插入到数组中。 根据需求，可以在开头，结尾或任何给定的数组索引处添加新元素。
在这里，我们看到插入操作的实际实现，我们在数组的末尾添加数据 -
算法 (Algorithm)
令Array为MAX元素的线性无序数组。
例子 (Example)
Result
设LA是具有N元素的线性阵列（无序）， K是正整数，使得K《=N 以下是将ITEM插入洛杉矶第 K 个位置的算法 -
1. Start
2. Set J = N
3. Set N = N+1
4. Repeat steps 5 and 6 while J >= K
5. Set LA[J+1] = LA[J]
6. Set J = J-1
7. Set LA[K] = ITEM
8. Stop
例子 (Example)
以下是上述算法的实现 -
#include <stdio.h>
main() {
int LA[] = {1,3,5,7,8};
int item = 10, k = 3, n = 5;
int i = 0, j = n;
printf("The original array elements are :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}
n = n + 1;
while( j >= k) {
LA[j+1] = LA[j];
j = j - 1;
}
LA[k] = item;
printf("The array elements after insertion :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}
}
当我们编译并执行上述程序时，它会产生以下结果 -
输出 (Output)
The original array elements are :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 7
LA[4] = 8
The array elements after insertion :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 10
LA[4] = 7
LA[5] = 8
有关阵列插入操作的其他变体， 请单击此处
删除操作 (Deletion Operation)
删除是指从数组中删除现有元素并重新组织数组的所有元素。
算法 (Algorithm)
考虑LA是具有N元素的线性阵列， K是正整数，使得K《=N 以下是删除在LA的第 K 个位置可用的元素的算法。
1. Start
2. Set J = K
3. Repeat steps 4 and 5 while J < N
4. Set LA[J] = LA[J + 1]
5. Set J = J+1
6. Set N = N-1
7. Stop
例子 (Example)
以下是上述算法的实现 -
#include <stdio.h>
void main() {
int LA[] = {1,3,5,7,8};
int k = 3, n = 5;
int i, j;
printf("The original array elements are :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}
j = k;
while( j < n) {
LA[j-1] = LA[j];
j = j + 1;
}
n = n -1;
printf("The array elements after deletion :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}
}
当我们编译并执行上述程序时，它会产生以下结果 -
输出 (Output)
The original array elements are :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 7
LA[4] = 8
The array elements after deletion :
LA[0] = 1
LA[1] = 3
LA[2] = 7
LA[3] = 8
搜索操作 (Search Operation)
您可以根据数组元素的值或索引搜索数组元素。
算法 (Algorithm)
考虑LA是具有N元素的线性阵列， K是正整数，使得K《=N 以下是使用顺序搜索查找具有ITEM值的元素的算法。
1. Start
2. Set J = 0
3. Repeat steps 4 and 5 while J < N
4. IF LA[J] is equal ITEM THEN GOTO STEP 6
5. Set J = J +1
6. PRINT J, ITEM
7. Stop
例子 (Example)
以下是上述算法的实现 -
#include <stdio.h>
void main() {
int LA[] = {1,3,5,7,8};
int item = 5, n = 5;
int i = 0, j = 0;
printf("The original array elements are :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}
while( j < n){
if( LA[j] == item ) {
break;
}
j = j + 1;
}
printf("Found element %d at position %d\n", item, j+1);
}
当我们编译并执行上述程序时，它会产生以下结果 -
输出 (Output)
The original array elements are :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 7
LA[4] = 8
Found element 5 at position 3
更新操作 (Update Operation)
更新操作是指在给定索引处更新阵列中的现有元素。
算法 (Algorithm)
考虑LA是具有N元素的线性阵列， K是正整数，使得K《=N 以下是更新在LA的第 K 个位置可用的元素的算法。
1. Start
2. Set LA[K-1] = ITEM
3. Stop
例子 (Example)
以下是上述算法的实现 -
#include <stdio.h>
void main() {
int LA[] = {1,3,5,7,8};
int k = 3, n = 5, item = 10;
int i, j;
printf("The original array elements are :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}
LA[k-1] = item;
printf("The array elements after updation :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}
}
当我们编译并执行上述程序时，它会产生以下结果 -
输出 (Output)
The original array elements are :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 7
LA[4] = 8
The array elements after updation :
LA[0] = 1
LA[1] = 3
LA[2] = 10
LA[3] = 7
LA[4] = 8
Data Structure and Algorithms - Linked List
链表是一系列数据结构，通过链接连接在一起。
链接列表是包含项目的一系列链接。 每个链接都包含与另一个链接的连接。 链表是数组后第二常用的数据结构。 以下是理解链表的概念的重要术语。
Link - 链接列表的每个链接都可以存储称为元素的数据。
Next - 链接列表的每个链接都包含指向下一个名为Next的链接的链接。
LinkedList - 链接列表包含指向名为First的第一个链接的连接链接。
链表清单表示
链表可以显示为节点链，其中每个节点指向下一个节点。
根据以上说明，以下是要考虑的重点。
链接列表包含一个名为first的链接元素。
每个链路都带有一个数据字段和一个名为next的链接字段。
每个链接使用其下一个链接与其下一个链接链接。
最后一个链接带有一个null链接以标记列表的结尾。
链表的类型
以下是各种类型的链表。
Simple Linked List - 项目导航仅向前。
Doubly Linked List - 可以向前和向后导航项目。
Circular Linked List - 最后一项包含第一个元素的链接作为下一个，第一个元素具有前一个元素的链接。
基本操作 (Basic Operations)
以下是列表支持的基本操作。
Insertion - 在列表的开头添加元素。
Deletion - 删除列表开头的元素。
Display - 显示完整列表。
Search - 使用给定键搜索元素。
Delete - 使用给定键删除元素。
插入操作 (Insertion Operation)
在链表中添加新节点是一个以上的步骤活动。 我们将在这里用图表来学习。 首先，使用相同的结构创建一个节点，并找到它必须插入的位置。
想象一下，我们在A （LeftNode）和C （RightNode）之间插入节点B （NewNode）。 然后将B.next指向C -
NewNode.next −> RightNode;
看起来应该是这样的 -
现在，左侧的下一个节点应指向新节点。
LeftNode.next −> NewNode;
这将把新节点放在两者的中间。 新列表应如下所示 -
如果在列表的开头插入节点，则应采取类似的步骤。 在末尾插入时，列表的倒数第二个节点应指向新节点，新节点将指向NULL。
删除操作 (Deletion Operation)
删除也是一个不止一步的过程。 我们将学习图画表达。 首先，使用搜索算法找到要删除的目标节点。
现在，目标节点的左（前）节点应指向目标节点的下一个节点 -
LeftNode.next −> TargetNode.next;
这将删除指向目标节点的链接。 现在，使用以下代码，我们将删除目标节点指向的内容。
TargetNode.next −> NULL;
我们需要使用已删除的节点。 我们可以将其保留在内存中，否则我们可以简单地释放内存并完全擦除目标节点。
反向操作
这项操作是彻底的。 我们需要让头节点指向最后一个节点并反转整个链表。
首先，我们遍历列表的末尾。 它应该指向NULL。 现在，我们将指出它的前一个节点 -
我们必须确保最后一个节点不是丢失的节点。 所以我们将有一些临时节点，它看起来像指向最后一个节点的头节点。 现在，我们将使所有左侧节点逐个指向它们之前的节点。
除了头节点指向的节点（第一个节点）之外，所有节点都应指向它们的前任，使它们成为新的后继节点。 第一个节点将指向NULL。
我们将使用temp节点使头节点指向新的第一个节点。
链接列表现在已反转。 要查看C编程语言中的链表实现，请单击此处 。
Data Structure - Doubly Linked List
双向链接列表是链接列表的变体，与单链接列表相比，可以以两种方式轻松地向前和向后导航。 以下是理解双向链表概念的重要术语。
Link - 链接列表的每个链接都可以存储称为元素的数据。
Next - 链接列表的每个链接都包含指向下一个名为Next的链接的链接。
Prev - 链表的每个链接都包含一个名为Prev的上一个链接的链接。
LinkedList - 链接列表包含指向名为First的第一个链接和名为Last的最后一个链接的连接链接。
双重链表清单表示
根据以上说明，以下是要考虑的重点。
双链表包含一个名为first和last的链接元素。
每个链路都带有一个数据字段和两个名为next和prev的链接字段。
每个链接使用其下一个链接与其下一个链接链接。
每个链接使用其先前的链接与其先前的链接链接。
最后一个链接带有一个null链接以标记列表的结尾。
基本操作 (Basic Operations)
以下是列表支持的基本操作。
Insertion - 在列表的开头添加元素。
Deletion - 删除列表开头的元素。
Insert Last - 在列表末尾添加元素。
Delete Last删除 - 从列表末尾删除元素。
Insert After - 在列表项Insert After添加元素。
Delete - 使用键从列表中删除元素。
Display forward - 以转发方式显示完整列表。
Display backward显示 - 以向后方式显示完整列表。
插入操作 (Insertion Operation)
下面的代码演示了双向链表开头的插入操作。
例子 (Example)
//insert link at the first location
void insertFirst(int key, int data) {
//create a link
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key = key;
link->data = data;
if(isEmpty()) {
//make it the last link
last = link;
} else {
//update first prev link
head->prev = link;
}
//point it to old first link
link->next = head;
//point first to new first link
head = link;
}
删除操作 (Deletion Operation)
下面的代码演示了双向链表开头的删除操作。
例子 (Example)
//delete first item
struct node* deleteFirst() {
//save reference to first link
struct node *tempLink = head;
//if only one link
if(head->next == NULL) {
last = NULL;
} else {
head->next->prev = NULL;
}
head = head->next;
//return the deleted link
return tempLink;
}
在操作结束时插入
下面的代码演示了双向链表的最后一个位置的插入操作。
例子 (Example)
//insert link at the last location
void insertLast(int key, int data) {
//create a link
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key = key;
link->data = data;
if(isEmpty()) {
//make it the last link
last = link;
} else {
//make link a new last link
last->next = link;
//mark old last node as prev of new link
link->prev = last;
}
//point last to new last node
last = link;
}
要查看C编程语言的实现，请单击此处 。
Data Structure - Circular Linked List
圆形链接列表是链接列表的变体，其中第一个元素指向最后一个元素，最后一个元素指向第一个元素。 单链表和双链表都可以制成循环链表。
单链表作为通函
在单链表中，最后一个节点的下一个指针指向第一个节点。
双重挂钩清单为通函
在双向链表中，最后一个节点的下一个指针指向第一个节点，第一个节点的前一个指针指向最后一个节点，在两个方向上形成圆形。
根据以上说明，以下是要考虑的重点。
最后一个链接的下一个链接指向列表的第一个链接，无论是单链还是双链表。
在双链表的情况下，第一个链接的前一个指向列表的最后一个。
基本操作 (Basic Operations)
以下是循环列表支持的重要操作。
insert - 在列表的开头插入一个元素。
delete - 从列表的开头删除元素。
display - 显示列表。
插入操作 (Insertion Operation)
下面的代码演示了基于单个链表的循环链表中的插入操作。
例子 (Example)
//insert link at the first location
void insertFirst(int key, int data) {
//create a link
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key = key;
link->data= data;
if (isEmpty()) {
head = link;
head->next = head;
} else {
//point it to old first node
link->next = head;
//point first to new first node
head = link;
}
}
删除操作 (Deletion Operation)
下面的代码演示了基于单个链表的循环链表中的删除操作。
//delete first item
struct node * deleteFirst() {
//save reference to first link
struct node *tempLink = head;
if(head->next == head) {
head = NULL;
return tempLink;
}
//mark next to first link as first
head = head->next;
//return the deleted link
return tempLink;
}
显示列表操作
以下代码演示了循环链表中的显示列表操作。
//display the list
void printList() {
struct node *ptr = head;
printf("\n[ ");
//start from the beginning
if(head != NULL) {
while(ptr->next != ptr) {
printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;
}
}
printf(" ]");
}
要了解它在C编程语言中的实现，请单击此处 。
Data Structure and Algorithms - Stack
堆栈是一种抽象数据类型（ADT），通常用于大多数编程语言。 它被命名为堆栈，因为它的行为类似于真实世界的堆栈，例如 - 一副牌或一堆盘子等。
真实世界的堆栈仅允许在一端进行操作。 例如，我们只能从堆叠顶部放置或移除卡或板。 同样，Stack ADT仅允许一端的所有数据操作。 在任何给定时间，我们只能访问堆栈的顶部元素。
此功能使其成为LIFO数据结构。 LIFO代表Last-in-first-out。 这里，首先访问最后放置（插入或添加）的元素。 在堆栈术语中，插入操作称为PUSH操作，删除操作称为POP操作。
堆栈表示
下图描绘了一个堆栈及其操作 -
堆栈可以通过数组，结构，指针和链接列表来实现。 堆栈可以是固定大小的堆栈，也可以具有动态调整大小的感觉。 在这里，我们将使用数组实现堆栈，这使得它成为固定大小的堆栈实现。
基本操作 (Basic Operations)
堆栈操作可能涉及初始化堆栈，使用它然后取消初始化。 除了这些基本内容之外，堆栈还用于以下两个主要操作 -
push() - 在堆栈上推送（存储）一个元素。
pop() - 从堆栈中删除（访问）一个元素。
当数据被推入堆栈时。
要有效地使用堆栈，我们还需要检查堆栈的状态。 出于同样的目的，将以下功能添加到堆栈中 -
peek() - 获取堆栈的顶部数据元素，而不删除它。
isFull() - 检查堆栈是否已满。
isEmpty() - 检查堆栈是否为空。
在任何时候，我们都维护一个指向堆栈上最后一个PUSHed数据的指针。 由于此指针始终表示堆栈的顶部，因此命名为top 。 top指针提供堆栈的最高值而不实际删除它。
首先，我们应该了解支持堆栈功能的过程 -
peek()
peek（）函数的算法 -
begin procedure peek
return stack[top]
end procedure
用C编程语言实现peek（）函数 -
Example
int peek() {
return stack[top];
}
isfull()
isfull（）函数的算法 -
begin procedure isfull
if top equals to MAXSIZE
return true
else
return false
endif
end procedure
在C编程语言中实现isfull（）函数 -
Example
bool isfull() {
if(top == MAXSIZE)
return true;
else
return false;
}
isempty()
isempty（）函数的算法 -
begin procedure isempty
if top less than 1
return true
else
return false
endif
end procedure
在C编程语言中实现isempty（）函数略有不同。 我们将top初始化为-1，因为数组中的索引从0开始。因此我们检查top是否低于零或-1以确定堆栈是否为空。 这是代码 -
Example
bool isempty() {
if(top == -1)
return true;
else
return false;
}
推动操作
将新数据元素放入堆栈的过程称为推送操作。 推送操作涉及一系列步骤 -
Step 1 - 检查堆栈是否已满。
Step 2 - 如果堆栈已满，则产生错误并退出。
Step 3 - 如果堆栈未满，则top增加下一个空白区域。
Step 4 - 将数据元素添加到堆栈位置，top指向该位置。
Step 5 - 返回成功。
如果链表用于实现堆栈，那么在步骤3中，我们需要动态分配空间。
PUSH操作的算法
推送操作的简单算法可以推导如下 -
begin procedure push: stack, data
if stack is full
return null
endif
top ← top + 1
stack[top] ← data
end procedure
在C中实现这个算法非常容易。 请参阅以下代码 -
Example
void push(int data) {
if(!isFull()) {
top = top + 1;
stack[top] = data;
} else {
printf("Could not insert data, Stack is full.\n");
}
}
流行操作
从堆栈中删除内容时访问内容称为弹出操作。 在pop（）操作的数组实现中，实际上并未移除数据元素，而是将top递减到堆栈中的较低位置以指向下一个值。 但是在链表实现中，pop（）实际上删除了数据元素并释放了内存空间。
Pop操作可能涉及以下步骤 -
Step 1 - 检查堆栈是否为空。
Step 2 - 如果堆栈为空，则产生错误并退出。
Step 3 - 如果堆栈不为空，则访问top指向的数据元素。
Step 4 - 将top的值减1。
Step 5 - 返回成功。
流行操作算法
一个简单的Pop操作算法可以推导如下 -
begin procedure pop: stack
if stack is empty
return null
endif
data ← stack[top]
top ← top - 1
return data
end procedure
在C中实现该算法如下 -
Example
int pop(int data) {
if(!isempty()) {
data = stack[top];
top = top - 1;
return data;
} else {
printf("Could not retrieve data, Stack is empty.\n");
}
}
有关C编程语言的完整堆栈程序，请单击此处 。
Data Structure - Expression Parsing
编写算术表达式的方法称为notation 。 算术表达式可以用三种不同但等效的符号书写，即不改变表达式的本质或输出。 这些符号是 -
- Infix Notation
- 前缀（波兰语）表示法
- 后缀（反向波兰）表示法
这些符号被命名为它们如何在表达式中使用运算符。 我们将在本章中学到相同的内容。
中缀表示法
我们用中infix表示法编写表达式，例如a - b + c，其中运算符用in操作数之间。 我们人类很容易用中缀符号进行读，写和说话，但同样适用于计算设备。 在时间和空间消耗方面，处理中缀符号的算法可能是困难且昂贵的。
前缀表示法
在这种表示法中，运算符是操作数的prefix ，即操作符在操作数之前写入。 例如， +ab 。 这相当于其中缀符号a + b 。 前缀表示法也称为Polish Notation 。
后缀表示法
这种符号样式称为Reversed Polish Notation 。 在这种表示法样式中，运算符postfix为操作数，即操作符在操作数之后写入。 例如， ab+ 。 这相当于其中缀符号a + b 。
下表简要介绍了所有三种符号的区别 -
| Sr.No. | 中缀表示法 | 前缀表示法 | 后缀表示法 |
|---|---|---|---|
| 1 | a + b | + ab | ab + |
| 2 | （a + b）* c | * + abc | ab + c * |
| 3 | a *（b + c） | * a + bc | abc + * |
| 4 | a/b + c/d | +/ab/cd | ab/cd/+ |
| 5 | （a + b）*（c + d） | * + ab + cd | ab + cd + * |
| 6 | （（a + b）* c） - d | - * + abcd | ab + c * d - |
解析表达式
正如我们已经讨论过的，设计一个解析中缀符号的算法或程序并不是一种非常有效的方法。 相反，这些中缀符号首先转换为后缀或前缀表示法，然后进行计算。
要解析任何算术表达式，我们还需要处理运算符优先级和关联性。
优先级 Precedence
当操作数位于两个不同的运算符之间时，哪个运算符将首先取操作数，由运算符优先于其他运算符决定。 例如 -
由于乘法运算优先于加法，因此将首先计算b * c。 稍后提供运算符优先级表。
结合性 Associativity
关联性描述了具有相同优先级的运算符出现在表达式中的规则。 例如，在表达式a + b -c中，+和 - 具有相同的优先级，然后表达式的哪个部分将首先被评估，由这些运算符的关联性决定。 这里，+和 - 都是左关联的，因此表达式将被评估为(a + b) − c 。
优先级和关联性决定了表达式的评估顺序。 以下是运算符优先级和关联表（从最高到最低） -
| Sr.No. | 操作者 | 优先权 | 关联性 |
|---|---|---|---|
| 1 | Exponentiation ^ | Highest | Right Associative |
| 2 | 乘法（*）和除法（/） | Second Highest | Left Associative |
| 3 | 加法（+）和减法（ - ） | Lowest | Left Associative |
上表显示了运算符的默认行为。 在表达式评估的任何时间点，可以使用括号来更改顺序。 例如 -
在a + b*c ，首先评估表达式部分b * c ，乘法作为加法的优先级。 我们在这里使用括号来首先评估(a + b)*c ，如(a + b)*c 。
后缀评估算法
我们现在来看看如何评估后缀表示法的算法 -
Step 1 − scan the expression from left to right
Step 2 − if it is an operand push it to stack
Step 3 − if it is an operator pull operand from stack and perform operation
Step 4 − store the output of step 3, back to stack
Step 5 − scan the expression until all operands are consumed
Step 6 − pop the stack and perform operation
要查看C编程语言的实现，请单击此处 。
Data Structure and Algorithms - Queue
队列是一种抽象的数据结构，有点类似于Stacks。 与堆栈不同，队列的两端都是开放的。 一端始终用于插入数据（入队），另一端用于删除数据（出队）。 队列遵循先进先出方法，即首先访问先存储的数据项。
一个真实的队列示例可以是单车道单向道路，车辆首先进入，首先退出。 更多真实世界的例子可以看作是售票窗口和公共汽车站的队列。
队列表示
我们现在明白，在队列中，我们出于不同的原因访问两端。 下面给出的下图试图将队列表示解释为数据结构 -
与堆栈一样，也可以使用数组，链接列表，指针和结构来实现队列。 为简单起见，我们将使用一维数组实现队列。
基本操作 (Basic Operations)
队列操作可能涉及初始化或定义队列，利用它，然后从存储器中完全擦除它。 在这里，我们将尝试理解与队列相关的基本操作 -
enqueue() - 将项添加（存储）到队列中。
dequeue() - 从队列中删除（访问）一个项目。
为了使上述队列操作有效，需要更多的功能。 这些是 -
peek() - 获取队列前面的元素而不删除它。
isfull() - 检查队列是否已满。
isempty() - 检查队列是否为空。
在队列中，我们总是将front指针指向的数据出列（或访问），并在队列中排队（或存储）数据时我们采用rear指针的帮助。
让我们首先了解一下队列的支持功能 -
peek()
此功能有助于查看队列front的数据。 peek（）函数的算法如下 -
Algorithm
begin procedure peek
return queue[front]
end procedure
用C编程语言实现peek（）函数 -
Example
int peek() {
return queue[front];
}
isfull()
由于我们使用单维数组来实现队列，我们只需检查后指针是否达到MAXSIZE以确定队列已满。 如果我们将队列保存在循环链表中，算法将有所不同。 isfull（）函数的算法 -
Algorithm
begin procedure isfull
if rear equals to MAXSIZE
return true
else
return false
endif
end procedure
在C编程语言中实现isfull（）函数 -
Example
bool isfull() {
if(rear == MAXSIZE - 1)
return true;
else
return false;
}
isempty()
isempty（）函数的算法 -
Algorithm
begin procedure isempty
if front is less than MIN OR front is greater than rear
return true
else
return false
endif
end procedure
如果front的值小于MIN或0，则表示队列尚未初始化，因此为空。
这是C编程代码 -
Example
bool isempty() {
if(front < 0 || front > rear)
return true;
else
return false;
}
入队行动
队列维护两个数据指针， front和rear 。 因此，其操作比堆栈的操作相对难以实现。
应采取以下步骤将数据排入（插入）到队列中 -
Step 1 - 检查队列是否已满。
Step 2 - 如果队列已满，则产生溢出错误并退出。
Step 3 - 如果队列未满，则增加rear指针以指向下一个空白区域。
Step 4 - 将数据元素添加到后方指向的队列位置。
Step 5 - 返回成功。
有时，我们还会检查队列是否已初始化，以处理任何无法预料的情况。
入队操作算法
procedure enqueue(data)
if queue is full
return overflow
endif
rear ← rear + 1
queue[rear] ← data
return true
end procedure
在C编程语言中实现enqueue（） -
Example
int enqueue(int data)
if(isfull())
return 0;
rear = rear + 1;
queue[rear] = data;
return 1;
end procedure
出列操作
从队列中访问数据是两个任务的过程 - 访问front指向的数据并在访问后删除数据。 采取以下步骤来执行dequeue操作 -
Step 1 - 检查队列是否为空。
Step 2 - 如果队列为空，则产生下溢错误并退出。
Step 3 - 如果队列不为空，请访问front指向的数据。
Step 4 - 增加front指针以指向下一个可用数据元素。
Step 5 - 返回成功。
出列操作的算法
procedure dequeue
if queue is empty
return underflow
end if
data = queue[front]
front ← front + 1
return true
end procedure
在C编程语言中实现dequeue（） -
Example
int dequeue() {
if(isempty())
return 0;
int data = queue[front];
front = front + 1;
return data;
}
有关C编程语言的完整Queue程序，请单击此处 。
Data Structure and Algorithms Linear Search
线性搜索是一种非常简单的搜索算法。 在这种类型的搜索中，逐个对所有项目进行顺序搜索。 检查每个项目，如果找到匹配项，则返回该特定项目，否则搜索将继续，直到数据收集结束。
算法 (Algorithm)
Linear Search ( Array A, Value x)
Step 1: Set i to 1
Step 2: if i > n then go to step 7
Step 3: if A[i] = x then go to step 6
Step 4: Set i to i + 1
Step 5: Go to Step 2
Step 6: Print Element x Found at index i and go to step 8
Step 7: Print element not found
Step 8: Exit
伪代码 (Pseudocode)
procedure linear_search (list, value)
for each item in the list
if match item == value
return the item's location
end if
end for
end procedure
要了解C编程语言中的线性搜索实现，请click-here 。
Data Structure and Algorithms Binary Search
二进制搜索是一种快速搜索算法，运行时复杂度为Ο（log n）。 这种搜索算法的工作原则是分而治之。 为使此算法正常工作，数据收集应采用排序形式。
二进制搜索通过比较集合的最中间项来查找特定项。 如果匹配发生，则返回项目的索引。 如果中间项大于项，则在中间项左侧的子阵列中搜索项。 否则，在中间项右侧的子阵列中搜索项。 该过程也在子阵列上继续，直到子阵列的大小减小到零。
二进制搜索如何工作？
要使二进制搜索起作用，必须对目标数组进行排序。 我们将通过一个图例来学习二元搜索的过程。 以下是我们的排序数组，让我们假设我们需要使用二进制搜索来搜索值31的位置。
首先，我们将使用此公式确定数组的一半 -
mid = low + (high - low)/2
这里，0 +（9-0）/ 2 = 4（整数值为4.5）。 所以，4是数组的中间位置。
现在我们将存储在位置4的值与搜索的值进行比较，即31.我们发现位置4的值是27，这不匹配。 由于值大于27并且我们有一个排序数组，因此我们也知道目标值必须位于数组的上半部分。
我们将低点改为+1，再次找到新的中值。
low = mid + 1
mid = low + (high - low)/2
我们新的中期现在是7。 我们将位置7处存储的值与目标值31进行比较。
存储在位置7的值不匹配，而是比我们正在寻找的值更多。 因此，该值必须位于此位置的下半部分。
因此，我们再次计算中期。 这次是5。
我们将位置5处存储的值与目标值进行比较。 我们发现这是一场比赛。
我们得出结论，目标值31存储在位置5处。
二进制搜索将可搜索项目减半，从而减少了对更少数字进行比较的次数。
伪代码 (Pseudocode)
二进制搜索算法的伪代码应如下所示 -
Procedure binary_search
A ← sorted array
n ← size of array
x ← value to be searched
Set lowerBound = 1
Set upperBound = n
while x not found
if upperBound < lowerBound
EXIT: x does not exists.
set midPoint = lowerBound + ( upperBound - lowerBound )/2
if A[midPoint] < x
set lowerBound = midPoint + 1
if A[midPoint] > x
set upperBound = midPoint - 1
if A[midPoint] = x
EXIT: x found at location midPoint
end while
end procedure
要了解使用C编程语言中的数组进行二进制搜索实现，请单击此处 。
Data Structure - Interpolation Search
插值搜索是二进制搜索的改进变体。 该搜索算法适用于所需值的探测位置。 为使此算法正常工作，数据收集应采用排序形式并均匀分布。
二进制搜索与线性搜索相比具有时间复杂性的巨大优势。 线性搜索具有Ο（n）的最坏情况复杂度，而二分搜索具有Ο（log n）。
存在可以预先知道目标数据的位置的情况。 例如，如果是电话目录，我们是否要搜索Morphius的电话号码。 在这里，线性搜索甚至二进制搜索看起来都很慢，因为我们可以直接跳转到存储名称从“M”开始的存储空间。
定位二进制搜索
在二进制搜索中，如果未找到所需数据，则列表的其余部分分为两部分，即较低和较高。 搜索是在其中任何一个中进行的。
即使对数据进行排序，二进制搜索也不会利用探测所需数据的位置。
插值搜索中的位置探测
插值搜索通过计算探测位置来找到特定项目。 最初，探针位置是集合中间项目的位置。
如果发生匹配，则返回该项的索引。 要将列表拆分为两部分，我们使用以下方法 -
mid = Lo + ((Hi - Lo)/(A[Hi] - A[Lo])) * (X - A[Lo])
where −
A = list
Lo = Lowest index of the list
Hi = Highest index of the list
A[n] = Value stored at index n in the list
如果中间项大于项，则再次在中间项右侧的子阵列中计算探测位置。 否则，在中间项左侧的子阵列中搜索该项。 该过程也在子阵列上继续，直到子阵列的大小减小到零。
与有利情况下的BST的Ο(log n)相比，插值搜索算法的运行时复杂度是Ο(log (log n)) 。
算法 (Algorithm)
由于它是现有BST算法的即兴创作，我们提到了使用位置探测搜索“目标”数据值索引的步骤 -
Step 1 − Start searching <b class="notranslate">data</b> from middle of the list.
Step 2 − If it is a match, return the index of the item, and exit.
Step 3 − If it is not a match, probe position.
Step 4 − Divide the list using probing formula and find the new midle.
Step 5 − If data is greater than middle, search in higher sub-list.
Step 6 − If data is smaller than middle, search in lower sub-list.
Step 7 − Repeat until match.
伪代码 (Pseudocode)
A → Array list
N → Size of A
X → Target Value
Procedure Interpolation_Search()
Set Lo → 0
Set Mid → -1
Set Hi → N-1
While X does not match
if Lo equals to Hi OR A[Lo] equals to A[Hi]
EXIT: Failure, Target not found
end if
Set Mid = Lo + ((Hi - Lo)/(A[Hi] - A[Lo])) * (X - A[Lo])
if A[Mid] = X
EXIT: Success, Target found at Mid
else
if A[Mid] < X
Set Lo to Mid+1
else if A[Mid] > X
Set Hi to Mid-1
end if
end if
End While
End Procedure
要了解C编程语言中插值搜索的实现， 请单击此处 。
Data Structure and Algorithms - Hash Table
哈希表是以关联方式存储数据的数据结构。 在散列表中，数据以数组格式存储，其中每个数据值都有自己唯一的索引值。 如果我们知道所需数据的索引，则访问数据会变得非常快。
因此，它成为一种数据结构，其中插入和搜索操作非常快，而与数据的大小无关。 散列表使用数组作为存储介质，并使用散列技术生成索引，其中要插入元素或将要定位元素。
Hashing
散列是一种将一系列键值转换为数组索引范围的技术。 我们将使用模运算符来获取一系列键值。 考虑大小为20的哈希表的示例，并且要存储以下项目。 项目采用（键，值）格式。
- (1,20)
- (2,70)
- (42,80)
- (4,25)
- (12,44)
- (14,32)
- (17,11)
- (13,78)
- (37,98)
| Sr.No. | 键 | 哈希 | 数组索引 |
|---|---|---|---|
| 1 | 1 | 1％20 = 1 | 1 |
| 2 | 2 | 2％20 = 2 | 2 |
| 3 | 42 | 42％20 = 2 | 2 |
| 4 | 4 | 4％20 = 4 | 4 |
| 5 | 12 | 12％20 = 12 | 12 |
| 6 | 14 | 14％20 = 14 | 14 |
| 7 | 17 | 17％20 = 17 | 17 |
| 8 | 13 | 13％20 = 13 | 13 |
| 9 | 37 | 37％20 = 17 | 17 |
线性探测
我们可以看到，可能会发生散列技术用于创建已使用的数组索引。 在这种情况下，我们可以通过查看下一个单元格来搜索数组中的下一个空位置，直到找到一个空单元格。 这种技术称为线性探测。
| Sr.No. | 键 | 哈希 | 数组索引 | 线性探测后，阵列索引 |
|---|---|---|---|---|
| 1 | 1 | 1％20 = 1 | 1 | 1 |
| 2 | 2 | 2％20 = 2 | 2 | 2 |
| 3 | 42 | 42％20 = 2 | 2 | 3 |
| 4 | 4 | 4％20 = 4 | 4 | 4 |
| 5 | 12 | 12％20 = 12 | 12 | 12 |
| 6 | 14 | 14％20 = 14 | 14 | 14 |
| 7 | 17 | 17％20 = 17 | 17 | 17 |
| 8 | 13 | 13％20 = 13 | 13 | 13 |
| 9 | 37 | 37％20 = 17 | 17 | 18 |
基本操作 (Basic Operations)
以下是哈希表的基本主要操作。
Search - 搜索哈希表中的元素。
Insert - 在哈希表中插入元素。
delete - 从哈希表中删除元素。
DataItem
定义具有一些数据和密钥的数据项，基于该数据项在哈希表中进行搜索。
struct DataItem {
int data;
int key;
};
哈希方法
定义散列方法以计算数据项的键的散列码。
int hashCode(int key){
return key % SIZE;
}
搜索操作 (Search Operation)
每当要搜索元素时，计算传递的密钥的哈希码，并使用该哈希码作为数组中的索引来定位元素。 如果在计算的哈希码中找不到元素，则使用线性探测来获取元素。
例子 (Example)
struct DataItem *search(int key) {
//get the hash
int hashIndex = hashCode(key);
//move in array until an empty
while(hashArray[hashIndex] != NULL) {
if(hashArray[hashIndex]->key == key)
return hashArray[hashIndex];
//go to next cell
++hashIndex;
//wrap around the table
hashIndex %= SIZE;
}
return NULL;
}
插入操作 (Insert Operation)
每当要插入元素时，计算传递的密钥的哈希码，并使用该哈希码作为数组中的索引来定位索引。 如果在计算的哈希码处找到元素，则对空位置使用线性探测。
例子 (Example)
void insert(int key,int data) {
struct DataItem *item = (struct DataItem*) malloc(sizeof(struct DataItem));
item->data = data;
item->key = key;
//get the hash
int hashIndex = hashCode(key);
//move in array until an empty or deleted cell
while(hashArray[hashIndex] != NULL && hashArray[hashIndex]->key != -1) {
//go to next cell
++hashIndex;
//wrap around the table
hashIndex %= SIZE;
}
hashArray[hashIndex] = item;
}
删除操作 (Delete Operation)
每当要删除元素时，计算传递的密钥的哈希码，并使用该哈希码作为数组中的索引来定位索引。 如果在计算的哈希码中找不到元素，则使用线性探测来获取元素。 找到后，在那里存储一个虚拟项目，以保持哈希表的性能不变。
例子 (Example)
struct DataItem* delete(struct DataItem* item) {
int key = item->key;
//get the hash
int hashIndex = hashCode(key);
//move in array until an empty
while(hashArray[hashIndex] !=NULL) {
if(hashArray[hashIndex]->key == key) {
struct DataItem* temp = hashArray[hashIndex];
//assign a dummy item at deleted position
hashArray[hashIndex] = dummyItem;
return temp;
}
//go to next cell
++hashIndex;
//wrap around the table
hashIndex %= SIZE;
}
return NULL;
}
要了解C编程语言中的哈希实现，请单击此处 。
Data Structure - Sorting Techniques
排序是指以特定格式排列数据。 排序算法指定按特定顺序排列数据的方式。 最常见的订单是按数字或字典顺序排列的。
排序的重要性在于，如果数据以排序的方式存储，则数据搜索可以被优化到非常高的水平。 排序还用于以更易读的格式表示数据。 以下是在现实场景中排序的一些示例 -
Telephone Directory - 电话簿存储按姓名分类的人的电话号码，以便可以轻松搜索姓名。
Dictionary - 字典按字母顺序存储单词，以便搜索任何单词变得容易。
就地排序和非就地排序
排序算法可能需要一些额外的空间用于比较和临时存储少量数据元素。 这些算法不需要任何额外的空间，并且据说排序就地发生，或者例如在阵列本身内发生。 这称为in-place sorting 。 冒泡排序是就地排序的一个例子。
但是，在某些排序算法中，程序需要的空间大于或等于被排序的元素。 使用相等或更多空间的排序称为not-in-place sorting 。 Merge-sort是非就地排序的一个例子。
稳定和不稳定的排序
如果排序算法在排序内容之后不会改变它们出现的类似内容的顺序，则称为stable sorting 。
如果排序算法在排序内容之后改变它们出现的类似内容的顺序，则称为unstable sorting 。
当我们希望保持原始元素的序列时，算法的稳定性很重要，例如在元组中。
自适应非自适应排序算法
如果排序算法利用了要排序的列表中已经“排序”的元素，则称该排序算法是自适应的。 也就是说，在排序源列表中是否已经对某些元素进行了排序时，自适应算法会将此考虑在内并尝试不对它们进行重新排序。
非自适应算法是不考虑已经排序的元素的算法。 他们试图强制重新排序每个元素以确认其排序。
重要术语 (Important Terms)
有些术语通常在讨论排序技术时被创造出来，这里简要介绍一下 -
增加订单
如果连续元素大于前一个元素，则称一系列值按increasing order 。 例如，1,3,4,6,8,9按递增顺序排列，因为每个下一个元素都大于前一个元素。
减少订单
如果连续元素小于当前元素，则称一系列值按decreasing order 。 例如，9,8,6,4,3,1按递减顺序排列，因为每个下一个元素都小于前一个元素。
Non-Increasing Order
如果连续元素小于或等于序列中的前一元素，则称一系列值以non-increasing order顺序。 当序列包含重复值时，会发生此顺序。 例如，9,8,6,3,3,1处于非递增顺序，因为每个下一个元素小于或等于（在3的情况下）但不大于任何先前元素。
Non-Decreasing Order
如果连续元素大于或等于序列中的前一元素，则称一系列值以non-decreasing order顺序。 当序列包含重复值时，会发生此顺序。 例如，1,3,3,6,8,9是非递减顺序，因为每个下一个元素大于或等于（在3的情况下）但不小于前一个。
Data Structure - Bubble Sort Algorithm
冒泡排序是一种简单的排序算法。 该排序算法是基于比较的算法，其中比较每对相邻元素，并且如果元素不按顺序则交换元素。 该算法不适用于大数据集，因为其平均和最差情况复杂度为0（n 2 ），其中n是项目数。
冒泡排序如何工作？
我们以一个未排序的数组为例。 冒泡排序花费Ο（n 2 ）时间，因此我们保持简短和精确。
冒泡排序从前两个元素开始，比较它们以检查哪一个更大。
在这种情况下，值33大于14，因此它已经在已排序的位置。 接下来，我们将33与27进行比较。
我们发现27小于33并且必须交换这两个值。
新数组应如下所示 -
接下来我们比较33和35.我们发现两者都处于已排序的位置。
然后我们转到接下来的两个值，35和10。
我们当时知道10小了35.因此它们没有排序。
我们交换这些值。 我们发现我们已经到了数组的末尾。 一次迭代后，数组应如下所示 -
确切地说，我们现在展示了每次迭代后数组的外观。 在第二次迭代之后，它应该看起来像这样 -
请注意，在每次迭代后，至少有一个值在末尾移动。
当不需要交换时，bubblesorts会知道数组是完全排序的。
现在我们应该研究一下泡沫排序的一些实际方面。
算法 (Algorithm)
我们假设list是n元素的数组。 我们进一步假设swap函数交换给定数组元素的值。
begin BubbleSort(list)
for all elements of list
if list[i] > list[i+1]
swap(list[i], list[i+1])
end if
end for
return list
end BubbleSort
伪代码 (Pseudocode)
我们在算法中观察到，冒号排序比较每对数组元素，除非整个数组按升序完全排序。 这可能会导致一些复杂性问题，例如，如果所有元素都已经提升，那么数组不需要更多交换。
为了解决问题，我们使用一个swapped标志变量，它将帮助我们查看是否发生了任何交换。 如果没有发生交换，即数组不再需要进行排序处理，它将退出循环。
BubbleSort算法的伪代码可以写成如下 -
procedure bubbleSort( list : array of items )
loop = list.count;
for i = 0 to loop-1 do:
swapped = false
for j = 0 to loop-1 do:
/* compare the adjacent elements */
if list[j] > list[j+1] then
/* swap them */
swap( list[j], list[j+1] )
swapped = true
end if
end for
/*if no number was swapped that means
array is sorted now, break the loop.*/
if(not swapped) then
break
end if
end for
end procedure return list
实现 (Implementation)
我们在原始算法及其即兴伪代码中未解决的另一个问题是，在每次迭代之后，最高值在数组末尾处稳定下来。 因此，下一次迭代不需要包括已经排序的元素。 为此，在我们的实现中，我们限制内部循环以避免已经排序的值。
要了解C编程语言中的冒泡排序实现，请单击此处 。
Data Structure and Algorithms Insertion Sort
这是一种基于比较的就地排序算法。 这里，维护一个始终排序的子列表。 例如，维护数组的下半部分以进行排序。 要在此已排序的子列表中“插入”的元素必须找到其适当的位置，然后必须将其插入其中。 因此名称， insertion sort 。
按顺序搜索数组，移动未排序的项并将其插入排序的子列表（在同一数组中）。 该算法不适用于大数据集，因为其平均和最差情况复杂度为0（n 2 ），其中n是项目数。
插入排序如何工作？
我们以一个未排序的数组为例。
插入排序比较前两个元素。
它发现14和33都已按升序排列。 目前，14位于已排序的子列表中。
插入排序向前移动并将33与27进行比较。
并发现33不在正确的位置。
它将33与27交换。它还检查已排序子列表的所有元素。 在这里，我们看到排序的子列表只有一个元素14，而27大于14.因此，排序的子列表在交换后仍然排序。
到目前为止，我们在已排序的子列表中有14和27。 接下来，它将33与10进行比较。
这些值不是按排序顺序排列的。
所以我们交换它们。
但是，交换使27和10未分类。
因此，我们也交换它们。
我们再次以未排序的顺序找到14和10。
我们再次交换它们。 到第三次迭代结束时，我们有一个包含4个项目的已排序子列表。
此过程将继续，直到排序的子列表中包含所有未排序的值。 现在我们将看到插入排序的一些编程方面。
算法 (Algorithm)
现在我们对这种排序技术的工作原理有了更大的了解，因此我们可以推导出简单的步骤来实现插入排序。
<b class="notranslate">Step 1</b> − If it is the first element, it is already sorted. return 1;
<b class="notranslate">Step 2</b> − Pick next element
<b class="notranslate">Step 3</b> − Compare with all elements in the sorted sub-list
<b class="notranslate">Step 4</b> − Shift all the elements in the sorted sub-list that is greater than the
value to be sorted
<b class="notranslate">Step 5</b> − Insert the value
<b class="notranslate">Step 6</b> − Repeat until list is sorted
伪代码 (Pseudocode)
procedure insertionSort( A : array of items )
int holePosition
int valueToInsert
for i = 1 to length(A) inclusive do:
/* select value to be inserted */
valueToInsert = A[i]
holePosition = i
/*locate hole position for the element to be inserted */
while holePosition > 0 and A[holePosition-1] > valueToInsert do:
A[holePosition] = A[holePosition-1]
holePosition = holePosition -1
end while
/* insert the number at hole position */
A[holePosition] = valueToInsert
end for
end procedure
要了解C编程语言中的插入排序实现，请单击此处 。
Data Structure and Algorithms Selection Sort
选择排序是一种简单的排序算法。 这种排序算法是一种就地比较算法，其中列表分为两部分，左端的排序部分和右端的未排序部分。 最初，排序部分为空，未排序部分为整个列表。
最小元素从未排序数组中选择，并与最左边的元素交换，该元素成为排序数组的一部分。 此过程继续将未排序的数组边界向右移动一个元素。
该算法不适用于大数据集，因为其平均和最差情况复杂度为0（n 2 ），其中n是项目数。
选择排序如何工作？
以下面描述的数组为例。
对于排序列表中的第一个位置，将按顺序扫描整个列表。 当前存储14的第一个位置，我们搜索整个列表并发现10是最低值。
所以我们用10代替14.在一次迭代10之后，恰好是列表中的最小值，出现在排序列表的第一个位置。
对于存在33的第二个位置，我们开始以线性方式扫描列表的其余部分。
我们发现14是列表中的第二低值，它应该出现在第二位。 我们交换这些值。
在两次迭代之后，两个最小值以排序的方式位于开头。
相同的过程应用于数组中的其余项。
以下是整个分拣过程的图示 -
现在，让我们学习一些选择排序的编程方面。
算法 (Algorithm)
<b class="notranslate">Step 1</b> − Set MIN to location 0
<b class="notranslate">Step 2</b> − Search the minimum element in the list
<b class="notranslate">Step 3</b> − Swap with value at location MIN
<b class="notranslate">Step 4</b> − Increment MIN to point to next element
<b class="notranslate">Step 5</b> − Repeat until list is sorted
伪代码 (Pseudocode)
procedure selection sort
list : array of items
n : size of list
for i = 1 to n - 1
/* set current element as minimum*/
min = i
/* check the element to be minimum */
for j = i+1 to n
if list[j] < list[min] then
min = j;
end if
end for
/* swap the minimum element with the current element*/
if indexMin != i then
swap list[min] and list[i]
end if
end for
end procedure
要了解C编程语言中的选择排序实现，请单击此处 。
Data Structures - Merge Sort Algorithm
合并排序是一种基于分而治之技术的排序技术。 在最坏情况下的时间复杂度为0（n log n）时，它是最受尊敬的算法之一。
合并排序首先将数组分成相等的一半，然后以排序的方式组合它们。
合并排序如何工作？
要理解合并排序，我们采用未排序的数组，如下所示 -
我们知道，除非实现原子值，否则合并排序首先将整个数组迭代地分成相等的一半。 我们在这里看到，8个项目的数组被分成两个大小为4的数组。
这不会改变原始项目的外观顺序。 现在我们将这两个数组分成两半。
我们进一步划分这些数组，我们实现原子价值，不能再划分。
现在，我们以完全相同的方式将它们组合在一起。 请注意这些列表的颜色代码。
我们首先比较每个列表的元素，然后以排序的方式将它们组合到另一个列表中。 我们看到14和33处于排序位置。 我们比较27和10并且在2个值的目标列表中我们首先放置10个，然后是27.我们改变19和35的顺序，而顺序地放置42和44。
在组合阶段的下一次迭代中，我们比较两个数据值的列表，并将它们合并到找到的数据值列表中，所有这些值都按排序顺序排列。
在最终合并之后，列表应如下所示 -
现在我们应该学习合并排序的一些编程方面。
算法 (Algorithm)
合并排序继续将列表分成相等的一半，直到它不再被分割。 根据定义，如果列表中只有一个元素，则对其进行排序。 然后，合并排序组合较小的排序列表，同时保持新列表的排序。
<b class="notranslate">Step 1</b> − if it is only one element in the list it is already sorted, return.
<b class="notranslate">Step 2</b> − divide the list recursively into two halves until it can no more be divided.
<b class="notranslate">Step 3</b> − merge the smaller lists into new list in sorted order.
伪代码 (Pseudocode)
我们现在将看到合并排序函数的伪代码。 我们的算法指出了两个主要功能 - 分而合。
合并排序适用于递归，我们将以相同的方式看到我们的实现。
procedure mergesort( var a as array )
if ( n == 1 ) return a
var l1 as array = a[0] ... a[n/2]
var l2 as array = a[n/2+1] ... a[n]
l1 = mergesort( l1 )
l2 = mergesort( l2 )
return merge( l1, l2 )
end procedure
procedure merge( var a as array, var b as array )
var c as array
while ( a and b have elements )
if ( a[0] > b[0] )
add b[0] to the end of c
remove b[0] from b
else
add a[0] to the end of c
remove a[0] from a
end if
end while
while ( a has elements )
add a[0] to the end of c
remove a[0] from a
end while
while ( b has elements )
add b[0] to the end of c
remove b[0] from b
end while
return c
end procedure
要了解C编程语言中的合并排序实现，请单击此处 。
Shell排序是一种高效的排序算法，基于插入排序算法。 该算法避免了大的移位，如插入排序的情况，如果较小的值是最右边的并且必须移动到最左边。
该算法对广泛传播的元素使用插入排序，首先对它们进行排序，然后对间距较小的元素进行排序。 该间距称为interval 。 此间隔基于Knuth的公式计算为 -
Knuth的公式
h = h * 3 + 1
where −
h is interval with initial value 1
该算法对于中等大小的数据集非常有效，因为其平均和最差情况复杂度为0（n），其中n是项目数。
Shell排序如何工作？
让我们考虑以下示例来了解shell排序的工作原理。 我们采用与前面示例中使用的相同的数组。 对于我们的示例和易于理解，我们采用间隔4.创建位于4个位置的所有值的虚拟子列表。 这些值是{35,14}，{33,19}，{42,27}和{10,44}
我们比较每个子列表中的值并在原始数组中交换它们（如果需要）。 完成此步骤后，新数组应如下所示 -
然后，我们采用2的间隔，这个差距产生两个子列表 - {14,27,35,42}，{19,10,33,44}
我们比较并交换原始数组中的值（如果需要）。 完成此步骤后，数组应如下所示 -
最后，我们使用值间隔1对数组的其余部分进行排序.Thell sort使用插入排序对数组进行排序。
以下是逐步描述 -
我们看到它只需要四次交换来对数组的其余部分进行排序。
算法 (Algorithm)
以下是shell排序的算法。
<b class="notranslate">Step 1</b> − Initialize the value of <i>h</i>
<b class="notranslate">Step 2</b> − Divide the list into smaller sub-list of equal interval <i>h</i>
<b class="notranslate">Step 3</b> − Sort these sub-lists using <b class="notranslate">insertion sort</b>
<b class="notranslate">Step 3</b> − Repeat until complete list is sorted
伪代码 (Pseudocode)
以下是shell排序的伪代码。
procedure shellSort()
A : array of items
/* calculate interval*/
while interval < A.length /3 do:
interval = interval * 3 + 1
end while
while interval > 0 do:
for outer = interval; outer < A.length; outer ++ do:
/* select value to be inserted */
valueToInsert = A[outer]
inner = outer;
/*shift element towards right*/
while inner > interval -1 && A[inner - interval] >= valueToInsert do:
A[inner] = A[inner - interval]
inner = inner - interval
end while
/* insert the number at hole position */
A[inner] = valueToInsert
end for
/* calculate interval*/
interval = (interval -1) /3;
end while
end procedure
要了解C编程语言中的shell排序实现，请单击此处 。
Data Structure and Algorithms - Shell Sort
Shell排序是一种高效的排序算法，基于插入排序算法。 该算法避免了大的移位，如插入排序的情况，如果较小的值是最右边的并且必须移动到最左边。
该算法对广泛传播的元素使用插入排序，首先对它们进行排序，然后对间距较小的元素进行排序。 该间距称为interval 。 此间隔基于Knuth的公式计算为 -
Knuth的公式
h = h * 3 + 1
where −
h is interval with initial value 1
该算法对于中等大小的数据集非常有效，因为该算法的平均和最坏情况复杂度取决于最着名的间隙序列是Ο（n），其中n是项目的数量。 最糟糕的情况是空间复杂度为O（n）。
Shell排序如何工作？
让我们考虑以下示例来了解shell排序的工作原理。 我们采用与前面示例中使用的相同的数组。 对于我们的示例和易于理解，我们采用间隔4.创建位于4个位置的所有值的虚拟子列表。 这些值是{35,14}，{33,19}，{42,27}和{10,44}
我们比较每个子列表中的值并在原始数组中交换它们（如果需要）。 完成此步骤后，新数组应如下所示 -
然后，我们取1的间隔，这个间隙产生两个子列表 - {14,27,35,42}，{19,10,33,44}
我们比较并交换原始数组中的值（如果需要）。 完成此步骤后，数组应如下所示 -
最后，我们使用值间隔1对数组的其余部分进行排序.Thell sort使用插入排序对数组进行排序。
以下是逐步描述 -
我们看到它只需要四次交换来对数组的其余部分进行排序。
算法 (Algorithm)
以下是shell排序的算法。
<b class="notranslate">Step 1</b> − Initialize the value of <i>h</i>
<b class="notranslate">Step 2</b> − Divide the list into smaller sub-list of equal interval <i>h</i>
<b class="notranslate">Step 3</b> − Sort these sub-lists using <b class="notranslate">insertion sort</b>
<b class="notranslate">Step 3</b> − Repeat until complete list is sorted
伪代码 (Pseudocode)
以下是shell排序的伪代码。
procedure shellSort()
A : array of items
/* calculate interval*/
while interval < A.length /3 do:
interval = interval * 3 + 1
end while
while interval > 0 do:
for outer = interval; outer < A.length; outer ++ do:
/* select value to be inserted */
valueToInsert = A[outer]
inner = outer;
/*shift element towards right*/
while inner > interval -1 && A[inner - interval] >= valueToInsert do:
A[inner] = A[inner - interval]
inner = inner - interval
end while
/* insert the number at hole position */
A[inner] = valueToInsert
end for
/* calculate interval*/
interval = (interval -1) /3;
end while
end procedure
要了解C编程语言中的shell排序实现，请单击此处 。
Data Structure and Algorithms - Quick Sort
快速排序是一种高效的排序算法，它基于将数据阵列划分为更小的数组。 一个大型数组被分成两个数组，其中一个数组的值小于指定的值，比如pivot，根据该数组创建分区，另一个数组保存的值大于数据透视值。
快速排序对数组进行分区，然后递归调用两次以对两个结果子数组进行排序。 该算法对于大尺寸数据集非常有效，因为其平均和最差情况复杂度为0（n 2 ），其中n是项目数。
快速排序中的分区
以下动画表示解释了如何在数组中查找透视值。
数据透视值将列表分为两部分。 并且递归地，我们找到每个子列表的轴，直到所有列表只包含一个元素。
快速排序枢轴算法
基于我们对快速排序中的分区的理解，我们现在将尝试为其编写算法，如下所示。
<b class="notranslate">Step 1</b> − Choose the highest index value has pivot
<b class="notranslate">Step 2</b> − Take two variables to point left and right of the list excluding pivot
<b class="notranslate">Step 3</b> − left points to the low index
<b class="notranslate">Step 4</b> − right points to the high
<b class="notranslate">Step 5</b> − while value at left is less than pivot move right
<b class="notranslate">Step 6</b> − while value at right is greater than pivot move left
<b class="notranslate">Step 7</b> − if both step 5 and step 6 does not match swap left and right
<b class="notranslate">Step 8</b> − if left ≥ right, the point where they met is new pivot
Quick Sort Pivot Pseudocode
上述算法的伪代码可以推导为 -
function partitionFunc(left, right, pivot)
leftPointer = left
rightPointer = right - 1
while True do
while A[++leftPointer] < pivot do
//do-nothing
end while
while rightPointer > 0 && A[--rightPointer] > pivot do
//do-nothing
end while
if leftPointer >= rightPointer
break
else
swap leftPointer,rightPointer
end if
end while
swap leftPointer,right
return leftPointer
end function
快速排序算法
递归地使用pivot算法，我们最终得到更小的可能分区。 然后处理每个分区以进行快速排序。 我们为quicksort定义递归算法如下 -
<b class="notranslate">Step 1</b> − Make the right-most index value pivot
<b class="notranslate">Step 2</b> − partition the array using pivot value
<b class="notranslate">Step 3</b> − quicksort left partition recursively
<b class="notranslate">Step 4</b> − quicksort right partition recursively
快速排序伪代码
要了解更多信息，请参阅伪代码以进行快速排序算法 -
procedure quickSort(left, right)
if right-left <= 0
return
else
pivot = A[right]
partition = partitionFunc(left, right, pivot)
quickSort(left,partition-1)
quickSort(partition+1,right)
end if
end procedure
要了解C编程语言中的快速排序实现，请单击此处 。
Data Structure - Graph Data Structure
图形是一组对象的图形表示，其中一些对象通过链接连接。 互连对象由称为vertices的点表示，连接顶点的链接称为edges 。
形式上，图形是一对集合(V, E) ，其中V是顶点集合， E是边缘集合，连接顶点对。 看看下面的图表 -
在上图中，
V = {a，b，c，d，e}
E = {ab，ac，bd，cd，de}
图数据结构
数学图可以用数据结构表示。 我们可以使用顶点数组和二维边数组来表示图形。 在我们继续前进之前，让我们熟悉一些重要的术语 -
Vertex - 图形的每个节点都表示为顶点。 在以下示例中，标记的圆圈表示顶点。 因此，A到G是顶点。 我们可以使用数组来表示它们，如下图所示。 这里A可以通过索引0来识别.B可以使用索引1来识别，依此类推。
Edge - 边表示两个顶点之间的路径或两个顶点之间的线。 在以下示例中，从A到B，B到C等的线表示边。 我们可以使用二维数组来表示数组，如下图所示。 这里AB可以在行0，列1，BC处表示为1，在行1，列2处依此类推，依此类推，将其他组合保持为0。
Adjacency - 如果两个节点或顶点通过边缘相互连接，则它们是相邻的。 在以下示例中，B与A相邻，C与B相邻，依此类推。
Path - 路径表示两个顶点之间的一系列边。 在以下示例中，ABCD表示从A到D的路径。
基本操作 (Basic Operations)
以下是图表的基本主要操作 -
Add Vertex - 向图形添加顶点。
Add Edge - 在图的两个顶点之间添加边。
Display Vertex - 显示图形的顶点。
要了解有关Graph的更多信息，请阅读Graph Theory Tutorial 。 我们将在接下来的章节中学习如何遍历图表。
Data Structure - Depth First Traversal
深度优先搜索（DFS）算法以向深运动的方式遍历图形，并使用堆栈记住在任何迭代中发生死角时获取下一个顶点以开始搜索。
如在上面给出的示例中，DFS算法首先从S到A到D到G到E到B，然后到F，最后到C.它使用以下规则。
Rule 1 - 访问相邻的未访问顶点。 将其标记为已访问。 显示它。 将其推入堆栈。
Rule 2 - 如果未找到相邻顶点，则从堆栈中弹出一个顶点。 （它将弹出堆栈中的所有顶点，这些顶点没有相邻的顶点。）
Rule 3 - 重复规则1和规则2，直到堆栈为空。
| 步 | 穿越 | 描述 |
|---|---|---|
| 1 |  | Initialize the stack. |
| 2 |  | 将S标记为已访问并将其放入堆栈。 从S探索任何未访问的相邻节点。 我们有三个节点，我们可以选择其中任何一个。 对于此示例，我们将按字母顺序获取节点。 |
| 3 |  | A标记为已访问并将其放入堆栈。 从A探索任何未访问的相邻节点S和D都与A相邻，但我们只关注未访问的节点。 |
| 4 |  | 访问D并将其标记为已访问并放入堆栈。 在这里，我们有B和C节点，它们与D相邻，两者都是未访问的。 但是，我们将再次按字母顺序选择。 |
| 5 |  | 我们选择B ，将其标记为已访问并放入堆栈。 这里B没有任何未访问的相邻节点。 所以，我们从堆栈弹出B |
| 6 |  | 我们检查堆栈顶部是否返回上一个节点并检查它是否有任何未访问的节点。 在这里，我们发现D位于堆栈的顶部。 |
| 7 |  | 现在只有未访问的相邻节点来自D是C 所以我们访问C ，将其标记为已访问并将其放入堆栈。 |
由于C没有任何未访问的相邻节点，因此我们不断弹出堆栈，直到找到具有未访问的相邻节点的节点。 在这种情况下，没有，我们会一直弹出，直到堆栈为空。
要了解这种算法在C编程语言中的实现， 请单击此处 。
Data Structure - Breadth First Traversal
广度优先搜索（BFS）算法以宽幅运动遍历图形并使用队列记住在任何迭代中发生死角时获取下一个顶点以开始搜索。
如在上面给出的示例中，BFS算法首先从A到B到E到F，然后到C和G，最后到D.它采用以下规则。
Rule 1 - 访问相邻的未访问顶点。 将其标记为已访问。 显示它。 将其插入队列中。
Rule 2 - 如果未找到相邻顶点，则从队列中删除第一个顶点。
Rule 3 - 重复规则1和规则2，直到队列为空。
| 步 | 穿越 | 描述 |
|---|---|---|
| 1 |  | Initialize the queue. |
| 2 |  | 我们从访问S （起始节点）开始，并将其标记为已访问。 |
| 3 |  | 然后我们从S看到一个未访问的相邻节点。 在这个例子中，我们有三个节点，但按字母顺序我们选择A ，将其标记为已访问并将其排入队列。 |
| 4 |  | 接下来，来自S的未访问的相邻节点是B 我们将其标记为已访问并将其排入队列。 |
| 5 |  | 接下来，来自S的未访问的相邻节点是C 我们将其标记为已访问并将其排入队列。 |
| 6 |  | 现在， S没有未访问的相邻节点。 所以，我们出列并找到A |
| 7 |  | 从A我们有D作为未访问的相邻节点。 我们将其标记为已访问并将其排入队列。 |
在这个阶段，我们没有未标记（未访问）的节点。 但是根据算法我们继续出列以获得所有未访问的节点。 当队列清空时，程序结束。
用C编程语言实现该算法可以在seen here 。
Data Structure and Algorithms - Tree
树表示由边连接的节点。 我们将具体讨论二叉树或二叉搜索树。
二叉树是用于数据存储目的的特殊数据结构。 二叉树具有特殊条件，即每个节点最多可以有两个子节点。 二叉树具有有序数组和链表的优点，因为搜索与排序数组一样快，插入或删除操作与链表一样快。
重要条款
以下是关于树的重要术语。
Path - 路径是指沿树边缘的节点序列。
Root - 树顶部的节点称为root。 每个树只有一个根，从根节点到任何节点只有一条路径。
Parent - 除根节点外的任何节点都有一条边向上到名为parent的节点。
Child - 由其边缘向下连接的给定节点下方的节点称为其子节点。
Leaf - 没有任何子节点的节点称为叶节点。
Subtree - 子树表示节点的后代。
Visiting - 访问是指在控制在节点上时检查节点的值。
Traversing - 遍历意味着以特定顺序遍历节点。
Levels - 节点级别表示节点的生成。 如果根节点处于级别0，则其下一个子节点处于级别1，其孙级处于级别2，依此类推。
keys - Key表示节点的值，基于该节点对节点执行搜索操作。
二进制搜索树表示
二叉搜索树表现出特殊的行为。 节点的左子节点必须具有小于其父节点值的值，并且节点的右子节点必须具有大于其父值的值。
我们将使用节点对象实现树并通过引用连接它们。
树节点
编写树节点的代码与下面给出的类似。 它有一个数据部分和对其左右子节点的引用。
struct node {
int data;
struct node *leftChild;
struct node *rightChild;
};
在树中，所有节点共享公共构造。
BST基本操作
可以在二叉搜索树数据结构上执行的基本操作如下 -
Insert - 在树中插入元素/创建树。
Search - 搜索树中的元素。
Preorder Traversal - 以Preorder Traversal树。
Inorder Traversal - 以有序方式遍历树。
Postorder Traversal - 以后序方式遍历树。
我们将在本章中学习创建（插入）树结构并在树中搜索数据项。 我们将在下一章中学习树遍历方法。
插入操作 (Insert Operation)
第一次插入创建了树。 之后，每当要插入元素时，首先找到其正确的位置。 从根节点开始搜索，然后如果数据小于键值，则在左子树中搜索空位置并插入数据。 否则，在右子树中搜索空位置并插入数据。
算法 (Algorithm)
If root is NULL
then create root node
return
If root exists then
compare the data with node.data
while until insertion position is located
If data is greater than node.data
goto right subtree
else
goto left subtree
endwhile
insert data
end If
实现 (Implementation)
insert函数的实现应如下所示 -
void insert(int data) {
struct node *tempNode = (struct node*) malloc(sizeof(struct node));
struct node *current;
struct node *parent;
tempNode->data = data;
tempNode->leftChild = NULL;
tempNode->rightChild = NULL;
//if tree is empty, create root node
if(root == NULL) {
root = tempNode;
} else {
current = root;
parent = NULL;
while(1) {
parent = current;
//go to left of the tree
if(data < parent->data) {
current = current->leftChild;
//insert to the left
if(current == NULL) {
parent->leftChild = tempNode;
return;
}
}
//go to right of the tree
else {
current = current->rightChild;
//insert to the right
if(current == NULL) {
parent->rightChild = tempNode;
return;
}
}
}
}
}
搜索操作 (Search Operation)
每当要搜索元素时，从根节点开始搜索，然后如果数据小于键值，则在左子树中搜索元素。 否则，搜索右子树中的元素。 对每个节点遵循相同的算法。
算法 (Algorithm)
If root.data is equal to search.data
return root
else
while data not found
If data is greater than node.data
goto right subtree
else
goto left subtree
If data found
return node
endwhile
return data not found
end if
此算法的实现应如下所示。
struct node* search(int data) {
struct node *current = root;
printf("Visiting elements: ");
while(current->data != data) {
if(current != NULL)
printf("%d ",current->data);
//go to left tree
if(current->data > data) {
current = current->leftChild;
}
//else go to right tree
else {
current = current->rightChild;
}
//not found
if(current == NULL) {
return NULL;
}
return current;
}
}
要了解二叉搜索树数据结构的实现，请单击此处 。
Data Structure & Algorithms - Tree Traversal
遍历是访问树的所有节点的过程，也可以打印它们的值。 因为所有节点都是通过边（链接）连接的，所以我们总是从根（头）节点开始。 也就是说，我们不能随机访问树中的节点。 我们使用三种方式遍历树 -
- 有序遍历
- Pre-order Traversal
- Post-order Traversal
通常，我们遍历树以搜索或定位树中的给定项或键或打印它包含的所有值。
In-order Traversal
在此遍历方法中，首先访问左子树，然后访问根，然后访问右子树。 我们应该永远记住，每个节点都可以代表一个子树。
如果按in-order遍历二叉树，则输出将按升序生成排序的键值。
我们从A开始，在按顺序遍历之后，我们移动到它的左子树B B也按顺序遍历。 该过程一直持续到访问所有节点。 这棵树的inorder遍历的输出将是 -
D → B → E → A → F → C → G
算法 (Algorithm)
Until all nodes are traversed −
<b class="notranslate">Step 1</b> − Recursively traverse left subtree.
<b class="notranslate">Step 2</b> − Visit root node.
<b class="notranslate">Step 3</b> − Recursively traverse right subtree.
Pre-order Traversal
在此遍历方法中，首先访问根节点，然后访问左子树，最后访问右子树。
我们从A开始，并且在预订遍历之后，我们首先访问A本身然后移动到其左边的子树B B也是预先遍历的。 该过程一直持续到访问所有节点。 此树的预订遍历的输出将是 -
A → B → D → E → C → F → G
算法 (Algorithm)
Until all nodes are traversed −
<b class="notranslate">Step 1</b> − Visit root node.
<b class="notranslate">Step 2</b> − Recursively traverse left subtree.
<b class="notranslate">Step 3</b> − Recursively traverse right subtree.
Post-order Traversal
在此遍历方法中，最后访问根节点，因此命名。 首先，我们遍历左子树，然后是右子树，最后是根节点。
我们从A开始， A跟踪后遍历之后，我们首先访问左子树B B也在下单后遍历。 该过程一直持续到访问所有节点。 此树的后序遍历输出将为 -
D → E → B → F → G → C → A
算法 (Algorithm)
Until all nodes are traversed −
<b class="notranslate">Step 1</b> − Recursively traverse left subtree.
<b class="notranslate">Step 2</b> − Recursively traverse right subtree.
<b class="notranslate">Step 3</b> − Visit root node.
要检查树遍历的C实现，请单击此处 。
Data Structure - Binary Search Tree
二进制搜索树（BST）是一个树，其中所有节点都遵循下面提到的属性 -
节点的左子树具有小于或等于其父节点密钥的密钥。
节点的右子树的密钥大于其父节点的密钥。
因此，BST将其所有子树划分为两个部分; 左子树和右子树可以定义为 -
left_subtree (keys) ≤ node (key) ≤ right_subtree (keys)
表示 Representation
BST是节点的集合，以维护BST属性的方式排列。 每个节点都有一个密钥和一个相关的值。 在搜索时，将所需的密钥与BST中的密钥进行比较，如果找到，则检索相关的值。
以下是BST的图示 -
我们观察到根节点密钥（27）在左子树上具有所有较低值的密钥，在右子树上具有较高值的密钥。
基本操作 (Basic Operations)
以下是树的基本操作 -
Search - 搜索树中的元素。
Insert - 在树中插入元素。
Pre-order Traversal - 以预订方式遍历树。
In-order Traversal - 以有序方式遍历树。
Post-order Traversal - 以后序方式遍历树。
Node
定义具有一些数据的节点，对其左右子节点的引用。
struct node {
int data;
struct node *leftChild;
struct node *rightChild;
};
搜索操作 (Search Operation)
每当要搜索元素时，从根节点开始搜索。 然后，如果数据小于键值，则在左子树中搜索元素。 否则，搜索右子树中的元素。 对每个节点遵循相同的算法。
算法 (Algorithm)
struct node* search(int data){
struct node *current = root;
printf("Visiting elements: ");
while(current->data != data){
if(current != NULL) {
printf("%d ",current->data);
//go to left tree
if(current->data > data){
current = current->leftChild;
} //else go to right tree
else {
current = current->rightChild;
}
//not found
if(current == NULL){
return NULL;
}
}
}
return current;
}
插入操作 (Insert Operation)
无论何时插入元素，首先要找到其正确的位置。 从根节点开始搜索，然后如果数据小于键值，则在左子树中搜索空位置并插入数据。 否则，在右子树中搜索空位置并插入数据。
算法 (Algorithm)
void insert(int data) {
struct node *tempNode = (struct node*) malloc(sizeof(struct node));
struct node *current;
struct node *parent;
tempNode->data = data;
tempNode->leftChild = NULL;
tempNode->rightChild = NULL;
//if tree is empty
if(root == NULL) {
root = tempNode;
} else {
current = root;
parent = NULL;
while(1) {
parent = current;
//go to left of the tree
if(data < parent->data) {
current = current->leftChild;
//insert to the left
if(current == NULL) {
parent->leftChild = tempNode;
return;
}
} //go to right of the tree
else {
current = current->rightChild;
//insert to the right
if(current == NULL) {
parent->rightChild = tempNode;
return;
}
}
}
}
}
Data Structure and Algorithms - AVL Trees
如果二叉搜索树的输入以排序（升序或降序）方式出现怎么办？ 它会看起来像这样 -
据观察，BST的最坏情况性能最接近线性搜索算法，即Ο（n）。 在实时数据中，我们无法预测数据模式及其频率。 因此，需要平衡现有的BST。
以他们的发明者Adelson ， Velski和Landis命名， AVL trees是高度平衡二元搜索树。 AVL树检查左侧和右侧子树的高度，并确保差异不大于1.这种差异称为Balance Factor 。
在这里，我们看到第一棵树是平衡的，接下来的两棵树是不平衡的 -
在第二个树中， C的左子树具有高度2，右子树具有高度0，因此差异为2.在第三个树中， A的右子树具有高度2而左侧缺失，因此它为0 ，差异又是2。 AVL树允许差异（平衡因子）仅为1。
<i><b class="notranslate">BalanceFactor</b></i> = height(left-sutree) − height(right-sutree)
如果左子树和右子树的高度差异大于1，则使用一些旋转技术来平衡树。
AVL轮换
为了平衡自身，AVL树可以执行以下四种旋转 -
- Left rotation
- 正确的旋转
- Left-Right rotation
- Left-Right rotation
前两个旋转是单旋转，接下来的两个旋转是双旋转。 要拥有一棵不平衡的树，我们至少需要一棵高度为2的树。通过这棵简单的树，让我们逐一理解它们。
左转
如果树变得不平衡，当一个节点插入到右子树的右子树中时，我们执行一个左旋转 -
在我们的示例中，节点A变得不平衡，因为节点插入到A右子树的右子树中。 我们通过使A为B的左子树来执行左旋转。
右转
如果节点插入左子树的左子树中，则AVL树可能变得不平衡。 然后树需要正确的旋转。
如图所示，通过执行右旋转，不平衡节点成为其左孩子的右孩子。
Left-Right Rotation
双旋转是已经解释的旋转版本的略微复杂版本。 为了更好地理解它们，我们应该注意旋转时执行的每个动作。 我们先来看看如何进行左右旋转。 左右旋转是左旋转然后右旋转的组合。
| 州 | 行动 |
|---|---|
 | 已将节点插入左子树的右子树中。 这使得C成为不平衡节点。 这些场景导致AVL树执行左右旋转。 |
 | 我们首先在C的左子树上执行左旋转。 这使得A成为B的左子树。 |
 | 节点C仍然是不平衡的，但是现在，这是因为左子树的左子树。 |
 | 我们现在将右旋转树，使B成为此子树的新根节点。 C现在成为其左子树的右子树。 |
 | 树现在平衡了。 |
Right-Left Rotation
第二种类型的双旋转是右 - 左旋转。 它是右旋转然后左旋转的组合。
| 州 | 行动 |
|---|---|
 | 已将节点插入右子树的左子树中。 这使得A是一个平衡因子为2的不平衡节点。 |
 | 首先，我们沿着C节点执行正确的旋转，使C成为其自己的左子树B的右子树。 现在， B成为A的正确子树。 |
 | 由于右子树的右子树并且需要左旋转，节点A仍然是不平衡的。 |
 | 通过使B成为子树的新根节点来执行左旋转。 A成为其右子树B的左子树。 |
| 树现在平衡了。 |
Data Structure & Algorithms - Spanning Tree
生成树是图G的子集，其具有覆盖有最小可能边数的所有顶点。 因此，生成树没有循环，也无法断开连接。
通过这个定义，我们可以得出结论，每个连通和无向图G都至少有一个生成树。 断开连接的图形没有任何生成树，因为它不能跨越所有顶点。
我们从一个完整的图表中找到了三棵生成树。 完整的无向图可以具有最大n n-2个生成树数，其中n是节点数。 在上面提到的示例中， n is 3,因此3 3−2 = 3生成树是可能的。
生成树的一般属性
我们现在知道一个图可以有多个生成树。 以下是连接到图G的生成树的一些属性 -
连接图G可以具有多个生成树。
图G的所有可能的生成树具有相同数量的边和顶点。
生成树没有任何循环（循环）。
从生成树中删除一条边将使图形断开连接，即生成树minimally connected 。
向生成树添加一条边将创建一个电路或循环，即生成树maximally acyclic 。
生成树的数学性质
生成树有n-1边，其中n是节点数（顶点）。
从完整的图表中，通过删除最大e - n + 1边，我们可以构建生成树。
完整的图形可以具有最多n n-2个生成树。
因此，我们可以得出结论，生成树是连接图G的子集，而断开连接的图没有生成树。
生成树的应用
生成树主要用于查找连接图中所有节点的最小路径。 生成树的常见应用是 -
Civil Network Planning
Computer Network Routing Protocol
Cluster Analysis
让我们通过一个小例子来理解这一点。 考虑一下，城市网络是一个巨大的图形，现在计划以这样的方式部署电话线，即在最小线路中我们可以连接到所有城市节点。 这是生成树进入图片的地方。
Minimum Spanning Tree (MST)
在加权图中，最小生成树是生成树，其权重最小于同一图的所有其他生成树。 在实际情况中，该权重可以被测量为距离，拥塞，交通负载或任何表示边缘的任意值。
最小生成树算法
我们将在这里学习两个最重要的生成树算法 -
两者都是贪婪的算法。
Heap Data Structures
堆是平衡二叉树数据结构的特例，其中根节点密钥与其子节点进行比较并相应地进行排列。 如果α有子节点β那么 -
键（α）≥键（β）
由于parent的值大于child的值，因此该属性会生成Max Heap 。 基于此标准，堆可以有两种类型 -
For Input → 35 33 42 10 14 19 27 44 26 31
Min-Heap - 根节点的值小于或等于其子节点的值。
Max-Heap - 根节点的值大于或等于其子节点的值。
两棵树都是使用相同的输入和到达顺序构建的。
最大堆构造算法
我们将使用相同的示例来演示如何创建Max Heap。 创建Min Heap的过程类似，但我们使用min值而不是max值。
我们将通过一次插入一个元素来导出最大堆的算法。 在任何时候，堆必须保持其属性。 在插入时，我们还假设我们在已经堆化的树中插入节点。
<b class="notranslate">Step 1</b> − Create a new node at the end of heap.
<b class="notranslate">Step 2</b> − Assign new value to the node.
<b class="notranslate">Step 3</b> − Compare the value of this child node with its parent.
<b class="notranslate">Step 4</b> − If value of parent is less than child, then swap them.
<b class="notranslate">Step 5</b> − Repeat step 3 & 4 until Heap property holds.
Note - 在Min Heap构造算法中，我们期望父节点的值小于子节点的值。
让我们通过动画插图了解Max Heap的构造。 我们考虑前面使用的相同输入样本。
最大堆删除算法
让我们推导出一种从最大堆中删除的算法。 Max（或Min）堆中的删除始终发生在根目录中以删除最大（或最小）值。
<b class="notranslate">Step 1</b> − Remove root node.
<b class="notranslate">Step 2</b> − Move the last element of last level to root.
<b class="notranslate">Step 3</b> − Compare the value of this child node with its parent.
<b class="notranslate">Step 4</b> − If value of parent is less than child, then swap them.
<b class="notranslate">Step 5</b> − Repeat step 3 & 4 until Heap property holds.
Data Structure - Recursion Basics
某些计算机编程语言允许模块或函数调用自身。 这种技术称为递归。 在递归中，函数α直接调用自身或调用函数β ，而函数β又调用原始函数α 。 函数α称为递归函数。
Example - 调用自身的函数。
int function(int value) {
if(value < 1)
return;
function(value - 1);
printf("%d ",value);
}
Example - 调用另一个函数的函数，该函数又调用它。
int function(int value) {
if(value < 1)
return;
function(value - 1);
printf("%d ",value);
}
属性 (Properties)/h2>
递归函数可以像循环一样无限。 为了避免递归函数的无限运行，递归函数必须具有两个属性 -
Base criteria - 必须至少有一个基本条件或条件，这样，当满足此条件时，函数将停止递归调用自身。
Progressive approach - 递归调用应该以这样一种方式进行，即每次进行递归调用时它都更接近基本条件。
实现 (Implementation)
许多编程语言通过stacks实现递归。 通常，每当函数（ caller ）将另一个函数（ callee ）或其自身调用为被调用者时，调用者函数就将执行控制转移给被调用者。 该传输过程还可能涉及一些要从呼叫者传递给被呼叫者的数据。
这意味着，调用函数必须暂时暂停其执行，并在执行控制从被调用函数返回时稍后恢复。 在这里，调用函数需要从执行点开始，它将自己置于保持状态。 它还需要与其正在处理的完全相同的数据值。 为此，为调用者函数创建激活记录（或堆栈帧）。
此激活记录保存有关局部变量，形式参数，返回地址和传递给调用函数的所有信息的信息。
递归分析
有人可能会争论为什么要使用递归，因为迭代可以完成相同的任务。 第一个原因是，递归使程序更具可读性，并且由于最新的增强型CPU系统，递归比迭代更有效。
时间复杂度 (Time Complexity)
在迭代的情况下，我们采用迭代次数来计算时间复杂度。 同样，在递归的情况下，假设一切都是常量，我们试图找出递归调用的次数。 对函数的调用是Ο（1），因此递归调用的（n）次数产生递归函数Ο（n）。
空间复杂性
空间复杂度计算为模块执行所需的额外空间量。 在迭代的情况下，编译器几乎不需要任何额外的空间。 编译器不断更新迭代中使用的变量值。 但是在递归的情况下，每次进行递归调用时系统都需要存储激活记录。 因此，认为递归函数的空间复杂度可能高于具有迭代的函数的空间复杂度。
Data Structure & Algorithms - Tower of Hanoi
河内塔，是一个数学难题，由三个塔（钉）和多个环组成，如图所示 -
这些环具有不同的尺寸并以升序堆叠，即较小的环位于较大的环上。 这个拼图还有其他变化，其中磁盘数量增加，但塔数仍然相同。
规则 (Rules)
任务是将所有磁盘移动到另一个塔而不违反排列顺序。 河内塔要遵循的一些规则是 -
- 在任何给定时间，只能在塔之间移动一个磁盘。
- 只能删除“顶部”磁盘。
- 没有大磁盘可以放在小磁盘上。
以下是用三个磁盘解决河内塔拼图的动画表示。
可以用最少2 n −1步骤解决具有n个盘的河内塔拼图。 此演示文稿显示具有3个磁盘的拼图已经采取2 3 - 1 = 7步。
算法 (Algorithm)
要为河内塔写一个算法，首先我们需要学习如何用较少量的磁盘来解决这个问题，比如→1或2.我们用标记， source ， destination和aux标记三个塔（仅用于帮助移动磁盘） ）。 如果我们只有一个磁盘，那么它可以很容易地从源移动到目标挂钩。
如果我们有2个磁盘 -
- 首先，我们将较小的（顶部）磁盘移动到辅助挂钩。
- 然后，我们将较大的（底部）磁盘移动到目标挂钩。
- 最后，我们将较小的磁盘从aux移动到目标peg。
所以现在，我们可以设计一个具有两个以上磁盘的Tower of Hanoi算法。 我们将磁盘堆分成两部分。 最大的磁盘（ 第 n 个磁盘）在一个部分中，所有其他（n-1个）磁盘在第二部分中。
我们的最终目标是将磁盘n从源移动到目标，然后将所有其他（n1）磁盘放到它上面。 我们可以设想以递归的方式对所有给定的磁盘组应用相同的方法。
要遵循的步骤是 -
<b class="notranslate">Step 1</b> − Move n-1 disks from <code><b class="notranslate">source</b></code> to <code><b class="notranslate">aux</b></code>
<b class="notranslate">Step 2</b> − Move n<sup>th</sup> disk from <code><b class="notranslate">source</b></code> to <code><b class="notranslate">dest</b></code>
<b class="notranslate">Step 3</b> − Move n-1 disks from <code><b class="notranslate">aux</b></code> to <code><b class="notranslate">dest</b></code>
River of Hanoi的递归算法可以如下驱动 -
START
Procedure Hanoi(disk, source, dest, aux)
IF disk == 1, THEN
move disk from source to dest
ELSE
Hanoi(disk - 1, source, aux, dest) // Step 1
move disk from source to dest // Step 2
Hanoi(disk - 1, aux, dest, source) // Step 3
END IF
END Procedure
STOP
要检查C编程中的实现， 请单击此处 。
Data Structure & Algorithms Fibonacci Series
Fibonacci系列通过添加两个先前的数字来生成后续数字。 Fibonacci系列从两个数字开始F 0 & F 1 。 F 0和F 1的初始值可分别取0,1或1,1。
斐波那契系列满足以下条件 -
F<sub>n</sub> = F<sub>n-1</sub> + F<sub>n-2</sub>
因此，Fibonacci系列看起来像这样 -
F 8 = 0 1 1 2 3 5 8 13
或者，这个 -
F 8 = 1 1 2 3 5 8 13 21
为了便于说明，F 8的斐波那契显示为 -
Fibonacci迭代算法
首先，我们尝试起草Fibonacci系列的迭代算法。
Procedure Fibonacci(n)
declare f<sub>0</sub>, f<sub>1</sub>, fib, loop
set f<sub>0</sub> to 0
set f<sub>1</sub> to 1
<b class="notranslate">display f<sub>0</sub>, f<sub>1</sub></b>
for loop ← 1 to n
fib ← f<sub>0</sub> + f<sub>1</sub>
f<sub>0</sub> ← f<sub>1</sub>
f<sub>1</sub> ← fib
<b class="notranslate">display fib</b>
end for
end procedure
要了解上述算法在C编程语言中的实现， 请单击此处 。
Fibonacci递归算法
让我们学习如何创建一个递归算法Fibonacci系列。 递归的基本标准。
START
Procedure Fibonacci(n)
declare f<sub>0</sub>, f<sub>1</sub>, fib, loop
set f<sub>0</sub> to 0
set f<sub>1</sub> to 1
<b class="notranslate">display f<sub>0</sub>, f<sub>1</sub></b>
for loop ← 1 to n
fib ← f<sub>0</sub> + f<sub>1</sub>
f<sub>0</sub> ← f<sub>1</sub>
f<sub>1</sub> ← fib
<b class="notranslate">display fib</b>
end for
END
要在c编程语言中查看上述算法的实现， 请单击此处 。
