第1章 “數(shù)據(jù)結構與算法”教學實施方案
1.1 “數(shù)據(jù)結構與算法”的理論體系
1.1.1 課程的基本定位
1.1.2 知識體系
1.2 “數(shù)據(jù)結構與算法”學習重點
1.2.1 概論
1.2.2 線性表
1.2.3 棧與隊列
1.2.4 字符串
1.2.5 二叉樹
1.2.6 樹
1.2.7 圖
1.2.8 內(nèi)排序
1.2.9 文件與外排序
1.2.10 檢索
第1章 “數(shù)據(jù)結構與算法”教學實施方案
1.1 “數(shù)據(jù)結構與算法”的理論體系
1.1.1 課程的基本定位
1.1.2 知識體系
1.2 “數(shù)據(jù)結構與算法”學習重點
1.2.1 概論
1.2.2 線性表
1.2.3 棧與隊列
1.2.4 字符串
1.2.5 二叉樹
1.2.6 樹
1.2.7 圖
1.2.8 內(nèi)排序
1.2.9 文件與外排序
1.2.10 檢索
1.2.11 索引
1.2.12 高級數(shù)據(jù)結構
第2章 面向?qū)ο蟪绦蛟O計與C++概述
2.1 面向?qū)ο蟪绦蛟O計概述
2.1.1 面向?qū)ο蟪绦蛟O計:類和對象
2.1.2 面向?qū)ο蟪绦蛟O計的特點
2.2 C++編程概述
2.2.1 C++中的類和對象
2.2.2 對象的定義
2.2.3 類的成員函數(shù)
2.2.4 構造函數(shù)和結構函數(shù)
2.2.5 友元
2.2.6 類的繼承
2.3 重載
2.3.1 函數(shù)重載
2.3.2 運算符重載
2.4 動態(tài)存儲分配
習題
第3章 STL簡介
3.1 泛型編程簡介
3.1.1 泛型編程的需求
3.1.2 C++中模板的使用
3.2 STL容器簡介
3.2.1 vector
3.2.2 deque
3.2.3 list
3.2.4 set和multiset
3.2.5 map和multimap
3.2.6 stack
3.2.7 queue
3.3 STL算法
3.3.1 STL算法簡介
3.3.2 非變動性算法
3.3.3 變動性算法
3.3.4 變序型算法和排序算法
3.3.5 已排序區(qū)間算法
3.3.6 數(shù)值算法
3.4 STL迭代器
3.4.1 迭代器簡介
3.4.2 迭代器類型
3.4.3 迭代器函數(shù)
3.4.4 迭代器配接器
3.5 文件流與輸入輸出
3.5.1 全局性的Stream對象
3.5.2 標準操作符<<和>>
3.5.3 標準10函數(shù)
習題
第4章 程序設計實踐
4.1 程序設計風格
4.1.1 命名
4.1.2 語句
4.1.3 注釋
4.1.4 程序組織原則
4.1.5 文檔
4.1.6 實踐和原則
4.2 界面
4.3 測試、性能和可擴展性
4.3.1 軟件測試基本概念
4.3.2 軟件測試原則
4.3.3 軟件測試策略
4.3.4 軟件測試方法
4.3.5 測試實例
4.3.6 性能和可擴展性
習題
第5章 問題建模
5.1 數(shù)學模型和數(shù)學建模
5.1.1 數(shù)學模型
5.1.2 數(shù)學模型示例——雨中行問題
5.1.3 生產(chǎn)計劃問題——線性規(guī)劃模型
5.1.4 預測疾病的發(fā)展變化趨勢——馬爾可夫鏈模型
5.1.5 Buffon投針實驗——蒙特卡羅方法
5.1.6 公交最優(yōu)路線查詢系統(tǒng)設計問題
5.2 設計模式
5.2.1 設計模式的概念
5.2.2 MVC的設計模式
5.2.3 設計模式舉例——工廠模式
習題
第6章 經(jīng)典算法設計
6.1 狀態(tài)空間
6.2 時間復雜度計算
6.2.1 算法時間復雜度分析
6.2.2 遞推方程求解
6.3 窮舉法
6.4 貪心法
6.5 遞歸和回溯
6.5.1 遞歸法
6.5.2 回溯法
6.5.3 回溯法的分支限界
6.6 搜索與剪枝
6.6.1 盲目搜索算法
6.6.2 剪枝
6.6.3 搜索的效率問題
6.7 分治法
6.7.1 分治策略
6.7.2 降低遞歸算法復雜性的途徑
6.8 動態(tài)規(guī)劃
6.9 算法思想小結
習題
第7章 問題求解實踐
7.1 問題求解
7.2 線性結構
7.2.1 數(shù)組元素循環(huán)右移k位——時空權衡
7.2.2 火車調(diào)度——棧的應用
7.2.3 KMP模式匹配算法的應用
7.3 樹形結構
7.3.1 二叉樹遍歷算法框架在問題求解中的應用
7.3.2 樹的應用
7.3.3 選擇樹的應用
7.3.4 樹與二叉樹的計數(shù)
7.4 線段樹
7.4.1 線段樹的定義及特征
7.4.2 線段樹的基本操作
7.5 圖的應用
7.5.1 圖的抽象
7.5.2 圖的搜索
7.5.3 基于深度優(yōu)先的拓撲排序
7.5.4 第二最短路徑
7.5.5 唯一最小生成樹
7.5.6 有向圖的強連通性問題
7.6 排序與檢索
7.6.1 統(tǒng)計逆序?qū)Φ臍w并思想
7.6.2 求兩個等長有序序列中位數(shù)的二分思想
7.7 算法優(yōu)化
習題
第8章 數(shù)據(jù)結構與算法技術應用實例
8.1 搜索引擎中的數(shù)據(jù)結構技術
8.1.1 概述
8.1.2 抓取系統(tǒng)
8.1.3 索引系統(tǒng)
8.1.4 檢索系統(tǒng)
8.2 在線評測算法實習范例
8.3 綜合實習范例
習題
第9章 試題及參考答案
9.1 期中考試
9.1.1 2007年期中考試試題
9.1.2 2007年期中考試參考答案
9.1.3 2008年期中考試試題
9.1.4 2008年期中考試參考答案
9.2 期末考試
9.2.1 2007年期末考試試題
9.2.2 2007年期末考試參考答案
9.2.3 2008年期末考試試題
9.2.4 2008年期末考試參考答案
9.3 高級專題考試
9.3.1 2007年高級專題考試試題
9.3.2 2007年高級專題考試參考答案
9.3.3 2008年高級專題考試試題
9.3.4 2008年高級專題考試參考答案
9.4 實習課程考試
9.4.1 2007年實習課考試試題
9.4.2 2007年實習課考試參考答案
9.4.3 2008年實習課考試試題
9.4.4 2008年實習課考試參考答案
參考文獻