【章名目錄】 第 1章　緒論 第 2章　線(xiàn)性結(jié)構(gòu) 第3章　樹(shù)與二叉樹(shù) 第4章　圖 第5章　查找 第6章　排序 【詳細(xì)目錄】 第 1章　緒論 1.1　數(shù)據(jù)結(jié)構(gòu)概述　1 1.1.1　數(shù)據(jù)結(jié)構(gòu)的基本概念與術(shù)語(yǔ)　1 1.1.2　數(shù)據(jù)的邏輯結(jié)構(gòu)　2 1.1.3　數(shù)據(jù)的物理結(jié)構(gòu)　4 1.2　算法與性能分析　5 1.2.1　算法的基本概念　5 1.2.2　描述算法的方法　6 1.2.3　算法設(shè)計(jì)的要求　7 1.2.4　算法效率分析　8 1.3　數(shù)據(jù)結(jié)構(gòu)、算法及程序的關(guān)系　12 1.3.1　數(shù)據(jù)結(jié)構(gòu)的作用　13 1.3.2　算法的作用　13 1.3.3　程序的作用　13 1.3.4　三者之間的關(guān)系　13 1.4　本章小結(jié)　14 練習(xí)題　14 第 2章　線(xiàn)性結(jié)構(gòu) 2.1　問(wèn)題導(dǎo)入：數(shù)組的局限性　16 2.2　順序表　17 2.2.1　非封裝的順序表　17 2.2.2　順序表類(lèi)　23 2.2.3　順序表類(lèi)模板　29 2.2.4　模仿的向量（vector）類(lèi)模板　30 2.2.5　順序表的應(yīng)用：Todo計(jì)劃表　36 2.3　鏈表　37 2.3.1　鏈表的基本概念　37 2.3.2　單鏈表　37 2.3.3　雙向鏈表　43 2.3.4　循環(huán)鏈表　44 2.3.5　模仿的鏈表類(lèi)模板list　45 2.3.6　鏈表的應(yīng)用：一元多項(xiàng)式相加　51 2.4　�！�52 2.4.1　棧的基本概念　52 2.4.2　順序棧　53 2.4.3　以標(biāo)準(zhǔn)模板庫(kù)的vector類(lèi)為底層結(jié)構(gòu)的順序�！�54 2.4.4　鏈�！�56 2.4.5　以標(biāo)準(zhǔn)模板庫(kù)的list類(lèi)為底層結(jié)構(gòu)的鏈�！�57 2.4.6　棧的應(yīng)用：括號(hào)匹配　59 2.5　隊(duì)列　60 2.5.1　隊(duì)列的基本概念　60 2.5.2　順序隊(duì)列　60 2.5.3　以標(biāo)準(zhǔn)模板庫(kù)的vector類(lèi)為底層結(jié)構(gòu)的順序隊(duì)列　61 2.5.4　鏈隊(duì)列　63 2.5.5　以標(biāo)準(zhǔn)模板庫(kù)的list類(lèi)為底層結(jié)構(gòu)的鏈隊(duì)列　65 2.5.6　優(yōu)先級(jí)隊(duì)列　65 2.5.7　隊(duì)列的應(yīng)用：打印機(jī)模擬　65 2.6　串　66 2.6.1　串的基本概念　66 2.6.2　模仿的String類(lèi)及其實(shí)現(xiàn)　66 2.6.3　模式匹配　70 2.6.4　串的應(yīng)用：文本檢索　76 2.7　多維數(shù)組與特殊矩陣　77 2.7.1　多維數(shù)組的定義　77 2.7.2　多維數(shù)組的存儲(chǔ)方式　78 2.7.3　特殊矩陣　79 2.7.4　稀疏矩陣　81 2.8　本章小結(jié)　82 練習(xí)題　83 第3章　樹(shù)與二叉樹(shù) 3.1　樹(shù)的基本概念　85 3.1.1　樹(shù)的定義　85 3.1.2　樹(shù)的基本術(shù)語(yǔ)　86 3.2　二叉樹(shù)的基本概念　87 3.2.1　二叉樹(shù)的定義　87 3.2.2　二叉樹(shù)的性質(zhì)　88 3.3　二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)　89 3.3.1　二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)　89 3.3.2　二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)　89 3.4　二叉樹(shù)遍歷　92 3.4.1　二叉樹(shù)遍歷概述　92 3.4.2　二叉樹(shù)的層次遍歷　92 3.4.3　二叉樹(shù)的先序、中序、后序遍歷遞歸算法　93 3.4.4　二叉樹(shù)的先序、中序、后序遍歷非遞歸算法　94 3.4.5　二叉樹(shù)遍歷遞歸程序轉(zhuǎn)換為非遞歸程序的一般方法　95 3.4.6　二叉樹(shù)遍歷的應(yīng)用　97 3.5　堆　109 3.5.1　堆的基本概念　109 3.5.2　建堆　109 3.5.3　堆排序　111 3.5.4　小根堆Heap類(lèi)　111 3.6　哈夫曼樹(shù)與哈夫曼編碼　112 3.6.1　哈夫曼樹(shù)的基本概念　112 3.6.2　哈夫曼樹(shù)構(gòu)建　113 3.6.3　哈夫曼編碼與解碼　115 3.7　樹(shù)與森林　117 3.7.1　樹(shù)的存儲(chǔ)與Tree類(lèi)　117 3.7.2　樹(shù)的遍歷　121 3.7.3　樹(shù)與二叉樹(shù)的轉(zhuǎn)換　123 3.7.4　樹(shù)的應(yīng)用：八數(shù)碼問(wèn)題　125 3.8　本章小結(jié)　127 練習(xí)題　128 第4章　圖 4.1　圖的基本概念　130 4.2　圖的存儲(chǔ)結(jié)構(gòu)　132 4.2.1　鄰接矩陣　132 4.2.2　鄰接表　132 4.3　Graph類(lèi)　133 4.4　圖的遍歷　138 4.4.1　廣度優(yōu)先搜索算法　138 4.4.2　深度優(yōu)先搜索算法　139 4.5　最小生成樹(shù)　141 4.5.1　圖的生成樹(shù)的基本概念　141 4.5.2　克魯斯卡爾算法　142 4.5.3　普里姆算法　146 4.6　最短路徑　148 4.6.1　單源最短路徑　148 4.6.2　迪杰斯特拉算法　149 4.6.3　所有頂點(diǎn)之間的最短路徑　152 4.7　拓?fù)渑判蚺c關(guān)鍵路徑　156 4.7.1　有向無(wú)環(huán)圖　156 4.7.2　拓?fù)渑判颉?57 4.7.3　關(guān)鍵路徑　158 4.8　圖的應(yīng)用：迷宮求解　160 4.9　本章小結(jié)　162 練習(xí)題　162 第5章　查找 5.1　查找的基本概念　166 5.2　靜態(tài)查找　168 5.2.1　順序查找　168 5.2.2　折半查找　169 5.2.3　分塊查找　170 5.3　二叉搜索樹(shù)　170 5.3.1　二叉搜索樹(shù)的基本概念　170 5.3.2　二叉搜索樹(shù)的操作　171 5.3.3　二叉樹(shù)的遍歷迭代器　177 5.3.4　線(xiàn)索二叉樹(shù)　182 5.3.5　增加線(xiàn)索的遍歷迭代器　188 5.4　平衡二叉搜索樹(shù)　191 5.4.1　平衡二叉搜索樹(shù)的基本概念　191 5.4.2　動(dòng)態(tài)平衡調(diào)整法　192 5.4.3　平衡二叉搜索樹(shù)插入節(jié)點(diǎn)　198 5.4.4　平衡二叉搜索樹(shù)刪除節(jié)點(diǎn)　199 5.4.5　平衡二叉搜索樹(shù)的應(yīng)用：詞頻統(tǒng)計(jì)　201 5.5　B-樹(shù)　202 5.5.1　B-樹(shù)的基本概念　202 5.5.2　B-樹(shù)的查找　202 5.5.3　B-樹(shù)的插入　203 5.5.4　B-樹(shù)的刪除　205 5.5.5　B+樹(shù)　211 5.6　散列　217 5.6.1　散列的基本概念　217 5.6.2　散列函數(shù)的構(gòu)造方法　218 5.6.3　處理散列沖突的方法　219 5.6.4　散列查找　223 5.7　本章小結(jié)　224 練習(xí)題　225 第6章　排序 6.1　排序的基本概念　227 6.2　插入排序　228 6.2.1　直接插入排序　228 6.2.2　折半插入排序　230 6.2.3　希爾排序　231 6.3　交換排序　233 6.3.1　冒泡排序　233 6.3.2　快速排序　235 6.4　選擇排序　236 6.4.1　直接選擇排序　236 6.4.2　堆排序　237 6.4.3　錦標(biāo)賽排序　238 6.5　歸并排序　242 6.5.1　二路歸并　242 6.5.2　迭代歸并排序　243 6.5.3　遞歸歸并排序　243 6.6　基數(shù)排序　244 6.7　外排序　246 6.7.1　內(nèi)排序與外排序　246 6.7.2　多路歸并排序　246 6.8　排序的應(yīng)用：國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽成績(jī)排序　248 6.9　本章小結(jié)　249 練習(xí)題　250 參考文獻(xiàn)