I am trying to put together a list class, but all of my calls to head are giving me NULL pointer exceptions... I'm not sure what is going on here. The functions are named in french but i have translated their purpose beside it. I've put comments on the affected lines.
I believe that working with head or head->next etc is causing the crash but i can't figure out how to fix it.
Thanks in advance for your advice.
#include <iostream>
using namespace std;
template <class T>
class Node {
T element;
Node<T>* next;
template <class T> friend class Liste;
template <class T> friend class Iterator;
};
template <class T>
class Iterator {
public:
bool operator==(Iterator i);
T operator*();
Iterator<T> operator++(int);
private:
Node<T>* position;
Liste<T>* container;
template <class T> friend class Liste;
};
template<class T>
class Liste {
public:
Liste();
~Liste();
bool estVide(); // checks if empty
T retournerTete(); // returns head value
T retournerFin(); // returns tail value
void ajouterEnTete(T cle); // insert to head of list
void ajouterEnFin(T cle); // insert to tail of list
void supprimerEnTete(); // delete from head of list
void supprimerEnFin(); // delete from tail of list
Iterator<T> begin(); // start iterator at first element
Iterator<T> end(); // end iterator by pointing to NULL
int BinarySearch(Liste<T> Liste, int start, int end, T key);
private:
Node<T> *head;
Node<T> *tail;
};
int main() {
Liste<int> Liste1 ;
int key, position, start = 0, end = 0;
char commande = 'Z';
cout << " Commandes " << endl;
cout << " F Finir " << endl; //end test
cout << " I Inserer une valeur a la queue de la liste" << endl; //insert at tail
cout << " T Inserer une valeur a la tete de la liste" << endl; //insert at head
cout << " S Supprimer la valeur a la tete" << endl; //delete at head
cout << " D Supprimer la valeur a la queue" << endl; //delete at tail
cout << " E Evaluer la valeur a la tete de la liste" << endl; //return head value
cout << " Q Evaluer la valeur a la queue de la liste" << endl; //return tail value
cout << " R Rechercher une valeur. " << endl; //binary search
cout << " A Afficher les donnees de la liste. " << endl << endl; //print list
while (commande != 'F')
{
cout << endl << "Entrer une commande : ";
cin >> commande;
switch (commande) {
case 'F': // Fin du programme
case 'f':
cout << "Le programme termine." << endl;
commande = 'F'; // Au cas où on aurait entré 'f'.
break;
case 'I': // Insertion d'une valeur a la queue de la liste.
case 'i':
cin >> key;
Liste1.ajouterEnFin(key);
cout << key << " a ete ajoute a la fin de la liste." << endl;
break;
case 'T': // Insertion d'une valeur a la tete de la liste.
case 't':
cin >> key;
Liste1.ajouterEnTete(key);
cout << key << " a ete ajoute au debut de la liste." << endl;
break;
case 'S': // Suppression de la valeur a la tete de la liste.
case 's':
Liste1.supprimerEnTete();
cout << "une valeur a ete supprime au debut de la liste." << endl;
break;
case 'D': // Suppression de la valeur a la queue de la liste.
case 'd':
Liste1.supprimerEnFin();
cout << "une valeur a ete supprime a la fin de la liste." << endl;
break;
case 'E': // Évaluation de la valeur a la tete de la liste.
case 'e':
cout << Liste1.retournerTete() << " est a la tete de la file." << endl;
break;
case 'Q': // Évaluation de la valeur au queue de la liste.
case 'q':
cout << Liste1.retournerFin() << " est a la queue de la file." << endl;
break;
case 'R': // Afficher la liste.
case 'r':
for (Iterator<int> i = Liste1.begin(); !(i == Liste1.endIt()); i++) {
end++;
}
cout << " Entrer une valeur : ";
cin >> key;
position = Liste1.BinarySearch(start, end, key);
if (position == -1)
cout << "pas trouve" << endl;
else
cout << " La valeur " << key << " se trouve a la position " << position << endl;
break;
case 'A': // Afficher la liste.
case 'a':
for (Iterator<int> i = Liste1.begin(); !(i == Liste1.endIt()); i++)
cout << *i << " ";
break;
default:
cout << "La commande n'est pas reconnue." << endl;
}
}
cout << "Au revoir" << endl;
return 0;
}
template<class T>
bool Iterator<T>::operator==(Iterator i) {
return position == i.position;
}
template<class T>
T Iterator<T>::operator*() {
return position->element;
}
template<class T>
Iterator<T> Iterator<T>::operator ++(int) {
if (position != NULL)
position = position->next; // exception thrown
return *this;
}
template <class T>
Liste<T>::Liste() {
head = NULL;
tail = NULL;
}
template <class T>
Liste<T>::~Liste() {
while (!estVide())
supprimerEnTete();
}
template <class T> // voir tete de la liste
T Liste<T>::retournerTete() {
if (estVide()) {
cout << " Vide " << endl;
return 0;
}
else
return head->element;
}
template <class T> // voir queue de la liste
T Liste<T>::retournerFin() {
if (estVide()) {
cout << " Vide " << endl;
return 0;
}
else
return tail->element;
}
template <class T> // inserer au debut
void Liste<T>::ajouterEnTete(T cle) {
Node<T> *N = new Node<T>;
N->element = cle;
if (estVide()) {
head = N;
tail = N;
}
else {
N->next = head;
head = N;
}
}
template <class T>
void Liste<T>::ajouterEnFin(T cle) {
Node<T> *N = new Node<T>;
N->element = cle;
if (estVide()) {
tail = N;
head = N;
}
else {
tail->next = N;
tail = N;
}
}
template<class T>
void Liste<T>::supprimerEnTete() {
if (!estVide()) {
Node<T> *p = head;
if (head->next == NULL) //exception thrown
tail = NULL;
head = p->next;
delete p;
}
}
template<class T>
void Liste<T>::supprimerEnFin() {
if (estVide()) { return; }
else if (head->next == NULL) { //exception thrown
supprimerEnTete();
}
else {
Node<T>* p = head;
while ((p->next)->next != NULL) //exception thrown
p = p->next;
tail = p;
p = p->next;
tail->next = NULL;
delete p;
}
}
template<class T>
Iterator<T> Liste<T>::begin() {
Iterator<T> i;
i.position = head;
i.container = this; //pointeur vers Liste
return i;
}
template<class T>
Iterator<T> Liste<T>::endIt() {
Iterator<T> i;
i.position = NULL;
i.container = this;
return i;
}
template<class T>
int Liste<T>::BinarySearch(Liste<T> Liste, int start, int end, T key) {
int middle;
Node<T> *curser = head;
while (curser->next != NULL) { //exception thrown
curser = curser->next;
end++;
}
if (end < start)
return -1;
middle = ((start + end) / 2);
if (key > middle)
BinarySearch(Liste, middle + 1, end, key);
else if (key < middle)
BinarySearch(Liste, start, middle - 1, key);
else
return middle;
}
