数据结构与程序设计：C语言

目    录第1章  编程原则 11.1  引言 11.2  Life游戏 31.2.1  Life游戏规则 31.2.2  示例 31.2.3  解决方案 51.2.4  Life游戏主程序 51.3  编程风格 91.3.1  命名 91.3.2  文档及其格式 101.3.3  程序的细化和模块化 111.3.4  小节练习 131.4  编码、测试及进一步细化 151.4.1  占位程序 151.4.2  计算相邻元胞的数目 161.4.3  输入和输出 171.4.4  驱动程序 201.4.5  程序的跟踪 211.4.6  测试程序的原则 221.4.7  小节练习 241.4.8  编程项目 241.5  注意事项 251.6  复习题 261.7  参考文献 261.7.1  C语言 261.7.2  编程原则 271.7.3  Life游戏 27第2章  软件工程介绍 282.1  程序维护 282.1.1  Life程序回顾 282.1.2  关于Life程序的新起点和新方法 302.1.3  小节练习 312.1.4  编程项目 322.2  算法研究：Life程序的第二个版本 322.2.1  列表：数据结构的说明 322.2.2  主程序 352.2.3  信息隐藏 382.2.4  细化：子程序的开发 382.2.5  算法的验证 412.2.6  小节练习 432.3  编码 432.3.1  列表函数 442.3.2  错误处理 452.3.3  演示和测试 462.3.4  小节练习 492.3.5  编程项目 502.4  Life函数的编码 502.4.1  Vivify函数 502.4.2  AddNeighbors函数 512.4.3  混合函数 522.4.4  初始化 522.4.5  编程项目 532.5  程序分析与比较 532.5.1  语句数 532.5.2  比较 542.5.3  时间和空间的平衡 552.5.4  小节练习 552.5.5  编程项目 552.6  总结和展望 552.6.1  Life 游戏 562.6.2  程序设计 572.6.3  C语言 582.6.4  编程项目 592.7  注意事项 602.8  复习题 612.9  参考文献 612.9.1  软件工程 612.9.2  算法验证 622.9.3  问题解决 62第3章  堆栈和递归 633.1  堆栈 633.1.1  引言 633.1.2  第一个示例：线性颠倒 643.1.3  信息隐藏 653.1.4  堆栈的说明 653.1.5  堆栈的实现 673.1.6  链接堆栈 693.1.7  小节练习 723.1.8  编程项目 733.2  递归 743.2.1  子程序的堆栈图解 743.2.2  子程序调用树 743.2.3  阶乘：一个递归定义 763.2.4  分而治之：汉诺(HANOI)塔 773.2.5  小节练习 823.2.6  编程项目 823.3  回溯：推迟工作 833.3.1  解决8王后难题 833.3.2  示例：4王后 843.3.3  回溯 853.3.4  细化：选择数据结构 863.3.5  回溯分析 883.3.6  小节练习 893.3.7  编程项目 903.4  递归法则 903.4.1  设计递归算法 903.4.2  递归如何工作 913.4.3  尾部递归 943.4.4  何时不使用递归 963.4.5  指南和总结 1003.4.6  小节练习 1003.5  注意事项 1013.6  复习题 1023.7  参考文献 103第4章  队列和链表 1044.1  定义 1044.2  队列的实现 1074.3  C语言中的环形队列 1104.3.1  小节练习 1124.3.2  编程项目 1134.4  队列的应用：模拟 1144.4.1  引言 1144.4.2  机场的模拟 1144.4.3  主程序 1164.4.4  模拟的步骤 1184.4.5  伪随机数 1214.4.6  示例结果 1234.4.7  编程项目 1254.5  指针和链表 1264.5.1  引言和综述 1264.5.2  指针和C语言中的动态内存 1284.5.3  链表基础 1324.5.4  小节练习 1334.6  链接队列 1344.6.1  小节练习 1364.6.2  编程项目 1374.7  应用：多项式算术 1374.7.1  项目的目的 1374.7.2  主程序 1384.7.3  数据结构及其实现 1424.7.4  读取和写出多项式 1434.7.5  多项式加法 1454.7.6  完成项目 1474.7.7  小节练习 1474.7.8  编程项目 1484.8  抽象数据类型及其实现 1494.8.1  引言 1494.8.2  通用定义 1504.8.3  数据说明的细化 1524.8.4  小节练习 1534.9  注意事项 1534.10  复习题 1544.11  参考文献 154
第5章  通用列表 1565.1  列表说明 1565.2  列表的实现 1585.2.1  连续实现 1585.2.2  简单的链接实现 1595.2.3  变更：保持当前位置 1635.2.4  双向链表 1645.2.5  实现的比较 1665.2.6  小节练习 1675.2.7  编程项目 1685.3  字符串 1685.4  应用：文本编辑器 1705.4.1  说明 1715.4.2  实现 1715.4.3　编程项目 1785.5  数组中的链表 1785.5.1  方法 1795.5.2  操作：空间管理 1805.5.3  其他操作 1835.5.4  链表的变化 1845.5.5  小节练习 1845.6  排列 1865.6.1  思想 1875.6.2  细化 1875.6.3  通用函数 1885.6.4  数据结构：优化 1885.6.5  最终的程序 1895.6.6  编程项目 1915.7  注意事项 1915.8  复习题 1925.9  参考文献 192第6章  搜索 1936.1  搜索：介绍及其表示 1936.1.1  键 1936.1.2  分析 1936.1.3  外部搜索和内部搜索 1946.1.4  C语言实现 1946.1.5  参数 1946.2  顺序搜索 1956.2.1  算法及函数 1956.2.2  算法分析 1966.2.3  测试 1976.2.4  小节练习 1996.2.5  编程项目 2006.3  寄物处：项目 2016.3.1  介绍和说明 2016.3.2  演示及测试程序 2036.3.3  编程项目 2056.4  二叉搜索 2066.4.1  算法研究 2076.4.2  忽略版本 2086.4.3  识别等式 2106.4.4  小节练习 2116.4.5  编程项目 2126.5  比较树 2126.5.1  分析n=10的情况 2136.5.2  算法推广 2156.5.3  方法的比较 2186.5.4  普遍关系 2196.5.5  小节练习 2206.5.6  编程项目 2206.6  下限 2206.6.1  优化程序 2206.6.2  任意搜索算法 2216.6.3  观察2-树 2216.6.4  搜索下限 2236.6.5  其他的搜索算法 2236.6.6  小节练习 2246.6.7  编程项目 2246.7  渐近线 2246.7.1  介绍 2246.7.2  Big-O表示法 2256.7.3  Big-O表示法的不精确性 2276.7.4  通用函数的排序 2286.7.5  小节练习 2296.7.6  编程项目 2296.8  注意事项 2296.9  复习题 2306.10  参考文献 230第7章  排序 2327.1  介绍和符号 2327.2  插入排序 2337.2.1  顺序列表 2337.2.2  通常的插入排序 2347.2.3  链接版本 2367.2.4  分析 2377.2.5  小节练习 2387.2.6  编程项目 2397.3  选择排序 2407.3.1  算法 2407.3.2  连续实现 2417.3.3  分析 2427.3.4  比较 2437.3.5  小节练习 2437.3.6  编程项目 2447.4  希尔排序 2447.4.1  小节练习 2467.4.2  编程项目 2467.5  下限 2467.5.1  小节练习 2487.5.2  编程项目 2487.6  “分而治之”排序 2497.6.1  主要思想 2497.6.2  示例 2507.6.3  小节练习 2537.7  链表的归并排序 2547.7.1  函数 2547.7.2  合并分析 2567.7.3  小节练习 2587.7.4  编程项目 2597.8  连续列表的快速排序 2607.8.1  主函数 2607.8.2  列表的划分 2617.8.3  快速排序分析 2637.8.4  快速排序的平均情形分析 2657.8.5  与归并排序的比较 2667.8.6  小节练习 2677.8.7  编程项目 2697.9  堆和堆排序 2697.9.1  2-树的列表 2697.9.2  堆排序 2717.9.3  堆排序分析 2737.9.4  优先级队列 2747.9.5  小节练习 2757.9.6  编程项目 2767.10  回顾：方法的比较 2767.10.1  使用的存储空间 2767.10.2  计算机时间 2767.10.3  编程量 2767.10.4  统计分析 2777.10.5  实验测试 2777.10.6  小节练习 2777.11  注意事项 2797.12  复习题 2797.13  参考文献 280第8章  表和信息检索 2828.1  引言：突破lg n障碍 2828.2  矩形数组 2838.2.1  行优先和列优先顺序 2838.2.2  下标矩形数组 2838.2.3  访问表 2848.2.4  小节练习 2848.3  各种形状的表 2858.3.1  三角表 2858.3.2  不规则表 2868.3.3  反向表 2878.3.4  小节练习 2888.3.5  编程项目 2898.4  表：一种新的抽象数据类型 2898.4.1  函数 2898.4.2  抽象数据类型 2908.4.3  实现 2908.4.4  比较 2918.5  应用：基数排序 2918.5.1  思想 2928.5.2  实现 2928.5.3  分析 2958.5.4  小节练习 2958.5.5  编程项目 2958.6  散列 2968.6.1  稀疏表 2968.6.2  选择散列函数 2978.6.3  利用开放寻址的解决方案 2998.6.4  冲突的链式解决方案 3038.6.5  小节练习 3058.6.6  编程项目 3068.7  散列分析 3078.7.1  一个数学娱乐问题的分析 3078.7.2  计数搜索次数 3078.7.3  链式方式的分析 3088.7.4  开放寻址方式的分析 3088.7.5  理论比较 3098.7.6  经验比较 3108.7.7  小节练习 3118.7.8  编程项目 3128.8  总结：方法的比较 3128.9  应用：回顾Life游戏 3128.9.1  算法的选择 3138.9.2  数据结构的声明 3138.9.3  主程序 3148.9.4  函数 3158.9.5  编程项目 3188.10  注意事项 3198.11  复习题 3198.12  参考文献 320
第9章  二叉树 3219.1  二叉树的介绍 3219.1.1  定义 3219.1.2  二叉树的遍历 3239.1.3  二叉树的链接实现 3279.1.4  小节练习 3299.2  二叉搜索树 3319.2.1  顺序列表和实现 3329.2.2  树搜索 3339.2.3  二叉搜索树的插入 3369.2.4  树排序 3389.2.5  二叉搜索树的删除 3399.2.6  小节练习 3429.2.7  编程项目 3439.3  构建二叉搜