【数据结构与算法基础概念】

课程目标

如果你想让自己的编程能力有质的飞跃，不再停留于调用现成的API，而是追求更完美的实现，那么这门课程就是你的必修课，因为程序设计=数据结构+算法。

通过对基础数据结构和算法的学习，能更深层次的理解程序，提升编写代码的能力，让程序的代码更优雅，性能更高。

课程内容

1. 数据结构和算法概述
2. 算法分析
3. 排序
4. 线性表
5. 符号表
6. 树
7. 堆
8. 优先队列
9. 并查集
10. 图

一、数据结构与算法概述

1.1 什么是数据结构

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

大白话：数据结构就是把数据元素按照一定的关系组织起来的集合，用来组织和储存数据。

1.2 数据结构分类

传统上，我们可以把数据结构分为逻辑结构和物理结构两大类。

逻辑结构的分类

逻辑结构是从具体问题中抽象出的模型，是抽象意义上的结构，按照对象中数据元素之间的关系分类。

1. 集合结构：集合中的元素除了属于同一个集合外，没有其他联系。
2. 线性结构：线性结构中的元素之间存在一对一的关系。
3. 树形结构：树形结构中的元素存在一对多的层次关系。
4. 图形关系：图形结构的数据元素是多对多的关系。

物理结构的分类

逻辑结构在计算机中真正的表示方式（映像），称为物理结构，也可以叫做存储结构。常见的存储结构有顺序储存结构、链式存储结构。

1.3什么是算法

官方解释：算法是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。

大白话：根据一定的条件，对一些数据进行计算，得到需要的结果。

1.4算法初体验

在程序中我们可以用不同的算法解决相同的问题，而不同的算法成本也不同。总体上，一个优秀的算法追求以下两个目标：

1. 花最少的时间完成需求；
2. 占有最少的内存空间完成需求；

例1：计算1~100的和：

解法1：累加

解法2：使用等差数列公式

例2：计算n的阶乘：

解法1：递归调用

解法2：从1×到n

二、 算法分析

2.1 算法的时间复杂的分析

事后分析估算方法：不建议，通常需要花费大量的时间和精力，测试完了如果发现是非常糟糕的算法，那么之前所做的事情就白费了。

事前分析估算方法：主要取决于以下几个要素：

1. 算法采用的策略和方案；
2. 编异产生的代码质量；
3. 问题的输入规模；
4. 机器执行指令的速度。

抛开计算机硬件，软件的因素，一个程序运行时间依赖于算法的好坏和问题的输入规模。

2.1.1 函数渐进增长

1. 算法函数中的常数可以忽略；
2. 算法函数中的最高次幂的常数因子可以忽略；
3. 算法函数中的最该次幂越小，算法效率越高。

2.1.2 算法的时间复杂度

2.1.2.1 大O记法

在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随着n的变化情况并确定T(n)的量级。算法的时间复杂度，就是算法的时间量度，记作:T(n)=O(f(n))。它表示随着问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称时间复杂度，其中f(n)是问题规模n的某个函数。

推导大O阶的表示法有以下几个规则：

1. 用常数1取代运行时间中的所有加法常数；
2. 在修改后的运行次数中，只保留高阶项；
3. 如果最高阶项存在，且常数因子不为1，则去除与这个项相乘的常数；

2.1.2.2 常见的O阶

1. 线性阶 一个for

2. 平方阶 二个for

3. 立方阶 三个for

4. 对数阶 ：随着输入规模n的增大，不管底数为多少，他们的增长趋势是一样的，所以我们会忽略底数。

   int i=1,n=100;
   while(i<n){
       i=i*2;
   }//2^x=n;则x=log(2)n
   

5. 常数阶
   

2.1.2.3 函数调用的时间复杂度分析

2.1.2.4 最坏情况

最坏情况是一种保证，在应用中，这是一种最基本的保障，即使在最坏情况下，也能够正常提供服务，所以，除非特别指定，我们提到的运行时间都指的是最坏情况下的运行时间。

2.2算法中的空间复杂度分析

2.2.1java中常见的内存占用

1. 基本数据类型内存占用情况：

2. 计算机访问内存的方式都是一次一个字节（8位）
3. 一个引用（机器地址）需要8个字节来表示
4. 创建一个对象，比如new Date(),除了Date对象内部存储的数据占用内存，该对象本身也有内存开销，每个对象自身开销是16个字节，用来保存对象的头信息。
5. 一般内存的使用，如果不够8个字节，都会被自动填充为8字节。
6. java中数组被限定为对象，他们一般会因为记录长度二需要额外的内存，一个原始数据类型数组一般需要24字节的头信息（16个自己对象的开销，4字节用于保存长度以及4个填充字节）再加上保存值所需要的内存。

2.2.2 算法的空间复杂度

了解了java的内存最基本的机制，就能够有效地帮助我们估计大量程序的内存使用情况。

例如：对指定的数组进行反转

解法1：使用temp变量

解法2：使用temp[]数组

三、 排序

3.1简单排序

3.1.1Comparable接口介绍

//定义比较规则
@Override
public int compareTo(Student o){
return this.getAge()-o.getAge();
}

3.1.2冒泡排序

排序原理：

1. 比较相邻的元素，如果一个元素比另一个元素大，就交换这两个元素的位置。
2. 对每一对相邻元素做同样的工作，从第一对元素开始到结尾的最后一对元素。最终最后位置的元素就是最大值。

public static void sort(int[] a){
    for(int i=a.length-1;i>0;i++){
        for(int j=0;j<i;j++){
            if(a[j]>a[j+1]){
                int temp=0;
                temp=a[j+1];
                a[j+1]=a[j];
                a[j]temp;
            }
        }
        
    }
}

3.1.3选择排序

排序原理：

1. 每一次遍历的过程中，都假定第一个索引处的元素是最小值，和其他索引处的值依次进行比较，如果当前索引处的值大于其他某个索引处的值，则假定其他某个索引出的值为最小值，最后可以找到最小值所在的索引
2. 交换第一个索引处和最小值所在的索引处的值

public static void sort(int[] a){
    for(int i=0;i<=a.length-1;i++){
        int minIndex=i;
        for(int j=i+1;j<a.length;j++){
            if(a[minIndex]>a[j]){
                minIndex=j;
            }
        }
        int temp=a[i];
        a[i]=a[minIndex];
        a[minIndex]=a[i];   
    }
}

3.1.4插入排序

排序原理：

1. 把所有的元素分为两组，已经排序的和未排序的；
2. 找到未排序的组中的第一个元素，向已经排序的组中进行插入；
3. 倒叙遍历已经排序的元素，依次和待插入的元素进行比较，直到找到一个元素小于等于待插入元素，那么就把待插入元素放到这个位置，其他的元素向后移动一位；

public static void sort(int[] a){
    for(int i=1;i<a.length;i++){
        for(int j=i;j>0;j--){
          if(a[j-1]>a[j]){
              int temp=a[j-1];
              a[j-1]=a[j];
              a[j]=temp;
          }else{
            break;
          }  
        }
    }
}

3.2高级排序

3.2.1希尔排序

排序原理：

1. 选定一个增长量h，按照增长量h作为数据分组的依据，对数据进行分组；
2. 对分好组的每一组数据完成插入排序；
3. 减小增长量，最小减为1，重复第二步操作。

增量h的确定：

int h=1;
while(h<5){
    h=2h+1;//3,7
}
//循环结束后我们就可以确定h的最大值
//h的减小规则为：
h=h/2;

public static void sort(int[] a){
    int N=a.length;
    int h=1;
    while(h<N/2){
        h=h*2+1;
    }
    while(h>=1){
        for(int i=h;i<N;i++){
            for(int j=i;j>=h;j-=h){
                if(a[j-h]>a[j]){
                    int temp=a[j-h];
                    a[j-h]=a[j];
                    a[j]=a[j-h];
                }else{
                    break;
                }
            }
        }
        h/=2;
    }
}

3.2.2归并排序

排序原理：

1. 尽可能的一组数据拆分成两个元素相等的子组，并对每一个子组继续拆分，直到拆分后的每个子组的元素个数是1为止。
2. 将相邻的两个子组进行合并成一个有序的大组；
3. 不断的重复步骤2，直到最终只有一个组为止。

public static void sort(int[] a,int left,int right){
    if(left>=right){
        return;
    }
    //中间索引
    int center=(left+right)/2;
    sort(a,left,center);
    sort(a,center+1,right);
    merge(a,left,center,right);
}
public static void merge(int[] a,int left,int center,int right){
    int[] tepArr=new int[data.length];
    int mid=center+1;
    int third=left;
    int tmp=left;
    while(left<=center&&mid<=right){
        if(a[left]<=a[mid]){
            tmpArr[third++]=a[left++];
        }else{
            tmpArr[third++]=a[mid++];
        }
    }
    while(mid<=right){
        tmpArr[third++]=a[mid++];
    }
    while(left<=center){
        tmpArr[third++]=a[left++];
    }
    //将临时数组中的内容拷贝回原数组
    while(tmp<=right){
        a[tmp]=tmpArr[tmp++];
    }
}

3.2.3快速排序

排序原理：

1. 首先设定一个分界值，通过该分界值将数组分成左右两部分；
2. 将大于或等于分界值的数据放到到数组右边，小于分界值的数据放到数组的左边。此时左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值；
3. 然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
4. 重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左侧和右侧两个部分的数据排完序后，整个数组的排序也就完成了。

public static void quickSort(int[] arr,int low,int high){
    int i,j,temp,t;
    if(low>high){
        return;
    }
    i=low;
    j=high;
    while(i<j){
        while(temp<=arr[j]&&i<j){
            j--;
        }
        while(temp>=arr[i]&&i<j){
            i++;
        }
        if(i<j){
            t=arr[j];
            arr[j]=arr[i];
            arr[i]=t;
        }
    }
    //将基准为与i和j相等位置的数字交换
    temp=arr[low];
    arr[low]=arr[i];
    arr[i]=temp;
    //递归调用左半数组
    quickSort(arr,low,j-1);
    //递归调用右半数组
    quickSort(arr,j+1,high);
}

3.2.4排序的稳定性

稳定性的定义：数组arr中有若干元素，其中A元素和B元素相等，并且A元素在B元素前面，如果使用某种排序算法排序后，能够保证A元素依然在B元素的前面，可以说这个该算法是稳定的。

稳定性的意义：如果一组数据只需要一次排序，则稳定性一般是没有意义的，如果一组数据需要多次排序，稳定性是有意义的。例如要排序的内容是一组商品对象，第一次排序按照价格由低到高排序，第二次排序按照销量由高到低排序，如果第二次排序使用稳定性算法，就可以使得相同销量的对象依旧保持着价格高低的顺序展现，只有销量不同的对象才需要重新排序。这样既可以保持第一次排序的原有意义，而且可以减少系统开销。

常见排序算法的稳定性：

稳定：冒泡排序，插入排序，归并排序

不稳定：选择排序，希尔排序，快速排序

四、线性表

线性表的特征：数据元素之间具有一种“一对一”的逻辑关系。

1. 第一个数据元素没有前驱，这个数据元素被称为头结点；
2. 最后一个数据元素没有后继，这个数据元素被称为尾结点；
3. 除了第一个和最后一个数据元素外，其他数据元素有且仅有一个前驱和一个后继。

线性表的分类：

线性表中数据存储的方式可以是顺序存储，也可以是链式存储，按照数据的存储方式不同，可以把线性表分为顺序表和链表。

4.1 顺序表

顺序表是在计算机内存中以数组的形式保存的线性表，线性表的顺序存储是指用一组地址连续的存储单元，依次存储线性表中的各个元素、使得线性表中再逻辑结构上响铃的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。

例如：java中的ArrayList实现

java中ArrayList集合的底层也是一种顺序表，使用数组实现，同样提供了增删改查以及扩容等功能。

1. 是否用数组实现；
2. 有没有扩容操作；
3. 有没有提供遍历方式；

4.2 链表

链表是一种物理存储单元上非连续、非顺序的存储结构，其物理结构不能只管的表示数据元素的逻辑顺序，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列的结点（链表中的每一个元素称为结点）组成，结点可以在运行时动态生成。

例如：java中的LinkedList实现

java中LinkedList集合也是使用双向链表实现，并提供了增删改查等相关方法

1. 底层是否用双向链表实现；
2. 结点类是否有三个域

相关问题：链表反转；中间值问题；判断链表是否有环；有环链表入口问题；约瑟夫问题

4.3栈

栈是一种基于先进后出(FILO)的数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。

我们称数据进入到栈的动作为压栈，数据从栈中出去的动作为弹栈。

相关问题：括号匹配问题；逆波兰表达式求值问题

4.4队列

队列是一种基于先进先出(FIFO)的数据结构，是一种只能在一端进行插入,在另一端进行删除操作的特殊线性表，它按照先进先出的原则存储数据，先进入的数据，在读取数据时先读被读出来。

五、符号表

符号表最主要的目的就是将一个键和一个值联系起来，符号表能够将存储的数据元素是一个键和一个值共同组成的键值对数据，我们可以根据键来查找对应的值。

六、二叉树入门

符号表的增删查操作，随着元素个数N的增多，其耗时也是线性增多的，时间复杂度都是O(n),为了提高运算效率，接下来我们学习树这种数据结构。

6.1树的基本定义

树是由n（n>=1）个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

树具有以下特点：

1. 每个结点有零个或多个子结点；
2. 没有父结点的结点为根结点；
3. 每一个非根结点只有一个父结点；
4. 每个结点及其后代结点整体上可以看做是一棵树，称为当前结点的父结点的一个子树。

6.2树的相关术语

结点的度：一个结点含有紫薯的个数；

叶结点：度为0的结点称为叶节点，也可以叫做终端结点

分支结点：度不为0的结点，也可以叫非终端结点

结点的层次：从根结点开始，根结点对的层次为1，根的直接后继层次为2，以此类推

结点的层次编号：将树中的结点，按照从上层到下层，从左到右的层序排成一个线性序列，把他们编成连续的自然数。

树的度：树中所有结点度的最大值

树的高度（深度）：树中结点的最大层次

森林：m(m>=0)个互不相交的树的集合，将一颗非空树的根结点点删去，树就变成了一个森林；给森林增加一个统一的根结点，森林就变成一棵树。

孩子结点：一个结点的直接后继

双亲结点（父结点）：一个结点的直接前驱

兄弟结点：同一双亲结点的孩子结点间互称兄弟结点

6.3二叉树的基本定义

二叉树就是度不超过2的树(每个结点最多有两个子结点)

满二叉树：一个二叉树，每一个层的结点都达到最大值

完全二叉树：叶节点只能出现在下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树

相关问题：层序遍历；前序遍历；后序遍历；中序遍历；二叉树的最大深度问题；折纸问题

七、堆

7.1堆的定义

堆是数据结构中一类特殊数据结构的统称，堆通常可以被看做是一颗完全二叉树的数组对象。

堆的特性：

1. 它是完全二叉树
2. 通常用数组实现；按层序顺序放入数组中；根节点在位置1，它的子结点在位置2,3……如果一个结点的位置为k，则它的父结点的位置为[k/2],而它的两个子结点的位置则分别为2k和2k+1。这样，在不使用指针的情况下，我们也可以通过计算数组的索引在树中上下移动：从a[k]向上一层，就令k等于k/2,向下一层就令k等于2k或2k+1。
3. 每个结点都大于等于它的两个子结点；这里要注意堆中仅仅规定了每个结点大于等于它的两个子结点，但这两个子结点的顺序并没有做规定，跟我们之前学习的二叉查找树是有区别的。

7.2堆排序实现步骤

实现步骤：

1. 构造堆；
2. 得到堆顶元素，这个值就是最大值；
3. 交换堆顶元素和数组中的最后一个元素，此时所有元素中的最大元素已经放到合适的位置；
4. 对堆进行调整，重新让除了最后一个元素的剩余元素中的最大值放到堆顶；
5. 重复2~4这个步骤，直到堆中剩一个元素为止。

八、优先队列

优先队列按照其作用不同，可以分为以下两种：

8.1最大优先队列

可以获取并删除队列中最大的值；基于大根堆实现

8.2最小优先队列

可以获取并删除队列中最小的值；基于小根堆来实现

8.3索引优先队列实现

在之前实现的最大优先队列和最小优先队列，他们可以分别快速访问到队列中最大元素和最小元素，但是他们有一个缺点，就是没有办法通过索引访问已存在于优先队列中的对象，并更新它们。为了实现这个目的，在优先队列的基础上，学习一种新的数据结构，索引优先队列。接下来我们以最小索引优先队列举列。

九、树的进阶—平衡树

之前我们学习过二叉查找树，发现它的查询效率比单纯的链表和数组的查询效率要高很多，大部分情况下，确实是这样的，但不幸的是，在最坏情况下，二叉查找树的性能还是很糟糕。

生如果成的树都像完全二叉树那样，那么即使在最坏情况下，查找的效率依旧会很好。

9.1 2-3查找树

为了保证查找树的平衡性，我们需要一些灵活性，因此在这里我们允许树中的一个结点保存多个键。确切的说，我们将一棵标准的二叉查找树中的结点称为2-结点(含有一个键和两条链)，而现在我们引入3-结点，它含有两个键和三条链。2-结点和3-结点中的每条链都对应着其中保存的键所分割产生的一个区间。

9.1.1 2-3查找树的定义

一棵2-3查找树要么为空，要么满足满足下面两个要求：

2-结点：含有一个键(及其对应的值)和两条链，左链接指向2-3树中的键都小于该结点，右链接指向的2-3树中的键都大于该结点。

3-结点：含有两个键(及其对应的值)和三条链，左链接指向的2-3树中的键都小于该结点，中链接指向的2-3树中的键都位于该结点的两个键之间，右链接指向的2-3树中的键都大于该结点。

9.1.2 2-3树的性质

1. 任意空链接到根结点的路径长度都是相等的
2. 4-结点变换成3结点时，树的高度不会发生变化，只有当根结点是临时的4-结点，分解根结点时，树高+1.
3. 2-3树与普通二叉查找树最大区别在于，普通的二叉查找树是自顶向下生长，而2-3树是自底向上生长。

9.2 红黑树

我们前面介绍了2-3树，可以看到2-3树能保证在插入元素之后，树依然保持平衡状态，它的最坏情况下所有子结点都是2-结点，树的高度为lgN,相比于我们普通的二叉查找树，最坏情况下树的高度为N，确实保证了最坏情况下的时间复杂度，但是2-3树实现起来过于复杂，所以我们介绍一种2-3树思想的简单实现：红黑树。

红黑树主要是对2-3树进行编码，红黑树背后的基本思想是用标准的二叉查找树(完全由2-结点构成)和一些额外的信息(替换3-结点)来表示2-3树。我们将树中的链接分为两种类型：

红链接：将两个2-结点连接起来构成一个3-结点；黑链接：则是2-3树中的普通链接。

确切的说，我们将3-结点表示为由由一条左斜的红色链接(两个2-结点其中之一是另一个的左子结点)相连的两个2-结点。这种表示法的一个优点是，我们无需修改就可以直接使用标准的二叉查找树的get方法。

9.2.1 红黑树的定义

红黑树是含有红黑链接并满足下列条件的二叉查找树：

1. 红链接均为左链接；
2. 没有任何一个结点同时和两条红链接相连；
3. 该树是完美黑色平衡的，即任意链接到根结点的黑链接数量相同。

9.2.2平衡化

在对红黑树进行一些增删改查的操作后，很有可能会出现红色的右链接或者两条连续红色的链接，而这些都不满足红黑树的定义，所以我们需要对这些情况通过旋转进行修复，让红黑树保持平衡。

9.2.2.1左旋

当某个结点的左子结点为黑色，右子结点为红色，此时需要左旋。

前提：当前结点为h，它的右子结点为x；

左旋过程：

1. 让x的左子结点变为h的右子结点：h.right=x.left;
2. 让h成为x的左子结点：x.left=h;
3. 让h的color属性变为x的color属性值：x.color=h.color;
4. 让h的color属性变为RED：h.color=true;

9.2.2.2右旋

当某个结点的左子结点是红色，且左子结点的左子结点也是红色，需要右旋

前提：当前结点为h，它的左子结点为x；

右旋过程：

1. 让x的右子结点成为h的左子结点：h.left = x.right;
2. 让h成为x的右子结点：x.right=h;
3. 让x的color变为h的color属性值：x.color = h.color;
4. 让h的color为RED；

9.2.2.3颜色反转

当一个结点的左子结点和右子结点的color都为RED时，也就是出现了临时的4-结点，此时只需要把左子结点和右子结点的颜色变为BLACK，同时让当前结点的颜色变为RED即可。

9.2.2.4根结点的颜色总是黑的

由于根结点不存在父节点，所以每次插入操作后，我们都需要把根结点的颜色设置为黑色。

9.3 B-树

前面我们已经学习了二叉查找树、2-3树以及它的实现红黑树。2-3树中，一个结点做多能有两个key，它的实现红黑树中使用对链接染色的方式去表达这两个key。接下来我们学习另外一种树型结构B树，这种数据结构中，一个结点允许多于两个key的存在。

B树是一种树状数据结构，它能够存储数据、对其进行排序并允许以O(logn)的时间复杂度进行查找、顺序读取、插入和删除等操作。

9.3.1 B树的特征

B树中允许一个结点中包含多个key，可以是3个、4个、5个甚至更多，并不确定，需要看具体的实现。现在我们选择一个参数M，来构造一个B树，我们可以把它称作是M阶的B树，那么该树会具有如下特点：

1. 每个结点最多有M-1个key，并且以升序排列；
2. 每个结点最多能有M个子结点；
3. 根结点至少有两个子结点；

在实际应用中B树的阶数一般都比较大（通常大于100），所以，即使存储大量的数据，B树的高度仍然比较小，这样在某些应用场景下，就可以体现出它的优势。

9.3.2 B树在磁盘文件中的应用

在我们的程序中，不可避免的需要通过IO操作文件，而我们的文件是存储在磁盘上的。计算机操作磁盘上的文件是通过文件系统进行操作的，在文件系统中就使用到了B树这种数据结构。

文件系统的设计者利用了磁盘预读原理，将一个结点的大小设为等于一个页（1024个字节或其整数倍），这样每个结点只需要一次I/O就可以完全载入。那么3层的B树可以容纳102410241024差不多10亿个数据，如果换成二叉查找树，则需要30层！假定操作系统一次读取一个节点，并且根节点保留在内存中，那么B树在10亿个数据中查找目标值，只需要小于3次硬盘读取就可以找到目标值，但红黑树需要小于30次，因此B树大大提高了IO的操作效率。

9.4 B+树

B+树是对B树的一种变形树，它与B树的差异在于：

1. 非叶节点仅具有索引作用，也就是说，非叶子结点只储存key,不存储value。
2. 树的所有叶节点构成一个有序链表，可以按照key排序的次序遍历全部数据。

9.4.1 B+树和B树的对比

B+树的优点在于：

1. 由于B+树在非叶子结点上不包含真正的数据，只当做索引使用，因此在内存相同的情况下，能够存放更多的key。
2. B+树的叶子结点都