双链表以及如何将迭代器移至下一个节点 [英] Doubly linked list and how to move the iterator to the next node
本文介绍了双链表以及如何将迭代器移至下一个节点的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我必须构建一个Deque列表，并在Deque列表内部，它具有一个函数调用find，以在列表内部查找值.但是，如果该迭代器不包含我要搜索的值，我将无法尝试将迭代器移至下一个节点.她是我的查找功能的代码段:
I have to build a Deque list and inside the the Deque list, it has a function call find, to find the value inside the list. But I'm having problem to try to move the iter over to the next node if that node does not contain the value that I am searching for. Her is the snippet of my find function:
unique_ptr<DequeIterator<E>> find(E match)
{
assert(!is_empty());
bool is_found = true;
// set the pointer point to the first node from the beginning
unique_ptr<DequeIterator<E>> iter(iter_begin());
while(iter->node()->value() != match)
{
// here is I want to move the iter position
// over to the next node
iter->next();
// print out the value at the node to re-check if
// it matches
cout << iter->node()->value() << endl;
}
if(is_found)
{
cout << "found" << iter->node()->value() << endl;
}
else
cout << "no match" << endl;
return iter;
}
unique_ptr<DequeIterator<E>> iter_begin()
{
// _head is set to nullptr inside the constructor
return unique_ptr<DequeIterator<E>>(new DequeIterator<E>(_head));
}
DequeIterator类
template<class E>
class DequeIterator {
public:
// You may need to modify this class. Feel free to modify the definitions of
// these functions, or add new member functions.
DequeIterator(DNode<E>* node) {
_node = node;
}
bool at_end() {
return _node == nullptr;
}
E value() {
assert(!at_end());
return _node->value();
}
void set_value(E x) {
assert(!at_end());
_node->set_value(x);
}
void next() {
assert(!at_end());
_node = _node->next();
}
DNode<E>* node() { return _node; }
private:
DNode<E>* _node;
};
这是我的DNode类
template<class E>
class DNode {
public:
DNode(DNode<E>* prev, E value, DNode<E>* next) {
_value = value;
_prev = prev;
_next = next;
dnode_census++;
}
~DNode() {
dnode_census--;
}
// The program crashes right here
// after it goes into the E value()
E value() { return _value; }
void set_value(E value) { _value = value; }
DNode<E>* prev() { return _prev; }
void set_prev(DNode<E>* prev) { _prev = prev; }
DNode<E>* next() { return _next; }
void set_next(DNode<E>* next) { _next = next; }
private:
E _value;
DNode<E> *_prev;
DNode<E> *_next;
};
双端队列
template<class E>
class Deque {
public:
Deque()
{
_head = 0;
_size = 0;
_tail = 0;
}
~Deque() {
clear();
}
// Make the deque empty. O(n) time.
void clear() {
while (!is_empty())
erase_back();
}
// Return the current size of the deque. O(1) time.
int size() {
return _size;
}
// Return true when the deque is empty. O(1) time.
bool is_empty() {
return (size() == 0);
}
unique_ptr<DequeIterator<E>> iter_begin()
{
return unique_ptr<DequeIterator<E>>(new DequeIterator<E>(_head));
}
unique_ptr<DequeIterator<E>> iter_at(int index)
{
assert((index >= 0) && (index <= size()));
unique_ptr<DequeIterator<E>> iter(iter_begin());
for(int j = 0; j < index; j++)
iter->next();
return iter;
}
E front()
{
assert(!is_empty());
return _head->value();
}
E back()
{
assert(!is_empty());
return _tail->value();
}
void insert_after(DequeIterator<E>& iter, E x)
{
if(_size == 0)
{
insert_front(x);
}
else
{
assert(!iter.at_end());
DNode<E>* temp = new DNode<E>(iter.node(), x, iter.node()->next());
iter.node()->next()->set_next(temp);
iter.node()->next()->set_prev(temp);
}
_size++;
}
void insert_before(DequeIterator<E>& iter, E x)
{
if(_size == 0)
{
insert_front(x);
}
else
{
assert(!is_empty());
DNode<E>* temp2 = new DNode<E>(iter.node()->prev(), x, iter.node());
(iter.node()->prev())->set_next(temp2);
(iter.node()->prev())->set_prev(temp2);
}
_size++;
}
void insert_front(E x)
{
if(is_empty())
{
DNode<E>* temp = new DNode<E>(nullptr, x, nullptr);
_head = temp;
_tail = temp;
}
else
{
DNode<E>* temp = _head;
DNode<E>* temp2 = new DNode<E>(nullptr, x, temp);
_head = temp2;
}
_size++;
}
void insert_back(E x)
{
if(is_empty())
{
insert_front(x);
}
else
{
assert(!is_empty());
DNode<E>* temp = new DNode<E>(_tail, x, nullptr);
_tail = temp;
_size++;
if(_size > 1)
cout << _tail->prev()->value() << endl;
}
}
void erase(DequeIterator<E>& iter)
{
assert((!is_empty()) || !iter.at_end());
DNode<E>* temp = iter.node();
temp->next()->set_prev(temp->prev());
temp->prev()->set_next(temp->next());
delete iter.node()->next();
_size--;
}
void erase_front()
{
assert(!is_empty());
DNode<E>* temp = _head;
_head = temp->next();
delete temp;
_size--;
}
void erase_back()
{
assert(!is_empty());
DNode<E>* temp = _tail;
_tail = temp->prev();
delete temp;
_size--;
}
unique_ptr<DequeIterator<E>> find(E match)
{
assert(!is_empty());
bool is_found = true;
unique_ptr<DequeIterator<E>> iter(iter_begin());
while(iter->value() != match)
{
iter->next();
cout << iter->value() << endl;
}
if(is_found)
{
cout << "found" << iter->node()->value() << endl;
}
else
cout << "no match" << endl;
return iter;
}
// Return the element value at position index, which must be
// valid. O(n) time.
E get(int index)
{
assert((index >= 0) && (index < size()));
unique_ptr<DequeIterator<E>> iter(iter_begin());
for(int j = 0; j < index; j++)
iter->next();
return iter->node()->value();
}
void meld(Deque<E>& other)
{
}
private:
DNode<E>* _head;
DNode<E>* _tail;
int _size;
};
main.cpp
int main() {
assert_no_leak(0);
// Element objects to reuse. All upper case letters of the alphabet.
//const int N = 5;
const int N = 26;
char letters[N];
for (int i = 0; i < N; i++)
letters[i] = 'A' + i;
// Now there are a series of unit tests. Each test checks a few
// related member functions. The tests use assert(...) to look for
// bugs, so if one of these assertions fails, that indicates a bug
// in your deque code.
print_test_title("Deque constructor");
unique_ptr<Deque<char>> q(new Deque<char>());
assert_no_leak(0);
print_test_title("Deque::size");
assert(q->size() == 0);
print_test_title("Deque::is_empty");
assert(q->is_empty());
print_test_title("Deque::insert_back");
for (int i = 0; i < N; i++) {
assert(q->size() == i);
assert_no_leak(i);
q->insert_back(letters[i]);
assert(!q->is_empty());
assert(q->size() == (i+1));
assert_no_leak(i+1);
}
print_test_title("iteration");
unique_ptr<DequeIterator<char>> iter(q->iter_begin());
assert(!iter->at_end());
assert_no_leak(N);
for (int i = 0; !iter->at_end(); i++, iter->next()) {
assert(i < N);
assert(iter->value() == letters[i]);
assert_no_leak(N);
}
assert_no_leak(N);
/* for (int i = 0; i < N; i++)
cout << q->get(i) << endl;*/
print_test_title("Deque::find");
iter = q->find('A');
assert(!iter->at_end());
assert(iter->value() == 'A');
assert_no_leak(N);
**// This is where I got the unhandled exception**
iter = q->find('T');
assert(!iter->at_end());
assert(iter->value() == 'T');
assert_no_leak(N);
iter = q->find('?');
assert(iter->at_end());
assert_no_leak(N);
print_test_title("Deque::get");
for (int index = 0; index < N; index++) {
assert(q->get(index) == letters[index]);
assert_no_leak(N);
}
print_test_title("Deque::front");
assert(q->front() == 'C');
assert_no_leak(N);
print_test_title("Deque::back");
assert(q->back() == 'Z');
assert_no_leak(N);
print_test_title("Deque::erase_front");
for (int i = 0; i < N; i++) {
assert(q->front() == letters[i]);
assert(q->size() == (N-i));
assert_no_leak(N-i);
q->erase_front();
}
assert(q->is_empty());
assert_no_leak(0);
print_test_title("Deque::erase_back");
for (int i = 0; i < N; i++)
q->insert_back(letters[i]);
for (int i = 0; i < N; i++) {
assert(q->back() == letters[N-i-1]);
assert(q->size() == (N-i));
assert_no_leak(N-i);
q->erase_back();
}
assert(q->is_empty());
assert_no_leak(0);
print_test_title("Deque::insert_front");
for (int i = 0; i < N; i++) {
q->insert_front(letters[i]);
assert(q->front() == letters[i]);
assert(q->size() == (i+1));
assert_no_leak(i+1);
}
assert(q->size() == N);
assert_no_leak(N);
print_test_title("Deque::clear");
q->clear();
assert(q->is_empty());
assert_no_leak(0);
for (int size = 0; size <= N; size++) {
assert(q->is_empty());
assert_no_leak(0);
for (int i = 0; i < size; i++)
q->insert_back(letters[i]);
assert(q->size() == size);
assert_no_leak(size);
q->clear();
assert(q->is_empty());
assert_no_leak(0);
}
print_test_title("insert_after, insert_before, erase");
assert(q->is_empty());
iter = q->iter_begin(); // iter is at end of empty queue
q->insert_before(*iter, 'X');
assert(queue_equals_string(*q, "X"));
assert_no_leak(1);
iter = q->iter_begin(); // iter is at start of queue with 1 element
q->insert_after(*iter, 'O');
assert(queue_equals_string(*q, "XO"));
assert_no_leak(2);
q->insert_after(*iter, 'Z');
assert(queue_equals_string(*q, "XZO"));
assert_no_leak(3);
iter->next(); // iter is at second position (Z)
q->insert_before(*iter, 'C');
assert(queue_equals_string(*q, "XCZO"));
assert_no_leak(4);
q->insert_after(*iter, 'A');
assert(queue_equals_string(*q, "XCZAO"));
assert_no_leak(5);
iter->next(); // iter is at fourth position (A)
q->erase(*iter); // erase A
assert(queue_equals_string(*q, "XCZO"));
assert_no_leak(4);
iter = q->iter_begin(); // X
iter->next(); // C
iter->next(); // Z
q->erase(*iter); // erase Z
assert(queue_equals_string(*q, "XCO"));
assert_no_leak(3);
q->erase(*q->iter_begin()); // erase X
assert(queue_equals_string(*q, "CO"));
assert_no_leak(2);
iter = q->iter_begin(); // erase O
iter->next();
q->erase(*iter);
assert(queue_equals_string(*q, "C"));
assert_no_leak(1);
q->erase(*q->iter_begin()); // erase C
assert(queue_equals_string(*q, ""));
assert_no_leak(0);
print_test_title("Deque::splice");
assert(q->is_empty());
assert_no_leak(0);
unique_ptr<Deque<char>> q2(new Deque<char>());
assert_no_leak(0);
for (int i = 0; i < 5; i++) {
q->insert_back(letters[i]);
q2->insert_back(letters[i]);
}
assert(q->size() == 5);
assert(q2->size() == 5);
assert_no_leak(10);
q->meld(*q2);
assert(q->size() == 10);
assert(q2->is_empty());
assert_no_leak(10);
assert(queue_equals_string(*q, "ABCDEABCDE"));
if (DO_PERFORMANCE_TEST) {
print_test_title("Performance");
q->clear();
time_t start = time(nullptr);
for (int i = 0; i < BIG_N; i++) {
q->insert_front('A');
if ((i % 1000) == 0)
cout << '.';
}
time_t stop = time(nullptr);
assert(q->size() == BIG_N);
cout << endl
<< " Elapsed time to insert_front " << BIG_N << " times: "
<< (stop - start) << " seconds" << endl;
}
return 0;
}
推荐答案
您实际上并没有使用该迭代器做任何事情.整个要点就是您要更改它以指向列表中的下一项.
You're not really doing anything with that iterator. The whole point is you want to change it to point to the next item in the list.
通常，使用迭代器可以实现 operator ++ .它可能看起来像这样:
Normally with iterators you would implement operator++. It might look something like this:
template <class E>
DequeIterator<E> & DequeIterator::operator++()
{
_node = _node->next;
return *this;
}
目前尚不清楚为什么要分配迭代器并使用 unique_ptr .通常，您按值返回迭代器，并且迭代器的内部非常简单(一个或两个指针).无需在堆上分配它们.
It's not clear why you are allocating your iterators and using unique_ptr. Normally you return iterators by value, and their internals are very simple (a pointer or two). No need to allocate them on the heap.
看到迭代器代码后，看来您只是在使用错误的 next().您是在当前节点而不是迭代器上调用它:
After seeing your iterator code, it seems you're just using the wrong next(). You're calling it on the current node, rather than the iterator:
iter->node()->next(); // incorrect
iter->next(); // correct
如 WhozCraig 在评论中所建议:
此迭代器与后增量匹配之间的区别具有按值的临时副本返回值的实现可能是有保证的随便的读者.
the difference between this iterator and a post-increment matching implementation with its by-value temp-copy return may be warranted for the casual reader.
我给出的 ++ 操作是前缀运算符，这意味着您需要执行 ++ * iter .如果要执行(* iter)++ ，则需要后缀运算符:
The ++ operation I gave was the prefix operator, meaning you need to do ++*iter. If you want to do (*iter)++, you need a postfix operator:
template <class E> DequeIterator<E> DequeIterator::operator++(int) {
DequeIterator<E> temp(*this);
_node = _node->next;
return temp;
}
由于列表是双向链接，因此您可能希望提供适当的-前缀和后缀运算符.
And since your list is double-linked, you might like to provide the appropriate -- prefix and postfix operators.
这篇关于双链表以及如何将迭代器移至下一个节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
