目　錄 第　一部分 數(shù)據(jù)結(jié)構(gòu) 第0章　基礎(chǔ)知識(shí)　2 0.1　基本概念和術(shù)語　2 0.2　數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)　3 0.2.1　邏輯結(jié)構(gòu)　3 0.2.2　存儲(chǔ)結(jié)構(gòu)　4 0.3　抽象數(shù)據(jù)類型及其描述　5 0.3.1　什么是抽象數(shù)據(jù)類型　5 0.3.2　抽象數(shù)據(jù)類型的描述　5 0.4　算法　5 0.4.1　數(shù)據(jù)結(jié)構(gòu)與算法的關(guān)系　6 0.4.2　什么是算法　6 0.4.3　算法的五大特性　6 0.4.4　算法的描述　6 0.5　算法分析　7 0.5.1　算法設(shè)計(jì)的4個(gè)目標(biāo)　7 0.5.2　算法的時(shí)間復(fù)雜度　7 0.5.3　算法的空間復(fù)雜度　9 第　1章 線性表　10 1.1　順序表及其應(yīng)用　10 1.1.1　將兩個(gè)有序的線性表合并 為一個(gè)有序的線性表　13 1.1.2　將兩個(gè)無序的線性表合并 為一個(gè)線性表　16 1.1.3　求兩個(gè)線性表的差集　18 1.1.4　分解順序表，使左邊的 元素小于或等于0，右邊的 大于0　19 1.1.5　求兩個(gè)任意長度的整數(shù) 之和　21 1.1.6　求兩個(gè)元素序列的 中位數(shù)　23 1.2　單鏈表及其應(yīng)用　25 1.2.1　逆置單鏈表　30 1.2.2　求兩個(gè)單鏈表的差集　34 1.2.3　合并兩個(gè)單鏈表　37 1.2.4　找出單鏈表表示的兩個(gè)單詞 共同后綴起始地址　40 1.2.5　找出單鏈表中倒數(shù)第k個(gè) 位置上的節(jié)點(diǎn)　42 1.3　循環(huán)單鏈表及其應(yīng)用　44 1.3.1　分解一個(gè)循環(huán)單鏈表為 兩個(gè)循環(huán)單鏈表　44 1.3.2　構(gòu)造3個(gè)循環(huán)單鏈表　47 1.3.3　約瑟夫問題　50 1.4　雙向鏈表及其應(yīng)用　53 1.4.1　雙向鏈表的創(chuàng)建與插入 操作　55 1.4.2　約瑟夫問題（雙向鏈表）　58 1.5　線性表的典型應(yīng)用　60 1.5.1　將兩個(gè)一元多項(xiàng)式相加　60 1.5.2　將兩個(gè)一元多項(xiàng)式相乘　65 第　2章 �！�71 2.1　順序棧及其應(yīng)用　71 2.1.1　將元素分別入棧和出棧　73 2.1.2　共享?xiàng)５娜霔：统鰲２僮鳌?5 2.1.3　求C (n,m)的值　78 2.1.4　求Ackermann(m,n)的值　80 2.2　鏈棧及其應(yīng)用　83 2.2.1　將十進(jìn)制數(shù)轉(zhuǎn)換為 八進(jìn)制數(shù)　86 2.2.2　檢查表達(dá)式中的括號(hào) 是否匹配　88 2.2.3　求算術(shù)表達(dá)式的值　90 2.2.4　判斷字符串是否中心 對稱　96 第3章　隊(duì)列　98 3.1　順序隊(duì)列及其應(yīng)用　98 3.1.1　將順序循環(huán)隊(duì)列中的元素 分別入隊(duì)和出隊(duì)　101 3.1.2　舞伴配對　104 3.1.3　模擬輪渡管理　106 3.2　鏈?zhǔn)疥?duì)列及其應(yīng)用　108 3.2.1　隊(duì)列在楊輝三角中的 應(yīng)用　111 3.2.2　判斷字符串是否為回文　114 3.3　棧和隊(duì)列的綜合應(yīng)用──停車場 管理　116 第4章　串　126 4.1　順序串及其應(yīng)用　126 4.1.1　利用串的基本運(yùn)算進(jìn)行 賦值、插入和刪除等操作　130 4.1.2　將浮點(diǎn)數(shù)轉(zhuǎn)換為對應(yīng)的串　134 4.1.3　求最長公共子串　135 4.1.4　求等值子串　137 4.1.5　將長度為5的單詞轉(zhuǎn)換為 大寫形式　138 4.1.6　將小寫字母a左、右兩邊的 串互換　140 4.2　串的模式匹配　142 第5章　數(shù)組　149 5.1　一維數(shù)組及其應(yīng)用　149 5.1.1　查找第k小元素　150 5.1.2　將奇數(shù)移動(dòng)到偶數(shù)的 左邊　151 5.2　二維數(shù)組（矩陣）及其應(yīng)用　153 5.2.1　輸出魔方陣　153 5.2.2　輸出內(nèi)螺旋矩陣　155 5.2.3　輸出逆螺旋矩陣　156 5.2.4　輸出外螺旋矩陣　158 5.2.5　輸出蛇形方陣　159 5.2.6　輸出折疊方陣　161 5.3　特殊矩陣的壓縮存儲(chǔ)及其應(yīng)用　162 5.4　稀疏矩陣的壓縮存儲(chǔ)及其應(yīng)用　166 第6章　廣義表　172 6.1　頭尾鏈表表示的廣義表及其 應(yīng)用　172 6.2　擴(kuò)展線性鏈表表示的廣義表 及其應(yīng)用　178 6.3　廣義表的綜合應(yīng)用——導(dǎo)師-學(xué)生 制管理　181 第7章　樹　187 7.1　樹的表示及創(chuàng)建二叉樹　187 7.1.1　采用廣義表創(chuàng)建二叉樹　194 7.1.2　創(chuàng)建二叉樹　196 7.2　二叉樹的遍歷　199 7.2.1　非遞歸先序遍歷二叉樹　205 7.2.2　按層次遍歷二叉樹　207 7.2.3　由中序和后序序列構(gòu)造 二叉樹　209 7.2.4　輸出樹的各條邊　212 7.3　二叉樹的應(yīng)用　214 7.3.1　求樹中節(jié)點(diǎn)的個(gè)數(shù)　214 7.3.2　交換二叉樹的左右子樹　216 7.3.3　判斷二叉樹是否為完全 二叉樹　219 7.3.4　計(jì)算二叉樹的高度和最大 寬度　223 7.3.5　求樹中根節(jié)點(diǎn)到任意節(jié)點(diǎn) 之間的路徑　226 7.4　哈夫曼樹　230 第8章　圖　235 8.1　圖的表示及應(yīng)用　235 8.1.1　利用鄰接矩陣創(chuàng)建 有向網(wǎng)　238 8.1.2　利用鄰接表創(chuàng)建有向圖　241 8.1.3　把圖的鄰接矩陣表示 轉(zhuǎn)換為鄰接表表示　244 8.2　圖的遍歷　248 8.2.1　判斷有向圖中是否存在 回路　249 8.2.2　深度優(yōu)先搜索遍歷 無向圖　251 8.2.3　圖的廣度優(yōu)先搜索遍歷　254 8.2.4　判斷有向圖中是否有根 頂點(diǎn)　258 8.2.5　求距離頂點(diǎn)v0的最短路徑 長度為k的所有頂點(diǎn)　261 8.2.6　判斷頂點(diǎn)u和頂點(diǎn)v之間 是否存在簡單路徑　265 8.2.7　判斷無向圖是否為一棵樹　269 第二部分　算 法 第9章　查找算法　274 9.1　與查找算法相關(guān)的概念　274 9.2　基于線性表的查找　275 9.2.1　順序查找　275 9.2.2　折半查找　276 9.2.3　分塊查找　279 9.3　基于樹的查找　281 9.4　哈希表的查找　285 第　10章 排序算法　290 10.1　排序的基本概念　290 10.2　插入排序　291 10.2.1　直接插入排序　291 10.2.2　折半插入排序　293 10.2.3　希爾排序　296 10.3　交換排序　298 10.3.1　冒泡排序　298 10.3.2　快速排序　302 10.4　選擇排序　305 10.4.1　簡單選擇排序　305 10.4.2　堆排序　308 10.5　歸并排序　313 10.6　基數(shù)排序　316 第　11章 遞推算法　324 11.1　順推法　324 11.1.1　斐波那契數(shù)列　324 11.1.2　角谷猜想　327 11.1.3　將十進(jìn)制整數(shù)轉(zhuǎn)換為 二進(jìn)制整數(shù)　328 11.1.4　將十進(jìn)制浮點(diǎn)數(shù)轉(zhuǎn)換為 二進(jìn)制數(shù)　329 11.1.5　母牛生小牛問題　330 11.1.6　輸出楊輝三角　332 11.1.7　質(zhì)因數(shù)分解　333 11.1.8　求最大公約數(shù)和最小公 倍數(shù)　333 11.2　逆推法　334 11.2.1　猴子摘桃　334 11.2.2　存錢問題　335 第　12章 遞歸算法　337 12.1　簡單遞歸　337 12.1.1　求n的階乘　337 12.1.2　斐波那契數(shù)列　340 12.1.3　求n個(gè)元素中的最大者　341 12.1.4　求n個(gè)數(shù)的和　342 12.1.5　將十進(jìn)制整數(shù)轉(zhuǎn)換為 二進(jìn)制整數(shù)　343 12.1.6　求整數(shù)的逆序數(shù)　344 12.1.7　求最大公約數(shù)　345 12.1.8　求Ackermann函數(shù)的值　346 12.1.9　求C (n,m)的值　347 12.2　復(fù)雜遞歸　348 12.2.1　逆置字符串　348 12.2.2　求最大和次大元素　349 12.2.3　求無序序列中第k大的 元素　351 12.2.4　和式分解　352 12.2.5　臺(tái)階問題　354 12.2.6　漢諾塔問題　356 12.2.7　大牛生小牛問題　358 12.2.8　從自然數(shù)1～n中任選r 個(gè)數(shù)的所有組合數(shù)　359 第　13章 枚舉算法　361 13.1　判斷n是否能被3、5、7整除　361 13.2　百錢買百雞　363 13.3　五猴分桃　364 13.4　輸出“水仙花數(shù)”　366 13.5　Mary的借書方案　367 13.6　整幣換零　368 13.7　填數(shù)游戲　369 13.8　誰在說謊　371 13.9　求最大連續(xù)子序列和　372 13.10　0/1背包問題　373 第　14章 貪心算法　376 14.1　貪心算法的基礎(chǔ)　376 14.1.1　貪心算法的基本思想　376 14.1.2　貪心選擇性質(zhì)　376 14.1.3　貪心算法的求解步驟　376 14.2　找零錢問題　377 14.3　會(huì)議安排問題　378 14.4　最優(yōu)裝載問題　381 14.5　哈夫曼編碼　383 14.6　加油點(diǎn)問題　387 14.7　背包問題　389 第　15章 回溯算法　392 15.1　回溯算法的基礎(chǔ)　392 15.1.1　回溯算法的解空間　392 15.1.2　回溯算法的搜索　393 15.2　求自然數(shù)1～n中r個(gè)數(shù)的所有 組合　394 15.3　填字游戲　395 15.4　和式分解（非遞歸實(shí)現(xiàn)）　399 15.5　裝箱問題　401 15.6　0/1背包問題　404 第　16章 數(shù)值算法　408 16.1　求實(shí)數(shù)的平方根　408 16.2　利用二分法求方程的根　409 16.3　利用牛頓迭代法求方程的根　411 16.4　利用高斯消元法求解線性方程組　413 16.5　利用梯形法求定積分　416 16.6　計(jì)算π的近似值　418 第　17章 實(shí)用算法　421 17.1　阿拉伯?dāng)?shù)字/中文大寫金額的 轉(zhuǎn)換　421 17.2　將15位身份證號(hào)轉(zhuǎn)換為18位　424 17.3　計(jì)算7的34次方　426 17.4　計(jì)算某年某月某日是一年中的 第幾天　427 17.5　大整數(shù)相乘　428 17.6　輸出萬年歷　430 17.7　求兩個(gè)正整數(shù)的差　434 17.8　利用二叉樹結(jié)構(gòu)計(jì)算算術(shù) 表達(dá)式的值　436 第　18章 常見錯(cuò)誤與程序調(diào)試技術(shù)　439 18.1　常見錯(cuò)誤　439 18.1.1　錯(cuò)誤分類　439 18.1.2　常見錯(cuò)誤舉例　440 18.2　程序調(diào)試　444 18.2.1　Visual C++ 6.0開發(fā) 環(huán)境中程序的調(diào)試　444 18.2.2　程序調(diào)試應(yīng)用舉例　451 18.3　小結(jié)　462