恐怕我当前对双向链表的实现无法适当地容纳迭代器。我的迭代器end()函数需要开始指向尾巴后的节点,以减少列表中的内容。当然,按照我目前设计的列表,tail-> next将为null。
我写这篇文章是为了理解我的第一个指针和尾指针是“虚拟节点”?
[我尝试制作第三个指针,但是考虑到与pushBack函数非常相似,所有东西都可以在我的doublyLinkedList类中将first和tail构造为nullptrs的情况下使用,因此我认为可以实现的实现。
我一直在尝试找出如何实现额外的虚拟节点的方法,任何解决方案都可以。
我只会显示我认为可能相关的代码部分。
struct node
{
T data;
node<T> * next;
node<T> * prev;
node() {
next = nullptr;
prev = nullptr;
};
node(T data, node<T> * next = nullptr, node<T> * prev = nullptr)
: data(data), next(next), prev(prev) {};
};
template <class T>
class LinkedList
{
private:
node<T> * first;
node<T> * tail;
int size;
public:
LinkedList();
LinkedList(const LinkedList&);
void copy(const LinkedList&);
void operator=(const LinkedList&);
//void insert_end(T dat);
void pushBack(T data);
void pushFront(T data);
void display();
void displayRev();
int getSize();
class Iterator
{
private:
node<T> * itr;
public:
Iterator(node<T> * itr = nullptr) : itr(itr){};
Iterator& operator++();
Iterator operator++(int);
Iterator& operator--();
Iterator operator--(int);
T operator*();
bool operator!=(LinkedList<T>::Iterator other);
bool operator==(LinkedList<T>::Iterator & other);
~Iterator() {}
};
/*BEGIN AND END*/
Iterator begin() { return Iterator(first); }
Iterator end(tail->next)
{
return Iterator(tail->next);
}
~LinkedList();
};
定义
template<class T>
typename LinkedList<T>::Iterator& LinkedList<T>::Iterator::operator--()
{
itr = itr->prev;
return *this;
}
template<class T>
typename LinkedList<T>::Iterator LinkedList<T>::Iterator::operator--(int)
{
auto tmp = *this;
itr = itr->prev;
return tmp;
}
//constructor
template <class T>
LinkedList<T>::LinkedList()
{
first = tail = nullptr;
size = 0;
/*node<T>* first = new node<T>;
node<T>* tail = new node<T>;
first->next = tail;
tail->prev = first;*/
}
template<class T>
void LinkedList<T>::pushBack(T data)
{
if (first == nullptr)
{
first = tail = new node<T>(data);
size++;
}
else
{
if (tail == nullptr)
{
tail = new node<T>(data);
first->next = tail;
tail->prev = first;
size++;
}
else
{
node<T> *prevTail = tail;
node<T> *newTail = new node<T>(data, nullptr, prevTail);
prevTail->next = newTail;
tail = newTail;
size++;
}
}
}
主要
#include "pch.h"
#include "LinkedList.h"
#include <iostream>
typedef LinkedList<int>::Iterator iter;
int main()
{
LinkedList<int> l1;
l1.pushBack(10);
l1.pushBack(20);
l1.pushBack(30);
for (auto itr = l1.begin(); itr != l1.end(); itr++)
{
std::cout << (*itr) << " ";
}
}
我过去三个小时来此一直无济于事,然后又回到了我开始的地方。如果有人能向我展示光明,我将不胜感激。
谢谢。
我可以看到很多简单的选项:
构造结束迭代器很困难,因为自然的方法是实例化Iterator{}
,这意味着Iterator::itr
节点指针将为空。但是,在这种情况下,减量运算符将无法实现。作为解决方案,可以删除这些操作。
template <class T>
class LinkedList
{
/* ... */
class Iterator
{
private:
node<T> * itr;
public:
Iterator(node<T> * itr = nullptr) : itr(itr){};
Iterator& operator++();
Iterator operator++(int);
T operator*();
bool operator!=(LinkedList<T>::Iterator other);
bool operator==(LinkedList<T>::Iterator & other);
};
Iterator begin() { return Iterator{first}; }
Iterator end() { return Iterator{}; }
};
prev
成员添加到迭代器我认为您可以向迭代器添加prev
指针以保留双向操作。
template <class T>
class LinkedList
{
/* ... */
class Iterator
{
private:
node<T> * current; // null if and only if this is end iterator.
node<T> * prev; // may be null (at head of list)
public:
Iterator() : current{nullptr}, prev{nullptr} {}
Iterator(node<T> * current) : current{current}, prev{current ? current->prev : nullptr} {}
Iterator(node<T> * current, node<T>* prev) : current{current}, prev{prev} {}
Iterator& operator++();
Iterator operator++(int);
Iterator& operator--(); // implemented using `prev`
Iterator operator--(int); // implemented using `prev`
T operator*();
bool operator!=(LinkedList<T>::Iterator other);
bool operator==(LinkedList<T>::Iterator & other);
};
Iterator begin() { return Iterator{first}; }
Iterator end() { return Iterator{nullptr, tail}; }
};