算法中使用的數(shù)據(jù)結(jié)構(gòu)解釋
在算法的執(zhí)行過程中，需要有能夠容納臨時(shí)數(shù)據(jù)的內(nèi)存數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)的有效實(shí)施需要選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)。迭代或遞歸算法需要專門為其邏輯設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)。
也有人表述為容器，存放數(shù)據(jù)的容器。
在遞歸算法的情況下，嵌套的數(shù)據(jù)結(jié)構(gòu)可以促進(jìn)其實(shí)現(xiàn)并提高其性能。本文將結(jié)合數(shù)據(jù)結(jié)構(gòu)來討論算法。本文的重點(diǎn)是Python數(shù)據(jù)結(jié)構(gòu)，因?yàn)槲覀儗⒃谡麄€(gè)文章中使用Python。然而，本文介紹的概念也可以應(yīng)用于其他語言，如Java和C++。
在這篇文章中，你應(yīng)該了解Python如何處理復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，以及哪一種結(jié)構(gòu)應(yīng)該用于特定類型的數(shù)據(jù)。
在這篇文章中，將討論以下幾點(diǎn)。
使用Python來探索數(shù)據(jù)結(jié)構(gòu)
對(duì)抽象數(shù)據(jù)類型的探索
隊(duì)列和堆棧
樹
Python數(shù)據(jù)結(jié)構(gòu)的探索
在任何編程語言中，數(shù)據(jù)結(jié)構(gòu)都是用來存儲(chǔ)和處理復(fù)雜數(shù)據(jù)的。Python中的數(shù)據(jù)結(jié)構(gòu)是用于有效管理、組織和搜索數(shù)據(jù)的容器。它們被用來存儲(chǔ)和處理被稱為集合的數(shù)據(jù)元素組。以下五個(gè)數(shù)據(jù)結(jié)構(gòu)可以用來在 Python 中存儲(chǔ)集合。
一個(gè)可以變異的有序元素序列
以不可變的方式排序的元素序列
集合的元素是無序的
字典將鍵值對(duì)定義為無序的包
數(shù)據(jù)框是一個(gè)用于存儲(chǔ)二維數(shù)據(jù)的二維結(jié)構(gòu)
在下面的小節(jié)中，我們將更詳細(xì)地探討它們。
列表
列表是 Python 的主要數(shù)據(jù)結(jié)構(gòu)，用于存儲(chǔ)可變?cè)?。一個(gè)列表不一定要包含相同類型的數(shù)據(jù)元素。
有必要用 [ ] 包圍列表中的元素，并用逗號(hào)將它們分開。例如，這段代碼一起創(chuàng)建了四個(gè)不同類型的數(shù)據(jù)元素。
[圖片上傳失敗...(image-e3bc07-1667467474169)]
在 Python 中，列表對(duì)于創(chuàng)建一維的可寫數(shù)據(jù)結(jié)構(gòu)是很有用的，在算法開發(fā)的不同階段都需要。
列表
列表可以使用數(shù)據(jù)結(jié)構(gòu)中的實(shí)用函數(shù)進(jìn)行管理，這使得它們非常有用。****為了利用它們，讓我們考慮以下情況。
有可能通過使用列表的索引來獲得某個(gè)特定位置的元素，因?yàn)榱斜碇性氐奈恢檬谴_定的。這個(gè)概念的演示可以在下面的代碼中找到。
這段代碼生成了一個(gè)四元素的列表，如下面的屏幕截圖所示。
[圖片上傳失敗...(image-fe3f43-1667467474169)]
因?yàn)樗饕龔?開始，所以用索引1檢索綠色，即bin_color[1]。
一個(gè)列表可以通過指定一個(gè)索引范圍來切分，以便檢索其元素的一個(gè)子集。你可以用下面的代碼創(chuàng)建一個(gè)列表的片斷。
Python 的 list 數(shù)據(jù)結(jié)構(gòu)是****最流行的單維數(shù)據(jù)結(jié)構(gòu)之一****。
在對(duì)列表進(jìn)行切片的過程中，范圍表示如下：
[圖片上傳失敗...(image-d3f4af-1667467474175)]
第一個(gè)數(shù)字（包括）和第二個(gè)數(shù)字（排除）
類似地bin_colors[0:2] 包含 bin_color[0] 和 bin_color[1]，但不包含 bin_color[2]
由于一些 Python 用戶抱怨列表不直觀，在使用它們時(shí)應(yīng)該記住這一點(diǎn)。****這里有一段代碼，你可能會(huì)覺得很有用。
如果沒有指定起始或結(jié)束索引，列表將從頭開始，如果都沒有指定索引，列表將在結(jié)束時(shí)結(jié)束。從前面的代碼可以看出，這個(gè)概念實(shí)際上已經(jīng)被證明了。
[圖片上傳失敗...(image-be5c99-1667467474175)]
在 Python 中也可以有負(fù)的索引，從列表的末端開始計(jì)算。下面是一個(gè)說明這一點(diǎn)的代碼例子。
當(dāng)我們想引用最后一個(gè)元素而不是第一個(gè)元素時(shí)，負(fù)指數(shù)特別有用。
[圖片上傳失敗...(image-efa171-1667467474174)]
列表中有兩種類型的嵌套：簡單和復(fù)雜。列表的嵌套是通過這個(gè)功能實(shí)現(xiàn)的。在迭代和遞歸算法的情況下，這提供了重要的能力。
考慮下面的代碼例子，它顯示了一個(gè)列表中的一個(gè)列表 (嵌套)。
[圖片上傳失敗...(image-ec1e53-1667467474169)]
在 Python 中，一個(gè) for 循環(huán)可以用來遍歷一個(gè)列表的每個(gè)元素。下面可以看到一個(gè)例子。****通過迭代前面的代碼，列表中的每個(gè)元素都被打印出來。
[圖片上傳失敗...(image-d8efad-1667467474174)]
Lambda中的函數(shù)
Lambda函數(shù)可以以多種方式應(yīng)用于列表。在算法的背景下，它們特別重要，因?yàn)樗鼈兲峁┝丝焖賱?chuàng)建函數(shù)的能力。它們有時(shí)在文獻(xiàn)中被稱為匿名函數(shù)。下面的例子展示了如何使用它們。
過濾數(shù)據(jù)的第一步是定義一個(gè)謂詞，這是一個(gè)接受單個(gè)參數(shù)并返回一個(gè)布爾值的函數(shù)。在下面的代碼中可以找到它的使用示范。
[圖片上傳失敗...(image-b448b9-1667467474174)]
使用lambda函數(shù)來過濾一個(gè)列表，我們?cè)谶@段代碼中指定過濾標(biāo)準(zhǔn)?；诙x的標(biāo)準(zhǔn)，過濾函數(shù)從一個(gè)序列中過濾元素。在 Python 中，它通常與 lambda 結(jié)合使用過濾函數(shù)。此外，圖元和集合也可以用它來過濾。x > 100是前面代碼中定義的標(biāo)準(zhǔn)。****列表中的所有元素將被遍歷，任何未能通過這個(gè)過濾器的元素將被刪除。
Lambda函數(shù)可用于使用map()函數(shù)來轉(zhuǎn)換數(shù)據(jù)，一個(gè)例子。
[圖片上傳失敗...(image-ea0dfd-1667467474174)]
用lambda函數(shù)來使用map函數(shù)是相當(dāng)強(qiáng)大的****。****當(dāng)與map函數(shù)一起使用時(shí)，可以使用lambda函數(shù)為序列的每個(gè)元素指定一個(gè)變換器。前面的代碼使用乘以2作為轉(zhuǎn)化器。列表中的每個(gè)元素都用map函數(shù)乘以2。
Reduce()可以用來在一個(gè)列表的每個(gè)元素上遞歸運(yùn)行一個(gè)函數(shù)，以便匯總數(shù)據(jù)。
[圖片上傳失敗...(image-f1a8e4-1667467474174)]
需要注意的是，reduce函數(shù)需要一個(gè)數(shù)據(jù)聚合函數(shù)。這段代碼包括一個(gè)名為functools的數(shù)據(jù)聚合函數(shù)。它指定了一個(gè)列表中的項(xiàng)目將如何被聚合。作為聚合的結(jié)果，前兩個(gè)元素將被替換成結(jié)果。直到我們到達(dá)終點(diǎn)，我們重復(fù)減少的過程，直到達(dá)到一個(gè)聚合的數(shù)字。doSum函數(shù)表示每次迭代中x1和x2的聚合標(biāo)準(zhǔn)。
270 是前面代碼塊的結(jié)果。
使用range() 范圍函數(shù)
使用range函數(shù)，可以很容易地生成大的數(shù)字列表。列表中的數(shù)字序列可以用這個(gè)函數(shù)自動(dòng)填充。
使用range函數(shù)很容易。要使用它，我們只需指定我們想要在列表中加入多少個(gè)元素。它從零開始，默認(rèn)情況下增加一個(gè)。
[圖片上傳失敗...(image-856984-1667467474174)]
此外，我們還可以指定步長和結(jié)束數(shù)。
[圖片上傳失敗...(image-2d7958-1667467474174)]
從3到29開始的奇數(shù)將由前面的范圍函數(shù)返回。
列表很耗時(shí)
使用大O符號(hào)，一個(gè)列表的時(shí)間復(fù)雜度可以總結(jié)為以下幾點(diǎn)。
[圖片上傳失敗...(image-46ed34-1667467474174)]
請(qǐng)注意，無論列表的大小，添加一個(gè)元素所需的時(shí)間都是一樣的。列表的大小會(huì)影響表中的其他操作。性能影響隨著列表的增長而增加。
Tuple 元組
集合也可以用元組來存儲(chǔ)，圖元是一種數(shù)據(jù)結(jié)構(gòu)。元組數(shù)據(jù)結(jié)構(gòu)與列表不同，它是不可變的（只讀）。元組的元素用（）包圍。
一個(gè)元組可以包含不同類型的元素，就像一個(gè)列表一樣。它們的元素也支持復(fù)雜的數(shù)據(jù)類型。因此，通過使用元組中的元組，可以創(chuàng)建嵌套的數(shù)據(jù)結(jié)構(gòu)。迭代和遞歸算法大大得益于創(chuàng)建嵌套數(shù)據(jù)結(jié)構(gòu)的能力。
你可以使用下面的代碼來創(chuàng)建元組。
[圖片上傳失敗...(image-ba830f-1667467474174)]
由于它們的性能優(yōu)勢(shì)，只要有可能，就應(yīng)該首選不可變的數(shù)據(jù)結(jié)構(gòu)（比如圖元）。不可變數(shù)據(jù)結(jié)構(gòu)的性能明顯快于可變數(shù)據(jù)結(jié)構(gòu)，特別是在處理大數(shù)據(jù)時(shí)。例如，我們必須為改變列表中的數(shù)據(jù)元素的能力付出代價(jià)，所以我們應(yīng)該仔細(xì)考慮是否真的有必要，以便將代碼實(shí)現(xiàn)為只讀元組。
這段代碼將圖元（100,200,300）稱為第三個(gè)元素，a[2]。這個(gè)元組的第二個(gè)元素是200，被稱為a[2][1]。
元組的時(shí)間復(fù)雜性
(使用Big O符號(hào)) 下面是一些元組函數(shù)的時(shí)間復(fù)雜性的例子。
[圖片上傳失敗...(image-cf2902-1667467474174)]
值得注意的是，Append在已經(jīng)存在的元組中增加了額外的元素。O(1)是其復(fù)雜性。
詞典
特別是在分布式算法中，鍵值對(duì)是很重要的。Python 中的 dictionary 包含這些鍵值對(duì)的集合。在創(chuàng)建 dictionary 時(shí)，選擇最適合在整個(gè)數(shù)據(jù)處理過程中識(shí)別數(shù)據(jù)的鍵是很重要的。任何類型的元素都可以作為值，例如數(shù)字或字符串。在 Python 中，一個(gè) list 總是被用作值，其他復(fù)雜的數(shù)據(jù)類型也是如此。作為一種值類型，字典可以用來創(chuàng)建嵌套字典。
為變量分配顏色的一個(gè)簡單方法是將鍵值對(duì)用{ }括起來。作為說明，這里有一段代碼，用三個(gè)鍵值對(duì)創(chuàng)建一個(gè)簡單的字典。
如下面的截圖所示，前面的代碼創(chuàng)建了三個(gè)鍵值對(duì)。
[圖片上傳失敗...(image-e1ee06-1667467474174)]
下面的代碼檢索和更新與一個(gè)鍵相關(guān)的值。
[圖片上傳失敗...(image-f99ed4-1667467474169)]
一個(gè)鍵可以被用作索引，也可以用get函數(shù)來檢索與之相關(guān)的一個(gè)值。
[圖片上傳失敗...(image-6e2229-1667467474174)]
使用下面的代碼，你可以更新與一個(gè)鍵相關(guān)的值。
[圖片上傳失敗...(image-b6b17d-1667467474174)]
我們可以通過在前面的代碼中更新字典中的鍵來更新一個(gè)值。
dictionary 的時(shí)間復(fù)雜性****的估計(jì)
一個(gè)用大O符號(hào)表示的字典有如下的時(shí)間復(fù)雜性。
[圖片上傳失敗...(image-3c529c-1667467474174)]
根據(jù)字典的復(fù)雜性分析，必須注意到鍵值的檢索或設(shè)置與字典的大小無關(guān)。換句話說，將一個(gè)鍵值對(duì)添加到三個(gè)維度的字典中與將一個(gè)鍵值對(duì)添加到一百萬維度的字典中所花費(fèi)的時(shí)間是一樣的。
集合 set()
集合是具有不同類型的元素的集合。在 [] 內(nèi)的是元素。請(qǐng)看下面的代碼塊作為一個(gè)例子。
[圖片上傳失敗...(image-fad2a-1667467474174)]
集合的特點(diǎn)是只為每個(gè)元素存儲(chǔ)不同的值。下面的圖示說明了如果你試圖添加另一個(gè)多余的元素會(huì)發(fā)生什么。
[圖片上傳失敗...(image-dac2b7-1667467474169)]
讓我們定義兩個(gè)集合來說明可以對(duì)它們進(jìn)行哪些操作。
黃色的東西屬于一個(gè)叫做黃色的集合
[圖片上傳失敗...(image-3e3ccd-1667467474174)]
**還有一個(gè)名為紅色的集合，它包含紅色的東西****這兩個(gè)集合有一些共同的東西。下面的維恩圖說明了這兩個(gè)集合之間的關(guān)系。******[圖片上傳失敗...(image-b73e45-1667467474168)]**** 這兩個(gè)集合可以用Python實(shí)現(xiàn)，如下所示。[圖片上傳失敗...(image-4f2178-1667467474174)]
這里有一個(gè)演示集合操作的Python代碼。****在Python中，集合可以被連接和相交，如前面的代碼片斷所示。正如我們所知，聯(lián)合將兩個(gè)集合的所有元素結(jié)合在一起，而相交則產(chǎn)生兩個(gè)集合共有的一個(gè)元素。應(yīng)該注意以下幾點(diǎn)。****要得到前面定義的兩個(gè)集合的并集，請(qǐng)使用****黃色|紅色****。****為了找到黃色和紅色之間的重疊部分，我們使用****yellow&red****集合時(shí)間復(fù)雜度分析****下面是對(duì)集合的時(shí)間復(fù)雜性的分析。[圖片上傳失敗...(image-d7c146-1667467474174)]
當(dāng)對(duì)集合進(jìn)行復(fù)雜度分析時(shí)，很明顯，無論集合的大小，向其添加元素所花費(fèi)的時(shí)間是不一樣的。****DataFrame****Python的pandas包提供了用于存儲(chǔ)表格數(shù)據(jù)的DataFrames。傳統(tǒng)的結(jié)構(gòu)化數(shù)據(jù)是使用這種數(shù)據(jù)結(jié)構(gòu)處理的，它是算法最重要的數(shù)據(jù)結(jié)構(gòu)之一。下面是一個(gè)需要考慮的表格。****現(xiàn)在可以用一個(gè)DataFrame來表示。****[圖片上傳失敗...(image-138e23-1667467474169)] 通過使用下面的代碼，我們可以創(chuàng)建一個(gè)簡單的DataFrame。[圖片上傳失敗...(image-bb7dab-1667467474174)]
**在前面的代碼中的df.column中指定了一個(gè)列名列表。****在其他語言和框架中也可以使用DataFrame來實(shí)現(xiàn)表格數(shù)據(jù)結(jié)構(gòu)。Apache Spark框架和R是兩個(gè)例子。****數(shù)據(jù)框架術(shù)****語****在這篇文章中，我們將研究在DataFrame背景下使用的一些術(shù)語。****DataFrame的列或行在pandas文檔中被稱為軸。****作為一個(gè)組，多個(gè)軸被稱為軸。****數(shù)據(jù)框架允許將標(biāo)簽應(yīng)用到列和行上。****創(chuàng)建DataFrame子集****可以通過兩種不同的方式來創(chuàng)建DataFrame的子集（假設(shè)子集的名稱為myDF）。*****選擇列******行的選擇*****讓我們仔細(xì)看一下它們各自的情況。****列的選擇：******[圖片上傳失敗...(image-fae2e6-1667467474168)]**** 選擇適當(dāng)?shù)奶卣骷菣C(jī)器學(xué)習(xí)算法中最重要的任務(wù)之一。根據(jù)算法的不同，在某一階段可能不需要所有的特征。下一節(jié)解釋了如何通過列選擇來選擇Python特征。****可以通過列的名稱來檢索，如下面的例子。[圖片上傳失敗...(image-53bbc-1667467474174)]
DataFrames 確定性地定位列。為了通過它的位置檢索一個(gè)列，請(qǐng)遵循以下步驟。****需要注意的是，我們?cè)谶@段代碼中只檢索了DataFrame的前三行。****選擇行[圖片上傳失敗...(image-a5be1-1667467474174)]
DataFrame的行代表我們問題空間中的數(shù)據(jù)點(diǎn)。創(chuàng)建一個(gè)問題空間的子集需要選擇行。有兩種方法來創(chuàng)建這個(gè)子集。
- 通過指定它們的位置來定位
- 通過指定一個(gè)來進(jìn)行過濾
- 通過確定行的位置，可以檢索出一個(gè)行的子集。
所有的列和前兩行將由前面的代碼返回。****[圖片上傳失敗...(image-37fd9a-1667467474169)] 創(chuàng)建子集的選擇標(biāo)準(zhǔn)可以通過向過濾器添加列來定義。使用這種方法，你可以選擇一個(gè)數(shù)據(jù)元素的子集，如下所示。[圖片上傳失敗...(image-3e0c4c-1667467474173)]
在這段代碼中，只有那些滿足過濾器條件的行被創(chuàng)建。矩陣矩陣中有列和行，它是一個(gè)二維數(shù)據(jù)結(jié)構(gòu)。在一個(gè)矩陣中，每個(gè)元素都由它的列和行來標(biāo)識(shí)。****Numpy數(shù)組可以用來在Python中創(chuàng)建矩陣值，如下所示。[圖片上傳失敗...(image-b06d11-1667467474173)]
前面的代碼將創(chuàng)建三行和三列。矩陣操作在矩陣數(shù)據(jù)操作中，有許多操作可供選擇。讓我們?cè)囋噷?duì)上面的矩陣進(jìn)行轉(zhuǎn)置。使用transpose()函數(shù)，列將被轉(zhuǎn)換成行，行將被轉(zhuǎn)換成列。
[圖片上傳失敗...(image-c9f086-1667467474173)]
多媒體數(shù)據(jù)處理在很大程度上依賴于矩陣操作。****在學(xué)習(xí)了數(shù)據(jù)結(jié)構(gòu)之后，我們的下一節(jié)將討論P(yáng)ython中的抽象數(shù)據(jù)類型。抽象數(shù)據(jù)類型：一個(gè)探索****人們普遍認(rèn)為，抽象是一個(gè)概念，它確定了復(fù)雜系統(tǒng)的共同核心功能。抽象數(shù)據(jù)類型（ADTs）是通過將這一概念應(yīng)用于通用數(shù)據(jù)結(jié)構(gòu)而創(chuàng)建的。****使用ADT的結(jié)果是更簡單、更干凈的算法，因?yàn)樗鼈冸[藏了實(shí)現(xiàn)層面的細(xì)節(jié)，并提供了一個(gè)與實(shí)現(xiàn)無關(guān)的數(shù)據(jù)結(jié)構(gòu)。各種編程語言都可以用來實(shí)現(xiàn)ADTs，包括C++、Java和Scala。在本節(jié)中，我們將使用Python實(shí)現(xiàn)ADTs。我們將從向量開始。矢量矢量是一種以單維存儲(chǔ)數(shù)據(jù)的結(jié)構(gòu)。Python 最流行的數(shù)據(jù)結(jié)構(gòu)是列表。Python 提供了兩種創(chuàng)建向量的方法。[圖片上傳失敗...(image-a5cb36-1667467474173)]
通過使用一個(gè) Python 列表，你可以用以下方式創(chuàng)建一個(gè)向量。****在這個(gè)由這段代碼創(chuàng)建的列表中會(huì)有四個(gè)元素。****也可以使用 NumPy 數(shù)組來創(chuàng)建向量，如下所示。[圖片上傳失敗...(image-336550-1667467474173)]
在這段代碼中，myVector是用np.array創(chuàng)建的。****在 Python 中，為了分隔整數(shù)的各個(gè)部分，使用了下劃線。通過這樣做，它們變得更易讀，更不容易出錯(cuò)。在處理這個(gè)問題時(shí)，大數(shù)字特別有用。相應(yīng)地，a=1可以用來表示10億堆棧一維列表可以存儲(chǔ)在堆棧中，它是一種線性數(shù)據(jù)結(jié)構(gòu)?？梢允褂煤筮M(jìn)先出或FILO系統(tǒng)來存儲(chǔ)項(xiàng)目。堆棧是由添加和刪除元素的過程來定義的。在一端只有一個(gè)添加，在另一端只有一個(gè)刪除。****堆?？梢园匆韵路绞竭M(jìn)行操作。
[圖片上傳失敗...(image-ef117c-1667467474173)]
*如果 isEmpty 返回 true，那么棧就是空的。******一個(gè)元素的添加是通過推送******填充最近添加的元素并將其刪除******從堆棧中推送和彈出數(shù)據(jù)可以用下面的圖來說明。*****在上圖的頂部部分，推操作被用來向堆棧添加項(xiàng)目。在步驟1.1、1.2和1.3中，推操作被使用了三次，向堆棧中添加了三個(gè)元素。在上圖的底部，從堆棧中檢索存儲(chǔ)的值。在步驟2.2和2.3中使用pop操作從堆棧中取出兩個(gè)后進(jìn)先出格式的元素。****堆棧類將在Python中由一個(gè)叫做Stack的類來定義。這個(gè)類的代碼將看起來像這樣。[圖片上傳失敗...(image-9d62af-1667467474173)]
使用下面的代碼，四個(gè)元素可以被推到棧上。
[圖片上傳失敗...(image-4075ed-1667467474173)]
使用前面的代碼，四個(gè)數(shù)據(jù)元素被創(chuàng)建在一個(gè)堆棧中。****堆棧有很高的時(shí)間復(fù)雜性****為了理解堆棧的時(shí)間復(fù)雜度（使用大O符號(hào)），我們來看看。
[圖片上傳失敗...(image-6fc4d0-1667467474173)]
堆棧的大小對(duì)上面列出的四種操作的性能沒有任何影響。****一個(gè)實(shí)踐中的例子****堆棧在許多應(yīng)用中被用作數(shù)據(jù)結(jié)構(gòu)。在網(wǎng)絡(luò)瀏覽器中，可以使用后進(jìn)先出的數(shù)據(jù)訪問模式來訪問歷史記錄，而歷史記錄可以存儲(chǔ)在堆棧中。在使用文字處理程序時(shí)，用戶可能想執(zhí)行撤銷操作。****隊(duì)列****隊(duì)列是存儲(chǔ)n個(gè)元素的單維結(jié)構(gòu)。一個(gè)FIFO格式用于添加和刪除元素。隊(duì)列的后端和前端分別被稱為后端和前端。去排隊(duì)是將元素從前端移除的過程。排隊(duì)是在末端添加元素的過程。****一個(gè)排隊(duì)操作顯示在圖的上部。結(jié)果隊(duì)列顯示在1.4中，是步驟1.1、1.2和1.3的結(jié)果。紅色在后面，黃色在前面。****下圖的底部顯示了一個(gè)去排隊(duì)操作。從隊(duì)列的前面，步驟2.2、2.3和2.4逐一移除元素。
[圖片上傳失敗...(image-bb146f-1667467474173)]
下面的代碼可以用來實(shí)現(xiàn)上圖中的隊(duì)列。[圖片上傳失敗...(image-a13030-1667467474173)]
下面是一張截圖，顯示了前述圖中的元素是如何排隊(duì)和脫隊(duì)的。
[圖片上傳失敗...(image-c547c4-1667467474173)]
在前面的代碼中，首先將四個(gè)項(xiàng)目排入隊(duì)列。隊(duì)列和堆棧是基于相同的基本思想的用一個(gè)類比來分析堆棧和隊(duì)列將有助于我們理解它們背后的基本思想。讓我們想象一下，我們有一張桌子，里面放著我們的郵件，比如說，來自加拿大郵政的郵件。把郵件堆放好后，我們逐一打開，看一看?？梢允褂靡韵聝煞N方法。****字母被堆疊起來，每個(gè)新的字母都被放在堆疊的頂部。字母是從上到下讀的。這里可以找到一個(gè)堆疊的例子。最近到達(dá)的信件將被首先處理。在列表頂部拿起一個(gè)字母的過程被稱為彈出操作。每當(dāng)一個(gè)字母到達(dá)時(shí)，將其推到頂部，這被稱為推操作。如果我們得到一個(gè)相當(dāng)大的堆棧，并且許多字母連續(xù)到達(dá)，如果我們最終得到一個(gè)大的堆棧，我們可能永遠(yuǎn)不會(huì)到達(dá)堆棧底部的重要字母。****當(dāng)我們查看一個(gè)或多個(gè)字母時(shí)，我們會(huì)注意先處理最老的那個(gè)：每次我們想檢查一個(gè)或多個(gè)字母時(shí)，我們都會(huì)先處理最老的那個(gè)。隊(duì)列就是我們所說的。將一個(gè)字母添加到堆中的過程被稱為enqueueing。當(dāng)一個(gè)字母從堆中被移除時(shí)，它被稱為去排隊(duì)操作。Tree 樹由于其分層的數(shù)據(jù)存儲(chǔ)能力，樹是算法中最有用的數(shù)據(jù)結(jié)構(gòu)之一。每當(dāng)我們需要表示算法中數(shù)據(jù)元素之間的層次關(guān)系時(shí)，我們就會(huì)使用樹。****這種數(shù)據(jù)結(jié)構(gòu)相當(dāng)有趣，也相當(dāng)重要，所以讓我們深入了解一下。****每棵樹的頂端都有一個(gè)根，還有一組由分支連接的節(jié)點(diǎn)，因此每棵樹的節(jié)點(diǎn)數(shù)量是有限的。****術(shù)語****為了理解樹形數(shù)據(jù)結(jié)構(gòu)，我們來研究一些術(shù)語。[圖片上傳失敗...(image-724ea2-1667467474173)]
根節(jié)點(diǎn)****根節(jié)點(diǎn)沒有父母。下圖的根節(jié)點(diǎn)是A，算法通常在其樹結(jié)構(gòu)中把最高值放在根節(jié)點(diǎn)上。****節(jié)點(diǎn)的級(jí)別****一個(gè)節(jié)點(diǎn)和它的根節(jié)點(diǎn)之間的距離決定了它的級(jí)別。例如，在下圖中，節(jié)點(diǎn)D、E、F的級(jí)別是2。****同級(jí)節(jié)點(diǎn)****在樹的同一層次的節(jié)點(diǎn)被稱為兄弟姐妹。我們可以看到下圖中的節(jié)點(diǎn)B和C是兄弟姐妹。****子節(jié)點(diǎn)和父節(jié)點(diǎn)****節(jié)點(diǎn)C的級(jí)別必須低于節(jié)點(diǎn)F的級(jí)別，這樣節(jié)點(diǎn)F才是節(jié)點(diǎn)C的孩子；反之，節(jié)點(diǎn)C是節(jié)點(diǎn)F的父。****節(jié)點(diǎn)的程度****節(jié)點(diǎn)按其擁有的子女?dāng)?shù)量進(jìn)行排序。下圖中顯示了一個(gè)雙度節(jié)點(diǎn)的例子。[圖片上傳失敗...(image-8fa1e9-1667467474173)]
一棵樹的度數(shù)****如果樹中的節(jié)點(diǎn)被相應(yīng)程度的節(jié)點(diǎn)所連接，那么這些節(jié)點(diǎn)可以有一個(gè)最大的程度。下面是一個(gè)度數(shù)為2的樹的例子。****子樹****樹的子樹由根節(jié)點(diǎn)和每個(gè)子節(jié)點(diǎn)組成，而根節(jié)點(diǎn)是由選定的節(jié)點(diǎn)形成的。如下圖所示，節(jié)點(diǎn)E的子樹由節(jié)點(diǎn)E作為根，節(jié)點(diǎn)G和H作為子節(jié)點(diǎn)組成。****葉子節(jié)點(diǎn)****在一棵樹上，一個(gè)葉子節(jié)點(diǎn)沒有子女。在下圖中，D、G、H和F是葉子節(jié)點(diǎn)。****內(nèi)部節(jié)點(diǎn)****如果它既不是根節(jié)點(diǎn)也不是葉節(jié)點(diǎn)，就沒有內(nèi)部節(jié)點(diǎn)這一說。為了有一個(gè)子節(jié)點(diǎn)，必須至少有一個(gè)父節(jié)點(diǎn)。****有不同類型的樹****根據(jù)樹的特性，可以將其分為不同的類型。****程度為2的樹被稱為二叉樹。例如，一棵二叉樹的度數(shù)為2，如下圖所示。****在上圖中，你可以看到一棵樹在四個(gè)層次上有八個(gè)節(jié)點(diǎn)。****每當(dāng)所有節(jié)點(diǎn)的度數(shù)相同時(shí)，這棵樹就是滿的。樹的度數(shù)將與節(jié)點(diǎn)的數(shù)量相同。如下圖所示，有幾種類型的樹。****如左圖所示，二叉樹不是一棵完整的樹，因?yàn)楣?jié)點(diǎn)C的度數(shù)是1，而所有其他節(jié)點(diǎn)的度數(shù)是2。左邊的樹和中間的樹都是全樹。****一棵理想的樹是一棵全樹，它的葉子節(jié)點(diǎn)都在同一級(jí)別。如上圖所示，右邊的二叉樹是一棵完美的全樹，因?yàn)樗械娜~子結(jié)點(diǎn)都在同一級(jí)別，即第2級(jí)。****有序樹是一棵樹，它的子節(jié)點(diǎn)按照特定的標(biāo)準(zhǔn)排列。例如，在從左到右遍歷一棵樹的過程中，同一級(jí)別的節(jié)點(diǎn)將隨著它們的上升而增加價(jià)值。
