PROG 2 – Aufgabe 2 (Klasse Polynom)

Gleiche wie Aufgabe 1 nur das hier eine linear verkettete Liste mit Hilfskopfknoten benutzt wird.

Programmiertechnik 2 – Aufgabe 2 (Klasse Polynom)

Lösung:
mainAufgabe1.cpp:

// mainAufgabe1.cpp
// Hauptprogramm zu Aufgabe1
//
// O.Bittel; 9.4.2008
//

#include <iostream>
#include "polynom.h"

using namespace std;

int main()
{
  // Polynom p:
  cout << "===== Polynom p =====" << endl;
  Polynom p;
  p.set(5,1);
  p.set(2,3);
  p.set(3,-4);
  cout << "Ist:  "; p.print();
  cout << "Soll: 1x^5 - 4x^3 + 3x^2" << endl;
  cout << "Ist:  ";
  for (int i = 0; i <= p.getGrad(); i++)
    cout << i << ", " << p.get(i) << ", ";
  cout << endl;
  cout << "Soll: 0, 0, 1, 0, 2, 3, 3, -4, 4, 0, 5, 1" << endl;
  // cout << "Ist:  " << p.eval(2) << endl;
  // cout << "Soll: 12" << endl;
  cout << endl;

  // Polynom r:
  cout << "===== Polynom r =====" << endl;
  Polynom r;
  r.set(2,8);
  r.set(0,3);
  r.set(20,7);
  r.set(3,6);
  cout << "Ist:  "; r.print();
  cout << "Soll: 7x^20 + 6x^3 + 8x^2 + 3" << endl;
  cout << "Ist:  " << r.getGrad() << endl;
  cout << "Soll: 20" << endl;
  cout << endl;

  // Polynom s:
  cout << "===== Polynom s und r =====" << endl;
  Polynom s = r;
  s.set(20,0);
  s.set(3,0);
  s.set(2,5);
  cout << "Ist:  "; s.print();
  cout << "Soll: 5x^2 + 3" << endl;
  cout << "Ist:  " << s.getGrad() << endl;
  cout << "Soll: 2" << endl;
  cout << "Ist:  "; r.print();
  cout << "Soll: 7x^20 + 6x^3 + 8x^2 + 3" << endl;
  cout << endl;

  // Addition:
  cout << "===== Addition p + s =====" << endl;
  Polynom t;
  t = p;
  t.add(s);
  cout << "Ist:  "; t.print();
  cout << "Soll: 1x^5 - 4x^3 + 8x^2 + 3" << endl;
  cout << endl;
  cout << "===== Addition p + r =====" << endl;
  t = p;
  t.add(r);
  cout << "Ist:  "; t.print();
  cout << "Soll: 7x^20 + 1x^5 + 2x^3 + 11x^2 + 3" << endl;
  cout << endl;

  // Multiplikation:
  cout << "===== Multiplikation p * 2x^5 =====" << endl;
  t = p;
  t.multTerm(5,2);
  cout << "Ist:  "; t.print(); cout << endl;
  cout << "Soll: 2x^10 - 8x^8 + 6x^7" << endl;
  cout << endl;
  cout << "===== Multiplikation p * s =====" << endl;
  t = p;
  t.mult(s);
  cout << "Ist:  "; t.print();
  cout << "Soll: 5x^7 - 17x^5 + 15x^4 - 12x^3 + 9x^2" << endl;
  cout << endl;

  int i;
  cin >> i;
}

polynom.cpp:

// polynom.cpp
//
// O. Bittel; 8.10.2008
// Bearbeitet von Andreas Giemza; 17.03.2010

#include <iostream>
#include "polynom.h"

using namespace std;

Polynom::Polynom()
{
  // Lege den Hilfsknoten an und setzte next auf 0
  head = new Element;
  head->next = 0;
}

Polynom::~Polynom()
{
  // Lösche alle Elemente und den Hilfsknoten
  while (head != 0)
  {
    Element* q = head;
    head = head->next;
    delete q;
  }
}

void Polynom::set(int i, int c)
{
  // Die zwei Laufvariabeln initialisieren
  Element* zeiger1 = head;
  Element* zeiger2 = head->next;
  // Zum anzeigen ob schon was eingefügt wurde
  bool elementGeschrieben = false;

  if (c == 0)                                     // Schauen ob das Element entfernt wird was der Fall ist bei einem Koeffizient von 0
  {
    // Liste durchgehen
    while (zeiger2 != 0)
    {
      if (zeiger2->exponent == i)
      {
        // Das Element davor auf das Element danach zeigen lassen
        zeiger1->next = zeiger2->next;
        delete zeiger2;
        // Durchgehen abbrechen da das Element schon gelöscht wurde
        break;
      }

      // Nächstes Element auswählen
      zeiger1 = zeiger2;
      zeiger2 = zeiger2->next;
    }
  }
  else                                            // Es wird was hinzugefügt oder aktuallisiert
  {
    if (zeiger2 == 0)                             // Noch kein Element in der Liste, es wird am Anfang hinzugefügt
    {
      // Neues Element anlegen und hinzufügen
      Element* h = new Element;
      h->exponent = i;
      h->koeffizient = c;
      h->next = 0;
      zeiger1->next = h;
    }
    else
    {
      // Liste durchgehen
      while (zeiger2 != 0)
      {
        // Bis zu dem Punkt wo der Exponent von zeiger 2 kleiner ist als i
        if (i > zeiger2->exponent)                // Hier wird was in der Liste hinzugefügt/aktualisiert
        {
          if (i == zeiger1->exponent)             // Aktualisiert
          {
            // Den neune Koeffizienten schreiben
            zeiger1->koeffizient = c;
            // Es wurde was angelegt oder geschrieben und die schleife wird abgebrochen
            elementGeschrieben = true;
            break;
          }
          else                                    // Hinzugefügt
          {
            // Neues Element anlegen und hinzufügen
            Element* h = new Element;
            h->exponent = i;
            h->koeffizient = c;
            h->next = zeiger2;
            zeiger1->next = h;
            // Es wurde was angelegt oder geschrieben und die schleife wird abgebrochen
            elementGeschrieben = true;
            break;
          }
        }

        // Nächstes Element auswählen
        zeiger1 = zeiger2;
        zeiger2 = zeiger2->next;
      }

      // Keine Exponenten sind grö�er also wird das Element am Ende hinzugefügt
      if (!elementGeschrieben)                    // Am Ende der Liste hinzugefügt/aktualsiert
      {
        if (i == zeiger1->exponent)               // Aktualisiert
          // Den neune Koeffizienten schreiben
          zeiger1->koeffizient = c;
        else                                      // Hinzugefügt
        {
          // Neues Element anlegen und hinzufügen
          Element* h = new Element;
          h->exponent = i;
          h->koeffizient = c;
          h->next = zeiger2;
          zeiger1->next = h;
        }
      }
    }
  }
}

void Polynom::print()
{
  // Indikator für das erste Element
  bool erstesElement = true;

  // Laufvariabel
  Element* zeiger = head->next;

  // Liste durchgehen
  while (zeiger)
  {
    // Das erste Element ausgeben
    if (erstesElement)
    {
      cout << zeiger->koeffizient << "x^" << zeiger->exponent;
      erstesElement = false;
    }
    // Weitere Elemente ausgeben wo der Exponent nicht null ist
    else if (zeiger->exponent != 0)
    {
      // Sonderfall für negative Koeffizienten
      if (zeiger->koeffizient < 0)
        cout << " - " << zeiger->koeffizient*-1 << "x^" << zeiger->exponent;
      else
        cout << " + " << zeiger->koeffizient << "x^" << zeiger->exponent;
    }
    // Das letzte Element wo der Exponent null ist falls existent
    else
    {
      // Sonderfall für negative Koeffizienten
      if (zeiger->koeffizient < 0)
        cout << " - " << zeiger->koeffizient*-1;
      else
        cout << " + " << zeiger->koeffizient;
    }

    // Laufvariabel auf nächstes Element zeigen lassen
    zeiger = zeiger->next;
  }

  // Nächste Zeile am ende
  cout << 'n';
}

int Polynom::getGrad()
{
  // Da wir eine sortierte Liste haben ist der Exponent des ersten Element der Grad des Polynoms
  return head->next->exponent;
}

int Polynom::get(int i)
{
  // Laufvariabel
  Element* zeiger = head->next;

  // Gehe die Liste durch
  while (zeiger)
  {
    // Ausgeben des Koeffizienten an der Stelle i
    if (zeiger->exponent == i)
      return zeiger->koeffizient;

    // Laufvariabel aufs nächste Element zeigen lassen
    zeiger = zeiger->next;
  }

  // Wenn es kein Element mit dem Exponenten i gibt wird 0 ausgegeben
  return 0;
}

Polynom::Polynom(const Polynom& x)
{
  // Lege den Hilfsknoten an
  head = new Element;
  head->next = 0;

  // Laufvariabeln zum kopieren
  Element* zeiger1 = x.head->next;
  Element* zeiger2 = head;

  // Gehe die Liste durch
  while (zeiger1)
  {
    // Lege das Element an und kopiere die Werte aus x
    Element* h = new Element;
    h->exponent = zeiger1->exponent;
    h->koeffizient = zeiger1->koeffizient;
    h->next = zeiger1->next;
    zeiger2->next = h;

    // Laufvariabeln aufs nächste Element
    zeiger1 = zeiger1->next;
    zeiger2 = zeiger2->next;
  }
}

Polynom& Polynom:: operator=(const Polynom& x)
{
  // Selbstzuweisung unterbinden
  if (this != &x)
  {
    // Löschen des momentanen Inhalts (siehe Destruktor)
    Element* zeiger2 = head->next;

    while (zeiger2 != 0)
    {
      Element* q = zeiger2;
      zeiger2 = zeiger2->next;
      delete q;
    }

    head->next = 0;

    // Kopieren den neuen Inhalt (siehe Copy-Konstruktor)
    Element* zeiger1 = x.head->next;
    zeiger2 = head;

    while (zeiger1)
    {
      Element* h = new Element;
      h->exponent = zeiger1->exponent;
      h->koeffizient = zeiger1->koeffizient;
      h->next = zeiger1->next;
      zeiger2->next = h;

      zeiger1 = zeiger1->next;
      zeiger2 = zeiger2->next;
    }
  }

  // Neuen Inhalt zurückgeben
  return *this;
}

void Polynom::add(const Polynom& x)
{
  // Laufvariabel
  Element* zeiger = x.head->next;

  // Gehe x Liste durch
  while (zeiger)
  {
    // Füge neuen Inhalt hinzu
    set(zeiger->exponent, zeiger->koeffizient + get(zeiger->exponent));

    // Nächstes Element
    zeiger = zeiger->next;
  }
}

void Polynom::multTerm(int i, int c)
{
  // Laufvariabeln
  Element* zeiger1 = head;
  Element* zeiger2 = head->next;

  // Liste durchgehen
  while (zeiger2)
  {
    // Neues Element anlegen und füllen
    Element* h = new Element;
    h->exponent = i + zeiger2->exponent;
    h->koeffizient = c * zeiger2->koeffizient;
    h->next = zeiger2->next;
    zeiger1->next = h;

    // Altes löschen
    delete zeiger2;

    // Weiter gehts ...
    zeiger1 = h;
    zeiger2 = h->next;
  }
}

void Polynom::mult(const Polynom& x)
{
  // Templiste anlegen
  Polynom prod;
  // Templisten Laufvariabeln anlegen
  Element* tzeiger1;
  Element* tzeiger2;
  // Indikator ob was hinzugefügt wurde
  bool elementGeschrieben;

  // Zeiger variabeln
  Element* zeiger1 = head->next;
  Element* zeiger2 = x.head->next;

  // Gehe die Liste durch und für jedes Element gehe die x Liste durch
  while (zeiger1)
  {
    while (zeiger2)
    {
      // Element in der Templiste hinzufügen (siehe set)
      tzeiger1 = prod.head;
      tzeiger2 = prod.head->next;
      elementGeschrieben = false;

      if (tzeiger2 == 0)                          // Noch kein Element in der Liste, es wird am Anfang hinzugefügt
      {
        Element* h = new Element;
        h->exponent = zeiger1->exponent + zeiger2->exponent;
        h->koeffizient = zeiger1->koeffizient * zeiger2->koeffizient;
        h->next = 0;
        tzeiger1->next = h;
      }
      else
      {
        while (tzeiger2)
        {
                                                  // Hier wird was in der Liste hinzugefügt/aktualisiert
          if (zeiger1->exponent + zeiger2->exponent > tzeiger2->exponent)
          {
                                                  // Aktualisiert
            if (zeiger1->exponent + zeiger2->exponent == tzeiger1->exponent)
            {
              tzeiger1->koeffizient = tzeiger1->koeffizient + zeiger1->koeffizient * zeiger2->koeffizient;
              elementGeschrieben = true;
              break;
            }
            else                                  // Hinzugefügt
            {
              Element* h = new Element;
              h->exponent = zeiger1->exponent + zeiger2->exponent;
              h->koeffizient = zeiger1->koeffizient * zeiger2->koeffizient;
              h->next = tzeiger2;
              tzeiger1->next = h;
              elementGeschrieben = true;
              break;
            }
          }

          tzeiger1 = tzeiger2;
          tzeiger2 = tzeiger2->next;
        }

        if (!elementGeschrieben)                  // Am Ende der Liste hinzugefügt/aktualsiert
        {
                                                  // Aktualisiert
          if (zeiger1->exponent + zeiger2->exponent == tzeiger1->exponent)
            tzeiger1->koeffizient = tzeiger1->koeffizient + zeiger1->koeffizient * zeiger2->koeffizient;
          else                                    // Hinzugefügt
          {
            Element* h = new Element;
            h->exponent = zeiger1->exponent + zeiger2->exponent;
            h->koeffizient = zeiger1->koeffizient * zeiger2->koeffizient;
            h->next = tzeiger2;
            tzeiger1->next = h;
          }
        }
      }

      // Gehe zum nächsten Element der x Liste
      zeiger2 = zeiger2->next;
    }

    // Zeiger auf x Liste resetten
    zeiger2 = x.head->next;
    // Gehe zum nächsten Element der Liste
    zeiger1 = zeiger1->next;
  }

  // Alte Liste löschen (siehe Destruktor)
  zeiger2 = head->next;

  while (zeiger2 != 0)
  {
    Element* q = zeiger2;
    zeiger2 = zeiger2->next;
    delete q;
  }

  head->next = 0;

  // Templiste zur neuen Liste machen
  *this = prod;
}

/*
void Polynom::mult(const Polynom& p)
{
Polynom prod;
for (int i = 0; i <= p.getGrad(); i++)
{
Polynom t = *this;
t.multTerm(i,p.a[i]);
prod.add(t);
}
*this = prod;
}
*/

polynom.h:

// polynom.h
// Andraes Giemza
// 17.03.2010

#ifndef POLYNOM_H
#define POLYNOM_H

class Polynom
{
  public:
    Polynom();
    Polynom(const Polynom& x);
    ~Polynom();
    Polynom& operator=(const Polynom& x);

    int getGrad();
    void set(int i, int c);
    int get(int i);
    void add(const Polynom& x);
    void mult(const Polynom& x);
    void multTerm(int i, int c);
    void print();

  private:
    // Element zum speichern der Daten
    struct Element
    {
      Element* next;
      int koeffizient;
      int exponent;
    };

    // Zeiger auf den Hilfsknoten
    Element* head;
};
#endif

Makefile:

# File: Makefile fuer Aufgabe1
#
# Aufruf:
#
#		make
#
# Author: Oliver Bittel
# Date: 12.09.2007

# Definitions:
CC = g++ -g   # -g wird nur fuer Debugger benoetigt!
OBJ = mainAufgabe1.o polynom.o
BIN = aufg2

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

mainAufgabe1.o: mainAufgabe1.cpp polynom.h
	$(CC) -c mainAufgabe1.cpp

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