C++：鏈接表表示

我知道如何表示一個鏈表基本上創建節點類（更優選結構），並且創建實際鏈表類的方式。不過，昨天我正在尋找的倒車單鏈表操作邏輯和我遇到的解決方案，近90％的被包括的函數，返回的數據類型節點*。因此，我感到困惑，因爲如果你想要顛倒一個列表，無論你做了什麼操作，難道它不是linkedList的類型嗎？我做錯了嗎？C++：鏈接表表示

鏈表實現我做所有的時間;

#include <iostream> using namespace std; struct Node { int data; Node *next; }; class linkedList { public: Node* firstPtr; Node* lastPtr; linkedList() { firstPtr=lastPtr=NULL; } void insert(int value) { Node* newNode=new Node; newNode->data=value; if(firstPtr==NULL) firstPtr=lastPtr=newNode; else { newNode->next=firstPtr; firstPtr=newNode; } } void print() { Node *temp=firstPtr; while(temp!=NULL) { cout<<temp->data<<" "; temp=temp->next; } } };

來源

2012-04-23 Ali

您能否提供一個列表反轉的函數調用，您會發現混淆？ – Andrey 2012-04-23 08:52:15

問題的重點是不實際的** **逆轉功能，但爲什麼**的功能（如反向）**將返回值類型** **節點 – Ali 2012-04-23 08:54:44

@rolandbishop：在您的例子，'LinkedList'只是一個封裝來隱藏來自客戶端的實現細節（'Node *'），而你看到一個網絡的解決方案只關注實現簡潔。 – 2012-04-23 11:37:22

你的做法是沒有錯，但你可能會在你的linkedList類給予太多的重視。

該類實際包含什麼？一個指向第一個節點的指針和一個指向最後一個節點的指針（這是冗餘信息，因爲你可以通過只知道第一個節點來找到最後一個節點）。所以基本上linkedList只是一個輔助類，沒有額外的信息。

linkedList中的成員函數可以很容易地在Node中移動，或者免費使用以Node作爲參數的函數。

來源

2012-04-23 08:50:02

感謝您的真棒回答！所以我們創建鏈表，在內存中反轉它，然後指向它的初始節點呢？ – Ali 2012-04-23 08:53:33

@rolandbishop well ...你指向新的第一個節點。如果您顛倒了列表，這可能不是您的初始節點。 – 2012-04-23 08:54:44

我猜我的「好..」部分不能快速表達自己。我完全理解你的意思，但我要求的是，我們可以簡單地稱之爲**鏈接列表**基本上可以通過指向其初始節點的單個節點獲得，對嗎？ – Ali 2012-04-23 08:56:41

那麼，什麼是鏈接列表，但指向第一個節點的指針呢？一個列表是完全可訪問的，只要你能夠到達第一個節點，你所需要的就是指向第一個節點的指針。

除非你想存儲額外的關於列表的控制信息（例如它的長度），這個列表本身不需要單獨的數據類型。

現在一些實施方式中（如你的）可以在列表中的指針也存儲到最後一個節點爲效率，允許你爲O追加一個項目（1），而不是爲O（n）。但這是一個額外功能的列表，而不是要求的一般列表。

來源

2012-04-23 08:49:12 paxdiablo

謝謝你很有道理。所以我們只需要一個指向**點的指針**列在內存右邊的列表？ – Ali 2012-04-23 08:52:34

@rolandbishop：我假設你的意思是「......指向**清單......」，在這種情況下你是對的。這就是你需要的一切。這不一定就是你所想的，因爲如上所述，你的額外控制信息有一些優點。所以存儲的長度，因爲它使size（）'O（1）而不是O（n）。 – paxdiablo 2012-04-23 08:54:30

這些功能可能會返回Node類型的*因爲倒車鏈表後，他們將返回指向列表中的第一個節點。

來源

2012-04-23 08:52:12

C++：鏈接表表示

回答

相關問題