数据结构与算法

作者 Brady joestar 日期 2017-07-04
数据结构与算法

数据结构与算法

写在前面

算法究竟有什么用？
算法的意义是什么？

算法的讨论主要涉及到性能，如何更快更好地计算出结果，转换数据，合理存储。很多时候不同数据结构和解决方法的选择，可能会造成数量级甚至指数级的差异。

针对某些特定的数据结构，以及在这之上运行的具体的操作手段。现实问题可以转化为特定的数据结构的问题+某些数学问题，基于此可以使用相应的运算规则进行运算。

data-structure

数据结构是一门研究非数值计算的程序设计问题中的操作对象，以及它们之间的关系和操作等相关问题的学科。

程序设计中有时候也会处理一些数学问题。

传统上，我们把数据结构分为逻辑结构和物理结构。

逻辑结构

  • 集合结构：集合结构中的数据元素同属于一个集合，他们之间是并列的关系，除此之外没有其他关系。

集合结构

  • 线性结构：线性结构中的元素存在一对一的相互关系。

线性结构

  • 树形结构：树形结构中的元素存在一对多的相互关系。

树形结构

  • 图形结构：图形结构中的元素存在多对多的相互关系。

图形结构

物理结构

物理结构指指数据的逻辑结构在计算机存储空间的存放形式。数据在内存中的存储结构，也就是物理结构，分为两种：顺序存储结构和链式存储结构。

  • 顺序存储结构：是把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。数组就是顺序存储结构的典型代表。其在内存中的存储形式类似于下图：

顺序存储结构

  • 链式存储结构：是把数据元素存放在内存中的任意存储单元里，也就是可以把数据存放在内存的各个位置。这些数据在内存中的地址可以是连续的，也可以是不连续的。

链式存储结构

algorithm

算法针对固定的数据结构。

通常而言，常用的数据结构有以下几种：

  • 数组
  • 链表。单链表，双链表，循环链表。
  • 栈
  • 队列
  • 二叉树。主要就是二叉树，其次是二叉查找树，二叉线索树。二叉查找树，二叉线索树比较偏，用的时候再说。
  • 图。邻接矩阵，邻接表，十字链表，邻接多重表。其中最常用的是邻接矩阵，邻接表其次常见，十字链表，邻接多重表听听就好。
    • 邻接矩阵：逻辑结构分为两部分：V和E集合。因此，用一个一维数组存放图中所有顶点数据；用一个二维数组存放顶点间关系（边或弧）的数据，
      二维数组是行到列的距离。aij，i到j。（这个不用记，伪代码想怎么写就怎么写。）

围绕上面的数据结构，衍生出相应的算法。下面的算法很多使用了递归。

  • 查找：主要针对数组、链表。有很多种查找方法，但是常用的就以下两种，且第一种居多。
    查找通常针对与已经排序号的序列，否则未排序的序列查找效率太低了。

    • 二分查找：二分查找的基本思想是将n个元素分成大致相等的两部分，取a[n/2]与x做比较，如果x=a[n/2],则找到x,算法中止；如果xa[n/2],则只要在数组a的右半部搜索x.
    • 二叉查找树查找

  • 排序：有以下几种常用的排序方法（可以快速编程实现的，无法快速编程实现的例如希尔排序、桶排序排除在外）：

    • 直接插入排序：将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增1的有序表。即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。
    • 简单选择排序：在要排序的一组数中，选出最小（或者最大）的一个数与第1个位置的数交换；然后在剩下的数当中再找最小（或者最大）的与第2个位置的数交换，依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。
    • 冒泡排序（交换排序）：在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒
    • 快速排序（交换排序）
      • 选择一个基准元素,通常选择第一个元素或者最后一个元素
      • 通过一趟排序讲待排序的记录分割成独立的两部分，其中一部分记录的元素值均比基准元素值小。另一部分记录的 元素值比基准值大。
      • 此时基准元素在其排好序后的正确位置
      • 然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。
    • 归并排序:归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

  • 出栈入栈，出队入队的各种操作。了解栈和队列的出入顺序，面对题随机应变就好。

  • 树的算法
    树的搜索有四种，主要分为前序、中序、后序和层次遍历，其中前序中序后序使用递归来进行非常简单，不使用递归的话可以使用栈来实现。

    • 前序遍历； 前序遍历按照“根结点-左孩子-右孩子”的顺序进行访问。
    • 中序遍历： 中序遍历按照“左孩子-根结点-右孩子”的顺序进行访问。
    • 后序遍历： 后序遍历按照“左孩子-右孩子-根结点”的顺序进行访问。
    • 层次遍历： 层次遍历需要借助与队列，按不同层次来逐一访问。

  • 图的算法

    • 深度优先:深度优先搜索（DFS），可以被形象的描述为“打破沙锅问到底”，具体一点就是访问一个顶点之后，我继而访问它的下一个邻接的顶点，如此往复，直到当前顶点一被访问或者它不存在邻接的顶点。
    • 广度优先:广度优先搜索（BFS），可以被形象的描述为“浅尝辄止”，具体一点就是每个顶点只访问它的邻接节点（如果它的邻接节点没有被访问）并且记录这个邻接节点，当访问完它的邻接节点之后就结束这个顶点的访问。
      广度优先用到了“先进先出”队列，通过这个队列来存储第一次发现的节点，以便下一次的处理；而对于再次发现的节点，我们不予理会——不放入队列
    • 拓扑排序:对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。
    • 关键路径：关键路径通常(但并非总是)是决定项目工期的进度活动序列。它是项目中最长的路径，即使很小浮动也可能直接影响整个项目的最早完成时间。
    • 从某个源点到其余各顶点的最短路径：迪杰斯特拉算法，不做过多阐述。

    • 每一对顶点的最短路径：knuth -carl算法，不做过多阐述。

      图论虽然说了六种算法，但是它们使用的频繁度是不同的。

      深度优先和广度优先均需要标记是否节点是否别访问。

  • 动态规划：动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

  • 贪心算法：贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行，根据某个优化测度，每一步都要确保能获得局部最优解。

动态规划和贪心算法掌握的多牛逼，做题中慢慢感受就行。

伪代码语法规则

伪代码是不标准的语言。我们可以将整个算法运行过程的结构用接近自然语言的形式（这里，你可以使用任何一种你熟悉的文字，中文，英文 等等，关键是你把你程序的意思表达出来）描述出来. 使用伪代码, 可以帮助我们更好的表述算法, 不用拘泥于具体的实现.

算法的伪代码描述形式上并不是非常严格，其主要特性和通常的规定如下：

  • 算法中出现的数组、变量可以是以下类型：整数、实数、字符、位串或指针。通常这些类型可以从算法的上下文来看是清楚的，并不需要额外加以说明。
  • 在算法中的某些指令或子任务可以用文字来叙述，例如，”设x是A中的最大项”，这里A是一个数组；或者”将x插入L中”，这里L是一个链表。这样做的目的是为了避免因那些与主要问题无关的细节使算法本身杂乱无章。
  • 算术表达式可以使用通常的算术运算符（+，-，*，/，以及表示幂的^）。逻辑表达式可以使用关系运算符=,≠,<,>,≤和≥，以及逻辑运算符与(and),或（or），非（not）。

每个人都有自己的伪代码写法，多年之后只会记得伪代码怎么写。形成自己的伪代码风格，想怎么写就怎么写。

除非要编译，否则看算法题首先考虑怎么用伪代码实现。

过程：思路 —》 伪代码 –》 代码，可以按照这个过程来进行编程。

思路主要分为两个部分：

  • 数据结构的设计
  • 基于特定数据结构的运算过程

思路 3分钟 ，伪代码五分钟， 代码剩下时间。
每次刷题按照这个节奏来。

java的输入输出

当通过new Scanner(System.in)创建一个Scanner，控制台会一直等待输入，直到敲回车键结束，把所输入的内容传给Scanner，作为扫描对象。如果要获取输入的内容，则只需要调用Scanner的nextLine()方法即可。
scanner讲解好文

SampleInput

1 2
3 4
5 6

SampleOutput

3
7
11

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNext()) {
        	int a = in.nextInt();
        	int b = in.nextInt();
        	System.out.println(a + b);
        }
    }
}

java 的scanner是非常简便的输出方式：

Scanner scanner = new Scanner(System.in);
       while(scanner.hasNext()){
           int a = scanner.nextInt();
           int b = scanner.nextInt();
           int c = scanner.nextInt();
           String d = scanner.next();
           System.out.println(a+b+c);
           System.out.println(d);
       }

下面是针对不同换行输入输出的情况：

1 2 3
wenbin
6
wenbin
1 2
3
wenbin
6
wenbin
1
2
3
jojo
6
jojo

刷题常用套路

刷题过程中记录的套路，动态更新中。

套路一

套路二

套路三

套路四

套路五

套路六

套路七

套路…

ps：图片来源参考自:鱼C工作室。感谢鱼C工作室贡献出了这么好的图片。

FEATURED TAGS