Ho "finito" (?) di scrivere la mia classe che implementa una lista circolare gestita tramite i 2 puntatori front e rear.
l'unico problema è che la funzione push_back, che esegue l'inserimento in coda di un valore, non funziona e non riesco a capire perchè.
ho seguito il debug linea per linea della funzione e il programma crasha dopo la } di chiusura.
la funzione è questa:
template <typename T>
void CircularQueue<T>::push_back(const T& value)
{
Node<T>* add = new Node<T>(value);
if (!isEmpty())
{
add->setNext(front);
rear->setNext(add);
rear = add;
}
else
{
front = add;
rear = add;
rear->setNext(front);
}
++size;
} // dopo questa riga viene lanciato l'errore
testata con questo main:
int main()
{
CircularQueue<int> queue;
queue.push_back(5);
return 0;
}
visual studio 2015 non mi specifica l'errore, dice soltanto "l'applicazione ha chiamato un punto d'interruzione", aprendomi il file delete_scalar.cpp, con questo contenuto:
//
// delete_scalar.cpp
//
// Copyright (c) Microsoft Corporation. All rights reserved.
//
// Defines the scalar operator delete.
//
#include <crtdbg.h>
#include <malloc.h>
#include <vcruntime_new.h>
void __CRTDECL operator delete(void* const block) noexcept
{
#ifdef _DEBUG
_free_dbg(block, _UNKNOWN_BLOCK);
#else
free(block);
#endif
}
mentre visual studio 2012 dava l'errore "_block_type_is_valid(phead- nblockuse)", sempre allo stesso punto.
la cosa curiosa è che (sembra) che a generare l'errore sia l'istruzione front = add. commentandola infatti non ci sono più errori a runtime e il programma viene eseguito correttamente, ma ovviamente con una logica sbagliata, poiché il puntatore alla testa della coda rimarrebbe settato a null anche con un elemento.
ho provato a cercare l'errore _block_type_is_valid(phead- nblockuse) ma non trovo niente di comprensibile per i miei livelli... oltretutto è in situazioni differenti dalle mie: l'unica cosa che mi sembra d'aver capito è che dovrebbe esserci un memory leak da qualche parte, ma... dove? anche l'inserimento in coda/testa su una lista li ho affrontati allo stesso modo (c'era sempre il puntatore add) e funzionavano alla perfezione...
la classe Node non ha overloaddato il distruttore. penso sia per questo che il programma si arrabbi, ma perché solo qui e non con le liste o con le pile? inoltre, come potrei overloaddare il distruttore di un nodo? non posso fare il delete del valore, poiché non è un puntatore...
spero possiate darmi una mano, perché io non so proprio come risolvere questa roba...
coda.h:
#pragma once
#include "../Single Linked Node/node.h"
template <typename T>
class CircularQueue
{
protected:
Node<T>* front;
Node<T>* rear;
size_t size;
public:
CircularQueue();
CircularQueue(const T& value);
CircularQueue(const CircularQueue<T>& copy);
~CircularQueue();
void push_back(const T& value);
const T pop_front();
const bool isEmpty();
/* Inserisce l'elemento specificato nella posizione specificata.
* Se la coda è vuota, l'elemento viene inserito in testa.
* Se la posizione specificata è superiore alla dimensione della pila, l'elemento verrà inserito in coda.
*/
void insertAt(const unsigned int pos, const T& value);
/* Cancella l'elemento posto nell'index-esima posizione.
Se la coda è vuota o se la posizione specificata non è valida, viene lanciata un'out_of_range exception.
*/
void eraseAt(const unsigned int pos);
/* Restituisce l'elemento alla posizione specificata.
Se la posizione non è valida viene lanciata un'out_of_range exception.
*/
const T getElementAt(const unsigned int pos);
};
coda.cpp:
#include "circularQueue.h"
#include "../Single Linked Node/node.cpp"
#include <stdexcept>
template <typename T>
CircularQueue<T>::CircularQueue()
{
front = nullptr;
rear = nullptr;
size = 0;
}
template <typename T>
CircularQueue<T>::CircularQueue(const T& value) : CircularQueue<T>()
{
push_back(value);
}
template <typename T>
CircularQueue<T>::CircularQueue(const CircularQueue<T>& copy) : CircularQueue<T>()
{
Node<T>* aux = copy.head;
while (aux != nullptr)
{
push_back(aux->getValue());
aux = aux->getNext();
}
}
template <typename T>
CircularQueue<T>::~CircularQueue()
{
while (front != nullptr && rear != nullptr)
pop_front();
}
template <typename T>
void CircularQueue<T>::push_back(const T& value)
{
Node<T>* add = new Node<T>(value);
if (!isEmpty())
{
add->setNext(front);
rear->setNext(add);
rear = add;
}
else
{
front = add;
rear = add;
rear->setNext(front);
}
++size;
}
template <typename T>
const T CircularQueue<T>::pop_front()
{
if (!isEmpty())
{
const T value = front->getValue();
Node<T>* second = front->getNext();
delete front;
front = second;
--size;
return value;
}
else
throw std::out_of_range("La coda e' vuota.");
}
template <typename T>
const bool CircularQueue<T>::isEmpty()
{
return (front == nullptr && rear == nullptr);
}
template <typename T>
void CircularQueue<T>::insertAt(const unsigned int pos, const T& value)
{
if (isEmpty() || pos >= size) // se la coda è vuota o se la posizione è maggiore della dimensione della coda, l'elemento viene inserito in coda
push_back(value);
else
{
Node<T>* prev = front; // puntatore all'elemento precedente del nuovo nodo
Node<T>* next = front->getNext(); // puntatore all'elemento successivo del nuovo nodo
for (unsigned i = 1; i != pos; ++i) // il nuovo elemento dovrà avere posizione pos dopo l'inserimento (partendo da 0)
{
prev = prev->getNext();
next = next->getNext();
}
Node<T>* add = new Node<T>(value, next);
prev->setNext(add);
}
}
template <typename T>
void CircularQueue<T>::eraseAt(const unsigned int pos)
{
if (isEmpty())
throw std::out_of_range("La coda e' vuota.");
else if (pos > size)
throw std::out_of_range("Posizione da eliminare non valida.");
else
{
if (pos == 1)
pop_front();
else
{
Node<T>* prev = front;
Node<T>* del = front->getNext();
for (unsigned i = 1; i != pos - 1; ++i)
{
prev = prev->getNext();
del = del->getNext();
}
prev->setNext(del->getNext());
delete del;
del = nullptr;
}
}
}
template <typename T>
const T CircularQueue<T>::getElementAt(const unsigned int pos)
{
if (isEmpty())
throw std::out_of_range("La coda e' vuota.");
else if (pos > size)
throw std::out_of_range("Posizione da eliminare non valida.");
else
{
Node<T>* aux = front;
for (unsigned i = 1; i != pos; ++i)
aux = aux->getNext();
return aux->getValue();
}
}