Doubly linked list and polymorphism

[bernardo.mclobo]

Hi.

I'm learning C++ by myself, so I'm a noob, also i'm a mad scientist :P
I'm trying to use a doubly linked list with polymorphism, and got a problem.

Here is my code:

#include <iostream>
#include<string>
#include<cstdlib>
#include<cstring>
#include<sstream>

using namespace std;

// node class
template<typename T>
class nodeType
{
public:
  nodeType();
  nodeType(T);
  ~nodeType();

  nodeType *next;
  nodeType *previous;
  T data;
  //string getkey();
  string Id;
  void imprime();
  // getkey
  string getkey()
  {
    stringstream llave;
    llave << data.getkey();
    llave >> Id;
    return Id;
  }
};
// by defect
template<typename T>
nodeType<T>::nodeType()
{
  data = NULL;
  next = NULL;
  previous = NULL;
}

// by parameter
template<typename T>
nodeType<T>::nodeType(T data_)
{
  data = data_;
  next = NULL;
  previous = NULL;
}

// node printing
template<typename T>
void nodeType<T>::imprime()
{
  data.imprime();
}

template<typename T>
nodeType<T>::~nodeType() 
{
  delete next;
  delete previous;
}

// list
template <class T>
class list
{
private:
  nodeType<T> *first;
  nodeType<T> *last;
  nodeType<T> *current;
  int m_num_nodes;

public:
  list();
  ~list();

  void add_head(T);
  void add_end(T);
  void add_sort(T);
  void search(string r);
  void del_by_data(int n);
  void print();
};

template<typename T>
list<T>::list()
{
  m_num_nodes = 0;
  first = NULL;
  last = NULL;
}

//add in the beginning ... 
template<typename T>
void list<T>::add_head(T data_)
{
  nodeType<T> *new_node = new nodeType<T>(data_);
  nodeType<T> *temp = first;

  if (!first)
  {
    first = new_node;
  }
  else
  {
    new_node->next = first;
    first = new_node;

    while (temp)
    {
      temp = temp->next;
    }
  }
  m_num_nodes++;
}

// add to the last
template<typename T>
void list<T>::add_end(T data_)
{
  nodeType<T> *new_node = new nodeType<T> (data_);
  nodeType<T> *temp = first;

  if (!first)
  {
    first = new_node;
  }
  else
  {
    while (temp->next != NULL)
    {
      temp = temp->next;
    }
    temp->next = new_node;
  }
  m_num_nodes++;
}

// it is supposed that sorts items in the list ...
template<typename T>
void list<T>::add_sort(T data_)
{
  nodeType<T> *new_node = new nodeType<T> (data_);
  nodeType<T> *temp = first;

  if (!first)
  {
    first = new_node;
    last = new_node;
  }
  else
  {
    if (first->getkey() > new_node->getkey())
    {
      new_node->next = first;
      first = new_node;
    }
    else
    {
      while ((temp->next != NULL) && (new_node->getkey() > temp->next->getkey()))
      {
         temp = temp->next;
      }
      // .. ¿? ..
      new_node->next = temp->next;
      temp->next = new_node;
      temp->previous = new_node->previous;
      new_node->previous = temp;
      temp->next = new_node;
    }
  }
  m_num_nodes++;
 }

// print list
template<typename T>
void list<T>::print()
{
  nodeType<T> *current;
  current = first;

  while (current != NULL)
  {
    current->imprime();
    current = current->next;
  }
}

template<typename T>
void list<T>::search(string r)
{
  bool found = false;
  current = first;

  while (current != NULL && !found)
  {
    if (current->getkey() == r)
    {
      found = true;
      current->imprime();
    }
    else
    {
      current = current->next;
    }
  }
  if (!found)
    cout << "Element not found\n";

}

template<typename T>
void list<T>::del_by_data(int n)
{

  nodeType<T> *temp = first;
  nodeType<T> *del;
  int i;
  bool deleted = false;

  if (n > 1 && n <= m_num_nodes)
  {
    for(i=1;i<n;i++)
    {
      temp=temp->next;
    }

    if (n == 1)
    {
      first = temp->next;
      temp->next->previous = NULL;
    }
    else if(n == m_num_nodes)
    {
      last = temp->previous;
      temp->previous->next = NULL;
    }
    else
    {
      temp->previous->next = temp->next;
      temp->next->previous = temp->previous;
    }
  }
  m_num_nodes--;
}


// destroy the constructor
template<typename T>
list<T>::~list() {
  nodeType<T> *item;
  nodeType<T> *next;

  for(item=first; item != 0; item = next)
  {
    next = item->next;
    delete item;
  }
}

class animal
{
public:
   virtual void print()const 
   {  cout << "Unknown animal type.\n";
   }
   virtual ~animal(){} 

   string getkey()
   {
     string tipoanimal;
  }

  void imprime()
  {
    cout << "Ok" << endl;
  };

protected:
   int npatas;
   string tipoanimal;
};

//... Clase Ave ..
class ave: public animal
{
protected:
  string nombre;
  string nada;
  string tipo;
  string canta;
  string carroniero;

public:
   ave(int n, string c, string nom, string tip, string cant, string car,  string nad)
   {
     npatas = n; 
     tipoanimal = c; 
     nombre = nom;
     tipo = tip;
     canta = cant;
     carroniero = car;
     nada = nad;
  }

   void print()const
   { 
    cout << "Un " << nombre << " es un " << tipoanimal << " que tiene " << npatas 
     <<  " patas y es del tipo " << tipo << " " << canta <<  " canta y " << 
      carroniero << " es carroñero y " << nada << " nada" <<  endl;
   }
};


// mamifero
class mamifero : public animal
{
protected:
  string nombre;
  string tipo;
public:
  mamifero(int n, string c, string nom, string tip)
  {
    npatas = n;
    tipoanimal = c;
    nombre = nom;
    tipo = tip;
  }

  void print() const
  {
    cout << "Un " << nombre << " es un " << tipoanimal << " que tiene " << npatas 
     <<  " patas y es del tipo " << tipo << endl;
  }
};

// Pez
class pez : public animal
{
protected:
  string nombre;
  string tipo;
  string nace;                                              // ovíparo,  vivíparo
public:
  pez(int n, string c, string nom, string tip, string nac)
  {
    npatas = n;
    tipoanimal = c;
    nombre = nom;
    tipo = tip;
    nace =nac;
  }

  void print() const
  {
    cout << "Un " << nombre << " es un " << tipoanimal << " que tiene " << npatas 
     <<  " patas y es del tipo " << tipo << ", además es " << nace << endl;
  }
};


// reptil
class reptil : public animal
{
protected:
  string nombre;
  string tipo;
  string venenoso;
  string tamanio;

public:
  reptil(int n,  string c,  string nom,  string tip,  string ven, string tam)
  {
    npatas = n;
    tipoanimal = c;
    nombre = nom;
    tipo = tip;
    venenoso = ven;
    tamanio = tam;
  }

  void print() const
  {
    cout << "Un " << nombre << " es un " << tipoanimal << " que tiene " << npatas <<  
      " patas y es del tipo " << tipo << " y " << venenoso << " venenoso, además es " << tamanio << endl;
  }
};

// ... Aves ..
class aguila : public ave
{
public:
  aguila(int n, string c, string nom, string tip, string cant, string car,  string nad) 
    : ave(n,c,nom, tip, cant, car, nad)
  {
     npatas = n; 
     tipoanimal = c; 
     nombre = nom;
     tipo = tip;
     canta = cant;
     carroniero = car;
     nada = nad;
  }
};

class colibri : public ave
{
public:
  colibri(int n,  string c,  string nom, string tip, string cant, string car, string nad) 
    : ave(n, c, nom, tip, cant, car, nad)
  {
    npatas = n; 
     tipoanimal = c; 
     nombre = nom;
     tipo = tip;
     canta = cant;
     carroniero = car;
     nada = nad;
  }
};

// ... Mamíferos ...
class gato :  public mamifero
{
public:
  gato(int n,  string c,  string nom,  string tip) : mamifero(n, c, nom,  tip)
  {
    npatas = n;
    tipoanimal = c;
    nombre = nom;
    tipo = tip;
  }
};

class elefante :  public mamifero
{
public:
  elefante(int n,  string c,  string nom,  string tip) : mamifero(n, c, nom, tip)
  {
    npatas = n;
    tipoanimal = c;
    nombre = nom;
    tipo = tip;
  }
};

// ... Peces ...
class beta : public pez
{
public:
  beta(int n, string c, string nom, string tip, string nac) : pez(n, c, nom, tip, nac)
  {
    npatas = n;
    tipoanimal = c;
    nombre = nom;
    tipo = tip;
    nace = nac;
  }
};

class angel : public pez
{
public:
  angel(int n, string c, string nom, string tip, string nac) : pez(n, c, nom, tip, nac)
  {
    npatas = n;
    tipoanimal = c;
    nombre = nom;
    tipo = tip;
    nace = nac;
  }
};

// ... reptil ...
class lagartija : public reptil
{
public:
  lagartija(int n, string c, string nom, string tip, string ven, string tam) 
    : reptil(n, c, nom, tip, ven, tam)
  {
    npatas = n;
    tipoanimal = c;
    nombre = nom;
    tipo = tip;
    venenoso =ven;
    tamanio = tam;
  }
};

class tortuga : public reptil
{
public:
  tortuga(int n, string c, string nom,  string tip, string ven, string tam) 
    : reptil(n, c, nom, tip, ven, tam)
  {
    npatas = n;
    tipoanimal = c;
    nombre = nom;
    tipo = tip;
  }
};

// ... imprime ...
void Imprime(animal animal)
{
  animal.print();
}

// +++++++++++++++++++++++++
// +++++++++++++++++++++++++
int main()
{
  list<animal> * list1 = new list<animal>();

  string element1;
  string element2;

  // ......
  int count = 10;
  //animal* p[count];
  ave* b[count];
  mamifero* m[count];
  pez* pp[count];
  reptil* r[count];
  int i, j ;
  // ......

  int dim, choice, pos;
  dim = 0;

  do{
    cout << "Select a choice.\n";
    cout << "1. Print list\n";
    cout << "2. Delete an element of the list\n";
    cout << "3. Search an element of the list\n";
    cout << "4. Exit\n";
    cout << "Option: ";
    cin >> choice;
    cout << endl;

    switch(choice)
    {
      case 1:
      {
    cout << "Printing list:\n";
    cout << "Se van a añadir los siguientes elementos:\n";
    cout << "Animal: Ave. Patas: 2,  Tipo: aguila, alimento:carnivora, Canta: no, Carroñero: no, Nada:no\n";
    cout << "Animal: ave, Patas: 2, Tipo:colibri, alimento:herbívoro, Canta:no, Carroñero:no, Nada:no\n";
    cout << "Animal: mamifero, Patas: 4, Tipo: gato, alimento:carnivoro\n";
    cout << "Animal: mamifero, Patas: 4, Tipo: elefante\n";
    cout << "Animal: reptil, Patas: 4, Tipo: tortuga, alimento: herbivoro, Venenoso:no, Tamaño: grande\n";
    cout << "Animal: reptil,  Patas:4, Tipo: lagartija, alimento: insectivoro, Venenoso:no, Tamaño: pequeña\n";
    cout << "Animal: pez, Patas:0, Tipo: angel, Nacimiento: oviparo\n";
    cout << "Animal: pez, Patas:0, Tipo: beta, Nacimiento: oviparo\n";


    // ... agrega elementos a la lista ...
    list1->add_sort(Empleado("AAAA780920NA1", "Juan Perez"));
//  list1->add_sort(Empleado("WWWW500222HH3", "Ana Banana"));
//  list1->add_sort(Empleado("DUDE010101R0", "Miguel Rosas"));
//  list1->add_sort(Empleado("AUDE010101R1", "Pedro Pérez"));
//  list1->add_sort(Empleado("EEEE400412HN4", "Berenice Rosas"));
//  list1->add_sort(new ave(2,"ave","aguila", "carnívoro", "no", "no", "no"));
    list1->print();
    cout<<endl;
    break;
      }

      case 2:
      {
    dim++;
    if (dim == 1)
    {
      cout << "Element to delete: \n";

      list1->del_by_data(1);
      element1 = "";
      cout << endl;
      list1->print();
      cout << endl;
      cout << "\nElement deleted\n";
      cout<<endl;
    }
    if (dim == 2)
    {
      cout << "Element to delete: \n";

      list1->del_by_data(4);
      cout << endl;
      list1->print();
      cout << endl;
      cout << "\nElement deleted\n";
      cout << endl;
      dim = 0;
    }

    break;
      }

      case 3:
      {
    dim++;
    if (dim == 1)
    {
      cout << "Element to search: \n";
      list1->search("");
      element1 = "";
      cout << endl;
      list1->print();

      cout << endl;
    }
    if(dim == 2)
    {
      cout << "Element to search: \n";
      list1->search("");
      element1 = "";
      cout << endl;
      list1->print();

      cout << endl;
      dim = 0;
    }
    break;
      }
    }
  }while(choice != 4);



  return 0;
}

My problem is when adding data to the list, it only can add one data, when I take the rest out of the comments, it makes a segmentation fault.

What i'm doing wrong? or any idea on how to fix it?

[Banfa]

Line 171 is redundent, it repeats line 168.

The problem is line 169

  temp->previous = new_node->previous;

You are inserting the new node after temp so temp->previous should not change. new_node is ... well new, and so its previous pointer is set to NULL, you overwrite a value that does not need to be changed with NULL.

You actually need to alter the previous pointer of the now after temp in the orignal list to point at new_node.

Line 37 is strange, you set data to NULL but data is not a pointer it is an anmial and you can't assign NULL to it.

You have no polymorphism because of how you have declared your list

list<animal> * list1 = new list<animal>();

Instead of a list of base class pointers animal* which could point to all sorts of polymorphic animal derivertives you are actually storing an actua animal class that means anything you put in the list will be truncated to an animal rather than maintaining its full class.

You would be able to see what I meant if you fixed you list and output the contents.

[bernardo.mclobo]

Hi, thanks for replying.

Let me see if I understand, you say that my list is the culprit of all my miserable time ... Hmm ... then I need to fix it ... I will post my changes.