數(shù)據(jù)結(jié)構(gòu)與算法

第l章 緒論
1.1 數(shù)據(jù)結(jié)構(gòu)簡介
1.1.1 數(shù)據(jù)結(jié)構(gòu)的發(fā)展歷史
1.1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語
1.2 有關(guān)的預(yù)備知識
1.2.1 集合
1.2.2 遞歸
1.2.3 數(shù)學(xué)證明方法
習(xí)題
第2章 算法的基本概念與算法分析
2.1 算法的基本概念
2.1.1 一個(gè)簡單的算法
2.1.2 什么是算法
2.1.3 算法與問題
2.1.4 算法與程序
2.2 算法的評估
2.2.1 算法的正確性
2.2.2 時(shí)間代價(jià)
2.2.3 空間代價(jià)
2.2.4 最優(yōu)性
2.3 算法的復(fù)雜度度量
2.3.1 基本操作
2.3.2 問題實(shí)例長度
2.3.3 復(fù)雜度函數(shù)及其漸進(jìn)性質(zhì)
2.3.4 最壞情形和最優(yōu)情形
2.3.5 平均情形和算法的期望復(fù)雜度
2.3.6 復(fù)雜度函數(shù)的表示
2.4 算法設(shè)計(jì)與分析的重要性
2.4.1 一個(gè)實(shí)例
2.4.2 計(jì)算機(jī)應(yīng)用領(lǐng)域的變化
2.4.3 計(jì)算機(jī)技術(shù)的發(fā)展需要設(shè)計(jì)有效算法
2.5 MAXMIN問題
2.5.1 MAxMIN問題的平凡算法
2.5.2 第一次改進(jìn)算法
2.5.3 第二次改進(jìn)算法
2.5.4 采用分治策略的改進(jìn)算法
2.5.5 算法MAxMIN的討論
習(xí)題
第3章 線性表
3.1 線性表的定義和基本運(yùn)算
3.2 線性表的實(shí)現(xiàn)
3.2.1 順序存儲結(jié)構(gòu)
3.2.2 鏈?zhǔn)酱鎯Y(jié)構(gòu)
3.2.3 兩種基本實(shí)現(xiàn)方法的比較
3.2.4 循環(huán)鏈表
3.2.5 雙向鏈表
3.3 線性表的應(yīng)用
習(xí)題
第4章 棧、隊(duì)列和數(shù)組
4.1 棧
4.1.1 順序棧
4.1.2 鏈?zhǔn)綏?br />4.1.3 順序棧與鏈?zhǔn)綏５谋容^
4.1.4 棧的應(yīng)用
4.2 隊(duì)列
4.2.1 隊(duì)列的定義及基本運(yùn)算
4.2.2 順序隊(duì)列
4.2.3 鏈?zhǔn)疥?duì)列
4.2.4 隊(duì)列的應(yīng)用
4.3 數(shù)組
4.3.1 數(shù)組的抽象數(shù)據(jù)類型
4.3.2 數(shù)組的存儲方式
4.3.3 特殊數(shù)組
4.3.4 數(shù)組的應(yīng)用
習(xí)題
第5章 樹形結(jié)構(gòu)
5.1 樹
5.1.1 樹的基本概念
5.1.2 樹的抽象數(shù)據(jù)類型
5.2 二叉樹
5.2.1 二叉樹的定義及其主要特性
5.2.2 二叉樹的實(shí)現(xiàn)
5.2.3 二叉樹的遍歷
5.3 樹、森林與二叉樹的關(guān)系
5.3.1 樹的存儲結(jié)構(gòu)
5.3.2 森林與二叉樹的轉(zhuǎn)換
5.3.3 樹和森林的遍歷
5.4 樹形結(jié)構(gòu)的應(yīng)用
5.4.1 等價(jià)類問題
5.4.2 哈夫曼樹和哈夫曼編碼
習(xí)題
第6章 圖
6.1 圖的基本概念
6.1.1 圖的基本概念
6.1.2 圖的抽象數(shù)據(jù)類型
6.2 圖的存儲結(jié)構(gòu)
6.2.1 鄰接矩陣
6.2.2 鄰接表
6.2.3 逆鄰接表
6.2.4 鄰接多重表
6.2.5 圖的實(shí)現(xiàn)
6.3 圖的遍歷及求圖的連通分量
6.3.1 深度優(yōu)先搜索
6.3.2 廣度優(yōu)先搜索
6.3.3 無向圖的連通分量
6.4 生成樹和最小代價(jià)生成樹
6.4.1 生成樹
6.4.2 最小代價(jià)生成樹
6.5 最短路徑
6.5.1 從某個(gè)源點(diǎn)到其他各頂點(diǎn)的最短路徑
6.5.2 每一對頂點(diǎn)間的最短路徑
6.6 有向無環(huán)圖及其應(yīng)用
6.6.1 有向無環(huán)圖
6.6.2 拓?fù)渑判?br />6.6.3 關(guān)鍵路徑
習(xí)題
第7章 查找
7.1 查找的基本概念
7.2 順序表的查找
7.2.1 順序查找
7.2.2 折半查找
7.2.3 索引順貢序表的查找
7.3 樹表的查找
7.3.1 二叉排序樹
7.3.2 平衡二叉樹
7.3.3 B-樹
7.4 P臺希表及其查找
7.4.1 什么是哈希
7.4.2 哈希函數(shù)的構(gòu)造方法
7.4.3 處理沖突的幾種方法
7.4.4 哈希表的查找及其效率分析
習(xí)題
第8章 內(nèi)部排序
8.1 排序的一般概念
8.2 插入排序
8.2.1 直接插入排序
8.2.2 折半插入排序
8.2.3 希爾排序
8.3 交換排序
8.3.1 起泡排序
8.3.2 快速排序
8.4 選擇排序
8.4.1 簡單選擇排序
8.4.2 堆排序
8.5 歸并排序
8.5.1 兩個(gè)有序序列的歸并操作
8.5.2 歸并排序
8.6 分配排序和基數(shù)排序
8.7 有關(guān)內(nèi)部排序算法的比較
習(xí)題
第9章 算法設(shè)計(jì)技術(shù)
9.1 求解問題的基本思路
9.2 分治技術(shù)
9.2.1 分治策略的思想
9.2.2 大整數(shù)乘法
9.2.3 矩陣相乘的Strassen算法
9.2.4 選擇問題的分治算法
9.3 貪心技術(shù)
9.3.1 貪心算法的思想
9.3.2 活動安排問題
9.3.3 背包問題
9.3.4 多機(jī)調(diào)度問題的近似算法
9.3.5 單源最短路徑問題的Dijkstra算法
9.4 回溯與分枝限界技術(shù)
9.4.1 兩個(gè)適合回溯技術(shù)的問題
9.4.2 八后問題
9.4.3 0-1背包問題的回溯算法
9.4.4 分枝限界算法
9.5 動態(tài)規(guī)劃技術(shù)
9.5.1 Fibonacci數(shù)的計(jì)算
9.5.2 矩陣連乘的順序問題
9.5.3 適合動態(tài)規(guī)劃算法的兩個(gè)條件
綜合練習(xí)題一
綜合練習(xí)題二
綜合練習(xí)題三
綜合練習(xí)題四
綜合練習(xí)題五
綜合模擬題一
綜合模擬題二
參考文獻(xiàn)