初識數據結構

葉鵬　沈曉恬

只見菩提老祖大袖輕揮，悟空眼前的場景頓時變化，像是來到一處荒山。只見十幾米遠的地方有一塊巨石。有個小妖從巖石后蹦出。那小妖手握一根骨棒，嗷嗷叫著向悟空沖來。悟空默運火眼金睛，見小妖身后隱約有層黑霧，霧中凝結出一道題目：“1+1=？”

悟空想起菩提老祖的教導，默默定義一個變量a，并將1+1賦值給此變量，隨后調用print（a）函數將結果輸出。

[a=1+1

print（a） ]

隨著數字2在天地間閃現，那小妖頓時如遭雷擊，瞬間被打得灰飛煙滅。

悟空心想，這還挺簡單的嘛，有這個程序，加法類型的小妖是來多少滅多少。

“悟空，”菩提老祖打斷悟空的思路，將他的念頭拉回來，“Python和其他一些語言不同，它使用縮進來表示代碼塊，不需要使用大括號{}。縮進的空格數是可變的，但同一代碼塊的語句，必須包含相同的縮進空格數。通常每一行包含一條Python語句，語句結尾直接換行，不需要加分號。”

“另外，代碼中可以添加一些說明性文字，稱為注釋，Python中的單行注釋以#開頭，多行可以用多個#號，也可以用'''或者"""。注釋不會被執行，只是方便人們閱讀代碼?！?/p>

[# 第一個注釋

# 第二個注釋

'''

第三個注釋

第四個注釋

'''

"""

第五個注釋

第六個注釋

"""

print （"Hello， Python！"） ]

悟空點頭表示記下，這時的猴子已經算是入門了。

內存和數據結構

悟空默運火眼金睛，內視己身，發現自己的內存單元密密麻麻，不太數得清楚，便好奇地問菩提老祖：“師父，我現在到底有多少個內存單元呢？”

菩提老祖回答：“內存的最小單位叫作字節，西方的叫法是byte。你現在有32GB，大約320億個字節?！?/p>

悟空脫口而出：“俺滴個乖乖，320億，居然這么多?！?/p>

菩提老祖發出一陣笑聲，“你這個沒見識的猢猻，零壹天尊的內存至少是NB級別的，1NB=1024BB，1BB=1024YB，1YB=1024ZB，1ZB=1024EB，1EB=1024PB，1PB=1024TB，1TB=1024

GB，1GB=1024MB，1MB=1024KB，1KB=

1024Byte，1Byte=8bit。bit是內存中的最小單位，稱為位。每位中只能存放0或1這兩個值之一。”

悟空心里大概合計了下，暗道：“1NB大約等于十萬億億GB，差距有點大。怪不得這單位就叫NB?！?/p>

說著，菩提老祖又揮了揮袖子。下一刻，悟空回轉到之前的禪房中。菩提老祖繼續說道：“你才剛剛上路?！?/p>

不服輸的猴子想到只要自己的內存翻倍80次就能趕上零壹天尊，頓時覺得前途一片光明。

“為了應付更復雜的情況，你內存中的數據，需要進行組織，在此界，我們將數據的組織形式和存儲方法稱為數據結構。常用的數據結構主要包括線性結構和非線性結構，非線性結構中又包含樹結構和圖結構。”

線性結構

線性結構是最基本也是最簡單的一種數據結構，它是由若干個數據元素構成的有限序列。

線性結構的特征是：

[1.必定存在唯一的一個第一個元素

2.必定存在唯一的一個最后的元素

3.除最后元素外，其他數據元素都有唯一的后繼元素

4.除第一個元素外，其他元素都有唯一的前驅元素 ]

線性結構按不同的物理存儲方式可分成順序表和鏈表。

順序表在內存中連續存儲數據。鏈表除了存儲數據，還包含指針，指針記錄了下一塊數據在內存中的位置（地址）。

“懂了！”悟空興奮地大叫。

菩提老祖對悟空說：“既然你已經懂了，那么我來考考你。你替我構建一個結構，并且要讓這個結構實現下面的功能，越先進入這個結構的數據，越后才能被取出，這種結構我們稱之為棧?！?p>

在程序中，我們通常只記錄某一個數據結構的開始地址，而要取得這個結構中任何一個數據時，我們需要通過一些方法來計算目標數據的地址。

要建立一個棧，其實就是實現兩個方法：push（進棧）和pop（出棧）。push方法是將新的值放到棧結構的頂部，pop方法將獲得該結構頂部元素的值。

悟空心想，我可以使用一個順序表來存儲變量，同時使用一個棧指針來表示棧結構頂部元素的位置。在push時，指針加1，然后把新的值存在新的頂部位置。在pop時，根據指針，得到頂部元素的值，然后位置減1。

核心算法如下：

[def? push（i）：

global n

if n>=10：

print （"無法壓棧"）

return err

stack[n]=i

n+=1

def? pop（）：

global n

if n<1：

print （"無法出棧"）

return err

# 返回棧頂的元素

n-=1

return stack[n]

]

悟空建立棧之后，問菩提老祖：“師父，既然有一種結構是先進后出的，那么是不是還有一種結構是先進先出的呢？”

（入隊列叫enqueue，出隊列叫dequeue）

“不錯！” 菩提老祖的聲音中透出贊賞的意味。

“這種結構叫作隊列。悟空，那么你覺得隊列這種結構，應該用數組還是鏈表來實現呢？”

悟空撓撓腦袋，說道：“應該還是用鏈表來實現更好一些吧？之前我們講到數組和鏈表優缺點的時候，提到一系列屬性……所以更加適合鏈表吧？”

菩提老祖點點頭：“以后你有機會，也試著去實現一下吧！”

所以基本來說，從存儲形式來看，線性結構可以分為順序表和鏈表;而從邏輯功能來看，可以分為堆棧和隊列。

非線性結構

悟空不愧是靈明石猴出生，學起東西來確實有舉一反三的能耐。他繼續向菩提老祖發問：“師父，不管是棧還是隊列，都是一個接一個下來的，是否有更復雜一點的結構呢？我在看管蟠桃園的時候，見那些蟠桃樹，都是枝枝杈杈，甚是復雜?！?/p>

菩提老祖哈哈大笑：“你這猴頭，還是忘不了王母娘娘的蟠桃！此間確實有一種名為樹的結構，對你非常有用。來來來，我們再來研討一番?！?/p>

在現實世界中，有些復雜的情況，線性結構有時難以勝任。一些數據之間，存在著一對多的關系，這就構成了所謂的樹狀結構，簡稱樹。

與線性結構不同，樹采用非線性結構組織數據。

直觀地看，樹結構組織起來的數據應該有層次關系。我們真實的世界中，這類特性的數據應用十分廣泛。

用形式化的語言描述，樹是由n個結點（n≥0）組成的有窮集合。在任意一棵非空樹中，有且僅有一個稱為根（root）的結點;當n>1時，其余的結點分為m個互不相交的有限集合（m>0），T1，T2…Tm。其中，每個集合本身又是一棵樹，稱為根的子樹（subtree）。

樹結構的物理存儲形式很多，最簡單的一種被稱為多重鏈表。在多重鏈表中，每個結點由一個數據域和若干指針域組成，其中，每個指針指向該結點的一個子結點。

“這零壹之道真是了不起??！”悟空由衷地贊嘆道，“那么還有更厲害的結構嗎？”

“還有一種更復雜的結構，被稱為圖?！?/p>

“圖？這名字一聽就很厲害啊，如同太上老君的太極圖、通天教主的誅仙陣圖，都是能鎮壓大教氣運的寶貝。”悟空心道。

從之前的描述中，我們可以發現線性結構是一種前后關系，樹結構是一種層次關系，各個子樹互不相交。而圖結構中，任何兩個數據元素之間都可能存在關系。圖（Graph）是由頂點的非空有限集合V（由n>0個頂點組成），與邊的集合E（頂點之間的關系）所構成。如果圖G中每一條邊都沒有方向，稱為無向圖;若有方向，則稱為有向圖。

最常見的存儲方法有兩種：鄰接矩陣的存儲方法和鄰接表的存儲方法。

鄰接矩陣利用兩個數組來存儲一個圖，一個一維數組表示圖的各個頂點，一個二維數組表示頂點間的關系。

鄰接表利用數組和鏈表來存儲一個圖。使用一個一維數組表示圖的各個頂點，每個頂點有一個對應的鏈表，用來表示由這個頂點發出的邊。對于邊數比較少的圖而言，更適合用鄰接表的存儲結構。

講完圖的概念后，菩提老祖又傳授了悟空幾個基本的小法術，比如如何飛行、如何變化等。悟空默默記在心頭。

說完這些，菩提老祖道：“我在此界的時間有限，對于零壹之道的了解也已經基本傳授于你，剩下就靠你自己了。唐三藏一干人等目前身陷排序塔中，你速去解救眾人。日后你重回四大部洲，我們依然保持原來的關系吧！”說罷，身形如同青煙一般，緩緩消逝。

悟空大喊：“師父！師父！”

不出所料，他的聲音回蕩在這房間里，無人應答。悟空心想，當務之急，是將取經組眾人解救，然后從這零壹界中脫身。

掃一掃，有視頻課哦！學Python算法，看西游漫記