FaGe's Blog

吹啊吹啊。

标签:include

共 29 篇文章

练习47:一个快速的URL路由

练习47:一个快速的URL路由 原文:Exercise 47: A Fast URL Router 译者:飞龙 我现在打算向你展示使用TSTree来创建服务器中的快速URL路由。它适用于应用中的简单的URL匹配,而不是在许多Web应用框架中的更复杂(一些情况下也不必要)的路由发现功能。 我打算编程一个小型命令行工具和路由交互,他叫做urlor,读取简单的路由文件,之后提示用户输入要检索的URL。 #include <lcthw/tstree.h> #include <lcthw/bstrlib.h> TSTree *add_route_data(TSTree *routes, bstring line) { struct bstrList *data = bsplit(line, ' '); check(data-...

阅读全文

练习46:三叉搜索树

练习46:三叉搜索树 原文:Exercise 46: Ternary Search Tree 译者:飞龙 我打算向你介绍的最后一种数据结构就是三叉搜索树(TSTree),它和BSTree很像,除了它有三个分支,low、equal和high。它的用法和BStree以及Hashmap基本相同,用于储存键值对的数据,但是它通过键中的独立字符来控制。这使得TSTree具有一些BStree和Hashmap不具备的功能。 TSTree的工作方式是,每个键都是字符串,根据字符串中字符的等性,通过构建或者遍历一棵树来进行插入。首先由根节点开始,观察每个节点的字符,如果小于、等于或大于则去往相应的方向。你可以参考这个头...

阅读全文

练习45:一个简单的TCP/IP客户端

练习45:一个简单的TCP/IP客户端 原文:Exercise 45: A Simple TCP/IP Client 译者:飞龙 我打算使用RingBuffer来创建一个非常简单的小型网络测试工具,叫做netclient。为此我需要向Makefile添加一些工具,来处理bin/目录下的小程序。 扩展Makefile 首先,为程序添加一些变量,就像单元测试的TESTS和TEST_SRC变量: PROGRAMS_SRC=$(wildcard bin/*.c) PROGRAMS=$(patsubst %.c,%,$(PROGRAMS_SRC)) 之后你可能想要添加PROGRAMS到所有目标中: all: $(TARGET) $(SO_TARGET) tests $(PROGRAMS) 之后在clean目标中向rm那一行添加PROGRAMS: rm -rf b...

阅读全文

练习44:环形缓冲区

练习44:环形缓冲区 原文:Exercise 44: Ring Buffer 译者:飞龙 环形缓冲区在处理异步IO时非常实用。它们可以在一端接收随机长度和区间的数据,在另一端以相同长度和区间提供密致的数据块。它们是Queue数据结构的变体,但是它针对于字节块而不是一系列指针。这个练习中我打算向你展示RingBuffer的代码,并且之后你需要对它执行完整的单元测试。 #ifndef _lcthw_RingBuffer_h #define _lcthw_RingBuffer_h #include <lcthw/bstrlib.h> typedef struct { char *buffer; int length; int start; int end; } RingBuffer; RingBuff...

阅读全文

练习42:栈和队列

练习42:栈和队列 原文:Exercise 42: Stacks and Queues 译者:飞龙 到现在为止,你已经知道了大多数用于构建其它数据结构的数据结构。如果你拥有一些List、DArray、Hashmap 和 Tree,你就能用他们构造出大多数其它的任何结构。你碰到的其它任何结构要么可以用它们实现,要么是它们的变体。如果不是的话,它可能是外来的数据结构,你可能不需要它。 Stack和Queue是非常简单的数据结构,它们是List的变体。它们是List的弱化或者转换形式,因为你只需要在List的一端放置元素。对于Stack,你只能能够在一段压入和弹出元素。而对于Queue,你只能够在...

阅读全文

练习39:字符串算法

练习39:字符串算法 原文:Exercise 39: String Algorithms 译者:飞龙 这个练习中,我会向你展示可能是最快的字符串搜索算法之一,并且将它与bstrlib.c中现有的binstr比较。binstr的文档说它仅仅使用了“暴力搜索”的字符串算法来寻找第一个实例。我所实现的函数使用Boyer-Moore-Horspool(BMH)算法,如果你分析理论时间的话,一般认为它会更快。你也会看到,如果我的实现没有任何缺陷,BMH的实际时间会比binstr简单的暴力搜索更糟。 这个练习的要点并不是真正解释算法本身,因为你可以直接去Boyer-Moore-Horspool 的维基百科页面去阅读它。这个...

阅读全文

练习38:哈希算法

练习38:哈希算法 原文:Exercise 38: Hashmap Algorithms 译者:飞龙 你需要在这个练习中实现下面这三个哈希函数: FNV-1a 以创造者Glenn Fowler、Phong Vo 和 Landon Curt Noll的名字命名。这个算法产生合理的数值并且相当快。 Adler-32 以Mark Adler命名。一个比较糟糕的算法,但是由来已久并且适于学习。 DJB Hash 由Dan J. Bernstein (DJB)发明的哈希算法,但是难以找到这个算法的讨论。它非常快,但是结果不是很好。 你应该看到我使用了Jenkins hash作为Hashmap数据结构的默认哈希函数,所以这个练习的重点会放在这三个新的函数上。它们的代...

阅读全文

练习37:哈希表

练习37:哈希表 原文:Exercise 37: Hashmaps 译者:飞龙 哈希表(HashMap、HashTable以及Dictionary)广泛用于许多动态编程语言来储存键值对的数据。哈希表通过在键上执行“哈希”运算产生整数,之后使用它来寻找相应的桶来获取或储存值。它是非常快速的使用数据结构,因为它适用于任何数据并且易于实现。 下面是哈希表(也叫作字典)的一个使用示例: fruit_weights = {'Apples': 10, 'Oranges': 100, 'Grapes': 1.0} for key, value in fruit_weights.items(): print key, "=", value 几乎所有现代语言都具备这种特性,所以许多人写完代...

阅读全文

练习35:排序和搜索

练习35:排序和搜索 原文:Exercise 35: Sorting And Searching 译者:飞龙 这个练习中我打算涉及到四个排序算法和一个搜索算法。排序算法是快速排序、堆排序、归并排序和基数排序。之后在你完成基数排序之后,我打算想你展示二分搜索。 然而,我是一个懒人,大多数C标准库都实现了堆排序、快速排序和归并排序算法,你可以直接使用它们: #include <lcthw/darray_algos.h> #include <stdlib.h> int DArray_qsort(DArray *array, DArray_compare cmp) { qsort(array->contents, DArray_count(array), sizeof(void *), cmp); return 0; } ...

阅读全文

练习34:动态数组

练习34:动态数组 原文:Exercise 34: Dynamic Array 译者:飞龙 动态数组是自增长的数组,它与链表有很多相同的特性。它通常占据更少的空间,跑得更快,还有一些其它的优势属性。这个练习会涉及到它的一些缺点,比如从开头移除元素会很慢,并给出解决方案(只从末尾移除)。 动态数组简单地实现为void **指针的数组,它是预分配内存的,并且指向数据。在链表中你创建了完整的结构体来储存void *value指针,但是动态数组中你只需要一个储存它们的单个数组。也就是说,你并不需要创建任何其它的指针储存上一个或下一个元素。它们可以直接索引。 我...

阅读全文