第二十二篇 玩转数据结构——构建动态数组
生活随笔
收集整理的這篇文章主要介紹了
第二十二篇 玩转数据结构——构建动态数组
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
1.. 數組基礎
- 數組就是把數據碼成一排進行存放。
- Java中，數組的每個元素類型必須相同，可以都為int類型，string類型，甚至是自定義類型。
- 數組的命名要語義化，例如，如果數組用來存放學生的成績，那么命名為scores就比較合適。
- 索引（index）是數組中的一個重要概念，它是我們給數組中的每個元素分配的編號，從0開始，依次遞增。如果數組中存放了n個元素，第一個元素的索引是0，最后一個元素的索引是n-1。
- 通過索引，我們可以對數組中的元素進行快速訪問，例如，我們訪問索引為2的元素也就是數組中的第3個元素，就可以通過scores[2]這種形式。
- 在Java中聲明一個簡單的數組
- public class Main {public static void main(String[] args) {int[] arr = new int[10];for (int i = 0; i < arr.length; i++)arr[i] = i;}
}
?
- 聲明一個有初始值的數組
- public class Main {public static void main(String[] args) {int[] scores = new int[]{100, 99, 86};for (int i = 0; i < scores.length; i++)System.out.println(scores[i]);}
}
?
- for循環的另一種使用形式
- public class Main {public static void main(String[] args) {int[] scores = new int[]{100, 99, 86};for (int score : scores)System.out.println(score);}
}
?
- 修改數組中的元素
- socres[1] = 98;
?
- 數組的索引可以是語義化的，也可以是非語義化的。
- 數組的最大優點，就是可以通過索引對數據進行快速查詢，因此，我們傾向于使用語義化的索引，這樣我們就很清楚自己在查什么。
- 如果我們的應用場景中，索引沒有語義，那么使用其它數據結構可能是更好的選擇。
- 對于一些特殊應用場景，雖然使用了語義化索引，但依然不適合使用數組，例如，身份證號，我們不能使用身份證號來作為數組的索引，因為這個數字太大了，會導致巨大的空間浪費。
- 如果數組的索引是非語義化的，我們就需要考慮很多問題，例如，當數組的空間未被填滿時，如何表示空位處的元素？如何向數組中添加新的元素？如何刪除掉數組中原有的元素？等等。Java所提供的原生數組是無法解決這些問題的，我們需要定制屬于自己的數組類Array，即，基于Java的原生數組，二次封裝屬于我們自己的數組類。
2.. 實現自定義數組類Array所包含的基本方法：
- public class Array {private int[] data; //設置為private，不希望用戶從外部直接獲取這些信息，防止用戶篡改數據private int size;//構造函數，傳入數組的容量capacity構造Arraypublic Array(int capacity) {data = new int[capacity];size = 0;}//無參數構造函數，默認數組容量capacity=10public Array() {this(10); //這里的capacity是IDE自動添加的提示信息，實際不存在
}//獲取數組中的元素個數public int getSize() {return size;}//獲取數組的容量public int getCapacity() {return data.length;}//判斷數組是否為空public boolean isEmpty() {return size == 0;}
}
?
3.. 實現向自定義數組中添加元素的方法
- 向數組中添加元素的最簡單的方法就是向數組的末尾添加元素
- //向數組末尾添加一個新元素
public void addLast(int e) {if (size == data.length) {throw new IllegalArgumentException("AddLast failed. Array is full.");}data[size] = e;size++;
}
?
- 向數組中指定索引位置插入一個元素
- //在index位置插入一個新元素e
public void add(int index, int e) {if (size == data.length) {throw new IllegalArgumentException("Add failed. Array is full.");}if (index < 0 || index > size) {throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size");}for (int i = size - 1; i >= index; i--) {data[i + 1] = data[i];}data[index] = e;size++;
}
?
- 定義完向數組中指定索引位置插入一個元素的方法add之后，我們之前定義的向數組末尾插入元素的方法addLast其實可以調用add方法來實現，我們調整addLast方法如下：
- //向數組末尾添加一個新元素
public void addLast(int e) {add(size, e);
}
?
- 我們還可以調用add方法實現一個向數組開頭添加一個新元素的方法
- //向數組開頭添加一個新元素
public void addFirst(int e) {add(0, e);
}
?
4.. 實現在數組中查詢元素和修改元素的方法
- 實現自定義打印數組格式
- @Override
public String toString() { //覆蓋父類的toString方法
StringBuilder res = new StringBuilder();res.append(String.format("Array: size=%d, capacity=%d\n", size, data.length));res.append('[');for (int i = 0; i < size; i++) {res.append(data[i]);if (i != size - 1) {res.append(", ");}}res.append(']');return res.toString();
}
?
- 在main函數中進行測試：
- public class Main {public static void main(String[] args) {Array arr = new Array(20);for (int i = 0; i < 10; i++) {arr.addLast(i); //測試addLast方法
}System.out.println(arr);arr.add(1, 100); //測試add方法
System.out.println(arr);arr.addFirst(-1); //測試addFirst方法
System.out.println(arr);}}
?
- 打印效果如下：
- Array: size=10, capacity=20
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array: size=11, capacity=20
[0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array: size=12, capacity=20
[-1, 0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9]
?
- 實現獲取指定索引元素的方法
- //獲取index位置的元素
public int get(int index) {if (index < 0 || index >= size) {throw new IllegalArgumentException("Get failed. Index is illegal.");}return data[index];
}
?
- 實現修改指定索引元素的方法
- //修改index位置的元素為e
public void set(int index, int e) {if (index < 0 || index >= size) {throw new IllegalArgumentException("Set failed. Index is illegal.");}data[index] = e;
}
?
- 實現查看數組中是否包含元素e的方法
- //查找數組中是否存在元素e
public boolean contains(int e) {for (int i = 0; i < size; i++) {if (data[i] == e) {return true;}}return false;
}
?
- 實現查看數組中指定元素的索引的方法，若找不到，返回-1
- //查看數組中元素e的索引，若找不到元素e，返回-1
public int find(int e){for(int i=0;i<size;i++){if(data[i] == e){return i;}}return -1;
}
?
- 實現刪除數組中指定索引的元素的方法
- //刪除掉index位置的元素，并且返回所刪除的元素
public int remove(int index) {if (index < 0 || index >= size) {throw new IllegalArgumentException("Add failed. Require index >= 0 and index < size");}int ret = data[index];for (int i = index + 1; i < size; i++) {data[i - 1] = data[i];}size--;return ret;
}//刪除掉數組開頭的元素，并返回所刪除的元素
public int removeFirst() {return remove(0);
}//刪除掉數組末尾的元素，并返回所刪除的元素
public int removeLast() {return remove(size - 1);
}//如果數組中有元素e，那么將其刪除，否則什么也不做
public void removeElement(int e) {int index = find(e);if (index != -1) {remove(index);}
}
?
5.. 整理我們目前實現的業務邏輯：
- public class Array {private int[] data; //設置為private，不希望用戶從外部直接獲取這些信息，防止用戶篡改數據private int size;//構造函數，傳入數組的容量capacity構造Arraypublic Array(int capacity) {data = new int[capacity];size = 0;}//無參數構造函數，默認數組容量capacity=10public Array() {this(10); //這里的capacity是IDE自動添加的提示信息，實際不存在
}//獲取數組中的元素個數public int getSize() {return size;}//獲取數組的容量public int getCapacity() {return data.length;}//判斷數組是否為空public boolean isEmpty() {return size == 0;}//向數組末尾添加一個新元素epublic void addLast(int e) {add(size, e);}//向數組開頭添加一個新元素epublic void addFirst(int e) {add(0, e);}//在index位置插入一個新元素epublic void add(int index, int e) {if (size == data.length) {throw new IllegalArgumentException("Add failed. Array is full.");}if (index < 0 || index > size) {throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size");}for (int i = size - 1; i >= index; i--) {data[i + 1] = data[i];}data[index] = e;size++;}//獲取index位置的元素public int get(int index) {if (index < 0 || index >= size) {throw new IllegalArgumentException("Get failed. Index is illegal.");}return data[index];}//修改index位置的元素為epublic void set(int index, int e) {if (index < 0 || index >= size) {throw new IllegalArgumentException("Set failed. Index is illegal.");}data[index] = e;}//查找數組中是否存在元素epublic boolean contains(int e) {for (int i = 0; i < size; i++) {if (data[i] == e) {return true;}}return false;}//查看數組中元素e的索引，若找不到元素e，返回-1public int find(int e) {for (int i = 0; i < size; i++) {if (data[i] == e) {return i;}}return -1;}//刪除掉index位置的元素，并且返回刪除的元素public int remove(int index) {if (index < 0 || index >= size) {throw new IllegalArgumentException("Remove failed. Index is illegal.");}int ret = data[index];for (int i = index + 1; i < size; i++) {data[i - 1] = data[i];}size--;return ret;}//刪除掉數組開頭的元素，并返回刪除的元素public int removeFirst() {return remove(0);}//刪除掉數組末尾的元素，并返回刪除的元素public int removeLast() {return remove(size - 1);}//如果數組中有元素e，那么將其刪除，否則什么也不做public void removeElement(int e) {int index = find(e);if (index != -1) {remove(index);}}@Overridepublic String toString() { //覆蓋父類的toString方法
StringBuilder res = new StringBuilder();res.append(String.format("Array: size=%d, capacity=%d\n", size, data.length));res.append('[');for (int i = 0; i < size; i++) {res.append(data[i]);if (i != size - 1) {res.append(", ");}}res.append(']');return res.toString();}
}
?
6.. 現在我們的自定義數組的元素只允許為int類型，我們需要進行優化，讓數組可以放置"任意"類型的元素，解決這個問題的技術稱之為"泛型"。這里的"任意"加了引號，這是因為在Java中一個泛型類并不能放置任意數據類型的元素，泛型不能放置基本數據類型，只能放置類對象。在Java中，共有8中基本數據類型：int、short、long、boolean、byte、char、float、double。如果將數組設置成泛型數組，那么就無法放置這些基本數據類型了。為了解決這個問題，Java語言為每個基本數據類型都設計了一個包裝類，把本來不是類對象的數據包裝成了類對象。這8中基本數據類型所對應的包裝類分別為：Int、Short、Long、Boolean、Byte、Char、Float、Double，在需要的情況下，包裝類與其對應的基本數據類型可以自動進行轉換。
7.. 優化后，Array類的業務邏輯如下：- public class Array<E> {private E[] data; //設置為private，不希望用戶從外部直接獲取這些信息，防止用戶篡改數據private int size;//構造函數，傳入數組的容量capacity構造Arraypublic Array(int capacity) {data = (E[]) new Object[capacity];size = 0;}//無參數構造函數，默認數組容量capacity=10public Array() {this(10); //這里的capacity是IDE自動添加的提示信息，實際不存在
}//獲取數組中的元素個數public int getSize() {return size;}//獲取數組的容量public int getCapacity() {return data.length;}//判斷數組是否為空public boolean isEmpty() {return size == 0;}//向數組末尾添加一個新元素epublic void addLast(E e) {add(size, e);}//向數組開頭添加一個新元素epublic void addFirst(E e) {add(0, e);}//在index位置插入一個新元素epublic void add(int index, E e) {if (size == data.length) {throw new IllegalArgumentException("Add failed. Array is full.");}if (index < 0 || index > size) {throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size");}for (int i = size - 1; i >= index; i--) {data[i + 1] = data[i];}data[index] = e;size++;}//獲取index位置的元素public E get(int index) {if (index < 0 || index >= size) {throw new IllegalArgumentException("Get failed. Index is illegal.");}return data[index];}//修改index位置的元素為epublic void set(int index, E e) {if (index < 0 || index >= size) {throw new IllegalArgumentException("Set failed. Index is illegal.");}data[index] = e;}//查找數組中是否存在元素epublic boolean contains(E e) {for (int i = 0; i < size; i++) {if (data[i].equals(e)) {return true;}}return false;}//查看數組中元素e的索引，若找不到元素e，返回-1public int find(E e) {for (int i = 0; i < size; i++) {if (data[i].equals(e)) {return i;}}return -1;}//刪除掉index位置的元素，并且返回刪除的元素public E remove(int index) {if (index < 0 || index >= size) {throw new IllegalArgumentException("Remove failed. Index is illegal.");}E ret = data[index];for (int i = index + 1; i < size; i++) {data[i - 1] = data[i];}size--; //data[size]會指向一個類對象，這部分空間不會被釋放loitering objectsdata[size] = null;return ret;}//刪除掉數組開頭的元素，并返回刪除的元素public E removeFirst() {return remove(0);}//刪除掉數組末尾的元素，并返回刪除的元素public E removeLast() {return remove(size - 1);}//如果數組中有元素e，那么將其刪除，否則什么也不做public void removeElement(E e) {int index = find(e);if (index != -1) {remove(index);}}@Overridepublic String toString() { //覆蓋父類的toString方法
StringBuilder res = new StringBuilder();res.append(String.format("Array: size=%d, capacity=%d\n", size, data.length));res.append('[');for (int i = 0; i < size; i++) {res.append(data[i]);if (i != size - 1) {res.append(", ");}}res.append(']');return res.toString();}
}
?
8.. 再次在main方法中實例化我們的自定義數組，進行測試：
- public class Main {public static void main(String[] args) {Array<Integer> arr = new Array<>(20);for (int i = 0; i < 10; i++) {arr.addLast(i);}System.out.println(arr);arr.add(1, 100);System.out.println(arr);arr.addFirst(-1);System.out.println(arr);arr.remove(2);System.out.println(arr);arr.removeElement(4);System.out.println(arr);arr.removeFirst();System.out.println(arr);arr.removeLast();System.out.println(arr);}
}
?
- 輸出結果如下：
- Array: size=10, capacity=20
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array: size=11, capacity=20
[0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array: size=12, capacity=20
[-1, 0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array: size=11, capacity=20
[-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array: size=10, capacity=20
[-1, 0, 1, 2, 3, 5, 6, 7, 8, 9]
Array: size=9, capacity=20
[0, 1, 2, 3, 5, 6, 7, 8, 9]
Array: size=8, capacity=20
[0, 1, 2, 3, 5, 6, 7, 8]
?
9.. 測試讓自定義數組去承載對象
- public class Student {private String name;private int score;public Student(String studetName, int studentScore) {name = studetName;score = studentScore;}@Overridepublic String toString() {return String.format("Student(name: %s, score: %d)", name, score);}public static void main(String[] args) {Array<Student> arr = new Array<>();arr.addLast(new Student("XueZou", 98));arr.addLast(new Student("Guiche", 100));arr.addLast(new Student("QUiShui", 99));System.out.println(arr);}
}
?
- 輸出結果如下：
- Array: size=3, capacity=10
[Student(name: XueZou, score: 98), Student(name: Guiche, score: 100), Student(name: QUiShui, score: 99)]
?
- 修改add方法的業務邏輯，使自定義數組支持擴容
- //在index位置插入一個新元素e
public void add(int index, E e) {if (index < 0 || index > size) {throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size");}if (size == data.length) {resize(2 * size); //擴大為原容量的2倍
}for (int i = size - 1; i >= index; i--) {data[i + 1] = data[i];}data[index] = e;size++;
}
?
- 我們需要實現resize方法，業務邏輯如下：
- private void resize(int newCapacity) {E[] newData = (E[]) new Object[newCapacity];for (int i = 0; i < size; i++) {newData[i] = data[i];}data = newData;
}
?
- 實現擴容后，進行測試：
- public static void main(String[] args) {Array<Integer> arr = new Array<>();for (int i = 0; i < 10; i++) {arr.addLast(i);}System.out.println(arr);arr.add(1, 100);System.out.println(arr);arr.addFirst(-1);System.out.println(arr);
}
?
- 輸出效果如下：
- Array: size=10, capacity=10
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array: size=11, capacity=20
[0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array: size=12, capacity=20
[-1, 0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9]
?
- 修改remove方法，使數組中的元素減少到一定程度時，自動縮小數組容量
- //刪除掉index位置的元素，并且返回刪除的元素
public E remove(int index) {if (index < 0 || index >= size) {throw new IllegalArgumentException("Remove failed. Index is illegal.");}E ret = data[index];for (int i = index + 1; i < size; i++) {data[i - 1] = data[i];}size--; //data[size]會指向一個類對象，這部分空間不會被釋放loitering objectsdata[size] = null;if (size == data.length / 2) {resize(data.length / 2); //被利用的空間等于總空間的一半時，將數組容量減少一半
}return ret;
}
?
- 實現自動降低容量后，進行測試：
- public static void main(String[] args) {Array<Integer> arr = new Array<>();for (int i = 0; i < 10; i++) {arr.addLast(i);}System.out.println(arr);arr.add(1, 100);System.out.println(arr);arr.addFirst(-1);System.out.println(arr);arr.remove(2);System.out.println(arr);arr.removeElement(4);System.out.println(arr);arr.removeFirst();System.out.println(arr);
}
?
- 輸出效果如下：
- Array: size=10, capacity=10
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array: size=11, capacity=20
[0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array: size=12, capacity=20
[-1, 0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array: size=11, capacity=20
[-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array: size=10, capacity=10
[-1, 0, 1, 2, 3, 5, 6, 7, 8, 9]
Array: size=9, capacity=10
[0, 1, 2, 3, 5, 6, 7, 8, 9]
?
- O(1), O(n), O(lgn), O(nlgn), O(n^2)
- 大O描述的是算法的運行時間和輸入數據之間的關系
- 通常我們會說下面的這段代碼的算法是O(n)的，n在這里簡單理解為nums中的元素個數，O(n)是說下面這段代碼的運行效率，與nums中的元素個數n是呈線性關系的，線性關系體現在n是一次方。
- public static int sum(int[] nums) {int sum = 0;for (int num: nums) {sum += num;return sum;}
?
- 按照這個思路我們對上面所實現的方法，挨個分析一下它們的算法的時間復雜度：添加操作中addLast(e)方法的時間復雜度是O(1)，這表示我們的算法所消耗的時間與我們數據的規模沒有關系，這里所指的數據規模是我們數組中的元素個數；addFirst(e)方法的時間復雜度是O(n)，因為每個元素都需要向后移動一位；add(index, e)方法的時間復雜度與index的具體取值相關，它的時間復雜度也是O(n)；綜合來看，添加操作是一個O(n)級別的算法。
- 刪除操作中，removeLast(e)方法的時間復雜度是O(1)；removeFirst(e)的時間復雜度是O(n)；remove(index, e)的時間復雜度也是O(n)；綜合來看，刪除操作的時間復雜度也是O(n)。
- 修改操作set(index, e)的時間復雜度是O(1)，這是數組的最大優勢，專業術語稱為"支持隨機訪問"。
- 查詢操作中，get(index)方法的時間復雜度是O(1)；find(e)方法和contains(e)方法的時間復雜度都是O(n)。
- 增：時間復雜度O(n);
- 刪：時間復雜度O(n);
- 改：已知索引O(1)，未知索引O(n);
- 查：已知索引O(1)，未知索引O(n);
- 因此，索引具有語義時，選擇數組是非常好的，我們可以通過索引輕松檢索數據中的內容。
- 對于添加操作，如果我們只使用addLast方法，那么它的時間復雜度本來應該是O(1)，但是，由于存在resize方法，而resize方法的時間復雜度是O(n)，所以addLast方法的時間復雜度就不是O(1)了，但是它的均攤復雜度是O(1);
- 類似的對于刪除操作，如果只使用removeLast方法，那么它的均攤復雜度也是O(1);
- 復雜度震蕩，是指我們在數組容量的臨界位置交替進行添加和刪除操作，這會導致數組不斷執行擴容和縮容操作，而擴容和縮容的時間復雜度都是O(n)，出現這種問題的原因在于，我們執行removeLast方法后，resize得有點著急(Eager)，解決方案是使用更加懶惰的策略(Lazy)，簡單理解就是，當數組占用量剛好減到1/2時，不著急縮容，等減到1/4時，再觸發縮容，只縮1/2。
- 我們需要稍微改動一下remove方法，如下所示：
- public E remove(int index) {if (index < 0 || index >= size) {throw new IllegalArgumentException("Remove failed. Index is illegal.");}E ret = data[index];for (int i = index + 1; i < size; i++) {data[i - 1] = data[i];}size--; //data[size]會指向一個類對象，這部分空間不會被釋放loitering objectsdata[size] = null;if (size == data.length / 4 && data.length / 2 != 0) { //改動在這里resize(data.length / 2); //被利用的空間等于總空間的一半時，將數組容量減少一半
}return ret;
}
?
轉載于:https://www.cnblogs.com/xuezou/p/9276945.html
創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎總結
以上是生活随笔為你收集整理的第二十二篇 玩转数据结构——构建动态数组的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Word文件怎么快速查找关键词
- 下一篇： .net 技术类网址