本文的最新版本位于：https://github.com/iwhales/algorithms_notes
轉(zhuǎn)載請(qǐng)注明出處：http://www.reibang.com/u/5e6f798c903a
參考：《數(shù)據(jù)結(jié)構(gòu)（Python 語言描述）》- 第4章 數(shù)組和鏈表
在編程語言中，最常用來實(shí)現(xiàn)集合(collection)的兩種數(shù)據(jù)結(jié)構(gòu)是數(shù)組和鏈表結(jié)構(gòu)引润。這兩種類型的結(jié)構(gòu)采用不同的方法在計(jì)算內(nèi)存中存儲(chǔ)和訪問數(shù)據(jù)。也正是由于這些不同的方法蔗喂，導(dǎo)致了操作這兩種結(jié)構(gòu)的算法存在不同的時(shí)間/空間取舍。由此蜜葱，我們需要了解數(shù)據(jù)結(jié)構(gòu)胞皱，以明白不同的數(shù)據(jù)結(jié)構(gòu)對(duì)算法的影響。
本文內(nèi)容目錄如下掘譬，會(huì)分拆為兩篇筆記，另一則筆記是 "數(shù)組和鏈表結(jié)構(gòu)(python)_2"呻拌。
1. 術(shù)語
本節(jié)中的一些概念并非特定于 Python葱轩，比如 Python 中并沒有類似于 C/C++ 中的數(shù)組(array)類型，所以在看到這些類型時(shí)藐握，請(qǐng)以 C/C++ 的視角進(jìn)行思考靴拱。
"數(shù)據(jù)結(jié)構(gòu)"和"具體數(shù)據(jù)類型(CDT)"這兩個(gè)術(shù)語，指的是集合的數(shù)據(jù)(collection's data)的內(nèi)部表示——集合是一種抽象數(shù)據(jù)類型(ADT)猾普。比如對(duì)于棧(stack)這種 ADT 集合袜炕，在其內(nèi)部可使用數(shù)組或鏈存儲(chǔ)數(shù)據(jù)，那么此時(shí)討論的"數(shù)據(jù)結(jié)構(gòu)"和"具體數(shù)據(jù)類型(CDT)"便是針對(duì)數(shù)組或鏈表進(jìn)行的初家。另外偎窘，隨著視角的變換也可將 ADT 集合直接視作"數(shù)據(jù)結(jié)構(gòu)"乌助，比如我們常說棧是一種先進(jìn)后出的數(shù)據(jù)結(jié)構(gòu)，便是在思考棧這種"數(shù)據(jù)結(jié)構(gòu)"的特征评架，而非是在討論棧內(nèi)部數(shù)據(jù)元素具體采用的"數(shù)據(jù)結(jié)構(gòu)"眷茁。
1.1 數(shù)據(jù)結(jié)構(gòu)
數(shù)據(jù)結(jié)構(gòu)(data structure)是一種組織和存儲(chǔ)數(shù)據(jù)的方式，它包含了數(shù)據(jù)值的集合纵诞、數(shù)據(jù)間的關(guān)系，以及可應(yīng)用于數(shù)據(jù)之上函數(shù)或操作培遵。常見數(shù)據(jù)結(jié)構(gòu)如：數(shù)組浙芙、鏈表、棧籽腕、隊(duì)列嗡呼。
下圖展示了哈希表(hash table)的數(shù)據(jù)結(jié)構(gòu)：
Tips：為什么數(shù)組即是數(shù)據(jù)結(jié)構(gòu)，又是數(shù)據(jù)類型皇耗？ 數(shù)據(jù)結(jié)構(gòu)是一種解決問題的思路南窗，而數(shù)據(jù)類型是這種思路的具體實(shí)現(xiàn)。在討論"數(shù)據(jù)結(jié)構(gòu)"時(shí)郎楼，我們是在研究這種結(jié)構(gòu)的具體特性万伤，比如使用了連續(xù)的內(nèi)存、支持隨機(jī)訪問等呜袁；在討論數(shù)據(jù)類型時(shí)敌买，我們是在討論這種類型使用方法，比如支持索引操作阶界。
1.2 具體數(shù)據(jù)類型
具體數(shù)據(jù)類型(Concrete Data Type芙粱，CDT)是 ADT 的實(shí)際實(shí)現(xiàn)方式，比如棧(ADT 類型)可由數(shù)組(CDT 類型)實(shí)現(xiàn)氧映。數(shù)組(array)春畔、鏈表(linked list)和樹(tree) 均屬于 CDT，它們都是基本數(shù)據(jù)結(jié)構(gòu)屯耸，通常由計(jì)算機(jī)語言提供拐迁。
參考： Examples of Concrete and Abstract Data Types Concrete data type vs Abstract data type (data structures)
1.3 抽象數(shù)據(jù)類型
抽象數(shù)據(jù)類型(Abstract Data Type，ADT)不單純是一組值的集合疗绣，還包括作用在值集上的操作的集合线召，在"構(gòu)造數(shù)據(jù)類型(Structured data types)"的基礎(chǔ)上同時(shí)增加了對(duì)數(shù)據(jù)的操作，并且類型的表示細(xì)節(jié)及操作的實(shí)現(xiàn)細(xì)節(jié)對(duì)外是不可見得——在 C 語言中多矮，構(gòu)造數(shù)據(jù)類型包括 數(shù)組(array)缓淹、結(jié)構(gòu)體(struct)哈打、聯(lián)合體 (union)、枚舉(enum)讯壶。
之所以命名為抽象數(shù)據(jù)類型料仗，就是因?yàn)橥獠恐恢浪鍪裁矗恢浪绾巫龇茫恢罃?shù)據(jù)的內(nèi)部表示細(xì)節(jié)立轧。 這樣，即使改變數(shù)據(jù)的表示和操作的實(shí)現(xiàn)躏吊，也不會(huì)影響程序的其他部分谆沃。抽象數(shù)據(jù)類型可達(dá)到更好的信息隱藏效果拓哺，因?yàn)樗钩绦虿灰蕾囉跀?shù)據(jù)結(jié)構(gòu)的具體實(shí)現(xiàn)方法校读，只要提供相同的操作账月，換用其他方法實(shí)現(xiàn)時(shí)，程序無需修改赁项，這個(gè)特征對(duì)于系統(tǒng)的維護(hù)很有利葛躏。
同一個(gè)數(shù)據(jù)結(jié)構(gòu)可以實(shí)現(xiàn)為 1 或多個(gè)抽象數(shù)據(jù)類型。比如悠菜，哈希表這種數(shù)據(jù)結(jié)構(gòu)舰攒，便可能由于哈希函數(shù)的不同而產(chǎn)生不同的實(shí)現(xiàn)，從而形成多個(gè)不同的抽象數(shù)據(jù)類型李剖。棧(stack)芒率、隊(duì)列(queue)和堆(heap) 也屬于抽象數(shù)據(jù)結(jié)構(gòu)。
要實(shí)現(xiàn)某個(gè) ADT 必須以某個(gè)恰當(dāng)?shù)?CDT 為基礎(chǔ)篙顺，進(jìn)行實(shí)現(xiàn)偶芍。比如，棧和隊(duì)列可以由數(shù)組或鏈表實(shí)現(xiàn)德玫；堆可以由數(shù)組或二叉樹(binary tree)實(shí)現(xiàn)匪蟀。
2. 數(shù)組數(shù)據(jù)結(jié)構(gòu)
Array Data Structure
由于在許多編程語言中，集合中的實(shí)現(xiàn)結(jié)構(gòu)主要是數(shù)組宰僧，而不是列表材彪。因此，我們需要熟悉用數(shù)組的方式來思考問題琴儿，本節(jié)內(nèi)容就是在要幫助我們了解如何利用數(shù)組實(shí)現(xiàn)集合段化，以及對(duì)部分操作進(jìn)行復(fù)雜度分析。
Python 的 array 模塊雖提供了 array 類造成，但該類與其它編程語言中的數(shù)組存在很大的區(qū)別显熏，其行為更類似于列表，而且僅能存儲(chǔ)數(shù)值晒屎。因此喘蟆，為了討論數(shù)組數(shù)據(jù)結(jié)構(gòu)缓升，我們將自定義一個(gè) Array 類(下文中提及的數(shù)組都特指該自定義類)，具體定義如下：
"""
File: arrays.py
An Array is a restricted list whose clients can use
only [], len, iter, and str.
To instantiate, use
<variable> = array(<capacity>, <optional fill value>)
The fill value is None by default.
"""
class Array(object):
"""Represents an array."""
def __init__(self, capacity, fillValue = None):
"""Capacity is the static size of the array.
fillValue is placed at each position."""
self._items = list()
for count in range(capacity):
self._items.append(fillValue)
def __len__(self):
"""-> The capacity of the array."""
return len(self._items)
def __str__(self):
"""-> The string representation of the array."""
return str(self._items)
def __iter__(self):
"""Supports iteration over a view of an array."""
return iter(self._items)
def __getitem__(self, index):
"""Subscript operator for access at index."""
return self._items[index]
def __setitem__(self, index, newItem):
"""Subscript operator for replacement at index."""
self._items[index] = newItem
2.1 隨機(jī)訪問和連續(xù)內(nèi)存
計(jì)算機(jī)通過為數(shù)組分配一段連續(xù)的內(nèi)存單位蕴轨，從而支持對(duì)數(shù)組的隨機(jī)訪問港谊。
索引操作便屬于隨機(jī)訪問，其步驟如下：
- 獲取數(shù)組內(nèi)存塊的基本地址——數(shù)組第1項(xiàng)的機(jī)器地址
- 給這個(gè)地址加上索引橙弱，返回最終結(jié)果歧寺。
2.2 物理尺寸和邏輯尺寸
物理尺寸：表示數(shù)組的最大容量，就是在創(chuàng)建數(shù)組時(shí)用于指定數(shù)組容量的數(shù)值棘脐。
邏輯尺寸：表示在數(shù)組中已填充了多少項(xiàng)成福。如果邏輯尺寸為了0，則表示數(shù)組為空荆残；如果邏輯尺寸不為 0，則最后一項(xiàng)的索引為邏輯尺寸減 1净当。
在操作數(shù)組時(shí)内斯，由程序員負(fù)責(zé)記錄數(shù)組的邏輯尺寸和物理尺寸。 邏輯尺寸和物理尺寸的比值被稱作數(shù)組的裝載因子(load factor)像啼，
2.3 數(shù)組的操作
這一節(jié)會(huì)在數(shù)組上實(shí)現(xiàn)幾種常見操作俘闯，這些操作數(shù)組的方法應(yīng)位于包含數(shù)組的集合中，集合利用這些方法操作其內(nèi)部的數(shù)組忽冻。分析這些常見操作的目的是為了解其運(yùn)行時(shí)間的復(fù)雜度真朗，以便在利用不同的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)集合時(shí)，可以有效對(duì)比不同數(shù)據(jù)結(jié)構(gòu)間的優(yōu)劣僧诚。
本節(jié)之后的示例中遮婶，會(huì)假設(shè)存在如下初始數(shù)據(jù)設(shè)置：
class ListCollection(object):
DEFAULT_CAPACITY = 5 # 默認(rèn)容量
def __init__(self):
self.logical_size = 0 # 邏輯尺寸
self._array = Array(ListCollection.DEFAULT_CAPACITY)
# --snip--
a. 增加數(shù)組的尺寸
當(dāng)插入新的項(xiàng)時(shí)，數(shù)組的邏輯尺寸等于物理尺寸湖笨，便需要增加數(shù)組的尺寸旗扑。
def increase_size(self):
if self.logical_size == len(self._array):
temp = Array(len(self._array)+1)
for i in range(self.logical_size):
temp[i] = self._array[i]
self._array = temp
# 舊數(shù)組的內(nèi)存留給垃圾回收程序處理
采用上述代碼增加數(shù)組尺寸時(shí)，復(fù)制操作的次數(shù)是線性的 O(n) 慈省。如果需要給數(shù)組添加 n 項(xiàng)臀防，那么整體的時(shí)間性能是 n(n+1)/2 ，即 O(n^2) 边败「ぶ裕考慮下述方案，每次將數(shù)組大小翻倍笑窜，從而將整體時(shí)間性能優(yōu)化為 O(log_2n) 致燥，但這樣做會(huì)以浪費(fèi)內(nèi)存為代價(jià)。
temp = Array(len(a_array)*2)
b. 減少數(shù)組的尺寸
當(dāng)數(shù)組的邏輯尺寸小于某個(gè)閾值時(shí)怖侦，就應(yīng)當(dāng)縮小其物理尺寸篡悟，以避免浪費(fèi)大量內(nèi)存谜叹。
def decrease_size(self):
if self.logical_size <= len(self._array)//4 and \
len(self._array) >= ListCollection.DEFAULT_CAPACITY*2:
temp = Array(len(self._array)//2)
for i in range(self.logical_size):
temp[i] = self._array[i]
self._array = temp
c. 在數(shù)組中插入一項(xiàng)
def insert_item(self, target_index, target_item):
self.increase_size() # 檢查是否需要增加數(shù)組尺寸
# 從最后一項(xiàng)開始以逐個(gè)向后移動(dòng)
for i in range(self.logical_size, target_index, -1):
self._array[i] = self._array[i-1]
self._array[target_index] = target_item
self.logical_size += 1
在插入過程中，移動(dòng)項(xiàng)的時(shí)間性能在平均情況下是線性的搬葬，因此荷腊，插入操作的時(shí)間性能是線性的。
e. 從數(shù)組中刪除一項(xiàng)
def remove_item(self, target_index, target_item):
# 從目標(biāo)項(xiàng)之后的一項(xiàng)開始急凰，逐個(gè)向前移動(dòng)
for i in range(target_index, self.logical_size-1):
self._array[i] = self._array[i+1]
self.logical_size -= 1
# 檢測是否需要減少物理尺寸
self.decrease_size()
由于移動(dòng)一項(xiàng)的事件性能平均是線性的女仰，因此，刪除操作的時(shí)間性能是線性的抡锈。
2.4 復(fù)雜度分析
下表給出了數(shù)組操作的運(yùn)行時(shí)間：
| 操作 | 運(yùn)行時(shí)間 |
|---|---|
| 訪問第 i 個(gè)位置的元素 | O(1)疾忍，最好情況和最壞情況 |
| 替換第 i 個(gè)位置的元素 | O(1)，最好情況和最壞情況 |
| 從邏輯末尾插入 | O(1)床三，平均情況 |
| 從邏輯末尾刪除 | O(1)一罩，平均情況 |
| 在第 i 個(gè)位置插入 | O(n)，平均情況 |
| 從第 i 個(gè)位置刪除 | O(n)撇簿，平均情況 |
| 增加容量 | O(n)聂渊，最好情況和最壞情況 |
| 減小容量 | O(n)，最好情況和最壞情況 |
可見數(shù)組提供了對(duì)已經(jīng)存在的項(xiàng)的快速訪問四瘫，并且提供了在邏輯末尾位置的快速插入和刪除汉嗽。然而，在任意位置的插入和刪除可能會(huì)慢上一個(gè)量級(jí)找蜜。調(diào)整大小所需時(shí)間也是線性階饼暑，但是如果調(diào)整每次變化的倍率，則能夠優(yōu)化所需時(shí)間洗做。
2.5 完整示例
綜合上面的代碼弓叛，以下是利用數(shù)組實(shí)現(xiàn)集合的一個(gè)完整示例：
class ListCollection(object):
DEFAULT_CAPACITY = 5 # 默認(rèn)容量
def __init__(self):
self.logical_size = 0 # 邏輯尺寸
self._array = Array(ListCollection.DEFAULT_CAPACITY)
def increase_size(self):
if self.logical_size == len(self._array):
temp = Array(len(self._array)+1)
for i in range(self.logical_size):
temp[i] = self._array[i]
self._array = temp
# 舊數(shù)組的內(nèi)存留給垃圾回收程序處理
def decrease_size(self):
if self.logical_size <= len(self._array)//4 and \
len(self._array) >= ListCollection.DEFAULT_CAPACITY*2:
temp = Array(len(self._array)//2)
for i in range(self.logical_size):
temp[i] = self._array[i]
self._array = temp
def insert_item(self, target_index, target_item):
self.increase_size()
for i in range(self.logical_size, target_index, -1):
self._array[i] = self._array[i-1]
self._array[target_index] = target_item
self.logical_size += 1
def remove_item(self, target_index):
# 從目標(biāo)項(xiàng)之后的一項(xiàng)開始，逐個(gè)向前移動(dòng)
for i in range(target_index, self.logical_size-1):
self._array[i] = self._array[i+1]
self.logical_size -= 1
# 檢測是否需要減少物理尺寸
self.decrease_size()
def __len__(self):
# 邏輯長度
return self.logical_size
def __getitem__(self, item):
if item < self.logical_size:
return self._array[item]
def __setitem__(self, key, value):
self.increase_size()
self._array[key] = value
self.logical_size += 1
def __str__(self):
return str(self._array[:self.logical_size])
2.6 二維數(shù)組
利用之前定義的 Array 類竭望，可以構(gòu)建出二維數(shù)組 Grid 類邪码，代碼如下：
"""
File: grid.py
僅能使用 [], str, getHeight 和 getWidth, 不提供迭代器
"""
from 數(shù)組數(shù)據(jù)結(jié)構(gòu) import Array
class Grid(object):
"""Represents a two-dimensional array."""
def __init__(self, rows, columns, fillValue=None):
self._data = Array(rows)
for row in range(rows):
self._data[row] = Array(columns, fillValue)
def getHeight(self):
"""Returns the number of rows."""
return len(self._data)
def getWidth(self):
"Returns the number of columns."""
return len(self._data[0])
def __getitem__(self, index):
"""Supports two-dimensional indexing with [][]."""
return self._data[index]
def __str__(self):
"""Returns a string representation of the grid."""
result = ""
for row in range(self.getHeight()):
for col in range(self.getWidth()):
result += str(self._data[row][col]) + " "
result += "\n"
return result
def main():
g = Grid(10, 10, 1)
print(g)
# 重置二維列表
for row in range(g.getHeight()):
for column in range(g.getWidth()):
g[row][column] = row*10 + column
print(g)
if __name__ == "__main__":
main()
