數據結構，我應該選擇哪一個，爲什麼

我寫定時器經理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

數據結構，我應該選擇哪一個，爲什麼

回答

相關問題