【数据结构（一）】初识数据结构

❣博主主页: 33的博客❣
▶文章专栏分类: Java从入门到精通◀
🚚我的代码仓库: 33的代码仓库🚚
🫵🫵🫵关注我带你学更多数据结构知识

1.前言

数据结构是计算机存储，组织数据的方式，指相互之间存在一种或多种特定关系的数据元素的集合，从这篇文章开始，我们将一起进入数据结构的学习，那么该如何学好数据结构呢？博主的建议是多写代码，多思考，多画图！

本章重点

掌握数据结构基本知识主要包括集合框架，时间和空间复杂度，算法效率，大O渐进表示，包装类，泛型相关知识。

---

2.集合架构

Java 集合框架Java Collection Framework ，又被称为容器和其实现类classes 。
类和接口总览：

---

3.时间和空间复杂度

遇到一个算法，我们怎么衡量一个算法的好坏呢？

3.1算法效率

算法效率分析分为两种：第一种是时间效率，第二种是空间效率。时间效率被称为时间复杂度，而空间效率被称作空间复杂度。

3.2时间复杂度

时间复杂度的定义：在计算机科学中，算法的时间复杂度是一个数学函数，它定量描述了该算法的运行时间。一个算法执行所耗费的时间，从理论上说，是不能算出来的，只有你把你的程序放在机器上跑起来，才能知道。但是我们需要每个算法都上机测试吗？是可以都上机测试，但是这很麻烦，所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。

有些算法的时间复杂度存在最好、平均和最坏情况:

最坏情况：任意输入规模的最大运行次数(上界)当说时间复杂度一般值最坏情况下
平均情况：任意输入规模的期望运行次数
最好情况：任意输入规模的最小运行次数(下界）

3.2.1大O的渐进表示

在计算时间复杂度时，我们不需要计算精确的执行次数，只需要大概的次数，那么我们就剋用大O渐进表示法去掉那些对结果影响不大的项，简明表示执行的次数。
规则：

1、用常数1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中，只保留最高阶项。
3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。

3.2.2常见时间复杂度举例

例1.

void func2(int N) {int count = 0;for (int k = 0; k < 2 * N ; k++) {count++;       //时间复杂度2N}int M = 10;while ((M--) > 0) {count++;	//时间复杂度10}System.out.println(count);}

时间复杂度2N+10 为O（N）

---

例2.

void func3(int N, int M) {int count = 0;for (int k = 0; k < M; k++) {count++;   //时间复杂度M}for (int k = 0; k < N ; k++) {count++;	//时间复杂度N}System.out.println(count);}

时间复杂度M+N为O（M+N）

---

例3.

// 计算func4的时间复杂度？
void func4(int N) {int count = 0;for (int k = 0; k < 100; k++) {count++;	//时间复杂度100}System.out.println(count);}

时间复杂度100为O（1）

---

例4.

// 计算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;}}}

假设array.length=N,那么第一次循环执行N-1次，第二次循坏执行N-2次，第三次循环执行N-3…最后一次为1，那么总次数就是（N-1)+(N-2)+(N-3)+…1,等差数列求和结果为（NN-N）/2那么时间复杂度为O（NN）。

---

例5.

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;}

那么剩下1个数就需要时间复杂度O（log2^N）。

---

例6.

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

递归复杂度=递归次数*每次递归后执行的次数
时间复杂度=（N-1）*1=O(N)

---

例7.

int fibonacci(int N) {return N < 2 ? N : fibonacci(N-1)+fibonacci(N-2);}//2^n

---

3.3空间复杂度

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度 。空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟时间复杂度类似，也使用大O渐进表示法。

---

例1.

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;}}}//输出O（1）

---

例2.

int[] fibonacci(int n) {long[] fibArray = new long[n + 1];fibArray[0] = 0;fibArray[1] = 1;for (int i = 2; i <= n ; i++) {fibArray[i] = fibArray[i - 1] + fibArray [i - 2];}return fibArray;}//O（N）

---

4.包装类

在Java中，由于基本类型不是继承自Object，为了在泛型代码中可以支持基本类型，Java给每个基本类型都对应了一个包装类型。

4.1基本数据和对应的包装类：

基本数据类型	包装类
byte	Byte
short	Short
int	Integer
long	Long
float	Float
double	Double
char	Character
boolean	Boolean

---

4.2装箱和拆箱

Integer a = 10;//装箱
int b = 20;
Integer c=b;//基本类型转变为包装类型

Integer a = 10;
int c = a;//拆箱，包装类型转换为基本类型

例

public static void main(String[] args) {Integer a = 127;Integer b = 127;Integer c = 128;Integer d = 128;System.out.println(a == b);//trueSystem.out.println(c == d);//false}

为什么输出结果一个是T一个是F呢，我们来看看源码

通过源码我们知道，如果范围在【-128，127】那么就返回数组中的值，否则就new一个对象。127在范围内，那么直接返回cache[255]的值；128不在范围内，久new一个 对象。

---

5.泛型

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

5.1引出范型

实现一个类，类中包含一个数组成员，使得数组中可以存放任何类型的数据，也可以根据成员方法返回数组中某个下标的值？

class MyArray {public Object[] array = new Object[10];public Object getPos(int pos) {return this.array[pos];}public void setVal(int pos,Object val) {this.array[pos] = val;}    }public class TestDemo {public static void main(String[] args) {MyArray myArray = new MyArray();myArray.setVal(0,10);myArray.setVal(1,"hello");//字符串也可以存放String ret = myArray.getPos(1);//编译报错//强行转化String ret =(String)myArray.getPos(1);System.out.println(ret);}}

但是我们发现，虽然任何类型的数据都可以存放，但是获得的时候报错，必须强制转换。但是，当代码很多的变量的时候，我们就不知道该变量是什么类型的，每次都要返回定义的时候去查看是什么类型，就比较繁琐。更多情况下，我们还是希望他只能够持有一种数据类型。而不是同时持有这么多类型。所以，泛型的主要目的：就是指定当前的容器，要持有什么类型的对象。让编译器去做检查。此时，就需要把类型，作为参数传递。需要什么类型，就传入什么类型。

---

5.2语法

class MyArray<T> {//添加< >表示这个类是泛型public T[] array = (T[])new Object[10];//这句代码是错误的，这样写只是为了不让编译器报错public T getPos(int pos) {return this.array[pos];}public void setVal(int pos,T val) {this.array[pos] = val;}}public class TestDemo {public static void main(String[] args) {MyArray<Integer> myArray = new MyArray<>();//传入<Integer>后，每次存储数据时会检查存入的数据是不是我传入的类型，获取数据的时候也不需要强制转化。myArray.setVal(0,10);myArray.setVal(1,12);int ret = myArray.getPos(1);System.out.println(ret);myArray.setVal(2,"bit");}}

---

5.3泛型类的使用

语法：

泛型类<参数类型> 变量名; //定义一个泛型类引用
MyArray<Integer> a;
new  泛型类<类型实参>(构造方法实参); // 示例化一个泛型类对象
MyArray<Integer> myArray = new MyArray<>();

5.4泛型是如何编译

在编译过程中将所有的T替换为object，这种机制称为擦除机制，在运行的时候并没有泛型的概念。
通过命令：javap -c 查看字节码文件，所有的T都是Object:

在编译的过程当中，将所有的T替换为Object这种机制，我们称为：擦除机制。
Java的泛型机制是在编译级别实现的。

实例化的时候不能实例化一个泛型数组。

T[] a=new T[5];//这样定义泛型是错误的，这个时候我们不知道到底定义的什么类型的数组
//以我们现在的知识，一般定义数组的时候，我们采取以下方式：
object[] a=new obje[5];

---

5.5泛型的上界

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

class 泛型类名称<类型形参 extends 类型边界> {...}
MyArray<Integer> l1;        // 正常，因为 Integer 是 Number 的子类型
MyArray<String> l2;     // 编译错误，因为 String 不是 Number 的子类型

---

5.6泛型方法

定义语法：

方法限定符 <类型形参列表> 返回值类型 方法名称(形参列表) { ... }

示例：

public class Util {//静态的泛型方法 需要在static后用<>声明泛型类型参数public static <E> void swap(E[] array, int i, int j) {E t = array[i];array[i] = array[j];array[j] = t;}}//使用Integer[] a = { ... };Util.swap(a, 0, 9);//使用类型推导Util.<Integer>swap(a, 0, 9);//不使用类型推导

---

6.总结

本篇介绍数据结构基本知识主要包括集合框架，时间和空间复杂度，算法效率，大O渐进表示，包装类，泛型相关知识，其中关于用泛型定义数组的内容，博主比并没有深入讲解，感兴趣的同学可以查看其他博主的内容。

下期预告：顺序表