在C++中遍历非STL链表可能吗？

Question

假设我使用的是非标准的链表类List.h.这个类正在运行,模板化,并具有添加/删除到前面和添加/删除到后面,isEmpty()等的典型功能.

此列表没有任何begin()和end()功能.此外,链表类必须包含迭代器功能吗？或者,当我创建一个新列表时,我可以自己创建这些东西吗？

我习惯使用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);
}

Answer 1

回应:

现在,我如何遍历此列表,以便找到所有这些整数的总和？这可能,或者我目前的功能是否可以阻止这种情况？我必须在List类中实现某种迭代器吗？

您需要实现一种迭代列表的方法,该方法不会(作为副作用)破坏您的列表.