《Python程序設(shè)計(jì)與算法基礎(chǔ)教程》課件（含思政案例） Ch11 數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)

Ch11數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)本章要點(diǎn)：數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)算法及其性能分析

查找算法

排序算法

常用數(shù)據(jù)結(jié)構(gòu)

數(shù)組

棧和隊(duì)列

集合

字典（映射）collections模塊的其它數(shù)據(jù)結(jié)構(gòu)資源下載提示2課件等資源：掃描封底的“課件下載”二維碼，在公眾號(hào)“書圈”中下載。素材（源碼）：掃描本書目錄上方的二維碼下載。講解視頻：掃描封底刮刮卡中的二維碼，再掃描書中相應(yīng)章節(jié)中（位于每章最前）的二維碼，作為開源的補(bǔ)充閱讀和學(xué)習(xí)資源。

案例研究：掃描封底刮刮卡中的二維碼，再掃描書中相應(yīng)章節(jié)中（位于每章最后）的二維碼，可以在線學(xué)習(xí)。每章練習(xí)題：掃描封底刮刮卡中的二維碼，再掃描每章習(xí)題部分的二維碼，下載本章練習(xí)題電子版。

題庫(kù)平臺(tái)：教師登錄網(wǎng)站（），聯(lián)系客服開通教師權(quán)限數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)著名的計(jì)算機(jī)科學(xué)家尼克勞斯?沃思（NikiklausWirth）指出：程序=算法+數(shù)據(jù)結(jié)構(gòu)算法是執(zhí)行特定任務(wù)的方法數(shù)據(jù)結(jié)構(gòu)是一種存儲(chǔ)數(shù)據(jù)的方式，有助于求解特定的問(wèn)題數(shù)據(jù)（Data）是能夠被計(jì)算機(jī)處理的對(duì)象集合。數(shù)據(jù)由數(shù)據(jù)元素（DateElement）組成，數(shù)據(jù)元素包含數(shù)據(jù)項(xiàng)（DataItem）在學(xué)生檔案管理系統(tǒng)中，每位學(xué)生信息是數(shù)據(jù)的基本單位，稱之為數(shù)據(jù)元素，也稱為元素（Element）、節(jié)點(diǎn)（Node）或者記錄（Record）組成數(shù)據(jù)元素的項(xiàng)稱之為數(shù)據(jù)項(xiàng)，數(shù)據(jù)項(xiàng)是數(shù)據(jù)的最小標(biāo)識(shí)單位，又稱為字段（Field）或者域（Field）例如，學(xué)生信息由學(xué)號(hào)、姓名、性別、出生年月、專業(yè)等組成數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)通常由三個(gè)部分組成：數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算結(jié)構(gòu)（1）數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)反映數(shù)據(jù)元素之間的邏輯關(guān)系。數(shù)據(jù)的邏輯結(jié)構(gòu)主要包括線性結(jié)構(gòu)（一對(duì)一的關(guān)系）、樹形結(jié)構(gòu)（一對(duì)多的關(guān)系）、圖形結(jié)構(gòu)（多對(duì)多的關(guān)系）、集合等（2）數(shù)據(jù)的物理結(jié)構(gòu)數(shù)據(jù)的物理結(jié)構(gòu)反映數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間的存放形式，即數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示。其具體的實(shí)現(xiàn)方法包括順序、鏈接、索引、散列等多種形式。一種數(shù)據(jù)結(jié)構(gòu)可以由一種或者多種物理存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)（3）數(shù)據(jù)的運(yùn)算結(jié)構(gòu)數(shù)據(jù)的運(yùn)算結(jié)構(gòu)反映在數(shù)據(jù)的邏輯結(jié)構(gòu)上定義的操作算法，例如檢索、插入、刪除、更新和排序等數(shù)據(jù)的邏輯結(jié)構(gòu)（1）反映數(shù)據(jù)元素之間的邏輯關(guān)系，與他們?cè)谟?jì)算機(jī)中的存儲(chǔ)位置無(wú)關(guān)數(shù)據(jù)結(jié)構(gòu)可以表示為DS=(D,R)，其中DS表示數(shù)據(jù)結(jié)構(gòu)，D表示數(shù)據(jù)集合，R表示關(guān)系（Relation）集合三口之家的成員的數(shù)據(jù)邏輯結(jié)構(gòu)可以表示如下：DS=(D,R)D={父親,母親,孩子}R={(父親,母親),(父親,孩子),(母親,孩子)}數(shù)據(jù)的邏輯結(jié)構(gòu)可以分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)線性結(jié)構(gòu)中的元素節(jié)點(diǎn)具有線性關(guān)系。如果從數(shù)據(jù)結(jié)構(gòu)的語(yǔ)言來(lái)描述，線性結(jié)構(gòu)具有以下特點(diǎn)。（1）線性結(jié)構(gòu)是非空集。（2）線性結(jié)構(gòu)有且僅有一個(gè)開始節(jié)點(diǎn)和一個(gè)終端節(jié)點(diǎn)。（3）線性結(jié)構(gòu)所有節(jié)點(diǎn)都最多只有一個(gè)直接前趨節(jié)點(diǎn)和一個(gè)直接后繼節(jié)點(diǎn)線性表、隊(duì)列、棧等數(shù)據(jù)結(jié)構(gòu)屬于線性結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)（2）非線性結(jié)構(gòu)中的各元素節(jié)點(diǎn)之間具有多個(gè)對(duì)應(yīng)關(guān)系。如果從數(shù)據(jù)結(jié)構(gòu)的語(yǔ)言來(lái)描述，非線性結(jié)構(gòu)具有以下特點(diǎn)。（1）非線性結(jié)構(gòu)是非空集。（2）非線性結(jié)構(gòu)的一個(gè)節(jié)點(diǎn)可能有多個(gè)直接前趨節(jié)點(diǎn)和多個(gè)直接后繼節(jié)點(diǎn)。在實(shí)際應(yīng)用中，數(shù)組、廣義表、樹結(jié)構(gòu)和圖結(jié)構(gòu)等數(shù)據(jù)結(jié)構(gòu)屬于非線性結(jié)構(gòu)常用的數(shù)據(jù)邏輯結(jié)構(gòu)包括如下幾種方式，如圖所示。（1）集合：數(shù)據(jù)結(jié)構(gòu)中的元素之間除了“同屬一個(gè)集合”的相互關(guān)系外，別無(wú)其他關(guān)系。（2）線性結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)中的元素存在一對(duì)一的相互關(guān)系。（3）樹形結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)中的元素存在一對(duì)多的相互關(guān)系。（4）圖形結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)中的元素存在多對(duì)多的相互關(guān)系數(shù)據(jù)的物理結(jié)構(gòu)數(shù)據(jù)的物理結(jié)構(gòu)是指邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間的存放形式。數(shù)據(jù)的物理結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的實(shí)現(xiàn)方式，它包括數(shù)據(jù)元素的機(jī)內(nèi)表示和關(guān)系的機(jī)內(nèi)表示實(shí)現(xiàn)邏輯數(shù)據(jù)結(jié)構(gòu)的常用方法包括順序、鏈接、索引、散列等。一種邏輯數(shù)據(jù)結(jié)構(gòu)可以表示成一種或者多種物理存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)元素之間的關(guān)系在計(jì)算機(jī)內(nèi)部的存儲(chǔ)結(jié)構(gòu)通常有兩種方式：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)借助元素在存儲(chǔ)器中的相對(duì)位置來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)借助指示元素存儲(chǔ)位置的指針來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系常用算法數(shù)據(jù)的算法基于數(shù)據(jù)的邏輯結(jié)構(gòu)，但具體實(shí)現(xiàn)要在物理存儲(chǔ)結(jié)構(gòu)上進(jìn)行基于數(shù)據(jù)結(jié)構(gòu)的常用算法包括以下幾種。（1）檢索：在數(shù)據(jù)結(jié)構(gòu)中查找滿足給定條件的節(jié)點(diǎn)。（2）插入：在數(shù)據(jù)結(jié)構(gòu)中增加新的節(jié)點(diǎn)。（3）刪除：從數(shù)據(jù)結(jié)構(gòu)中刪除指定節(jié)點(diǎn)。（4）更新：改變指定節(jié)點(diǎn)的一個(gè)或者多個(gè)字段的值。（5）排序：按某種指定的順序重新排列節(jié)點(diǎn)（從而可以提高其他算法的操作效率）常用的數(shù)據(jù)結(jié)構(gòu)線性表隊(duì)列棧樹圖堆散列表線性表線性表（LinearList）是最基本的一種數(shù)據(jù)結(jié)構(gòu)，是具有相同特性的數(shù)據(jù)元素的有限序列，通常記做(a1,a2,…,an）。其中a1無(wú)前趨，an無(wú)后繼，其他每個(gè)元素都有一個(gè)前趨和后繼線性表的物理存儲(chǔ)結(jié)構(gòu)主要有兩種：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，前者稱為順序表，后者稱為線性鏈表順序存儲(chǔ)結(jié)構(gòu)使用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素順序表的優(yōu)點(diǎn)是查找和訪問(wèn)元素速度快，但插入和刪除開銷大鏈表（LinkedList）是一種數(shù)據(jù)元素按照鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)進(jìn)行存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)，這種存儲(chǔ)結(jié)構(gòu)具有在物理上存在非連續(xù)的特點(diǎn)鏈表由一系列數(shù)據(jù)節(jié)點(diǎn)構(gòu)成，每個(gè)數(shù)據(jù)節(jié)點(diǎn)包括數(shù)據(jù)域和指針域兩部分線性鏈表的優(yōu)點(diǎn)在于插入和刪除效率高。其缺點(diǎn)是訪問(wèn)元素時(shí)需要遍歷鏈表的所有元素，因而效率欠佳隊(duì)列和棧隊(duì)列（Queue）是先進(jìn)先出的系列（FIFO，F(xiàn)irstInFirstOut），即最先添加的元素，是最先彈出的元素列表可以實(shí)現(xiàn)隊(duì)列，但并不適合。因?yàn)閺牧斜淼念^部移除一個(gè)元素，列表中的所有元素都需要移動(dòng)位置，所以效率不高。用戶可以使用collections模塊中的deque對(duì)象來(lái)刪除列表頭部的元素棧（Stack）是后進(jìn)先出的隊(duì)列（LIFO，LastInFirstOut），即最后添加（push）的元素，是最先彈出（pop）的元素向列表最后位置添加元素和從最后位置移除元素非常方便和高效，故使用列表可以快捷高效地實(shí)現(xiàn)棧list.append()方法對(duì)應(yīng)于入棧操作（push）；list.pop()對(duì)應(yīng)于出棧操作（pop）樹（1）樹（Tree）是典型的非線性結(jié)構(gòu)，由n（n>=1）個(gè)有限節(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合，其形狀像一棵倒掛的樹樹具有以下的特點(diǎn)。（1）每個(gè)節(jié)點(diǎn)有零個(gè)或多個(gè)子節(jié)點(diǎn)。（2）沒(méi)有父節(jié)點(diǎn)的節(jié)點(diǎn)稱為根節(jié)點(diǎn)（root）。（3）每一個(gè)非根節(jié)點(diǎn)有且只有一個(gè)父節(jié)點(diǎn)。（4）除了葉子節(jié)點(diǎn)外，每個(gè)子節(jié)點(diǎn)可以分為多個(gè)不相交的子樹樹的常用術(shù)語(yǔ)（1）（1）節(jié)點(diǎn)：每個(gè)元素稱為節(jié)點(diǎn)。（2）根節(jié)點(diǎn)：沒(méi)有父節(jié)點(diǎn)的節(jié)點(diǎn)稱為根節(jié)點(diǎn)。（3）節(jié)點(diǎn)的度（degree）：一個(gè)節(jié)點(diǎn)含有的子節(jié)點(diǎn)個(gè)數(shù)稱為該節(jié)點(diǎn)的度。（4）葉節(jié)點(diǎn)或終端節(jié)點(diǎn)（leaf）：度為0的節(jié)點(diǎn)稱為葉節(jié)點(diǎn)。（5）非終端節(jié)點(diǎn)或分支節(jié)點(diǎn)（branch）：度不為0的節(jié)點(diǎn)。樹（2）樹的常用術(shù)語(yǔ)（2）（6）雙親節(jié)點(diǎn)或父節(jié)點(diǎn)（parent）：若一個(gè)節(jié)點(diǎn)含有子節(jié)點(diǎn)，則這個(gè)節(jié)點(diǎn)稱為其子節(jié)點(diǎn)的父節(jié)點(diǎn)。（7）孩子節(jié)點(diǎn)或子節(jié)點(diǎn)（child）：一個(gè)節(jié)點(diǎn)含有的子樹的根節(jié)點(diǎn)稱為該節(jié)點(diǎn)的子節(jié)點(diǎn)。（8）兄弟節(jié)點(diǎn)（sibling）：具有相同父節(jié)點(diǎn)的節(jié)點(diǎn)互稱為兄弟節(jié)點(diǎn)。（9）樹的度：一棵樹中，最大的節(jié)點(diǎn)的度稱為樹的度。（10）節(jié)點(diǎn)的層次（level）：從根開始定義起，根為第1層，根的子節(jié)點(diǎn)為第2層，以此類推（11）樹的高度或深度（depth）：樹中節(jié)點(diǎn)的最大層次。（12）堂兄弟節(jié)點(diǎn)：雙親在同一層的節(jié)點(diǎn)互為堂兄弟節(jié)點(diǎn)。（13）節(jié)點(diǎn)的祖先：從根到該節(jié)點(diǎn)所經(jīng)分支上的所有節(jié)點(diǎn)。（14）子孫：以某節(jié)點(diǎn)為根的子樹中任一節(jié)點(diǎn)都稱為該節(jié)點(diǎn)的子孫。（15）森林：m（m>=0）棵互不相交的樹的集合稱為森林。樹（3）樹的常用術(shù)語(yǔ)（3）（16）空樹?？占弦彩菢?，稱為空樹?？諛渲袥](méi)有節(jié)點(diǎn)。（17）無(wú)序樹：樹中任意節(jié)點(diǎn)的子結(jié)點(diǎn)之間沒(méi)有順序關(guān)系，這種樹稱為無(wú)序樹，也稱為自由樹。（18）有序樹：樹中任意節(jié)點(diǎn)的子結(jié)點(diǎn)之間有順序關(guān)系，這種樹稱為有序樹。（19）二叉樹：每個(gè)節(jié)點(diǎn)最多含有兩個(gè)子樹的樹稱為二叉樹。（20）滿二叉樹：如果一棵二叉樹只有度為0的結(jié)點(diǎn)和度為2的結(jié)點(diǎn)，并且度為0的結(jié)點(diǎn)在同一層上，則這棵二叉樹為滿二叉樹。即，一棵深度為k且有2k-1個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹。滿二叉樹每一層的結(jié)點(diǎn)個(gè)數(shù)都達(dá)到了最大值，即滿二叉樹的第i層上有2i-1個(gè)結(jié)點(diǎn)。如圖5-6（a）所示是一棵深度為3的滿二叉樹（21）完全二叉樹：滿二叉樹中葉子節(jié)點(diǎn)所在的層次中，如果自右向左連續(xù)缺少若干葉子節(jié)點(diǎn)，這樣的得到的二叉樹被稱為完全二叉樹。即，若設(shè)二叉樹的深度為k，除第k層外，其它各層（1～k-1）的節(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，而第k層所有的節(jié)點(diǎn)都連續(xù)集中在最左邊，這就是一個(gè)完全二叉樹。如圖5-6（b）所示是一棵完全二叉樹。如圖5-6（c）所示是一棵非完全二叉樹。滿二叉樹是完全二叉樹的特殊形態(tài)。（22）哈夫曼樹（最優(yōu)二叉樹）：帶權(quán)路徑最短的二叉樹稱為哈夫曼樹或最優(yōu)二叉樹二叉樹重要性質(zhì)二叉樹的遍歷（1）二叉樹是n個(gè)有限元素的集合，該集合或者為空、或者由一個(gè)稱為根的元素及兩個(gè)不相交的、被分別稱為左子樹和右子樹的二叉樹組成二叉樹具有五種基本形態(tài)遍歷二叉樹，就是按一定的規(guī)則和順序遍歷二叉樹的所有節(jié)點(diǎn)，使每一個(gè)節(jié)點(diǎn)都被訪問(wèn)一次，而且只被訪問(wèn)一次在任一給定節(jié)點(diǎn)上，可以按某種次序執(zhí)行三個(gè)操作。（1）訪問(wèn)節(jié)點(diǎn)本身（N）。（2）遍歷該節(jié)點(diǎn)的左子樹（L）。（3）遍歷該節(jié)點(diǎn)的右子樹（R）以上三種操作有六種遍歷方法：NLR、LNR、LRN、NRL、RNL、RLN二叉樹的遍歷（2）1、NLR：前序遍歷（PreorderTraversal），又稱為先序遍歷。若二叉樹非空，則依次執(zhí)行如下操作。訪問(wèn)根結(jié)點(diǎn)（N）遍歷左子樹（L）遍歷右子樹（R）2、LNR：中序遍歷（InorderTraversal）。若二叉樹非空，則依次執(zhí)行如下操作。遍歷左子樹（L）訪問(wèn)根結(jié)點(diǎn)（N）遍歷右子樹（R）3、LRN：后序遍歷（PostorderTraversal）。若二叉樹非空，則依次執(zhí)行如下操作。遍歷左子樹（L）遍歷右子樹（R）訪問(wèn)根結(jié)點(diǎn)（N）圖、堆、散列表圖（Graph）是另一種非線性數(shù)據(jù)結(jié)構(gòu)。圖是由頂點(diǎn)集合V（Vertex）和邊集合E（Edge）組成的，定義為G=(V，E)在圖結(jié)構(gòu)中，數(shù)據(jù)節(jié)點(diǎn)一般稱為頂點(diǎn)，而邊是頂點(diǎn)的有序偶對(duì)。如果兩個(gè)頂點(diǎn)之間存在一條邊，那么就表示這兩個(gè)頂點(diǎn)具有相鄰關(guān)系堆（Heap）是一種特殊的樹形數(shù)據(jù)結(jié)構(gòu)，其中子節(jié)點(diǎn)與父節(jié)點(diǎn)是一種有序關(guān)系散列表（Hashtable，也叫哈希表）是把鍵值映射（映射函數(shù)）到表（散列表）的數(shù)據(jù)結(jié)構(gòu)，通過(guò)鍵值可以實(shí)現(xiàn)快速查找算法及其性能分析著名的計(jì)算機(jī)科學(xué)家尼克勞斯?沃思（NikiklausWirth）指出：程序=數(shù)據(jù)結(jié)構(gòu)+算法數(shù)據(jù)結(jié)構(gòu)用于描述數(shù)據(jù)，算法則基于數(shù)據(jù)結(jié)構(gòu)操作數(shù)據(jù)算法是指解決問(wèn)題的一種方法或一個(gè)過(guò)程。算法通常使用計(jì)算機(jī)程序來(lái)實(shí)現(xiàn)。算法接手待處理的輸入數(shù)據(jù)；然后執(zhí)行相應(yīng)的處理過(guò)程；最后輸出處理的結(jié)果算法的時(shí)間復(fù)雜度分析算法的運(yùn)行時(shí)間長(zhǎng)度，與算法本身的設(shè)計(jì)和所求解的問(wèn)題的規(guī)模有關(guān)。算法的時(shí)間性能分析，又稱之為算法的時(shí)間復(fù)雜度（TimeComplexity）分析問(wèn)題的規(guī)模（Size）即算法求解問(wèn)題的輸入量，通常用一個(gè)整數(shù)表示一個(gè)算法運(yùn)行的總時(shí)間取決于以下兩個(gè)主要因素（1）每條語(yǔ)句的執(zhí)行時(shí)間成本（2）每條語(yǔ)句的執(zhí)行次數(shù)（頻度）【例11.1】算法中語(yǔ)句的頻度之和示例（frequency.py）循環(huán)語(yǔ)句運(yùn)行了n*n次，總算法執(zhí)行語(yǔ)句頻度為：n2+2total=0foriinrange(n):forjinrange(n):total+=a[i][j]print(total)增長(zhǎng)量級(jí)增長(zhǎng)量級(jí)用于描述函數(shù)的漸進(jìn)增長(zhǎng)行為，一般使用大O符號(hào)表示。例如，2n、100n與n+1屬于相同的增長(zhǎng)量級(jí)，記為O(n)，表示函數(shù)隨n線性增長(zhǎng)算法分析中常用的增長(zhǎng)量級(jí)如表11-2所示算法的空間復(fù)雜度分析衡量算法有效性的另一個(gè)指標(biāo)是內(nèi)存消耗。對(duì)于復(fù)雜的算法，如果其消耗的內(nèi)存超過(guò)運(yùn)行該算法的計(jì)算機(jī)的可用物理內(nèi)存，則算法無(wú)法正常執(zhí)行。算法的內(nèi)存消耗分析，又稱之為算法的空間復(fù)雜度（SpaceComplexity）分析確定一個(gè)Python程序內(nèi)存使用的典型方法是，先統(tǒng)計(jì)程序使用的對(duì)象的數(shù)量，然后根據(jù)對(duì)象的類型乘以各對(duì)象占用的字節(jié)數(shù)。使用函數(shù)sys.getsizeof(x)，可以返回一個(gè)內(nèi)置數(shù)據(jù)類型x在系統(tǒng)中所占用的字節(jié)數(shù)【例11.2】Python語(yǔ)言中對(duì)象占用內(nèi)存大小示例>>>importsys>>>sys.getsizeof(100)#整數(shù)對(duì)象占用內(nèi)存大小。輸出：28>>>sys.getsizeof("1.23")#字符串對(duì)象占用內(nèi)存大小。輸出：53>>>sys.getsizeof(True)#布爾邏輯型對(duì)象占用內(nèi)存大小。輸出：28查找算法順序查找法假定要從n個(gè)元素中查找x的值是否存在，最原始的辦法是從頭到尾逐個(gè)查找，這種查找方法稱為順序查找法算法的時(shí)間復(fù)雜度為O(n)【例11.3】在列表中順序查找特定數(shù)值x（sequentialSearch.py）……tobecontinued【例11.4】在列表中順序查找最大值和最小值（MaxMin.py）……tobecontinued【例11.3】在列表中順序查找特定數(shù)值（sequentialSearch.py）defsequentialSearch(alist,item):#順序查找法pos=0#初始查找位置found=False#未找到數(shù)據(jù)對(duì)象whilepos<len(alist)andnotfound:#列表未結(jié)束并且還未找到則一直循環(huán)ifalist[pos]==item:#找到匹配對(duì)象，返回Truefound=Trueelse:#否則查找位置+1pos=pos+1returnfounddefmain():testlist=[1,3,33,8,37,29,32,15,5]#測(cè)試數(shù)據(jù)列表print(sequentialSearch(testlist,3))#查找數(shù)據(jù)3print(sequentialSearch(testlist,13))#查找數(shù)據(jù)13if__name__=='__main__':main()【例11.4】在列表中順序查找最大值和最小值（MaxMin.py）

defmax1(alist):#查找最大值pos=0#初始查找位置iMax=alist[0]#假設(shè)第一個(gè)值最大whilepos<len(alist):#在列表中循環(huán)ifalist[pos]>iMax:#如果列表當(dāng)前值大于最大值iMaxiMax=alist[pos]#則當(dāng)前值為最大值iMaxpos=pos+1#查找位置+1returniMax#返回最大值defmin1(alist):#查找最小值iMin=alist[0]#假設(shè)第一個(gè)值最小foriteminalist:#對(duì)于列表中每個(gè)數(shù)值ifitem<iMin:#如果列表當(dāng)前值小于最小值iMiniMin=item#則當(dāng)前值為最小值iMinreturniMin#返回最小值defmain():testlist=[1,3,33,8,37,29,32,15,5]#測(cè)試數(shù)據(jù)列表print("最大值=",max1(testlist))#查找并打印列表中最大值print("最小值=",min1(testlist))#查找并打印列表中最小值if__name__=='__main__':main()二分查找法二分查找法又稱折半查找法，用于預(yù)排序列表的查找問(wèn)題要在排序列表a中查找元素t，首先，將列表alist中間位置的項(xiàng)與查找關(guān)鍵字t比較，如果兩者相等，則查找成功；否則利用中間項(xiàng)將列表分成前、后兩個(gè)子表，如果中間位置項(xiàng)目大于t，則進(jìn)一步查找前一子表，否則進(jìn)一步查找后一子表。重復(fù)以上過(guò)程，直到找到滿足條件的記錄，即查找成功；或直到子表不存在為止，即查找不成功對(duì)于包含N個(gè)元素的表，其時(shí)間復(fù)雜度為O(log2N)【例11.5】二分查找法的遞歸實(shí)現(xiàn)（binarySearch.py）……tobecontinued【例11.6】二分查找法的非遞歸實(shí)現(xiàn)（binarySearchNoRecursion.py）……tobecontinued【例11.5】二分查找法的遞歸實(shí)現(xiàn)def_binarySearch(key,a,lo,hi):ifhi<=lo:return-1#查找失敗，返回-1mid=(lo+hi)//2#計(jì)算中間位置ifa[mid]>key:#中間位置項(xiàng)目大于查找關(guān)鍵字return_binarySearch(key,a,lo,mid)#遞歸查找前一子表elifa[mid]<key:#中間位置項(xiàng)目小于查找關(guān)鍵字return_binarySearch(key,a,mid+1,hi)#遞歸查找后一子表else:#中間位置項(xiàng)目等于查找關(guān)鍵字returnmid#查找成功，返回下標(biāo)位置defbinarySearch(key,a):#二分查找return_binarySearch(key,a,0,len(a))#遞歸二分查找法defmain():a=[1,13,26,33,45,55,68,72,83,99]print("關(guān)鍵字位于列表索引",binarySearch(33,a))#二分查找關(guān)鍵字33print("關(guān)鍵字位于列表索引",binarySearch(58,a))#二分查找關(guān)鍵字58if__name__=='__main__':main()【例11.6】二分查找法的非遞歸實(shí)現(xiàn)defbinarySearch(key,a):#二分查找法的非遞歸實(shí)現(xiàn)low=0#左邊界high=len(a)-1#右邊界whilelow<=high:#左邊界小于等于右邊界，則循環(huán)mid=(low+high)//2#計(jì)算中間位置ifa[mid]<key:#中間位置項(xiàng)目小于查找關(guān)鍵字low=mid+1#調(diào)整左邊界（在后一子表查找）elifa[mid]>key:#中間位置項(xiàng)目大于查找關(guān)鍵字high=mid-1#調(diào)整右邊界（在前一子表查找）else:#中間位置項(xiàng)目等于查找關(guān)鍵字returnmid#查找成功，返回下標(biāo)位置return-1#查找不成功（不存在關(guān)鍵字），返回-1defmain():a=[1,13,26,33,45,55,68,72,83,99]print("關(guān)鍵字位于列表索引",binarySearch(33,a))#二分查找關(guān)鍵字33print("關(guān)鍵字位于列表索引",binarySearch(58,a))#二分查找關(guān)鍵字58if__name__=='__main__':main()Python語(yǔ)言提供的查找算法（1）運(yùn)算符in：“xinalist”測(cè)試值x是否在列表alist中存在（2）內(nèi)置函數(shù)max、min：查找列表的最大值和最小值【例11.7】Python語(yǔ)言提供的查找算法示例>>>3in[1,3,33,8,37,29,32,15,5]#輸出：True>>>13in[1,3,33,8,37,29,32,15,5]#輸出：False>>>max([1,3,33,8,37,29,32,15,5])#輸出：37>>>min([1,3,33,8,37,29,32,15,5])#輸出：1冒泡排序算法對(duì)于包含N個(gè)元素的列表A，按遞增順序排序的冒泡法的算法如下：（1）第1輪比較：從第一個(gè)元素開始，對(duì)列表中所有N個(gè)元素進(jìn)行兩兩大小比較，如果不滿足升序關(guān)系，則交換。即A[0]與A[1]比較，若A[0]>A[1]，則A[0]與A[1]交換；然后A[1]與A[2]比較，若A[1]>A[2]，則A[1]與A[2]交換；……直至最后A[N-2]與A[N-1]比較，若A[N-2]>A[N-1]，則A[N-2]與A[N-1]交換。第一輪比較完成后，列表元素中最大的數(shù)“沉”到列表最后，而那些較小的數(shù)如同氣泡一樣上浮一個(gè)位置，顧名思義“冒泡法”排序。（2）第2輪比較：從第一個(gè)元素開始，對(duì)列表中前N-1個(gè)元素（第N個(gè)元素，即A[N-1]已經(jīng)最大，無(wú)需參加排序）繼續(xù)兩兩大小比較，如果不滿足升序關(guān)系，則交換。第二輪比較完成后，列表元素中次大的數(shù)“沉”到最后，即A[N-2]為列表元素中次大的數(shù)。（3）以此類推，進(jìn)行第N-1輪比較后，列表中所有元素均按遞增順序排好序?！纠?1.8】冒泡排序算法的實(shí)現(xiàn)（bubbleSort.py）defbubbleSort(a):foriinrange(len(a)-1,0,-1):#外循環(huán)forjinrange(i):#內(nèi)循環(huán)ifa[j]>a[j+1]:#大數(shù)往下沉a[j],a[j+1]=a[j+1],a[j]#print(a)#跟蹤調(diào)試defmain():a=[2,97,86,64,50,80,3,71,8,76]bubbleSort(a)print(a)if__name__=='__main__':main()選擇排序法對(duì)于包含N個(gè)元素的列表A，按遞增順序排序的選擇法的基本思想是：每次在若干無(wú)序數(shù)據(jù)中查找最小數(shù)，并放在無(wú)序數(shù)據(jù)中的首位。其算法如下：（1）從N個(gè)元素的列表中找最小值及其下標(biāo)，最小值與列表的第1個(gè)元素交換。（2）從列表的第2個(gè)元素開始的N-1個(gè)元素中再找最小值及其下標(biāo)，該最小值（即整個(gè)列表元素的次小值）與列表第2個(gè)元素交換。（3）以此類推，進(jìn)行第N-1輪選擇和交換后，列表中所有元素均按遞增順序排好序。【例11.9】選擇排序算法的實(shí)現(xiàn)（selectionSort.py）

defselectionSort(a):foriinrange(0,len(a)-1):#外循環(huán)（0~N-2）m=i#當(dāng)前位置下標(biāo)forjinrange(i+1,len(a)):#內(nèi)循環(huán)ifa[j]<a[m]:#查找最小值的位置m=ja[i],a[m]=a[m],a[i]#元素交換#print(a)#跟蹤調(diào)試defmain():a=[59,12,77,64,72,69,46,89,31,9]selectionSort(a)print(a)if__name__=='__main__':main()插入排序法對(duì)于包含N個(gè)元素的列表A，按遞增順序排序的插入排序法的基本思想是：依次檢查列表中的每個(gè)元素，將其插入到其左側(cè)已經(jīng)排好序的列表中的適當(dāng)位置。其算法如下：（1）第2個(gè)元素與列表中其左側(cè)的第1個(gè)元素比較，如果A[0]>A[1]，則交換位置，結(jié)果左側(cè)2個(gè)元素排序完畢。（2）第3個(gè)元素依次與其左側(cè)的列表的元素比較，直至插入對(duì)應(yīng)的排序位置，結(jié)果左側(cè)的3個(gè)元素排序完畢。（3）以此類推，進(jìn)行第N-1輪比較和交換后，列表中所有元素均按遞增順序排好序?！纠?1.10】插入排序算法的實(shí)現(xiàn)（insertSort.py）

definsertSort(a):foriinrange(1,len(a)):#外循環(huán)（1~N-1）j=iwhile(j>0)and(a[j]<a[j-1]):#內(nèi)循環(huán)a[j],a[j-1]=a[j-1],a[j]#元素交換j-=1#繼續(xù)循環(huán)#print(a)#跟蹤調(diào)試defmain():a=[59,12,77,64,72,69,46,89,31,9]insertSort(a)print(a)if__name__=='__main__':main()歸并排序法歸并排序法基于分而治之（DivideandConquer）的思想。算法的操作步驟如下。（1）將包含N個(gè)元素的列表分成兩個(gè)含N/2元素的子列表。（2）對(duì)兩個(gè)子列表遞歸調(diào)用歸并排序（最后可以將整個(gè)列表分解成N個(gè)子列表）。（2）合并兩個(gè)已排序好的子列表。【例11.11】歸并排序算法的實(shí)現(xiàn)（mergeSort.py）

defmerge(left,right):#合并兩個(gè)列表merged=[]i,j=0,0#i和j分別作為left和right的下標(biāo)left_len,right_len=len(left),len(right)#獲取左右子列表長(zhǎng)度whilei<left_lenandj<right_len:#循環(huán)歸并左右子列表元素ifleft[i]<=right[j]:merged.append(left[i])#歸并左子列表元素i+=1else:merged.append(right[j])#歸并右子列表元素j+=1merged.extend(left[i:])#歸并左子列表剩余元素merged.extend(right[j:])#歸并右子列表剩余元素#print(left,right,merged)#跟蹤調(diào)試returnmerged#返回歸并好的列表defmergeSort(a):#歸并排序iflen(a)<=1:#空或者只有1個(gè)元素，直接返回列表returnamid=len(a)//2#列表中間位置left=mergeSort(a[:mid])#歸并排序左子列表right=mergeSort(a[mid:])#歸并排序右子列表returnmerge(left,right)#合并排好序的左右兩個(gè)子列表defmain():a=[59,12,77,64,72,69,46,89,31,9]a1=mergeSort(a)print(a1)if__name__=='__main__':main()快速排序法快速排序是對(duì)冒泡排序的一種改進(jìn)，由C.A.R.Hoare在1962年提出。其基本思想是：通過(guò)一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小；然后遞歸對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序?？焖倥判蛩惴ǖ囊惶伺判虻牟僮鞑襟E如下。（1）設(shè)置兩個(gè)變量i和j，分別為列表首末元素的下標(biāo)，即i=0，j=N-1。（2）設(shè)置列表的第1個(gè)元素作為關(guān)鍵數(shù)據(jù)，即key=A[0]。（3）從j開始向前搜索，找到第一個(gè)小于key的值A(chǔ)[j]，將A[j]和A[i]互換。（4）從i開始向后搜索，找到第一個(gè)大于key的A[i]，將A[i]和A[j]互換。（5）重復(fù)第（3）和（4）步，直到i=j?！纠?1.12】快速排序算法的實(shí)現(xiàn)（quickSort.py）

defquickSort(a,low,high):#對(duì)列表a快速排序，列表下界為low，上界為highi=low#i等于列表下界j=high#j等于列表上界ifi>=j:#如果下界大于等于上界，返回結(jié)果列表areturnakey=a[i]#設(shè)置列表的第1個(gè)元素作為關(guān)鍵數(shù)據(jù)#print(key)#跟蹤調(diào)試whilei<j:#循環(huán)直到i=jwhilei<janda[j]>=key:#j開始向前搜索，找到第一個(gè)小于key的值a[j]j=j-1a[i]=a[j]whilei<janda[i]<=key:#i開始向后搜索，找到第一個(gè)大于key的a[i]i=i+1a[j]=a[i]a[i]=key#a[i]等于關(guān)鍵數(shù)據(jù)#print(a)#跟蹤調(diào)試quickSort(a,low,i-1)#遞歸調(diào)用快速排序算法（列表下界為low，上界為i-1）quickSort(a,j+1,high)#遞歸調(diào)用快速排序算法（列表下界為j+1，上界為high）defmain():a=[59,12,77,64,72,69,46,89,31,9]quickSort(a,0,len(a)-1)print(a)if__name__=='__main__':main()Python語(yǔ)言提供的排序算法（1）內(nèi)置數(shù)據(jù)類型list中的方法sort()，把列表的項(xiàng)按升序重新排列（2）內(nèi)置函數(shù)sorted()則保持原列表不變，函數(shù)返回一個(gè)新的包含按升序排列的項(xiàng)的列表【例11.13】Python語(yǔ)言提供的查找算法示例>>>a=[59,12,77,64,72,69,46,89,31,9]>>>sorted(a)#輸出：[9,12,31,46,59,64,69,72,77,89]>>>a#輸出：[59,12,77,64,72,69,46,89,31,9]>>>a.sort()>>>a#輸出：[9,12,31,46,59,64,69,72,77,89]常用數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲(chǔ)、組織數(shù)據(jù)的方式。通常由數(shù)據(jù)元素的集合和集合中數(shù)據(jù)元素之間的關(guān)系組成。算法的實(shí)現(xiàn)基于數(shù)據(jù)結(jié)構(gòu)，選擇恰當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)可以帶來(lái)更高的運(yùn)行或者存儲(chǔ)效率數(shù)據(jù)結(jié)構(gòu)通常由三個(gè)部分組成：數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算結(jié)構(gòu)數(shù)組Python語(yǔ)言沒(méi)有直接提供數(shù)組數(shù)據(jù)類型，通常使用列表作為數(shù)組列表支持?jǐn)?shù)組要求的四種核心操作：創(chuàng)建數(shù)組、索引訪問(wèn)、索引賦值和迭代遍歷【例11.14】Python數(shù)組示例生成一副撲克牌（每副撲克牌包含52張牌，大小王除外），并且隨機(jī)洗牌后輸出一副撲克牌importrandomSUITS=['Club','Diamond','Heart','Spade']#梅花、方塊、紅桃、黑桃RANKS=['2','3','4','5','6','7','8','9','10','J','Q','K','A']#生成一副撲克牌，每副撲克牌包含52張牌（大、小王除外）deck=[]#一副撲克牌forrankinRANKS:forsuitinSUITS:card=rank+'of'+suitdeck+=[card]#洗牌n=len(deck)foriinrange(n):r=random.randrange(i,n)temp=deck[r]deck[r]=deck[i]deck[i]=temp#輸出一副撲克牌forsindeck:print(s)array.array對(duì)象和數(shù)組array模塊包含一個(gè)array對(duì)象，用于實(shí)現(xiàn)其他編程語(yǔ)言中的數(shù)組數(shù)據(jù)結(jié)構(gòu)array對(duì)象是包含相同基本數(shù)據(jù)類型的列表，其操作與list對(duì)象基本一致，區(qū)別是創(chuàng)建array對(duì)象時(shí)，必須指定其元素類型typecode，且其元素只能為該類型，否則導(dǎo)致TypeErrorarray對(duì)象支持包括索引訪問(wèn)、切片操作、連接操作、重復(fù)操作、成員關(guān)系操作、比較運(yùn)算操作，以及求長(zhǎng)度、最大值、最小值等的基本操作【例11.15】array.array對(duì)象和數(shù)組示例>>>importarray>>>a=array.array('b',(1,2,3,4,5))>>>a[1]#輸出：22>>>a[1]=22>>>a[1:]#輸出：array('b',[22,3,4,5])array('b',[22,3,4,5])>>>a[0]="abc"#報(bào)錯(cuò)TypeError:anintegerisrequired(gottypestr)棧和隊(duì)列隊(duì)列（Queue）是先進(jìn)先出的系列（FIFO，F(xiàn)irstInFirstOut），即最先添加的元素，是最先彈出的元素棧（Stack）是后進(jìn)先出的隊(duì)列（LIFO，LastInFirstOut），即最后添加（push）的元素，是最先彈出（pop）的元素棧的實(shí)現(xiàn)：使用列表list.append()方法對(duì)應(yīng)于入棧操作（push）list.pop()對(duì)應(yīng)于出棧操作（pop）可以使用collections模塊中的deque對(duì)象【例11.16】棧的實(shí)現(xiàn)示例創(chuàng)建一個(gè)包含整數(shù)1和2的棧，展示入棧和出棧操作，以及打印棧的內(nèi)容classStack:def__init__(self,size=16):#初始化棧self.stack=[]defpush(self,obj):#入棧操作（push）self.stack.append(obj)defpop(self):#出棧操作（pop）try:returnself.stack.pop()exceptIndexErrorase:print("stackisempty")def__str__(self):returnstr(self.stack)defmain():stack=Stack()#創(chuàng)建并初始化棧stack.push(1)#整數(shù)1入棧stack.push(2)#整數(shù)2入棧print(stack)#打印棧的內(nèi)容stack.pop()#整數(shù)2出棧stack.pop()#整數(shù)1出棧stack.pop()#出棧操作，但是因?yàn)槭强諚?，提?stackisempty"if__name__=='__main__':main()deque對(duì)象collections.deque（雙端隊(duì)列）支持從任意一端增加和刪除元素deque是線程安全的、內(nèi)存高效的隊(duì)列，它被設(shè)計(jì)為從兩端追加和彈出都非?？靌eque對(duì)象dq支持下列方法：dq.append(x)：在右端添加元素x。dq.appendleft(x)：在左端添加元素x。dq.pop()：從右端彈出元素。若隊(duì)列中無(wú)元素，則導(dǎo)致IndexError。dq.popleft()：從左端彈出元素。若隊(duì)列中無(wú)元素，則導(dǎo)致IndexError。dq.extend(iterable)：在右端添加系列iterable中的元素。dq.extendleft(iterable)：在左端添加系列iterable中的元素。dq.remove(value)：移除第一個(gè)找到的x。若未找到，則導(dǎo)致IndexError。dq.count(x)：返回元素x在隊(duì)列中出現(xiàn)的個(gè)數(shù)。dq.clear()：刪除所有元素，即清空隊(duì)列。dq.reverse()：反轉(zhuǎn)隊(duì)列中所有元素。dq.rotate(n)：如果n>0，所有元素向右移動(dòng)n個(gè)位置（循環(huán)）；否則向左【例11.17】deque對(duì)象示例讀取文件，返回文件的最后n行內(nèi)容importcollectionsdeftail(filename,n=10):'Returnthelastnlinesofafile'withopen(filename)asf:returncollections.deque(f,n)if__name__=='__main__':path=r'deque_tail.py'#本示例程序dq=tail(path,n=2)#最后兩行print(dq.popleft())print(dq.popleft())

deque作為棧（LIFO）deque對(duì)象方法append()用于入棧操作；pop()對(duì)應(yīng)于出棧操作【例11.18】deque作為棧示例>>>fromcollectionsimport*>>>dq=deque()>>>dq.append(1);dq.append(2);dq.append(3)#整數(shù)1、2、3入棧>>>dq.pop();dq.pop();dq.pop()#整數(shù)3、2、1出棧321deque作為隊(duì)列（FIFO）deque對(duì)象方法append()用于進(jìn)隊(duì)操作；popleft()對(duì)應(yīng)于出隊(duì)操作【例11.19】deque作為隊(duì)列示例>>>fromcollectionsimport*>>>dq=deque()>>>dq.append(1);dq.append(2);dq.append(3)#整數(shù)1、2、3入隊(duì)>>>dq.popleft();dq.popleft();dq.popleft()#整數(shù)1、2、3出隊(duì)123collections模塊的其它數(shù)據(jù)結(jié)構(gòu)在collections.abc模塊中包含若干ABCs（AbstractBaseClasses，抽象基類）。抽象基類用于定義接口，繼承抽象基類的派生類實(shí)現(xiàn)這些接口功能。抽象類的派生類需要實(shí)現(xiàn)對(duì)應(yīng)的抽象方法；抽象類的派生類自動(dòng)擁有抽象類包含的繼承方法（mixins），不需要重新實(shí)現(xiàn)，方便派生類的開發(fā)在collections模塊和容器類型中包含若干實(shí)用的容器類型對(duì)象，用于實(shí)現(xiàn)常用的數(shù)據(jù)結(jié)構(gòu)。例如collections.deque實(shí)現(xiàn)了線程安全的雙端隊(duì)列namedtuple對(duì)象namedtuple對(duì)象使用namedtuple的構(gòu)造函數(shù)，可以定義一個(gè)tuple的子類命名元組。namedtuple對(duì)象既可以使用元素名稱訪問(wèn)其元素，也可使用索引訪問(wèn)【例11.20】namedtuple對(duì)象示例>>>fromcollectionsimport*>>>p=namedtuple('Point',['x','y'])>>>print(p._fields)#打印類的字段屬性。輸出：('x','y')>>>p.x=11;p.y=22>>>p.x+p.y#使用元素名稱訪問(wèn)命名元組的元素。輸出：33【例11.21】namedtuple對(duì)象方法示例>>>fromcollectionsimport*>>>p=namedtuple('Point',['x','y'])>>>t=[3,4]>>>p1=p._make(t);p1Point(x=3,y=4)>>>p1._asdict()OrderedDict([('x',3),('y',4)])>>>p1._replace(x=30)Point(x=30,y=4)【例11.22】namedtuple對(duì)象應(yīng)用示例讀取csv格式的文件employees.csv的內(nèi)容（姓名、年齡、職稱、系別和工資）fromcollectionsimport*#導(dǎo)入模塊importcsv#導(dǎo)入模塊EmployeeRecord=namedtuple('EmployeeRecord','name,age,title,department,paygrade')forempinmap(EmployeeRecord._make,csv.reader(open("employees.csv"))):print(,emp.title)#輸出職工姓名和職稱employees.csv的文件內(nèi)容如下：Mary 45 Professor Chinese 8000Tom 30 Lecturer Math 5000Clinton 50 Professor Computer 9000UserDict、UserList和UserString對(duì)象collections.UserDict、UserList和UserString分別是dict、list和str的子類【例11.23】UserString對(duì)象示例>>>fromcollectionsimport*>>>us=UserString('abc')>>>us.data

'abc'defaultdict對(duì)象【例11.24】defaultdict對(duì)象示例>>>s=[('r',1),('g',2),('b',3)]>>>dd=defaultdict(int,s)>>>dddefaultdict(<class'int'>,{'r':1,'g':2,'b':3})>>>dd['b']3>>>dd['w']#不存在時(shí)，返回默認(rèn)值00>>>s1=[('r',1),('g',2),('b',3),('r',4),('b',5)]>>>dd1=defaultdict(list)>>>fork,vins1:dd1[k].append(v)>>>list(dd1.items())[('r',[1,4]),('g',[2]),('b',[3,5])]

OrderedDict對(duì)象collections.OrderedDict是dict的子類，能夠記錄字典元素插入的順序OrderedDict對(duì)象的元素保持插入的順序，更新鍵的值時(shí)，不改變順序；刪除項(xiàng)，然后再插入與刪除項(xiàng)相同的鍵/值對(duì)時(shí)，則置于末尾【例11.25】OrderedDict對(duì)象示例>>>fromcollectionsimport*>>>d={'banana':3,'apple':4,'pear':1,'orange':2}>>>d.items()#輸出：dict_items([('banana',3),('apple',4),('pear',1),('orange',2)])dict_items([('banana',3),('apple',4),('pear',1),('orange',2)])>>>sorted(d.items())#輸出：[('apple',4),('banana',3),('orange',2),('pear',1)][('apple',4),('banana',3),('orange',2),('pear',1)]>>>od=OrderedDict(sorted(d.items()))>>>od#輸出：OrderedDict([('apple',4),('banana',3),('orange',2),('pear',1)])OrderedDict([('apple',4),('banana',3),('orange',2),('pear',1)])>>>od.popitem()#輸出：('pear',1)('pear',1)ChainMap對(duì)象collections.ChainMap對(duì)象用于連接多個(gè)mapChainMap對(duì)象cmap除了支持字典映射的屬性和方法外，還包含下列屬性和方法cmap.maps：屬性。返回cmap對(duì)象內(nèi)部包含的map的列表。cmap.parents：屬性。返回包含其父map的新的ChainMap對(duì)象，即ChainMap(*d.maps[1:])。cmap.new_child()：方法。返回新的ChainMap對(duì)象，即ChainMap({},*d.maps)?！纠?1.26】ChainMap對(duì)象示例>>>fromcollectionsimport*>>>m1={'a':1,'b':2};m2={'a':2,'x':3,'y':4};m=ChainMap(m1,m2)>>>m.maps#輸出：[{'a':1,'b':2},{'a':2,'x':3,'y':4}]>>>m.parents#輸出：ChainMap({'a':2,'x':3,'y':4})>>>m.new_child()#輸出：ChainMap({},{'a':1,'b':2},{'a':2,'x':3,'y':4})>>>m['a']#查詢鍵'a'的值。輸出：1>>>m['x']#查詢鍵'x'的值。輸出：3>>>m['a']=99#更新鍵'a'的值為99>>>m['x']=10#更新鍵'x'的值，因父map不能更新，故在子map中插入鍵/值對(duì)>>>m#輸出：ChainMap({'a':99,'b':2,'x':10},{'a':2,'x':3,'y':4})【例11.27】ChainMap對(duì)象應(yīng)用程序中參數(shù)值可以為默認(rèn)