1.内容介绍

1. 数据结构与算法概述（了解）
2. 常见的数据结构;（掌握）
3. 常见的算法;(了解)

2.数据结构与算法概述

2.1.为什么需要学习数据结构与算法

1）让我们写的代码更高效执行
2）面试中需要问到

2.2.数据结构概念理解

数据结构就是用来装数据以及数据与之间关系的一种集合。如何把相关联的数据存储到计算机，为后续的分析提供有效的数据源，是数据结构产生的由来。数据结构就是计算机存储、组织数据的方式。好的数据结构，让我们做起事来事半功倍。精心选择的数据结构可以带来更高的计算速度和存储效率。

数据结构是用来存储数据，而这些数据有特定关系。

2.2.1.逻辑结构

数据与数据之间的联系被称为数据的逻辑结构 ，根据关系的紧密程度，逻辑结构被分为四种

1.集合
数据结构中的元素之间除了“同属一个集合” 的相互关系外，别无其他关系。打个比方，我有一个篮子，篮子里面放了一个苹果，一个香蕉，一个梨子。这三种水果除了放在一个篮子里面，他们没有其它联系。这篮子里三种水果就属于一个集合，他们老死不相往来。

2.线性结构
数据结构中的元素存在一对一的相互关系；打个比方，我要高考了，但是我数学不好，所以我请了一个数学老师给我单独补课，并且规定在我补课期间，该数学老师不能跟其他人补课，那么我和这个数学老师就是一对一的关系，我们之间的关系就是他跟我补课。还比如排队，每列只站一个人，每列总共十个人，那么他们每个人之间有先后关系，但是都是一对一的先后关系。

3.树形结构
数据结构中的元素存在一对多的相互关系；比如，一个数学老师给两个或者多个学生补课，那么老师和学生之间就是一对多的关系。

4.图形结构
数据结构中的元素存在多对多的相互关系。
比如我们的交通网，长沙有n条高速公路到达上海，同时上海也有k条高速公路到达长沙，长沙到上海是一对三n的关系，上海到长沙也是一对k的关系，所以长沙和上海是多对多的关系。

2.2.2.物理结构

数据的逻辑结构在计算机存储空间的存放形式被称为数据的物理结构。
1.顺序存储结构
把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素,称作线性表的顺序存储结构。

特点：
1、随机存取表中元素。
2、插入和删除操作需要移动元素。

2.链接存储结构
在计算机中用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的)。它不要求逻辑上相邻的元素在物理位置上也相邻.因此它没有顺序存储结构所具有的弱点,但也同时失去了顺序表可随机存取的优点。

特点：
1、比顺序存储结构的存储密度小 (每个节点都由数据域和指针域组成，所以相同空间内假设全存满的话顺序比链式存储更多)。
2、逻辑上相邻的节点物理上不必相邻。
3、插入、删除灵活 (不必移动节点，只要改变节点中的指针)。
4、查找结点时链式存储要比顺序存储慢。
5、每个结点是由数据域和指针域组成。

3.数据索引存储结构
除建立存储结点信息外，还建立附加的索引表来标识结点的地址。索引表由若干索引项组成，如果每个节点在索引表中都有一个索引项，则该索引表就被称为稠密索引。若一组节点在索引表中只对应于一个索引项，则该索引表就成为稀疏索引。索引项的一般形式一般是关键字、地址。在搜索引擎中，需要按某些关键字的值来查找记录，为此可以按关键字建立索引，这种索引就叫做倒排索引(因为是根据关键词来找链接地址，而不是通过某个链接搜索关键词，这里反过来了，所以称为倒排索引)，带有倒排索引的文件就叫做倒排索引文件，又称为倒排文件。倒排文件可以实现快速检索，这种索引存储方法是目前搜索引擎最常用的存储方法。

存储单词的过程：先在某个地址空间存储单词，然后把该单词的关键词和存储地址存到附加的索引表。

查找某个单词的过程：先根据关键词找索引表，得到数据存储地址。然后再通过存储地址得到数据。

特点：

索引存储结构是用结点的索引号来确定结点存储地址，其优点是检索速度快，缺点是增加了附加的索引表,会占用较多的存储空间。

4.数据散列存储结构 hash

散列存储，又称hash存储，是一种力图将数据元素的存储位置与关键字之间建立确定对应关系的查找技术。比如将汤高这个名字通过一个函数转换成为一个值，这个值就是姓名汤高在计算机中的存储地址，这个函数称为hash函数。hash函数有很多种，今天先不谈。以后再细讲。 T_user_id%100

散列法存储的基本思想是：它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表

特点：

散列是数组存储方式的一种发展，相比数组，散列的数据访问速度要高于数组。要依据数据的某一部分来查找数据时数组一般要从头遍历数组才能确定想要查找的数据位置，而散列是通过函数通过“想要查找的数据”作为“输入”、“数据的位置”作为“输出”来实现快速访问，因此时间复杂度可以认为为O(1)，而数组遍历的时间复杂度为O(n)。

逻辑结构是面向问题的，而物理结构就是面向计算机的，其基本的目标就是将数据及其逻辑关系存储到计算机的内存中。

2.3.算法概述

2.3.1.算法概念

算法是解决问题步骤的有限集合，通常用某一种计算机语言进行伪码描述。 就是java中一个方法

• 算法的五大特征：输入、输出、有穷性、确定性、可行性。
  输入：零个或多个输入。
  输出：一个或多个输出。
  有穷性：有限步骤后在可接受时间内完成。
  确定性：每个步骤都有确定含义，无二义性。
  可行性：每一步都是可行的。
• 算法设计要求：正确性、可读性、健壮性、时间效率高和存储低。
  正确性：有输入输出，无二义性，有正确答案。
  可读性：方便阅读。
  健壮性：输入不合法能处理
  时间效率高和存储低：时间空间复杂度越低越好。

2.3.2 算法复杂度

算法复杂度分为时间复杂度和空间复杂度。其作用： 时间复杂度是度量算法执行的时间长短；而空间复杂度是度量算法所需存储空间的大小。

时间复杂度

1.时间频度
　　一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。

执行时间和运行的环境有关系,但是可以从理论上判断语句执行次数.–时间频度

2.分类
　　按数量级递增排列，常见的时间复杂度有：常数阶O(1),对数阶O(log2n),线性阶O(n),线性对数阶O(nlog2n),平方阶O(n2)，立方阶O(n3),…，k次方阶O(nk), 指数阶O(2n) 。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。
Eg：
要在 hash 表中找到一个元素就是 O(1)
要在无序数组中找到一个元素就是 O(n)
访问数组的第 n 个元素是 O(1)
访问链表的第 n 个元素是 O(n)

空间复杂度

与时间复杂度类似，空间复杂度是指算法在计算机内执行时所需存储空间的度量。记作: 　　S(n)=O(f(n)) 　　我们一般所讨论的是除正常占用内存开销外的辅助存储单元规模。

2.3.2.常见算法

递归，多种排序，多种查找，hash算法，雪花片算法等

2.4.小结

3.常见的数据结构

3.1.集合结构 SET

Set： 不可重复
HashSet
TreeSet

3.2.线性结构

常见的线性结构有，线性表，栈，队列，串和数组。

3.2.1.数组

数组就是相同数据类型的元素按一定顺序排列的集合

3.2.2.线性表

数据节点除了第一个和最后一个外，其他节点有且只有一个前驱和后继。
第一个节点没有前驱
最后一个没有后继

1）顺序表 把线性表按照顺序物理结构来存储

一般用数组来实现 相当于是ArrayList
2）链表 把线性表按照链式物理结构来存储 单向链表，双向链表，循环链表

Java中LinkedList

3.2.3.栈 顺序栈 链栈

栈是一种只能从表的一端存取数据且遵循 “先进后出” 原则的线性存储结构

3.2.4.队列 顺序队列 链式队列

队列是一种只能从表的一端进。另一端取数据且遵循 “先进先出” 原则的线性存储结构

3.2.5.串 String StringBuilder StringBuffer

串存储结构也是一种线性存储结构，因为字符串中的字符之间也具有"一对一"的逻辑关系

定长顺序存储：Java String

  不能追加

堆分配存储：用动态数组存储字符串； java StringBuilder，StringBuffer

可以进行追加

块链存储：用链表存储字符串 java中不支持

3.3.树形结构(了解)

无论是线性表，栈还是队列，它们都是线性结构的，每个节点的左边最多一个节点，右边也最多一个节点。对于大量的输入数据，线性表的访问时间太长，效率较低，不宜使用。

3.3.1.树的定义

在树结构中，除了根节点和叶子节点。其他节点都有一个前驱，1个或多个后继。
根没有前驱
叶子没有后继。

森林：多颗树就是森林

二叉树：就是有且仅有两个分叉的树，而多叉树当然是有很多分叉的树。

节点只有两个后继就叫二叉树。

3.3.2.二叉树

常用的二叉树有，二叉排序树，平衡二叉树，赫夫曼树，红黑树

1. 二叉排序树（二叉查找树）：
   二叉查找树是一种动态查找表，具有这些性质：
   （1）若它的左子树不为空，则左子树上的所有节点的值都小于它的根节点的值；
   （2）若它的右子树不为空，则右子树上所有节点的值都大于它的根节点的值；
   （3）其他的左右子树也分别为二叉查找树；
   （4）二叉查找树是动态查找表，在查找的过程中可见添加和删除相应的元素，在这些操作中需要保持二叉查找树的以上性质。
   

2)平衡二叉树
含有相同节点的二叉查找树可以有不同的形态，而二叉查找树的平均查找长度与树的深度有关，所以需要找出一个查找平均长度最小的一棵，那就是平衡二叉树，具有以下性质：
（1）要么是棵空树，要么其根节点左右子树的深度之差的绝对值不超过1；
（2）其左右子树也都是平衡二叉树；

3)红黑树（HashMap=数组+链表+红黑树）
红黑树是一种自平衡二叉树，在平衡二叉树的基础上每个节点又增加了一个颜色的属性，节点的颜色只能是红色或黑色。具有以下性质：
（1）根节点只能是黑色；
（2）红黑树中所有的叶子节点后面再接上左右两个空节点，这样可以保持算法的一致性，而且所有的空节点都是黑色；
（3）其他的节点要么是红色，要么是黑色，红色节点的父节点和左右孩子节点都是黑色，及黑红相间；
（4）在任何一棵子树中，从根节点向下走到空节点的路径上所经过的黑节点的数目相同，从而保证了是一个平衡二叉树。

3.3.3.多叉树

B-树、B+树（innodb底层索引）、字典树（trie树）、后缀树、广义后缀树。

3.4.图形结构-推荐

略过

3.5.小结

4.常见算法

4.1.散列算法（hash算法）

通过一个key能够获取唯一值。

T_Id%100+1

一致性hash算法

4.2.递归

递归: 自己调用自己，要有出口 1+2+3+…+100
递归优化：如果是做数据库查询的话，一次性查询出来，再来构造树状结构

4.3.排序

Java中 Arrays.sort Collections.sort

public static void main(String[] args) {
    int[] nums = {5,7,8,4,3};
    for (int i = 0; i < nums.length -1; i++) {
        for (int j = 0; j < nums.length-i-1; j++) {
            if (nums[j]>nums[j+1]){
                 int tmp  = nums[j+1];
                 nums[j+1] = nums[j];
                 nums[j] = tmp;
            }
        }
    }
    System.out.println(Arrays.toString(nums));
}

4.4.查找

https://www.jianshu.com/p/95d224c4d13e
[1.顺序查找] 无序数据查找

public class SearchTest {
    public static void main(String[] args) {
        Emp[] emps = {new Emp(3L,"zs"),new Emp(2L,"ls"),
                new Emp(9L,"ww"),new Emp(7L,"zl"),
                new Emp(5L,"tj"),new Emp(6L,"gw")};

        System.out.println(squ(emps, 5));

    }

    //顺序查询
    static Emp squ(Emp[] arr,int id){

        for (Emp emp : arr) {
           if (emp.getId().intValue()==id)
               return emp;
        }
        return null;
    }
}

class Emp{
    private Long id;
    private String name;

    public Long getId() {
        return id;
    }

    public void setId(Long id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public Emp(Long id, String name) {
        this.id = id;
        this.name = name;
    }

    public Emp() {
    }

    @Override
    public String toString() {
        return "Emp{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }
}

[2. 二分查找] 有序数据

package cn.itsource.algorithm;

import java.util.Arrays;
import java.util.Comparator;

public class SearchTest {
    public static void main(String[] args) {
        Employee[] employees = {new Employee(3L, "zs"), new Employee(2L, "ls"),
                new Employee(9L, "ww"), new Employee(7L, "zl"),
                new Employee(5L, "tj"), new Employee(6L, "gw")};


        //排序
        Arrays.sort(employees, new Comparator<Employee>() {
            @Override
            public int compare(Employee o1, Employee o2) {
                return o1.getId().intValue() < o2.getId().intValue() ? -1 : 1;
            }
        });

        for (Employee employee : employees) {
            System.out.println(employee);
        }

        System.out.println("==================");
        Long id = 3L;
        Employee employee = search(employees, id);
        System.out.println(employee);


    }

    //二分查找 
    public static Employee search(Employee[] employees,Long id){
        int low = 0;
        int high = employees.length - 1;
        int middle = 0;          //定义middle

        if(id < employees[low].getId() || id > employees[high].getId() || low > high){
            return null;
        }

        while(low <= high){
            middle = (low + high) / 2;
            if(employees[middle].getId() > id){
                //比关键字大则关键字在左区域
                high = middle - 1;
            }else if(employees[middle].getId() < id){
                //比关键字小则关键字在右区域
                low = middle + 1;
            }else{
                return employees[middle];
            }
        }

        return null;      //最后仍然没有找到，则返回-1

    }
}

[3. 插值查找]
[4. 斐波那契查找]
[5. 树表查找]
[6. 分块查找]
[7. 哈希查找] 一个key，一个map

5.课程总结

5.1.重点

5.2.难点

5.3.如何掌握？

1.多多理解
2.学会看说明手册

5.4.排错技巧（技巧）

1…
2…

6.课后练习

1.总结
2.课堂作业

7.面试题

8.扩展知识或课外阅读推荐（可选）

8.1.扩展知识

8.2.课外阅读

http://data.biancheng.net/