?博主主頁: 33的博客?
?文章專欄分類: Java從入門到精通?
🚚我的代碼倉庫: 33的代碼倉庫🚚
🫵🫵🫵關注我?guī)銓W更多數據結構知識

1.前言

數據結構是計算機存儲，組織數據的方式，指相互之間存在一種或多種特定關系的數據元素的集合，從這篇文章開始，我們將一起進入數據結構的學習，那么該如何學好數據結構呢？博主的建議是多寫代碼，多思考，多畫圖！

本章重點

掌握數據結構基本知識主要包括集合框架，時間和空間復雜度，算法效率，大O漸進表示，包裝類，泛型相關知識。

---

2.集合架構

Java 集合框架Java Collection Framework ，又被稱為容器和其實現類classes 。
類和接口總覽：

---

3.時間和空間復雜度

遇到一個算法，我們怎么衡量一個算法的好壞呢？

3.1算法效率

算法效率分析分為兩種：第一種是時間效率，第二種是空間效率。時間效率被稱為時間復雜度，而空間效率被稱作空間復雜度。

3.2時間復雜度

時間復雜度的定義：在計算機科學中，算法的時間復雜度是一個數學函數，它定量描述了該算法的運行時間。一個算法執(zhí)行所耗費的時間，從理論上說，是不能算出來的，只有你把你的程序放在機器上跑起來，才能知道。但是我們需要每個算法都上機測試嗎？是可以都上機測試，但是這很麻煩，所以才有了時間復雜度這個分析方式。一個算法所花費的時間與其中語句的執(zhí)行次數成正比例，算法中的基本操作的執(zhí)行次數，為算法的時間復雜度。

有些算法的時間復雜度存在最好、平均和最壞情況:

最壞情況：任意輸入規(guī)模的最大運行次數(上界)當說時間復雜度一般值最壞情況下
平均情況：任意輸入規(guī)模的期望運行次數
最好情況：任意輸入規(guī)模的最小運行次數(下界）

3.2.1大O的漸進表示

在計算時間復雜度時，我們不需要計算精確的執(zhí)行次數，只需要大概的次數，那么我們就剋用大O漸進表示法去掉那些對結果影響不大的項，簡明表示執(zhí)行的次數。
規(guī)則：

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,那么第一次循環(huán)執(zhí)行N-1次，第二次循壞執(zhí)行N-2次，第三次循環(huán)執(zhí)行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;}

遞歸復雜度=遞歸次數*每次遞歸后執(zhí)行的次數
時間復雜度=（N-1）*1=O(N)

---

例7.

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

---

3.3空間復雜度

空間復雜度是對一個算法在運行過程中臨時占用存儲空間大小的量度 ?？臻g復雜度不是程序占用了多少bytes的空間，因為這個也沒太大意義，所以空間復雜度算的是變量的個數?？臻g復雜度計算規(guī)則基本跟時間復雜度類似，也使用大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;//基本類型轉變?yōu)榘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);}}

但是我們發(fā)現，雖然任何類型的數據都可以存放，但是獲得的時候報錯，必須強制轉換。但是，當代碼很多的變量的時候，我們就不知道該變量是什么類型的，每次都要返回定義的時候去查看是什么類型，就比較繁瑣。更多情況下，我們還是希望他只能夠持有一種數據類型。而不是同時持有這么多類型。所以，泛型的主要目的：就是指定當前的容器，要持有什么類型的對象。讓編譯器去做檢查。此時，就需要把類型，作為參數傳遞。需要什么類型，就傳入什么類型。

---

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 查看字節(jié)碼文件，所有的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 {//靜態(tài)的泛型方法 需要在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漸進表示，包裝類，泛型相關知識，其中關于用泛型定義數組的內容，博主比并沒有深入講解，感興趣的同學可以查看其他博主的內容。

下期預告：順序表