Je ne peux pas supprimer le nombre minimum dans la liste Doublement lié puis le suivant

Question

Donc, j'ai été bloqué ces trois derniers jours en essayant de supprimer le pointeur minimum de la liste doublement chaînée. Il se bloque toujours au point que j'utilise min = a.erase (min). J'ai fait des recherches en disant que vous devriez "supprimer" d'abord en utilisant "delete (* min)" mais il ne compilera pas. En ce moment je suis concentré sur la suppression d'une valeur puis j'ajouterai la boucle pour passer encore n fois pour chaque petit nombre (ie - je dois trouver minimum, imprimer, supprimer, répéter jusqu'à la fin)

J'avais un code qui fonctionnait mais ça ne fonctionnait pas tout le temps, ça me faisait recommencer.

#include <cstdlib> 
#include <iostream> 
#include <cstdlib> 
#include <ctime> 
#include <iomanip> 
typedef int Object; 

using namespace std; 
#include <cstdlib> 
typedef int Object; 

class List{ 
private: 
// The basic doubly linked list node. 
// Nested inside of List, can be public 
// because the Node is itself private 
    struct Node 
    { 
     Object data; 
     Node *prev; 
     Node *next; 

     Node(const Object & d = Object(), Node * p = NULL, Node * n = NULL) 
      : data(d), prev(p), next(n) { } 
    }; 

public: 
    class const_iterator 
    { 
    public: 

    // Public constructor for const_iterator. 
     const_iterator() : current(NULL) 
     { } 

    // Return the object stored at the current position. 
    // For const_iterator, this is an accessor with a 
    // const reference return type. 
     const Object & operator*() const 
     { 
      return retrieve(); 
     } 

     const_iterator & operator++() 
     { 
      current = current->next; 
      return *this; 
     } 

    const_iterator operator++ (int) 
    { 
     const_iterator old = *this; 
     ++(*this); 
     return old; 
    } 

    const_iterator & operator--() 
    { 
     current = current->prev; 
     return *this; 
    } 

    const_iterator operator-- (int) 
    { 
     const_iterator old = *this; 
     --(*this); 
     return old; 
    } 

    bool operator== (const const_iterator & rhs) const 
    { 
     return current == rhs.current; 
    } 

    bool operator!= (const const_iterator & rhs) const 
    { 
     return !(*this == rhs); 
    } 

    protected: 
    Node *current; 

    // Protected helper in const_iterator that returns the object 
    // stored at the current position. Can be called by all 
    // three versions of operator* without any type conversions. 
    Object & retrieve() const 
    { 
     return current->data; 
    } 

    // Protected constructor for const_iterator. 
    // Expects a pointer that represents the current position. 
    const_iterator(Node *p) : current(p) 
    { } 

    friend class List; 
    }; 

    class iterator : public const_iterator 
    { 
    public: 

    // Public constructor for iterator. 
    // Calls the base-class constructor. 
    // Must be provided because the private constructor 
    // is written; otherwise zero-parameter constructor 
    // would be disabled. 
    iterator() 
    { } 

    Object & operator*() 
    { 
     return retrieve(); 
    } 

    // Return the object stored at the current position. 
    // For iterator, there is an accessor with a 
    // const reference return type and a mutator with 
    // a reference return type. The accessor is shown first. 
    const Object & operator*() const 
    { 
     return const_iterator::operator*(); 
    } 

    iterator & operator++() 
    { 
     current = current->next; 
     return *this; 
    } 

    iterator operator++ (int) 
    { 
     iterator old = *this; 
     ++(*this); 
     return old; 
    } 

    iterator & operator--() 
    { 
     current = current->prev; 
     return *this; 
    } 

    iterator operator-- (int) 
    { 
     iterator old = *this; 
     --(*this); 
     return old; 
    } 

    protected: 
    // Protected constructor for iterator. 
    // Expects the current position. 
    iterator(Node *p) : const_iterator(p) 
    { } 

    friend class List; 
    }; 

public: 
    List() 
    { 
     init(); 
    } 

    ~List() 
    { 
    clear(); 
    delete head; 
    delete tail; 
    } 

    List(const List & rhs) 
    { 
    init(); 
    *this = rhs; 
} 

const List & operator= (const List & rhs) 
{ 
    if (this == &rhs) 
     return *this; 
    clear(); 
    for (const_iterator itr = rhs.begin(); itr != rhs.end(); ++itr) 
     push_back(*itr); 
    return *this; 
} 

// Return iterator representing beginning of list. 
// Mutator version is first, then accessor version. 
iterator begin() 
{ 
    return iterator(head->next); 
} 

const_iterator begin() const 
{ 
    return const_iterator(head->next); 
} 

// Return iterator representing endmarker of list. 
// Mutator version is first, then accessor version. 
iterator end() 
{ 
    return iterator(tail); 
} 

const_iterator end() const 
{ 
    return const_iterator(tail); 
} 

// Return number of elements currently in the list. 
int size() const 
{ 
    return theSize; 
} 

// Return true if the list is empty, false otherwise. 
bool empty() const 
{ 
    return size() == 0; 
} 

void clear() 
{ 
    while (!empty()) 
     pop_front(); 
} 

// front, back, push_front, push_back, pop_front, and pop_back 
// are the basic double-ended queue operations. 
Object & front() 
{ 
    return *begin(); 
} 

const Object & front() const 
{ 
    return *begin(); 
} 

Object & back() 
{ 
    return *--end(); 
} 

const Object & back() const 
{ 
    return *--end(); 
} 

void push_front(const Object & x) 
{ 
    insert(begin(), x); 
} 

void push_back(const Object & x) 
{ 
    insert(end(), x); 
} 

void pop_front() 
{ 
    erase(begin()); 
} 

void pop_back() 
{ 
    erase(--end()); 
} 

// Insert x before itr. 
iterator insert(iterator itr, const Object & x) 
{ 
    Node *p = itr.current; 
    theSize++; 
    return iterator(p->prev = p->prev->next = new Node(x, p->prev, p)); 
} 

// Erase item at itr. 
iterator erase(iterator itr) 
{ 
    Node *p = itr.current; 
    iterator retVal(p->next); 
    p->prev->next = p->next; 
    p->next->prev = p->prev; 
    delete p; 
    theSize--; 

    return retVal; 
} 

iterator erase(iterator start, iterator end) 
{ 
    for (iterator itr = start; itr != end;) 
     itr = erase(itr); 

    return end; 
} 

private: 
int theSize; 
Node *head; 
Node *tail; 

void init() 
{ 
    theSize = 0; 
    head = new Node; 
    tail = new Node; 
    head->next = tail; 
    tail->prev = head; 
} 
}; 

int main() 
{ 
    size_t n; 
    cout << "Please enter the amount of random numbers to be generated " <<   endl; 
    cin >> n; 
    int randomRange; 
    List a; 

    srand(time(NULL)); 


    for (int i = 0; i < n;i++) { 
     randomRange = rand() % 10000 + 1; 
     a.insert(a.end(), randomRange); 
    } 

    cout << endl; 
    //a.erase(--a.end()); 
    cout << "The size is: " <<a.size() << endl; 
    cout << endl; 
    for (List::iterator it = a.begin();it != a.end(); ++it) 
    { 
     cout << *it << endl; 
    } 
    //List::iterator it = a.begin(); 
    List::iterator min = a.begin(); 

    cout << endl; 
    //cout << *min << endl; 
    for (List::iterator it = a.begin();it != a.end(); ++it) { 
     //++min; 

      if (*it < *min) { 
       //cout <<"1st it is : "<< *it << endl; 
       //cout << "1st min is : " << *min << endl; 
       *min = *it; 
       //cout <<"this is min"<< *it << endl; 




       //cout << "check" << endl; 
       //cout << "smallest" << *min << endl; 
      } 


      //cout << "after if loop it is : " << *it << endl; 
     // cout << "after if loop min is : " << *min << endl; 
      //cout << "check2" << endl; 
    } 
    cout <<"small" << *min << endl; 
    //delete (*it); 

    while (min != a.end()) 
    { 
     a.erase(min); 
    } 

    for (List::iterator min ;min != a.end(); ++min) 
    { 
     cout << *min << endl; 
    } 
    return 0; 

Answer 1

Lorsque vous appelez a.erase(min) l'itérateur min est invalidée. Utilisez min = a.erase (min), puisque la fonction erase renvoie l'itérateur suivant.

EDIT: Cependant, ce changement ne fait pas ce que vous voulez. Voici ce que la fonction principale doit être:

int main() 
{ 
    size_t n; 
    cout << "Please enter the amount of random numbers to be generated " <<   endl; 
    cin >> n; 
    int randomRange; 
    List a; 

    srand(time(NULL)); 


    for (int i = 0; i < n;i++) { 
     randomRange = rand() % 10000 + 1; 
     a.insert(a.end(), randomRange); 
    } 

    cout << endl; 
    cout << "The size is: " <<a.size() << endl; 
    cout << endl; 
    for (List::iterator it = a.begin();it != a.end(); ++it) 
    { 
     cout << *it << endl; 
    } 

    cout << endl; 

    while (a.size()) // Repeat until size is zero 
    { 
     List::iterator min = a.begin(); // Initialize the minimum iterator 
     for (List::iterator it = a.begin();it != a.end(); ++it) { 

       if (*it < *min) 
       { 
        // New minimum found, save iterator, not value. 
        min = it; 
       } 
     } 
     cout <<"small: " << *min << endl; // print the minimum 
     a.erase(min); // Erase the minimum 
    } 

    return 0; 
} 

EDIT: Sinon, vous pouvez trier votre liste et puis juste imprimer le contenu. La fonction principale pourrait alors être:

int main() 
{ 
    size_t n; 
    cout << "Please enter the amount of random numbers to be generated " <<   endl; 
    cin >> n; 
    int randomRange; 
    List a; 

    srand(time(NULL)); 


    for (size_t i = 0; i < n;i++) { 
     randomRange = rand() % 10000 + 1; 
     a.insert(a.end(), randomRange); 
    } 

    cout << endl; 

    cout << "The size is: " <<a.size() << endl; 
    cout << endl; 
    for (List::iterator it = a.begin();it != a.end(); ++it) 
    { 
     cout << *it << endl; 
    } 
    cout << endl; 

    // Use bubble sort 
    for (List::iterator it1 = a.begin(); it1 != a.end(); ++it1) 
    for (List::iterator it2 = a.begin(); it2 != it1; ++it2) 
    { 
     List::iterator it3 = ++it2; --it2; // Your iterators does not support arithmetic... 
     if (*it2 > *it3) 
     { 
      std::swap(*it2, *it3); 
     } 
    } 

    for (List::iterator min = a.begin() ;min != a.end(); ++min) 
    { 
     cout << *min << endl; 
    } 
    return 0; 
}