Python中的鏈接矩陣實現？

我知道在一個鏈表中有一個頭節點和一個尾節點。那麼，對於我的數據結構分配，我們假設創建一個鏈接的矩陣，引用一個北，南，東，西節點。我對如何實現這一點感到喪失。困擾我的一個持續性問題是頭節點和尾節點。用戶輸入行數和列數。我應該在每行開始時有多個頭節點，並且在每行末尾有多個尾節點？如果是這樣，我應該將多個頭/尾節點存儲在一個列表中嗎？Python中的鏈接矩陣實現？

謝謝。

來源

2013-10-07 Ansdai

一個好的方法是從許多二維數據結構中實現一維數據結構 - 也就是通過容器_容器。在這種情況下，它將是鏈接列表的鏈接列表。根據您如何實現1-D鏈接列表的確切細節，這可能只需要保持對每個子鏈接列表頭節點的引用。（因爲，例如，每個列表的最後一個節點返回到它的頭節點）。 – martineau

嗨，謝謝你的評論！我還在考慮另一種方法，其中包括實際製作包含節點本身的矩陣，然後使用try /除了查看矩陣中的每個節點是否包含鄰居，並且如果是，則相應地引用它。但是，使用這樣的矩陣會破壞鏈表的目的，所以也許我可以將它用作腳手架。之後，我會以某種方式從矩陣中提取節點並將其轉換爲鏈接列表，但那是我丟失的地方。感謝您的時間，我是CS的初學者，非常感謝您提供進一步的建議。 – Ansdai

矩陣只是一個數組（或列表的列表）的數組。主要區別在於所有元素總是存在，因此隨機訪問將會快速而緊湊。鏈接列表不會成爲大多數人的首選，除非涉及大量的元素並且矩陣通常只是部分滿。 – martineau

有解釋此的方法不止一種，而是一種選擇是：

有一個單一的「頭」，在左上角的右下節點和一個「尾巴」節點。然後會有行頭，行尾，列頭和列尾節點，但這些都可以從整個頭部和尾部訪問，所以你不需要跟蹤它們，它們是已經是鏈接矩陣的一部分，所以它們不需要成爲單獨鏈表的一部分。

（當然，一個是建立了零將可能有較當前行的頭/尾的局部變量的RXC矩陣，但是這不是問題的功能。）

來源

2013-10-07 21:25:33 abarnert

這真的取決於你想要什麼選項/需要有效支持。例如，只有一個頭指針的單鏈表可以是一個堆棧（在頭部插入和刪除）。如果你添加尾指針，你可以在任何一端插入，但只能在頭部（堆棧或隊列）移除。雙向鏈表可以支持在任一端插入或刪除（deque）。如果您嘗試實施一項操作，即您的數據結構不是爲您設計的，則會招致O（N）處罰。

因此，我將從一個指向（0,0）元素的指針開始，然後開始處理您的指導員要求的操作。你可能會發現你需要額外的指針，你可能不需要。我的猜測是你會用單頭指針來罰款。

來源

2013-10-08 00:20:31

Python中的鏈接矩陣實現？

回答

相關問題