數據結構與演算法(二)數組

• 2019 年 10 月 8 日
• 筆記

數組：

在堆中連續開闢的一段空間，每個元素佔有相同大小的空間。一經開闢，即固定大小，無法改變長短。

對數組如何增刪查改

插入

public void insetAtIndex(int index, int element) {    cheakRange(index); // 檢查插入的是否超過數組開闢範圍    cheakCapicity(); // 看是否需要擴容      for (int i = size; i > index; i--) {      elementDatas[i] = elementDatas[i - 1];    }    elementDatas[index] = element;  }

數組的插入操作 效率很低 如果數組長度特別大，在首部附近插入數據，將會把幾乎所有的數組數組都要向後移動。

刪除

public int removeAtIndex(int index) {    // 檢查刪除的是否超過數組開闢範圍    cheakRange(index);      int old = elementDatas[index];    for (int i = index + 1; i < size; i++) {      elementDatas[i - 1] = elementDatas[i];    }    //清空最後的空間  	elementDatas[index] = null;  }

查詢

通過角標偏移就可以找到對應的數組。由於記憶體地址是連續的 所查數據只要是(查找數據index*偏移量)。

public int get(int index) {  	// 判斷查找的是否在範圍內  		cheakRange(index);  		return elementDatas[i];  }

替換

在查找的基礎上直接替換就可以

elementDatas[i] = element;

• 優點：查找,替換快
• 缺點：插入刪除效率低

注意:在數組增刪查改的時候，要判斷是否在數組範圍內操作。

在增加的時候，如果超過數組開闢空間範圍，要對數組進行擴容：重新創建一個更大的數組，再將舊數組內容拷貝過去，再進行操作。