初識數(shù)據(jù)結(jié)構(gòu)

葉鵬　沈曉恬

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

悟空想起菩提老祖的教導(dǎo)，默默定義一個變量a，并將1+1賦值給此變量，隨后調(diào)用print（a）函數(shù)將結(jié)果輸出。

[a=1+1

print（a） ]

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

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

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

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

[# 第一個注釋

# 第二個注釋

'''

第三個注釋

第四個注釋

'''

"""

第五個注釋

第六個注釋

"""

print （"Hello， Python！"） ]

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

內(nèi)存和數(shù)據(jù)結(jié)構(gòu)

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

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

悟空脫口而出：“俺滴個乖乖，320億，居然這么多。”

菩提老祖發(fā)出一陣笑聲，“你這個沒見識的猢猻，零壹天尊的內(nèi)存至少是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是內(nèi)存中的最小單位，稱為位。每位中只能存放0或1這兩個值之一。”

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

說著，菩提老祖又揮了揮袖子。下一刻，悟空回轉(zhuǎn)到之前的禪房中。菩提老祖繼續(xù)說道：“你才剛剛上路。”

不服輸?shù)暮镒酉氲街灰约旱膬?nèi)存翻倍80次就能趕上零壹天尊，頓時覺得前途一片光明。

“為了應(yīng)付更復(fù)雜的情況，你內(nèi)存中的數(shù)據(jù)，需要進(jìn)行組織，在此界，我們將數(shù)據(jù)的組織形式和存儲方法稱為數(shù)據(jù)結(jié)構(gòu)。常用的數(shù)據(jù)結(jié)構(gòu)主要包括線性結(jié)構(gòu)和非線性結(jié)構(gòu)，非線性結(jié)構(gòu)中又包含樹結(jié)構(gòu)和圖結(jié)構(gòu)。”

線性結(jié)構(gòu)

線性結(jié)構(gòu)是最基本也是最簡單的一種數(shù)據(jù)結(jié)構(gòu)，它是由若干個數(shù)據(jù)元素構(gòu)成的有限序列。

線性結(jié)構(gòu)的特征是：

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

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

3.除最后元素外，其他數(shù)據(jù)元素都有唯一的后繼元素

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

線性結(jié)構(gòu)按不同的物理存儲方式可分成順序表和鏈表。

順序表在內(nèi)存中連續(xù)存儲數(shù)據(jù)。鏈表除了存儲數(shù)據(jù)，還包含指針，指針記錄了下一塊數(shù)據(jù)在內(nèi)存中的位置（地址）。

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

菩提老祖對悟空說：“既然你已經(jīng)懂了，那么我來考考你。你替我構(gòu)建一個結(jié)構(gòu)，并且要讓這個結(jié)構(gòu)實現(xiàn)下面的功能，越先進(jìn)入這個結(jié)構(gòu)的數(shù)據(jù)，越后才能被取出，這種結(jié)構(gòu)我們稱之為棧?！?p>

在程序中，我們通常只記錄某一個數(shù)據(jù)結(jié)構(gòu)的開始地址，而要取得這個結(jié)構(gòu)中任何一個數(shù)據(jù)時，我們需要通過一些方法來計算目標(biāo)數(shù)據(jù)的地址。

要建立一個棧，其實就是實現(xiàn)兩個方法：push（進(jìn)棧）和pop（出棧）。push方法是將新的值放到棧結(jié)構(gòu)的頂部，pop方法將獲得該結(jié)構(gòu)頂部元素的值。

悟空心想，我可以使用一個順序表來存儲變量，同時使用一個棧指針來表示棧結(jié)構(gòu)頂部元素的位置。在push時，指針加1，然后把新的值存在新的頂部位置。在pop時，根據(jù)指針，得到頂部元素的值，然后位置減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

# 返回棧頂?shù)脑?/p>

n-=1

return stack[n]

]

悟空建立棧之后，問菩提老祖：“師父，既然有一種結(jié)構(gòu)是先進(jìn)后出的，那么是不是還有一種結(jié)構(gòu)是先進(jìn)先出的呢？”

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

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

“這種結(jié)構(gòu)叫作隊列。悟空，那么你覺得隊列這種結(jié)構(gòu)，應(yīng)該用數(shù)組還是鏈表來實現(xiàn)呢？”

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

菩提老祖點點頭：“以后你有機(jī)會，也試著去實現(xiàn)一下吧！”

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

非線性結(jié)構(gòu)

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

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

在現(xiàn)實世界中，有些復(fù)雜的情況，線性結(jié)構(gòu)有時難以勝任。一些數(shù)據(jù)之間，存在著一對多的關(guān)系，這就構(gòu)成了所謂的樹狀結(jié)構(gòu)，簡稱樹。

與線性結(jié)構(gòu)不同，樹采用非線性結(jié)構(gòu)組織數(shù)據(jù)。

直觀地看，樹結(jié)構(gòu)組織起來的數(shù)據(jù)應(yīng)該有層次關(guān)系。我們真實的世界中，這類特性的數(shù)據(jù)應(yīng)用十分廣泛。

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

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

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

“還有一種更復(fù)雜的結(jié)構(gòu)，被稱為圖?！?/p>

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

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

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

鄰接矩陣?yán)脙蓚€數(shù)組來存儲一個圖，一個一維數(shù)組表示圖的各個頂點，一個二維數(shù)組表示頂點間的關(guān)系。

鄰接表利用數(shù)組和鏈表來存儲一個圖。使用一個一維數(shù)組表示圖的各個頂點，每個頂點有一個對應(yīng)的鏈表，用來表示由這個頂點發(fā)出的邊。對于邊數(shù)比較少的圖而言，更適合用鄰接表的存儲結(jié)構(gòu)。

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

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

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

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

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