C程序設(shè)計(jì)的抽象思維

寫(xiě)給學(xué)生
寫(xiě)給教師
致謝
第一部分 預(yù)備知識(shí)
第1章 ANSI C概述
1.1 什么是C
1.2 C程序的結(jié)構(gòu)
1.2.1 注釋
1.2.2 包含的庫(kù)文件
1.2.3 程序級(jí)的定義
1.2.4 函數(shù)原型
1.2.5 主程序
1.2.6 函數(shù)定義
1.3 變量、值和類(lèi)型
1.3.1 變量
1.3.2 命名規(guī)則
1.3.3 局部變量和全局變量
1.3.4 數(shù)據(jù)類(lèi)型的概念
1.3.5 整數(shù)類(lèi)型
1.3.6 浮點(diǎn)類(lèi)型
1.3.7 文本類(lèi)型
1.3.8 布爾類(lèi)型
1.3.9 簡(jiǎn)單輸入輸出
1.4 表達(dá)式
1.4.1 優(yōu)先級(jí)與結(jié)合性
1.4.2 表達(dá)式中的類(lèi)型混合
1.4.3 整數(shù)除法和求余運(yùn)算
1.4.4 類(lèi)型轉(zhuǎn)換
1.4.5 賦值運(yùn)算符
1.4.6 遞增與遞減運(yùn)算符
1.4.7 布爾運(yùn)算符
1.5 語(yǔ)句
1.5.1 簡(jiǎn)單語(yǔ)句
1.5.2 塊
1.5.3 if語(yǔ)句
1.5.4 switch語(yǔ)句
1.5.5 while語(yǔ)句
1.5.6 for語(yǔ)句
1.6 函數(shù)
1.6.1 返回函數(shù)結(jié)果
1.6.2 函數(shù)定義和原型
1.6.3 函數(shù)調(diào)用過(guò)程的機(jī)制
1.6.4 逐步求精
1.7 總結(jié)
1.8 復(fù)習(xí)題
1.9 編程練習(xí)

第2章 C的數(shù)據(jù)類(lèi)型
2.1 枚舉類(lèi)型
2.1.1 枚舉類(lèi)型的內(nèi)部表示
2.1.2 標(biāo)量類(lèi)型
2.1.3 理解typedef
2.2 數(shù)據(jù)和內(nèi)存
2.2.1 位、字節(jié)、字
2.2.2 內(nèi)存地址
2.3 指針
2.3.1 把地址當(dāng)作數(shù)值
2.3.2 聲明指針變量
2.3.3 基本的指針運(yùn)算
2.3.4 特殊指針NULL
2.3.5 傳遞引用
2.4 數(shù)組
2.4.1 聲明數(shù)組
2.4.2 數(shù)組選擇
2.4.3 分配的空間和利用的空間
2.4.4 把數(shù)組作為參數(shù)
2.4.5 初始化數(shù)組
2.4.6 多維數(shù)組
2.5 指針和數(shù)組
2.5.1 指針運(yùn)算
2.5.2 指針的自加和自減
2.5.3 指針和數(shù)組的關(guān)系
2.6 記錄
2.6.1 定義一種新的結(jié)構(gòu)類(lèi)型
2.6.2 聲明結(jié)構(gòu)變量
2.6.3 記錄選擇
2.6.4 初始化紀(jì)錄
2.6.5 記錄的指針
2.7 動(dòng)態(tài)分配
2.7.1 類(lèi)型void
2.7.2 對(duì)內(nèi)存限制的處理
2.7.3 動(dòng)態(tài)數(shù)組
2.7.4 動(dòng)態(tài)記錄
2.8 總結(jié)
2.9 復(fù)習(xí)題
2.10 編程練習(xí)

第3章 庫(kù)和接口
3.1 接口的概念
3.1.1 接口和實(shí)現(xiàn)
3.1.2 包和抽象
3.1.3 良好的接口設(shè)計(jì)規(guī)則
3.2 隨機(jī)數(shù)字
3.2.1 random.h接口的結(jié)構(gòu)
3.2.2 構(gòu)造一個(gè)客戶程序
3.2.3 ANSI中有關(guān)隨機(jī)數(shù)字的函數(shù)
3.2.4 實(shí)現(xiàn)random.c
3.3 字符串
3.3.1 字符的底層表示
3.3.2 數(shù)據(jù)類(lèi)型string
3.3.3 ANSI字符串庫(kù)
3.3.4 接口strlib.h
3.4 標(biāo)準(zhǔn)的I/O庫(kù)
3.4.1 數(shù)據(jù)文件
3.4.2 在C中使用文件
3.4.3 標(biāo)準(zhǔn)文件
3.4.4 字符I/O
3.4.5 從輸入文件中重讀字符
3.4.6 更新文件
3.4.7 面向行的I/O
3.4.8 格式化的I/O
3.4.9 scanf函數(shù)
3.5 其他ANSI庫(kù)
3.6 總結(jié)
3.7 復(fù)習(xí)題
3.8 編程練習(xí)

第二部分 遞歸和算法分析
第4章 遞歸入門(mén)
4.1 一個(gè)簡(jiǎn)單的遞歸示例
4.2 階乘函數(shù)
4.2.1 Fact的遞歸公式
4.2.2 追蹤遞歸過(guò)程
4.2.3 遞歸跳躍的信任
4.3 費(fèi)波那契函數(shù)
4.3.1 計(jì)算費(fèi)波那契序列
4.3.2 增進(jìn)實(shí)現(xiàn)遞歸的信心
4.3.3 遞歸實(shí)現(xiàn)的效率
4.3.4 不應(yīng)該責(zé)備遞歸
4.4 其他遞歸示例
4.4.1 探測(cè)回文
4.4.2 二分查找
4.4.3 交互遞歸
4.5 遞歸的思考
4.5.1 保持整體觀
4.5.2 避免常見(jiàn)的陷阱
4.6 總結(jié)
4.7 復(fù)習(xí)題
4.8 編程練習(xí)

第5章 遞歸過(guò)程
5.1 漢諾塔
5.1.1 分解問(wèn)題
5.1.2 尋找遞歸策略
5.1.3 證實(shí)遞歸策略
5.1.4 編碼解決方案
5.1.5 追蹤遞歸過(guò)程
5.2 產(chǎn)生排列
5.3 遞歸的繪圖應(yīng)用
5.3.1 繪圖庫(kù)
5.3.2 電腦藝術(shù)示例
5.3.3 不規(guī)則碎片形
5.4 總結(jié)
5.5 復(fù)習(xí)題
5.6 編程練習(xí)

第6章 回溯算法
6.1 用遞歸回溯解決迷宮問(wèn)題
6.1.1 右手規(guī)則
6.1.2 尋找遞歸方法
6.1.3 識(shí)別簡(jiǎn)單情景
6.1.4 迷宮解決方案算法編碼
6.1.5 確信解決方案可以正確運(yùn)行
6.2 回溯與對(duì)策
6.2.1 拿子游戲
6.2.2 一般化的雙人游戲程序
6.2.3 最小最大策略
6.2.4 實(shí)現(xiàn)最小最大化算法
6.2.5 在具體的游戲中采用一般化策略
6.3 總結(jié)
6.4 復(fù)習(xí)題
6.5 編程練習(xí)

第7章 算法分析
7.1 排序問(wèn)題
7.1.1 選擇排序算法
7.1.2 性能的經(jīng)驗(yàn)度量
7.1.3 分析選擇排序的性能
7.2 計(jì)算復(fù)雜度
7.2.1 大O符號(hào)
7.2.2 大O的標(biāo)準(zhǔn)簡(jiǎn)化
7.2.3 排序算法的計(jì)算復(fù)雜度
7.2.4 根據(jù)代碼結(jié)構(gòu)預(yù)測(cè)計(jì)算復(fù)雜度
7.2.5 最差情況復(fù)雜度與平均情況復(fù)雜度
7.2.6 大O的正式定義
7.3 遞歸幫助
7.3.1 分治策略的威力
7.3.2 合并兩個(gè)數(shù)組
7.3.3 合并排序算法
7.3.4 合并排序的計(jì)算復(fù)雜度
7.3.5 比較N2和NlogN的性能
7.4 標(biāo)準(zhǔn)復(fù)雜度類(lèi)型
7.5 快速排序算法
7.5.1 分割數(shù)組
7.5.2 分析快速排序的性能
7.6 數(shù)學(xué)歸納法
7.7 總結(jié)
7.8 復(fù)習(xí)題
7.9 編程練習(xí)

第三部分 數(shù)據(jù)抽象
第8章 抽象數(shù)據(jù)類(lèi)型
8.1 棧
8.1.1 棧的基本概念
8.1.2 棧和函數(shù)調(diào)用
8.1.3 棧和袖珍計(jì)算器
8.2 定義棧的ADT
8.2.1 定義棧抽象的類(lèi)型
8.2.2 不透明類(lèi)型
8.2.3 定義stack.h接口
8.3 在應(yīng)用中使用棧
8.4 實(shí)現(xiàn)棧抽象
8.4.1 定義具體類(lèi)型
8.4.2 實(shí)現(xiàn)棧操作
8.4.3 不透明類(lèi)型的優(yōu)點(diǎn)
8.4.4 改進(jìn)stack.c的實(shí)現(xiàn)
8.5 定義一個(gè)scannerADT
8.5.1 封裝狀態(tài)的危險(xiǎn)
8.5.2 抽象數(shù)據(jù)類(lèi)型作為封裝狀態(tài)的替代
8.5.3 實(shí)現(xiàn)掃描器抽象
8.6 總結(jié)
8.7 復(fù)習(xí)題
8.8 編程練習(xí)

第9章 效率與ADT
9.1 編輯器緩沖區(qū)的概念
9.2 定義緩沖區(qū)抽象
9.2.1 接口buffer.h中的函數(shù)
9.2.2 為編輯器應(yīng)用編寫(xiě)代碼
9.3 用數(shù)組實(shí)現(xiàn)編輯器
9.3.1 定義具體類(lèi)型
9.3.2 實(shí)現(xiàn)緩沖區(qū)的操作
9.3.3 數(shù)組實(shí)現(xiàn)的計(jì)算復(fù)雜度
9.4 用棧實(shí)現(xiàn)編輯器
9.4.1 定義基于棧的緩沖區(qū)的具體結(jié)構(gòu)
9.4.2 實(shí)現(xiàn)緩沖區(qū)的操作
9.4.3 比較計(jì)算復(fù)雜度
9.5 用鏈表實(shí)現(xiàn)編輯器
9.5.1 鏈表的概念
9.5.2 設(shè)計(jì)鏈表數(shù)據(jù)結(jié)構(gòu)
9.5.3 使用鏈表表示緩沖區(qū)
9.5.4 鏈表緩沖區(qū)中的插入
9.5.5 鏈表緩沖區(qū)中的刪除
9.5.6 鏈表表示中的光標(biāo)移動(dòng)
9.5.7 鏈表的習(xí)慣用法
9.5.8 完成緩沖區(qū)實(shí)現(xiàn)
9.5.9 鏈表緩沖區(qū)的計(jì)算復(fù)雜度
9.5.10 雙向鏈表
9.5.11 時(shí)間空間的權(quán)衡
9.6 總結(jié)
9.7 復(fù)習(xí)題
9.8 編程練習(xí)

第10章 線性結(jié)構(gòu)
10.1 ?；仡?br /> 10.2 隊(duì)列
10.2.1 接口queue.h的結(jié)構(gòu)
10.2.2 基于數(shù)組的隊(duì)列實(shí)現(xiàn)
10.2.3 隊(duì)列的鏈表實(shí)現(xiàn)
10.3 使用隊(duì)列的仿真
10.3.1 仿真與模型
10.3.2 排隊(duì)模型
10.3.3 離散時(shí)間
10.3.4 仿真時(shí)間中的事件
10.3.5 實(shí)現(xiàn)仿真
10.4 總結(jié)
10.5 復(fù)習(xí)題
10.6 編程練習(xí)

第11章 符號(hào)表
11.1 定義符號(hào)表抽象
11.1.1 選擇值和鍵的類(lèi)型
11.1.2 表示未定義項(xiàng)
11.1.3 符號(hào)表接口的初始版本
11.2 散列
11.2.1 實(shí)現(xiàn)散列表策略
11.2.2 選擇散列函數(shù)
11.2.3 確定桶的數(shù)量
11.3 初級(jí)接口的限制
11.4 使用函數(shù)作為數(shù)據(jù)
11.4.1 一個(gè)一般測(cè)繪函數(shù)
11.4.2 聲明函數(shù)指針與函數(shù)類(lèi)
11.4.3 實(shí)現(xiàn)PlotFunction
11.4.4 qsort函數(shù)
11.5 映射函數(shù)
11.5.1 映射符號(hào)表中的所有項(xiàng)
11.5.2 實(shí)現(xiàn)MapSymbolTable
11.5.3 向回調(diào)函數(shù)傳遞客戶數(shù)據(jù)
11.6 迭代器
11.6.1 使用迭代器
11.6.2 定義迭代器接口
11.6.3 實(shí)現(xiàn)符號(hào)表的迭代器抽象
11.7 命令分派表
11.8 總結(jié)
11.9 復(fù)習(xí)題
11.10 編程練習(xí)

第四部分 遞歸數(shù)據(jù)
第12章 遞歸列表
12.1 鏈表的遞歸表述
12.2 定義抽象鏈表類(lèi)型
12.2.1 不變類(lèi)型
12.2.2 操縱鏈表結(jié)構(gòu)的函數(shù)
12.2.3 連接多個(gè)鏈表
12.2.4 不變類(lèi)型間的內(nèi)部共享
12.3 使用鏈表表示大整數(shù)
12.3.1 bigint.h 接口
12.3.2 表示類(lèi)型bigIntADT
12.3.3 實(shí)現(xiàn)bigint包
12.3.4 使用bigint.h包
12.4 總結(jié)
12.5 復(fù)習(xí)題
12.6 編程練習(xí)

第13章 樹(shù)
13.1 家譜樹(shù)
13.1.1 描述樹(shù)的術(shù)語(yǔ)
13.1.2 樹(shù)的遞歸特性
13.1.3 用C語(yǔ)言表示家譜樹(shù)
13.2 二叉搜索樹(shù)
13.2.1 使用二叉搜索樹(shù)的底層動(dòng)機(jī)
13.2.2 在二叉搜索樹(shù)中查找節(jié)點(diǎn)
13.2.3 在二叉搜索樹(shù)中插入新節(jié)點(diǎn)
13.2.4 樹(shù)的遍歷
13.3 平衡樹(shù)
13.3.1 樹(shù)的平衡策略
13.3.2 舉例說(shuō)明AVL的思想
13.3.3 單旋轉(zhuǎn)
13.3.4 雙旋轉(zhuǎn)
13.3.5 實(shí)現(xiàn)AVL算法
13.4 為二叉搜索樹(shù)定義一般化接口
13.4.1 允許用戶定義節(jié)點(diǎn)結(jié)構(gòu)
13.4.2 一般化用作鍵的類(lèi)型
13.4.3 刪除節(jié)點(diǎn)
13.4.4 實(shí)現(xiàn)二叉搜索樹(shù)包
13.4.5 使用二叉樹(shù)實(shí)現(xiàn)symtab.h接口
13.5 總結(jié)
13.6 復(fù)習(xí)題
13.7 編程練習(xí)

第14章 表達(dá)式樹(shù)
14.1 解釋器概述
14.2 表達(dá)式的抽象結(jié)構(gòu)
14.2.1 表達(dá)式的遞歸定義
14.2.2 多義性
14.2.3 表達(dá)式樹(shù)
14.2.4 定義表達(dá)式的抽象接口
14.3 定義具體表達(dá)式類(lèi)型
14.3.1 聯(lián)合類(lèi)型
14.3.2 使用標(biāo)記的聯(lián)合表示表達(dá)式
14.3.3 可視化具體表示
14.3.4 實(shí)現(xiàn)構(gòu)建器和選擇器函數(shù)
14.4 語(yǔ)法分析表達(dá)式
14.4.1 語(yǔ)法分析和語(yǔ)法
14.4.2 不考慮優(yōu)先級(jí)的語(yǔ)法分析
14.4.3 在語(yǔ)法分析器中加入優(yōu)先級(jí)
14.5 計(jì)算表達(dá)式
14.6 總結(jié)
14.7 復(fù)習(xí)題
14.8 編程練習(xí)

第15章 集合
15.1 為數(shù)學(xué)抽象的集合
15.1.1 成員資格
15.1.2 集合運(yùn)算
15.1.3 集合恒等式
15.2 設(shè)計(jì)集合接口
15.2.1 定義元素類(lèi)型
15.2.2 編寫(xiě)set.h 接口
15.2.3 字符集合
15.2.4 使用指針集合來(lái)避免重復(fù)
15.3 實(shí)現(xiàn)集合包
15.4 設(shè)計(jì)多態(tài)迭代器
15.4.1 泛化迭代器函數(shù)的原型
15.4.2 在迭代器實(shí)現(xiàn)中加入多態(tài)性
15.4.3 導(dǎo)出聚集類(lèi)型
15.4.4 編碼迭代器包
15.4.5 foreach的習(xí)慣用法
15.5 提高整型集合的效率
15.5.1 特征向量
15.5.2 壓縮的位數(shù)組
15.5.3 位運(yùn)算符
15.5.4 使用位操作符實(shí)現(xiàn)特征向量
15.5.5 實(shí)現(xiàn)高級(jí)集合操作
15.5.6 使用混合實(shí)現(xiàn)
15.6 總結(jié)
15.7 復(fù)習(xí)題
15.8 編程練習(xí)

第16章 圖
16.1 圖的結(jié)構(gòu)
16.1.1 有向圖和無(wú)向圖
16.1.2 路徑和環(huán)
16.1.3 連通性
16.2 圖的實(shí)現(xiàn)策略
16.2.1 使用鄰接列表表示連接
16.2.2 使用鄰接矩陣表示連接
16.3 擴(kuò)展圖抽象
16.3.1 將數(shù)據(jù)與節(jié)點(diǎn)和圖關(guān)聯(lián)
16.3.2 顯式弧
16.3.3 迭代和圖
16.3.4 分層抽象
16.3.5 基于集合的圖接口
16.4 圖的遍歷
16.4.1 深度優(yōu)先遍歷
16.4.2 廣度優(yōu)先搜索
16.5 尋找最短路徑
16.6 總結(jié)
16.7 復(fù)習(xí)題
16.8 編程練習(xí)

第17章 Java的未來(lái)
17.1 面向?qū)ο蠓独?br /> 17.1.1 面向?qū)ο缶幊痰臍v史
17.1.2 對(duì)象、類(lèi)和方法
17.1.3 類(lèi)層次與繼承
17.2 Java入門(mén)
17.2.1 Web結(jié)構(gòu)
17.2.2 applet
17.2.3 執(zhí)行Java applet
17.3 Java的結(jié)構(gòu)
17.3.1 Java的語(yǔ)法
17.3.2 Java中的原子類(lèi)型
17.3.3 定義新類(lèi)
17.3.4 構(gòu)造器方法
17.3.5 this關(guān)鍵字
17.3.6 定義方法
17.3.7 定義子類(lèi)
17.4 Java中的預(yù)定義類(lèi)
17.4.1 String類(lèi)
17.4.2 Hashtable類(lèi)
17.4.3 原子類(lèi)型的對(duì)象包裝器
17.4.4 Vector類(lèi)
17.4.5 Stack類(lèi)
17.5 創(chuàng)建交互applet的工具
17.5.1 組件與容器
17.5.2 action方法
17.5.3 用于畫(huà)圖形的簡(jiǎn)單applet
17.5.4 更進(jìn)一步
17.6 總結(jié)
17.7 復(fù)習(xí)題
17.8 編程練習(xí)
……