數(shù)據(jù)結(jié)構(gòu)：C語(yǔ)言描述

出版者的話
編委會(huì)
叢書(shū)序言
前言
教學(xué)安排建議
第1章 緒論
1.1 數(shù)據(jù)結(jié)構(gòu)的概念及分類(lèi)
1.1.1 為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)
1.1.2 與數(shù)據(jù)結(jié)構(gòu)相關(guān)的基本術(shù)語(yǔ)
1.1.3 數(shù)據(jù)結(jié)構(gòu)的分類(lèi)
1.1.4 數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu)
1.1.5 定義在數(shù)據(jù)結(jié)構(gòu)上的操作
1.2 使用c語(yǔ)言描述數(shù)據(jù)結(jié)構(gòu)
1.2.1 數(shù)據(jù)類(lèi)型
1.2.2 算法的控制結(jié)構(gòu)
1.2.3 算法的函數(shù)結(jié)構(gòu)
1.2.4 動(dòng)態(tài)存儲(chǔ)分配
1.2.5 邏輯和關(guān)系運(yùn)算的約定
1.2.6 輸入與輸出
1.3 算法和算法設(shè)計(jì)
1.3.1 算法的定義和特性
1.3.2 算法的設(shè)計(jì)步驟
1.3.3 算法設(shè)計(jì)的基本方法
1.4 算法分析與度量
1.4.1 算法的評(píng)價(jià)標(biāo)準(zhǔn)
1.4.2 算法的時(shí)間和空間復(fù)雜度度量
1.4.3 算法的漸近分析
小結(jié)
習(xí)題
第2章 線性表
2.1 線性表的定義及操作
2.1.1 線性表的定義和特點(diǎn)
2.1.2 線性表的主要操作
2.2 順序表
2.2.1 順序表的定義和特點(diǎn)
2.2.2 順序表的結(jié)構(gòu)定義
2.2.3 順序表主要操作的實(shí)現(xiàn)
2.2.4 順序表主要操作的性能分析
2.2.5 順序表的應(yīng)用舉例
2.3 單鏈表
2.3.1 單鏈表的定義和特點(diǎn)
2.3.2 單鏈表的結(jié)構(gòu)定義
2.3.3 單鏈表中的插入與刪除
2.3.4 帶頭結(jié)點(diǎn)的單鏈表
2.3.5 單鏈表主要操作的性能分析
2.3.6 單鏈表的順序訪問(wèn)與尾遞歸
2.3.7 單鏈表的應(yīng)用舉例
2.4 順序表與線性鏈表的比較
2.5 線性鏈表的其他變形
2.5.1 循環(huán)鏈表
2.5.2 雙向鏈表
2.5.3 靜態(tài)鏈表
2.6 線性表的應(yīng)用：字符串
2.6.1 字符串的概念
2.6.2 字符串的初始化和賦值
2.6.3 c語(yǔ)言中有關(guān)字符串的庫(kù)函數(shù)
2.6.4 自定義字符串的存儲(chǔ)表示
2.7 單鏈表的應(yīng)用：一元多項(xiàng)式及其運(yùn)算
2.7.1 一元多項(xiàng)式的表示
2.7.2 多項(xiàng)式的結(jié)構(gòu)定義
2.7.3 多項(xiàng)式的加法
2.7.4 多項(xiàng)式的乘法
小結(jié)
習(xí)題
第3章 棧、隊(duì)列和數(shù)組
3.1 棧
3.1.1 棧的概念
3.1.2 順序棧
3.1.3 鏈?zhǔn)綏?br />3.1.4 棧的混洗
3.2 隊(duì)列
3.2.1 隊(duì)列的概念
3.2.2 循環(huán)隊(duì)列
3.2.3 鏈?zhǔn)疥?duì)列
3.3 棧的應(yīng)用
3.3.1 數(shù)制轉(zhuǎn)換
3.3.2 括號(hào)匹配
3.3.3 表達(dá)式的計(jì)算與優(yōu)先級(jí)處理
3.3.4 棧與遞歸的實(shí)現(xiàn)
3.4 隊(duì)列的應(yīng)用
3.4.1 打印楊輝三角形與逐行處理
3.4.2 電路布線與兩點(diǎn)間的最短路徑
3.5 數(shù)組
3.5.1 一維數(shù)組
3.5.2 多維數(shù)組
3.5.3 數(shù)組的應(yīng)用舉例
3.6 在算法設(shè)計(jì)中使用遞歸
3.6.1 漢諾塔問(wèn)題與分治法
3.6.2 迷宮問(wèn)題與回溯法
3.6.3 計(jì)算組合數(shù)與動(dòng)態(tài)規(guī)劃
3.7 特殊矩陣
3.7.1 對(duì)稱(chēng)矩陣的壓縮存儲(chǔ)
3.7.2 三對(duì)角線矩陣的壓縮存儲(chǔ)
3.7.3 稀疏矩陣的壓縮存儲(chǔ)
3.8 雙端隊(duì)列
3.8.1 雙端隊(duì)列的概念
3.8.2 雙端隊(duì)列的主要操作
3.8.3 雙端隊(duì)列的順序存儲(chǔ)表示
3.8.4 雙端隊(duì)列的鏈接存儲(chǔ)表示
小結(jié)
習(xí)題
第4章 樹(shù)與二叉樹(shù)
4.1 樹(shù)的基本概念
4.1.1 樹(shù)的定義和術(shù)語(yǔ)
4.1.2 樹(shù)的基本操作
4.2 二叉樹(shù)
4.2.1 二叉樹(shù)的概念
4.2.2 二叉樹(shù)的性質(zhì)
4.2.3 二叉樹(shù)的主要操作
4.3 二叉樹(shù)的存儲(chǔ)表示
4.3.1 二叉樹(shù)的順序存儲(chǔ)表示
4.3.2 二叉樹(shù)的鏈表存儲(chǔ)表示
4.4 二叉樹(shù)的遍歷
4.4.1 二叉樹(shù)遍歷的遞歸算法
4.4.2 遞歸遍歷算法的應(yīng)用舉例
4.4.3 二叉樹(shù)遍歷的非遞歸算法
4.4.4 非遞歸遍歷算法的應(yīng)用舉例
4.4.5 二叉樹(shù)的計(jì)數(shù)
4.5 線索二叉樹(shù)
4.5.1 線索二叉樹(shù)的概念
4.5.2 線索二叉樹(shù)的種類(lèi)
4.5.3 中序線索二叉樹(shù)的建立和遍歷
4.5.4 前序與后序線索二叉樹(shù)
4.6 樹(shù)與森林
4.6.1 樹(shù)的存儲(chǔ)表示
4.6.2 森林與二叉樹(shù)的轉(zhuǎn)換
4.6.3 樹(shù)與森林的深度優(yōu)先遍歷
4.6.4 樹(shù)與森林的廣度優(yōu)先遍歷
4.6.5 樹(shù)遍歷算法的應(yīng)用舉例
4.7 二叉樹(shù)的應(yīng)用：二叉排序樹(shù)
4.7.1 二叉排序樹(shù)的概念
4.7.2 二叉排序樹(shù)的查找
4.7.3 二叉排序樹(shù)的插入
4.7.4 二叉排序樹(shù)的刪除
4.7.5 二叉排序樹(shù)的性能分析
4.8 二叉樹(shù)的應(yīng)用：平衡二叉樹(shù)
4.8.1 平衡二叉樹(shù)的概念
4.8.2 平衡化旋轉(zhuǎn)
4.8.3 平衡二叉樹(shù)的插入
4.8.4 平衡二叉樹(shù)的刪除
4.8.5 平衡二叉樹(shù)的性能分析
4.9 二叉樹(shù)的應(yīng)用：huffman樹(shù)
4.9.1 帶權(quán)路徑長(zhǎng)度的概念
4.9.2 huffman樹(shù)與huffman算法
4.9.3 huffman樹(shù)的應(yīng)用：最優(yōu)判定樹(shù)
4.9.4 huffman樹(shù)的應(yīng)用：huffman編碼
4.10 二叉樹(shù)的應(yīng)用：堆
4.10.1 小根堆和大根堆
4.10.2 堆的建立
4.10.3 堆的插入
4.10.4 堆的刪除
4.11 樹(shù)的應(yīng)用：八皇后問(wèn)題與樹(shù)的剪枝
4.11.1 八皇后問(wèn)題的提出
4.11.2 八皇后問(wèn)題的狀態(tài)樹(shù)
4.11.3 八皇后問(wèn)題算法
小結(jié)
習(xí)題
第5章 圖
5.1 圖的基本概念
5.1.1 與圖有關(guān)的概念
5.1.2 圖的基本操作
5.2 圖的存儲(chǔ)結(jié)構(gòu)
5.2.1 圖的鄰接矩陣表示
5.2.2 圖的鄰接表表示
5.2.3 鄰接矩陣表示與鄰接表表示的比較
5.2.4 圖的鄰接多重表表示
5.3 圖的遍歷
5.3.1 深度優(yōu)先搜索
5.3.2 廣度優(yōu)先搜索
5.3.3 連通分量
5.3.4 重連通圖
5.3.5 歐拉回路與一筆畫(huà)問(wèn)題
5.3.6 有向圖的強(qiáng)連通分量
5.4 最小生成樹(shù)
5.4.1 最小生成樹(shù)求解和貪婪法
5.4.2 kruskal算法
5.4.3 prim算法
5.5 最短路徑
5.5.1 非負(fù)權(quán)重的單源最短路徑
5.5.2 所有頂點(diǎn)之間的最短路徑
5.5.3 無(wú)權(quán)重的最短路徑
5.6 用頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)（aov網(wǎng)絡(luò)）
5.7 用邊表示活動(dòng)的網(wǎng)絡(luò)（aoe網(wǎng)絡(luò)）
小結(jié)
習(xí)題
第6章 查找
6.1 查找的基本概念與性能分析
6.1.1 查找的概念
6.1.2 查找算法的性能分析
6.2 順序查找法
6.2.1 順序表上的順序查找算法
6.2.2 線性鏈表上的順序查找算法
6.3 折半查找法
6.3.1 一般的折半查找法
6.3.2 擬最優(yōu)查找樹(shù)：折半查找的改進(jìn)方法
6.3.3 斐波那契查找：折半查找的變形
6.3.4 插值查找：折半查找的變形
6.4 b樹(shù)
6.4.1 索引順序表與分塊查找
6.4.2 多級(jí)索引結(jié)構(gòu)與m叉查找樹(shù)
6.4.3 b樹(shù)的概念
6.4.4 b樹(shù)上的查找
6.4.5 b樹(shù)上的插入
6.4.6 b樹(shù)上的刪除
6.4.7 b+樹(shù)
6.5 散列表及其查找
6.5.1 散列的概念
6.5.2 常見(jiàn)的散列函數(shù)
6.5.3 解決沖突的開(kāi)地址法
6.5.4 解決沖突的鏈地址法
6.5.5 散列法分析
小結(jié)
習(xí)題
第7章 排序
7.1 排序的概念與算法性能
7.1.1 排序的概念
7.1.2 排序算法的性能
7.1.3 數(shù)據(jù)表和靜態(tài)鏈表的結(jié)構(gòu)定義
7.2 幾種簡(jiǎn)單的排序方法
7.2.1 直接插入排序
7.2.2 基于鏈表的直接插入排序
7.2.3 折半插入排序
7.2.4 起泡排序
7.2.5 簡(jiǎn)單選擇排序
7.3 希爾排序
7.3.1 希爾排序的設(shè)計(jì)思路
7.3.2 希爾排序的算法實(shí)現(xiàn)
7.4 快速排序
7.4.1 快速排序的設(shè)計(jì)思路
7.4.2 快速排序的算法描述
7.4.3 快速排序的算法分析
7.4.4 快速排序的改進(jìn)算法
7.5 堆排序
7.5.1 大根堆
7.5.2 堆排序的算法
7.5.3 堆排序的算法分析
7.6 歸并排序
7.6.1 兩路歸并
7.6.2 遞歸的歸并排序算法
7.6.3 迭代的歸并排序算法
7.6.4 基于鏈表的歸并排序算法
7.7 基數(shù)排序
7.7.1 基數(shù)排序的概念
7.7.2 msd基數(shù)排序
7.7.3 lsd基數(shù)排序
7.8 內(nèi)排序算法的分析與比較
7.8.1 排序方法的下界
7.8.2 各種內(nèi)排序方法的比較
7.8.3 鏈表排序結(jié)果的重排
小結(jié)
習(xí)題
附錄一 2009～2011年全國(guó)考研計(jì)算機(jī)學(xué)科聯(lián)考專(zhuān)業(yè)基礎(chǔ)綜合考試數(shù)據(jù)結(jié)構(gòu)部分試題解析
附錄二 大作業(yè)要求及樣例
參考文獻(xiàn)