陣列
隨機訪問
- 陣列是一種線性表資料結構，用一組連續的記憶體空間，來存盤同一型別的資料
- 線性表：資料排成線一樣的結構，最多只有前和后兩個方向
- 資料、堆疊、佇列、鏈表都是線性表結構
- 堆、圖、二叉樹等資料之間不具有簡單前后關系的結構，所以是非線性表結構
- 隨機訪問
- 在連續的地址空間存相同型別的資料，這兩個限制使陣列具有隨機訪問的特性，但是在插入、洗掉時，為了保證資料連續性，需要做大量的資料搬移操作，影響性能
- 隨機訪問時間復雜度為 O(1)
- 如何實作通過下標訪問資料
例如，int[] a = new int[10] 申請長度為10的陣列，首地址為1000，連續記憶體空間為1000~1039
每個
int型別占4個位元組，每個記憶體地址上可以存入1個位元組，所以知道首地址便可以推出后續其他地址計算公式：a[i]_address = base_address + i * data_type_size
低效的插入洗掉
- 插入
- 在陣列中插入資料，需要移位操作
- 平均時間復雜度為 O(n)，最好 O(1)，最壞 O(n)
- 如果不要求陣列有序，只當作存盤資料的集合，可以直接把第 k 位移到尾部，然后插入第 k 位
- 洗掉
- 在陣列中洗掉資料，需要移位操作
- 平均時間復雜度為 O(n)，最好 O(1)，最壞 O(n)
- 為了避免連續洗掉造成連續搬移，可以將觸發洗掉操作的資料記下來，待空間不夠時，集中進行搬移
為何從 0 開始編號
- 從陣列的記憶體模型來看，“下標“最準確的定義應該位”偏移“，a[0] 為偏移為 0 的位置，即首地址，計算 a[i] 的地址需要：a[i]_address = base_address + i * data_type_size，從 1 開始編號需要多做一次減法運算
- 歷史原因：C 語言設計者用 0 開始標記陣列下標，后來的高級語言沿用了此習慣
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/90052.html
標籤：其他
上一篇：重建二叉樹