數(shù)據(jù)結構：C語言描述

第1章  概論
1.1  什么是數(shù)據(jù)結構
1.2  數(shù)據(jù)抽象和抽象數(shù)據(jù)類型
1.3  數(shù)據(jù)結構的描述
1.4  算法和算法分析
  1.4.1  算法及其性能標準
  1.4.2  算法的時間復雜度
  1.4.3  漸近時間復雜度
  1.4.4  最壞、最好和平均情況時間復雜度
  1.4.5  算法的空間復雜度
小結
習題1
第2章  兩種基本數(shù)據(jù)結構
2.1  結構與聯(lián)合
  2.1.1  結構
  2.1.2  聯(lián)合
2.2  數(shù)組
  2.2.1  一維數(shù)組
  2.2.2  二維數(shù)組
  2.2.3  多維數(shù)組
2.3  鏈表
  2.3.1  指針
  2.3.2  單鏈表
  2.3.3  帶表頭結點的單鏈表
  2.3.4  循環(huán)鏈表
  2.3.5  雙向鏈表
小結
習題2
第3章  堆棧和隊列
3.1  堆棧
  3.1.1  堆棧ADT
  3.1.2  堆棧的順序表示
  3.1.3  堆棧的鏈接表示
3.2  隊列
  3.2.1  隊列ADT
  3.2.2  隊列的順序表示
  3.2.3  隊列的鏈接表示
3.3*  表達式的計算
  3.3.1表達式
  3.3.2  中綴表達式轉(zhuǎn)換為后綴表達式
  3.3.3  計算后綴表達式的值
3.4*  遞歸和遞歸過程
  3.4.1  遞歸的概念
  3.4.2遞歸的實現(xiàn)
3.5*  演示和測試
小結
習題3
第4章  線性表和數(shù)組
4.1  線性表
  4.1.1  線性表ADT
  4.1.2  線性表的順序表示
  4.1.3  線性表的鏈接表示
  4.1.4  兩種存儲表示的比較
4.2*  多項式的算術運算
  4.2.1  多項式ADT
  4.2.2  多項式的鏈接表示
  4.2.3  多項式的輸入和輸出
  4.2.4  多項式相加
4.3  數(shù)組作為抽象數(shù)據(jù)類型
4.4  特殊矩陣
  4.4.1  對稱矩陣
  4.4.2*  帶狀矩陣
4.5  稀疏矩陣
  4.5.1  稀疏矩陣ADT
  4.5.2  稀疏矩陣的順序表示
  4.5.3  稀疏矩陣轉(zhuǎn)置
  4.5.4*  稀疏矩陣相乘
  4.5.5  稀疏矩陣的正交鏈表表示
  4.5.6*  建立正交鏈表
  4.5.7*  打印正交鏈表
小結
習題4
第5章  字符串和廣義表
5.1  字符串
  5.1.1  字符串ADT
  5.1.2  字符串的存儲表示
  5.1.3  簡單模式匹配算法
  5.1.4*  模式匹配的KMP算法
5.2*  廣義表
  5.2.1  廣義表的概念
  5.2.2  廣義表ADT
  5.2.3  廣義表的存儲表示
  5.2.4  廣義表的算法
小結
習題5
第6章  樹
6.1  樹的墓本概念
  6.1.1  樹的定義
  6.1.2  基本術語
6.2  二叉樹
  6.2.1  二叉樹的定義和性質(zhì)
  6.2.2  二叉樹ADT
  6.2.3  二叉樹的存儲表示
  6.2.4  二叉樹的遍歷
  6.2.5*  二叉樹遍歷的非遞歸算法
  6.2.6*  二叉樹遍歷的匝用實例
  6.2.7*  線索二叉樹
6.3  樹和森林
  6.3.1  森林與二叉樹的轉(zhuǎn)換
  6.3.2  樹和森林的存儲表示
  6.3.3  樹和森林的遍歷
6.4*  堆和優(yōu)先權隊列
  6.4.1  堆
  6.4.2  優(yōu)先權隊列
6.5  哈夫曼樹和哈夫曼編碼
  6.5.1  樹的路徑長度
  6.5.2  哈夫曼樹和哈夫曼算法
  6.5.3  哈夫曼編碼
6.6*  并查集和等價關系
  6.6.1  并查集
  6.6.2  并查集的實現(xiàn)
  6.6.3  集合按等價關系分組
小結
習題6
第7章集合和搜索
7.1  集合及其表示
  7.1.1  集合和搜索
  7.1.2  集合ADT
  7.1.3  集合的表示
7.2  順序搜索
7.3  二分搜索
  7.3.1  對半搜索
  7.3.2*  二叉判定樹
  7.3.3*  斐波那契搜索
7.4*  搜索算法的時間下界
小結
習題7
第8章搜索樹
8.1  二叉搜索樹
  8.1.1  二叉搜索樹的定義
  8.1.2  二叉搜索樹的搜索
  8.1.3  二叉搜索樹的插入
  8.1.4  二叉搜索樹的刪除
  8.1.5*  二叉搜索樹的高度
8.2*  二叉平衡樹
  8.2.1  二叉平衡樹的定義
  8.2.2  二叉平衡樹的平衡旋轉(zhuǎn)
  8.2.3  二叉平衡樹的插入
  8.2.4  二叉平衡樹的刪除
  8.2.5  二叉平衡數(shù)的高度
8.3  B-樹
  8.3.I  m叉搜索樹
  8.3.2  B—樹的定義
  8.3.3  B—樹的高度
  8.3.4  B-樹的搜索
  8.3.5  B—樹的插入
  8.3.6  B—樹的刪除
8.4*  鍵樹
  8.4.1  鍵樹的定義
  8.4.2  雙鏈樹
  8.4.3  Trie樹
8.5*  伸展樹
小結
習題8
第9章  跳表和散列表
9.1  字典
9.2*  跳表
  9.2.1  什么是跳表
  9.2.2  跳表的搜索
  9.2.3  跳表的插入
  9.2.4  跳表的刪除
9.3  散列表
  9.3.1  散列技術
  9.3.2  散列函數(shù)
  9.3.3  解決沖突的拉鏈法
  9.3.4  解決沖突的線性探查法
  9.3.5  解決沖突的其他開地址法
  9.3.6  性能分析
小結
習題9
第10  章圖
10.1  圖的基本概念
  10.1.1  圖的定義與術語
  10.1.2  圖ADT
10.2  圖的存儲結構
  10.2.1  矩陣表示法
  10.2.2  鄰接表表示法
  10.2.3*  多重表表示法
10.3  圖的遍歷
  10.3.1  深度優(yōu)先遍歷
  10.3.2  寬度優(yōu)先遍歷
10.4  拓撲排序和關鍵路徑
  10.4.1  拓撲排序
  10.4.2*  關鍵路徑
10.5  最小代價生成樹
  10.5.1  普里姆算法
  10.5.2*  克魯斯卡爾算法
10.6*  最短路徑
  10.6.1  單源最短路徑
  10.6.2  所有頂點之間的最短路徑
小結
習題10
第11章  內(nèi)排序
11.1  排序的基本概念
11.2  插入排序
  11.2.1  直接插入排序
  11.2.2*  希爾排序
11.3  交換排序
  11.3.1  冒泡排序
  11.3.2  快速排序
11.4  合并排序
  11.4.1  兩路合并排序
  11.4.2  合并排序的迭代算法
  11.4.3*  鏈表上的合并排序
11.5  選擇排序
  11.5.1  簡單選擇排序
  11.5.2*  堆排序
11.6*  排序算法的時間下界
11.7*  基數(shù)排序
小結
習題11
第12章  文件和外排序
12.1*  輔助存儲器簡介
  12.1.1  主存儲器和輔助存儲器
  12.1.2  磁盤存儲器
12.2  文件
  12.2.1  文件的基本概念
  12.2.2  文件的組織方式
  12.2.3  C語言文件
12.3  文件的索引結構
  12.3.1  靜態(tài)索引結構
  12.3.2  動態(tài)索引結構
12.4*  外排序
  12.4.1  外排序的基本過程
  12.4.2  初始游程的生成
  12.4.3  多路合并
  12.4.4  最佳合并樹
小結
習題12
附錄A  軟件工程概述
  一、 軟件開發(fā)方法學
  二、 系統(tǒng)測試方法
附錄B  實習要求和實習題
  一、實習目的
  二、實習要求
  三、實習步驟
  四、實習報告
  五、實習題
附錄C  專用名詞中英文對照表
參考文獻