朴素数据结构（二）：简单离散结构——链表与散列表

/ 0评 / 0赞

链表 Linked list

有时我们希望能够将不同的内存块之间建立联系，而不需要将内存块复制到一起。通常而言，我们可以使用链表来实现。

单向链表

单向链表的思路是简单的。首先我们有一段内存，以及下一段内存的地址。但是这样我们会发现似乎无法表示第三块内存，那么我们则使用一个结构体来包括指向一段内存的指针和指向下一个结构体的指针，如下：

typedef struct linked_list {
    void *content;
    struct linked_list *next;
} linked_list_t;

这样我们就可以表示不连续但是相互关联的内存片段了。这里的 content 的类型我们使用了 void *, 这意味着我们之后将需要手动管理内容指针，而不是像之前使用 #define 为全部类型指定内容类型。这给了我们更高的自由度——现在我们可以在链表中存储任意数据类型而不需要局限为一种，如下所示：

// ...
linked_list_t list, list2;
char *str = "I am a string";
double number = 42.000001;
list.next = &list2;
list.content = (void *) &str;
list2.content = (void *) &number;
// ...

但是这样做也会有明显的问题——类型信息会丢失。我们依然有方法保留类型信息，但是目前由于我们会避免使用混合类型链表，所以这个信息就仍然交给开发者自行管理。

对于链表，手动进行管理会很麻烦，而且很容易出错。那么我们写一些包装函数来避免错误的产生：

linked_list_t *linked_list_new() {
    linked_list_t *list = malloc(sizeof(linked_list_t));
    list->content = NULL;
    list->next = NULL;
    return list;
}

void linked_list_delete(linked_list_t  *list) {
    if (list == NULL) return;
    linked_list_delete(list->next);
    free(list);
}

void linked_list_append(linked_list_t *list, void *content) {
    if (list->content == NULL) {
        list->content = content;
    } else {
        if (list->next == NULL) {
            linked_list_t *node = malloc(sizeof(linked_list_t));
            node->content = content;
            node->next = NULL;
            list->next = node;
        } else {
            linked_list_append(list->next, content);
        }
    }
}

void linked_list_insert(linked_list_t *list, void *content, size_t position) {
    if (list == NULL) return;
    linked_list_t *current = list;
    while (position-->0) {
        current = current->next;
        if (current == NULL) return;
    }
    linked_list_t *originalNext = current->next;
    linked_list_t *node = malloc(sizeof(linked_list_t));
    node->content = content;
    node->next = originalNext;
    current->next = node;
}

linked_list_t* linked_list_remove(linked_list_t *list, void *content) {
    if (list->content == content) {
        linked_list_t *newHead = list->next;
        list->next = NULL;
        linked_list_delete(list);
        return newHead;
    } else {
        linked_list_t *last = list;
        linked_list_t *current = list->next;
        while (current) {
            if (current->content == content) {
                last->next = current->next;
                free(current);
                break;
            }
            last = current;
            current = current->next;
        }
        return list;
    }
}

bool linked_list_contains(linked_list_t *list, void *content) {
    linked_list_t *current = list;
    while (current) {
        if (current->content == content)
            return true;
        current = current->next;
    }
    return false;
}

包装函数的最大作用是降低程序的复杂度和去除可能重复的代码段，顺便还可以起到辅助检查的作用。短的函数通常检查和调试起来会更简单。

这里我们使用了内容不复制。这就意味着对于比较和删除函数来说，有时尽管指针指向的内容相同，但是由于内存地址不同，所以仍旧视为不同的元素。要规避这个问题，我们可以引入比较函数，对于 linked_list_contains 函数的例子如下：

bool linked_list_contains_x(linked_list_t *list, void *content, bool (*comparator)(void *, void *)) {
    linked_list_t *current = list;
    while (current) {
        if (comparator(current->content, content))
            return true;
        current = current->next;
    }
    return false;
}

双向链表

双向链表则需要注意更多的东西。此时我们对于每个节点都会有两个指针需要处理，其结构如下：

typedef struct dual_linked_list {
    void *content;
    struct dual_linked_list *prev;
    struct dual_linked_list *next;
} dual_linked_list_t;

其创建、销毁和单向链表大同小异；但是其插入和删除则需要考虑更多内容：

void dual_linked_list_insert(dual_linked_list_t *list, void *content, size_t position) {
    dual_linked_list_t *current = list;
    for(position-->0) {
        current = current->next;
        if (current == NULL) return;
    }
    dual_linked_list_t *originalNext = current->next;
    dual_linked_list_t *node = malloc(sizeof(dual_linked_list_t));
    node->content = content;
    node->prev = current;
    node->next = originalNext;
    originalNext->prev = node;
    current->next = node;
}

dual_linked_list_t *dual_linked_list_remove(dual_linked_list_t *list, void *content) {
    dual_linked_list_t *current = list;
    if (current->content == content) {
        dual_linked_list_t *newHead = current->next;
        newHead->prev = NULL;
        current->next = NULL;
        dual_linked_list_delete(current);
        return newHead;
    } eles {
        while (current != NULL && current->content != content) {
            current = current->next;
        }
        if (current != NULL) {
            current->prev->next = current->next;
            current->next->prev = current->prev;
            free(current);
        }
        return list;
    }
}

链表环

通过上面的内容，我们可以思考到一个问题：链表可以成环。如果我们将链表尾部的后继指针指向链表开头，我们就创建了一个环。

这样一个环拥有一个良好的性质：对于环队列，或任何环状的结构，都可以用链表环来表示，而不需要做多余的判断。

同时它还具有一个不好的性质：当我们尝试使用之前的释放链表的方法去释放一个链表环时，这个程序将会出错或者挂死。那么如何正确地释放这个链表呢？这个问题作为练习。

散列集合 Hash set

有些时候我们希望能够表示一组数据，而且希望可以快速地查找这个数据是否存在于这个集合当中。对于整数，我们可以使用位图；对于小数，我们可以维护一个有序数组。但对于难以用数字表示的内容，比如字符串或者结构体，我们需要更好的方案。

一个方案是使用散列集合，即将字符串或者结构体映射成为一个整数，这样我们就可以使用简单的方式来处理了。下面出于简单说明概念而不拘泥于 C 语言的各种黑魔法，暂且只考虑字符串映射到数字的问题。

我们可以考虑这样一个函数 stringHash, 其作用是将字符串映射到 0 ~ 127 的整数上。显然这个函数可能会使得多个不一样的字符串映射到同一个数字上，但这个问题并不影响我们建立散列集合。下面给出这样一个函数的可能形式：

uint8_t stringHash(const char* str) {
    uint8_t result = 0;
    for (size_t i = 0; i < strlen(str); ++i) {
        result ^= (str[i] ^ i);
    }
    return result;
}

为了避免 ab 与 ba 拥有同样数值以及偶数个相同字符会导致函数值总是为 0, 特意选择 XOR 一个 i 使得这些值对顺序敏感，但尽管如此我们还是可以构造一个巧妙的字符串使得函数值相同。不过我们既然已经选择将字符串映射到一个字节上，我们应该做好冲突的准备。

一个常见的冲突解决方案是将冲突的值存储到链表当中，当进行存在性检查的时候，我们只需要先计算出其散列值，再进入到链表中单独比对即可。我们来实现这个容器：

#define HASHSET_CELL_SIZE 128

typedef struct hashset {
    linked_list_t* cell[HASHSET_CELL_SIZE];
} hashset_t;

hashset_t *hashset_new() {
    hashset_t *set = malloc(sizeof(hashset_t));
    for (int i = 0; i < HASHSET_CELL_SIZE; i++) {
        set->cell[i] = NULL;
    }
    return set;
}

void hashset_delete(hashset_t *set) {
    if (set == NULL) return;
    linked_list_delete(set->cell);
    free(set);
}

bool hashset_add(hashset_t *set, const char *str) {
    if (hashset_contains(set, str)) {
        return false;
    }
    uint8_t index = stringHash(str);
    if (set->cell[index] == NULL) {
        set->cell[index] = linked_list_new();
        set->cell[index]->content = str;
    } else {
        linked_list_append(set->cell[index], str);
    }
    return true;
}

void hashset_remove(hashset_t *set, const char *str) {
    uint8_t index = stringHash(str);
    if (set->cell[index] == NULL) return;
    else {
        if (set->cell[index]->next == NULL && set->cell[index]->content == (void*) str) {
            linked_list_delete(set->cell[index]);
            set->cell[index] = NULL;
        } else {
            set->cell[index] = linked_list_remove(set->cell[index], str);
        }
    }
}

bool hashset_contains(hashset_t *set, const char *str) {
    uint8_t index = stringHash(str);
    if (set == NULL) return false;
    if (set->cell[index] == NULL) return false;
    else return linked_list_contains(set->cell[index], str);
}

注意到在初始情况下，我们直接声明了 128 个链表指针，而实际情况下我们可能根本不需要使用这么多指针。但是这是必须的——我们的散列函数会产生 128 个值，而要希望散列集合能正常工作，我们需要保证散列函数是满射的。

但是如果我们实际存储量要远大于 128 个字符串呢？这时候肯定会产生大量的冲突，使得整个散列集合的查找和插入速度逐渐退化成链表的查找速度。这时候我们就需要对散列表进行扩容操作。更改散列表容量需要更改对应的散列函数，而这显然是不现实的——我们无法在运行过程中更改代码，至少在当前的配置下不行。

那么我们可以考虑编写一个足够好的散列函数，这个散列函数可以生成一个足够大的散列值，我们只需要按需取得一部分就可以了。下面展示一个简单的例子：

uint32_t stringHash(const char* str) {
    uint32_t out = 0xabadcafe;
    int sift = 0;
    for (size_t i = 0; i < strlen(str); i++) {
        uint32_t shiftedChar = ((uint32_t) str[i]) << sift;
        out ^= shiftedChar;
        if ((sift += 2) == 8) sift = 0;
    }
    return out;
}

/// ... in use
uint8_t index = (uint8_t) (stringHash(str) % 0xff);
/// ...

但是在扩容的时候，我们还需要将集合中的每个元素重新计算散列值（因为散列函数的取值范围变动了），并按照新的散列值重新放入集合的相应位置。

散列表 Hash map

现在我们有了集合，那么我们是否可以给出一个函数从集合映射到集合呢？

当然可以，而且并不需要作出太大的改动。我们只需要利用一下散列集合的索引值作为另一个散列集合的索引值即可。注意到这里的索引值并不是单纯地从散列函数中计算得出的值，而是包括在链表中位置的偏移量。

流 Stream

如何编写一个程序，在只使用 2GiB 内存的情况下在保存在磁盘中的 20 亿个 int 里找到最大值？平均数呢？（不需要考虑浮点数精度问题）。

一道面试题

答：2K 内存已经够用。（顺便 20 亿个整数的大小大概为 7.45GiB.）

有很多问题的解决方法并不是一股脑地把数据读入内存再操作，而是按需读入再进行操作。甚至我们可以让求值也不立即进行，而是按需进行。这种懒惰的操作不仅可以让我们节省计算资源，还可以让我们在有限的计算机上表示包含无穷的概念（如整数集合、有理数集合等）。

当然能够表示无穷并不代表可以计算无穷。这个技巧只是用有限空间表示一个包含无穷的概念，对其运算则仍然需要无穷长的时间。

具体怎么做呢？

假如我们拥有函数 getNextNumer 负责从磁盘中读出下一个数字的内容、hasNextNumber 判断是否还需要继续读出数字，那么对于最大值，其解法很简单：

// ...
int maxNumber = INT_MIN;
while (hasNextNumber()) {
    int currentNumber = getNextNumber();
    if (currentNumber > maxNumber)
        maxNumber = currentNumber;
}
return maxNumber;
// ...

这似乎有点显然了——然而好的思路总应该是显然的。

对于平均数，我们可以使用滚动平均算法来求：

// ...
long long count = 0;
double average = 0.0;
while (hasNextNumber()) {
    average = ((double) (count)) / ((double) (count + 1)) * average + ((double) getNextNumber()) / ((double) (count + 1));
}
return average;
// ...

惰性求值 Lazy evaluation

我们现在依旧是按照命令式的思维来进行编写的，这使得我们总是在提前求值。虽然并不是说提前求值不好，但是有时我们希望能够节约计算机资源。我们能否在 C 语言中实现懒惰求值呢？

所谓惰性求值，即对于任何表达式，直到确实需要使用这个值的时候才开始进行计算，否则就搁置计算。这样做的好处是，我们之前提到过，可以表示一些无穷的概念；还有一种好处就是这使得我们在编写程序的时候可以用数学抽象来定义控制流，而不需要告诉计算机每一步需要干什么。

但可惜 C 语言并不原生支持这个功能。然而我们可以借助之前的函数指针和链表，实现一些好玩的内容，比如具有惰性求值特性的管道流。

首先，我们定义一个管道节点。一个管道节点意味着一个操作，而管道节点又分成两类——过程管道和终结管道，前者表示对流入数据的一个处理，后者则表示对数据的收集。我们也约定直到遇到终结管道节点之前不进行求值。管道节点的 C 代码如下：

typedef enum pipe_type {
    process = 0,
    terminal = 1
} pipe_type;

typedef struct pipe_node {
    pipe_type type;
    struct pipe_node *next;
    // TODO: Function pointer?
} pipe_node_t;

我们还没有定义函数指针。仔细思考一下，我们需要用到的函数大抵有三类：数据提供函数 (Supplier)、数据映射函数 (Mapper)、数据归约函数 (Reducer)。如果比较熟悉 MapReduce 的话，会发现总体思路其实是十分相似的。

这三个主要函数的签名如下：

typedef void* (supplier)();
typedef void* (mapper)(void *);
typedef void* (reducer)(void *, void *);

由于 C 语言并不支持反射或者自省，即函数信息在编译后就会丢失，所以我们需要手动为这些函数做标记，扩充到 pipe_node_t 中如下:

typedef enum fn_type {
    supplier = 0,
    mapper = 1,
    reducer = 2
} fn_type;

typedef struct pipe_node {
    pipe_type type;
    struct pipe_node *next;
    fn_type fn_type;
    void *fn_ptr;
} pipe_node_t;

我们可以看到 fn_ptr 在结构体中成为了一个通用指针而非函数指针，在使用时我们需要将其转换成为对应函数指针格式。

我们首先来编写一个最简单的 supplier: 自然数数列。它的功能就是生成从 0 开始不断向上增加的整数。这里我们就不需要再将 void * 看作指针，而是直接将其值视作数，如下：

static int _currentCount = 0;
supplier int_stream;

void *int_stream() {
    return _currentCount++;
}

注意到我们使用了一个全局静态变量——这会导致在重用这个函数时出现错误——我们希望这个调用从始至终总是从 0 开始往上增加的。这就意味着我们应该将这种具有上下文的函数包裹成一个结构（或者说一个类）。我们来进行更改：

typedef struct supplier {
    void *context;
    void *(*supply)(void);
} supplier_t;

同样的，如果我们的映射函数和规约函数也需要上下文的话，我们也需要为其进行同样的包装：

这样我们也需要一并更改 pipe_node 中的内容：

现在我们可以写一些简单的管道节点生成函数并将其串联起来了：

管道流初看起来似乎并没有什么卵用，但是其具有一个优秀的性质：（如果正确实现的话）可以并发执行。我们将每个节点需要使用的上下文单独包装起来，使之互不影响。这在之后我们面临的多线程或者多进程编程中会有很大帮助。

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

Your comments will be submitted to a human moderator and will only be shown publicly after approval. The moderator reserves the full right to not approve any comment without reason. Please be civil.