Algorithms_基础数据结构(01)_线性表之数组数组的应用案例分析
文章目錄
- 大綱圖
- 數組的經典面試題目
- 數據結構三要素
- 數據邏輯結構（線性結構&非線性結構）
- 數據存儲結構（順序存儲、鏈式存儲、索引存儲和散列存儲）
- 順序存儲
- 鏈式存儲
- 索引存儲
- 散列存儲
- 數據的運算
- 線性表
- 什么是數組
- 數組的訪問
- 數組的插入與刪除
- 插入
- 刪除
- 數組的CRUD
- 增加
- 刪除
- 修改
- 查找
- 完整示例
- 引導案例參考答案
大綱圖
數組的經典面試題目
給你一個文件里面包含全國人民（14億）的年齡數據（0~180），現在要你統計每一個年齡有多少人？ 給定機器為 單臺+2CPU+2G內存。不得使用現成的容器，比如map等。
文件格式
18 19 21 18 3 9 .... ....數據結構三要素
我們都知道數據結構三要素
- 數據邏輯結構
- 數據存儲結構
- 數據的運算
數據邏輯結構（線性結構&非線性結構）
邏輯結構是指數據元素之間的邏輯關系，即從邏輯關系上描述數據。它與數據的存儲無關，是獨立于計算機的。
數據存儲結構（順序存儲、鏈式存儲、索引存儲和散列存儲）
存儲結構是指數據結構在計算機中的表示（又稱映像），也稱物理結構。它包括數據元素的表示和關系的表示。
數據的存儲結構是邏輯結構用計算機語言的實現，它依賴于計算機語言。數據的存儲結構主要有：順序存儲、鏈式存儲、索引存儲和散列存儲。
順序存儲
把邏輯上相鄰的元素存儲在物理位置上也相鄰的存儲單元里，元素之間的關系由存儲單元的鄰接關系來體現。
- 優點是可以實現隨機存取，每個元素占用最少的存儲空間；
- 缺點是只能使用相鄰的一整塊存儲單元，因此可能產生較多的外部碎片。
鏈式存儲
不要求邏輯上相鄰的元素在物理位置上也相鄰，借助指示元素存儲地址的指針表示元素之間的邏輯關系。
- 優點是不會出現碎片現象，充分利用所有存儲單元；
- 缺點是每個元素因存儲指針而占用額外的存儲空間，并且只能實現順序存取。
索引存儲
存儲元素信息的同時，還建立附加的索引表。索引表中的每一項稱為索引項，索引項的一般形式是：（關鍵字，地址）。
- 優點是檢索速度快；
- 缺點是增加了附加的索引表，會占用較多的存儲空間。另外，在增加和刪除數據時要修改索引表，因而會花費較多的時間。
散列存儲
根據元素的關鍵字直接計算出該元素的存儲地址，又稱為Hash存儲。
- 優點是檢索、增加和刪除結點的操作都很快；
- 缺點是如果散列函數不好可能出現元素存儲單元的沖突，而解決沖突會增加時間和空間開銷。
數據的運算
施加在數據上的運算包括運算的定義和實現。運算的定義是針對邏輯結構的，指出運算的功能；運算的實現是針對存儲結構的，指出運算的具體操作步驟。
線性表
我們知道具有“一對一”邏輯關系的數據，最好的存儲方式是使用線性表。
線性表，形象的可以理解為物理空間中的一段內存區域中存儲的數據，用一條線串起來的，前后相連
其中又可以細分為： 順序表和 鏈表
順序表： 將數據依次存儲在連續的整塊物理空間中，這種存儲結構稱為順序存儲結構,簡稱順序表
鏈表： 數據分散的存儲在物理空間中，通過指針維系它們之間的邏輯關系，這種存儲結構稱為鏈式存儲結構，簡稱鏈表
數據結構中，一組數據中的每個個體被稱為“數據元素”（簡稱“元素”）。例如，圖 1 顯示的這組數據，其中 1、2、3、4 和 5 都是這組數據鐘的一個元素。
- 某一元素的左側相鄰元素稱為“直接前驅”，位于此元素左側的所有元素都統稱為“前驅元素”；
- 某一元素的右側相鄰元素稱為“直接后繼”，位于此元素右側的所有元素都統稱為“后繼元素”；
順序表存儲數據同數組非常接近。其實，順序表存儲數據使用的就是數組，接下來我們就以數組為例來演示線性表吧
什么是數組
數組是一個有限的、類型相同的數據的集合，在內存中是一段連續的內存區域。
perceive : 感知
store in RAM : 在 Random Access Memory 中的存儲 。
consecutive: 連續的
- 數組下標從0開始，如上圖對應著下標依次是0、1、2、3、4、5。
- 數組里面存儲的數據類型必一致，上圖中存的都是int類型。
- 數組中的全部元素是“連續”的存儲在一塊內存空間中的，如上圖右側，元素與元素之間不會有別的存儲隔離。
- 另外，也是因為數組需要連續的內存空間，所以數組在定義的時候就需要提前指定固定大小，不能改變。
數組的訪問
數組支持隨機訪問.
我們可以通過下標隨機訪問數組中任何一個元素, 因為數組元素的存儲是連續的，所以我們可以通過數組內存空間的首地址加上元素的偏移量計算出某一個元素的內存地址，如下：
array[n]的地址 = array數組內存空間的首地址 + 每個元素大小*n舉個例子： 有一個長度為10的int數組，int[] a = new int[10].
計算機給數組a[10]分配了一塊連續的內存空間1000~1039,其中，內存塊的首地址為base_address = 1000.
計算機會為每個內存單元分配一個地址，計算機通過地址來訪問內存中的數據。當計算即需要隨機訪問數組中的某個元素的時候，它會首先通過下面的尋址公式，計算該元素存存儲的內存地址：
a[i]_address = base_address + i * data_type_size其中data_type_size表示數組中每個元素的大小。例如，數組中存儲的int類型的數據，所以，data_type_size就是4字節。
通過上述公式可知：數組中通過下標去訪問數據時并不需要遍歷整個數組，因此數組的訪問時間復雜度是 O(1).
當然這里需要注意，如果不是通過下標去訪問，而是通過內容去查找數組中的元素，則時間復雜度不是O(1)，極端的情況下需要遍歷整個數組的元素，時間復雜度可能是O(n).
通過不同的查找算法所需的時間復雜度是不一樣的。
數組的插入與刪除
因為數組元素的連續性要求，所以導致數組在插入和刪除元素的時候效率比較低.
舉個例子
插入
假設要在數組中間插入一個新元素，就必須要將相鄰的后面的元素全部往后移動一個位置，留出空位給這個新元素。
還是拿上面那圖舉例，如果需要在下標為2的地方插入一個新元素11，那就需要將原有的2、3、4、5幾個下標的元素往后移動一位，新元素再插入下標為2的位置，最后形成新的數組是 23、4、11、6、15、5、7
刪除
數組的刪除與數組的插入類似。刪除一個元素，就必須要將相鄰的后面的元素全部往前移動一個位。
- 如果新元素是插入在數組的最開頭位置，那整個原始數組都需要向后移動一位，此時的時間復雜度為最壞情況即O(n).
- 如果新元素要插入的位置是最末尾，則無需其它元素移動，則此時時間復雜度為最好情況即O(1）
- 所以數組插入的時間復雜度是O(n)
如果需要刪除一個元素，需要把它后面的元素全部一個一個往前移動（不能同時移動！），元素越多，耗時越長。
舉個例子： 把第三個元素刪除后引起了4次元素移動。
或者下面的這個圖更直觀一些
數組的CRUD
約定好哈： 按順序添加，不要跳著添加參數
我們知道數組是內存內連續的一段區域，雖然初始化數組后，通過首地址以及數組內元素類型的長度，可以任意的找到下標對應元素的內存地址，為啥不建議跳著插入呢？ ，舉個例子 比如 1個 數組，容量為10 ，下標 0 ~9 ， 你跳著插入a[9] ,然后又在a[9]前面未插入值的下標位置插入了一個值，那么該下標后面的元素都要后移一，最后一位沒地方可以存了。。。這種情況就必須得擴容了，才能保證數據不丟失。 (擴容也很簡單：弄個臨時數組，容量為原來的2倍，把原來的數組的數據copy過去。 至于什么時候觸發這個擴容，JDK中的加載因子是原數組的容量使用了0.75的時候)
這樣搞得話，是不是造成了空間的浪費？？？
增加
/*** @param index 數組下標* @param element 目標值*/public void add(int index, int element) {if (index < 0 || index > (arr.length - 1)) {throw new IllegalArgumentException("參數錯誤");}if (size == arr.length) {throw new IllegalArgumentException("Array Full");}// Step 1 : 從最后一個元素一直到index位置的元素，往后挪動一位for (int i = (arr.length - 1); i > index; i--) {// 從最后一位開始，不能寫成 arr[i+1] = arr[i]; 第一次循環 下標為最后一位 index +1 下標越界arr[i] = arr[i -1 ];}// Step 2 : 空出來的那個下標位置，賦值arr[index] = element;// Step 3 : 維護數組當前sizesize++;}核心代碼：
// Step 1 : 從最后一個元素一直到index位置的元素，往后挪動一位for (int i = (arr.length - 1); i > index; i--) {// 從最后一位開始，不能寫成 arr[i+1] = arr[i]; 第一次循環 下標為最后一位 +1 下標越界arr[i] = arr[i -1 ];}// Step 2 : 空出來的那個下標位置，賦值arr[index] = element;解釋下：
數組的特性，是內存中一段連續的區域，
-------> 初始化特定容量的數組后，這個數組所占用的內存大小就是確定的
------> 繼而每個下標對應的元素在內存中的地址就是可以通過如下公式計算出來的 a[i]_address = base_address + i * data_type_size
------>
刪除
public void delete(int index){if (index < 0 || index > (arr.length -1)){throw new IllegalArgumentException("參數不合法");}for (int i = index ; i< (arr.length -1); i++) {if (i != arr.length-1){ // 防止最后一位，進入運算后 i+1 導致數據組下標越界arr[i] = arr[i+1];}else{// 最后一位 初始arr[i] = 0 ;}}size--;}修改
public void update(int index, int element){if (index < 0 || index > (arr.length - 1)) {throw new IllegalArgumentException("參數錯誤");}arr[index] = element;}查找
public int get(int index){if (index < 0 || index > (arr.length - 1)) {throw new IllegalArgumentException("參數錯誤");}return arr[index];}完整示例
/*** @author 小工匠* @version v1.0* @create 2019-12-25 21:59* @motto show me the code ,change the word* @blog https://artisan.blog.csdn.net/* @description**/public class ArtisanArray {/*** 存儲元素的數組*/private int[] arr;/*** 當前數組中元素的個數*/private int size;/*** 默認初始化容量為16的int數組*/public ArtisanArray() {this.arr = new int[16];this.size = 0;}/*** 指定數組容量** @param capacity*/public ArtisanArray(int capacity) {this.arr = new int[capacity];this.size = 0;}/*** @param index 數組下標* @param element 目標值*/public void add(int index, int element) {if (index < 0 || index > (arr.length - 1)) {throw new IllegalArgumentException("參數錯誤");}if (size == arr.length) {throw new IllegalArgumentException("Array Full");}// Step 1 : 從最后一個元素一直到index位置的元素，往后挪動一位for (int i = (arr.length - 1); i > index; i--) {// 從最后一位開始，不能寫成 arr[i+1] = arr[i]; 第一次循環 下標為最后一位 index +1 下標越界arr[i] = arr[i -1 ];}// Step 2 : 空出來的那個下標位置，賦值arr[index] = element;// Step 3 : 維護數組當前sizesize++;}public void delete(int index){if (index < 0 || index > (arr.length -1)){throw new IllegalArgumentException("參數不合法");}for (int i = index ; i< (arr.length -1); i++) {if (i != arr.length-1){ // 防止最后一位，進入運算后 i+1 導致數據組下標越界arr[i] = arr[i+1];}else{// 最后一位 初始arr[i] = 0 ;}}size--;}public void update(int index, int element){if (index < 0 || index > (arr.length - 1)) {throw new IllegalArgumentException("參數錯誤");}arr[index] = element;}public int get(int index){if (index < 0 || index > (arr.length - 1)) {throw new IllegalArgumentException("參數錯誤");}return arr[index];}public static void main(String[] args) {ArtisanArray artisanArray = new ArtisanArray(10);System.out.println("Init...");// 初始化幾個數據artisanArray.add(0, 10);artisanArray.add(1, 11);artisanArray.add(2, 12);artisanArray.add(3, 13);artisanArray.add(4, 14);artisanArray.add(5, 15);artisanArray.add(6, 16);artisanArray.add(7, 17);artisanArray.print();System.out.println("ADD... INDEX = 5");artisanArray.add(5, 25);artisanArray.print();System.out.println("UPDATE... INDEX = 5");artisanArray.update(5, 55);artisanArray.print();System.out.println("GET... INDEX = 5");System.out.println(artisanArray.get(5));System.out.println("DELETE... INDEX = 5");artisanArray.delete(5);artisanArray.print();}public void print() {System.out.println("數組容量capacity：" + arr.length + " ,數組當前數據量size=" + size);for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}System.out.println();System.out.println();} }引導案例參考答案
再來看下我們的這個問題
給你一個文件里面包含全國人民（14億）的年齡數據（0~180），現在要你統計每一個年齡有多少人？ 給定機器為 單臺+2CPU+2G內存。不得使用現成的容器，比如map等。
分析：
----> 年齡范圍 0~180 , 是不是開辟一個容量為181的數組就夠了？
----> 統計每一個年齡有多少人—> 每個年齡就是對應的數組下標，碰到一個 逐個加一，是不是就解決了？
Code
import java.io.*; import java.util.Random;/*** @author 小工匠* @version v1.0* @create 2019-12-28 16:54* @motto show me the code ,change the word* @blog https://artisan.blog.csdn.net/* @description**/public class AgeCount {public static void main(String[] args) throws IOException {// 模擬文件simulatorAgeFile();String fileName = "D:\\age.txt";long start = System.currentTimeMillis();// 讀取文件 逐行讀取InputStreamReader inputStreamReader = new InputStreamReader(new FileInputStream(fileName),"utf-8");BufferedReader bufferedReader = new BufferedReader(inputStreamReader);int[] age = new int[500];int total = 0 ;String line = null;while( (line = bufferedReader.readLine()) != null){ // 時間復雜度 O(n)int index = Integer.valueOf(line) ;age[index]++ ; // 年齡累加total++ ; // 總量累加}//估算下時間： O(n) 14億數據. 最差的CPU也得 100萬/秒 *1000 = 10億 100~1000s之間 => 500s以下 60*8=480sSystem.out.println("總共的數據大小: " + total);for(int i = 0 ; i < 200 ; i ++){//下標從0開始的System.out.println(i + ":" + age[i]);}//124306ms => 124秒System.out.println("計算花費的時間為:" + (System.currentTimeMillis() - start) + "ms");}public static void simulatorAgeFile() throws IOException {final String fileName = "d:\\age.txt";final Random random = new Random();BufferedWriter objWriter = null;objWriter = new BufferedWriter(new OutputStreamWriter(new FileOutputStream(fileName)));for (int i = 0; i < 1400000000; i++) {// 0 - 200 隨機整數int age = (int) (Math.random() * 100 * 2);objWriter.write(age + "\r\n");}objWriter.flush();objWriter.close();} }14億 ， 125秒統計完畢
總結
以上是生活随笔為你收集整理的Algorithms_基础数据结构(01)_线性表之数组数组的应用案例分析的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Algorithms_算法专项_Bitm
- 下一篇： Algorithms_基础数据结构(02