Data Structures and Algorithms in C
1.0.0
在这里，您会发现C中实现的一些数据结构和算法。这些算法主要基于Thomas H. Cormen的算法简介。
每个模块由至少一个标头文件（.h）和一个包含代码语料库（.c）的源文件组成。为了使用这些模块之一，我建议您遵循以下步骤：
/modules所需的数据结构或算法List.c ）的模块目录（例如/modules/List ）/include/ folder，查找所需的标题（.h）文件（例如List.h ）并下载。#include "foo.h" ）。大多数模块包括例如HashFunctions或Comparators甚至其他数据结构。发现所需的内容并下载所有文件。#include "foo.h" 。如果克隆整个文件夹，则可以运行：
make ：这使每个模块变得富裕make run-tests ：汇编每个模块并执行所有测试make valgind-tests ：它编译每个模块并使用Valgrind执行所有测试| 数据结构 | 定义 |
|---|---|
| 布卢姆过滤器 | Bloom Filter是一种由伯顿·霍华德·布鲁姆（Burton Howard Bloom）在1970年构思的概率数据结构，用于测试元素是否是集合的成员。误报匹配是可能的，但是假否定性不是 - 换句话说，查询返回“可能在集合中”或“绝对不在集合中”。可以将元素添加到集合中，但不能删除（尽管可以使用计数Bloom Filter变体来解决）；添加的项目越多，误报的概率就越大。 |
| 红黑树 | 红色 - 黑树是一种自我平衡的二进制搜索树。每个节点都存储一个代表“颜色”（“红色”或“黑色”）的额外位，用于确保在插入和删除过程中树保持平衡。修改树时，新树将被重新排列并“重新粉刷”以恢复着色属性，以限制在最坏情况下树的不平衡。这些属性的设计使得可以有效地进行重新安排和重新着色。重新平衡并不是完美的，但可以保证在O（logn）时间搜索，其中n是树的节点的数量。插入和删除操作以及树的重排和重新上色也在O（logn）时间进行。 |
| 链接列表 | 链接列表是数据元素的线性集合，其顺序不通过其物理位置在内存中给出。相反，每个元素指向下一个。它是一个数据结构，该数据结构由共同代表序列的节点集合组成。 |
| 队列 | 优先队列是一种抽象数据类型，类似于常规队列或堆栈数据结构，其中每个元素还具有与之相关的“优先级”。在优先级的队列中，在优先级较低的元素之前提供了高优先级的元素。 |
| 列表 | 一般实现非常简单的键和链条。没有提供重建。 |
| 用红黑树刺 | 由一张桌子组成，其中每行都有一个指向红色树的指针，我们得到了上述最佳复杂性，同时避免了太多的碰撞。 |
| 用水桶到红黑树的台面 | 标签由一桶指向红色的黑树组成 |
| 麦克什普 | 最大 - 蜂座是一个完整的二进制树，其中每个内部节点中的值大于或等于该节点的子女的值。将堆的元素映射到数组中是微不足道的：如果一个节点存储为索引K，则其左子女存储在索引2K+1中，而其右子则以index 2k+2为单位。 |
| 分离 | 分离集合数据结构（也称为Unim-Fend数据结构或合并 - 输入集）是一个数据结构，该数据结构存储了分离集合（非重叠）集的集合。同等地，它将集合的分区存储到不相交的子集中。它提供了添加新集合，合并集合（通过其工会代替）并找到一组代表成员的操作。最后一个操作允许有效找出是否有两个元素在相同或不同的集合中。 |
| 带有线程的工作调度程序 | 使用UNIX PTHREADS的多线程作业调度程序。 |
| 算法 | 定义 |
|---|---|
| heapsort | Hepsort是一种基于比较的排序算法。可以将heperort视为改进的选择：类似选择的选择，Hepsort将其输入分为一个分类和未分类的区域，并且它通过从中提取最大元素并将其插入到分类区域中，从而迭代地收缩了未分类的区域。与选择排序不同，hepsort不会浪费时间，并在未分类区域的线性时间扫描中浪费时间。相反，Heap排序在堆数据结构中维护未排序的区域，以更快地找到每个步骤中最大的元素。 |
| QuickSort | QuickSort是一种有效的排序算法。它由英国计算机科学家托尼·霍尔（Tony Hoare）于1959年开发，并于1961年出版，仍然是一种用于分类的算法。如果实现良好，它的速度可能比合并排序更快，并且比Heapsort快两到三倍。 |
| 公用事业 | 定义 |
|---|---|
| 比较器 | 比较两个值并返回0，> 0，<0的函数 |
| 哈希功能 | 字符串哈希功能 |
为了测试已创建的模块，我使用了库acutest.h 。
有关Acutest库的更多信息
创建简单程序（主要功能）作为所有模块的使用示例。
☑️与Myrto Iglezou合作制作了一些模块。 ☑️
©Konstantinos Nikoletos | 2021
