最新消息:XAMPP默认安装之后是很不安全的,我们只需要点击左方菜单的 "安全"选项,按照向导操作即可完成安全设置。

陣列 (Array) & 串列 (Linked List)

XAMPP下载 admin 606浏览 0评论
 其實資料在程式語言中有很多種型態,像是 int (integer), float, double, string, boolean, list, array…等等。當我們把各種型態的資料組還在一起,就變成很多很多的資料(廢話)~~ 像資料的集合,又有tuple, array, list, set, dic (dictionary), struct…等等等。

今天以 Python 為例,來討論 陣列 (Array) 和 串列 (Linked List)。

其實 Python 是從 C 語言演化而來。因為 C 語言對電腦來說算是低階語言,階層低表示對於電腦而言比較好理解,所以程式設計者為了理解電腦的運作,進而發展出了資料結構等很多東西。雖然之後演化出的各種語言,對於程式設計者有很多使用上的改變,但資料結構的東西是一種電腦運作的方式,概念和邏輯上大同小異。即使時代在演進,若要電腦的運作方式,了解資料結構還是很必要的。

註:語言階層的高底指的是對於人而言,編寫程式的理解度和複雜度,與電腦的理解方式則呈負相關。因為電腦最熟悉的語言是 0 跟 1 的排列組合,但是人不容易讀,所以才有 C、Python 等等的語言出現。人如果愈容易理解和編寫程式碼,則階層愈高,反之亦然。

回到今天的主題,在 Python 裏,同樣是陣列,但有 array 和 list 兩種數據類型。兩者的差異在於,前者屬於 Python 模組 numpy 裡的一種數據類型,所包含的所有元素類型都必須相同;而後者則是 Python 內建的數據類型,可以包含不同的元素類型。

numpy.array = [1, 2, 3, 4]
list = [1, 2, 3, ‘string’, (12, ‘hi’)]
那為什麼 list 可以包含不同的元素類型?它其實就像 C 語言裡的 指針(Pointer),保存的資料是數據存放的位置。因此不論 list 裡的元素型態是什麼,只要藉由讀取元素的位置,就可以獲取我們所存在 list 的資料。

回過頭來,那什麼是 串列 (Linked List)?這邊來看個例子。

Memory 0 1 2 3 4
Data 11 22 33 44 55
這是一串已經排序好的陣列。在 C 語言中的陣列,如果要插入一個資料,必須將資料的位置一個一個往後挪,把位置空出來,才能把資料放進去。假設要插入 18,勢必得把 11 後面的資料全部往後移一位。

Memory 0 1 2 3 4 5
Data 11   22 33 44 55
Memory 0 1 2 3 4 5
Data 11 18 22 33 44 55
但 C 語言有一種資料類型叫做 指標 (Pointer)。每一筆資料都有其存取在記憶體(Memory)的位置,指標就是用來讀取儲存位置的物件。我們可以藉由改變讀取記憶體位置的順序,來改變資料的排列。

假設原本指標讀取位置的順序是這樣:

Memory 0 1 2 3 4
想當然,輸出會是:

Data 11 22 33 44 55
但如果讀去位置的順序是:

Memory 3 1 4 0 2
輸出:

Data 44 22 55 11 33
但重點來了,list 在記憶體中的儲存空間是有連續性的,每一個位置都指向下一筆資料。對於已經存在記憶體中的資料,我們沒有辦法將資料全部刪除,就只為了空出位置給要插入的新資料。那我們要怎麼來改變讀取資料記憶體位置的順序?接下來我們用 Python 來示範。

全部的程式碼
data = [11, 22, 33, 44, 55, 66, 77, 88, 99, 100]
right = []
insert_num = 41
length = len(data)
# Initialization
for i in range(length):
right.append(0)

# 設定right來存放data中每一個節點右邊節點的位置
for i in range(length):
if i != length-1:
right[i] = i + 1
else:
right[i] = 0 # 0代表右邊沒節點

# data插入節點
data.append(insert_num)
right.append(0) # right增加位置給插入的節點存放右邊節點的位置資料
length = len(data)

# 從鏈結串列的頭部開始讀取
t = 0
for i in range(length):
#如果目前節點的下一個節點值大於待插入的數字,將數插入到中間
if data[right[t]] > data[length-1]:
#將目前節點的右邊位置給予新插入的節點存放在right
right[length-1] = right[t]
#將新插入節點的位置給到目前節點的right存放
right[t] = length-1
#跳出回圈
break

t = right[t]

#印出鏈結串列的所有數字
t = 0
tmp = []
for i in range(length):
tmp.append(data[t])
t = right[t]

print (tmp)
拉蒙碎碎念
其實如果仔細思考,如果插入的數字為 8 比第 0 位的數字還小,但實際結果卻是插不進去的。

#插入前
data = [11, 22, 33, 44, 55, 66, 77, 88, 99, 100, 8]
right = [1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 0]

#插入後
data = [11, 8, 22, 33, 41, 44, 55, 66, 77, 88, 99, 100]
right = [10, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1]
因為right所存放的只有連結到下一筆資料的位置,也就是右邊位置,卻沒有考慮到第 0 位本身自己的位置。因次程式碼其實可以再修改修改的。

以上的程式碼,其實是在模擬串列的運作。但實際上在 Python 中,有很多內建的function可以用,一樣也可以達到上述插入資料的效果。例如:append,pop,insert,remove…等等。有興趣的朋友可以自己去查查看。

转载请注明:XAMPP中文组官网 » 陣列 (Array) & 串列 (Linked List)

您必须 登录 才能发表评论!