C程序設計的抽象思維

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

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

第3章 庫和接口
3.1 接口的概念
3.1.1 接口和實現(xiàn)
3.1.2 包和抽象
3.1.3 良好的接口設計規(guī)則
3.2 隨機數字
3.2.1 random.h接口的結構
3.2.2 構造一個客戶程序
3.2.3 ANSI中有關隨機數字的函數
3.2.4 實現(xiàn)random.c
3.3 字符串
3.3.1 字符的底層表示
3.3.2 數據類型string
3.3.3 ANSI字符串庫
3.3.4 接口strlib.h
3.4 標準的I/O庫
3.4.1 數據文件
3.4.2 在C中使用文件
3.4.3 標準文件
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函數
3.5 其他ANSI庫
3.6 總結
3.7 復習題
3.8 編程練習

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

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

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

第7章 算法分析
7.1 排序問題
7.1.1 選擇排序算法
7.1.2 性能的經驗度量
7.1.3 分析選擇排序的性能
7.2 計算復雜度
7.2.1 大O符號
7.2.2 大O的標準簡化
7.2.3 排序算法的計算復雜度
7.2.4 根據代碼結構預測計算復雜度
7.2.5 最差情況復雜度與平均情況復雜度
7.2.6 大O的正式定義
7.3 遞歸幫助
7.3.1 分治策略的威力
7.3.2 合并兩個數組
7.3.3 合并排序算法
7.3.4 合并排序的計算復雜度
7.3.5 比較N2和NlogN的性能
7.4 標準復雜度類型
7.5 快速排序算法
7.5.1 分割數組
7.5.2 分析快速排序的性能
7.6 數學歸納法
7.7 總結
7.8 復習題
7.9 編程練習

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

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

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

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

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

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

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

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

第16章 圖
16.1 圖的結構
16.1.1 有向圖和無向圖
16.1.2 路徑和環(huán)
16.1.3 連通性
16.2 圖的實現(xiàn)策略
16.2.1 使用鄰接列表表示連接
16.2.2 使用鄰接矩陣表示連接
16.3 擴展圖抽象
16.3.1 將數據與節(jié)點和圖關聯(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 總結
16.7 復習題
16.8 編程練習

第17章 Java的未來
17.1 面向對象范例
17.1.1 面向對象編程的歷史
17.1.2 對象、類和方法
17.1.3 類層次與繼承
17.2 Java入門
17.2.1 Web結構
17.2.2 applet
17.2.3 執(zhí)行Java applet
17.3 Java的結構
17.3.1 Java的語法
17.3.2 Java中的原子類型
17.3.3 定義新類
17.3.4 構造器方法
17.3.5 this關鍵字
17.3.6 定義方法
17.3.7 定義子類
17.4 Java中的預定義類
17.4.1 String類
17.4.2 Hashtable類
17.4.3 原子類型的對象包裝器
17.4.4 Vector類
17.4.5 Stack類
17.5 創(chuàng)建交互applet的工具
17.5.1 組件與容器
17.5.2 action方法
17.5.3 用于畫圖形的簡單applet
17.5.4 更進一步
17.6 總結
17.7 復習題
17.8 編程練習
……