数据结构初识

 目录 

1.初识

2.时间复杂度

常见时间复杂度举例：

3.空间复杂度

4.包装类&简单认识泛型

4.1装箱和拆箱

 5.泛型

6.泛型的上界

7.泛型方法

8.List接口

1.初识

1.多画图

2.多思考

3.多写代码

4.多做题

牛客网-题库/在线编程/剑指offer  算法篇：面试必刷TOP101(学哪个刷哪个)

5.看书籍：《大话数据结构》  查漏补缺

数据结构 是一门逻辑非常严谨的学科 学习的时候，学习的时候要多调试  因为代码量非常多！！！

前置知识：

1.泛型

2.包装类

Java当中集合类背后就是数据结构，集合类有很多，所以把这些集合类有些书上会叫作：集合框架

集合框架 里面有很多的集合类，每个集合类背后又是一个数据结构

学习的角度：

1.背后的数据结构

2.对应的集合类

3.集合框架

学习目标：

1.认识Java当中的集合类

2.学习复杂度

本质：数据结构的种类有很多！

为什么会有这么多数据结构？-》描述或者组织数据的方式不同   

每一个集合类描述和组织数据的方式是不一样的

概念：什么是数据结构？

数据结构=》数据+结构--》描述或者组织一些数据

2.时间复杂度

衡量算法效率~~~

算法中基本操作的执行次数，为算法的时间复杂度 

e.g.  3N^2+2N+10

三条规定：
1.用常数1取代运行时间中的所有加法常数     3N^2+2N+1

2.再修改后的运行次数函数中，只保留最高阶项  3N^2

3.如果最高阶项存在且不是1，则去除与这个项相乘的常数   所以 O（N^2）

常见时间复杂度举例：

// 计算bubbleSort的时间复杂度？（冒泡排序）
//相邻元素两两交换void bubbleSort(int[] array) {for (int end = array.length; end > 0; end--) {boolean sorted = true;for (int i = 1; i < end; i++) {if (array[i - 1] > array[i]) {Swap(array, i - 1, i);sorted = false;}}if (sorted == true) {break;}}
}

最好： (n -1)+(n -2)+...+1+0 = 1/2*n^2        O(N^2)

最坏：O（N）

//二分查找
int binarySearch(int[] array, int value) {int begin = 0;int end = array.length - 1;while (begin <= end) {int mid = begin + ((end-begin) / 2);if (array[mid] < value)begin = mid + 1;else if (array[mid] > value)end = mid - 1;elsereturn mid;}return -1;
}

时间复杂度的计算 不能光看代码 还要结合思想

// 计算阶乘递归factorial的时间复杂度？
long factorial(int N) {return N < 2 ? N : factorial(N-1) * N;
}

 递归的复杂度 = 递归的次数*每次递归执行的次数

时间复杂度为O（N) 

// 计算斐波那契递归fibonacci的时间复杂度？
int fibonacci(int N) {return N < 2 ? N : fibonacci(N-1)+fibonacci(N-2);
}

时间复杂度为O(2^n)

常见的复杂度：结合代码的思想来看

O（1）  O(logN)    O(N)   O(N*logN)   O(N*2)

3.空间复杂度

临时占用存储空间大小的量度

冒泡排序    O(1)           

斐波那契    O(N)

递归    O(N)

4.包装类&简单认识泛型

除了 Integer 和 Character， 其余基本类型的包装类都是首字母大写

4.1装箱和拆箱

public class Main{public static void main(String[] args) {Integer a = new Integer(10);int b = a;//自动拆箱System.out.println(b);//显示拆箱 拆箱为自己指定的元素int c = a.intValue();System.out.println(c);double d = a.doubleValue();System.out.println(d);}public static void main1(String[] args) {//装箱：把一个基本数据类型转化为包装类型的过程//自动装箱 & 显示装箱int a = 10;Integer b = a;//自动装箱System.out.println(b);Integer c = Integer.valueOf(a);//显示装箱System.out.println(c);}
}

面试题： 为什么一个True，一个False呢？

 原因：

装箱的源代码：

 5.泛型

泛型： 就是适用于许多许多类型 。从代码上讲，就是对类型实现了参数化。

泛型的主要目的：就是指定当前的容器，要吃有什么类型的对象。让编译器去做检查

/*
实现一个类，类中包含一个数组成员，使得数组中可以存放任何类型的数据，也可以根据成员方法返回数组中某个下标的值*/
import java.util.Arrays;//<T>:代表当前类是一个泛型类
//<T extends Number> T是Number或者Number的子类
class MyArray<T>{public Object[] array = new Object[10];//public T[] array = new T[10];不允许实例化一个泛型数组//public T[] array = (T[])new Object[10]; 这样写也不好！！！public void set(int pos,T val){array[pos] = val;}public T get(int pos){return (T)array[pos];//强转成T类型的元素}public Object[] getArray(){return array;}}
public class Main{public static void main(String[] args) {MyArray<String> myArray = new MyArray<>();//指定String类型的数据myArray.set(0,"hello");//myArray.set(1,90);这里不能放整型了String str = myArray.get(0);System.out.println(str);Object[] ret = myArray.getArray();System.out.println(Arrays.toString(ret));//相当于将类型作为参数传给TMyArray<Integer> myArray2 = new MyArray<>();myArray2.set(0,1);Integer a = myArray2.get(0);System.out.println(a);}
}

底层原理：

6.泛型的上界

在定义泛型类时，有时需要对传入的类型变量做一定的约束，可以通过类型边界来约束

语法

class 泛型类名称 < 类型形参 extends 类型边界 > {

}

小试牛刀：（复杂实例）

/*
写一个泛型类  实现一个方法，这个方法是求指定类型数组的最大值的T extends Comparable<T>   T一定是实现Comparable接口的
* */class Alg<T extends Comparable<T>> {public T findMax(T[] array) {T max = array[0];for (int i = 1; i < array.length; i++) {if(array[i].compareTo(max) >0){max = array[i];}}return max;}
}
class A implements Comparable<A>{@Overridepublic int compareTo(A o) {return 0;}
}
public class Main{public static void main(String[] args) {Alg<String> alg = new Alg<>();Alg<Integer> alg2 = new Alg<>();Alg<Integer> alg3 = new Alg<>();Integer[] array = {1,13,51,71,19};Integer ret = alg2.findMax(array);System.out.println(ret);}
}

extends在泛型中：上界  （拓展）

7.泛型方法

接下来我们实现一个泛型方法

class Alg2 {//泛型方法public<T extends Comparable<T>> T findMax(T[] array) {T max = array[0];for (int i = 1; i < array.length; i++) {if(array[i].compareTo(max) >0){max = array[i];}}return max;}
}
public class Main{public static void main(String[] args) {Alg2 alg2 = new Alg2();Integer[] array = {1,13,51,71,19};Integer ret = alg2.findMax(array);System.out.println(ret);}
}

 变成静态的话，不用实例化对象

8.List接口

import java.util.*;public class Main{ArrayList<String> arrayList = new ArrayList<>();List<String> list = new ArrayList<>();//推荐写法List<String> list1 = new Stack<>();List<String> list2 = new Vector<>();List<String> list3 = new LinkedList<>();}