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

出版說明
前言
第1章 數(shù)據(jù)結(jié)構(gòu)與算法
1.1 引言
1.1.1 為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)
1.1.2 數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容
1.2 數(shù)據(jù)結(jié)構(gòu)的概念
1.2.1 基本概念和術(shù)語(yǔ)
1.2.2 抽象數(shù)據(jù)類型
1.3 數(shù)據(jù)結(jié)構(gòu)的描述方法
1.3.1 數(shù)據(jù)結(jié)構(gòu)的C語(yǔ)言描述
1.3.2 數(shù)據(jù)結(jié)構(gòu)的C++語(yǔ)言描述
1.3.3 數(shù)據(jù)結(jié)構(gòu)的Java語(yǔ)言描述
1.4 算法
1.4.1 算法及其特征
1.4.2 算法的描述
1.4.3 算法的性能分析
1.5 典型例題
1.6 本章小結(jié)
1.6.1 知識(shí)點(diǎn)小結(jié)
1.6.2 擴(kuò)展學(xué)習(xí)導(dǎo)讀
練習(xí)題
實(shí)驗(yàn)題
題目1 比較算法復(fù)雜性描述函數(shù)的增長(zhǎng)
題目2 矩陣連乘算法的時(shí)間和空間復(fù)雜度
第2章 遞歸
2.1 引言
2.1.1 問題的提出
2.1.2 什么是遞歸
2.2 遞歸調(diào)用的實(shí)現(xiàn)原理
2.2.1 遞歸算法的構(gòu)成
2.2.2 遞歸調(diào)用的內(nèi)部過程
2.2.3 遞歸的正確性證明
2.3 遞歸轉(zhuǎn)化為非遞歸
2.3.1 遞歸轉(zhuǎn)化為遞推
2.3.2 遞歸轉(zhuǎn)化為回溯
2.3.3 手工模擬遞歸
2.4 典型例題
2.5 本章小結(jié)
2.5.1 知識(shí)點(diǎn)小結(jié)
2.5.2 擴(kuò)展學(xué)習(xí)導(dǎo)讀
練習(xí)題
實(shí)驗(yàn)題
題目1 全排列的遞歸實(shí)現(xiàn)
題目2 八皇后問題
題目3 比較遞歸與非遞歸算法的時(shí)空效率
第3章 線性結(jié)構(gòu)
3.1 引言
3.1.1 問題的提出
3.1.2 線性表的定義
3.1.3 線性表的基本運(yùn)算
3.2 線性表的順序存儲(chǔ)與實(shí)現(xiàn)
3.2.1 順序表
3.2.2 順序表上基本運(yùn)算的實(shí)現(xiàn)
3.2.3 順序表應(yīng)用舉例
3.3 線性表的鏈?zhǔn)酱鎯?chǔ)與實(shí)現(xiàn)
3.3.1 單鏈表
3.3.2 單鏈表上基本運(yùn)算的實(shí)現(xiàn)
3.3.3 循環(huán)鏈表
3.3.4 雙向鏈表
3.3.5 鏈表應(yīng)用舉例
3.4 順序表和鏈表的比較
3.5 堆棧
3.5.1 堆棧的定義及基本運(yùn)算
3.5.2 堆棧的存儲(chǔ)及運(yùn)算實(shí)現(xiàn)
3.5.3 堆棧的應(yīng)用舉例
3.6 隊(duì)列
3.6.1 隊(duì)列的定義及基本運(yùn)算
3.6.2 隊(duì)列的存儲(chǔ)及運(yùn)算實(shí)現(xiàn)
3.6.3 隊(duì)列的應(yīng)用舉例
3.7 其他線性結(jié)構(gòu)及擴(kuò)展
3.7.1 字符串
3.7.2 數(shù)組
3.7.3 特殊矩陣
3.7.4 稀疏矩陣
3.8 典型例題
3.9 本章小結(jié)
3.9.1 知識(shí)點(diǎn)小結(jié)
3.9.2 擴(kuò)展學(xué)習(xí)導(dǎo)讀
練習(xí)題
實(shí)驗(yàn)題
題目1 Josephus環(huán)問題
題目2 一元多項(xiàng)式運(yùn)算
題目3 模擬停車場(chǎng)管理
第4章 樹結(jié)構(gòu)
4.1 引言
4.1.1 問題提出
4.1.2 相關(guān)概念
4.2 二叉樹
4.2.1 二叉樹的基本運(yùn)算
4.2.2 二叉樹的主要性質(zhì)
4.2.3 二叉樹的存儲(chǔ)
4.2.4 二叉樹基本運(yùn)算的實(shí)現(xiàn)
4.3 二叉樹的遍歷
4.3.1 遞歸方法實(shí)現(xiàn)二叉樹遍歷
4.3.2 非遞歸方法實(shí)現(xiàn)二叉樹的三種遍歷
4.3.3 按層次遍歷二叉樹
4.4 二叉樹遍歷的應(yīng)用
4.4.1 構(gòu)造二叉樹的二叉鏈表存儲(chǔ)
4.4.2 在二叉樹中查找值為x的數(shù)據(jù)元素
4.4.3 統(tǒng)計(jì)給定二叉樹中葉子結(jié)點(diǎn)的數(shù)目
4.4.4 表達(dá)式運(yùn)算
4.4.5 由遍歷序列恢復(fù)二叉樹
4.5 線索二叉樹
4.5.1 線索二叉樹的定義及其結(jié)構(gòu)
4.5.2 線索二叉樹的創(chuàng)建
4.5.3 線索二叉樹的遍歷
4.6 最優(yōu)二叉樹
4.6.1 最優(yōu)二叉樹的概念
4.6.2 最優(yōu)二叉樹的構(gòu)造
4.6.3 最優(yōu)二叉樹的應(yīng)用——哈夫曼編碼
4.7 樹
4.7.1 樹的基本操作
4.7.2 樹的表示
4.7.3 樹的存儲(chǔ)
4.7.4 樹和森林與二叉樹之間的轉(zhuǎn)換
4.7.5 樹或森林的遍歷
4.7.6 樹的應(yīng)用
4.8 典型例題
4.9 本章小結(jié)
4.9.1 知識(shí)點(diǎn)小結(jié)
4.9.2 擴(kuò)展學(xué)習(xí)導(dǎo)讀
練習(xí)題
實(shí)驗(yàn)題
第5章 圖結(jié)構(gòu)
5.1 引言
5.1.1 問題的提出
5.1.2 相關(guān)概念
5.1.3 圖的基本操作
5.2 圖的存儲(chǔ)
5.2.1 鄰接矩陣
5.2.2 鄰接表
5.3 圖的遍歷
5.3.1 深度優(yōu)先搜索
5.3.2 廣度優(yōu)先搜索
5.3.3 遍歷圖的簡(jiǎn)單應(yīng)用
5.4 生成樹和最小生成樹
5.4.1 生成樹和生成森林
5.4.2 最小生成樹
5.4.3 構(gòu)造最小生成樹的Prim算法
5.4.4 構(gòu)造最小生成樹的Kruskal算法
5.5 最短路徑
5.5.1 單源點(diǎn)最短路徑——Dijkstra算法
5.5.2 每一對(duì)頂點(diǎn)之間的最短路徑
5.6 拓?fù)渑判蚺c關(guān)鍵路徑
5.6.1 有向無(wú)環(huán)圖的概念
5.6.2 AOV網(wǎng)與拓?fù)渑判?br />5.6.3 AOE網(wǎng)與關(guān)鍵路徑
5.7 典型例題
5.8 本章小結(jié)
5.8.1 知識(shí)點(diǎn)小結(jié)
5.8.2 擴(kuò)展學(xué)習(xí)導(dǎo)讀
練習(xí)題
實(shí)驗(yàn)題
題目校園導(dǎo)游程序
第6章 查找技術(shù)
6.1 引言
6.1.1 問題提出
6.1.2 相關(guān)概念
6.2 線性表查找
6.2.1 順序查找
6.2.2 順序存儲(chǔ)的有序表查找
6.3 樹結(jié)構(gòu)查找
6.3.1 二叉排序樹
6.3.2 平衡二叉樹
6.4 散列表查找
6.4.1 基本概念
6.4.2 散列函數(shù)的構(gòu)造方法
6.4.3 處理沖突的方法
6.4.4 散列表的性能分析
6.5 查找方法的比較
6.6 典型例題
6.7 本章小結(jié)
6.7.1 知識(shí)點(diǎn)小結(jié)
6.7.2 擴(kuò)展學(xué)習(xí)導(dǎo)讀
練習(xí)題
實(shí)驗(yàn)題
題目1 職工信息檢索系統(tǒng)
題目2 個(gè)人圖書管理系統(tǒng)
第7章 排序技術(shù)
7.1 引言
7.1.1 問題的提出
7.1.2 相關(guān)概念
7.2 插入排序
7.2.1 直接插入排序
7.2.2 折半插入排序
7.2.3 希爾排序
7.3 交換排序
7.3.1 冒泡排序
7.3.2 快速排序
7.4 選擇排序
7.4.1 簡(jiǎn)單選擇排序
7.4.2 樹結(jié)構(gòu)選擇排序
7.4.3 堆排序
7.5 歸并排序
7.6 基數(shù)排序
7.6.1 多關(guān)鍵碼排序
7.6.2 鏈?zhǔn)交鶖?shù)排序
7.7 排序方法比較
7.7.1 性能比較
7.7.2 不同排序方法的適用情況
7.8 典型例題
7.9 本章小結(jié)
7.9.1 知識(shí)點(diǎn)小結(jié)
7.9.2 擴(kuò)展學(xué)習(xí)導(dǎo)讀
練習(xí)題
實(shí)驗(yàn)題
題目 各種內(nèi)部排序的性能比較
第8章 擴(kuò)展應(yīng)用舉例
8.1 求最大子段和
8.1.1 問題描述
8.1.2 問題分析與解決
8.2 表達(dá)式樹的構(gòu)造
8.2.1 問題描述
8.2.2 問題分析與解決
8.3 由等價(jià)關(guān)系求劃分
8.3.1 問題描述
8.3.2 問題分析與解決
8.4 本章小結(jié)
8.4.1 知識(shí)點(diǎn)小結(jié)
8.4.2 擴(kuò)展學(xué)習(xí)導(dǎo)讀
練習(xí)題
實(shí)驗(yàn)題
題目1 模擬銀行排隊(duì)辦理業(yè)務(wù)
題目2 0-1背包問題
附錄
附錄A 實(shí)驗(yàn)要求
附錄B 模擬試卷
模擬試卷一（本科水平）
模擬試卷二（本科水平）
模擬試卷三（研究生入學(xué)考試水平）
模擬試卷四（研究生入學(xué)考試水平）
附錄C 2012年全國(guó)碩士研究生入學(xué)
統(tǒng)一考試計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科聯(lián)考試卷（“數(shù)據(jù)結(jié)構(gòu)”部分）
參考文獻(xiàn)