鏈表C++，問題自學習

Question

 #include <iostream> 
    using namespace std; 



    struct Node 
    { 
     int item; // storage for the node's item 
     Node* next; // pointer to the next node 
    }; 

    Node* addNode(Node*& head, int data , int& count) 
{ 
    Node * q;  // new node 
    q = new Node; // allocate memory for the new mode 
    q->item = data; // inserting data for the new node 
    q->next = head; // point to previous node ?? how would i do that? (am i doing it correctly?) 
    count++; // keep track of number of node 
    head = q; 
    return q; 
} 



    int main() 
    { 
     int a, count=0; 
     int data; 
     bool repeat; 
     Node *head= NULL; 
     //^^ assuming thats creating the first node ^^ 
     do 
     { 
     cout << "please enter the data for the next node" <<endl; 
     cin >> data; 
     addNode(head, data, count); 
     cout << "do you wish to enter another node? (enter true or false)" << endl; 
     cin >>repeat; 
     } 
     while (repeat == true); 


     // assuming this is the print function 
      while(head != NULL) 
     { 
      cout << "output" << temp->item << endl; 
      cout << temp->next << endl; 
     } 

     system("pause"); 
     return 0; 
    } 

好，我試圖在列表中添加新元素我怎麼會左右移動頭部像一個LIFO內存（棧），所以最後一個元素是在最頂端..

任何幫助將不勝感激！指針和節點最近都在和我的大腦搞混......

Answer 1

因爲我不知道所有的答案完全回答是，這裏有一個鏈表實現（書面無testig：

// your (correct) structure 
struct Node 
{ 
    float item; // storage for the node's item 
    Node* next; // pointer to the next node 
}; 

現在，我們需要兩個指針某處名單照顧：

/* some pointers */ 
struct List 
{ 
    Node* head; 
    Node* tail; 
}; 

現在我們需要創建一些元素。正如其他人所說，你可以做到這一點與新：

/* create some elements we want to link in */ 
Node* elem1 = new Node(); 
Node* elem2 = new Node(); 
Node* elem3 = new Node(); 
/* maybe even set their properties! */ 
elem1->item = 3.14; 
elem2->item = 3.14; 
elem3->item = 3.14; 

通知我怎麼沒嘗試將這些元素添加到列表中了嗎？那是因爲我有一記功能，看起來像這樣：

void addtolist(List &list, Node* node) 
{ 
    /* if no head, initialise the list */ 
    if (list->head == NULL) 
    { 
     list->head = node; 
     list->tail = node; 
    } 
    else if (list->head != NULL && list->tail != NULL) 
    { 
     /* access the tail element and set its 
      next to this ptr. 
      Move tail to this node */ 
     list->tail->next = node; 
     list->tail = node; 
    } 
    else 
    { 
     /* probably raise an exception! */ 
    } 
} 

您可以通過執行此稱之爲：

List l; 
addtolist(l, elem1); /* etc */ 

刪除元素是較爲棘手的，因爲你必須去那個元素，記住它的前一個元素，抓住它的下一個元素，加入它們並刪除你所在的Node *。

現在爲遍歷列表...您的術語HEAD|TAIL讓我想起了Erlang和尾遞歸，其中當前元素被稱爲頭部，其餘部分被稱爲尾部。如果我寫：

Node* cur = l.head; 
while (cur != NULL) 
{ 
    // do something with cur.item ? 
    cur = cur->next; 
} 

您可以看到發生這種情況。用List結構代替cur與head在這裏將是無害的。

最後，我在這裏用了一個很類似C的方法，但有範圍的模板：

template<typename T> 
struct node 
{ 
    T item; // storage for the node's item 
    Node<T>* next; // pointer to the next node 
}; 

和封裝List結構爲一類：

template<typename T> 
class List 
{ 
protected: 
    Node<T>* head; 
    Node<T>* tail; 
public: 

    void addtolist(Node<T>* node); 
    Node<T>* gethead(); 
    Node<T>* gettail(); 
} 

這使你稍微接近std::list。

Answer 2

temp是一個未初始化的指針。所以 -

temp-> item = a; // temp is not initialized or pointing to a memory location 
        // that has Node object to use operator -> 

首先，temp需要對其進行分配使用new內存位置。

temp = new Node; 
temp -> item = a; 

現在把它分配給head。同樣爲while循環中的子節點分配內存。在程序終止之前使用delete返回從子項到頭的所有資源。

Answer 3

你似乎在這裏有一些誤解：

你的「頭」是列表的開始。這始終是一個開始。

你 add 通過將元素分配給最後一個節點的next指針，將元素附加到鏈接列表。

第三，你沒有分配任何東西。

Node *head= new Node(); 
Node *temp = new Node(); 
cout<<"enter something into data"<<endl; 
cin >> a ; 
temp->item = a; 
head->next = temp; 

現在......添加下一個東西，您需要跟蹤最後一個節點（尾部），或遍歷列表以查找最後一個節點。

Node *nextNode = new Node(); 
nextNode->item = 0.0; 
Node *i; 
for (i = head; i->next != null; i = i->next); 
i->next = nextNode; 

這是O（n）執行時間。通過保持尾部的軌道，你讓它O（1）：

Node *head= new Node(); 
Node *tail = head; 
Node *temp = new Node(); 
cout<<"enter something into data"<<endl; 
cin >> a ; 
temp->item = a; 
tail->next = temp; 
tail = temp; 

Node *nextNode = new Node(); 
nextNode->item = 0.0; 
tail->next = nextNode; 
tail = nextNode; 

編輯：正如指出的那樣，如果你要預先考慮到列表中，您可以：

temp->next = head; 
head = temp; 

Answer 4

此外筆記您在

temp-> item = a; 

做從int到float隱式轉換爲a是int，而temp->item是double。

解決你的問題：你想訪問temp之前分配一個新的結構，從而

temp = new Node();