數據結構與算法:Python 語言實現 (Data Structures and Algorithms in Python) 数据结构与算法:Python语言实现

[美]邁克爾 T. 古德里奇(Michael T. Goodrich) 羅伯特·塔馬

買這商品的人也買了...

商品描述

本書採用Python語言介紹數據結構和算法,包括其設計、分析和實施。

本書源代碼簡潔、明確,面向對象的觀點貫穿始終,通過繼承最大限度地提高代碼重用,同時彰顯不同抽象數據類型和算法之間的異同。

作者簡介

邁克爾·T.古德里奇(Michael T. Goodrich)加州大學歐文分校計算機科學系教授,之前是約翰·霍普金斯大學教授。
他是AAAS、ACM和IEEE會士,曾榮獲IEEE計算機協會技術成就獎和ACM卓越服務獎等。

羅伯托·塔馬西亞(Roberto Tamassia)布朗大學計算機科學系教授及系主任,兼任幾何計算中心主任。
他是AAAS、ACM和IEEE會士,曾榮獲IEEE計算機協會技術成就獎。

邁克爾·H.戈德瓦瑟(Michael H. Goldwasser)聖路易斯大學數學系和計算機科學系教授,兼任計算機科學項目主任,曾在芝加哥羅耀拉大學任教。

目錄大綱

出版者的話

譯者序

前言

致謝

作者簡介

第1章Python入門1 
1.1 Python概述1 
1.1.1 Python解釋器1 
1.1.2 Python程序預覽1 
1.2 Python對象2 
1.2.1標識符、對象和賦值語句2 
1.2 .2創建和使用對象4 
1.2.3 Python的內置類4 
1.3表達式、運算符和優先級8 
1.4控制流程12 
1.4.1條件語句12 
1.4.2循環語句14 
1.5函數16 
1.5.1信息傳遞17 
1.5.2 Python的內置函數19 
1.6簡單的輸入和輸出20 
1.6.1控制台輸入和輸出21 
1.6.2文件21 
1.7異常處理22 
1.7.1拋出異常23 
1.7.2捕捉異常24 
1.8迭代器和生成器26 
1.9 Python的其他便利特點28 
1.9.1條件表達式29 
1.9.2解析語法29 
1.9.3序列類型的打包和解包30
1.10作用域和命名空間31 
1.11模塊和import語句32 
1.12練習34 
擴展閱讀36 

第2章面向對象編程37 
2.1目標、原則和模式37 
2.1.1面向對象的設計目標37 
2.1.2面向對象的設計原則38 
2.1.3設計模式39 
2.2軟件開發40 
2.2.1設計40 
2.2.2偽代碼41 
2.2.3編碼風格和文檔42 
2.2.4測試和調試43 
2.3類定義44 
2.3.1例子:CreditCard類45 
2.3 .2運算符重載和Python的特殊方法48 
2.3.3例子:多維向量類50 
2.3.4迭代器51 
2.3.5例子:Range類52 
2.4繼承53 
2.4.1擴展CreditCard類54 
2.4.2數列的層次圖57 
2.4.3抽象基類60 
2.5命名空間和麵向對象62 
2.5.1實例和類命名空間62 
2.5.2名稱解析和動態調度65 
2.6深拷貝和淺拷貝65 
2.7練習67 
擴展閱讀70

第3章算法分析71 
3.1實驗研究71 
3.2本書使用的7種函數74 
3.2.1常數函數74 
3.2.2對數函數74 
3.2.3線性函數75 
3.2.4 n-log-n函數75 
3.2. 5二次函數76 
3.2.6三次函數和其他多項式77 
3.2.7指數函數77 
3.2.8比較增長率79 
3.3漸近分析79 
3.3.1大O符號80 
3.3.2比較分析82 
3.3.3算法分析示例84 
3.4簡單的證明技術89 
3.4.1示例89 
3.4.2反證法89 
3.4.3歸納和循環不變量90 
3.5練習91 
擴展閱讀95 

第4章遞歸96 
4.1說明性的例子96 
4.1.1階乘函數96 
4.1.2繪製英式標尺97 
4.1.3二分查找99 
4.1.4文件系統101 
4.2分析遞歸算法104 
4.3遞歸算法的不足106 
4.4遞歸的其他例子109 
4.4.1線性遞歸109
4.4.2二路遞歸112 
4.4.3多重遞歸113 
4.5設計遞歸算法114 
4.6消除尾遞歸115 
4.7練習116 
擴展閱讀118 

第5章基於數組的序列119 
5.1 Python序列類型119 
5.2低層次數組119 
5.2.1引用數組121 
5.2.2 Python中的緊湊數組122 
5.3動態數組和攤銷124 
5.3.1實現動態數組126 
5.3.2動態數組的攤銷分析127 
5.3.3 Python列表類130 
5.4 Python序列類型的效率130 
5.4.1 Python的列表和元組類130 
5.4.2 Python的字符串類134 
5.5使用基於數組的序列136 
5.5.1為遊戲存儲高分136 
5.5.2為序列排序138 
5.5.3簡單密碼技術140 
5.6多維數據集142 
5.7練習145 
擴展閱讀147 

第6章棧、隊列和雙端隊列148 
6.1棧148 
6.1.1棧的抽像數據類型148 
6.1.2簡單的基於數組的棧實現149
6.1.3使用棧實現數據的逆置152 
6.1.4括號和HTML標記匹配152 
6.2隊列155 
6.2.1隊列的抽像數據類型155 
6.2.2基於數組的隊列實現156 
6.3雙端隊列160 
6.3.1雙端隊列的抽像數據類型160 
6.3.2使用環形數組實現雙端隊列161 
6.3.3 Python collections模塊中的雙端隊列162 
6.4練習163 
擴展閱讀165 

第7章鍊錶166 
7.1單向鍊錶166 
7.1.1用單向鍊錶實現棧169 
7.1.2用單向鍊錶實現隊列171 
7.2循環鍊錶173 
7.2.1輪轉調度173 
7.2.2用循環鍊錶實現隊列174 
7.3雙向鍊錶175 
7.3.1雙向鍊錶的基本實現177 
7.3. 2用雙向鍊錶實現雙端隊列179 
7.4位置列表的抽像數據類型180 
7.4.1含位置信息的列表抽像數據類型182 
7.4.2雙向鍊錶實現183 
7.5位置列表的排序186 
7.6案例研究:維護訪問頻率186 
7.6.1使用有序表187
7.6.2啟發式動態調整列表188 
7.7基於鏈接的序列與基於數組的序列190 
7.8練習192 
擴展閱讀195 

第8章樹196 
8.1樹的基本概念196 
8.1.1樹的定義和屬性196 
8.1.2樹的抽像數據類型199 
8.1.3計算深度和高度201 
8.2二叉樹203 
8.2.1二叉樹的抽像數據類型204 
8.2.2二叉樹的屬性206 
8.3樹的實現207 
8.3.1二叉樹的鍊式存儲結構207 
8.3.2基於數組表示的二叉樹212 
8.3.3一般樹的鍊式存儲結構214 
8.4樹的遍曆算法214 
8.4.1樹的先序和後序遍歷214 
8.4.2樹的廣度優先遍歷216