快速列表数据结构

• 下载源代码 - 284 KB

引言

FastList 纯粹是我对数据结构的组合实现，以便拥有更强大的（可能不适用于所有情况，但适用于某些特定情况）结构。 它是一个模板类，使您能够使用双向链表的快速插入和删除属性以及数组的快速访问操作。 这样，就可以实现 O(1) 删除、O(1) 插入和 O(1) 访问时间。

背景

在许多应用程序中，我们想要的只是向动态数组添加或删除一些元素，并对这些值进行操作。 如果有一种能够在 O(1) 时间内执行所有这些操作的结构，岂不是很棒？

当我进行图像的连通分量分析时，我遇到了一个问题，需要快速的插入、删除和访问操作。 因为我不需要排序算法，所以我没有实现它，但是你可以尝试实现快速排序（我的代码有它的基础，所以我很快就会实现它）。 那将会非常棒。

算法 & 结构

本文中使用的数据结构非常简单。 双向链表保存实际数据。 数组的每个元素都保存一个指向链表中节点的指针。 当一个项目被删除时，它会从链表中删除。 fastlist 中唯一的改变是指定某个位置是空闲、已删除还是仍被占用的值。 因此，即使您删除元素，fastlist 也会不断增长，直到您解构 fastlist。 这是因为我不想执行任何重新分配，因为这会浪费时间。

Using the Code

要正确使用该代码，唯一的要求是指定最大数据量。 如果您不知道这个数量，给它一个难以获得的巨大值（或者实现动态增长，这显然不是我的目的）。 例如，在我的图像处理代码中，我正在做的是处理彩色图像，彩色图像的尺寸类似于 640x480x3。 而且，数组的值不能超过这个值。（这甚至不到 1 MB，并且您的内存始终有足够的空间来存储此类数据。）因为随着技术的发展，内存对于许多应用程序来说变得不那么严重的问题了。

这是您声明模板对象的方式

FastList<int>* ft = new FastList<int>(100);

之后，您只需要调用函数

ft->AddItem(5);
ft->AddItem(3);
ft->RemoveItem(2);

访问数组元素

ft->GetItem(2);

重要！

请注意，当您删除一个元素时，数组的大小不会变小。 因此，如果您添加一个项目并删除前一个项目，请不要费心递减索引来获取旧值。 您旧的插入值不会移动到任何地方。 无论您删除什么以及如何删除，它都保留在原来的位置。

关注点

我实现的搜索是 O(n)，这是一种经典的数组搜索。 我放置了快速排序的代码，这些代码是从维基百科上获取的。

历史

• 版本 1.0。
• 初始版本。