Irhine

home

Everyday Algorithm

08 Mar 2014

本文仅为读书笔记，版权归原书作者及中文译者所有。

基础数据结构

链表

链表由一连串的元素（成为节点）构成。每个节点包含要存储的数据项以及一个指针，它指向链表中的下一个节点。当程序读取每个数据项时，将创建一个新的节点（使用malloc()函数），必将其添加到链表的尾部。在输入结束时，计算机内存中将维护一个节点列表，其中每个节点都包含数据项（例如城市名称和气温信息）以及指向下一个节点的指针。每个节点中的指针称为链（link），因此将这种数据结构称为链表（linked list）。每个链表都以一个简单的指针开始，它指向链表中的第一个数据项，这个指针称为头指针（head）。

struct Node {
        char *City;
        int Temp;
        struct Node *Next;
    };

typedef struct Node * Link;

Link Head;

创建typedef是为了增强代码可读性。“链”是指向“节点”的指针。我们定义的第一个“链”是“头指针”，当链表为空时它是NULL，否则它指向第一个节点。 初始化一个这种类型的新链表只需要简单的初始化合适的变量：

Head = NULL;
NodeCount = 0;

一旦添加了第一个节点，头指针将指向它。添加节点可能很容易或者是乏味的。如果在添加节点时无需考虑他们在链表（无序链表）中所占据的位置，可以简单的将节点添加在链表头部。当为每个节点都分配了空间是，它的“链”将指向当前“头指针”，然后更新“头指针”以指向新的“节点”。

对于有序链表，向其中添加节点需要做更多的的工作：

程序清单2-1通过定义两个函数来执行这些任务，这样就可以执行添加节点的实际工作了：

在遍历链表时，仅当经过插入点或者已经到达链表尾部是。才能知道已经到了添加节点的位置。因此，将需要保存前一个被检查的节点地址。插入发生在当前被检查的节点和前一个节点之间：

prev->Next = pn;    /* prev must now point to pn */
pn->Next = curr;    /* and pn must now point to curr */

为了简化设计，程序中可以创建一个虚拟节点，并使当前链表从该节点延续下来。这样，链表就永远不会为空，实现的逻辑也将大大简化。程2-1从数据文件中读取城市和气温的信息，将记录插入到一个链表中（按气温和城市名称的升序排序），丢弃重复的记录，然后打印该有序链表，并指示位于中间的条目。数据记录是文本文件中简单的行，前三个字符表示气温，气候接着最多124个字符表示城市名称。 注意：如果不使用链表这样的动态结构，在不读取数据两边的情况下，将不可能确定出中间的气温。最后一个循环用于打印链表中的记录，它显示了遍历链表有多简单。

双向链表

双向链表使用的节点包含数据以及指向前一个和后一个节点的链。由于经常在链表商执行双向遍历，因此在双向链表的实现中建议定义一个额外的指针，用于跟踪链表中的最后一个节点。该指针称为尾指针（tail），它具有与头指针相同的功能————但是位于链表的尾部。 为了避免操作双向链表的过程中出错，一些优秀的程序员通常都有一组通用的例程，并且总是使用他们来实现双向链表。 具体例程见代码部分。

链表的其他特征

无论何时需要在内存中存储数量不确定的数据项时，采用动态数据结构很可能是最佳的方法。 使用链表的最大不便是他们的潜在长度。搜索一个很长的链表可能很费时，而且如果不得不重复搜索很长的链表，其代价可能变得令人无法忍受。有多种技术可以用来减小开销：

这些方法只会在链表不太长的情况下才有效，数据项非常多的情况下，链表的效率太低，应选择其他的动态数据结构：

如果性能和空间是需要重点考虑的因素，使用单链表；大多数情况，应该使用双链表，建立第二个指针的额外开销只会给性能带来很小的负担。

栈和队列，stack and queue

用数组和链表都可以很好地实现栈和队列，但是建议在编译时而不是在运行时确定最大大小；因此，数组是实现这些数据结构的合理方式。

栈的特征

栈是一种简单的数据结构，可以最容易的表示为数组，其中添加和删除数据项是在同一端进行的。栈存储数据的方法称为后进先出（LIFO）。 栈的应用有很多，大多数情况下，当程序员需要知道什么动作或数据位于当前正在进行的动作之前是，就可以使用栈。例如，当今的大多数编译器通过使用栈来实现高级语言。当调用函数或子例程时，就把代码行的下一个指令的地址放到栈上。然后，当函数返回时，程序就会从栈中获取到该地址，并从那一点继续向下执行。在函数调用了其他函数的情况下，将把每一个返回地址都放到栈上。这样，当函数结束时，就可以找到它们在栈中的地址。

队列的特征

队列是可以在一端添加数据项而在另一端删除数据项的数据结构。

队列的基本操作：

队列虽然看起来容易实现，但实际上隐藏了许多微妙的细节。首当其冲的就是内存的表示问题。一般用数组或者链表来实现队列。这两种情况都存在同一个问题：如果保持在队尾添加元素并从队头删除元素，队列的数据结构将缓慢地在内存中迁移。

散列

当数据的数量不确定时，链表提供了一种在内存中存储数据的方法。但链表的缺点是，它们的构造使得必须按顺序访问节点。也就是说，为了到达任意的节点，都必须访问链表中它之前的所有节点。可以使用多种技术（比如对节点进行排序，或者将最近访问的节点放到靠近链表头部的位置）来减少顺序查找所需的时间；但是这些方法都无法消除查找本身是按照顺序进行的这个要求。

为了提供对内存中存储的数据项的快速、随机访问，一种巧妙的解决方案是散列表（hash table）。C语言中的常规表（比如struct数组）要求提前确定表中的元素数量。不过散列表可以在表中存放数量不确定的项目，同时不会损失快速、近似随机的访问。

散列的概念

散列表的秘密是：它提供了一种方法，可以计算出特定的数据存储在表中的什么位置。这种测定是由散列函数（hash function）执行的，它接受一份要存储到表中的数据，并生成一个数字，用来指定数据将存储在表中的哪个槽（slot）中。这个数字称为散列键（hash key）。

例如，有一个表，它具有26个可能的槽，设计一个允许将英文单词存放到表中的散列函数非常简单，可以使用每个单词的首字母作为散列键：

char * word_to_hash;
hash_key = tolower(*word_to_hash) - 'a';

这样，数据将被存储到table[hash_key]中。虽然这个散列函数很简单，但是它使得最终的表很小，以至于不能存放许多单词。在实际应用中，必须使用更大的表。

一个需要立即考虑的问题是：如何解决两个表项散列到表中同一个槽的问题。这种情况称为冲突（collision）。所有解决冲突的方法分为两类：

散列函数

将生日转换为0~365之间的唯一数字的散列函数是一种特例。它被称为完美散列函数（perfect hash function）。它是完美的，因为对于传给它的每份数据，它都会生成唯一的散列值。在一年内没有任何两个日期具有相同的散列值。为了生成完美的散列值，必须知道散列函数的所有可能的输入，并且必须能够编写一个函数，它可以为每个输入生成唯一的值。就生日而言，我们知道日期的范围，以及如何为每个日期构造唯一的数字。我们可以编写一个非完美的散列函数，比如：

hash_value = dd * mm - 1;

它将大致产生0~371之间的键。它是非完美的，因为它不会为每个唯一的输入生成唯一的输出：3月10日和10月3日都会生成散列值29。更糟糕的是，重复的值倾向于聚集在表的下部，而上部主要包含空槽（所有大于31的素数都未被使用，通过大于12的素数的乘积计算得到的所有散列也是如此）。如果选择一种非完美的算法，就以为着无法保证通过不超过一次的查找即可访问表元素。

不过，在现实情况中，几乎不可能构造完美的散列算法，花费精力寻找他们往往是白费力气。不可能编写出它们，因为通常几乎不可能提前知道要散列的完整数据集。

良好的散列函数具有以下两个特点：

之前用每个单词的首字母作为散列键，这个函数无疑是快速的，但它具有两个问题：

为了生成最大数量的散列键，散列函数通常会生成相当多的结果，然后用这个数量除以表的大小。 通常，散列函数具有如下形式：

hash-key = calculated-key % tablesize

其中%是取模运算。为了提高散列键的离散程度，tablesize应该是一个素数。生成calculated-key的过程是许多计算机科学论文的主题。不过，事实证明，应用程序用于计算散列键所花费的时间，很少，缓慢的性能很少是由于拙劣的散列算法产生的。如果满足以下条件，散列函数一般将快速工作：

查找

比较两个字符串以及在一个字符串中查找另一个字符串是密切相关的基本编程操作。字符串比较操作要回答“两个给定的字符串相似么，或者它们相同么？”这样的问题。ANSI C中的strcmp()系列函数提供了这种操作。相比而言，字符串查找操作要从头至尾查看一个大文本块，找出与目标字符串匹配的任何子串。为了解决这个问题，ANSI C提供了strstr()函数。这些ANSI函数都是相关的，这是由于从本质上讲，任何查找操作都必须反复比较查找文本的多个不同的子串。不过，这些ANSI C函数只提供了最基本的查找和比较操作。

查找的特征

蛮力查找

蛮力查找只是简单地缓慢通过一段文本，以寻找指定的字符串。当你需要快速且无需太多想象力地解决简单的问题时，就可能编写这种类型的算法。

未经优化的蛮力查找主要是读取一段文本，并且对每个字符调用strncmp()函数，已测试字符串是否匹配。

一种优化的思路是，仅当在字符串的第一个字符上发生匹配时，才需要调用strncmp()函数，而不会为每个字符都调用它。不过，即使在调用strncmp()之前测试是否存在这个匹配，我们仍将对每个字符执行两种测试：一种用于测试匹配，另一种用于测试文本末尾的标记。如我们前面所指出的，良好的查找性能期望对每个字符执行少于一次的比较。

一种解决方案是使用switch语句，许多编译器会把switch语句实现为一个跳转表（jump table），而不是一系列的if/else条件（跳转表是一个已知大小的数组，其元素由指向可执行代码的指针组成）。当使用跳转表时，switch中的变量只需测试一次，即可跳转到相应case语句的代码上。使用以下代码将是理想的，尤其是当编译器把switch语句实现为跳转表时：

switch(*text)
{
    case '\0':      /* test for end of the text */
        return NULL;
    case *string:   /* test for match with string */
        // call to strncmp()
    default:
        text += 1;      /* look at next character */
}

不幸的是，C语言不允许在运行时评估case语句；因此，诸如 case * string 之类的代码是非法的。在编译时必须知道每个case的值。此外，这种短小（<4）的switch语句基本上都会被实现为一系列的if/else语句，这意味着查找文本中的每个字符热然会被检查许多次。

下面的函数利用查找表解决了上面的问题：

char * BruteSearch(const char * text, const char * string)
{
    int len = strlen(string);

    /* the table. "static" assures its initialized to '\0's */
    static char lookup[UCHAR_MAX + 1]; 
    lookup[0] = 1;  /* EOT process */
    lookup[(unsigned char)(*string)] = 2;   /* a match */

    for ( ; ; text++)
    {   
        switch(lookup[(unsigned char)(*text)])
        {   
            case 0:
                break;      /* it's not EOF or a match */
            case 1:
                return (NULL);      /* EOF */
            case 2:
                if (strncmp(string + 1, text + 1, len - 1) == 0)
                    return ((char *)text);      /* a match */
                break;
            default:    /* good coding to include default */
                break;
        }   
    }   
}

这个函数实现了一个查找表，这个表包含256个值，其中每个值对应于以8位字节表示的一个可能的字符。使用static关键字将lookup表中的值都初始化为0。然后进入表中，并把特殊的值赋予我们感兴趣的字符：

然后使用switch语句来确定每个输入字符的查找值：

这个版本比较快，有三个原因：

他还有另外一个优点，即可以在不产生更多比较的情况下来查找额外的字符串。例如，要执行不区分大小写的查找，可以通过设置查找表，使得*string的大写和小写版本都返回2，并且case 2调用不区分大小写版本的strncmp()。

需要注意的是，当在*string 和 *text 之间找到一个匹配时，应该在text中的下一帧继续查找额外的匹配。你可能想尝试跳过 *string的长度，但这在很多情况下是不对的，例如在ffffff中查找ff的匹配结果。

查找时间的两个极端是：

经过优化的蛮力查找算法很容易理解，并且工作的相当好。可以在大多数情况下使用它。

排序

ANSI C的 qsort() 函数是一个可工作的基本排序工具，但它存在以下的问题：

尽管有这些缺点，qsort() 通常还是很好的选择，因为编译器库的版本通常速度非常快。

排序的基本特征

所有的排序都是基于每个记录内包含的键的。

冒泡排序

如果需要一种可以快速编程的小排序算法，可以选择冒泡排序。它对于几乎排好序的文件这行的非常快，但是他的常规性能相对较差，所以通常不要使用它。

冒泡排序算法非常简单：连续的扫描待排序的记录，每扫描一次，都会移动最大的记录到顶部，就像气泡一样缓慢上升－－因此而得名。由于每次扫描都会把一条记录置于它的最终正确的位置上，因此下一次扫描将不需要重新检查这条记录。

伪代码

for limit = n - 1 to 1 begin
    for i = 0 to limit begin
        if array[i] > array[i + 1] then
            swap array[i] and array[i + 1]
    end
end

时间复杂度是：O(n2)

插入排序

插入排序的工作方式类似于桥牌选手在对一副牌进行排序时所做的那样：当选取后续的每一张牌时，就相对于以前选取的牌把它插入到正确的位置。

插入排序的一个重要的设计要点是：在选取每个新纪录并准备把它插入到有序记录当中属于它的位置时，如何（从前往后还是从后往前）来查看一遍有序记录？对于这个问题，书中给出的结论是，通常情况下，应该从后往前查找有序的记录。

伪代码：

for step = 1 to N begin
    temp = array[step]
    for i = step - 1 to 0 begin
        if array[i] > temp then
            array[i + 1] = array[i]
        else
            break
    end
    array[i + 1] = temp
end

时间复杂度是：O(n2)

希尔排序

希尔排序是插入排序的一个灵巧的变体。它首先观察到插入排序之所以缓慢的原因是：它一次只把一个项目称过一组有序的记录。因此，如果记录离它们的最终位置很远，则只有在经过许多次交换之后才能正确地定位它们。改进的方式是：在排序的早期阶段允许记录跳转较大的距离。针对这个问题，希尔排序的思想是：把记录分成几个交替的组，使用插入排序对每个组进行排序。

例如，有8个待排序的记录。首先，把它们分成交替的4对，并对每一对进行排序。然后把记录分成两个交替的组，每组包含4个记录，并再次进行排序。最后，对整组记录进行排序。

这种每隔h个记录选择一个记录以便反复再分为交替记录集的方式称为“h排序”，并且可以根据所用的h的序列来描述希尔排序。

使希尔排序工作的关键是：可以使用任何稳定递减的h序列，只要h的最后一个值是1即可。实际上，当h为1时，我们所得到的只是普通的插入排序。这最后一遍插入排序会确定所有记录的最终顺序；所有之前的排序都只有一个目标：为下一步排序产生上一遍排序可以在线性时间内排序的“几乎”有序的文件。

选择合适的h值序列需要做大量的工作。但是“最佳的”序列仍然是未知的。一种产生表现良好的h的序列的方法是：

设 h(1) = 1, n = 待排序的记录数
设 h(s+1) = 3h(s) + 1, 当h > n/9 时停止

希尔排序的时间复杂度依赖于所选的h序列，使用上面的h值序列的实现大约具有N(1.25)的阶。虽然希尔排序不具有像插入排序或者冒泡排序处理已经有序的记录时那样引人注目的速度，但是处理逆序或随机顺序的记录时它不会遭受显著的速度降级。希尔排序的运行时间对输入数据相当不敏感，它唯一负面的特性是，它不是一种稳定的排序。不过综合起来讲，这行特性使得希尔排序成为几乎任何情况下的一个优秀的选择，它应该是优先考虑的几种算法之一。

快速排序

O(NlgN)

快速排序对待排序的记录采用“分治”法。在排序的每一步，都把记录分成两个分区。这种分区是基于称为基准(pivot)的记录进行的。将小于基准的所有记录划分到一个分区中，而将大于基准的记录划分到另一个分区中。等于基准的记录则可以划分到任何一个分区中。通过允许将等于基准的记录划分到任何一个分区中，快排将把由于数据集包含许多具有等号键的记录而引起的降级行为减至最少。然后，快排将对两个分区进行快速排序。

快排实现的难点在于：

堆排序

一般来讲，正确实现的快速排序难以超越。不过快排最坏的情况下是O(n2)的，总是存在你的程序将遇到最坏条件的可能性。在本节中，我们将研究堆排序，它是O(NlgN)的另一种排序，通常要比快排慢一些，但是不存在最会情况。

stillzhl
Python Programmer

github.com/stillzhl
twitter.com/highly3