引言

算法和数据结构是程序的基石，几乎每一个程序都需要它们，但绝大多数程序都不需要发明新的算法和数据结构。

为了方便后面的讨论，我们先在这里给出HTML中name-value键值对的定义：

typedef struct Nameval Nameval;
struct Nameval {
    char *name;
    int value;
};

Sorting

这里我们讨论一个现被广泛使用的排序算法：快排（quicksort）。

快排的递归实现

快排的核心思想就是分治，它每次选出一个枢轴点（pivot），然后将数组中比这一点值小的数放在它左边，比它大的数放在它右边，再递归处理左边的数组和右边的数组。由此我们可以轻松地写出以下优雅的递归代码（枢轴点随机）：

/* swap - swap arr[i] and arr[j] */
void swap(int arr[], int i, int j) {
    int temp;
    temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

/* quicksort - sort the array into increasing order recursively */
void quicksort(int arr[], int n_arr) {
    int last = 0;
    if (n_arr <= 1)    /* if array size < 1, then no need for sorting */
        return;
    swap(arr, 0, rand() % n_arr); /* generate pivot and move it to v[0] */
    /* move the elements smaller than pivot */
    for (int i = 1; i < n_arr; ++i) {
        if (arr[i] < arr[0])
            swap(arr, ++last, i);
    }
    /* restore povit */
    swap(arr, 0, last);
    /* recursively sort each part */
    quicksort(arr, last);
    quicksort(arr + last + 1, n_arr - last - 1);
}

快排的迭代实现

快排一般都是用递归形式写的，那么它如何用迭代的方式来写呢？

对于可以用分治解决的问题，我们一般都可以用辅助栈来将递归转换为迭代。这里我使用C++来实现，这样可以让我们更专注于算法思想而非语言的细枝末节。

// keep the range being sorted
struct SortRange {
    // constructor
    SortRange(size_t s, size_t e) : start(s), end(e) {}

    size_t start;
    size_t end;  // exclude index end
};

// quicksort_iter - sort the array into increasing order iteratively
void quicksort_iter(vector<int> &arr) {
    stack<SortRange> helper;
    default_random_engine e(time(nullptr));
    helper.push({0, arr.size()});
    // sort until the stack is empty
    while (!helper.empty()) {
        size_t last, start, end;
        start = helper.top().start;
        end = helper.top().end;
        last = start;
        // generate uniform distribution random numbers from [start, end-1]
        uniform_int_distribution<size_t> u(start, end - 1);
        helper.pop();
        if (end - start <= 1)  // if array size <= 1, no need for sorting
            continue;
        // generate pivot and move it to arr[start]
        swap(arr[start], arr[u(e)]);
        // move the elements smaller than pivot
        for (size_t i = start + 1; i != end; ++i)
            if (arr[i] < arr[start])
                swap(arr[++last], arr[i]);
        // restore pivot
        swap(arr[start], arr[last]);
        // put each part into stack for next loop
        helper.push({start, last});
        helper.push({last + 1, end});
    }
}

那么是不是我们应该避免用递归实现快排呢？毕竟“迭代快于递归”嘛。其实，快排可以说是递归优于迭代的典例了，既优雅又高效，可以放心地用递归版本。两者效率的讨论详见：Quicksort:Iterative or Recursive

快排的性能

显然快排是效率较高的排序算法，因为它不需要接连地与每一个其他数组元素比较，而每次只需与枢轴点的值比较，比它小就放左边，比它大就放右边。这一点就使得快排优于插入排序和冒泡排序。

若每轮都能较为平均地分为两部分，那么当整个数组共有n个元素时，n + 2 n / 2 + 3 n / 3 + ……共有logn轮，因此时间复杂度为O(nlogn)。但现实中是会有一些特殊的输入序列会使快排的划分完全不均匀，致使较差的性能表现，主要有以下三种：

已经接近顺序
已经接近逆序
所有元素都相等（其实是前两种的特殊情况）

在这些时候，若枢轴点选择不当，可以达到最差时间复杂度O(n²)。

Growing Arrays

这一节主要是讨论如何用C实现一个动态数组（类似C++中的vector），相比于实现的算法思路，我认为书中的一个设计细节更为引人注目。

当数组元素的个数要超出现有已分配的数组大小时，我们需要再分配更多的内存来容纳元素，在C语言中也就需要realloc函数。若实现动态数组的数据结构如下：

struct NVtab {
    int nval;   /* current number of values */
    int max;    /* allocated number of values */
    Nameval *nameval;    /* array of name-value pairs */
}nvtab;

那么在增添数组元素的函数中，我们很可能写出这样的代码：

...
if (nvtab.nameval == NULL) {   /* first time */
   ...
} else if(nvtab.nval > nvtab.max) {  /* grow */
    nvtab.nameval = (Nameval *)realloc(nvtab.nameval, (NVGROW * nvtab.max) * sizeof(Nameval));
    if (nvtab.nameval == NULL)
        return -1;
    ...
}

当分配内存成功时，这段代码是没问题的。但如果分配失败的话，nvtab.namval所指向的数组就会丢失了。因此，我们应该用一个局部变量来暂存分配的结果，若分配成功了，再由nvtab.nameval接管分配好的数组。

if (nvtab.nameval == NULL) {   /* first time */
   ...
} else if(nvtab.nval > nvtab.max) {  /* grow */
    Nameval *tmp = (Nameval *)realloc(nvtab.nameval, (NVGROW * nvtab.max) * sizeof(Nameval));
    if (tmp == NULL)
        return -1;
    nvtab.nameval = tmp;
    ...
}

Lists

Exercise 2-8. Write recursive and iterative versions of reverse, which reverses a list. Do not create new list items; re-use the existing ones.

这是一个很典型的数据结构题。我们在稍加思索后可以很容易地想出迭代的解法：遍历链表，将每一个节点指向它的前一个节点，第一个节点指向NULL。转换为代码：

/* reverse_iter - reverse the whole list iteratively */
Nameval *reverse_iter(Nameval *listp)
{
    Nameval *next;
    Nameval *prev = NULL;
    while (listp != NULL) {
        next = listp->next;
        listp->next = prev;
        prev = listp;
        listp = next;
    }
    return prev; 
}

那么如何递归地求解呢？写递归，最关键就是要牢记两条基本准则：

基准情形。必须要有某些基准情形，它无须递归就能解出。
不断推进。对于需要递归求解的情形，每一次递归调用都必须朝着接近基准情形的方向推进。
摘录自《数据结构与算法分析——C语言描述》

在这一道题目中，基准情况就是链表的第一个节点和最后一个节点。

若链表为空，则返回空。
若链表只有一个节点或到达了最后一个节点，这个节点就是头结点，它应指向前一个节点或NULL。

链表是单向的，它无法在顺序遍历时不记住前一个节点的情况下，指向前一个节点，因此我们应该在递归回溯时从后往前修改指针以达到指向前一个节点的目的。如：

node->next->next = node;

这样便实现了让后一个节点指向前一个节点。

综上，我们便可以写出递归的解法：

/* reverse_recur_helper - help to reverse the list recursively and get the head node */
void reverse_recur_helper(Nameval *listp, Nameval **head)
{
    if (listp == NULL)
        return;
    if (listp->next == NULL) {
        *head = listp;
        return;
    }
    reverse_recur_helper(listp->next, head);
    listp->next->next = listp;
    listp->next = NULL;
}

/* reverse_recur - reverse the list recursively */
Nameval *reverse_recur(Nameval *listp)
{
    Nameval *head;
    reverse_recur_helper(listp, &head);
    return head;
}

Hash Tables

在实现哈希表的查找时，我们很容易想到这样实现：

Nameval *lookup(char *name);

但这样的实现会使得如下的操作进行两次hash计算：

if (lookup("name") == NULL)
    additem(newitem("name", value));

因此，将查找和插入选项结合起来是一个更好的选择。

Nameval *lookup(char *name, int create, int value);

将整型转换为字符串

在创建HTMLname-value键值对时，为了方便，我想将name直接表示为value的字符串形式。在C++中，这是十分容易实现的：

name = to_string(value);

在C语言当中，我以前一直都是使用itoa函数的，但最近才发现该函数并不属于C语言标准，标准的写法应为：

/* to_string - convert an int to string */
char *to_string(int value) {
    char *buf;
    int size;
    size = snprintf(NULL, 0, "%d", value);  /* get length of string */
    buf = (char *)malloc(size + 1);   /* allocate one character more for null-terminator */
    snprintf(buf, size + 1, "%d", value);
    return buf;
}
name = to_string(value);