數據結構與算法學習筆記之 從0編號的數組

前言

數組看似簡單，但掌握精髓的卻沒有多少；他既是編程語言中的數據類型，又是最基礎的數據結構；

一個小問題：

　為什么數據要從0開始編號，而不是 從1開始呢？

正文

帶著問題進入學習

如何實現隨機訪問？

什么是數組？

數組（array）是一種線性表數據結構，它用一組連續的內存空間來儲存一組具有相同類型的數據。

我們從定義來分析：

?

線性表：

是數據排成像一條線一樣的結構。每個線性表上的數據最多有前后兩個方向。諸如數組，鏈表，隊列，棧等都是線性表結構。

?

連續的內存空間和相同類型的數據：

這個特性是數組“隨機訪問”速度飛快的緣由，這也導致了從數組中刪除、插入數據，為了保證連續性，需要大量的工作量

?

計算機會給每個內存單元分配一個地址，計算機通過地址來訪問內存中的數據。

當計算機隨機訪問數組中的某個元素時，它會首先通過下面的尋址公式，計算出該元素的內存地址：

a[i]_address?=?base_address?+?i?*?data_type_size

data_type_siza表示數組中的每一個元素的大小。如果是int類型的數據，data_type_size為4個字節；

數組和鏈表的區別

鏈表適合插入、刪除，時間復雜度為O（1），數組適合查找，但是這里要注意一下，時間復雜度并不是O（1），即便是排好序的數組，你用二分法查找，時間復雜度也是O（logn），

正確的描述為:數組支持隨機訪問，根據下標隨機訪問的時間復雜度為O（1）

?

低效的“插入”“刪除”

插入操作

假設數組的長度為 n，現在，如果我們需要將一個數據插入到數組中的第 k 個位置，為了把第 k 個位置騰出來，給新來的數據，我們需要將第 k～n 這部分的元素都順序地往后挪一位，下面我們分析一下時間復雜度

如果在數組的末尾插入元素，那就不需要移動數據了，這時的時間復雜度為 O(1)，但如果在數組的開頭插入元素，那所有的數據都需要依次往后移動一位，所以最壞時間復雜度是 O(n)，因為我們在每個位置插入元素的概率是一樣的，所以平均情況時間復雜度為 (1+2+…n)/n=O(n)

如果數組中的數據是有序的，我們在某個位置插入一個新的元素時，就必須按照剛才的方法搬移 k 之后的數據，如果數組中存儲的數據并沒有任何規律，數組只是被當作一個存儲數據的集合。在這種情況下，如果要將某個數組插入到第 k 個位置

為了避免大規模的數據搬移，我們還有一個簡單的辦法就是

直接將第 k 位的數據搬移到數組元素的最后，把新的元素直接放入第 k 個位置。

?

刪除操作

和插入類似，

如果刪除數組末尾的數據，最好情況時間復雜度為 O(1)；

如果刪除開頭的數據，則最壞情況時間復雜度為 O(n)；

平均情況時間復雜度也為 O（n）

?

提高效率：

將多次刪除操作中集中在一起執行，可以先記錄已經刪除的數據，但是不進行數據遷移，而僅僅是記錄，當發現沒有更多空間存儲時，再執行真正的刪除操作。這也是 JVM 標記清除垃圾回收算法的核心思想。

?

數組訪問越界問題

C語言中的數據越界是一種未決行為，一般比較難發現的邏輯錯誤。相比之下，Java會有越界檢查。

?

用數組還是容器？

數組先指定了空間大小，容器如ArrayList可以動態擴容。

1.希望存儲基本類型數據，可以用數組

2.事先知道數據大小，并且操作簡單，可以用數組
3.直觀表示多維，可以用數組
4.業務開發，使用容器足夠，開發框架，追求性能，首先數組。

?

為什么數組要從 0 開始編號？

由于數組是通過尋址公式，計算出該元素存儲的內存地址：
a[i]_address = base_address + i * data_type_size
如果數組是從 1 開始計數，那么就會變成：
a[i]_address = base_address + （i-1）* data_type_size

?

以上內容為個人的學習筆記，僅作為學習交流之用。

?

歡迎大家關注公眾號，不定時干貨，只做有價值的輸出

作者：Dawnzhang?
出處：https://www.cnblogs.com/clwydjgs/p/9755971.html

版權：本文版權歸作者
轉載：歡迎轉載，但未經作者同意，必須保留此段聲明；必須在文章中給出原文連接；否則必究法律責任

小舟從此逝，江海寄余生。 --狐貍