數據結構實例教程（C語言版）

目　錄

第1章　緒論及C語言介紹　1
1.1　基本概念與術語　1
1.2　學習數據結構的意義　3
1.3　算法的描述和分析　5
1.4　C語言相關知識介紹　6
知識實踐一　學生管理系統(tǒng)登錄模塊設計　9
習題　10

第2章　線性表的結構分析與應用　12
2.1　線性表的邏輯結構　12
2.2　線性表的順序存儲結構　13
2.2.1　順序表定義及地址計算　13
2.2.2　順序表基本運算　13
2.3　線性表的鏈式存儲結構　16
2.3.1　單鏈表　16
2.3.2　循環(huán)鏈表　18
2.4　順序表和鏈表的比較　19
知識實踐二　學生管理系統(tǒng)成績插入、刪除模塊設計　20
知識實踐三　嵌入式系統(tǒng)中任務的創(chuàng)建和刪除模擬設計　23
習題　25

第3章　棧和隊列的結構分析與應用　27
3.1　?！?7
3.1.1　棧的定義及基本運算　27
3.1.2　順序棧及操作實現　28
3.1.3　鏈棧及操作實現　30
3.2　隊列　32
3.2.1　隊列的定義及基本運算　32
3.2.2　順序隊列及操作實現　32
3.2.3　鏈隊列及操作實現　35
知識實踐四　計算器中進制轉換模塊設計　37
知識實踐五　單片機或者嵌入式系統(tǒng)中斷模擬設計　39
知識實踐六　學生舞會舞伴配對系統(tǒng)設計　42
習題　44

第4章　字符串的結構分析與應用　46
4.1　串的定義及其運算　46
4.1.1　串的基本概念　46
4.1.2　串的基本運算　47
4.2　串的存儲結構　47
4.2.1　串的順序存儲結構　47
4.2.2　串的鏈式存儲結構　48
4.2.3　子串的定位運算　48
知識實踐七　學生管理系統(tǒng)家庭情況模塊設計　49
習題　50

第5章　二維數組及廣義表的結構分析　51
5.1　二維數組的存儲結構及求址方法　51
5.2　矩陣的壓縮存儲　52
5.2.1　特殊矩陣　52
5.2.2　稀疏矩陣　53
5.3　廣義表的概念　54
知識實踐八　求二維數組元素在內存中的存儲位置　55
習題　56

第6章　樹和二叉樹的結構分析與應用　57
6.1　樹的概念　57
6.2　二叉樹　59
6.2.1　二叉樹的定義　59
6.2.2　二叉樹的性質　60
6.2.3　二叉樹的存儲結構　60
6.3　 二叉樹的遍歷　64
6.4　線索二叉樹　66
6.5　樹和森林　67
6.5.1　樹、森林與二叉樹的相互轉換　67
6.5.2　樹的存儲結構　69
6.5.3　樹和森林的遍歷　71
6.6　哈夫曼樹及其應用　72
6.6.1　哈夫曼樹的定義　72
6.6.2　哈夫曼樹的構造　73
6.6.3　哈夫曼樹編碼　74
知識實踐九　利用二叉樹遍歷實現學生成績排序模塊設計　74
習題　76

第7章　圖的結構分析與應用　80
7.1　圖的概念及相關術語　80
7.1.1　圖的概念　80
7.1.2 圖的相關術語　81
7.2　圖的存儲結構　83
7.2.1　鄰接矩陣表示法　83
7.2.2　鄰接表表示法　84
7.3　圖的遍歷　86
7.3.1　深度優(yōu)先遍歷　87
7.3.2　廣度優(yōu)先遍歷　89
7.4　最小生成樹　90
7.4.1　普里姆算法　91
7.4.2　克魯斯卡爾算法　91
7.5　最短路徑　92
7.5.1　單源最短路徑　92
7.5.2　每一對頂點之間的最短路徑　93
知識實踐十　江蘇省地級市組成的地圖遍歷　96
習題　98

第8章　查找的分析與應用　101
8.1　基本概念　101
8.2　線性表查找　102
8.2.1　順序查找　102
8.2.2　二分查找　103
8.2.3　分塊查找　105
8.3　二叉排序樹　106
8.3.1　二叉排序樹定義　106
8.3.2　二叉排序樹的插入和生成　107
8.3.3　二叉排序樹的刪除　108
8.3.4　二叉排序樹的查找　109
8.4　散列技術　109
8.4.1　散列表的概念　109
8.4.2　散列函數的構造方法　110
8.4.3　處理沖突的方法　110
知識實踐十一　利用二分法查找實現學生信息查詢模塊設計　111
習題　113

第9章　排序的分析與應用　114
9.1　排序的基本概念　114
9.1.1　排序的定義　114
9.1.2　相關概念　115
9.2　插入排序　116
9.2.1　直接插入排序　117
9.2.2　希爾排序　120
9.3　交換排序　121
9.3.1　冒泡排序　121
9.3.2　快速排序　123
9.4　選擇排序　126
9.4.1　直接選擇排序　126
9.4.2　堆排序　128
9.5　歸并排序　131
9.6　各種內部排序算法的比較　133
知識實踐十二　學生總成績排序模塊設計　134
習題　136

第10章　文件　138
10.1　文件的概念　138
10.1.1　文件的基本概念　138
10.1.2　文件的邏輯結構和物理結構　139
10.1.3　文件的操作　139
10.2　順序文件　140
10.2.1　存儲在順序存儲器上的順序文件　140
10.2.2　存儲在直接存儲器上的順序文件　140
10.3　索引文件　140
10.4　索引順序文件　141
10.4.1　索引順序文件的特點　141
10.4.2　VSAM文件的組織方法　141
10.5　散列文件　142
10.5.1　散列文件的組織方式　142
10.5.2　散列文件的操作　142
10.6　多關鍵字文件　143
10.6.1　多關鍵字文件概念　143
10.6.2　倒排文件　144
10.6.3　多重表文件　144
習題　146

第11章　數據結構綜合應用　147
11.1　綜合應用一：新生報到信息注冊系統(tǒng)設計　147
11.1.1　案例需求分析　147
11.1.2　案例知識目標　148
11.1.3　案例核心算法及實現　148
11.1.4　其他參考代碼　151
11.2　綜合應用二：萬達停車場管理系統(tǒng)設計　152
11.2.1　案例需求分析　152
11.2.2　案例知識目標　154
11.2.3　案例核心算法及實現　154
11.2.4　其他參考代碼　158
11.3　綜合應用三：最短時間旅游路線查詢系統(tǒng)設計　158
11.3.1　案例需求分析　158
11.3.2　案例知識目標　159
11.3.3　案例核心算法及實現　160
11.3.4　其他參考代碼　162