數(shù)據(jù)結(jié)構(gòu)實(shí)例教程（C語(yǔ)言版）

目　錄

第1章　緒論及C語(yǔ)言介紹　1
1.1　基本概念與術(shù)語(yǔ)　1
1.2　學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義　3
1.3　算法的描述和分析　5
1.4　C語(yǔ)言相關(guān)知識(shí)介紹　6
知識(shí)實(shí)踐一　學(xué)生管理系統(tǒng)登錄模塊設(shè)計(jì)　9
習(xí)題　10

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

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

第4章　字符串的結(jié)構(gòu)分析與應(yīng)用　46
4.1　串的定義及其運(yùn)算　46
4.1.1　串的基本概念　46
4.1.2　串的基本運(yùn)算　47
4.2　串的存儲(chǔ)結(jié)構(gòu)　47
4.2.1　串的順序存儲(chǔ)結(jié)構(gòu)　47
4.2.2　串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)　48
4.2.3　子串的定位運(yùn)算　48
知識(shí)實(shí)踐七　學(xué)生管理系統(tǒng)家庭情況模塊設(shè)計(jì)　49
習(xí)題　50

第5章　二維數(shù)組及廣義表的結(jié)構(gòu)分析　51
5.1　二維數(shù)組的存儲(chǔ)結(jié)構(gòu)及求址方法　51
5.2　矩陣的壓縮存儲(chǔ)　52
5.2.1　特殊矩陣　52
5.2.2　稀疏矩陣　53
5.3　廣義表的概念　54
知識(shí)實(shí)踐八　求二維數(shù)組元素在內(nèi)存中的存儲(chǔ)位置　55
習(xí)題　56

第6章　樹(shù)和二叉樹(shù)的結(jié)構(gòu)分析與應(yīng)用　57
6.1　樹(shù)的概念　57
6.2　二叉樹(shù)　59
6.2.1　二叉樹(shù)的定義　59
6.2.2　二叉樹(shù)的性質(zhì)　60
6.2.3　二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)　60
6.3　 二叉樹(shù)的遍歷　64
6.4　線索二叉樹(shù)　66
6.5　樹(shù)和森林　67
6.5.1　樹(shù)、森林與二叉樹(shù)的相互轉(zhuǎn)換　67
6.5.2　樹(shù)的存儲(chǔ)結(jié)構(gòu)　69
6.5.3　樹(shù)和森林的遍歷　71
6.6　哈夫曼樹(shù)及其應(yīng)用　72
6.6.1　哈夫曼樹(shù)的定義　72
6.6.2　哈夫曼樹(shù)的構(gòu)造　73
6.6.3　哈夫曼樹(shù)編碼　74
知識(shí)實(shí)踐九　利用二叉樹(shù)遍歷實(shí)現(xiàn)學(xué)生成績(jī)排序模塊設(shè)計(jì)　74
習(xí)題　76

第7章　圖的結(jié)構(gòu)分析與應(yīng)用　80
7.1　圖的概念及相關(guān)術(shù)語(yǔ)　80
7.1.1　圖的概念　80
7.1.2 圖的相關(guān)術(shù)語(yǔ)　81
7.2　圖的存儲(chǔ)結(jié)構(gòu)　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　最小生成樹(shù)　90
7.4.1　普里姆算法　91
7.4.2　克魯斯卡爾算法　91
7.5　最短路徑　92
7.5.1　單源最短路徑　92
7.5.2　每一對(duì)頂點(diǎn)之間的最短路徑　93
知識(shí)實(shí)踐十　江蘇省地級(jí)市組成的地圖遍歷　96
習(xí)題　98

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

第9章　排序的分析與應(yīng)用　114
9.1　排序的基本概念　114
9.1.1　排序的定義　114
9.1.2　相關(guān)概念　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　各種內(nèi)部排序算法的比較　133
知識(shí)實(shí)踐十二　學(xué)生總成績(jī)排序模塊設(shè)計(jì)　134
習(xí)題　136

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

第11章　數(shù)據(jù)結(jié)構(gòu)綜合應(yīng)用　147
11.1　綜合應(yīng)用一：新生報(bào)到信息注冊(cè)系統(tǒng)設(shè)計(jì)　147
11.1.1　案例需求分析　147
11.1.2　案例知識(shí)目標(biāo)　148
11.1.3　案例核心算法及實(shí)現(xiàn)　148
11.1.4　其他參考代碼　151
11.2　綜合應(yīng)用二：萬(wàn)達(dá)停車場(chǎng)管理系統(tǒng)設(shè)計(jì)　152
11.2.1　案例需求分析　152
11.2.2　案例知識(shí)目標(biāo)　154
11.2.3　案例核心算法及實(shí)現(xiàn)　154
11.2.4　其他參考代碼　158
11.3　綜合應(yīng)用三：最短時(shí)間旅游路線查詢系統(tǒng)設(shè)計(jì)　158
11.3.1　案例需求分析　158
11.3.2　案例知識(shí)目標(biāo)　159
11.3.3　案例核心算法及實(shí)現(xiàn)　160
11.3.4　其他參考代碼　162