iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 6
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...等等。有興趣的朋友可以自己去查查看。

寫到後來其實已經有點頭昏昏的了,如果有什麼錯誤的地方,還請留言告訴我,謝謝。


上一篇
[演算法] 列舉法 (Enumeration)
下一篇
[資料結構] 堆疊 (Stack)
系列文
30天學演算法和資料結構31

尚未有邦友留言

立即登入留言