數據結構筆記pdf

㈠ 利用Python進行數據分析筆記：3.1數據結構

元組是一種固定長度、不可變的Python對象序列。創建元組最簡單的辦法是用逗號分隔序列值：

tuple 函數將任意序列或迭代器轉換為元組：

中括弧 [] 可以獲取元組的元素， Python中序列索引從0開始 ：

元組一旦創建，各個位置上的對象是無法被修改的，如果元組的一個對象是可變的，例如列表，你可以在它內部進行修改：

可以使用 + 號連接元組來生成更長的元組：

元組乘以整數，則會和列表一樣，生成含有多份拷貝的元組：

將元組型的表達式賦值給變數，Python會對等號右邊的值進行拆包：

拆包的一個常用場景就是遍歷元組或列表組成的序列：

*rest 用於在函數調用時獲取任意長度的位置參數列表：

count 用於計量某個數值在元組中出現的次數：

列表的長度可變，內容可以修改。可以使用 [] 或者 list 類型函數來定義列表：

append 方法將元素添加到列表尾部：

insert 方法可以將元素插入到指定列表位置：
（ 插入位置范圍在0到列表長度之間 ）

pop 是 insert 的反操作，將特定位置的元素移除並返回：

remove 方法會定位第一個符合要求的值並移除它：

in 關鍵字可以檢查一個值是否在列表中；
not in 表示不在：

+ 號可以連接兩個列表：

extend 方法可以向該列表添加多個元素：

使用 extend 將元素添加到已經存在的列表是更好的方式，比 + 快。

sort 方法可以對列表進行排序：

key 可以傳遞一個用於生成排序值的函數，例如通過字元串的長度進行排序：

bisect.bisect 找到元素應當被插入的位置，返回位置信息
bisect.insort 將元素插入到已排序列表的相應位置保持序列排序

bisect 模塊的函數並不會檢查列表是否已經排序，因此對未排序列表使用bisect不會報錯，但是可能導致不正確結果

切片符號可以對大多數序列類型選取子集，基本形式是 [start:stop]
起始位置start索引包含，結束位置stop索引不包含

切片還可以將序列賦值給變數：

start和stop可以省略，默認傳入起始位置或結束位置，負索引可以從序列尾部進行索引：

步進值 step 可以在第二個冒號後面使用， 意思是每隔多少個數取一個值：

對列表或元組進行翻轉時，一種很聰明的用法時向步進值傳值-1：

dict(字典)可能是Python內建數據結構中最重要的，它更為常用的名字是 哈希表 或者 關聯數組 。
字典是鍵值對集合，其中鍵和值都是Python對象。
{} 是創建字典的一種方式，字典中用逗號將鍵值對分隔：

你可以訪問、插入或設置字典中的元素,:

in 檢查字典是否含有一個鍵：

del 或 pop 方法刪除值， pop 方法會在刪除的同時返回被刪的值，並刪除鍵：

update 方法將兩個字典合並：
update方法改變了字典元素位置，對於字典中已經存在的鍵，如果傳給update方法的數據也含有相同的鍵，則它的值將會被覆蓋。

字典的值可以是任何Python對象，但鍵必須是不可變的對象，比如標量類型（整數、浮點數、字元串）或元組（且元組內對象也必須是不可變對象）。
通過 hash 函數可以檢查一個對象是否可以哈希化（即是否可以用作字典的鍵）：

集合是一種無序且元素唯一的容器。

set 函數或者是用字面值集與大括弧，創建集合：

union 方法或 | 二元操作符獲得兩個集合的聯合即兩個集合中不同元素的並集：

intersection 方法或 & 操作符獲得交集即兩個集合中同時包含的元素：

常用的集合方法列表：

和字典類似，集合的元素必須是不可變的。如果想要包含列表型的元素，必須先轉換為元組：

㈡ 鏁版嵁緇撴瀯絎旇

鏈鏂囧皢浠嬬粛浜屽弶鏍戠殑鐩稿叧鐭ヨ瘑錛屽寘鎷浜屽弶鏍戠殑緇撶偣涓鏁般佹爲娣便侀亶鍘嗙瓑鍐呭廣
🌳浜屽弶鏍戠殑緇撶偣涓鏁
浜屽弶鏍戠殑絎琄灞備笂錛屾渶澶氭湁2鐨刱-1嬈″籙涓緇撶偣錛涙繁搴︿負M鐨勪簩鍙夋爲鏈澶氭湁2鐨凪嬈″籙-1涓緇撶偣錛涙繁搴︿負5鐨勬弧浜屽弶鏍戜腑錛屽彾瀛愮粨鐐圭殑涓鏁頒負2鐨(5-1)嬈″籙銆
🌲鏍戞繁
鍋囧畾鏍圭粨鐐圭殑灞傛℃槸0錛屽惈鏈15涓緇撶偣鐨勪簩鍙夋爲鐨勬渶灝忔爲娣辨槸3銆
🔍浜屽垎娉曟煡鎵
瀵逛簬涓涓闀垮害涓10鐨勬帓濂藉簭鐨勮〃鐢ㄤ簩鍒嗘硶鏌ユ壘錛岃嫢鏌ユ壘涓嶆垚鍔燂紝鑷沖皯闇瑕佹瘮杈冪殑嬈℃暟涓3銆

㈢ 鏁版嵁緇撴瀯瀛︿範絎旇幫細濡備綍鏇村ソ鍦版帉鎻＄粡鍏哥畻娉

鏁版嵁緇撴瀯鏄璁＄畻鏈虹戝︿腑鐨勯噸瑕佸熀紜錛屾帉鎻″ソ鏁版嵁緇撴瀯瀵逛簬緙栫▼鑳藉姏鍜岄棶棰樿В鍐寵兘鍔涚殑鎻愬崌鑷沖叧閲嶈併傛湰鏂囧皢浠嬬粛濡備綍鏇村ソ鍦版帉鎻＄粡鍏哥畻娉曪紝甯鍔╄昏呮洿濂藉湴搴旂敤鏁版嵁緇撴瀯銆
📚鎵撳ソ鍩虹
緙栫▼鍩虹鐭ヨ瘑鏄鎺屾彙鏁版嵁緇撴瀯鐨勫墠鎻愶紝鍙鏈夋墦濂藉熀紜錛屾墠鑳芥洿濂藉湴搴旂敤鏁版嵁緇撴瀯銆傚洜姝わ紝鍦ㄥ︿範鏁版嵁緇撴瀯涔嬪墠錛岀『淇濅綘宸茬粡鎺屾彙浜嗙紪紼嬬殑鍩虹鐭ヨ瘑錛岃繖鏍鋒墠鑳戒負鍚庣畫鐨勫︿範鎵撲笅鍧氬疄鍩虹銆
🤔娣卞叆鐞嗚В綆楁硶閫昏緫
瀵逛簬姣忎釜緇忓吀綆楁硶錛岃佹繁鍏ョ悊瑙ｅ叾閫昏緫榪囩▼錛岃繖鏈夊姪浜庝綘鏇村ソ鍦板簲鐢ㄥ畠浠銆傚彧鏈夋繁鍏ョ悊瑙ｇ畻娉曠殑閫昏緫錛屾墠鑳芥洿濂藉湴搴旂敤瀹冧滑瑙ｅ喅瀹為檯闂棰樸
💻鑷宸辮捐℃暟鎹瀛樺偍緇撴瀯
灝濊瘯鑷宸辮捐℃暟鎹瀛樺偍緇撴瀯騫剁紪鍐欑畻娉曚唬鐮侊紝榪欐牱鍙浠ュ姞娣變綘鐨勭悊瑙ｃ傞氳繃鑷宸辯殑璁捐″拰緙栧啓錛屼綘鍙浠ユ洿濂藉湴鐞嗚В鏁版嵁緇撴瀯鍜岀畻娉曠殑瀹炵幇榪囩▼銆
🔍瀵規瘮浼樺寲綆楁硶
涓庣粡鍏哥畻娉曠殑浠ｇ爜榪涜屽規瘮錛屾壘鍑鴻嚜宸辯殑涓嶈凍錛屼粠綆楁硶璁捐″拰綆楁硶澶嶆潅搴︿袱涓鏂歸潰榪涜屼紭鍖栵紝鐩磋嚦瀹屽叏鎺屾彙緇忓吀綆楁硶鐨勫疄鐜拌繃紼嬨傚彧鏈変笉鏂鍦板規瘮鍜屼紭鍖栵紝鎵嶈兘鏇村ソ鍦版帉鎻＄粡鍏哥畻娉曠殑瀹炵幇榪囩▼銆
🚀鎸戞垬鏇村氱畻娉曢棶棰
鍦ㄥ﹀畬鏁版嵁緇撴瀯鍚庯紝浣犲皢浼氬彂鐜拌嚜宸辯殑緙栫▼鑳藉姏鍜岄棶棰樿В鍐寵兘鍔涙湁浜嗘樉钁楃殑鎻愬崌銆傜幇鍦錛屾槸鏃跺欑戶緇鍓嶈繘錛屾寫鎴樻洿澶氱殑綆楁硶闂棰樹簡錛

㈣ 數據結構與演算法之美筆記——散列表（上）

摘要:

我們已經知道隨機訪問數組元素時間復雜度只有 ，效率極高，當我們想利用數組的這個特性時就需要將元素下標與存儲信息對應。例如，一個商店只有四件商品，依次編號 0 至 3，這樣就可以將四件商品信息按照編號對應下標的方式存儲到數組中，依據編號就可以快速從數組中找到相應商品信息。

如果一段時間之後，商店盈利並且重新進貨 100 件商品，商家想對大量商品在編號上區分類別，這時候需要使用類別編號加順序編號的方式標識每件商品，這種編號變得復雜，並不能直接對應數組下標，此時的商品編號又該如何對應數組下標以實現快速查找商品的功能？這時候我們可以將類別編號去除之後按照順序編號對應數組下標，同樣也能享受數組高效率隨機訪問的福利。這個例子中，商品編號稱為「 鍵 」或「 關鍵字 」，將鍵轉化為數組對應下標的方法就是「 散列函數 」或「 Hash 函數 」，由散列函數生成的值叫做「 散列值 」或「 Hash 值 」，而這樣的數組就是散列表。

從散列表的原理來看，數據通過散列函數計算得到散列值是關鍵，這個步驟中散列函數又是其中的核心，一個散列函數需要遵守以下三個原則。

因為散列函數生成的散列值對應數組下標，而數組下標就是非負整數，所以需要滿足第一個原則；兩個相等的數據經過散列演算法得到的散列值肯定相等，否則利用散列值在散列表中查找數據就無從談起；至於第三個原則雖然在情理之中，卻不那麼容易做到，即使是被廣泛運用的散列演算法也會出現散列值沖突的情況，導致無法滿足第三個原則。

散列函數作為散列表的核心部分，必然不能拖散列表的執行效率後腿，畢竟散列表的查詢、插入和刪除操作都需要經過散列函數，所以散列函數不能太復雜，執行效率不能太低。由於散列函數不可避免地都會出現散列沖突情況，散列函數要盡量降低散列沖突，使散列值能夠均勻地分布在散列表中。

解決散列沖突主要有「 開放定址 」（open addressing）和「 鏈表法 」（chaining）兩類方法。

開放定址法是指插入操作時，當生成的散列值對應槽位已經被其他數據佔用，就探測空閑位置供插入使用，其中探測方法又分為「 線性探測 」（Linear Probing）、「 二次探測 」（Quadratic Probing）和「 雙重散列 」（Double hashing）三種。

線性探測是其中較為簡單的一種，這種探測方式是當遇到散列沖突的情況就順序查找（查找到數組尾部時轉向數組頭部繼續查找），直到查找到空槽將數據插入。當進行查找操作時，也是同樣的操作，利用散列值從散列表中取出對應元素，與目標數據比對，如果不相等就繼續順序查找，直到查找到對應元素或遇到空槽為止，最壞情況下查找操作的時間復雜度可能會下降為 。

散列表除了支持插入和查找操作外，當然也支持刪除操作，不過並不能將需刪除的元素置為空。如果刪除操作是將元素置為空的話，查找操作遇到空槽就會結束，存儲在被刪除元素之後的數據就可能無法正確查找到，這時的刪除操作應該使用標記的方式，而不是使用將元素置空，當查找到被標識已刪除的元素將繼續查找，而不是就此停止。

線性探測是一次一個元素的探測，二次探測就是使用都是線性探測的二次方步長探測。例如線性探測是 ，那二次探測對應的就是 。

雙重探測是當第一個散列函數沖突時使用第二個散列函數運算散列值，利用這種方式探測。例如，當 沖突時，就使用 計算散列值，如果再沖突就使用 計算散列值，依此類推。

關於散列表的空位多少使用「 裝載因子 」（load factor）表示，裝載因子滿足數學關系 ，也就是說裝載因子越大，散列表的空閑空間越小，散列沖突的可能性也就越大，一般我們會保持散列表有一定比例的空閑空間。

為了保持散列表一定比例的空閑空間，在裝載因子到達一定閾值時需要對散列表數據進行搬移，但散列表搬移比較耗時。你可以試想下這樣的步驟，在申請一個新的更大的散列表空間後，需要將舊散列表的數據重新通過散列函數生成散列值，再存儲到新散列表中，想想都覺得麻煩。

散列表搬移的操作肯定會降低散列表的操作效率，那能不能對這一過程進行改進？其實可以將低效的擴容操作分攤至插入操作，當裝載因子達到閾值時不一次性進行散列表搬移，而是在每次插入操作時將一個舊散列表數據搬移至新散列表，這樣搬移操作的執行效率得到了提高，插入操作的時間復雜度也依然能保持 的高效。當新舊兩個散列表同時存在時查詢操作就要略作修改，需先在新散列表中查詢，如果沒有查找到目標數據再到舊散列表中查找。

當然，如果你對內存有更高效的利用要求，可以在裝載因子降低至某一閾值時對散列表進行縮容處理。

除了開放定址之外，還可以使用鏈表法解決散列沖突的問題。散列值對應的槽位並不直接存儲數據，而是將數據存儲在槽位對應的鏈表上，當進行查找操作時，根據散列函數計算的散列值找到對應槽位，再在槽位對應的鏈表上查找對應數據。

鏈表法操作的時間復雜度與散列表槽位和數據在槽位上的分布情況有關，假設有 n 個數據均勻分布在 m 個槽位的散列表上，那鏈表法的時間復雜度為 。鏈表法可以不用像開放定址一樣關心裝載因子，但需要注意散列函數對散列值的計算，使鏈表結點能夠盡可能均勻地分布在散列表槽位上，避免散列表退化為鏈表。有時黑客甚至會精心製造數據，利用散列函數製造散列沖突，使數據集中某些槽位上，造成散列表性能的極度退化。

面對這樣的惡意行為散列表只能坐以待斃嗎？其實不然，當槽位上的鏈表過長時，可以將其改造成之前學習過的跳錶等，鏈表改造為跳錶後查詢的時間復雜度也只是退化為 ，依然是可以接受的范圍。

鏈表法在存儲利用上比開放定址更加高效，不用提前申請存儲空間，當有新數據時申請一個新的結點就行。而且鏈表法對裝載因子也不那麼敏感，裝載因子的增高也只是意味著槽位對應的鏈表更長而已，鏈表增長也有將鏈表改造為跳錶等結構的應對策略，所以鏈表法在裝載因子超過 1 的情況下都可保持高效。

開放定址不存在像鏈表法一樣有鏈表過長而導致效率降低的煩惱，不過裝載因子是開放定址的晴雨表，裝載因子過高會造成散列沖突機率的上升，開放定址就需要不斷探測空閑位置，演算法的執行成本會不斷被提高。而且在刪除操作時只能將數據先標記為刪除，對於頻繁增刪的數據效率會受到影響。

當然也可以在這種風險出現前進行散列表的動態擴容，不過這樣就會出現大量空閑的存儲空間，導致存儲的利用效率過低，這種現象在數據量越大的情況下越明顯。所以開放定址比較適用於數據量較小的情況。

鏈表法對於散列沖突的處理更加靈活，同時對存儲空間的利用效率也更高，但鏈表結點除了存儲數據外還需要存儲指針，如果存儲數據較小指針佔用的存儲甚至會導致整體存儲翻倍的情況，但存儲數據較大時指針佔用的存儲也就可以忽略不計，所以鏈表法較適合存儲數據對象較大，但頻繁的增刪操作不會對鏈表法造成明顯的影響。因為這樣的特點，鏈表法更加適合大數據量，或者數據對象較大的時候，如果數據操作頻繁，那鏈表法更是不二之選。

散列表由數組擴展而來，使用散列函數將鍵計算為散列值，散列值對應數據存儲的數組下標。雖然散列表的執行效率較高，但會有散列沖突的問題，可以通過開放定址法和鏈表法解決此問題。

開放定址存儲利用效率較低，適用數據量較小並且增刪不頻繁的情況，如果數據量較大，增刪頻繁的情況更加適用鏈表法，相對之下鏈表法更加普適。