写给大家看的算法书

2018-09-29

什么是算法

所谓算法指的是对特定问题的解决步骤。特定问题一般有对信息进行排序，搜索目标信息等。

算法有两个必要条件

  1. 准确性
  2. 可停止性

算法的准确性除了说对相应的问题，得出正确的结果之外，在多了某些特别的边界输入值也保持一致。证明算法准确性的其中一个方法是，对于算法中的任意一个步骤，输入当前步骤满足条件的值，看看是否能得到当前步骤产生的准确的结果，以此细分并判定。这种方法叫断言（Assertion）。

而可停止性意味着算法必须是最终可停止的，即保证无论什么样的输入，也一定可以在有限时间内正确地停止。

几个重要的算法

  1. 专用于数论计算的算法
  • 求解最大公约数的辗转相除法
  • 求解联立方程的高斯消元法
  • 求解定积分近似值的梯形公式
  • 计算质数的爱拉托斯特尼筛法
  1. 对一组乱序的数据进行升序或者降序排序的算法（sort）
  • 选择排序
  • 冒泡排序
  • 插入排序
  • 希尔排序
  • 归并排序
  • 快速排序
  1. 在大量数据中找出目标数据的搜索算法（search）
  • 线性搜索（linear search）
  • 二分搜索（binary search）
  1. 在一个字符串中找到符合特定模式的子串（子字符串）的匹配算法
  • 简单字符串搜索
  • KMP 算法
  • BM 算法

结构性化编程思想

结构发编程思想是一种旨在高效描述程序、最大限度减少设计误差的方法论，一般用以下三种结构的组合来表示：

  1. 顺序结构：以记述的顺序依次进行处理
  2. 选择结构：根据条件的不同改变处理进程
  3. 循环结构：在条件成立的情况下，进行一定量的重复处理

注：面向过程的程序，也基本是由这三种构造的组合来编写的。

数据结构

数组

把同类数据紧密排列就得到“数组”。数据排成一条直线的数组叫 一维数组，数据像长方形一样纵横排列的数组叫二维数组，数据像长方体一样排列的数组叫三维数组。

  • 保存到数组里面的所有数据都必须是同类型的数据。
  • 优势：能快速定位第 N 个数据

环形缓冲区

环形缓冲区，即让一维数组首尾相连，指定末尾元素的下一个元素是起始元素，便能得到末尾元素的后面还存在元素。有点类似时钟，十二点之后，又回到一点。

堆栈

把数据用堆叠的方式来管理的数据结构就是堆栈。

堆栈管理数据的两种操作：

  • 写入数据（堆积）称为入栈（Push）
  • 读取数据称为出栈（POP）

像堆栈这样，最后写入的数据被最先读取的数据管理方式称作 LIFO（Last In, First Out），或者 FILO（First In, Last Out）

队列

即像排队一样，从最先的数据开始按顺序处理数据的数据结构，称为队列。

像队列一样，具有最先输入的数据最先输出的特征的数据管理方式，被称为 FIFO（First In，First Out）或者 LILO（Last In，Last Out）

链表

链表通过像结绳一样的方式按顺序或者逆序管理前后的关联的数据。其中的各个元素的位置可以自由排列，无论数据的存储位置如何变更，链表也可以正确管理各个数据的顺序。

单向链表

在链表里，用一根有方向的绳子把数据连接起来的链表叫单向链表。在单项链表中，每个元素都有以下信息：

  • 数据（可以是整数值、实数值、字符串等等）
  • 指向下一项元素的指针（即 NEXT 指针，表示下一个元素保存在哪里）

单向链表的最后一个元素的 NEXT 指针标示终止信息，表示的是“没有下一个元素”；而指向第一个元素的指针称作 HEAD 指针。每一个单向链表都是由 HEAD 指针指示的元素开始。

注：如果一个单向链表中一个数据都没有的话，那么它的 HEAD 指针指示的就是“没有第一个元素”。

双向链表

在链表里，用向前和向后两根有方向的绳子来把数据连接起来的链表叫双向链表。双向链表中，每个元素有以下信息：

  • 数据
  • 指向下一项元素的指（NEXT 指针）
  • 指向上一项元素的指针（PREV 指针）

NEXT 指针保存的是下一个元素的位置信息，PREV 指针保存的是上一个元素的位置信息。而末尾元素的 NEXT 指针及起始元素的 PREV 指针都分别表示“没有下一个元素”这样的终止信息。

单向链表只能从前到后检索数据，而双向链表可以从前到后也可以从后到前检索数据。

注：当双向链表里一个元素都没有的时候，HEAD 指针和 TAIL 指针分别保存“没有起始元素”和“没有末尾元素”。

链表更适合需要进行插入、删除操作，主要是用户访问读取的话，则用数组更适合。

树

树是一种管理有像树干、树枝、树叶一样关系的数据的数据结构。

树由 节点（顶边）和边（枝）构成，并且由一个节点作为起始点。这个起始点称为树的根节点。

  • **父节点：**旧的节点
  • **子节点：**通过边延伸出来的新节点
  • **叶子节点：**一个子节点都没有的节点
  • **深度：**由根节点触发，到达某一个节点所要经过的边的个数

二叉树

在树形结构中，如果每个父节点只有两个子节点，那么这样的树被称为二叉树（Binary tree）。其中，一个父节点的两个子节点分别叫做 左子节点 和 右子节点。另，也可以存在叶子节点或只有一个子节点的情况，限制在于每一个节点不能拥有超过两个子节点。

二叉树可以看作是每一个元素都拥有两个 指向下一个元素的指针 的单向链表。通常用于表示父节点存储的数据大小关系，也用于表示二项式运算的式子。另外，搜索算法为了提高效率，也常常利用这种数据结构。

注：二叉树还可以用数组来表示。

图

关注两个以上的数据项目之间是如何关联在一起，并且通过图形一样的方式把这种关联表现出来，称为 图。而用图来表现的项目被称作 节点，表示节点之间关系的线则被称为 边。

  • **有向图：**由节点和有方向组成的图
  • **加权图：**一个图的每条边都拥有权重

算法

排序算法

  • 桶排序
    • 准备与待排序数据取值范围大小个数的木桶，利用这些木桶对数据进行保存、排序。
    • 适合用于数据取值范围较小的场合
  • 选择排序
    • 遍历数据，把数据中的最大值（或最小值）与起始（或者末尾）数据进行交换。
  • 交换排序（冒泡排序）
    • 对比相邻的两个数据，根据大小关系调整两个数据的顺序。
  • 插入排序
    • 把目标数据按照正常的大小排列顺序插入相应的位置中。
  • 归并排序
    • 把目标数据分隔成更小的部分进行排序，更小的部分正确排序之后再合并起来。
  • 希尔排序
    • 把目标数据按照一定的个数分成几个区域进行插入排序
  • 快速排序
    • 从目标数据中任意选取一个数据，以这个数据的值为分割点，把目标数据分隔为两部分。这样循环操作。

搜索算法

  • 线性搜索
    • 从头开始按顺序排除的搜索，虽然慢，但简单
    • 随着数据量的增大，效率成反比
  • 二分搜索
    • 适合在已排序的数据列中所搜
  • 利用哈希表进行搜索
    • 利用数据结构
  • 简单字符串搜索
    • 字符串搜索一个重要特征便是 待搜索的目标字符串是数组
  • 利用 KMP 算法进行字符串搜索
    • 可以根据子字符串及搜索时字符串出现不匹配的位置，决定下一次开始比较字符的位置，从而优化搜索效率
    • KMP 来源三位作者的首字母
  • 利用 BM 算法进行字符串搜索
    • BM 算法是根据字符串的末尾字符开始向前做字符比较，并根据字符串信息和失配位置来确定跳过字符串比较的位置，从而优化搜索效率。
    • 名字同样来源于两位作者的首字母
# 算法
# 编程