寫bool表達式來判斷一個列表是否正在增加

我有下面給出的程序，我能夠完成賦值到某個點，除了添加一個菜單選項，如果給定的列表正在增加或減少例如，對於包含head-（）（11）（8）（15）（3）的列表，isIncreasing（）應該返回false。但是，在包含head-（）（7）（9）（15）的列表上工作時，它將返回true。寫bool表達式來判斷一個列表是否正在增加

我怎麼會看名單，並告訴該程序來比較值，並做出此決定

分配告訴我們，這個新的操作應該有簽名：

布爾列表::需求增強（）const;

LIST.H

#ifndef LIST_H 
#define LIST_H 
#include <iostream> 
#include "ListNode.h" 
#include "ListIterator.h" 

namespace cs20 { 

template <class Object> 
class List { 
public: 
    List(); 
    List(const List& rhs); 
    ~List(); 

    bool isEmpty() const; 
    void makeEmpty(); 
    ListIterator<Object> zeroth() const; 
    ListIterator<Object> first() const; 
    void insert(const Object& data, 
       const ListIterator<Object> &iter); 
    void insert(const Object& data); 
    ListIterator<Object> findPrevious(const Object& data) const; 
    void remove(const Object& data); 

    const List& operator =(const List& rhs); 
private: 
    ListNode<Object> * head; 

}; 

} 
#endif

LIST.CPP

#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> 
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

實現 LISTMENU.CPP

// Menu.cpp：定義控制檯應用程序的入口點。 //

#include <iostream> 
#include "List.h" 
#include "ListNode.h" 
#include "ListIterator.h" 
#include "List.cpp" 
#include "ListNode.cpp" 
#include "ListIterator.cpp" 

using namespace std; 
using namespace cs20; 

enum CHOICE {MAKEEMPTY, REMOVE, ISEMPTY, FINDPREVIOUS, INSERT, QUIT, PRINT }; 

CHOICE menu(); 
void printList(const List<int>& l); 

int main(int argc, char* argv[]) { 
    int value; 
    List<int> list; 
    ListIterator<int> iter; 

    CHOICE choice; 
    do { 
     choice = menu(); 
     switch(choice) { 
     case MAKEEMPTY: 
      list.makeEmpty(); 
      break; 
     case ISEMPTY: 
      if (list.isEmpty()) { 
       cout << "list is empty" << endl; 
      } 
      else { 
       cout << "list is not empty" << endl; 
      } 
      break; 
     case REMOVE: 
      cout << "Please provide int to remove: "; 
      cin >> value; 
      list.remove(value); 
      break; 
     case INSERT: 
      cout << "Please provide int to insert: "; 
      cin >> value; 
      list.insert(value); 
      break; 
     case FINDPREVIOUS: 
      cout << "Please provide int to find: "; 
      cin >> value; 
      iter = list.findPrevious(value); 
      if (iter.isValid()) { 
       cout << "previous element = " << iter.retrieve() << endl; 
      } 
      else { 
       cout << "data element was not found!" << endl; 
      } 
      break; 
     case PRINT: 
      printList(list); 
      break; 
     case QUIT: 
      break; 
    } 

    } while (choice != QUIT); 

    return(0); 
} 

int sample() { 
    cout << "Forming Lists" << endl; 
    int one = 1, two = 2; 
    List<int> l1 = List<int>(); 
    List<int> l2 = List<int>(); 

    l1.insert(one); 
    l1.insert(two); 

    cout << "print l1" << endl; 
    printList(l1); 

    cout << "l2 = l1" << endl; 
    l2 = l1; 

    cout << "print l2" << endl; 
    printList(l2);  

    cout << "l1.remove(one)" << endl; 
    l1.remove(one); 

    cout << "print l1" << endl; 
    printList(l1); 

    cout << "print l2" << endl; 
    printList(l2); 
    cout << "findPrevious 1 in l2" << endl; 
    ListIterator<int> iter = l2.findPrevious(one); 
    if (iter.isValid()) { 
     cout << "--iter valid" << endl; 
     cout << iter.retrieve() << endl; 
    } 
    else { 
     cout << "--iter not valid" << endl; 
    } 

    cout << "findPrevious 2 in l2" << endl; 
    iter = l2.findPrevious(two); 
    if (iter.isValid()) { 
     cout << "--iter valid" << endl; 
     cout << iter.retrieve() << endl; 
    } 
    else { 
     cout << "--iter not valid" << endl; 
    } 

    cout << "findPrevious 1 in l1" << endl; 
    iter = l1.findPrevious(one); 
    if (iter.isValid()) { 
     cout << "--iter valid" << endl; 
     cout << iter.retrieve() << endl; 
    } 
    else { 
     cout << "--iter not valid" << endl; 
    } 

    cout << "findPrevious 2 in l1" << endl; 
    iter = l1.findPrevious(two); 
    if (iter.isValid()) { 
     cout << "--iter valid" << endl; 
     cout << iter.retrieve() << endl; 
    } 
    else { 
     cout << "--iter not valid" << endl; 
    } 

    cout << "print l1" << endl; 
    printList(l1);  

     // you can remove whatever you want, whether it exists or not 
    cout << "l1.remove(one)" << endl; 
    l1.remove(one); 

    cout << "print l1" << endl; 
    printList(l1);  

    return(0); 
} 

void printList(const List<int>& l) { 
    if (l.isEmpty()) 
     cout << "Empty list" << endl; 
    else { 
     ListIterator<int> iter = l.first(); 
     while (iter.isValid()) { 
      cout << iter.retrieve() << " -> "; 
      iter.advance(); 
     } 
     cout << "NULL"; 
     cout << endl; 
    } 
} 

CHOICE menu() { 
    char choice; 
    CHOICE result; 
    cout << "(M)akeEmpty I(s)Empty (R)emove (I)nsert (F)indPrevious (P)rint (Q)uit: " << endl; 
    cin >> choice; 
    switch(choice) { 
    case 'M': 
    case 'm': 
     result = MAKEEMPTY; 
     break; 
    case 'S': 
    case 's': 
     result = ISEMPTY; 
     break; 
    case 'R': 
    case 'r': 
     result = REMOVE; 
     break; 
    case 'I': 
    case 'i': 
     result = INSERT; 
     break; 
    case 'F': 
    case 'f': 
     result = FINDPREVIOUS; 
     break; 
    case 'Q': 
    case 'q': 
     result = QUIT; 
     break; 
    case 'P': 
    case 'p': 
     result = PRINT; 
     break; 
    } 

    return(result); 
}

來源

2013-10-21 rezivor

首先，您不能在不同的翻譯單元中定義這些模板，並且從用戶文件中包含cpp文件非常奇怪。如果你想讓它們在cpp中，請將它包含在標題的底部。其次，提供迭代器並使用'std :: is_sorted'。 – chris

它可以在O（1）中完成 - 只需檢查插入的項目是否大於或等於先前的項目，並且小於或等於下一個項目。刪除項目不會破壞列表的排序不變量。 –

@chris我該如何實現？ – rezivor

與第一環節開始：

記錄當前鏈接的價值
迭代到下一個環節
測試，如果它是更大大於（或等於）前一鏈接的記錄值的值
如果是的話，從1
否則重複返回false

如果您在列表中得到所有的方式，你知道該列表是通過提高所有道路。

來源

2013-10-21 23:32:04 GraphicsMuncher

寫bool表達式來判斷一個列表是否正在增加

回答

相關問題