为什么在第一个推压头之后仍然为空

Question

我正在尝试创建单链表。在第一次推送之后，head仍然是空。为什么头在第一次推送后没有更新？

using namespace std;
typedef struct node {
    int data;        // will store information
    node *next;     // the reference to the next node
};
void push(node*,int);
void print(node*);
int main()
{
    node* head = NULL;  //empty linked list
    push(head, 2);
    if (head == NULL) {
        cout << "vrvrvr";
    }
    push(head, 3);
    push(head, 5);
    push(head, 2);
    //print(head);
    getchar();
    return 0;
}
void push(node* x, int y){
    node *temp = new node();
    if (x == NULL) { // check linked list is empty
        temp->next = x;
        temp->data = y;
        x = temp;
    }
    else {
        node *temp1 = new node();
        temp1 = x;
        while (temp1->next != NULL) { // go to the last node
            temp1 = temp1->next;
        }
        temp1->next = temp;
        temp->data = y;
        temp->next = NULL;
        delete temp1; // 'temp' node will be the last node
    }
}
void print(node* x){
    node *temp1 = new node();
    temp1 = x;
    while (temp1->next != NULL) {
        cout << temp1->data << endl;
        temp1 = temp1->next;
    }
}

Answer 1

push的主要问题是，在函数中对x所做的更改是函数的本地更改。它不会改变main中head的值。

您可以通过将参数类型更改为node*&来解决此问题。

void push(node*& x, int y) {
   ...
}

我看到的其他问题都在区块中：

else {
    node *temp1 = new node();
    temp1 = x;
    // Problem 1:
    // After this, the memory returned by the previous line is lost.
    // It is a memory leak.
    while (temp1->next != NULL) { // go to the last node
        temp1 = temp1->next;
    }
    temp1->next = temp;
    temp->data = y;
    temp->next = NULL;
    delete temp1; // 'temp' node will be the last node
    // Problem 2:
    // You are deleting a node from the linked list.
    // The linked list now has a dangling pointer.
}

您可以使用来纠正这些问题

    node *temp1 = x;
    while (temp1->next != NULL) { // go to the last node
        temp1 = temp1->next;
    }
    temp1->next = temp;
    temp->data = y;
    temp->next = NULL;
}

建议改进

1. 从node的定义中删除typedef。在您发布的代码中，它是一个悬空的typedef。此外，您可以在C++中使用不带typedef的node。

   struct node {
      int data;
      node *next;
   };
   

2. 向node添加构造函数。

   struct node {
      node(int d) : data(d), next(nullptr) {}
      int data;
      node *next;
   };
   

   这将简化push中的代码。

   void push(node*& x, int y){
      node *temp = new node(y);
      if (x == NULL) { // check linked list is empty
         x = temp;
      }
      else {
         node *temp1 = x;
         while (temp1->next != NULL) { // go to the last node
            temp1 = temp1->next;
         }
         temp1->next = temp;
      }
   }