FaGe's Blog

吹啊吹啊。

标签:飞龙

共 20 篇文章

练习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...

阅读全文

练习41:将 Cachegrind 和 Callgrind 用于性能调优

练习41:将 Cachegrind 和 Callgrind 用于性能调优 原文:Exercise 41: Using Cachegrind And Callgrind For Performance Tuning 译者:飞龙 这个练习中,我打算上一节速成课,内容是使用Valgrind的两个工具callgrind和cachegrind。这两个工具会分析你程序的执行,并且告诉你哪一部分运行缓慢。这些结果非常精确,因为Valgrind的工作方式有助于你解决一些问题,比如执行过多的代码行,热点,内容访问问题,甚至是CPU的缓存未命中。 为了做这个练习,我打算使用bstree_tests单元测试,你之前用于寻找能提升算法的地方。你需要确保你这些程序的版本...

阅读全文

练习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数据结构的默认哈希函数,所以这个练习的重点会放在这三个新的函数上。它们的代...

阅读全文

练习36:更安全的字符串

练习36:更安全的字符串 原文:Exercise 36: Safer Strings 译者:飞龙 我已经在练习26中,构建devpkg的时候介绍了Better String库。这个练习让你从现在开始熟悉bstring库,并且明白C风格字符串为什么十分糟糕。之后你需要修改liblcthw的代码来使用bstring。 为什么C风格字符串十分糟糕 当人们谈论C的问题时,“字符串”的概念永远是首要缺陷之一。你已经用过它们,并且我也谈论过它们的种种缺陷,但是对为什么C字符串拥有缺陷,以及为什么一直是这样没有明确的解释。我会试着现在做出解释,部分原因是C风格字符串经过数十年的使用,有足够的证据...

阅读全文

练习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; } ...

阅读全文

练习33:链表算法

练习33:链表算法 原文:Exercise 33: Linked List Algorithms 译者:飞龙 我将想你介绍涉及到排序的两个算法,你可以用它们操作链表。我首先要警告你,如果你打算对数据排序,不要使用链表,它们对于排序十分麻烦,并且有更好的数据结构作为替代。我向你介绍这两种算法只是因为它们难以在链表上完成,并且让你思考如何高效操作它们。 为了编写这本书,我打算将算法放在两个不同的文件中,list_algos.h和list_algos.c,之后在list_algos_test.c中编写测试。现在你要按照我的结构,因为它足以把事情做好,但是如果你使用其它的库要记住这并不是通用...

阅读全文

练习32:双向链表

练习32:双向链表 原文:Exercise 32: Double Linked Lists 译者:飞龙 这本书的目的是教给你计算机实际上如何工作,这也包括多种数据结构和算法函数。计算机自己其实并没有太大用处。为了让它们做一些有用的事情,你需要构建数据,之后在这些结构上组织处理。其它编程语言带有实现所有这些结构的库,或者带有直接的语法来创建它们。C需要你手动实现所有数据结构,这使它成为最“完美”的语言,让你知道它们的工作原理。 我的目标是交给你这些数据结构,以及相关算法的知识,来帮助你完成下面这三件事: 理解Python、Ruby或JavaScript的data = {"...

阅读全文

练习31:代码调试

练习31:代码调试 原文:Exercise 31: Debugging Code 译者:飞龙 我已经教给你一些关于我的强大的调试宏的技巧,并且你已经开始用它们了。当我调试代码时,我使用debug()宏,分析发生了什么以及跟踪问题。在这个练习中我打算教给你一些使用gdb的技巧,用于监视一个不会退出的简单程序。你会学到如何使用gdb附加到运行中的进程,并挂起它来观察发生了什么。在此之后我会给你一些用于gdb的小提示和小技巧。 调试输出、GDB或Valgrind 我主要按照一种“科学方法”的方式来调试,我会提出可能的所有原因,之后排除它们或证明它们导致了缺陷。许多程序...

阅读全文