移动链表中的第一项以结束 C++

Question

我需要将链表中的第一项移动到链表的末尾。我的问题是我要进入无限循环。当我消除无限循环的原因时（tail -> link != NULL；在 for 循环中），我遇到了段错误。因此，正在寻找有关如何使此代码正常工作的想法。

#include <iostream>
#include <string>
using namespace std;

struct Node
{
  string data;
  Node *link;
};

class Lilist
{
  public:
    Lilist() {head = NULL;}
    void add(string item);
    void show();
    void move_front_to_back();
    Node* search(string target);

  private:
    Node *head;
};

int main()
{
  Lilist L1, L2;
  string target;

  L1.add("Charlie"); //add puts a name at the end of the list
  L1.add("Lisa");
  L1.add("Drew");
  L1.add("Derrick");
  L1.add("AJ");
  L1.add("Bojian");

  cout << "Now showing list One:\n";
  L1.show(); // displays the list (This function displayed the list properly)
  cout << "\n";

  L1.move_front_to_back();
  L1.move_front_to_back();
  L1.show();
  cout << "\n";

  return(0);
}


void Lilist::add(string item)
{
  Node *temp;
  if(head == NULL)
  {
    head = new Node;
    head -> data = item;
    head -> link = NULL;
  }
  else
  {
    for(temp = head; temp -> link != NULL; temp = temp -> link)
        ;
    temp -> link = new Node;
    temp = temp -> link;
    temp -> data = item;
    temp -> link = NULL;
  }
}

void Lilist::show()
{
  for(Node *temp = head; temp != NULL; temp = temp -> link)
    std::cout << temp -> data << " ";
}

void Lilist::move_front_to_back()
{
  Node *temp;
  Node *tail;

  temp = head;

  for(tail = head; tail != NULL; tail = tail -> link)
    ;

  head = head -> link;
  tail -> link = temp;
  temp -> link = NULL;
}

Answer 1

问题在于您如何计算 tail。请注意这一点（为简洁起见省略了不相关的行）：

for(tail = head; tail != NULL; tail = tail -> link)
  ;
tail -> link = temp;

请注意，for 循环只会在 tail 为 NULL 时终止。然后，您取消引用 tail ... 这是 null.

所以改变for循环条件：

for (tail = head; tail->link != NULL; tail = tail->link)
  ;

这将找到列表中的最后一个元素，而不是从末尾流出。

[Live example]

Answer 2

Angew 已经解释了您的原始代码失败的原因。我会建议另一种方法 - 给 Lilist 一个 tail 成员，该成员与其 head 成员一起管理。这样你就不必在需要的时候去寻找 tail，你总是知道哪个 Node 是当前的 tail，例如：

#include <iostream>
#include <string>

using namespace std;

struct Node
{
    string data;
    Node *next;

    Node(string s);
};

class Lilist
{
public:
    Lilist();
    ~Lilist();
    void add(string item);
    void show();
    void move_front_to_back();
    Node* search(string target);

private:
    Node *head;
    Node *tail;
};

Node::Node(string s)
    : data(s), next(NULL)
{
}

Lilist::Lilist()
    : head(NULL), tail(NULL)
{
}

Lilist::~Lilist()
{
    for(Node *temp = head; temp != NULL; temp = temp->next)
        delete temp;
}

void Lilist::add(string item)
{
    Node *temp = new Node(item);

    if (head == NULL)
        head = temp;

    if (tail != NULL)
        tail->next = temp;

    tail = temp;
}

void Lilist::show()
{
    for(Node *temp = head; temp != NULL; temp = temp->next)
        cout << temp->data << " ";
}

void Lilist::move_front_to_back()
{
    if (head == tail)
        return;

    Node *temp = head;

    head = temp->next;
    temp->next = NULL;

    tail->next = temp;
    tail = temp;
}

Node* Lilist::search(string target)
{
    for(Node *temp = head; temp != NULL; temp = temp->next)
    {
        if (temp->data == target)
            return temp;
    }
    return NULL;
}

移动链表中的第一项以结束 C++

Moving first item in linked list to end C++

c++

linked-list