Ecco tutto.
list.h
#pragma once
#include "nodo.h"
#include <iostream>
using namespace std;
template <class T>
class List
{
protected:
Nodo<T>* head; // puntatore alla testa della lista
/* Restituisce il puntatore all'elemento di index-esima posizione.
Se index non è valido viene lanciata un'out_of_range exception.
*/
Nodo<T>* operator[] (const int index);
// Effettua lo swap delle informazioni contenute nei due nodi.
friend void swap(Nodo<T>* a, Nodo<T>* b)
{
T temp = a->getValue();
a->setValue(b->getValue());
b->setValue(temp);
}
public:
// Costruttore di default.
List();
// Costruttore copia
List(const List<T>&);
// Aggiunge un elemento in testa dato il puntatore al nodo.
void push_front(Nodo<T>* node);
// Aggiunge un elemento in testa dato il suo valore.
void push_front(const T& item);
// Aggiunge un nodo in testa.
void push_front(const Nodo<T> node);
// Aggiunge un elemento in coda dato il puntatore al nodo.
void push_back(Nodo<T>* node);
// Aggiunge un elemento in coda dato il suo valore.
void push_back(const T& item);
// Rimuove un elemento all'inizio della lista.
void pop_front(void);
// Rimuove un elemento alla fine della lista.
void pop_back(void);
// Restituisce il numero di elementi contenuti nella lista.
int size(void);
// Restituisce il nodo all'index-esima posizione.
Nodo<T>& elementAt(const int index);
// Restituisce il puntatore all'index-esimo nodo.
Nodo<T>* pointerAt(const int index);
// Rimuove l'elemento di index-esima posizione dalla lista.
void eraseAt(const int index);
/* Cancella la prima occorrenza del valore passato.
Se non sono presenti valori uguali a quello passato viene restituito false.
*/
bool eraseItem(const T& item);
// Rimuove tutti gli elementi dalla lista.
void clear(void);
// Controlla se un dato valore è presente almeno una volta all'interno della lista.
bool searchIf(const T& item);
// Restituisce la posizione della prima occorrenza di item all'interno della lista (-1 se item non è presente).
int searchFirstIndex(const T& item);
// Controlla se la lista è vuota.
bool isEmpty(void);
/* Effettua un inserimento ordinato all'interno della lista.
È necessario che T fornisca l'overloading degli operatori > e <.
*/
void sortedInsert(const T& item);
/* Applica l'algoritmo naive sort agli elementi della lista.
È necessario che T fornisca l'overloading degli operatori > e <.
*/
void naiveSort(void);
/* Riordina la lista in modo simile ad un array.
È necessario che T fornisca l'overloading degli operatori > e <.
*/
void naiveSortArrays(void);
/* Restituisce una lista che ha gli elementi invertiti rispetto all'istanza chiamante. */
List<T> reverse(void);
/* Stampa il contenuto della lista.
È necessario che T fornisca l'overloading dell'operator<<.
*/
friend ostream& operator<< (ostream& output, const List<T>& lista)
{
Nodo<T>* aux = lista.head;
if (aux == NULL)
output << "Lista vuota.";
else
{
while (aux != NULL)
{
output << aux->getValue() << " ";
aux = aux->getNext();
}
}
return output;
}
List<T>& operator=(const List<T>&);
};
#define LIST_FUNCTIONS
#include "list.cpp"
list.cpp
#ifndef LIST_FUNCTIONS
#include "list.h"
#else
template <typename T>
Nodo<T>* List<T>::operator[](const int index)
{
if (isEmpty()) // se la lista è vuota lancia l'eccezione
throw out_of_range("La lista e' vuota!");
else if (size() <= index) // se è richiesto l'accesso a un elemento in overflow
throw out_of_range("La lista contiene meno elementi di rispetto all'indice passato.");
else if (index < 0) // se l'indice è negativo
throw out_of_range("index e' negativo!");
else // scorre fino ad arrivare all'elemento specificato
{
Nodo<T>* aux = head;
for (int i = 0; i < index; i++)
aux = aux->getNext();
return aux;
}
}
template <typename T>
List<T>::List()
{
head = NULL;
}
template <typename T>
List<T>::List(const List<T>& copy)
{
head = new Nodo<T>(copy.head);
Nodo<T>* aux = copy.head->getNext();
while (aux != NULL) // continua ad aggiungere elementi in coda
{
push_back(aux);
aux = aux->getNext();
}
}
template <typename T>
void List<T>::push_front(Nodo<T>* node)
{
push_front(node->getValue()); // aggiunge l'elemento in testa
/* Nota: non è possibile aggiungere direttamente il nodo alla testa, poiché effettuando un node->setNext verrebbe modificato anche il nodo originale:
* se questo nodo appartiene già ad una lista, dopo l'inserimento effettuato in questo modo il nodo punterà alla testa della lista in cui verrà aggiunto, andando a modificare
* irreversibilmente la seconda lista.
*/
}
template <typename T>
void List<T>::push_front(const T& item)
{
if (isEmpty()) // se la lista è vuota
head = new Nodo<T>(item); // aggiunge direttamente il nodo
else
{
Nodo<T> *add = new Nodo<T>(item, head); // nodo da aggiungere alla testa
head = add; // la testa punta al nodo appena aggiunto
}
}
template <typename T>
void List<T>::push_front(const Nodo<T> node)
{
if (isEmpty())
head = new Nodo<T>(node.getValue(), NULL);
else
{
node.setNext(head->getNext());
head = new Nodo<T>(node);
}
}
template <typename T>
void List<T>::push_back(Nodo<T>* node)
{
if (isEmpty())
push_front(node);
else
{
Nodo<T>* aux = head;
while (aux->getNext() != NULL)
aux = aux->getNext();
aux->setNext(node);
}
}
template <typename T>
void List<T>::push_back(const T& item)
{
push_back(new Nodo<T>(item));
}
template <typename T>
void List<T>::pop_front(void)
{
if (isEmpty())
throw std::out_of_range("La lista e' vuota.");
else
{
Nodo<T>* second = head->getNext();
delete head;
head = second;
}
}
template <typename T>
void List<T>::pop_back(void)
{
if (isEmpty())
throw out_of_range("La lista e' vuota.");
else
{
Nodo<T> *aux = head;
while (aux->getNext() != NULL)
aux = aux->getNext();
delete aux->getNext();
aux->setNext(NULL);
}
}
template <typename T>
int List<T>::size(void)
{
int count = 0;
Nodo<T>* aux = head;
while (aux != NULL)
{
++count;
aux = aux->getNext();
}
return count;
}
template <typename T>
Nodo<T>* List<T>::pointerAt(const int index)
{
return (*this)[index];
}
template <typename T>
Nodo<T>& List<T>::elementAt(const int index)
{
return *(this->pointerAt(index));
}
template <typename T>
void List<T>::eraseAt(const int index)
{
if (isEmpty())
throw out_of_range("La lista e' vuota.");
else if (index >= size())
throw out_of_range("overflow exception.");
else
{
if (index == 0)
pop_front();
else
{
Nodo<T>* prec = head;
Nodo<T>* toDelete = head->getNext();
for (int i = 0; i < index; i++)
{
prec = prec->getNext();
toDelete = toDelete->getNext();
}
prec->setNext(toDelete->getNext());
delete toDelete;
toDelete = NULL;
}
}
}
template <typename T>
bool List<T>::eraseItem(const T& item)
{
bool flag = false; // valore restituito dal metodo
int index = searchFirstIndex(item);
if (index != -1)
{
flag = true;
eraseAt(index);
}
return flag;
}
template <typename T>
void List<T>::clear(void)
{
while (head != NULL)
pop_front();
}
template <typename T>
bool List<T>::searchIf(const T& item)
{
bool flag = false;
if (!isEmpty())
{
Nodo<T>* aux = head;
while (aux != NULL && aux->getValue() != item)
aux = aux->getNext();
if (aux != NULL)
flag = true;
}
return flag;
}
template <typename T>
int List<T>::searchFirstIndex(const T& item)
{
int index = -1;
if (!isEmpty && searchIf(item))
{
int count = 0;
Nodo<T>* aux = head;
while (aux != item)
{
aux = aux->getNext();
++count;
}
index = count;
}
return index;
}
template <typename T>
bool List<T>::isEmpty(void)
{
return (head == NULL);
}
template <typename T>
void List<T>::sortedInsert(const T& item)
{
if (isEmpty())
push_front(item);
else
{
if (head->getValue() > item)
push_front(item);
else
{
Nodo<T>* prec = head;
Nodo<T>* succ = head->getNext();
while (succ != NULL && succ->getValue() < item)
{
prec = prec->getNext();
succ = succ->getNext();
}
Nodo<T>* add = new Nodo<T>(item);
add->setNext(succ);
prec->setNext(add);
}
}
}
template <typename T>
void List<T>::naiveSort(void)
{
if (head != NULL && head->getNext() != NULL) // effettua l'ordinamento solo se ci sono almeno 2 elementi nella lista
{
Nodo<T>* a = head; // nodo che viene confrontato mano a mano con tutti gli altri
while (a->getNext() != NULL) // il nodo si ferma alla coda
{
Nodo<T>* b = a->getNext(); // nodo che verrà confrontato a ogni iterazione con il nodo a
while (b != NULL) // b deve scorrere tutta la lista
{
if (b->getValue() < a->getValue())
swap(a, b);
b = b->getNext();
}
a = a->getNext();
}
}
}
template <typename T>
void List<T>::naiveSortArrays(void)
{
if (head != NULL && head->getNext() != NULL) // riordina la lista solo se ci sono almeno 2 elementi
{
for (int i = 0; i < size() - 1; i++)
{
for (int j = i + 1; j < size(); j++)
{
if (pointerAt(j)->getValue() < pointerAt(i)->getValue())
swap(pointerAt(i), pointerAt(j));
}
}
}
}
template <typename T>
List<T> List<T>::reverse(void)
{
List<T> result;
Nodo<T>* aux = head;
while (aux != NULL)
{
result.push_front(aux->getValue());
aux = aux->getNext();
}
return result;
}
template <typename T>
List<T>& List<T>::operator=(const List<T>& copy)
{
Nodo<T>* aux = copy.head;
while (aux != NULL)
{
cout << "loop" << endl;
push_back(aux->getValue());
aux = aux->getNext();
}
return *this;
}
#endif
nodo.h
#pragma once
#include <iostream>
using namespace std;
template <typename T>
class Nodo
{
private:
T value; // valore contenuto all'interno del nodo
Nodo<T>* next; // puntatore all'elemento successivo
public:
/* Costruttore di default. */
Nodo();
/* Costruttore con parametro l'informazione del nodo. */
Nodo(const T& info);
/* Costruttore con parametri. */
Nodo(const T& info, Nodo<T>* next);
/* Costruttore copia. */
Nodo(const Nodo<T>& copy);
/* Costruttore copia. */
Nodo(Nodo<T>* copy);
// Imposta il valore di T.
void setValue(const T& value);
// Imposta il puntatore al nodo successivo.
void setNext(Nodo<T>* next);
// Ottiene il valore del nodo.
T getValue(void);
// Ottiene il puntatore al nodo successivo.
Nodo<T>* getNext(void);
Nodo<T>& operator=(const Nodo<T>*);
};
#define NODE_FUNCTIONS
#include "nodo.cpp"
nodo.cpp
#ifndef NODE_FUNCTIONS
#include "nodo.h"
#else
template <typename T>
Nodo<T>::Nodo() : value()
{
next = NULL;
}
template <typename T>
Nodo<T>::Nodo(const T& info)
{
value = info;
next = NULL;
}
template <typename T>
Nodo<T>::Nodo(const T& info, Nodo<T>* next)
{
value = info;
this->next = next;
}
template <typename T>
Nodo<T>::Nodo(const Nodo<T>& copy)
{
value = copy.value;
next = copy.next;
}
template <typename T>
Nodo<T>::Nodo(Nodo<T>* copy)
{
value = copy->getValue();
next = copy->getNext();
}
template <typename T>
void Nodo<T>::setValue(const T& value)
{
this->value = value;
}
template <typename T>
void Nodo<T>::setNext(Nodo<T>* next)
{
this->next = next;
}
template <typename T>
T Nodo<T>::getValue(void)
{
return value;
}
template <typename T>
Nodo<T>* Nodo<T>::getNext(void)
{
return next;
}
template <typename T>
Nodo<T>& Nodo<T>::operator=(const Nodo<T>* node)
{
value = node->value;
next = node->next;
}
#endif
integerList.h (aggiunge metodi specifici per una lista di interi):
#pragma once
#include "list.h"
class IntegerList : public List<int>
{
public:
// Restituisce il totale della sommatoria di tutti gli elementi della lista.
int somma(void);
// Restituisce la media fra gli elementi della lista.
double media(void);
/* Restituisce il valore dell'elemento massimo della lista.
Se la lista è vuota viene lanciata un'out_of_range exception.
*/
int max(void);
// Imposta il valore di pari e dispari alle rispettive sommatorie di tutti i numeri pari e di tutti i numeri dispari presenti nella lista.
void sommaPariDispari(int* pari, int* dispari);
// mancante punto f
// Cancella il primo elemento della lista se questo è pari.
int eraseIfEven(void);
// Rende positiva tutta la lista.
void abs(void);
// mancante punto j
};
integerList.cpp
#include "integerList.h"
int IntegerList::somma(void)
{
Nodo<int> *aux = head;
int tot = 0;
while (aux != NULL)
{
tot += aux->getValue();
aux = aux->getNext();
}
return tot;
}
int IntegerList::max(void)
{
if (isEmpty())
throw out_of_range("Impossibile calcolare il massimo. La lista e' vuota.");
else
{
Nodo<int>* aux = head->getNext();
int max = head->getValue();
while (aux != NULL)
{
if (aux->getValue() > max)
max = aux->getValue();
aux = aux->getNext();
}
return max;
}
}
double IntegerList::media(void)
{
if (size() != 0)
return (double)somma() / size();
else
{
std::cerr << "Lista vuota." << std::endl;
return 0;
}
}
void IntegerList::sommaPariDispari(int* pari, int* dispari)
{
Nodo<int>* aux = head;
*pari = 0;
*dispari = 0;
while (aux != NULL)
{
if (aux->getValue() % 2 == 0)
(*pari) += aux->getValue();
else
(*dispari) += aux->getValue();
aux = aux->getNext();
}
}
int IntegerList::eraseIfEven(void)
{
if (head->getValue() % 2 == 0)
{
pop_front();
return 1;
}
else
return 0;
}
void IntegerList::abs(void)
{
Nodo<int>* aux = head;
while (aux != NULL)
{
if (aux->getValue() < 0)
aux->setValue(aux->getValue() * -1);
aux = aux->getNext();
}
}
main.cpp
#include "integerList.h"
#include <iostream>
using namespace std;
int menu(void);
int main (void)
{
IntegerList list;
List<int> reversed;
int scelta;
int pari = 0;
int dispari = 0;
int info;
do
{
scelta = menu();
switch (scelta)
{
case 1:
cout << "La somma della lista e': " << list.somma() << endl;
break;
case 2:
cout << "La media degli elementi della lista e': " << list.media() << endl;
break;
case 3:
cout << "L'elemento massimo della lista e': " << list.max() << endl;
break;
case 4:
list.sommaPariDispari(&pari, &dispari);
cout << "La somma dei pari e': " << pari << ", dei dispari: " << dispari << endl;
break;
case 5:
if (list.eraseIfEven() == 0)
cout << "Elemento non cancellato." << endl;
else
cout << "Elemento cancellato." << endl;
break;
case 6:
list.abs();
cout << "Lista positivizzata." << endl;
break;
case 7:
cout << "Inserisci l'elemento da aggiungere in coda: ";
cin >> info;
list.push_back(info);
break;
case 8:
cout << list << endl;
break;
case 9:
cout << "Lista prima dell'ordinamento: " << list << endl;
list.naiveSort();
cout << "Lista dopo l'ordinamento: " << list << endl;
break;
case 10:
cout << "Lista prima dell'ordinamento: " << list << endl;
list.naiveSortArrays();
cout << "Lista dopo l'ordinamento: " << list << endl;
break;
case 11:
cout << "Lista attuale (non verra' modificata): " << list << endl;
list.reverse();
cout << "prova" << endl;
cout << "Lista invertita: " << reversed << endl;
break;
}
} while (scelta != 20);
return 0;
}
int menu(void)
{
int scelta;
cout << "1. Somma gli elementi della lista." << endl;
cout << "2. Calcola la media della lista." << endl;
cout << "3. Massimo elemento della lista." << endl;
cout << "4. Somma elementi pari e dispari." << endl;
cout << "5. Cancella il primo elemento se e' pari." << endl;
cout << "6. Positivizza tutta la lista." << endl;
cout << "7. Aggiungi un elemento in coda." << endl;
cout << "8. Stampa il contenuto della lista." << endl;
cout << "9. Riordina la lista." << endl;
cout << "10. Riordina la lista (con i for)." << endl;
cout << "11. Inverti gli elementi della lista." << endl;
cin >> scelta;
return scelta;
}