培训笔记6

数据结构&算法基础

数据结构与算法的由来及其意义

为什么要学习数据结构与算法?

随着应用程序变得越来越复杂和数据越来越丰富，几百万、几十亿甚至几百亿的数据就会出现，而对这么大对数据进行搜索、插入或者排序等的操作就越来越慢，数据结构就是用来解决这些问题的。

从数组到链表

比较项	数组	链表
逻辑结构	（1）数组在内存中连续； (2)使用数组之前，必须事先固定数组长度，不支持动态改变数组大小；(3) 数组元素增加时，有可能会数组越界；(4) 数组元素减少时，会造成内存浪费；（5）数组增删时需要移动其它元素	（1）链表采用动态内存分配的方式，在内存中不连续 (2)支持动态增加或者删除元素 (3)需要时可以使用malloc或者new来申请内存，不用时使用free或者delete来释放内存
内存结构	数组从栈上分配内存，使用方便，但是自由度小	链表从堆上分配内存，自由度大，但是要注意内存泄漏
访问效率	数组在内存中顺序存储，可通过下标访问，访问效率高	链表访问效率低，如果想要访问某个元素，需要从头遍历
越界问题	数组的大小是固定的，所以存在访问越界的风险	只要可以申请得到链表空间，链表就无越界风险

链表

链表是一种由一组顶点（节点）组成的数据结构，这些顶点共同表示一个序列。在最简单的形式下，每个顶点由一个数据和一个引用（链接）组成，该引用指向序列中的下一个顶点。

struct Node
{
  int a,b;
  char c;
  Node *next=NULL;
};

• 链表中的元素可存储在内存的任何地方
• 链表的每个元素都存储了下一个元素的地址，从而使一系列随机的内存地址串在一起。

树

定义

上图这些元素具有的就是 “一对多” 的逻辑关系, 观察这些元素之间的逻辑关系会发现，它们整体上很像一棵倒着的树，这也是将存储它们的结构起名为“树”（或者 “树形”）的原因。

存储具有 “一对多” 逻辑关系的数据，数据结构推荐使用树存储结构。

概念

1.考虑结点K。根A到结点K的唯一路径上的任意结点,称为结点K的祖先。如结点B是结点K的祖先,而结点K是结点B的子孙。路径上最接近结点K的结点E称为K的双亲,而K为结点E的孩子。根A是树中唯一没有双亲的结点。有相同双亲的结点称为兄弟,如结点K和结点L有相同的双亲E,即K和L为兄弟。
2.树中一个结点的孩子个数称为该结点的度,树中结点的最大度数称为树的度。如结点B的度为2,结点D的度为3,树的度为3。
3.度大于0的结点称为分支结点(又称非终端结点);度为0(没有子女结点)的结点称为叶子结点(又称终端结点)。在分支结点中,每个结点的分支数就是该结点的度。
4.结点的深度、高度和层次:

• 结点的层次从树根开始定义,根结点为第1层,它的子结点为第2层,以此类推。双亲在同一层的结点互为堂兄弟,图中结点G与E,F,H,I,J互为堂兄弟。

• 结点的深度是从根结点开始自顶向下逐层累加的。

• 结点的高度是从叶结点开始自底向上逐层累加的。

• 树的高度(或深度)是树中结点的最大层数。图中树的高度为4。

5.有序树和无序树。树中结点的各子树从左到右是有次序的,不能互换,称该树为有序树,否则称为无序树。假设图为有序树,若将子结点位置互换,则变成一棵不同的树。
6.路径和路径长度。树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的,而路径长度是路径上所经过的边的个数。
注意:由于树中的分支是有向的,即从双亲指向孩子,所以树中的路径是从上向下的,同一双亲的两个孩子之间不存在路径。
7.森林。森林是m (m≥0)棵互不相交的树的集合。森林的概念与树的概念十分相近，因为只要把树的根结点删去就成了森林。反之，只要给m棵独立的树加上一个结点，并把这m棵树作为该结点的子树，则森林就变成了树。

二叉树

概念

简单地理解，满足以下两个条件的树就是二叉树：

1. 本身是有序树；

2. 树中包含的各个节点的度不能超过 2，即只能是 0、1 或者 2；

性质

经过前人的总结，二叉树具有以下几个性质：

1. 二叉树中，第 i 层最多有 2^(i-1) 个结点。
2. 如果二叉树的深度为 K，那么此二叉树最多有 (2^K)-1 个结点。
3. 二叉树中，终端结点数（叶子结点数）为 n0，度为 2 的结点数为 n2，则 n0=n2+1。

二叉树还可以继续分类，衍生出满二叉树和完全二叉树。

满二叉树

如果二叉树中除了叶子结点，每个结点的度都为 2，则此二叉树称为满二叉树。
满二叉树除了满足普通二叉树的性质，还具有以下性质：

1. 满二叉树中第 i 层的节点数为 2^(i-1) 个。
2. 深度为 k 的满二叉树必有 (2^k)-1 个节点 ，叶子数为 2^(k-1)。
3. 满二叉树中不存在度为 1 的节点，每一个分支点中都两棵深度相同的子树，且叶子节点都在最底层。
   4 具有 n 个节点的满二叉树的深度为 log2(n+1)。

完全二叉树

如果二叉树中除去最后一层节点为满二叉树，且最后一层的结点依次从左到右分布，则此二叉树被称为完全二叉树。
如图a所示是一棵完全二叉树，图b由于最后一层的节点没有按照从左向右分布，因此只能算作是普通的二叉树。
完全二叉树除了具有普通二叉树的性质，它自身也具有一些独特的性质，比如说，n 个结点的完全二叉树的深度为 log2n+1。

对于任意一个完全二叉树来说，如果将含有的结点按照层次从左到右依次标号（如图a)，对于任意一个结点 i ，完全二叉树还有以下几个结论成立：

1. 当 i>1 时，父亲结点为结点 [i/2] 。（i=1 时，表示的是根结点，无父亲结点）
2. 如果 2i>n（总结点的个数） ，则结点 i 肯定没有左孩子（为叶子结点）；否则其左孩子是结点 2i 。
3. 如果 2i+1>n ，则结点 i 肯定没有右孩子；否则右孩子是结点 2i+1 。

二叉树的遍历

分为先序遍历，中序遍历，后序遍历

二叉树的遍历( traversing binary tree )是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。

先序遍历

先序遍历(PreOrder) 的操作过程如下：
若二叉树为空，则什么也不做，否则，

1. 访问根结点;
2. 先序遍历左子树;
3. 先序遍历右子树。

void PreOrder(BiTree T){
 if(T != NULL){
  visit(T); //访问根节点
  PreOrder(T->lchild); //递归遍历左子树
  PreOrder(T->rchild); //递归遍历右子树
 }
}

中序遍历

中序遍历( InOrder)的操作过程如下：
若二叉树为空，则什么也不做，否则，

1. 中序遍历左子树;
2. 访问根结点;
3. 中序遍历右子树。

void InOrder(BiTree T){
 if(T != NULL){
  InOrder(T->lchild); //递归遍历左子树
  visit(T); //访问根结点
  InOrder(T->rchild); //递归遍历右子树
 }
}

后序遍历

后序遍历(PostOrder) 的操作过程如下：
若二叉树为空，则什么也不做，否则，

1. 后序遍历左子树;
2. 后序遍历右子树;
3. 访问根结点。

哈希表，Hash

哈希表，也可以称为散列表或者 Hash 表，拥有数组支持按照下标随机访问数据的特性，所以哈希表其实就是数组的一种扩展，由数组演化而来。可以说，如果没有数组，就没有散列表。

哈希表存储的是由键（key）和值（value）组成的数据，通过散列函数将键key映射到对应的value上，其存储方式称之为散列技术。
散列技术是指在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使每一个关键字都对应一个存储位置。即：存储位置=f（关键字）。这样，在查找的过程中，只需要通过这个对应关系f 找到给定值key的映射f（key）。只要集合中存在关键字和key相等的记录，则必在存储位置f（key）处。我们把这种对应关系f 称为散列函数或哈希函数。

队列&应用

和链表相比，队列的特殊性体现在以下两个方面：

1. 元素只能从队列的一端进入，从另一端出去
2. 队列中各个元素的进出必须遵循“先进先出”的原则，即最先入队的元素必须最先出队。

通常，我们将元素进入队列的一端称为“队尾”，进入队列的过程称为“入队”；将元素从队列中出去的一端称为“队头”，出队列的过程称为“出队”。

应用

队列在操作系统中应用的十分广泛，比如用它解决 CPU 资源的竞争问题。

对于一台计算机来说，CPU 通常只有 1 个，是非常重要的资源。如果在很短的时间内，有多个程序向操作系统申请使用 CPU，就会出现竞争 CPU 资源的现象。不同的操作系统，解决这一问题的方法是不一样的，有一种方法就用到了队列这种存储结构。

假设在某段时间里，有 A、B、C 三个程序向操作系统申请 CPU 资源，操作系统会根据它们的申请次序，将它们排成一个队列。根据“先进先出”原则，最先进队列的程序出队列，并获得 CPU 的使用权。待该程序执行完或者使用 CPU 一段时间后，操作系统会将 CPU 资源分配给下一个出队的程序，以此类推。如果该程序在获得 CPU 资源的时间段内没有执行完，则只能重新入队，等待操作系统再次将 CPU 资源分配给它。

队列的相关操作

queue<type> q; //定义队列，type为数据类型，例如int，float，char等
q.empty();  //判断队列是否为空
q.size();   //返回队列长度
q.push(item);   //对于queue，在队尾压入一个新元素
q.pop();   //对于queue，删除队首元素
q.front();  //返回队首元素的值，但不删除该元素
q.back();   //返回队尾元素的值，但不删除该元素

广度优先搜索(Breadth-First Search,BFS)

广度优先搜索（BFS,或称为宽度优先搜索）是基本的暴力技术，常用于解决图，树的遍历问题
在具体编程时，一般用队列这种数据结构来具体实现BFS，甚至可以说“BFS=队列”

BFS 为什么需要队列？
对于 BFS 算法，正如上面所说的，我们需要一层一层遍历所有的相邻结点。那么相邻结点之间的先后顺序如何确定？因此我们需要一个数据结构来进行存储和操作，需要使得先遍历的结点先被存储，直到当前层都被存储后，按照先后顺序，先被存储的结点也会被先取出来，继续遍历它的相邻结点。
因此我们可以发现，First In First Out (FIFO) 完全契合这里的使用情况。因此对于 BFS 我们需要使用 Queue 这样的一个数据结构，来存储每一层的结点，同时维护『先进先出 FIFO』的顺序。

BFS 算法过程
BFS 的实现过程也非常直接，主要由 3 部分组成：

• 起始：将起点（源点，树的根节点）放入队列中
• 扩散：从队列中取出队头的结点，将它的相邻结点放入队列，不断重复这一步
• 终止：当队列为空时，说明我们遍历了所有的结点，整个图都被搜索了一遍

优先队列（priority_quque）

优先队列也是一种队列，只不过不同的是，优先队列的出队顺序是按照优先级来的；在有些情况下，可能需要找到元素集合中的最小或者最大元素，可以利用优先队列来完成操作.

优先队列和队列的区别在于，对于优先队列，元素进入队列的顺序可能与其被操作的顺序不同，作业调度是优先队列的一个应用实例，它根据优先级的高低而不是先到先服务的方式来进行调度。

堆（Heap）

堆的概念：
数据结构二叉堆能够很好地实现优先队列的基本操作。在二叉堆的数组中，每个元素都要保证
大于等于另两个特定位置的元素。相应地，这些位置的元素又至少要大于等于数组中的另两个元素，
以此类推。如果我们将所有元素画成一棵二叉树，将每个较大元素和两个较小的元素用边连接就可以很容易看出这种结构。

定义:
当一棵二叉树的每个结点都大于等于它的两个子结点时，它被称为堆有序。
相应地，在堆有序的二叉树中，每个结点都小于等于它的父结点（如果有的话）。从任意结点向上，我们都能得到一列非递减的元素；从任意结点向下，我们都能得到一列非递增的元素

（简单起见，在下文中我们将二叉堆简称为堆）
在一个堆中，位置 k 的结点的父结点的位置为 k/2 ，而它的两个子结点的位置则分别为 2k 和 2k+1。这样在不使用指针的情况下我们也可以通过计算数组的索引在树中上下移动：从 a[k] 向上一层
就令 k 等于 k/2，向下一层则令 k 等于 2k 或 2k+1。
用数组（堆）实现的完全二叉树的结构是很严格的，但它的灵活性已经足以让我们高效地实现优
先队列。

堆的算法

我们用长度为 N+1 的数组 a[] 来表示一个大小为 N 的堆，我们不会使用 a[0]， 堆 元 素 放 在 a[1] 至
a[N] 中。在排序算法中，我们只通过辅助函数 less() 和 exch() 来访问元素，堆的操作会首先进行一些简单的改动，打破堆的状态，然后再遍历堆并按照要求将堆的状态恢复。我们称这个过程叫做堆的有序化（reheapifying）。

堆实现的比较和交换方法如下方的代码所示

bool less(int i, int j)
{
  return a[i] < a[j];
}
void exch(int i, int j)
{
  int t = a[i];
  a[i] = a[j];
  a[j] = t;
}

由下至上的堆有序化（上浮）

如果堆的有序状态因为某个结点变得比它的父结点更大而被打破，那么我们就需要通过交换它和它的父结点来修复堆。交换后，这个结点比它的两个子结点都大（一个是曾经的父结点，另一个比它更小，因为它是曾经父结点的子结点），但这个结点仍然可能比它现在的父结点更大。我们可以一遍遍地用同样的办法恢复秩序，将这个结点不断向上移动直到我们遇到了一个更大的父结点。只要记住位置 k 的结点的父结点的位置是 k/2，这个过程实现起来很简单。swim() 方法中的循环可以保证只有位置 k 上的结点大于它的父结点时堆的有序状态才会被打破。因此只要该结点不再大于它的父结点，堆的有序状态就恢复了。至于方法名，当一个结点太大的时候它需要浮（swim）到堆的更高层。

void swim(int k)
{
  while(k > 1 && less(k/2, k))
  {
    exch(k/2, k);
    k = k/2;
  }
}

由上至下的堆有序化（下沉）

如果堆的有序状态因为某个结点变得比它的两个子结点或是其中之一更小了而被打破了，那么我们可以通过将它和它的两个子结点中的较大者交换来恢复堆。交换可能会在子结点处继续打破堆的有序状态，因此我们需要不断地用相同的方式将其修复，将结点向下移动直到它的子结点都比它更小或是到达了堆的底部。由位置为 k 的结点的子结点位于 2k 和 2k+1 可以直接得到对应的代码。
至于方法名，由上至下的堆有序化的实现代码见下方的代码框。当一个结点太小的时候它需要沉（sink）到堆的更低层。

void sink(int k)
{
  while(2*k <= N)
  {
    int j = 2*k;
    if(j < N && less(j, j+1)) j++;
    if(!less(k,j)) break;
    exch(k, j);
    k = j;
  }
}

堆排序

这段代码用 sink() 方法将 a[1] 到a[N] 的元素排序（sink() 被修改过，以a[] 和 N 作为参数）。for 循环构造了堆，然后 while 循环将最大的元素 a[1] 和a[N] 交换并修复了堆，如此重复直到堆变空。将 exch() 和 less() 的实现中的索引减一即可得到和其他排序算法一致的实现（将 a[0] 至 a[N-1] 排序）。

void Heap_sort(int *a,int *N)
{
  for(int k = N/2; k >= 1; k++) sink(a, k, N);
  while(N > 1)
  {
    exch(a, 1, N--);
    sink(a, 1, N);
  }
}

栈&应用

对于逻辑关系为“一对一”的数据，除了用顺序表和链表存储外，还可以用栈结构存储。

栈是一种“特殊”的线性存储结构，它的特殊之处体现在以下两个地方：
1、元素进栈和出栈的操作只能从一端完成，另一端是封闭的，如下图所示：

通常，我们将元素进栈的过程简称为“入栈”、“进栈”或者“压栈”；将元素出栈的过程简称为“出栈”或者“弹栈”。

2、栈中无论存数据还是取数据，都必须遵循“先进后出”的原则，即最先入栈的元素最先出栈。以图 1 的栈为例，很容易可以看出是元素 1 最先入栈，然后依次是元素 2、3、4 入栈。在此基础上，如果想取出元素 1，根据“先进后出”的原则，必须先依次将元素 4、3、2 出栈，最后才能轮到元素 1 出栈。

我们习惯将栈的开口端称为栈顶，封口端称为栈底。例如在图 1 中，元素 4 一侧为栈顶，元素 1 一侧为栈底，如图 2 所示。

由此我们可以对栈存储结构下一个定义：栈一种“只能从一端存取元素，且存取过程必须遵循‘先进后出’原则”的线性存储结构。

栈的实际应用

1. 实现浏览器的“回退”功能
   所谓浏览器的“回退”功能，比如您用浏览器打开 A 页面，然后从 A 页面跳转到 B 页面，然后再从 B 页面跳转到 C 页面。这种情况下，如果想回到 A 页面，有两种方法：
   重新搜索找到 A 页面；
   借助浏览器的“回退”功能，先从 C 页面回退到 B 页面，再从 B 页面回退到 A 页面。
   很多浏览器的“回退”功能就位于工具栏中，图标是一个类似←的箭头。

浏览器的“回退”功能底层就是用栈存储结构实现的，当从 A 页面跳转到 B 页面时，浏览器会执行入栈操作，A 页面信息会存入栈中；同样，从 B 页面跳转到 C 页面时，B 页面信息会存入栈中。当点击浏览器的“回退”按钮时，浏览器会执行“出栈”操作，根据“先进后出”的原则，B 页面先出栈，然后 A 页面出栈，这样就实现了“回退”的功能。

2. 实现 C 语言函数的相互调用
   C语言程序中，函数间的相互调用过程也是用栈存储结构实现的。

栈的相关操作

stack<type> s; 定义栈，type为数据类型，例如int，float，char等
s.push(item); 把item放到栈顶
s.top() 返回栈顶的元素但不删除
s.pop() 删除栈顶的元素但不返回
s.empty()判断栈是否为空，若为空返回true否则返回false
s.size()返回栈中元素个数

Dijkstra双栈算术表达式

( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) )

算术表达式可能是一个数，或者是由一个左括号、一个算术表达式、一个运算符、另一个
算术表达式和一个右括号组成的表达式。简单起见，这里定义的是未省略括号的算术表达式，它明
确地说明了所有运算符的操作数

如何用程序计算如上低级算术表达式的值？

( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) )
( 1 + ( 5 * ( 4 * 5 ) ) )
( 1 + ( 5 * 20 ) )
( 1 + 100 )
101

深度优先搜索(Depth-First Search,DFS)

深度优先搜索（Depth First Search），是图的一种搜索方式，以深度为优先级去进行搜索，用一句话概括就是：“一直往下走，走不通回头，换条路再走，直到无路可走”。具体算法描述为：
选择一个起始点 u 作为当前结点，执行如下操作：
a. 访问 当前结点，并且标记该结点已被访问，然后跳转到 b；
b. 如果存在一个和 当前结点 相邻并且尚未被访问的结点 v ，则将 v 设为当前结点，继续执行 a；
c. 如果不存在这样的 v ，则进行回溯，回溯的过程就是回退 当前结点；
上述所说的 当前结点 需要用一个栈来维护，每次访问到的结点入栈，回溯的时候出栈。除了栈，另一种实现深度优先搜索的方式是递归，代码更加简单，相对好理解。

我们刚才讲到树的遍历的思想其实就是DFS