在C++中遍历非STL的链表，是否可行？

Question

假设我正在使用一个非标准的链表类List.h。这个类是模板化的，具有向前/向后添加和删除、isEmpty()等典型功能。但是这个列表没有任何begin()和end()功能。另外，链表类必须包括迭代器功能吗？还是当我创建一个新的List时可以自己创建迭代器功能？我习惯于使用STL，所以我通常会使用以下代码：

typedef vector<OBJECT>::iterator QuoteIt;
for(QuoteIt i = deposits.begin(); i != deposits.end(); ++i)

无论如何，假设我创建了一个新的“列表”。

List<int>deposits;

甚至可以是对象列表。

List<OBJECT>deposits;

那么假设我使用addToBack()方法添加了20个不同的整数，这将创建相应数量的新节点。

现在，我该如何遍历这个列表以找到所有这些整数的总和？是否有可能实现这一点，或者我的当前功能会阻止这样做？我需要向我的List类中实现某种迭代器吗？

我知道可以保留一个外部变量，每次调用addToBack()时跟踪我的总和。然而，我希望代码也能兼容节点对象列表（我想最终能够搜索节点中的一个值，并检索同一节点中的另一个值）。

我习惯于使用stl::list并创建具有迭代器的for循环，但我真的不知道如何使其与其他类配合工作。

另外，这是List()的代码：

template<class NODETYPE>
class List{

public:
List();
~List();
void insertAtFront(const NODETYPE &);
void insertAtBack(const NODETYPE  &);
bool removeFromFront( NODETYPE &);
bool removeFromBack( NODETYPE &);
bool isEmpty() const;

private:
ListNode< NODETYPE > *firstPtr; //pointer to first node
ListNode< NODETYPE > *lastPtr;
//Function to allocate a new node
ListNode< NODETYPE > *getNewNode ( const NODETYPE &);

};
//default constructor
template <class NODETYPE>
List< NODETYPE > ::List()
:  firstPtr(0),
   lastPtr(0)
{
cout<<"Creating Nodes! \n\n!"<<endl;
}
//deconstructor
template <class NODETYPE>
List<NODETYPE>::~List(){
    if(!isEmpty() ){
        cout<<"Destroying nodes!"<<endl;
        ListNode<NODETYPE> *currentPtr=firstPtr;
        ListNode<NODETYPE> *tempPtr;

        while( currentPtr !=0){
            tempPtr = currentPtr;
            currentPtr=currentPtr->nextPtr;
            delete tempPtr;
        }
    }
cout<<"All nodes destroyed! \n\n";
}

template <class NODETYPE>
bool List <NODETYPE>::removeFromFront( NODETYPE & value){
if ( isEmpty() )
    return false;
else{
    ListNode<NODETYPE> *tempPtr = firstPtr;

    if (firstPtr== lastPtr)
        firstPtr=lastPtr = 0;
    else
        firstPtr=firstPtr->nextPtr;

    value = tempPtr->data;
    delete tempPtr;

    return true;
}    
}     
template <class NODETYPE>
bool List<NODETYPE>::removeFromBack(NODETYPE &value)
{
    if (isEmpty())
        return false;
    else{
        ListNode< NODETYPE> *tempPtr = lastPtr;
        if( firstPtr == lastPtr)
            firstPtr = lastPtr = 0;
        else{
            ListNode<NODETYPE> *currentPtr=firstPtr;

            //Finds second to last element
            while(currentPtr->nextPtr !=lastPtr)
                currentPtr=currentPtr->nextPtr;

            lastPtr = currentPtr;
            currentPtr->nextPtr=0;
        }

        value = tempPtr->data;
        delete tempPtr;

        return true;
    }
}

//Checks to see if list is empty
template< class NODETYPE>
bool List< NODETYPE >::isEmpty() const{
return firstPtr == 0;
}
//returns a pointer to newly created Node
template<class NODETYPE>
ListNode<NODETYPE> *List<NODETYPE>::getNewNode(const NODETYPE &value){
return new ListNode<NODETYPE>(value);
}

- Staypuft

---

我有什么遗漏吗？在填满列表后，你怎么可能对其中一个列表进行任何操作（除了调用isEmpty()）？肯定有一些访问列表条目的方法。 - Troubadour

@Troubadour：removeFromFront和removeFromBack分别返回列表的顶部和底部。可以将此集合用作堆栈或队列（其中不允许查看）。 - Bill Lynch

Answer 1

回复：

现在，我该如何遍历这个列表，以便找到所有这些整数的总和？这可能吗，还是我的当前功能会阻止它？我需要对我的List类实现某种迭代器吗？

你需要实现一种遍历列表的方法，不会（作为副作用）销毁你的列表。

- Bill Lynch

Answer 2

回答：

现在，我该如何遍历此列表以使我能够找到所有这些整数的总和？ 是否可能，或者我的当前功能会阻止它？ 我需要向我的List Class实现某种迭代器吗？

无论你如何设计链表，你必须有某种指针指向列表的开头，并且你必须有一种知道何时到达结尾的方法（例如，“next”为null时，或者通过指针指向结尾）。通过一种方式或另一种方式公开那些数据，您始终可以设置列表遍历：

1. 从开头开始。（在您的情况下，获取firstPtr。）
2. 如果您没有到达结尾，请移动到下一个元素。（在您的情况下，获取->nextPtr。）

使用该模式在访问每个元素时累加值，您应该能够轻松处理您的任务。

如果您的列表不提供对其开头的公共访问，则肯定不是通用列表！

- Kerrek SB

---

私有的：ListNode<NODETYPE>* firstPtr; 一个简单的更改到public:也许就是我需要的...嗯。 - Staypuft

Answer 3

你可以采用多种方式来处理这个问题。你可以选择创建自己的迭代器，也可以公共访问列表头。

选择Option 1与stl列表兼容，因此你可能想走这条路。迭代器本质上是一个指针，它覆盖了增加和减少运算符，以便在列表中前进到下一个或上一个位置。

如果你学过基本的数据结构，那么遍历列表就是微不足道的事情。

Node<type> t = head;
while (t != NULL)
{
   // process node here
   t = t->next;
}

代码的不同可能取决于是否使用了虚拟节点。

- Sophy Pal

Answer 4

由于没有仅获取节点而不将其从列表中删除的功能，因此您无法简单地创建“附加”迭代器而不更改List类。最少需要做的是：

• 使外部的ListIterator类成为友元
• 使begin和end函数成为自由函数
• 向List类添加begin和end函数

如果这三个都没有，您将无法实现所需功能。

- Xeo

Answer 5

你的列表似乎有两种迭代方式（正向和反向）

List<int>deposits;
.. add stuff:

int o;
int sum = 0;
while(deposits.removeFromFront(o)) {
  sum+=o;
}

不好的一点是，如果你迭代它，你也会破坏这个列表， 你可以为List::firstPtr和ListNode::nextPtr提供公共访问器，在这种情况下，你可以这样做：

List<int>deposits;
.. add stuff:


int sum = 0;

for(ListNode<int> *ptr = deposits.firstPtr; ptr ; ptr = ptr->nextPtr) 
  sum+=ptr->data;

然而，如果可以的话，请使用现有的STL容器。

- nos