通常「可展開」網格表示爲列表列表（行列表，每行有單元格列表），這些列表是某種鏈接列表。在這個數據結構中操作（移除，插入）行非常簡單且便宜，它只是重新鏈接前一個節點的問題，但是當涉及到列時，例如刪除一列，它變成了一個很長的操作，我需要'循環'所有行來刪除索引單元格。顯然這不是好行爲，至少對我來說是這樣。網格數據結構
我不是在這裏說數據庫;我發現的一個很好的例子是將一些文本文件轉換爲文本編輯器（據我所知）文本編輯器主要將行分割成行，並且很容易刪除行。我想要刪除一列與刪除某一行一樣廉價和高效。
最後，我需要的是一些多維網格，但我認爲任何2D網格都適用於MD，對嗎？
你可以有一個二維「鏈接矩陣」（我忘了正確的術語）：
... Col 3 ... Col 4 ...
| |
... --X-- ... --Y-- ...
| |
... ... ... ... ...
每個單元有四個鄰居，如圖所示。此外，您需要可能指示行/列位置的行和列標題，以及指向每行或列中的第一個單元格。這些最容易表示爲沒有上鄰居的特殊單元格（對於列標題）。
在3到4之間插入新列意味着在列3中迭代單元格X並插入新的右側鄰居Z.此新單元格Z向左連接X並向右連接到Y.您還需要添加新列標題，並垂直鏈接新單元格。然後可以重新編號4後的所有列的位置（第4列變爲第5列）。
... Col 3 Col 4 Col 5 ...
| | |
... --X-----Z-----Y-- ...
| | |
... ... ... ... ...
插入柱的費用是用於更新所述列標題O（Ñ）用於插入並連接的新的細胞，並再次O（米）。這是一個類似的刪除過程。
因爲每個單元只有四個鏈接，所以相同的算法用於行插入/刪除。
感謝您的回覆，但似乎您並不瞭解我的問題，您的答案是您已將行操作作爲列很貴！這與我所需要的相反。簡而言之，列刪除仍然非常緩慢，因爲我仍然必須遍歷所有這些單元並重新鏈接。它並不像刪除一行那樣簡單便宜。 在插入列時，該列將作爲列生成'已經'（考慮替換列）。然而，爲了簡單起見，我使用了'刪除'。 – KA1 2010-08-23 03:47:48
刪除我的方案中的列與刪除行具有相同的算法成本。如果您的行數多於列數，那麼絕對成本可能會有所不同 - 但這種成本在每個單元中仍然是線性的。我認爲除了推遲某些工作（例如，將某一列標記爲已刪除，然後在保存時批量刪除所有標記的列）之外，您可以做得比這更好。 – Edmund 2010-08-23 04:17:36
我*不*談論導航，我需要更好的結構*操縱*不用於導航。實際上'列表清單'結構對於導航來說比每個單元格增加更多指針要好得多 再次，我正在尋找更好的解決方案，以便進行有效的數據操作。謝謝。 – KA1 2010-08-23 23:48:25
保持原有的數據結構。另外，在創建每個列時給它一個唯一的ID。刪除列時，只需將其ID添加到所有刪除列標識的哈希表中即可。每當你走一行時，檢查每個元素的列id（需要與元素的所有其他數據一起存儲），如果它已被刪除，則將它與行相拼接。
如果您有每個網格元素可指向的每列數據結構，則不需要散列表和ID。那麼你只需要在該數據結構中刪除一個位。
順便說一句，埃德蒙的方案也適合你。即使需要花費O（n）時間來刪除長度爲n的行或列，您可以推測分攤該成本與創建這n個元素的成本，使得刪除O（1）攤銷時間成爲可能。
我知道「鏈接列表」通常是從理論的角度來理解，但實際上它們通常是低效的。
我會建議朝隨機存取容器移動以獲得一些速度。最簡單的是一個數組，但是根據我們正在談論的數據大小，雙端隊列或索引跳過列表/ B *樹可能會更好。 （1）（array，deque）/ O（log N）（跳過列表/ B *樹）中的給定索引的能力在概念上，它不會變化很多）操作，而不是使用簡單鏈接列表的O（N）。
然後是魔法的時候了。基斯已經暴露了基本思想：而不是實際刪除該列，只需將其標記爲已刪除，然後在您走向結構時將其標記爲「跳過」即可。然而，哈希表需要線性步行才能到達第N列。使用Fenwick樹會產生計算真實指數的有效方法，然後您可以直接跳到那裏。
請注意，將行標記爲已刪除的關鍵好處在於操作的明顯可能性爲undo。
另請注意，您可能想要構建一個壓縮函數，以消除不時刪除的列，而不是讓它們累積。
所以你想O（1）刪除行和列？ – 2010-08-23 23:13:15
是的，這就是我所問的。 – KA1 2010-08-24 02:10:55
謝謝大家，我在下面的答案中找到了非常有用的想法。 ，並不能真正推薦其中之一。所有這些都是很好的答案，需要閱讀這些問題。 – KA1 2010-08-26 20:06:54