C++中的循环链表（在开头插入）

Question

我正在为考试复习旧题。一项任务是实现插入和打印功能，将元素插入循环列表的开头。提供了一个程序来测试学生的解决方案。

我的插入解决方案是：

void Circular_List::insert(std::string const& str)
{
    if (entry == nullptr) {
        entry = new Element(str);
        entry -> next = entry;
    }
    else {
        Element* temp = entry;
        entry = new Element(str);
        entry -> next = temp;
    }
}

我的思考过程：

它似乎有效，因为我的打印：

void Circular_List::print() const
{
    Element* temp = entry;
    while (temp -> next != temp) {
        cout << temp -> name << endl;
        temp = temp -> next; 
    }
}

以正确的顺序打印列表，但我首先添加的元素除外。我不明白为什么它不打印第一个元素。提供的程序打印出 20 次迭代。例如，如果我插入 a、b、c、d、e，程序将打印

d->c->b->a->a->a->a->a->a->a->a->a->a->a->a->a->a->a->a->a->

这看起来很不对劲，它不应该循环到列表的前面而不是只打印一个吗？

测试程序：

  int j = 0;
  for (Circular_List::Iterator i = l.begin(); i != l.end() && j < 20; ++i, ++j)
  {
    cout << *i << "->";
  }
  cout << endl;

class Iterator
  {
  public:
    Iterator(Element* e) : pos(e) {}
    ~Iterator() = default;
    Iterator(Iterator const&) = default;
    Iterator& operator=(Iterator const&) = default;
    bool operator!=(Iterator const& i) { return pos != i.pos; }
    operator bool() { return pos != nullptr; }
    Iterator& operator++() { pos = pos->next; return *this;}
    std::string operator*() { return pos->name; }
  private:
    Element* pos;
  };

我假设我的插入有误，但我不知道我做错了什么？

Answer 1

当您将第二个元素插入列表时，您的第一个元素使下一个条目指向它自己。您需要更新两个下一个字段：一个在插入的记录中，另一个在列表中以指向插入的记录。你没有做到后者。 else 子句应该是：

    Element* temp = new Element(str);
    temp->next = entry->next;
    entry->next = temp;
    entry = temp;

这使得 entry 成为指向最后一个循环元素和 entry->next - 第一个循环元素的指针；

顺便说一句，您的第二张图不正确，因为 'a'->next 应该指向 'a' 而不是入口。

C++中的循环链表（在开头插入）

Circular linked list in C++ (insert at beginning)

c++

pointers

circular-list