程序設(shè)計(jì)抽象思想：C語言描述

定　價(jià)：￥78.00

作　者：	（美）Eric S.Roberts著；閃四清譯；閃四清譯
出版社：	清華大學(xué)出版社
叢編項(xiàng)：	國(guó)外經(jīng)典教材·計(jì)算機(jī)科學(xué)與技術(shù)
標(biāo)　簽：	C

購(gòu)買這本書可以去

ISBN：	9787302101659	出版時(shí)間：	2005-06-01	包裝：	平裝
開本：	26cm	頁(yè)數(shù)：	665	字?jǐn)?shù)：

內(nèi)容簡(jiǎn)介

　　本書全面介紹了數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)內(nèi)容，幫助學(xué)生深入了解軟件工程的思想和技術(shù)。學(xué)生還可以通過對(duì)一些高級(jí)編程概念（如接口、抽象和封裝）的了解，為進(jìn)一步深入學(xué)習(xí)高級(jí)編程知識(shí)打下堅(jiān)實(shí)的基礎(chǔ)。本書觀點(diǎn)清晰明了、語言風(fēng)格鮮明獨(dú)特，深入淺出地介紹了一些高級(jí)主題。本書特色：◆介紹了多個(gè)庫(kù)包，可用于簡(jiǎn)化編程流程，使學(xué)生可以專注于高層次理論問題的研究，避免了C語言編程的繁瑣細(xì)節(jié)；◆詳細(xì)討論了遞歸編程的用法，包括大量難度各異的編程示例和練習(xí)，如簡(jiǎn)單的遞歸函數(shù)，分析雙人游戲的最小最大（minimax）策略，等等；◆幫助讀者培養(yǎng)編寫健壯、可重用代碼的良好編程習(xí)慣。本書前言寫給教師本教程適用于大學(xué)編程課程，它覆蓋了AMCCurriculum78報(bào)告中所定義的計(jì)算機(jī)科學(xué)2標(biāo)準(zhǔn)課程的材料，并且包括ComputingCurriculum1991算法與數(shù)據(jù)結(jié)構(gòu)課程中的大部分知識(shí)。本書將教會(huì)學(xué)生現(xiàn)代軟件工程方法論。本書的內(nèi)容建立在我于1995年寫的TheArtandScienceofC教科書的基礎(chǔ)上，并將抽象和接口設(shè)計(jì)作為核心主題。雖然我寫作這兩本書是有先后順序的，但是讀者完全可以單獨(dú)使用本書。本書的第Ⅰ部分包括了TheArtandScienceofC中學(xué)生應(yīng)該掌握的所有背景知識(shí)。這些背景知識(shí)對(duì)于理解本課程其他部分中的例子和方法已經(jīng)綽綽有余了。由于第Ⅰ部分的介紹是比較簡(jiǎn)單，因此學(xué)生必須熟悉計(jì)算機(jī)基礎(chǔ)課程中涉及的基本編程概念。但是，讀者不需要對(duì)C語言有所了解，因?yàn)樵诒緯那皫渍轮袑⒔榻BC語言的基礎(chǔ)。學(xué)習(xí)過TheArtandScienaofC課程的學(xué)生完全可以跳過第Ⅰ部分的內(nèi)容。在學(xué)習(xí)完了第Ⅰ部分的預(yù)備知識(shí)之后，學(xué)生可以繼續(xù)該課程的學(xué)習(xí)。第Ⅱ部分將討論遞歸算法。在第Ⅱ部分的4章內(nèi)容中，穿插了大量的實(shí)例。根據(jù)我個(gè)人的經(jīng)驗(yàn)，介紹遞歸算法的最合理時(shí)刻是在第Ⅱ門編程課程開始學(xué)習(xí)的時(shí)候。很多學(xué)生都會(huì)覺得遞歸是一個(gè)難以理解的概念，必須花很多時(shí)間才能較好地掌握它。如果在新學(xué)期的一開始就面臨遞歸這個(gè)難點(diǎn)，那么學(xué)生將有更多的時(shí)間來掌握它。在本書中，盡可能早地介紹遞歸概念，其目的是讓讀者在作業(yè)和考試中運(yùn)用這種知識(shí)。期中考試可以檢查學(xué)生對(duì)遞歸概念的掌握情況，對(duì)于那些確確實(shí)實(shí)理解遞歸概念比較差的學(xué)生，可以給他們以警示，以便他們及時(shí)采取相應(yīng)的補(bǔ)救措施。如果想壓縮學(xué)習(xí)遞歸的時(shí)間，那么可以跳過第Ⅱ部分的6.1節(jié)，這對(duì)整個(gè)課程的講述沒有什么影響。也許鞍點(diǎn)算法對(duì)于部分學(xué)生來說有點(diǎn)兒太復(fù)雜了，但是它卻很好地說明遞歸算法可以使用很少的代碼來解決非常困難的問題。類似地，第7章中大O的理論基礎(chǔ)也不是該課程的重點(diǎn)內(nèi)容。第Ⅲ部分有雙重目的：一方面，它介紹了數(shù)據(jù)結(jié)構(gòu)課程中涉及的非遞歸算法的概念，包括堆棧、隊(duì)列以及符號(hào)表；另一方面，這部分為學(xué)生提供了一些工具，從而幫助學(xué)生理解其他部分中涉及的基于接口編程的數(shù)據(jù)抽象概念。與這個(gè)概念相一致的是抽象數(shù)據(jù)類型（ADT），它是由行為而不是由表現(xiàn)形式定義。本書的一個(gè)重要特點(diǎn)是，它不完全使用ANSIC的工具來定義ADT，其中ADT的內(nèi)部表示對(duì)于客戶端來說是不可訪問的。由于這樣的編程風(fēng)格強(qiáng)調(diào)了抽象的難度，因此可以培養(yǎng)學(xué)生具有編寫良好結(jié)構(gòu)的程序和模塊的習(xí)慣。我認(rèn)為在本書中學(xué)習(xí)的接口是個(gè)實(shí)用的工具。在許多情況下，學(xué)生可以在他們自己的代碼中包含和實(shí)現(xiàn)這些接口。在第Ⅲ部分的最后一章，即第11章，將介紹幾個(gè)重要的概念，例如，函數(shù)指針、映射函數(shù)以及迭代器。相對(duì)來說，迭代器在斯坦福大學(xué)的課程中是新近加入的，但是教學(xué)效果相當(dāng)好。根據(jù)我們的經(jīng)驗(yàn)，減少客戶代碼的復(fù)雜性所帶來的收益遠(yuǎn)遠(yuǎn)超過建立迭代器抽象所做工作的代價(jià)。第Ⅲ和第Ⅳ部分的重點(diǎn)是抽象數(shù)據(jù)類型。在某種程度上，這是人為劃分的結(jié)果。這兩部分的不同之處在于，第Ⅳ部分中的抽象數(shù)據(jù)類型是用遞歸實(shí)現(xiàn)的，而第Ⅲ部分則不是。這樣安排的好處是第Ⅳ部分在本書中起到綜合的作用，將前兩部分的遞歸和ADT進(jìn)行綜合。盡管第14章中關(guān)于表達(dá)式樹的內(nèi)容可以跳過，但是我發(fā)現(xiàn)盡早地在課程中包括這些內(nèi)容是很有價(jià)值的，因?yàn)檫@樣可以減少對(duì)C語言編譯器操作的神秘感，可以幫助學(xué)生更好地理解和控制程序。第17章確實(shí)不是本課程的主要內(nèi)容，而是為學(xué)生繼續(xù)接下來的學(xué)習(xí)作的預(yù)備。本章主要使用Java語言介紹面向?qū)ο缶幊?，講述主要的概念。盡管有些機(jī)構(gòu)已經(jīng)開始采用由淺入深的順序方式介紹Java，但是我們認(rèn)為，由于下列一些原因，先介紹結(jié)構(gòu)化編程方法再介紹面向?qū)ο缶幊谭椒ㄊ呛苡幸饬x的：1.Java環(huán)境的變化太快了，無法為教學(xué)提供穩(wěn)固的基礎(chǔ)；2.學(xué)生有必要理解結(jié)構(gòu)化編程方法；3.如果在基礎(chǔ)課程中強(qiáng)調(diào)數(shù)據(jù)抽象和接口，那么學(xué)生學(xué)習(xí)面向?qū)ο缶幊虒⒏尤菀?。在斯坦福大學(xué)的經(jīng)驗(yàn)給我們的啟示是，這種策略很有效，它能夠使學(xué)生相對(duì)容易地接受面向?qū)ο蟮母拍睢?/div>

作者簡(jiǎn)介

　　EricS.Roberts于1980年在哈佛大學(xué)獲取了應(yīng)用數(shù)學(xué)的博士學(xué)位，畢業(yè)后在Wellesley大學(xué)創(chuàng)建了計(jì)算機(jī)科學(xué)系并擔(dān)任主任，隨后在加利福尼亞的DigitalEquipemntCorporation的系統(tǒng)研發(fā)中心擔(dān)任了5年的調(diào)研員，現(xiàn)就職于斯坦福大學(xué)計(jì)算機(jī)科學(xué)系，并擔(dān)任斯坦福大學(xué)教務(wù)部主任。作為一位知名教授，Roberts還編寫過TheArtandScienceofC等經(jīng)典教材。閃四清，大學(xué)教師，長(zhǎng)期從事數(shù)據(jù)庫(kù)、數(shù)據(jù)挖掘、數(shù)據(jù)結(jié)構(gòu)等方面的數(shù)學(xué)、學(xué)術(shù)研究。已經(jīng)發(fā)表學(xué)術(shù)論文30多篇，翻譯、編寫了《數(shù)據(jù)庫(kù)系統(tǒng)原理和應(yīng)用》等多部著作。相關(guān)圖書C++精解和程序設(shè)計(jì)（第4版）數(shù)據(jù)庫(kù)原理（第2版）C++簡(jiǎn)明教程精通Office商務(wù)應(yīng)用完美C++教程C語言教程：模塊化程序設(shè)計(jì)（第2版）TCP/IP網(wǎng)絡(luò)互聯(lián)技術(shù)（卷3）：客戶-服務(wù)器編程與應(yīng)用（Windows套接字版）信息技術(shù)基礎(chǔ)（第3版）

圖書目錄

第Ⅰ部分預(yù)備知識(shí)
第1章 ANSI C概述 1
1.1 什么是C 1
1.2 C程序的結(jié)構(gòu) 3
1.2.1 注釋 4
1.2.2 庫(kù)包含 5
1.2.3 程序級(jí)定義 5
1.2.4 函數(shù)原型 5
1.2.5 main程序 6
1.2.6 函數(shù)定義 7
1.3 變量、值和類型 7
1.3.1 變量 7
1.3.2 命名規(guī)則 8
1.3.3 局部變量和全局變量 9
1.3.4 數(shù)據(jù)類型的概念 9
1.3.5 整數(shù)類型 9
1.3.6 浮點(diǎn)類型 10
1.3.7 文本類型 11
1.3.8 布爾類型 12
1.3.9 簡(jiǎn)單的輸入與輸出 12
1.4 表達(dá)式 14
1.4.1 優(yōu)先級(jí)與結(jié)合性 14
1.4.2 表達(dá)式中的類型混合 15
1.4.3 整數(shù)除法和求余運(yùn)算符 16
1.4.4 類型轉(zhuǎn)換 17
1.4.5 賦值運(yùn)算符 17
1.4.6 遞增與遞減運(yùn)算符 19
1.4.7 布爾運(yùn)算符 20
1.5 語句 22
1.5.1 簡(jiǎn)單語句 22
1.5.2 塊 22
1.5.3 if語句 23
1.5.4 switch語句 23
1.5.5 while語句 25
1.5.6 for語句 28
1.6 函數(shù) 29
1.6.1 返回函數(shù)結(jié)果 29
1.6.2 函數(shù)定義和原型 30
1.6.3 函數(shù)調(diào)用過程的機(jī)制 30
1.6.4 逐步求精 31
1.7 小結(jié) 31
1.8 復(fù)習(xí)題 32
1.9 編程練習(xí) 33
第2章 C的數(shù)據(jù)類型 38
2.1 枚舉類型 38
2.1.1 枚舉類型的內(nèi)部表示 39
2.1.2 標(biāo)量類型 40
2.1.3 理解typedef 41
2.2 數(shù)據(jù)和內(nèi)存 41
2.2.1 位、字節(jié)、字 42
2.2.2 內(nèi)存地址 42
2.3 指針 44
2.3.1 把地址當(dāng)作數(shù)值 44
2.3.2 聲明指針變量 45
2.3.3 基本的指針運(yùn)算 45
2.3.4 特殊指針NULL 47
2.3.5 通過引用傳遞參數(shù) 48
2.4 數(shù)組 51
2.4.1 聲明數(shù)組 51
2.4.2 數(shù)組選擇 52
2.4.3 有效空間和已分配空間 53
2.4.4 作為參數(shù)傳遞數(shù)組 54
2.4.5 初始化數(shù)組 56
2.4.6 多維數(shù)組 57
2.5 指針和數(shù)組 59
2.5.1 指針運(yùn)算 60
2.5.2 指針的自加和自減 62
2.5.3 指針和數(shù)組的關(guān)系 62
2.6 記錄 64
2.6.1 定義一種新的結(jié)構(gòu)類型 65
2.6.2 聲明結(jié)構(gòu)變量 66
2.6.3 記錄選擇 66
2.6.4 初始化紀(jì)錄 66
2.6.5 記錄的指針 67
2.7 動(dòng)態(tài)分配 68
2.7.1 類型void* 68
2.7.2 應(yīng)對(duì)內(nèi)存限制 70
2.7.3 動(dòng)態(tài)數(shù)組 71
2.7.4 動(dòng)態(tài)記錄 72
2.8 小結(jié) 73
2.9 復(fù)習(xí)題 74
2.10 編程練習(xí) 76
第3章庫(kù)和接口 83
3.1 接口的概念 83
3.1.1 接口和實(shí)現(xiàn) 84
3.1.2 包和抽象 84
3.1.3 良好的接口設(shè)計(jì)規(guī)則 85
3.2 隨機(jī)數(shù)字 85
3.2.1 random.h接口的結(jié)構(gòu) 86
3.2.2 構(gòu)建客戶程序 89
3.2.3 有關(guān)隨機(jī)數(shù)字的ANSI函數(shù) 91
3.2.4 實(shí)現(xiàn)random.c 93
3.3 字符串 96
3.3.1 字符串的底層表示 96
3.3.2 數(shù)據(jù)類型string 97
3.3.3 ANSI字符串庫(kù) 98
3.3.4 接口strlib.h 102
3.4 標(biāo)準(zhǔn)的I/O庫(kù) 108
3.4.1 數(shù)據(jù)文件 108
3.4.2 在C中使用文件 109
3.4.3 標(biāo)準(zhǔn)文件 110
3.4.4 字符I/O 110
3.4.5 從輸入文件中重讀字符 111
3.4.6 更新文件 112
3.4.7 面向行的I/O 113
3.4.8 格式化的I/O 114
3.4.9 scanf函數(shù) 115
3.5 其他ANSI庫(kù) 116
3.6 小結(jié) 118
3.7 復(fù)習(xí)題 118
3.8 編程練習(xí) 120
第Ⅱ部分遞歸和算法分析
第4章遞歸入門 127
4.1 一個(gè)簡(jiǎn)單的遞歸示例 128
4.2 階乘函數(shù) 129
4.2.1 Fact的遞歸公式 130
4.2.2 追蹤遞歸過程 130
4.2.3 遞歸跳躍的信任 134
4.3 費(fèi)波那契函數(shù) 134
4.3.1 計(jì)算費(fèi)波那契序列 135
4.3.2 增進(jìn)實(shí)現(xiàn)遞歸的信心 136
4.3.3 遞歸實(shí)現(xiàn)的效率 137
4.3.4 不應(yīng)該責(zé)備遞歸 138
4.4 其他遞歸示例 139
4.4.1 探測(cè)回文 139
4.4.2 二分查找 142
4.4.3 交互遞歸 143
4.5 以遞歸的方式思考 144
4.5.1 保持整體觀 145
4.5.2 避免常見的錯(cuò)誤 145
4.6 小結(jié) 146
4.7 復(fù)習(xí)題 147
4.8 編程練習(xí) 149
第5章遞歸過程 152
5.1 漢諾塔 152
5.1.1 分解問題 153
5.1.2 尋找遞歸策略 153
5.1.3 驗(yàn)證遞歸策略 155
5.1.4 解決方案的編碼 156
5.1.5 追蹤遞歸過程 156
5.2 產(chǎn)生排列 160
5.3 遞歸在繪圖中的應(yīng)用 162
5.3.1 圖形庫(kù) 162
5.3.2 電腦藝術(shù)示例 165
5.3.3 不規(guī)則碎片形 169
5.4 小結(jié) 173
5.5 復(fù)習(xí)題 174
5.6 編程練習(xí) 175
第6章回溯算法 183
6.1 用遞歸回溯解決迷宮問題 183
6.1.1 右手規(guī)則 183
6.1.2 尋找遞歸方法 184
6.1.3 識(shí)別簡(jiǎn)單情景 185
6.1.4 編寫迷宮解決方案算法 186
6.1.5 確信解決方案可以正確運(yùn)行 190
6.2 回溯與游戲 192
6.2.1 拿子游戲 193
6.2.2 常規(guī)化的雙人游戲程序 199
6.2.3 最小最大策略 200
6.2.4 實(shí)現(xiàn)最小最大化算法 202
6.2.5 在具體的游戲中采用常規(guī)策略 204
6.3 小結(jié) 216
6.4 復(fù)習(xí)題 217
6.5 編程練習(xí) 218
第7章算法分析 225
7.1 排序問題 225
7.1.1 選擇排序算法 226
7.1.2 性能的經(jīng)驗(yàn)度量 227
7.1.3 分析選擇排序的性能 228
7.2 計(jì)算復(fù)雜度 230
7.2.1 大O符號(hào) 230
7.2.2 大O的標(biāo)準(zhǔn)簡(jiǎn)化 230
7.2.3 排序算法的計(jì)算復(fù)雜度 231
7.2.4 根據(jù)代碼結(jié)構(gòu)預(yù)測(cè)計(jì)算復(fù)雜度 232
7.2.5 最差情況復(fù)雜度與平均情況復(fù)雜度 233
7.2.6 大O的正式定義 233
7.3 遞歸幫助 235
7.3.1 分治策略的威力 235
7.3.2 合并兩個(gè)數(shù)組 236
7.3.3 合并排序算法 237
7.3.4 合并排序的計(jì)算復(fù)雜度 239
7.3.5 比較N2和NlogN的性能 240
7.4 標(biāo)準(zhǔn)復(fù)雜度類型 241
7.5 快速排序算法 242
7.5.1 分割數(shù)組 244
7.5.2 分析快速排序的性能 246
7.6 數(shù)學(xué)歸納法 247
7.7 小結(jié) 250
7.8 復(fù)習(xí)題 250
7.9 編程練習(xí) 252
第Ⅲ部分數(shù)據(jù)抽象
第8章抽象數(shù)據(jù)類型 257
8.1 堆棧 258
8.1.1 基本的堆棧比喻 258
8.1.2 堆棧和函數(shù)調(diào)用 258
8.1.3 堆棧和袖珍計(jì)算器 259
8.2 定義堆棧的ADT 259
8.2.1 定義堆棧抽象的類型 260
8.2.2 不透明類型 261
8.2.3 定義stack.h接口 262
8.3 在應(yīng)用程序中使用堆棧 265
8.4 實(shí)現(xiàn)堆棧抽象 269
8.4.1 定義具體類型 269
8.4.2 實(shí)現(xiàn)堆棧操作 269
8.4.3 不透明類型的優(yōu)點(diǎn) 271
8.4.4 改進(jìn)stack.c的實(shí)現(xiàn) 272
8.5 定義掃描器ADT 273
8.5.1 封裝狀態(tài)的危險(xiǎn) 274
8.5.2 抽象數(shù)據(jù)類型作為封裝狀態(tài)的替代 274
8.5.3 實(shí)現(xiàn)掃描器抽象 279
8.6 小結(jié) 283
8.7 復(fù)習(xí)題 284
8.8 編程練習(xí) 285
第9章效率與ADT 297
9.1 編輯器緩沖區(qū)的概念 297
9.2 定義緩沖區(qū)抽象 298
9.2.1 接口buffer.h中的函數(shù) 299
9.2.2 為編輯器應(yīng)用程序編寫代碼 301
9.3 用數(shù)組實(shí)現(xiàn)編輯器 303
9.3.1 定義具體類型 303
9.3.2 實(shí)現(xiàn)緩沖區(qū)的操作 304
9.3.3 數(shù)組實(shí)現(xiàn)的計(jì)算復(fù)雜度 308
9.4 用堆棧實(shí)現(xiàn)編輯器 309
9.4.1 定義基于堆棧的緩沖區(qū)的具體結(jié)構(gòu) 310
9.4.2 實(shí)現(xiàn)緩沖區(qū)的操作 310
9.4.3 比較計(jì)算復(fù)雜度 313
9.5 用鏈表實(shí)現(xiàn)編輯器 313
9.5.1 鏈表的概念 314
9.5.2 設(shè)計(jì)鏈表數(shù)據(jù)結(jié)構(gòu) 314
9.5.3 使用鏈表表示緩沖區(qū) 316
9.5.4 鏈表緩沖區(qū)中的插入 317
9.5.5 鏈表緩沖區(qū)中的刪除 320
9.5.6 鏈表表示中的光標(biāo)移動(dòng) 321
9.5.7 鏈表的習(xí)慣用法 323
9.5.8 完成緩沖區(qū)實(shí)現(xiàn) 324
9.5.9 鏈表緩沖區(qū)的計(jì)算復(fù)雜度 328
9.5.10 雙向鏈表 328
9.5.11 時(shí)間-空間的權(quán)衡 329
9.6 小結(jié) 329
9.7 復(fù)習(xí)題 330
9.8 編程練習(xí) 331
第10章線性結(jié)構(gòu) 337
10.1 堆?；仡?337
10.2 隊(duì)列 344
10.2.1 接口queue.h的結(jié)構(gòu) 344
10.2.2 基于數(shù)組的隊(duì)列實(shí)現(xiàn) 347
10.2.3 隊(duì)列的鏈表實(shí)現(xiàn) 351
10.3 使用隊(duì)列的仿真 355
10.3.1 仿真與模型 356
10.3.2 排隊(duì)模型 356
10.3.3 離散時(shí)間 356
10.3.4 仿真時(shí)間中的事件 357
10.3.5 實(shí)現(xiàn)仿真 357
10.4 小結(jié) 364
10.5 復(fù)習(xí)題 365
10.6 編程練習(xí) 366
第11章符號(hào)表 371
11.1 定義符號(hào)表抽象 371
11.1.1 選擇值和鍵的類型 372
11.1.2 表示未定義項(xiàng) 373
11.1.3 符號(hào)表接口的初始版本 373
11.2 散列 375
11.2.1 實(shí)現(xiàn)散列表策略 375
11.2.2 選擇散列函數(shù) 380
11.2.3 確定桶的數(shù)量 381
11.3 初級(jí)接口的限制 382
11.4 使用函數(shù)作為數(shù)據(jù) 384
11.4.1 通用繪圖函數(shù) 384
11.4.2 聲明函數(shù)指針與函數(shù)類 385
11.4.3 實(shí)現(xiàn)PlotFunction 386
11.4.4 qsort函數(shù) 387
11.5 映射函數(shù) 391
11.5.1 映射符號(hào)表中的所有項(xiàng) 391
11.5.2 實(shí)現(xiàn)MapSymbolTable 394
11.5.3 向回調(diào)函數(shù)傳遞客戶數(shù)據(jù) 395
11.6 迭代器 396
11.6.1 使用迭代器 396
11.6.2 定義迭代器接口 397
11.6.3 實(shí)現(xiàn)針對(duì)符號(hào)表的迭代器抽象 398
11.7 命令分派表 401
11.8 小結(jié) 404
11.9 復(fù)習(xí)題 405
11.10 編程練習(xí) 406
第Ⅳ部分遞歸數(shù) 據(jù)
第12章遞歸鏈表 411
12.1 鏈表的遞歸表述 412
12.2 定義抽象鏈表類型 413
12.2.1 不變類型 416
12.2.2 操縱鏈表結(jié)構(gòu)的函數(shù) 417
12.2.3 連接多個(gè)鏈表 419
12.2.4 不變類型間的內(nèi)部共享 421
12.3 使用鏈表表示大整數(shù) 422
12.3.1 bigint.h接口 423
12.3.2 表示類型bigIntADT 425
12.3.3 實(shí)現(xiàn)bigint包 426
12.3.4 使用bigint.h包 430
12.4 小結(jié) 432
12.5 復(fù)習(xí)題 433
12.6 編程練習(xí) 434
第13章樹 438
13.1 家譜樹 438
13.1.1 描述樹的術(shù)語 439
13.1.2 樹的遞歸特性 439
13.1.3 用C語言表示家譜樹 440
13.2 二叉搜索樹 441
13.2.1 使用二叉搜索樹的底層動(dòng)機(jī) 442
13.2.2 在二叉搜索樹中查找節(jié)點(diǎn) 443
13.2.3 在二叉搜索樹中插入新節(jié)點(diǎn) 444
13.2.4 樹的遍歷 447
13.3 平衡樹 449
13.3.1 樹的平衡策略 450
13.3.2 舉例說明AVL的思想 451
13.3.3 單旋轉(zhuǎn) 452
13.3.4 雙旋轉(zhuǎn) 454
13.3.5 實(shí)現(xiàn)AVL算法 455
13.4 為二叉搜索樹定義通用接口 458
13.4.1 允許客戶定義節(jié)點(diǎn)結(jié)構(gòu) 462
13.4.2 泛化鍵的類型 465
13.4.3 刪除節(jié)點(diǎn) 465
13.4.4 實(shí)現(xiàn)二叉搜索樹包 467
13.4.5 使用二叉樹實(shí)現(xiàn)symtab.h接口 472
13.5 小結(jié) 474
13.6 復(fù)習(xí)題 474
13.7 編程練習(xí) 477
第14章表達(dá)式樹 484
14.1 解釋器概述 484
14.2 表達(dá)式的抽象結(jié)構(gòu) 487
14.2.1 表達(dá)式的遞歸定義 487
14.2.2 歧義性 488
14.2.3 表達(dá)式樹 489
14.2.4 定義表達(dá)式的抽象接口 490
14.3 定義具體表達(dá)式類型 494
14.3.1 聯(lián)合類型 494
14.3.2 用帶標(biāo)記聯(lián)合表示表達(dá)式 496
14.3.3 可視化具體表示 498
14.3.4 實(shí)現(xiàn)構(gòu)造器和選擇器函數(shù) 500
14.4 分析表達(dá)式 502
14.4.1 語法分析和語法 502
14.4.2 不考慮優(yōu)先級(jí)的語法分析 503
14.4.3 在語法分析器中加入優(yōu)先級(jí) 507
14.5 計(jì)算表達(dá)式 509
14.6 小結(jié) 511
14.7 復(fù)習(xí)題 512
14.8 編程練習(xí) 513
第15章集合 525
15.1 作為數(shù)學(xué)抽象的集合 525
15.1.1 成員資格 526
15.1.2 集合運(yùn)算 526
15.1.3 集合恒等式 527
15.2 設(shè)計(jì)集合接口 529
15.2.1 定義元素類型 529
15.2.2 編寫set.h 接口 531
15.2.3 字符集合 534
15.2.4 使用指針集合來避免重復(fù) 535
15.3 實(shí)現(xiàn)集合包 537
15.4 設(shè)計(jì)多態(tài)迭代器 544
15.4.1 泛化迭代器函數(shù)的原型 544
15.4.2 在迭代器中實(shí)現(xiàn)多態(tài)性 545
15.4.3 導(dǎo)出聚集類型 546
15.4.4 編碼迭代器包 550
15.4.5 foreach的習(xí)慣用法 554
15.5 提高整數(shù)集合的效率 554
15.5.1 特征向量 555
15.5.2 壓縮的位數(shù)組 555
15.5.3 位運(yùn)算符 556
15.5.4 使用位運(yùn)算符實(shí)現(xiàn)特征向量 559
15.5.5 實(shí)現(xiàn)高級(jí)集合操作 561
15.5.6 使用混合實(shí)現(xiàn) 561
15.6 小結(jié) 561
15.7 復(fù)習(xí)題 563
15.8 編程練習(xí) 565
第16章圖 570
16.1 圖的結(jié)構(gòu) 570
16.1.1 有向圖和無向圖 572
16.1.2 路徑和環(huán) 573
16.1.3 連通性 573
16.2 圖的實(shí)現(xiàn)策略 574
16.2.1 使用鄰接列表表示連接 575
16.2.2 使用鄰接矩陣表示連接 578
16.3 擴(kuò)展圖抽象 581
16.3.1 將數(shù)據(jù)與節(jié)點(diǎn)和圖關(guān)聯(lián) 581
16.3.2 顯式弧 581
16.3.3 迭代和圖 582
16.3.4 分層抽象 583
16.3.5 基于集合的圖接口 584
16.4 圖的遍歷 592
16.4.1 深度優(yōu)先遍歷 593
16.4.2 廣度優(yōu)先搜索 595
16.5 尋找最短路徑 597
16.6 小結(jié) 604
16.7 復(fù)習(xí)題 605
16.8 編程練習(xí) 607
第17章展望Java 614
17.1 面向?qū)ο蠓妒?614
17.1.1 面向?qū)ο缶幊痰臍v史 615
17.1.2 對(duì)象、類和方法 616
17.1.3 類層次結(jié)構(gòu)與繼承 616
17.2 Java簡(jiǎn)介 618
17.2.1 Web結(jié)構(gòu) 618
17.2.2 applet 619
17.2.3 執(zhí)行Java applet 623
17.3 Java結(jié)構(gòu) 624
17.3.1 Java的語法 625
17.3.2 Java中的原子類型 626
17.3.3 定義一個(gè)新類 626
17.3.4 構(gòu)造器方法 628
17.3.5 this關(guān)鍵字 628
17.3.6 定義方法 629
17.3.7 定義子類 631
17.4 Java中的預(yù)定義類 637
17.4.1 String類 637
17.4.2 Hashtable類 638
17.4.3 原子類型的對(duì)象包裝器 641
17.4.4 Vector類 641
17.4.5 Stack類 643
17.5 創(chuàng)建交互式applet的工具 644
17.5.1 組件與容器 644
17.5.2 action方法 645
17.5.3 用于繪制簡(jiǎn)單圖形的applet 646
17.5.4 更進(jìn)一步 654
17.6 小結(jié) 654
17.8 復(fù)習(xí)題 654
17.9 編程練習(xí) 656