这个练习中，我打算上一节速成课，内容是使用Valgrind的两个工具callgrind和cachegrind。这两个工具会分析你程序的执行，并且告诉你哪一部分运行缓慢。这些结果非常精确，因为Valgrind的工作方式有助于你解决一些问题，比如执行过多的代码行，热点，内容访问问题，甚至是CPU的缓存未命中。

我彻底失败了。我放弃了多年以来尝试理清C语言如何编写的想法，因为它的发明是有缺陷的。起初，我的书中有一章叫做“解构 K&R C”。这一章的目的是告诉人们永远不要假设它们的代码是正确的，或者对于任何人的代码，不管它有多出名，也不能避免缺陷。这看起来似乎并不是革命性的想法，并且对我来说它只是分析代码缺陷和...

我现在打算向你展示使用TSTree来创建服务器中的快速URL路由。它适用于应用中的简单的URL匹配，而不是在许多Web应用框架中的更复杂（一些情况下也不必要）的路由发现功能。

我打算使用RingBuffer来创建一个非常简单的小型网络测试工具，叫做netclient。为此我需要向Makefile添加一些工具，来处理bin/目录下的小程序。

我打算向你介绍的最后一种数据结构就是三叉搜索树（TSTree），它和BSTree很像，除了它有三个分支，low、equal和high。它的用法和BStree以及Hashmap基本相同，用于储存键值对的数据，但是它通过键中的独立字符来控制。这使得TSTree具有一些BStree和Hashmap不具备的功能。

这是一个简单的算法，我将其用于“联机”（不储存任何样本）收集概要统计。我在任何需要执行一些统计，比如均值、标准差和求和中使用它，但是其中我并不会储存所需的全部样本。我只需要储存计算出的结果，它们仅仅含有5个数值。

环形缓冲区在处理异步IO时非常实用。它们可以在一段接收随机长度和区间的数据，在另一端以相同长度和区间提供密致的数据块。它们是Queue数据结构的变体，但是它针对于字节块而不是一系列指针。这个练习中我打算想你展示RingBuffer的代码，并且之后你需要对它执行完整的单元测试。

二叉树是最简单的树形数据结构，虽然它在许多语言中被哈希表取代，但仍旧对于一些应用很实用。二叉树的各种变体可用于一些非常实用东西，比如数据库的索引、搜索算法结构、以及图像处理。

这个练习中，我会向你展示可能是最快的字符串搜索算法之一，并且将它与bstrlib.c中现有的binstr比较。binstr的文档说它仅仅使用了“暴力搜索”的字符串算法来寻找第一个实例。我所实现的函数使用Boyer-Moore-Horspool（BMH）算法，如果你分析理论时间的话，一般认为它会更快。你也会看到，如果我的实现没有任何缺陷，BMH的...

到现在为止，你已经知道了大多数用于构建其它数据结构的数据结构。如果你拥有一些List、DArray、Hashmap 和 Tree，你就能用他们构造出大多数其它的任何结构。你碰到的其它任何结构要么可以用它们实现，要么是它们的变体。如果不是的话，它可能是外来的数据结构，你可能不需要它。

练习38：哈希算法 原文：Exercise 38: Hashmap Algorithms 译者：飞龙 你需要在这个练习中实现下面这三个哈希函数： FNV-1a 以创造者Glenn Fowler、Phong Vo 和 Landon Curt Noll的名字命名。这个算法产生合理的数值并且相当快。 Adler-32 以Mark Adler命名。一个比较糟糕的算法，但是由来已久并且适于学习。 DJB Hash ...

哈希表（HashMap、HashTable以及Dictionary）广泛用于许多动态编程语言来储存键值对的数据。哈希表通过在键上执行“哈希”运算产生整数，之后使用它来寻找相应的桶来获取或储存值。它是非常快速的使用数据结构，因为它适用于任何数据并且易于实现。

这个练习中我打算涉及到四个排序算法和一个搜索算法。排序算法是快速排序、堆排序、归并排序和基数排序。之后在你完成基数排序之后，我打算想你展示二分搜索。

我已经在练习26中，构建devpkg的时候介绍了Better String库。这个练习让你从现在开始熟悉bstring库，并且明白C风格字符串为什么十分糟糕。之后你需要修改liblcthw的代码来使用bstring。

动态数组是自增长的数组，它与链表有很多相同的特性。它通常占据更少的空间，跑得更快，还有一些其它的优势属性。这个练习会涉及到它的一些缺点，比如从开头移除元素会很慢，并给出解决方案（只从末尾移除）。

我将想你介绍涉及到排序的两个算法，你可以用它们操作链表。我首先要警告你，如果你打算对数据排序，不要使用链表，它们对于排序十分麻烦，并且有更好的数据结构作为替代。我向你介绍这两种算法只是因为它们难以在链表上完成，并且让你思考如何高效操作它们。

这本书的目的是教给你计算机实际上如何工作，这也包括多种数据结构和算法函数。计算机自己其实并没有太大用处。为了让它们做一些有用的事情，你需要构建数据，之后在这些结构上组织处理。其它编程语言带有实现所有这些结构的库，或者带有直接的语法来创建它们。C需要你手动实现所有数据结构，这使它成为最“完美”的语言，...

我已经教给你一些关于我的强大的调试宏的技巧，并且你已经开始用它们了。当我调试代码时，我使用debug()宏，分析发生了什么以及跟踪问题。在这个练习中我打算教给你一些使用gdb的技巧，用于监视一个不会退出的简单程序。你会学到如何使用gdb附加到运行中的进程，并挂起它来观察发生了什么。在此之后我会给你一些用于gdb...

自动化测试经常用于例如Python和Ruby的其它语言，但是很少用于C。一部分原因是自动化加载和测试C的代码片段具有较高的难度。这一章中，我们会创建一个非常小型的测试“框架”，并且使用你的框架目录构建测试用例的示例。

C语言编程的核心能力之一就是链接OS所提供的库。链接是一种为你的程序天机额外特性的方法，这些特性有其它人在系统中创建并打包。你已经使用了一些自动包含的标准库，但是我打算对哭的不同类型和它们的作用做个解释。

在下面的三个练习中你会创建一个项目的目录框架，用于构建之后的C程序。这个目录框架会在这本书中剩余的章节中使用，并且这个练习中我会涉及到Makefile便于你理解它。

你已经学到了大多数C语言的基础，并且准备好开始成为一个更严谨的程序员了。这里就是从初学者走向专家的地方，不仅仅对于C，更对于核心的计算机科学概念。我将会教给你一些核心的数据结构和算法，它们是每个程序员都要懂的，还有一些我在真实程序中所使用的一些非常有趣的东西。

这本书你已经完成一半了，所以你需要做一个期中检测。期中检测中你需要重新构建一个我特地为本书编写的软件，叫做devpkg。随后你需要以一些方式扩展它，并且通过编写一些单元测试来改进代码。

在C语言中，你可以通过创建“变参函数”来创建你自己的printf或者scanf版本。这些函数使用stdarg.h头，它们可以让你为你的库创建更加便利的接口。它们对于创建特定类型的“构建”函数、格式化函数和任何用到可变参数的函数都非常实用。

你已经学会了使用printf来打印变量，这非常不错，但是还需要学习更多。这个练习中你会用到fscanf和fgets在结构体重构建关于一个人的信息。在这个关于读取输入的简介之后，你会得到C语言IO函数的完整列表。其中一些你已经见过并且使用过了，所以这个练习也是一个记忆练习。

这个练习是一个脑筋急转弯，我会向你介绍最著名的C语言黑魔法之一，叫做“达夫设备”，以“发明者”汤姆·达夫的名字命名。这一强大（或邪恶？）的代码中，几乎你学过的任何东西都被包装在一个小的结构中。弄清它的工作机制也是一个好玩的谜题。

许多人在开始编程时，对“作用域”这个概念都不是很清楚。起初它来源于系统栈的使用方式（在之前提到过一些），以及它用于临时变量储存的方式。这个练习中，我们会通过学习站数据结构如何工作来了解作用域，然后再来看看现代C语言处理作用域的方式。

这个练习是C语言中所有可用的数据类型和控制结构的摘要。它也可以作为一份参考在补完你的知识，并且不含有任何代码。我会通过创建教学卡片的方式，让你记住一些信息，所以你会在脑子里记住所有重要的概念。

在C中有一个永恒的问题，它伴随了你很长时间，然而在这个练习我打算使用一系列我开发的宏来解决它。到现在为止你都不知道它们的强大之处，所以你必须使用它们，总有一天你会来找我说，“Zed，这些调试宏真是太伟大了，我应该把我的第一个孩子的出生归功于你，因为你治好了我十年的心脏病，并且打消了我数次想要自杀的念头...

Whatever I have up till now accepted as most true and assured I have gotten either from the senses or through the senses. But from time to time I have found that the senses deceive, and it is prudent never to trust completely those who have deceived us even once. 勒内·笛卡尔，《第一哲学沉思录》