Python是國際流行的用于教授入門級程序設計課程的語言，國內(nèi)高校也開始使用。本書是結合國內(nèi)數(shù)據(jù)結構課程現(xiàn)狀，以Python作為工作語言，編撰的一本數(shù)據(jù)結構教程。書中結合抽象數(shù)據(jù)類型結構的思想，基于Python的面向對象機制，討論了各種基本數(shù)據(jù)結構的思想、性質、問題和實現(xiàn)，相關算法的設計、實現(xiàn)和特性等。書中還研究了一些數(shù)據(jù)結構的應用案例。本書要求學習者已有基本Python程序設計的知識和經(jīng)驗，可以作為基于Python的計算機基礎課程中的數(shù)據(jù)結構課程教材，也可以作為學習Python語言基本內(nèi)容之后的面向對象等高級編程技術的進階讀物。
本書基于作者在北京大學用Python講授相應課程的經(jīng)驗，用Python作為工作語言討論數(shù)據(jù)結構和算法的基本問題。撰寫過程中主要有以下幾方面考慮：
●作為以Python為門計算機編程課程之后相應的數(shù)據(jù)結構課程的教材。
●結合數(shù)據(jù)結構和算法，討論Python中重要數(shù)據(jù)類型的實現(xiàn)情況和性質，幫助讀者理解Python語言程序，學習如何寫出高效的Python程序。
●展示Python的面向對象技術可以怎樣運用。書中構造了一批相互關聯(lián)的數(shù)據(jù)結構類，前面定義的類被反復應用在后續(xù)章節(jié)的數(shù)據(jù)結構和算法中。鑒于這些情況，本書不但可以作為數(shù)據(jù)結構課程的教材，也可以作為學習Python語言編程技術的后續(xù)讀物（假設讀者已經(jīng)有了Python編程的基本知識）。
由于Python語言的一些優(yōu)點，近年來，國外已經(jīng)有不少大學（包括許多一流大學）采用它作為門計算機科學技術課程的教學語言，國內(nèi)院校也已經(jīng)出現(xiàn)這種變化。作者在北京大學數(shù)學學院開設了基于Python語言的程序設計和數(shù)據(jù)結構課程，通過親身實踐，發(fā)現(xiàn)用Python講授這兩門課程也是一種很好的安排。
用Python學習數(shù)據(jù)結構，的優(yōu)點就是可以看到復雜的數(shù)據(jù)結構怎樣一步步地從基本的語言機制構造起來。在一個章節(jié)里定義的數(shù)據(jù)結構，經(jīng)�？梢栽诤罄m(xù)章節(jié)的算法和數(shù)據(jù)結構中直接使用，如果不適用，常�？梢酝ㄟ^簡單的類派生來調(diào)整。這些數(shù)據(jù)結構還可以非常方便地用在各種練習里，或用于解決實際問題。學生可以看到書中的（或他們自己寫的）代碼不是玩具，而是切實有用的軟件構件。在基于本書的課程中，很容易安排一些有一定規(guī)模的面向實際應用的開發(fā)課題，使學生得到更好的實際鍛煉。
第2版做了些內(nèi)容調(diào)整，主要是精簡了有關Python面向對象的討論，增加（或者充實）了廣義表和數(shù)組（3.6節(jié)）、等價類和查并集（6.8節(jié)）、平衡二叉樹的刪除操作（8.7.4節(jié)）、外存字典（8.8.4節(jié)）、外排序問題和算法（9.6節(jié)）等方面的內(nèi)容。本書覆蓋了大部分高校數(shù)據(jù)結構課程（教材）的基本內(nèi)容和研究生入學考試要求的數(shù)據(jù)結構知識。
本書的成型源于作者多年講授基于C語言的數(shù)據(jù)結構課程的經(jīng)驗，張乃孝老師的《算法與數(shù)據(jù)結構——C語言描述》是作者一直使用的教材，本書編寫時也參考了該書的一些體例。此外，北京大學數(shù)學學院2013級的學生在學習中提出了許多很好的問題，參加課程輔導工作的劉海洋、胡婷婷、張可和陳晨也提供了很多幫助。在此表示衷心的感謝。
裘宗燕
2021年9月于北京
裘宗燕: 北京大學數(shù)學學院信息科學系教授。長期從事計算機軟件與理論、程序設計語言和符號計算方面的研究和教學工作。已出版多部著作和譯著，包括《程序設計語言基礎》（譯著，北京大學出版社，1990），《Mathematica數(shù)學軟件系統(tǒng)的應用與程序設計》（編著，北京大學出版社，1994），《計算概論（上）》（合著，高等教育出版社，1997），《從問題到程序—程序設計與C語言引論》（編著，北京大學出版社，1999）等；自2000年以來，他先后為機械工業(yè)出版社華章分社翻譯了《程序設計實踐》（2000），《C++程序設計語言（特別版）》（2001），《C++語言的設計和演化》（2002），《程序設計語言——概念和結構》（2002），《從規(guī)范出發(fā)的程序設計》（2003），《計算機程序的構造和解釋》（2004）等一系列經(jīng)典著作，他認真的工作作風、嚴謹?shù)闹螌W態(tài)度，以及所做出的巨大貢獻，贏得廣大讀者的好評。 在北京大學教授的主要課程：計算概論（一年級本科生，主要內(nèi)容為C語言程序設計），程序設計技術與方法（本科生），程序設計語言原理（研究生），算法和數(shù)據(jù)結構（本科生），算法設計與分析（本科生和研究生），數(shù)理邏輯（本科生）等。 點擊進入[URL=http://www.math.pku.edu.cn/teachers/qiuzy/]作者主頁[/URL]。
前言
第1章 緒論1
1.1 計算機問題求解1
1.1.1 程序開發(fā)過程1
1.1.2 一個簡單例子3
1.2 問題求解：交叉路口的紅綠燈安排4
1.2.1 問題分析和嚴格化5
1.2.2 圖的頂點分組和算法6
1.2.3 算法的精化和Python描述7
1.2.4 討論8
1.3 算法和算法分析10
1.3.1 問題、問題實例和算法10
1.3.2 算法的代價及其度量13
1.3.3 算法分析19
1.3.4 Python程序的計算代價（復雜度）21
1.4 數(shù)據(jù)結構24
1.4.1 數(shù)據(jù)結構及其分類24
1.4.2 計算機內(nèi)存對象表示27
1.4.3 Python對象和數(shù)據(jù)結構30
練習32
第2章 抽象數(shù)據(jù)類型和Python類34
2.1 抽象數(shù)據(jù)類型34
2.1.1 數(shù)據(jù)類型和數(shù)據(jù)構造34
2.1.2 抽象數(shù)據(jù)類型的概念36
2.1.3 抽象數(shù)據(jù)類型的描述37
2.2 Python的類和面向對象編程39
2.2.1 類的定義和使用39
2.2.2 繼承44
2.2.3 異常類和自定義異常48
2.2.4 本書采用的ADT描述形式50
總結50
練習51
第3章 線性表53
3.1 線性表的概念和表抽象數(shù)據(jù)類型53
3.1.1 表的概念和性質53
3.1.2 表抽象數(shù)據(jù)類型53
3.1.3 線性表的實現(xiàn)：基本考慮55
3.2 順序表56
3.2.1 基本實現(xiàn)方式56
3.2.2 順序表基本操作的實現(xiàn)57
3.2.3 順序表的實現(xiàn)結構61
3.2.4 Python的list64
3.2.5 順序表的簡單總結65
3.3 鏈接表66
3.3.1 線性表的基本需要和鏈接表66
3.3.2 單鏈表67
3.3.3 單鏈表類的實現(xiàn)72
3.4 鏈表的變形和操作75
3.4.1 單鏈表的簡單變形75
3.4.2 循環(huán)單鏈表78
3.4.3 雙鏈表79
3.4.4 兩個鏈表操作81
3.4.5 在順序表里實現(xiàn)“鏈表”85
3.4.6 不同鏈表的簡單總結86
3.5 表的應用87
3.5.1 Josephus問題和基于數(shù)組概念的解法87
3.5.2 基于順序表的解88
3.5.3 基于循環(huán)單鏈表的解88
*3.6 廣義表和數(shù)組 本書中標星號的小節(jié)為選學/選講內(nèi)容。89
3.6.1 廣義表89
3.6.2 數(shù)組92
3.6.3 矩陣94
總結97
練習98
第4章 字符串102
4.1 字符集、字符串和字符串操作102
4.1.1 字符串的相關概念102
4.1.2 字符串抽象數(shù)據(jù)類型104
4.2 字符串的實現(xiàn)104
4.2.1 基本實現(xiàn)問題和技術104
4.2.2 實際語言里的字符串105
4.2.3 Python的字符串106
4.3 字符串匹配（子串查找）107
4.3.1 字符串匹配問題107
4.3.2 串匹配和樸素匹配算法108
4.3.3 無回溯串匹配算法（KMP算法）110
4.4 字符串匹配問題115
4.4.1 串匹配/搜索的不同需要115
4.4.2 一種簡化的正則表達式117
*4.5 Python正則表達式119
4.5.1 正則表達式標準庫包re119
4.5.2 基本情況119
4.5.3 主要操作120
4.5.4 正則表達式的構造121
4.5.5 正則表達式的使用127
總結127
練習128
第5章 棧和隊列130
5.1 概述130
5.1.1 棧、隊列和數(shù)據(jù)使用順序130
5.1.2 應用環(huán)境131
5.2 棧：概念和實現(xiàn)131
5.2.1 棧抽象數(shù)據(jù)類型131
5.2.2 棧的順序表實現(xiàn)132
5.2.3 棧的鏈接表實現(xiàn)134
5.3 棧的應用134
5.3.1 簡單應用：括號匹配問題135
5.3.2 表達式的表示、計算和變換137
5.3.3 棧與遞歸144
5.4 隊列149
5.4.1 隊列抽象數(shù)據(jù)類型149
5.4.2 隊列的鏈接表實現(xiàn)150
5.4.3 隊列的順序表實現(xiàn)150
5.4.4 隊列的list實現(xiàn)152
5.4.5 隊列的應用155
5.5 迷宮求解和狀態(tài)空間搜索156
5.5.1 迷宮求解：分析和設計156
5.5.2 求解迷宮的算法159
5.5.3 迷宮問題和搜索161
5.6 幾點補充166
5.6.1 與棧或隊列相關的幾種結構166
5.6.2 順序實現(xiàn)和鏈接實現(xiàn)166
總結167
練習168
第6章 二叉樹和樹170
6.1 二叉樹170
6.1.1 概念和性質170
6.1.2 抽象數(shù)據(jù)類型175
6.1.3 遍歷二叉樹176
6.2 二叉樹的list實現(xiàn)177
6.2.1 設計和實現(xiàn)178
6.2.2 二叉樹的簡單應用：表達式樹179
6.3 優(yōu)先隊列182
6.3.1 概念182
6.3.2 基于線性表的實現(xiàn)183
6.3.3 樹形結構和堆185
6.3.4 優(yōu)先隊列的堆實現(xiàn)186
6.3.5 堆的應用：堆排序189
6.4 應用：離散事件模擬190
6.4.1 通用的模擬框架191
6.4.2 海關檢查站模擬系統(tǒng)192
6.5 二叉樹的類實現(xiàn)196
6.5.1 二叉樹結點類197
6.5.2 遍歷算法198
6.5.3 二叉樹類202
6.6 哈夫曼樹203
6.6.1 哈夫曼樹和哈夫曼算法203
6.6.2 哈夫曼算法的實現(xiàn)204
6.6.3 哈夫曼編碼205
6.7 樹和樹林207
6.7.1 實例和表示207
6.7.2 定義和相關概念208
6.7.3 抽象數(shù)據(jù)類型和操作210
6.7.4 樹的實現(xiàn)211
6.7.5 樹的Python實現(xiàn)212
*6.8 等價類和查并集214
6.8.1 概念和問
新書資訊