PROG 2 – Aufgabe 3 (Klassenschablone Set)

Übungsaufgabe zu Klassenschablonen.

Programmiertechnik 2 – Aufgabe 3 (Klassenschablone Set)

Lösung:
main.cpp:

// main.cpp
//
// Andreas Giemza, FH KN
// 16.04.2010

#include <iostream>

#include "set.h"
#include "point.h"

using namespace std;

int main()
{
  cout << "===== Set<int> s =====n";

  Set<int> s;

  s.insert(1);
  s.insert(2);
  s.insert(3);
  s.insert(4);
  s.insert(5);
  s.insert(6);
  s.insert(6);
  s.insert(5);
  s.insert(4);
  s.insert(3);
  s.insert(2);
  s.insert(1);
  s.insert(6);

  cout << "Ist:  "; s.print();
  cout << "Soll: 1, 2, 3, 4, 5, 6n";

  cout << "n===== Set<string> t =====n";

  Set<string> t;

  t.insert("Haus");
  t.insert("Maus");
  t.insert("Laus");
  t.insert("Argwohn");
  t.insert("Aal");
  t.insert("Haus");
  t.insert("Zunder");
  t.insert("Aal");
  t.insert("Klaus");
  t.insert("Maus");
  t.insert("Laus");
  t.insert("Haus");

  cout << "Ist:  "; t.print();
  cout << "Soll: Aal, Argwohn, Haus, Klaus, Laus, Maus, Zundern";

  cout << "n===== Set<Point> u =====n";

  Set<Point> u;

  u.insert(Point(2.3, 4.5));
  u.insert(Point(3.4, 5.6));
  u.insert(Point(1.2, 3.4));
  u.insert(Point(2.3, 4.5));
  u.insert(Point(1.2, 3.3));
  u.insert(Point(2.2, 4.8));
  u.insert(Point(2.3, 1.6));
  u.insert(Point(2.3, 4.9));
  u.insert(Point(2.3, 33.6));

  cout << "Ist:  "; u.print();
  cout << "Soll: (1.2, 3.3), (1.2, 3.4), (2.2, 4.8), (2.3, 1.6), (2.3, 4.5), (2.3, 4.9), (2.3, 33.6), (3.4, 5.6)n";
}

set.h:

// set.h
//
// Andreas Giemza, FH KN
// 16.04.2010

#ifndef SET_H
#define SET_H

using namespace std;

template <class T>
class Set
{
  public:
    Set();
    ~Set();

    virtual void insert(T x);
    virtual void print();

  private:
    struct Element
    {
      Element* next;
      T content;
    };

    Element* head;
};

template <class T>
Set<T>::Set()
{
  // Leere Liste erstellen
  head = 0;
}

template <class T>
Set<T>::~Set()
{
  // Geht die Liste solange durch bis wir am Ende angekommen sind
  while (head != 0)
  {
    Element* q = head;
    head = head->next;
    delete q;
  }
}

template <class T>
void Set<T>::insert(T x)
{
  // Sonderfall falls noch nichts in der Liste ist
  if (head == 0)
  {
    Element* q = new Element;
    q->content = x;
    q->next = 0;
    head = q;
  }
  // Sonderfall falls es gleich am Anfang der Liste eingef�¼gt wird
  else if (head->content > x)
  {
    // Schaut ob es nicht schon in der Liste vorhanden ist
    if (head->content != x)
    {
      // Element wird eingef�¼ht
      Element* q = new Element;
      q->content = x;
      q->next = head;
      head = q;
    }
  }
  // ansonsten wird es irgendwo inder Liste oder am Ende angeh�¤ngt
  else
  {
    // Temp Zeiger
    Element* p = head;

    // Geht die Liste durch bis das n�¤chste Element gr�¶�Ÿer gleich x ist
    while (p->next != 0 && x >= p->next->content)
      p = p->next;

    if (p->content != x)
    {
      Element* q = new Element;
      q->content = x;
      q->next = p->next;
      p->next = q;
    }
  }
}

template <class T>
void Set<T>::print()
{
  // Schaut ob wir nicht schon am letzten Element sind
  if (head != 0 && head->next != 0)
  {
    // Gibt das erste aus
    cout << head->content;

    // Zeiegr auf n�¤chste
    Element* p = head->next;

    // Geht die Liste durch bis man am Ende ist
    while (p != 0)
    {
      // und gibt immer ein element mit Komma aus
      cout << ", " << p->content;
      p = p->next;
    }
  }
  // Sonderfall f�¼r das letzte Element (damit nicht am Ende noch ein Komma ist)
  //else if (head != 0 && head->next == 0)
  //cout << head->content;

  cout << 'n';
}
#endif

point.cpp:

// point.cpp
//
// Andreas Giemza, FH KN
// 27.04.2010

#include "point.h"

ostream& operator<<(ostream& s, const Point& z)
{
  s << '(' << z.x << ", " << z.y << ')';

  return s;
}

bool operator==(Point a, Point b)
{
  // Nur gleich wenn der x UND der y Wert gleich sind
  return ((a.x == b.x) && (a.y == b.y));
}

bool operator!=(Point a, Point b)
{
  // Es muss sich nur einer unterscheiden damit es schon ungleich ist
  return ((a.x != b.x) || (a.y != b.y));
}

bool operator>(Point a, Point b)
{
  // Damit es gr�¶�Ÿer ist muss der x Wert gr�¶ser sein ODER x ist gleich aber dann ist der y Wert gr�¶�Ÿer
  return ((a.x > b.x) || (a.x == b.x) && (a.y > b.y));
}

bool operator>=(Point a, Point b)
{
  // Damit es gr�¶�Ÿergleich  ist muss der x Wert gr�¶ser sein ODER x ist gleich aber dann ist der y Wert gr�¶�Ÿergleich
  return ((a.x > b.x) || (a.x == b.x) && (a.y >= b.y));
}

point.h:

// point.h
//
// Andreas Giemza, FH KN
// 16.04.2010

#ifndef POINT_H
#define POINT_H

#include <iostream>

using namespace std;

// Die Point Struktur
struct Point
{
  Point(double a=0, double b=0) : x(a), y(b) {}
  double x;
  double y;
};

// Prototypen der angepassten Operatoren
ostream& operator<<(ostream& s, const Point& z);
bool operator==(Point a, Point b);
bool operator!=(Point a, Point b);
bool operator>(Point a, Point b);
bool operator>=(Point a, Point b);
#endif

Makefile:

# Author: Andreas Giemza
# Date: 12.09.2007

CC = g++ -g
OBJ = main.o point.o
BIN = aufg3

$(BIN): $(OBJ)
	$(CC) -o $(BIN) $(OBJ)

main.o: main.cpp point.h set.h
	$(CC) -c main.cpp

point.o: point.cpp point.h
	$(CC) -c point.cpp