第1章 準(zhǔn)備旅行
1.1 我們要去哪兒
本章計劃
1.2 數(shù)學(xué)、科學(xué)和工程學(xué)合而為
1.3 尋找計算機(jī)科學(xué)中的持久原則
1.4 軟件系統(tǒng)結(jié)構(gòu)的原則
1.5 效率與權(quán)衡
1.6 軟件工程原則
1.7 數(shù)學(xué)方法
1.8 關(guān)于編程符號的一些注釋
1.9 后續(xù)內(nèi)容簡介
1.10 本章小結(jié)
第2章 面向?qū)ο缶幊虒?dǎo)論
2.1 介紹
本章計劃
2.2 繪制矩形ApPkt
2.2.1 學(xué)習(xí)內(nèi)容
2.2.2 復(fù)習(xí)題
2.2.3 練習(xí)
2.3 Draw5hapes Applet
2.3.1 學(xué)習(xí)內(nèi)容
2.3.2 復(fù)習(xí)題
2.3.3 練習(xí)
2.4 結(jié)論
2.4.1 學(xué)習(xí)內(nèi)容
2.4.2 復(fù)習(xí)題
2.4.3 練習(xí)
2.5 陷阱
2.6 提示和技巧
2.7 參考資料
2.8 本章小結(jié)
第3章 鏈?zhǔn)綌?shù)據(jù)表示
3.1 介紹
本章計劃
3.2 什么是指針
3.2.1 學(xué)習(xí)內(nèi)容
3.2.2 鏈?zhǔn)奖硎镜膬蓚€實(shí)例
3.3 使用Java的隱式指針
3.3.1 學(xué)習(xí)內(nèi)容
3.3.2 復(fù)習(xí)題
3.3.3 練習(xí)
3.4 指針圖例表示法
3.4.1 學(xué)習(xí)內(nèi)容
3.4.2 復(fù)習(xí)題
3.4.3 練習(xí)
3.5 線性鏈表
3.5.1 學(xué)習(xí)內(nèi)容
3.5.2 在鏈表中插入新的次節(jié)點(diǎn)
3.5.3 聲明Java鏈表類
3.5.4 在鏈表中搜索某節(jié)點(diǎn)項(xiàng)
3.5.5 刪除鏈表的末端節(jié)點(diǎn)
3.5.6 在鏈表中插入新的末端節(jié)點(diǎn)
3.5.7 如何打印鏈表
3.5.8 把所有東西合在一起
3.5.9 現(xiàn)在還要做什么
3.5.10 復(fù)習(xí)題
3.5.11 練習(xí)
3.6 其他鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)
3.6.1 學(xué)習(xí)內(nèi)容
3.6.2 復(fù)習(xí)題
3.6.3 練習(xí)
3.7 陷阱
3.8 提示與技巧
3.9 參考資料
3.10 本章小結(jié)
第4章 遞歸
4.1 介紹
本章計劃
4.2 遞歸地思考
4.2.1 學(xué)習(xí)內(nèi)容
4.2.2 如何遞歸累加
4.2.3 調(diào)用樹與調(diào)用軌跡
4.2.4 遞歸連乘
4.2.5 逆轉(zhuǎn)鏈表與數(shù)組
4.2.6 逆轉(zhuǎn)數(shù)組
4.2.7 歸納思想
4.2.8 復(fù)習(xí)題
4.2.9 練習(xí)
4.3 常見陷阱——無窮回歸
4.3.1 學(xué)習(xí)內(nèi)容
4.3.2 復(fù)習(xí)題
4.3.3 練習(xí)
4.4 一個指數(shù)級運(yùn)行時間的遞歸算法
4.4.1 學(xué)習(xí)內(nèi)容
4.4.2 漢諾塔
4.4.3 復(fù)習(xí)題
4.4.4 練習(xí)
4.5 陷阱
4.6 提示與技巧
4.7 參考資料
4.8 本章小結(jié)
第5章 模塊化與數(shù)據(jù)抽象
5.1 介紹
本章計劃
5.2 優(yōu)先隊(duì)列——一種抽象數(shù)據(jù)類型
5.2.1 學(xué)習(xí)內(nèi)容
5.2.2 優(yōu)先隊(duì)列ADT接口
5.2.3 復(fù)習(xí)題
5.2.4 練習(xí)
5.3 優(yōu)先隊(duì)列的兩種實(shí)現(xiàn)
5.3.1 學(xué)習(xí)內(nèi)容
5.3.2 利用已排序鏈表實(shí)現(xiàn)優(yōu)先隊(duì)列
5.3.3 利用未排序數(shù)組實(shí)現(xiàn)優(yōu)先隊(duì)列
5.3.4 復(fù)習(xí)題
5.3.5 練習(xí)
5.4 在優(yōu)先隊(duì)列中填人新型對象
5.4.1 學(xué)習(xí)內(nèi)容
5.4.2 復(fù)習(xí)題
5.4.3 練習(xí)
5.5 程序設(shè)計中的模塊化與信息隱藏
5.5.1 學(xué)習(xí)內(nèi)容
5.5.2 復(fù)習(xí)題
5.6 陷阱
5.7 提示與技巧
5.8 參考資料
5.9 本章小結(jié)
第6章 線性數(shù)據(jù)結(jié)構(gòu)——堆棧與隊(duì)列
6.1 介紹
本章計劃
6.2 堆棧的一些背景知識
6.2.1 學(xué)習(xí)內(nèi)容
6.2.2 復(fù)習(xí)題
6.2.3 練習(xí)
6.3 堆棧與隊(duì)列的ADT
6.3.1 學(xué)習(xí)內(nèi)容
6.3.2 堆棧類與隊(duì)列類的接口
6.3.3 復(fù)習(xí)題
6.3.4 練習(xí)
6.4 使用堆棧ADT檢查括號對稱性
6.4.1 學(xué)習(xí)內(nèi)容
6.4.2 復(fù)習(xí)題
6.4.3 練習(xí)
6.5 利用堆棧ADT計算后綴表達(dá)式
6.5.1 學(xué)習(xí)內(nèi)容
6.5.2 復(fù)習(xí)題
6.5.3 練習(xí)
6.6 實(shí)現(xiàn)堆棧ADT
6.6.1 學(xué)習(xí)內(nèi)容
6.6.2 順序堆棧表示
6.6.3 鏈?zhǔn)蕉褩１硎?br />6.6.4 復(fù)習(xí)題
6.6.5 練習(xí)
6.7 Java如何利用堆棧實(shí)現(xiàn)遞歸方法調(diào)用
6.7.1 學(xué)習(xí)內(nèi)容
6.7.2 復(fù)習(xí)題
6.7.3 練習(xí)
6.8 隊(duì)列ADT的實(shí)現(xiàn)
6.8.1 學(xué)習(xí)內(nèi)容
6.8.2 順序隊(duì)列表示
6.8.3 鏈?zhǔn)疥?duì)列表示
6.8.4 比較鏈?zhǔn)疥?duì)列表示與順序隊(duì)列表示
6.8.5 復(fù)習(xí)題
6.8.6 練習(xí)
6.9 其他隊(duì)列應(yīng)用
6.9.1 學(xué)習(xí)內(nèi)容
6.9.2 操作系統(tǒng)中的隊(duì)列
6.9.3 在模擬試驗(yàn)中使用隊(duì)列
6.9.4 復(fù)習(xí)題
6.9.5 練習(xí)
6.10 陷阱
6.11 提示與技巧
6.12 參考資料
6.13 本章小結(jié)
第7章 鏈表、字符串和動態(tài)內(nèi)存分配
7.1 引言和動機(jī)
本章計劃
7.2 表
7.2.1 學(xué)習(xí)內(nèi)容
7.2.2 表的ADT
7.2.3 順序表表示
7.2.4 單向鏈表表示
7.2.5 比較順序和鏈?zhǔn)奖硎?br />7.2.6 其他鏈表表示
7.2.7 循環(huán)鏈表
7.2.8 雙向鏈表
7.2.9 帶有頭節(jié)點(diǎn)的鏈表
7.2.10 復(fù)習(xí)題
7.2.11 練習(xí)
7.3 廣義表
7.3.1 學(xué)習(xí)內(nèi)容
7.3.2 復(fù)習(xí)題
7.3.3 練習(xí)
7.4 廣義表的應(yīng)用
7.4.1 學(xué)習(xí)內(nèi)容
7.4.2 復(fù)習(xí)題
7.4.3 練習(xí)
7.5 字符串
7.5.1 學(xué)習(xí)內(nèi)容
7.5.2 Java中的只讀字符串
7.5.3 Java中的String Buffer
7.5.4 在文本文件和字處理程序中的字符串表示方法
7.5.5 復(fù)習(xí)題
7.5.6 練習(xí)
7.6 動態(tài)內(nèi)存分配
7.6.1 學(xué)習(xí)內(nèi)容
7.6.2 可用空間列表和垃圾收集
7.6.3 堆和動態(tài)內(nèi)存分配
7.6.4 最先適配
7.6.5 最佳適配
7.6.6 分段存儲與合并
7.6.7 壓縮以對應(yīng)分配失敗
7.6.8 比較各種應(yīng)用中堆的使用
7.6.9 引用計數(shù)
7.6.10 復(fù)習(xí)題
7.6.11 練習(xí)
7.7 陷阱
7.8 揭示與技巧
7.9 參考資料
7.10 本章小結(jié)
第8章 樹與圖
8.1 介紹
本章計劃
8.2 樹——基本概念與術(shù)語
8.2.1 學(xué)習(xí)內(nèi)容
8.2.2 復(fù)習(xí)題
8.2.3 練習(xí)
8.3 二叉樹
8.3.1 學(xué)習(xí)內(nèi)容
8.3.2 復(fù)習(xí)題
8.3.3 練習(xí)
8.4 順序二叉樹表示
8.12 圖——基本概念與術(shù)語
8.12.1 學(xué)習(xí)內(nèi)容
8.12.2 一些正式定義
8.12.3 路徑、環(huán)路與鄰接
8.12.4 連通性與子圖
8.12.5 鄰接點(diǎn)集與度
8.12.6 復(fù)習(xí)題
8.12.7 練習(xí)
8.13 圖的表示
8.13.1 學(xué)習(xí)內(nèi)容
8.13.2 復(fù)習(xí)題
8.13.3 練習(xí)
8.14 圖的搜索
8.14.1 學(xué)習(xí)內(nèi)容
8.14.2 復(fù)習(xí)題
8.14.3 練習(xí)
8.15 拓?fù)渑判?br />8.15.1 學(xué)習(xí)內(nèi)容
8.15.2 復(fù)習(xí)題
8.15.3 練習(xí)
8.16 陷阱
8.17 提示與技巧
8.18 參考資料
8.19 本章小結(jié)
第9章 散列和Table ADT
9.1 介紹
本章計劃
9.2 Table ADT
9.2.1 學(xué)習(xí)內(nèi)容
9.2.2 復(fù)習(xí)題
9.2.3 練習(xí)
9.3 通過簡單的示例介紹散列技術(shù)
9.3.1 學(xué)習(xí)內(nèi)容
9.3.2 復(fù)習(xí)題
9.3.3 練習(xí)
9.4 沖突、負(fù)載因子和集群
9.4.1 學(xué)習(xí)內(nèi)容
9.4.2 沖突
9.4.3 von Mises的概率討論
9.4.4 負(fù)載因子和集群
9.4.5 復(fù)習(xí)題
9.4.6 練習(xí)
9.5 使用開放定址的散列算法
9.5.1 學(xué)習(xí)內(nèi)容
9.5.2 基本群集和它消失的兩個示例
9.5.3 保證探測序列會覆蓋整個表
9.5.4 性能公式
9.5.5 比較理論和經(jīng)驗(yàn)結(jié)果
9.5.6 復(fù)習(xí)題
9.5.7 練習(xí)
9.6 選擇散列函數(shù)
9.6.1 學(xué)習(xí)內(nèi)容
9.6.2 除余法
9.6.3 其他的散列函數(shù)方法
9.6.4 復(fù)習(xí)題
9.6.5 練習(xí)
9.7 使用Table ADT的查找方法比較
9.7.1 學(xué)習(xí)內(nèi)容
9.7.2 復(fù)習(xí)題
9.7.3 練習(xí)
9.8 陷阱
9.9 提示與技巧
9.10 參考資料
9.11 本章小結(jié)
第10章 排序
10.1 介紹
本章計劃
10.2 背景知識
10.2.1 學(xué)習(xí)內(nèi)容
10.2.2 復(fù)習(xí)題
10.2.3 練習(xí)
10.3 優(yōu)先隊(duì)列排序方法
10.3.1 學(xué)習(xí)內(nèi)容
10.3.2 一些預(yù)設(shè)
10.3.3 優(yōu)先隊(duì)列排序
10.3.4 SelectionSort
10.3.5 HeapSort
10.3.6 復(fù)習(xí)題
10.3.7 練習(xí)
10.4 分而治之方法
10.4.1 學(xué)習(xí)內(nèi)容
10.4.2 MergeSort
10.4.3 QuickSort
10.4.4 復(fù)習(xí)題
10.4.5 練習(xí)
10.5 插入關(guān)鍵字且保持有序的方法
10.5.1 學(xué)習(xí)內(nèi)容
10.5.2 InsertionSort
10.5.3 TreeSort
10.5.4 復(fù)習(xí)題
10.5.5 練習(xí)
10.6 O(n)方法——地址計算排序
10.6.1 學(xué)習(xí)內(nèi)容
10.6.2 ProxmapSort
10.6.3 RadixSort
10.6.4 復(fù)習(xí)題
10.6.5 練習(xí)
10.7 其他方法
10.7.1 學(xué)習(xí)內(nèi)容
10.7.2 ShellSort
10.7.3 BubbleSort
10.7.4 復(fù)習(xí)題
10.7.5 練習(xí)
10.8 比較與展望
10.8.1 學(xué)習(xí)內(nèi)容
10.8.2 一些簡單的智慧
10.8.3 復(fù)習(xí)題
10.8.4 練習(xí)
10.9 陷阱
10.10 提示與技巧
10.11 參考資料
10.12 本章小結(jié)
附錄A JAVA要點(diǎn)回顧
A.1 JAVA向?qū)?br />本附錄計劃
A.2 標(biāo)識符、保留字、名稱和變量
A.2.1 學(xué)習(xí)內(nèi)容
A.2.2 復(fù)習(xí)題
A.2.3 練習(xí)
A.3 Java中的數(shù)據(jù)類型
A.3.1 Java中的引用數(shù)據(jù)類型
A.3.2 復(fù)習(xí)題
A.3.3 練習(xí)
A.4 Java操作符和表達(dá)式
A.4.1 Java中的操作符優(yōu)先級和結(jié)合
A.4.2 復(fù)習(xí)題
A.4.3 練習(xí)
A.5 Java中的控制流
A.5.1 選擇語句
A.5.2 循環(huán)語句
A.5.3 break、continue和return語句
A.5.4 復(fù)習(xí)題
A.5.5 練習(xí)
A.6 Java中的類、方法和對象
A.6.1 學(xué)習(xí)內(nèi)容
A.6.2 復(fù)習(xí)題
A.6.3 練習(xí)
A.7 在Java中引入包
A.7.1 學(xué)習(xí)內(nèi)容
A.7.2 復(fù)習(xí)題
A.7.3 練習(xí)
A.8 Java中的注釋
A.8.1 學(xué)習(xí)內(nèi)容
A.8.2 復(fù)習(xí)題
A.8.3 練習(xí)
A.9 參考資料
附錄B 表示效率的語言
B.1 介紹
本附錄計劃
B.2 我們用什么來作為衡量標(biāo)準(zhǔn)
B.2.1 學(xué)習(xí)內(nèi)容
B.2.2 復(fù)習(xí)題
B.2.3 練習(xí)
B.3 O-符號意義的直觀認(rèn)識
B.3.1 學(xué)習(xí)內(nèi)容
B.3.2 注意
B.3.3 本書其余部分所涉及的內(nèi)容
B.3.4 復(fù)習(xí)題
B.3.5 練習(xí)
B.4 O-符號的定義和操縱
B.4.1 學(xué)習(xí)內(nèi)容
B.4.2 O-符號的正式證明的例子
B.4.3 用于操縱O—符號的實(shí)用的簡化操作
B.4.4 復(fù)習(xí)題
B.4.5 練習(xí)
B.5 O-表示法沒有包含的知識
B.5.1 學(xué)習(xí)內(nèi)容
B.5.2 復(fù)習(xí)題
B.5.3 練習(xí)
B.6 參考資料
B.7 本附錄小結(jié)
附錄C 軟件工程概念
C.1 介紹
本附錄計劃
C.2 面向?qū)ο笤O(shè)計與自頂向下編程
C.2.1 學(xué)習(xí)內(nèi)容
C.2.2 你是否有張獲獎彩票
C.2.3 選定Table的數(shù)據(jù)表示
C.2.4 第二種求精
C.2.5 復(fù)習(xí)題
C.2.6 練習(xí)
C.3 程序正確性證明
C.3.1 學(xué)習(xí)內(nèi)容
C.3.2 一個小錯誤
C.3.3 形式邏輯一瞥
C.3.4 復(fù)習(xí)題
C.3.5 練習(xí)
C.4 程序轉(zhuǎn)換與優(yōu)化
C.4.1 學(xué)習(xí)內(nèi)容
C.4.2 復(fù)習(xí)題
C.4.3 練習(xí)
C.5 測試程序
C.5.1 學(xué)習(xí)內(nèi)容
C.5.2 自底向上測試
C.5.3 單元測試、帶格式的調(diào)試輔助器與測試容器
C.5.4 集成測試
C.5.5 可接受性測試與回歸測試
C.5.6 自頂向下測試與樁
C.5.7 測試計劃
C.5.8 測試與驗(yàn)證的角色比較
C.5.9 復(fù)習(xí)題
C.5.10 練習(xí)
C.6 度量與調(diào)節(jié)哲學(xué)
C.6.1 學(xué)習(xí)內(nèi)容
C.6.2 比較一些二叉搜索方法
C.6.3 復(fù)習(xí)題
C.6.4 練習(xí)
C.7 軟件重用與自底向上編程
C.7.1 學(xué)習(xí)內(nèi)容
C.7.2 復(fù)習(xí)題
C.7.3 練習(xí)
C.8 程序結(jié)構(gòu)化與文檔
C.8.1 學(xué)習(xí)內(nèi)容
C.8.2 編程風(fēng)格原則
C.8.3 文檔
C.8.4 復(fù)習(xí)題
C.8.5 練習(xí)
C.9 陷阱
C.10 提示與技巧
C.11 參考資料
C.12 附錄小結(jié)