Bsp. Linked-List als Template-Klasse

Die vorhin vorgestellte Klasse wird in eine Template-Klasse umgewandelt. Im folgenden Bsp. werden dynamisch alloziierte Objekte der Klasse ``String'' in der ``double linked list'' verwaltet.

string.h

#include <iostream.h>
extern "C"
{
  #include <string.h> // strcpy(), ...
  #include <stdlib.h> // atof(), ...
  #include <stdio.h> // sprintf()
}

class String
{
public:
  String(char *s="");
  String(char*, char*);
  String(float);
  String(int);
  String(const String&); // copy constructor
  ~String();
  String& String::operator = (const String&);
  int String::operator == (const String&);
  String& String::operator += (const String&);
  friend String operator + 
    (const String&, const String&);
  friend ostream& operator << (ostream&, String&); 
  friend istream& operator >> (istream&, String&);
  operator int();
  operator float();  
private:
  char *the_string;
};

string.cc

#include "string.h"

String::String(const String& c)
{
  the_string = new char [strlen(c.the_string)+1];
  strcpy(the_string, c.the_string);
  cerr << "Copy constructor called! "
       << "the_string is:" << c.the_string << endl;
}

String::String(char *s)
{
  the_string = new char [strlen(s)+1];
  strcpy(the_string, s);
}

String::~String()
{
  cerr << "Destruktor called! "
       << "the_string is:" << the_string <<endl;
  delete the_string;
}

String::String(char *s, char *t)
{
  the_string = new char [strlen(s)+strlen(t)+1];
  strcpy(the_string, s);
  strcat(the_string, t);
}

String& String::operator = (const String& t)
{
  if ( this == &t ) return(*this);
  delete the_string;
  the_string = new char [strlen(t.the_string)+1];
  strcpy(the_string, t.the_string);
  return(*this);
}

int String::operator == (const String& t)
{
  return(!strcmp(the_string, t.the_string));
}

String& String::operator += (const String& t)
{
  char *cptr;
  cptr = new char [strlen(the_string)+
         strlen(t.the_string)+1];
  strcpy(cptr, the_string);
  strcat(cptr, t.the_string);  
  delete the_string;
  the_string = cptr;
  return(*this);
}

String operator + (const String& s, const String& t)
{
  String ret(s.the_string, t.the_string);
  return ret;
}

ostream& operator << (ostream& s, String& r)
{ return s << r.the_string; }

istream& operator >> (istream& s, String& r)
{ char buf[100];
  s >> buf;
  r = buf;
  return s;
}

String::String(float f)
{
  char buf[128];
  sprintf(buf, "%e", f);
  the_string = new char [strlen(buf)+1];
  strcpy(the_string, buf);
}

String::String(int i)
{
  char buf[128];
  sprintf(buf, "%i", i);
  the_string = new char [strlen(buf)+1];
  strcpy(the_string, buf);
}
String::operator int()
{
  if(the_string) 
    return atoi(the_string);
  else return 0;
}

String::operator float()
{
  if(the_string) 
    return atof(the_string);
  else return 0.0;
}

template-list.cc

#include <iostream.h>
#include <iomanip.h>
#include <new.h>
#include "string.h"
extern "C" 
{
  // for exit() 
 #include <stdlib.h>
  // for strcpy() and strlen()
 #include <string.h>  
} 

// forward reference
template <class T> class List;

template <class T>
class Element
{
public:
  friend class List<T>; 
  Element(T*);
  ~Element();
  void Print();
private:
  T* data;
  Element<T> *next;
  Element<T> *prior;
};

template <class T>
Element<T>::~Element()
{
  cerr << "Destructor for Element called: "
       << endl;
  if (this)
  {
    cerr << this->data << endl;
    if (this->data)
      delete this->data;
  }
}

template <class T>
Element<T>::Element(T* data)
{
  this->data = new T(*data);
  next = prior = NULL;
}

template <class T>
void Element<T>::Print()
{
  cout << *data;
}

template <class T>
class List 
{
public:
  List(T*);
  ~List();
  Element<T>* First();
  Element<T>* Next(Element<T> *p);
  Element<T>* Prior(Element<T> *p);
  int Put_Begin(T*);
  int Insert(T*, Element<T> *p); // insert after p
  void Delete(T*);
  Element<T>* Find(T*);
  void Print();
private:
  Element<T> *first;
  Element<T> *last;
  int Equal(T* t, T* s);
};

template <class T>
void List<T>::Print()
{
  Element<T> *e = first;
  while(e)
  {
    cout << setiosflags(ios::showbase | ios::uppercase)
         << "Element at " << hex << e
         << " with value " << (*e->data)
         << " next: " << e->next
         << " prior: " << e->prior << endl;
    
    e = e->next;
  }
}

template <class T>
void List<T>::Delete(T* data)
{
  Element<T> *found = Find(data);
  if (found)
  {
    if ((found == first) && (found == last))
      first = last =  NULL;
    else if (found == first)
    {
      first = found->next;
      if (first)
        first->prior = NULL;
    }
    else if (found == last)
    {
      last = found->prior;
      last->next = NULL;
    }
    else
    {
      (found->next)->prior = found->prior;
      (found->prior)->next = found->next;
    }
    delete found;
  }
}

template <class T>
List<T>::~List()
{
  cerr << "Destructor for List called: "
       << endl;

  Element<T> *tmp, *e = first;
  while (e)
  {
    tmp = e->next;
    delete e;
    e = tmp;
  }
}

template <class T>
List<T>::List(T* data)
{
  last = first = new Element<T>(data);
  last->prior = last->next = NULL;
}

template <class T>
int List<T>::Put_Begin(T* data)
{
  Element<T> *n = new Element<T>(data);
  n->prior = NULL;
  if (first)
    first->prior = n;
  n->next = first;
  first = n;
  return 1;
}

template <class T>
int List<T>::Equal(T* t, T* s)
{
  return *t == *s;
}

template <class T>
Element<T>* List<T>::Find(T* data)
{
  Element<T> *e = first;
  while(e)
  {
    if (Equal(data, e->data))
      return e;
    else 
      e = e->next;
  }
  return NULL;
}

template <class T>
Element<T>* List<T>::First()
{
  return first;
}

template <class T>
Element<T>* List<T>::Next(Element<T> *p)
{
  if (p)
    return p->next;
  else
    return p;
}

template <class T>
Element<T>* List<T>::Prior(Element<T> *p)
{
  if (p)
    return p->prior;
  else
    return p;
}

void NoSpace()
{
  cerr << "New Failed" << endl;
  exit(1);
}

int main()
{

  // Rufe die Funktion NoSpace() auf
  // wenn new keinen freien Speicher 
  // belegen kann
  set_new_handler(NoSpace);

  char c;
  Element<String> *e;
  String tmp = "first";
  List<String> *l1 = new List<String> (&tmp);

  cout << "** Double Linked List Example **" <<endl;
  while(1)
  {
    cout << "1) enter new value;" << endl;
    cout << "2) find value;" << endl;
    cout << "3) display linked list;" << endl;
    cout << "4) delete element;" << endl;
    cout << "9) end program;" << endl;
    cin >>c;
    switch(c)
    {
    case '1':
      cout << "enter new value ";
      cin >> tmp;
      l1->Put_Begin(&tmp); 
      break;
    case '2':
      cout << "enter value ";
      cin >> tmp;
      e = l1->Find(&tmp);
      if (e)
      {
        cout << "habe ";
        e->Print();
        cout << " gefunden" << endl;
      }      
      else
        cout << tmp << " wurde nicht gefunden" << endl;
      break;
    case '3':
      l1->Print();
      break;
    case '4':
      cout << "enter value ";
      cin >> tmp;
      l1->Delete(&tmp);
      break;
    case '9':
      delete l1;
      exit(0);
    default:
      cout << "unkown command!" << endl;    
    }
  }
  return 0;
}

// cxx -define_templates
// g++