《程序员实用算法》源代码

本书重点关注的是实用、立即可用的代码，并且广泛讨论了可移植性和特定于实现的细节。本书作者介绍了一些有用但很少被讨论的算法，它们可用于语音查找、日期和时间例程（直到公元1年）、B树和索引文件、数据压缩、任意精度的算术、校验和与数据验证，并且还最全面地介绍了查找例程、排序算法和数据结构。

数据结构与算法是计算机专业的核心课程，是计算机软件开发和应用人员必备的专业基础。今天的大多数关于算法的图书都是大学教科书，或者是令人厌倦的相同算法集合改头换面后的作品。本书是给出所有算法的完整代码实现的第一本书，这些算法对于开发人员在其日常工作中是有用的。

本书介绍了关于算法的基础知识、基本数据结构、散列、查找、排序、树、日期和时间、任意精度的算术运算、数据压缩以及数据完整性和验证等内容。本书的目的是为在应用程序中使用的算法提供一个实用的纲要。与关于算法的大多数著作不同的是，本书不是一本教材：书中没有提供实现细节，把它作为练习留给读者完成；也没有利用较小的代码段对算法进行高度理论化的讨论，以说明如何进行实现。相反，本书完全用C语言实现了各种算法，并且讨论了如何在各种应用程序中最佳地使用它们。

本书只要求读者具有C语言的初级知识以及不超出基本代数之外的数学知识。源代码是符合ANSI标准的，并且对它们进行了测试，它们都可以运行在UNIX下以及Borland、Microsoft和Watcom的编译器上。

封面图

目录

• 译者序
• 前言
• 致谢
• 第1章绪论
• 11评估算法
• 12修改算法
• 121主要的优化：I/O
• 122主要的优化：函数调用
• 13资源和参考资料
• 第2章基本数据结构
• 21链表
• 211双向链表
• 212链表的其他特征
• 22栈和队列
• 221栈的特征
• 222队列的特征
• 第3章散列
• 31散列的概念
• 32散列函数
• 33冲突解决方法
• 331线性再散列法
• 332非线性再散列法
• 333外部拉链法
• 34性能问题
• 35资源和参考资料
• 第4章查找
• 41查找的特征
• 411准备时间
• 412运行时间
• 413回溯的需要
• 42蛮力查找
• 43BoyerMoore查找
• 431启发式方法#1：跳过字符
• 432启发式方法#2：重复模式
• 44多字符串查找
• 45用于正则表达式的字符串
• 查找：grep
• 46近似字符串匹配技术
• 47语音比较：Soundex算法
• 48Metaphone：现代的Soundex
• 49选择技术
• 410资源和参考资料
• 4101通用参考资料
• 4102BoyerMoore
• 4103多字符串查找
• 4104正则表达式查找
• 4105近似字符串匹配
• 4106Soundex算法和Metaphone
• 算法
• 第5章排序
• 51排序的基本特征
• 511稳定性
• 512对哨兵的需求
• 513对链表进行排序的能力
• 514输入的阶的相关性
• 515对额外存储空间的需求
• 516内部排序技术与外部排序
• 技术
• 52排序模型
• 521冒泡排序
• 522插入排序
• 523希尔排序
• 524快速排序
• 525堆排序
• 53对链表进行插入排序
• 54对链表进行快速排序
• 55对多个键进行排序——不稳定
• 排序的修正方法
• 56网络排序
• 57小结：选择一种排序算法
• 58资源和参考资料
• 第6章树
• 61二叉树
• 611树查找
• 612节点插入
• 613节点删除
• 614二叉查找树的性能
• 615AVL树
• 62红黑树
• 63伸展树
• 64B树
• 641保持B树平衡
• 642实现B树算法
• 643B树实现的代码
• 65可以看见森林吗
• 66资源和参考资料
• 第7章日期和时间
• 71日期例程的库
• 72时间例程
• 73用于日期和时间数据的格式
• 74最后的提醒
• 75资源和参考资料
• 第8章任意精度的算术
• 81构建计算器82表示数字
• 83计算
• 84加法
• 85减法
• 86乘法
• 87除法
• 88关于计算器要注意的最后几点
• 89用于计算平方根的牛顿算法
• 810分期付款表
• 811资源和参考资料
• 第9章数据压缩
• 91行程编码
• 92霍夫曼压缩
• 921代码
• 922其他问题
• 93滑动窗口压缩
• 94基于字典的压缩（LZW）
• 941LZW算法的伪代码
• 942LZW压缩的实现
• 943填满字典
• 95使用哪种压缩方法
• 96资源和参考资料
• 第10章数据完整性和验证
• 101简单的校验和
• 102加权校验和
• 103循环冗余校验
• 1031CRCCCITT
• 1032CRC16
• 1033CRC32
• 104资源和参考资料