使用數組實現圖形

Question

我想實現一個生成圖形的工具，這些圖形的內存將在數據結構（所謂的「磁帶」）上分配。您可以將磁帶想象爲一組元素，每個元素都包含「節點ID」，鏈接到其「父節點」以及其「子節點」。

我在尋找的是一種識別陣列中的可用插槽便宜的方法，以便在添加新節點時可以快速識別空插槽。

如果我使用動態數組實現磁帶會怎麼樣？在數組大小需要調整大小的情況下，我是否可以避免將整個磁帶複製到新分配的數組中？

這裏有人有什麼想法嗎？

Answer 1

我假設你想要預先分配一個大的「磁帶」。數千個節點。

您應該結合2個概念：

• 第一店磁帶上最後一次使用的條目。下一次需要一個新的條目時，只需在最後使用的條目之後選擇一個。
• 第二保留一個自由列表。使用磁帶條目的前4個字節（或64位中的8個字節）作爲指向下一個空閒條目的指針。磁帶的開頭應指向第一個空閒條目。

每當磁帶上的條目被釋放時，將其添加到空閒列表中。

每當需要帶一個新的條目：

• 檢查是否有空閒列表元素。如果在空閒列表爲空的情況下接收到第一個條目並將其從空閒列表中刪除，請使用上次使用的條目並在其之後立即使用。

您也可以將其與重新分配方案結合使用，您可以在其中保留磁帶的總分配大小，並在最後使用的條目到達磁帶末尾時重新分配。