数据结构，我应该选择哪一个，为什么

我写定时器经理C，其中包括：数据结构，我应该选择哪一个，为什么

创造新的计时器
删除定时器
去除死皮定时器
冻结定时器
和所有其他的东西，我还没有想过。

关键是 - 内存量应尽可能小。起初我想过链接列表，但如果我删除了一些中间部分，我应该重建列表，这可能需要一些时间。典型的动态数组是相同的 - 我应该小心点指出，当我重新绑定这个结构时，不会错过其中的一些。

任何想法？

Thx for all answer

来源

2011-05-31 JosiP

这是功课？ – Nix 2011-05-31 12:54:28

那么通常它是（双重）链接列表的中间修改它的优势之一。 – jmg 2011-05-31 12:55:12

从链表中删除时不需要重建任何东西。这是一个O(1)操作。无论你选择什么样的结构，你都可能需要小心指针。

来源

2011-05-31 12:54:30 cnicutar

对于两个事实（链表和指针）都是+1 – jv42 2011-05-31 12:57:20

这是误导 - 如果您要从任一端移除，或者您已经有对该项目的引用，则它只是一个O（1）操作。如果您必须在列表中找到要删除的项目，则不是O（1）。从这个问题来看，移除定时器似乎可能发生在列表中的任何地方。 – pfhayes 2011-05-31 13:05:58

@PFHayes我假定了一个双向链表。如果你不知道如何在一个双向链表中不断移除一个元素，请问一个问题 - 我会帮你:-)。像这样描述它：“*我不知道如何从列表*中不断移除元素”。 – cnicutar 2011-05-31 13:07:11

如果内存量必须尽可能小我会去一个数组，使用数组的唯一缺点是调整数组的大小是昂贵的（大量的CPU周期），但是如果你可以设置一个使用单个数组大小达到此最大值的计时器数量的上限将是有效的。如果定时器的数量是非常动态的，则列表（矢量集合）就是要走的路。

来源

2011-05-31 12:58:34 Will

通常，一个数组使用最少的内存。单块，分配开销少，并且没有管理开销，如链接列表中的下一个/上一个指针。

当然，从一个足够大的数组的开始/中间移除比从链表中移除给定节点更省时，并且数组中的任何指针/索引将不再引用一旦你完成了相同的元素，所以你必须小心处理你给定时器API的用户以及如何找到特定句柄的定时器数据。但是，如果内存使用真的是唯一重要的问题，那么该阵列将获胜。

我以前做过类似的事情，并且亲自从链表开始，除非它明显会失败一些特定的约束。如果可以防止活动计时器列表变得太大，那么指向“timerdata”结构的指针数组也可能运行良好。

来源

2011-05-31 13:03:01

您可以使用堆/优先级队列。这与数组具有相同的内存需求，但插入和移除是O（lg n）操作。队列中的项目可以按每个计时器对象的触发时间排序。当实时定时器触发时，您必须调整列表中每个其他定时器的触发时间。因此，如果timer1设置为在1秒后关闭，并且timer2设置为在1.5秒后关闭，那么当timer1触发时，必须调整timer2在0.5秒后关闭。这样的事可能吗？

来源

2011-05-31 13:15:06 James

什么是定时器元件？这里面是什么？它是否只是一个被某个计时器中断或某个复杂类别不断计数的值，可能是用它自己的线程来计时的？

哪些操作可能最常执行？ - 优化对这些人的访问。

订购清单有什么好处，例如：以递增的到期时间顺序，使得下一个定时器超时总是在列表的开始处（即，delta-队列）。

RGDS，马丁

来源

2011-05-31 13:53:23

数据结构，我应该选择哪一个，为什么

回答

相关问题