链接列表插入在 for/while 循环中不起作用

Question

我正在学习DSA，正在尝试实现链表，但是我写的插入函数不是在 for 或 while 循环中工作，当我在循环外调用该函数时，它是不一样的，它是这样工作的。我无法弄清楚，请有人帮助我。

#include <iostream>

class Node {

public:
  int data;
  Node *next;

  Node(int &num) {
    this->data = num;
    next = NULL;
  }
};

class LinkedList {

  Node *head = NULL;

public:
  void insert(int num) {
    Node *tmp;
    if (head == NULL) {
      head = new Node(num);
      tmp = head;
    } else {
      tmp->next = new Node(num);
      tmp = tmp->next;
    }
  }

  void printList() {
    Node *tmp = head;
    while (tmp) {
      std::cout << tmp->data << "  ";
      tmp = tmp->next;
    }
    std::cout << std::endl;
  }

  void reverseList() {
    Node *curr = head, *prev = NULL, *nextNode;
    while (curr) {
      nextNode = curr->next;
      curr->next = prev;
      prev = curr;
      curr = nextNode;
    }
    head = prev;
  }
};

int main() {
  LinkedList list1;
  // This is not working
  int num;
  while (num != -1) {
    std::cin >> num;
    list1.insert(num);
  }

  // This is working
  // list1.insert(1);
  // list1.insert(2);
  // list1.insert(3);
  // list1.insert(4);
  // list1.insert(5);

  list1.printList();
  list1.reverseList();
  list1.printList();

  return 0;
}

I expect this after insertion

编辑：尽管@Roberto Montalti 为我解决了这个问题，但在此之前我尝试使用有效的 for 循环传递递增值，但是一旦我将 cin 拉出它就会崩溃。有人可以告诉我引擎盖下发生了什么吗？

for (int i = 1; i <= 10; i++)
{
    list1.insert(i);
}

Answer 1

当插入第 n 个项目（排除第一个）时 tmp 是一个空指针，我不明白你在那里做什么，你正在分配一些内存的 next 然后你让那个指针指向另一个位置，丢失了您之前分配的下一个指针，如果您想要最佳插入，您必须跟踪最后一个项目。这样你只分配给一些 *tmp 然后超出范围会丢失你所有的数据......最好的方法是只保留指向最后插入的项目的指针，不需要使用 *tmp.

class LinkedList
{
   Node *head = NULL;
   Node *tail = NULL;

public:
    void insert(int num)
    {
        if (head == NULL)
        {
            head = new Node(num);
            tail = head;
        }
        else
        {
            tail->next = new Node(num);
            tail = tail->next;
        }
    }
...
}

Answer 2

您需要循环直到到达列表的末尾，然后在之后添加新节点。像这样。

void insert(int num) {
    Node *tmp = head;
    if (head == NULL) {
        head = new Node(num);
    }
    else {
        while (tmp->next != NULL) {
            tmp = tmp->next;
        }
        tmp->next = new Node(num);
    }
  }

Answer 3

首先你需要为列表的尾部和头部分别定义一个节点，如下所示

Node *h;
Node *t;

你也可以将 Node 与 LinkedList 分开 class 这样你就可以轻松修改

class Node{
public:
    int data;
    Node *next;
    Node(int data, Node* next);
    ~Node();
};
Node::Node(int data, Node* next)
{
    this->data= data;
    this->next= next;
}
Node::~Node(){}
}

之后您可以尝试将这些函数添加到您的 LinkedList class 所以它可以处理其他特殊情况，例如空列表或完整列表等。

void addToHead(int data){
Node *x = new Node(data,h);
    h=x;
    if(t==NULL){
        t=x;
    }


void addToTail(int data){
Node *x = new Node(data,NULL);
    if(isEmpty()){
        h=t=x;
    }
    else
    {
        t->next=x;
        t=x;
    }
}

现在在实现节点 class 和其他功能后尝试插入功能，

void insert(int v){
if(h==nullptr){addToHead(v); return;}
if(h->data>=v) {addToHead(v);return;}
if(t->data<=v) {addToTail(v); return;}
// In this case there is at least two nodes
Node *k=h->next;
Node *p=h;

while(k != nullptr){
if(k->data >v){
Node *z =new Node(v,k);
p->next=z;
return;
}
p=k;
k=k->next;
}

}

实现所有这些的想法是，当它遍历链接列表中的元素时不会丢失指针，因此您不会以运行时间错误结束。

希望对你有用。

Answer 4

您的插入函数有问题。在此处阅读有关分段错误的信息 https://www.geeksforgeeks.org/core-dump-segmentation-fault-c-cpp/#:~:text=Core%20Dump%2FSegmentation%20fault%20is,is%20known%20as%20core%20dump。

您可以使用这个

作为快速解决方法

using namespace std;
#include <iostream>
    class Node
    {
    public:
        int data;
        Node *next;
        Node(int num)
        {
            this->data = num;
            next = NULL;
        }
    };
    
    class LinkedList
    {
    Node *head = NULL;
    
    public:
        void insert(int num)
        {
            Node *tmp= new Node(num);
            tmp->next=head;
            head=tmp;
        }
        void printList()
        {
            Node *tmp = head;
            while (tmp)
            {
                std::cout << tmp->data << "  ";
                tmp = tmp->next;
            }
            std::cout << std::endl;
        }
        void reverseList()
        {
            Node *curr = head, *prev = NULL, *nextNode;
            while (curr)
            {
                nextNode = curr->next;
                curr->next = prev;
                prev = curr;
                curr = nextNode;
            }
            head = prev;
        }
    };
    
    int main()
    {
        LinkedList list1;
        // This is not working
        int num,i=0,n;
        cout<<"Type the value of n";
        cin>>n;
        while (i<n)
        {
            cin >> num;
            cout<<num<<" "<<&num<<endl;
            list1.insert(num);
            i++;
        }

    
        list1.printList();
        list1.reverseList();
        list1.printList();
    
        return 0;
    }

链接列表插入在 for/while 循环中不起作用

Linked List insertion isn't working in for/while loop

c++

oop

linked-list