數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)：C語(yǔ)言

目    錄第1章  編程原則 11.1  引言 11.2  Life游戲 31.2.1  Life游戲規(guī)則 31.2.2  示例 31.2.3  解決方案 51.2.4  Life游戲主程序 51.3  編程風(fēng)格 91.3.1  命名 91.3.2  文檔及其格式 101.3.3  程序的細(xì)化和模塊化 111.3.4  小節(jié)練習(xí) 131.4  編碼、測(cè)試及進(jìn)一步細(xì)化 151.4.1  占位程序 151.4.2  計(jì)算相鄰元胞的數(shù)目 161.4.3  輸入和輸出 171.4.4  驅(qū)動(dòng)程序 201.4.5  程序的跟蹤 211.4.6  測(cè)試程序的原則 221.4.7  小節(jié)練習(xí) 241.4.8  編程項(xiàng)目 241.5  注意事項(xiàng) 251.6  復(fù)習(xí)題 261.7  參考文獻(xiàn) 261.7.1  C語(yǔ)言 261.7.2  編程原則 271.7.3  Life游戲 27第2章  軟件工程介紹 282.1  程序維護(hù) 282.1.1  Life程序回顧 282.1.2  關(guān)于Life程序的新起點(diǎn)和新方法 302.1.3  小節(jié)練習(xí) 312.1.4  編程項(xiàng)目 322.2  算法研究：Life程序的第二個(gè)版本 322.2.1  列表：數(shù)據(jù)結(jié)構(gòu)的說(shuō)明 322.2.2  主程序 352.2.3  信息隱藏 382.2.4  細(xì)化：子程序的開(kāi)發(fā) 382.2.5  算法的驗(yàn)證 412.2.6  小節(jié)練習(xí) 432.3  編碼 432.3.1  列表函數(shù) 442.3.2  錯(cuò)誤處理 452.3.3  演示和測(cè)試 462.3.4  小節(jié)練習(xí) 492.3.5  編程項(xiàng)目 502.4  Life函數(shù)的編碼 502.4.1  Vivify函數(shù) 502.4.2  AddNeighbors函數(shù) 512.4.3  混合函數(shù) 522.4.4  初始化 522.4.5  編程項(xiàng)目 532.5  程序分析與比較 532.5.1  語(yǔ)句數(shù) 532.5.2  比較 542.5.3  時(shí)間和空間的平衡 552.5.4  小節(jié)練習(xí) 552.5.5  編程項(xiàng)目 552.6  總結(jié)和展望 552.6.1  Life 游戲 562.6.2  程序設(shè)計(jì) 572.6.3  C語(yǔ)言 582.6.4  編程項(xiàng)目 592.7  注意事項(xiàng) 602.8  復(fù)習(xí)題 612.9  參考文獻(xiàn) 612.9.1  軟件工程 612.9.2  算法驗(yàn)證 622.9.3  問(wèn)題解決 62第3章  堆棧和遞歸 633.1  堆棧 633.1.1  引言 633.1.2  第一個(gè)示例：線性顛倒 643.1.3  信息隱藏 653.1.4  堆棧的說(shuō)明 653.1.5  堆棧的實(shí)現(xiàn) 673.1.6  鏈接堆棧 693.1.7  小節(jié)練習(xí) 723.1.8  編程項(xiàng)目 733.2  遞歸 743.2.1  子程序的堆棧圖解 743.2.2  子程序調(diào)用樹(shù) 743.2.3  階乘：一個(gè)遞歸定義 763.2.4  分而治之：漢諾(HANOI)塔 773.2.5  小節(jié)練習(xí) 823.2.6  編程項(xiàng)目 823.3  回溯：推遲工作 833.3.1  解決8王后難題 833.3.2  示例：4王后 843.3.3  回溯 853.3.4  細(xì)化：選擇數(shù)據(jù)結(jié)構(gòu) 863.3.5  回溯分析 883.3.6  小節(jié)練習(xí) 893.3.7  編程項(xiàng)目 903.4  遞歸法則 903.4.1  設(shè)計(jì)遞歸算法 903.4.2  遞歸如何工作 913.4.3  尾部遞歸 943.4.4  何時(shí)不使用遞歸 963.4.5  指南和總結(jié) 1003.4.6  小節(jié)練習(xí) 1003.5  注意事項(xiàng) 1013.6  復(fù)習(xí)題 1023.7  參考文獻(xiàn) 103第4章  隊(duì)列和鏈表 1044.1  定義 1044.2  隊(duì)列的實(shí)現(xiàn) 1074.3  C語(yǔ)言中的環(huán)形隊(duì)列 1104.3.1  小節(jié)練習(xí) 1124.3.2  編程項(xiàng)目 1134.4  隊(duì)列的應(yīng)用：模擬 1144.4.1  引言 1144.4.2  機(jī)場(chǎng)的模擬 1144.4.3  主程序 1164.4.4  模擬的步驟 1184.4.5  偽隨機(jī)數(shù) 1214.4.6  示例結(jié)果 1234.4.7  編程項(xiàng)目 1254.5  指針和鏈表 1264.5.1  引言和綜述 1264.5.2  指針和C語(yǔ)言中的動(dòng)態(tài)內(nèi)存 1284.5.3  鏈表基礎(chǔ) 1324.5.4  小節(jié)練習(xí) 1334.6  鏈接隊(duì)列 1344.6.1  小節(jié)練習(xí) 1364.6.2  編程項(xiàng)目 1374.7  應(yīng)用：多項(xiàng)式算術(shù) 1374.7.1  項(xiàng)目的目的 1374.7.2  主程序 1384.7.3  數(shù)據(jù)結(jié)構(gòu)及其實(shí)現(xiàn) 1424.7.4  讀取和寫出多項(xiàng)式 1434.7.5  多項(xiàng)式加法 1454.7.6  完成項(xiàng)目 1474.7.7  小節(jié)練習(xí) 1474.7.8  編程項(xiàng)目 1484.8  抽象數(shù)據(jù)類型及其實(shí)現(xiàn) 1494.8.1  引言 1494.8.2  通用定義 1504.8.3  數(shù)據(jù)說(shuō)明的細(xì)化 1524.8.4  小節(jié)練習(xí) 1534.9  注意事項(xiàng) 1534.10  復(fù)習(xí)題 1544.11  參考文獻(xiàn) 154
第5章  通用列表 1565.1  列表說(shuō)明 1565.2  列表的實(shí)現(xiàn) 1585.2.1  連續(xù)實(shí)現(xiàn) 1585.2.2  簡(jiǎn)單的鏈接實(shí)現(xiàn) 1595.2.3  變更：保持當(dāng)前位置 1635.2.4  雙向鏈表 1645.2.5  實(shí)現(xiàn)的比較 1665.2.6  小節(jié)練習(xí) 1675.2.7  編程項(xiàng)目 1685.3  字符串 1685.4  應(yīng)用：文本編輯器 1705.4.1  說(shuō)明 1715.4.2  實(shí)現(xiàn) 1715.4.3　編程項(xiàng)目 1785.5  數(shù)組中的鏈表 1785.5.1  方法 1795.5.2  操作：空間管理 1805.5.3  其他操作 1835.5.4  鏈表的變化 1845.5.5  小節(jié)練習(xí) 1845.6  排列 1865.6.1  思想 1875.6.2  細(xì)化 1875.6.3  通用函數(shù) 1885.6.4  數(shù)據(jù)結(jié)構(gòu)：優(yōu)化 1885.6.5  最終的程序 1895.6.6  編程項(xiàng)目 1915.7  注意事項(xiàng) 1915.8  復(fù)習(xí)題 1925.9  參考文獻(xiàn) 192第6章  搜索 1936.1  搜索：介紹及其表示 1936.1.1  鍵 1936.1.2  分析 1936.1.3  外部搜索和內(nèi)部搜索 1946.1.4  C語(yǔ)言實(shí)現(xiàn) 1946.1.5  參數(shù) 1946.2  順序搜索 1956.2.1  算法及函數(shù) 1956.2.2  算法分析 1966.2.3  測(cè)試 1976.2.4  小節(jié)練習(xí) 1996.2.5  編程項(xiàng)目 2006.3  寄物處：項(xiàng)目 2016.3.1  介紹和說(shuō)明 2016.3.2  演示及測(cè)試程序 2036.3.3  編程項(xiàng)目 2056.4  二叉搜索 2066.4.1  算法研究 2076.4.2  忽略版本 2086.4.3  識(shí)別等式 2106.4.4  小節(jié)練習(xí) 2116.4.5  編程項(xiàng)目 2126.5  比較樹(shù) 2126.5.1  分析n=10的情況 2136.5.2  算法推廣 2156.5.3  方法的比較 2186.5.4  普遍關(guān)系 2196.5.5  小節(jié)練習(xí) 2206.5.6  編程項(xiàng)目 2206.6  下限 2206.6.1  優(yōu)化程序 2206.6.2  任意搜索算法 2216.6.3  觀察2-樹(shù) 2216.6.4  搜索下限 2236.6.5  其他的搜索算法 2236.6.6  小節(jié)練習(xí) 2246.6.7  編程項(xiàng)目 2246.7  漸近線 2246.7.1  介紹 2246.7.2  Big-O表示法 2256.7.3  Big-O表示法的不精確性 2276.7.4  通用函數(shù)的排序 2286.7.5  小節(jié)練習(xí) 2296.7.6  編程項(xiàng)目 2296.8  注意事項(xiàng) 2296.9  復(fù)習(xí)題 2306.10  參考文獻(xiàn) 230第7章  排序 2327.1  介紹和符號(hào) 2327.2  插入排序 2337.2.1  順序列表 2337.2.2  通常的插入排序 2347.2.3  鏈接版本 2367.2.4  分析 2377.2.5  小節(jié)練習(xí) 2387.2.6  編程項(xiàng)目 2397.3  選擇排序 2407.3.1  算法 2407.3.2  連續(xù)實(shí)現(xiàn) 2417.3.3  分析 2427.3.4  比較 2437.3.5  小節(jié)練習(xí) 2437.3.6  編程項(xiàng)目 2447.4  希爾排序 2447.4.1  小節(jié)練習(xí) 2467.4.2  編程項(xiàng)目 2467.5  下限 2467.5.1  小節(jié)練習(xí) 2487.5.2  編程項(xiàng)目 2487.6  “分而治之”排序 2497.6.1  主要思想 2497.6.2  示例 2507.6.3  小節(jié)練習(xí) 2537.7  鏈表的歸并排序 2547.7.1  函數(shù) 2547.7.2  合并分析 2567.7.3  小節(jié)練習(xí) 2587.7.4  編程項(xiàng)目 2597.8  連續(xù)列表的快速排序 2607.8.1  主函數(shù) 2607.8.2  列表的劃分 2617.8.3  快速排序分析 2637.8.4  快速排序的平均情形分析 2657.8.5  與歸并排序的比較 2667.8.6  小節(jié)練習(xí) 2677.8.7  編程項(xiàng)目 2697.9  堆和堆排序 2697.9.1  2-樹(shù)的列表 2697.9.2  堆排序 2717.9.3  堆排序分析 2737.9.4  優(yōu)先級(jí)隊(duì)列 2747.9.5  小節(jié)練習(xí) 2757.9.6  編程項(xiàng)目 2767.10  回顧：方法的比較 2767.10.1  使用的存儲(chǔ)空間 2767.10.2  計(jì)算機(jī)時(shí)間 2767.10.3  編程量 2767.10.4  統(tǒng)計(jì)分析 2777.10.5  實(shí)驗(yàn)測(cè)試 2777.10.6  小節(jié)練習(xí) 2777.11  注意事項(xiàng) 2797.12  復(fù)習(xí)題 2797.13  參考文獻(xiàn) 280第8章  表和信息檢索 2828.1  引言：突破lg n障礙 2828.2  矩形數(shù)組 2838.2.1  行優(yōu)先和列優(yōu)先順序 2838.2.2  下標(biāo)矩形數(shù)組 2838.2.3  訪問(wèn)表 2848.2.4  小節(jié)練習(xí) 2848.3  各種形狀的表 2858.3.1  三角表 2858.3.2  不規(guī)則表 2868.3.3  反向表 2878.3.4  小節(jié)練習(xí) 2888.3.5  編程項(xiàng)目 2898.4  表：一種新的抽象數(shù)據(jù)類型 2898.4.1  函數(shù) 2898.4.2  抽象數(shù)據(jù)類型 2908.4.3  實(shí)現(xiàn) 2908.4.4  比較 2918.5  應(yīng)用：基數(shù)排序 2918.5.1  思想 2928.5.2  實(shí)現(xiàn) 2928.5.3  分析 2958.5.4  小節(jié)練習(xí) 2958.5.5  編程項(xiàng)目 2958.6  散列 2968.6.1  稀疏表 2968.6.2  選擇散列函數(shù) 2978.6.3  利用開(kāi)放尋址的解決方案 2998.6.4  沖突的鏈?zhǔn)浇鉀Q方案 3038.6.5  小節(jié)練習(xí) 3058.6.6  編程項(xiàng)目 3068.7  散列分析 3078.7.1  一個(gè)數(shù)學(xué)娛樂(lè)問(wèn)題的分析 3078.7.2  計(jì)數(shù)搜索次數(shù) 3078.7.3  鏈?zhǔn)椒绞降姆治?nbsp;3088.7.4  開(kāi)放尋址方式的分析 3088.7.5  理論比較 3098.7.6  經(jīng)驗(yàn)比較 3108.7.7  小節(jié)練習(xí) 3118.7.8  編程項(xiàng)目 3128.8  總結(jié)：方法的比較 3128.9  應(yīng)用：回顧Life游戲 3128.9.1  算法的選擇 3138.9.2  數(shù)據(jù)結(jié)構(gòu)的聲明 3138.9.3  主程序 3148.9.4  函數(shù) 3158.9.5  編程項(xiàng)目 3188.10  注意事項(xiàng) 3198.11  復(fù)習(xí)題 3198.12  參考文獻(xiàn) 320
第9章  二叉樹(shù) 3219.1  二叉樹(shù)的介紹 3219.1.1  定義 3219.1.2  二叉樹(shù)的遍歷 3239.1.3  二叉樹(shù)的鏈接實(shí)現(xiàn) 3279.1.4  小節(jié)練習(xí) 3299.2  二叉搜索樹(shù) 3319.2.1  順序列表和實(shí)現(xiàn) 3329.2.2  樹(shù)搜索 3339.2.3  二叉搜索樹(shù)的插入 3369.2.4  樹(shù)排序 3389.2.5  二叉搜索樹(shù)的刪除 3399.2.6  小節(jié)練習(xí) 3429.2.7  編程項(xiàng)目 3439.3  構(gòu)建二叉搜