Day9

1.定时器

定时任务java.util.TimerTask由 定时器java.util.Timer安排为一次执行或重复执行的任务。

eg:（1）重写定时任务

public class MyTimerTask extends TimeTask{
    @Override
    public void run(){
        System.out.println(" ...");
    }
}

(2)测试定时器执行任务

Timer timer=new Timer();//创建定时器 ​ MyTimerTask myTimerTask=new MyTimerTask();//创建一个任务 ​ time.schedule(myTimerTask,5000)//任务在五秒后执行

2.数据结构

定义

数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成 。

常用的数据结构有：数组，栈，链表，队列，树，图，堆，散列表等。

集合：数据结构中的元素之间除了“同属一个集合” 的相互关系外，别无其他关系。

线性结构

数据结构中的元素存在一对一的相互关系。

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

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

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

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

树形结构

数据结构中的元素存在一对多的相互关系。

树：是一种数据结构，它是由n(n>=1)个有限结点组成一个具有层次关系的集合。

二叉树：树中包含的各个节点的度不能超过 2 ，也就是任意节点最多只有两个分叉的树，而多叉树当然是有很多分叉的树 ，在二叉树的概念下又衍生出满二叉树和完全二叉树的概念，而从存储结构上来说，二叉树又分为基于顺序存储（数组）的二叉树，和基于链式(链表)存储的二叉树。

红黑树: 是一种自平衡二叉树，在平衡二叉树的基础上每个节点又增加了一个颜色的属性，节点的颜色只能是红色或黑色。

图形结构

数据结构中的元素存在多对多的相互关系。

无向图：图的边是没有方向的。

有向图：图的边是有方向的。

有向无环：图的边是有方向的，但是不会形成一个闭环。

混合图：图的边可能是无向的，也可能是有向的。

顺序存储结构

一组地址连续的存储单元依次存储线性表的各个数据元素。

链接存储结构

它不要求逻辑上相邻的元素在物理位置上也相邻。

数据索引存储结构：

除建立存储结点信息外，还建立附加的索引表来标识结点的地址。

数据散列存储结构

是一种力图将数据元素的存储位置与关键字之间建立确定对应关系的查找技术。

自定义数据结构-(链表结构)

public class LinkedList {
    //链表顶端
    Node first;
    int size;
    public void add(Object obj){
        Node node = new Node(obj);
        //每次添加数据封装成一个Node对象
        if(first == null){
        //如果是第一次添加数据,应该将第一个节点放到链表顶端first
        first = node;
        }else{
        二次，三次 及之后新的数据添加到链表尾部，挂在最后一个Node对象后面
        Node temp = first;
        temp.next == null;
        表示最后一个节点
        temp.next != null;
        表示还有下一个节点,所以需要遍历
        while(temp.next != null){
            temp = temp.next;
            //把下一个节点地址值给到temp，temp最终指向最后一个节点
        }
            temp.next = node;
            //最新的节点挂到链表末尾
        }
        size++;
    }
}

3.算法

定义

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

算法的五大特征：输入、输出、有穷性、确定性、可行性。

输入：零个或多个输入。

输出：一个或多个输出。

有穷性：有限步骤后在可接受时间内完成。

确定性：每个步骤都有确定含义，无二义性。

可行性：每一步都是可行的。

算法设计要求：正确性、可读性、健壮性、时间效率高和存储低。

正确性：有输入输出，无二义性，有正确答案。

可读性：方便阅读。

健壮性：输入不合法能处理

时间效率高和存储低：时间空间复杂度越低越好。

算法复杂度

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

时间复杂度

按数量级递增排列，常见的时间复杂度有：常数阶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)

二分搜索的时间复杂度最好的情况是 O(1)，最坏情况（平均情况）下 O(log n)

访问链表的第 n 个元素是 O(n)

一个For循环是O(n)

两个For循环嵌套是O(n2) --> 课程TreeData查询

三个Foreach嵌套是O(n3)

空间复杂度

与时间复杂度类似，空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。比如直接插入排序的时间复杂度是O(n^2),空间复杂度是O(1) 。而一般的递归算法就要有O(n)的空间复杂度了，因为每次递归都要存储返回信息。一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。我们一般所讨论的是除正常占用内存开销外的辅助存储单元规模，一个算法的好坏通过时间复杂度和空间复杂度来衡量。

递归

递归: 自己调用自己，要有出口

排序

查找

顺序查找：无序数据查找,从前往后查找。

二分查找：有序数据中进行查找