概述

关于数据结构和算法部分,默认采用的语言是C++. 如果需要其他语言请联系作者.

数据结构

数据结构是以某种特定的布局方式存储数据的容器[^1]。这种“布局方式”决定了数据结构对于某些操作是高效的，而对于其他操作则是低效的。首先我们需要理解各种数据结构，才能在处理实际问题时选取最合适的数据结构。数据是计算机科学当中最关键的实体，而数据结构则可以将数据以某种组织形式存储，因此，数据结构的价值不言而喻。

数据需要根据不同的场景，按照特定的格式进行存储。有很多数据结构能够满足以不同格式存储数据的需求。

[^1]: 可以理解为字面意义上的容器, 也可以理解为C++的容器.

1. 数据: 是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合, 定义的数据类型。 2. 数据元素：数据的基本单位, 在计算机中通常作为整体处理。数据库中也被称为记录(行). 或者可以理解为实例化的一个对象. 3. 数据对象：性质相同的数据元素的集合，是数据的一个子集。 4. 数据项：一个数据元素可以由若干个数据项组成，数据项是不可分割的最小单位。 在数据库中是一个数据元素的某一个值. 或者可以理解为一个类对象的某个成员变量. 5. 数据结构：加上数据元素之间的关系的数据对象. 数据结构的三要素: 1. 逻辑结构：探讨数据元素之间的逻辑关系. 集合(各个元素同属于一个集合，别无其他关系)，表，树，图 2. 存储结构：探讨如何用计算机表示数据元素的逻辑关系. 顺序，链式，索引，散列(根据元素的关键字直接计算出该元素的存储地址，又称为哈希（Hash）存储) 顺序结构是指内存连续的存储单元进行存储，而链式结构是指 内存不连续的结构，通过一个节点指向另外一个节点的地址。 3. 对数据的运算或操作: 抽象数据类型ADT

基本操作

一般是增删查.

  1. 增: 增加元素. push(), enqueue(), insert() 等。
  2. 删: 删除元素. pop(), dequeue(), delete() 等.
  3. 查: 查找位置, 查找数据结构的一些信息. size(), search(int i)等
  4. 改: 改动数据结构中的某个值. set(), a[3] = 0;等.
计算机中一切数据都是由基本数据类型构成。是CPU可以直接进行运算的类型，在算法中直接使用。
  • 整型 int short long
  • 浮点型 float double
  • 字符 char
  • 布尔运算

char 类型的长度由编程语言采用的编码方法决定。例如，Java、JavaScript、TypeScript、C# 都采用 UTF-16 编码，因此 char 类型的长度为 2 字节。 在 Python 中，整数类型 int 可以是任意大小，只受限于可用内存；浮点数 float 是双精度 64 位；没有 char 类型，单个字符实际上是长度为 1 的字符串 str 。 C 和 C++ 未明确规定基本数据 类型的大小，而因实现和平台各异。 字符 char 的大小在 C 和 C++ 中为 1 字节，在大多数编程语言中取决于特定的字符编码方法。即使表示布尔量仅需 1 位（或），它在内存中通常也存储为 1 字节。这是因为现代计算机 CPU 通常将 1 字节作为最小寻址内存单元。

常见的数据结构

具有相同特性数据元素(同类型)的一组有限(有限性)序列(有先后次序，顺序性)，逻辑(只讨论元素间的逻辑关系,抽象性)特性：表头表尾唯一，中间的前驱后继唯一

  1. 有限性：元素个数有限

  2. 顺序性：有先后次序

  3. 同类型：数据元素类型相同，有先后次序

  4. 抽象性：只讨论元素间的逻辑关系

  5. 数组: 最简单、也是使用最广泛的数据结构。栈、队列等其他数据结构均由数组演变而来。每个数据元素都关联一个正数值，我们称之为索引，它表明数组中每个元素所在的位置。大部分语言将初始索引定义为零。

  6. 链表: 线性结构, 但与数组在内存分配, 内部结构和数据的基本操作方面都有不同.链表就像一个节点链，其中每个节点包含着数据和指向后续节点的指针。 链表还包含一个头指针，它指向链表的第一个元素，但当列表为空时，它指向null或无具体内容。链表一般用于实现文件系统、哈希表和邻接表。可分为单向链表和双向链表.

    1. 单向链表通常用于实现栈、队列、哈希表和图等数据结构。
    2. 双向链表常用于需要快速查找前一个和后一个元素的场景。
      1. 高级数据结构：比如在红黑树、B 树中，我们需要访问节点的父节点，这可以通过在节点中保存一个指向父节点的引用来实现，类似于双向链表。
      2. 浏览器历史：在网页浏览器中，当用户点击前进或后退按钮时，浏览器需要知道用户访问过的前一个和后一个网页。双向链表的特性使得这种操作变得简单。
      3. LRU 算法：在缓存淘汰（LRU）算法中，我们需要快速找到最近最少使用的数据，以及支持快速添加和删除节点。这时候使用双向链表就非常合适。
    3. 环形链表常用于需要周期性操作的场景，比如操作系统的资源调度。
      1. 时间片轮转调度算法：在操作系统中，时间片轮转调度算法是一种常见的 CPU 调度算法，它需要对一组进程进行循环。每个进程被赋予一个时间片，当时间片用完时，CPU 将切换到下一个进程。这种循环操作可以通过环形链表来实现。
      2. 数据缓冲区：在某些数据缓冲区的实现中，也可能会使用环形链表。比如在音频、视频播放器中，数据流可能会被分成多个缓冲块并放入一个环形链表，以便实现无缝播放。

  7. 栈: 后进先出当插入和删除操作都在链表的一端进行时,它表现出先进后出的特性

  8. 队列: 先进先出当插入操作在链表的一端进行，删除操作在链表的另一端进行，它表现出先进先出的特性

  9. 哈希表: 哈希法（Hashing）是一个用于唯一标识对象并将每个对象存储在一些预先计算的唯一索引（称为“键（key）”）中的过程。因此，对象以键值对的形式存储，这些键值对的集合被称为“字典”。可以使用键搜索每个对象。基于哈希法有很多不同的数据结构，但最常用的数据结构是哈希表。哈希表通常使用数组实现。链式地址是解决哈希冲突的主流方案之一，在该方案中，所有冲突的元素都会被放到一个链表中。

  10. 树形结构是一种层级式的数据结构，由顶点（节点）和连接它们的边组成。 树类似于图，但区分树和图的重要特征是树中不存在环路。树形结构被广泛应用于人工智能和复杂算法，它可以提供解决问题的有效存储机制。

  11. 图是一组以网络形式相互连接的节点。节点也称为顶点。 一对节点（x，y）称为边（edge），表示顶点x连接到顶点y。边可以包含权重/成本，显示从顶点x到y所需的成本。 邻接表是表示图的一种常用方式，其中图的每个顶点都与一个链表相关联，链表中的每个元素都代表与该顶点相连的其他顶点。

从逻辑结构上来看，数组必须实现定于固定的长度，不能适应数据动态增减的情况，即数组的大小一旦定义就不能改变。当数据增加是，可能超过原先定义的元素的个数；当数据减少时，造成内存浪费；链表动态进行存储分配，可以适应数据动态地增减的情况，且可以方便地插入、删除数据项。

从内存存储的角度看；数组从栈中分配空间（用new则在堆上创建），对程序员方便快速，但是自由度小；链表从堆中分配空间，自由度大但是申请管理比较麻烦。

从访问方式类看，数组在内存中是连续的存储，因此可以利用下标索引进行访问；链表是链式存储结构，在访问元素时候只能够通过线性方式由前到后顺序的访问，所以访问效率比数组要低。

算法

时间复杂度

一种衡量算法执行时间随输入规模增长而变化的度量方式。用于估计算法的执行时间，指明算法的运行时间如何随着输入的增加而增长。

1. 识别基本操作: 确定算法中执行操作最多的基本操作 2. 设置输入规模: 确定用于表示输入规模的变量： n数组长度，m矩阵行数 3. 构造操作次数函数: 简历关于输入规模的n的操作次数函数T(n) 4. 求解时间复杂度: 省略常数项,低阶项,系数.

常见的算法

算法 思想 应用
分治法 把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并 循环赛日程安排问题、排序算法（快速排序、归并排序）
动态规划 通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法，适用于有重叠子问题和最优子结构性质的问题.动态规划的核心问题是问题的状态的定义和状态转移方程的求解。关键在于，将重复出现的子问题在第一次求解之后就将其保存起来，以后再遇到时不用重复求解。是按照自底向上的方式计算最优解。（类似于数学归纳法）当题目求解的是最大值或最小值，可行与否或方案总数时，考虑使用动态规划问题。 背包问题、斐波那契数列
贪心法 一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法 旅行推销员问题（最短路径问题）、最小生成树、哈夫曼编码

:::tip 2016 东南大学 台阶总共有n级，青蛙每次可以跳1~n级，一共有几种跳法:

给定一个数组，编写一个算法，找出这个数组中最大的逆序差，分析时间复杂度。（逆序差就是i小于j的情况下，A[j]-A[i]的差，比如[4,15,5,6,9,1,16,11] 的最大逆序差是16 - 1 = 15

参考

  1. RSA加密算法
  2. Hello 算法
  3. ALGORITHM-TUTORIAL