2

我正在尝试编写一个查看值列表的方法,并确定它们是否增加或不增加

例如,对于包含 head-() (11) (8) (15) (3) 的列表,isIncreasing() 应该返回 false。但是,在处理包含 head- () (7) (9) (15) 的列表时,它会返回 true。

我发现自己对这个问题越来越感到沮丧,这真的让我很难过。如果有人可以拼凑一些代码,那将会创造奇迹。由于我想查看一组中的每个数字的情况总是会给我带来问题。

我开始写出带有签名的方法

bool List<Object>::isIncreasing() const;

从那里我不知道从哪里开始

有什么帮助吗?

万分感谢

编辑实施

#ifndef LIST_CPP
#define LIST_CPP

#include "List.h"

namespace cs20 {
template <class Object>
List<Object>::List() {
    head = new ListNode<Object>;
}

template <class Object>
List<Object>::List( const List<Object>& rhs ) {
    head = new ListNode<Object>;
    *this = rhs;
}

template <class Object>
List<Object>::~List() {
    makeEmpty();
    delete head;
}

template <class Object>
bool List<Object>::isEmpty() const {
    return( head->nextIsNull() );
}

template <class Object>
void List<Object>::makeEmpty() {
    while (!isEmpty()) {
        remove( first().retrieve() );
    }
}

template <class Object>
ListIterator<Object> List<Object>::zeroth() const {
    return( ListIterator<Object>( head ) );
}

template <class Object>
ListIterator<Object> List<Object>::first() const {
    return( ListIterator<Object>( head->getNext() ) );
}

template <class Object>
void List<Object>::insert( const Object& data,
                           const ListIterator<Object> &iter ) {
    if (iter.isValid()) {
        ListNode<Object>* newnode = new ListNode<Object>( data, iter.current->getNext() );
        iter.current->setNext( newnode );
    }
}

template <class Object>
void List<Object>::insert( const Object& data ) {
    // insert after the header node
    ListNode<Object>* newnode = new ListNode<Object>( data, head->getNext() );
    head->setNext( newnode );
}

template <class Object>
ListIterator<Object> List<Object>::findPrevious( const Object& data ) const {
    ListNode<Object>* node = head;
    while( node->getNext() != NULL && node->getNext()->getElement() != data ) {
        node = node->getNext();
    }
    if (node->getNext() == NULL) {
        node = NULL;
    }
    return ListIterator<Object>( node );
}


template <class Object>
bool List<Object>::isIncreasing() const {


    }

template <class Object>
void List<Object>::insert_back( const Object& data ) {
    ListNode<Object>* newnode = new ListNode<Object>( data, NULL );
    ListNode<Object>* lastNode = head;
    while (lastNode->getNext()!= NULL && lastNode->getNext()->getElement() != data )
        lastNode = lastNode->getNext();
    lastNode->setNext( newnode );

}

template <class Object>
void List<Object>::remove( const Object& data ) {
    ListIterator<Object> iter = findPrevious( data );
    if (iter.isValid()) {
        ListNode<Object>* node = findPrevious( data ).current;
        if (node->getNext() != NULL) {
            ListNode<Object> *oldNode = node->getNext();
            node->setNext( node->getNext()->getNext() );  // Skip oldNode
            delete oldNode;
        }
    }
}

// Deep copy of linked list
template <class Object>
const List<Object>& List<Object>::operator =( const List<Object>& rhs ) {
    if (this != &rhs) {
        makeEmpty();

        ListIterator<Object> rightiter = rhs.first( );
        ListIterator<Object> myiterator = zeroth();
        while( rightiter.isValid() ) {
            insert( rightiter.retrieve(), myiterator );
            rightiter.advance();
            myiterator.advance();
        }
    }
    return( *this );
}

}

#endif

编辑 2 下面是 isIncreasing 应该如何工作的“输出”

测试提示:

运行方法: insert( 3 ); 插入(2);插入(1);打印列表。它应该是什么样子?调用:isIncreasing(); 它应该返回什么?打印列表。它应该是什么样子?运行方法:remove(3); 删除(2);打印列表。它应该是什么样子?调用:isIncreasing(); 它应该返回什么?打印列表。它应该是什么样子?运行方法:remove(1); 运行方法: insert( 7 ); 插入(9);插入(11);打印列表。它应该是什么样子?调用:isIncreasing(); 它应该返回什么?打印列表。它应该是什么样子?

4

3 回答 3

1

像下面的伪代码怎么样

int last_value = std::numeric_limits<int>::min();

for (current_node = list_head; current_node != nullptr; current_node = current_node->next)
{
    if (current_node->value > last_value)
    {
        last_value = current_node->value;
    }
    else
    {
        return false;
    }
}

return true;
于 2013-10-22T07:47:04.097 回答
1

像这样的东西(未经测试):

template <class Object>
bool List<Object>::isIncreasing() const
{
    ListNode<Object>* node= head;
    while (node->getNext() != NULL)
    {
        // Check if the next element is smaller (or the same as )... if so return false.
        if (node->getNext()->getElement() <= node->getElement())
            return false;
        node = node->getNext();
    }
    // If we get here then all values are increasing
    return true;
}
于 2013-10-22T07:59:02.430 回答
1

另一种伪代码可能性:

node = GetHead();
while( node != End() )
{
    nodeBefore = node++;
    if( node != End() &&
        *nodeBefore >= *node )
    {
        break;
    }
}

if( Size() > 0 && node == End() )
{
    bIsAscending = true;
}
于 2013-10-22T08:03:18.940 回答