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

　　本书详细介绍了使用C语言实现数据结构的基本思想和程序算法，重点阐述了问题说明和程序的设计、分析、测试、验证以及正确性等方面的内容。本书主要特色：通过一些应用和所使用的开发标准，着重介绍了递归。包括一些案例分析，这些案将各个主题应用到实际的程序中。讨论了软件工程的一些主要原则，并将这些原则应用于大型编程项目中。详细介绍了数据抽象过程和数据抽象类型（ADT），并将ADT与实现决策相分离。本书可以为高等院校计算机及相关专业的教材，也可供各类软件开发人员参考。如果读者具备一些基础的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  构建二叉搜