9. ANSI-C-Aufgabe: Baumstrukturen

Aufgabenstellung:

Bäume zur Simulation eines Schneeballsystems in der Vermarktung von salzigen Schokoladenbällchen

In dieser Übung wollen wir einmal nachvollziehen, wie ein Schneeballsystem bei der Vermarktung von beliebten Produkten funktionieren kann und wie man es mit Hilfe von Baumstrukturen gekonnt verwalten kann.


Das besondere an einem Schneeballsystem ist, daß ein einzelner Klinkenputzer Subunternehmer einstellen kann, die dann für ihn losziehen und Klinken putzen. Jeder Subunternehmer darf dann, weil der ursprüngliche Klinkenputzer so gütig war, ihm Arbeit zu geben, diesem einen gewissen Anteil seines Profits, quasi als Dankeschön, abgeben. Der Subunternehmer selber darf selbstverständlich auch wieder Subunternehmer einstellen, die Sub-Subunternehmer. Die Sub-Subunternehmer drücken dann an den Subunternehmer ab, der von diesem Gewinn dann wieder seinen Teil an den ursprünglichen Klinkenputzer abdrückt.

Es ist also leicht zu sehen, daß diese Struktur am passensten durch eine Baumstruktur abgebildet werden kann, die sich dynamisch verwalten läßt.

Für den Fall, daß denn der Chefkoch mal seine super-leckeren salzigen Schokoladenbällchen vermarkten möchte, könnte man zu einem solchem Baum kommen:


Man könnte sich nun allerlei passende Operationen auf diesem Baumkonstrukt vorstellen, die den Ablauf eines Schneeballsystems simulieren. So müssen Personen eingestellt werden, die die Möglichkeit haben müssen, Profit zu erwirtschaften und auch die Möglichkeit haben, neue Subunternehmer einzustellen. Auf der anderen Seite müssen diese auch wieder entlassen oder durch andere ausgetauscht werden können.

Die Deklaration der entsprechenden Funktionen, wie auch die dazu notwendigen Datenstrukturen, findet ihr in diesem Headerfile.

Anforderungen

• Es sind die Funktionen aus dem Headerfile vollständig zu implementieren
  
  
• Erzeugt mit Hilfe der von euch erstellten Sourcefile(s) eine Bibliothek mit dem Namen libtree.a
  
  
• Erstellt euch ein Testprogramm, daß alle Möglichkeiten testet - ohne Testprogramm von euch, keine Abnahme!

Hinweise

• Prüft die Gültigkeit der Parameter (keine NULL-Zeiger, kein negativer Profit, keine doppelten Namen im Baum).
  Wie im Fehlerfall verfahren werden soll, ist in der zugehörigen Funktionsbeschreibung erläutert. Ist dort kein Fehlerfall angegeben, so wird 0 zurückgeliefert. In dem Fall, daß ein kompletter Baum eingefügt wird und in dem einzufügenden eine Node denselben Namen hat, wie im Zielbaum, wird diese Node aus dem einzufügenden Baum gelöscht (mit tree_removeNode).
  
  
• Gebt den Speicher wieder frei (wenn Nodes entfernt werden, Referenzen für immer gelöscht werden,...)
  
  
• Beachtet, daß zwei Knoten auch gleich sind, wenn ihre Werte (Namen) gleich sind.
  
  
• Ob ihr Namen case-sensitive oder case-insensitive gleich betrachtet, ist euch überlassen. Dieses spielt im Rahmen der Aufgabenstellung keine Rolle.
  
  
• Implementiert euch Hilsfunktionen, die die Arbeit erleichtern können, wie z.B.
  int isEqual(t_tree* tree1, t_tree* tree2)
int isNameIn(t_tree* tree, char* name)
t_tree* getNodeBefore(t_tree* tree, t_tree* node)
  
  
• Der obige Baum hätte zum Beispiel aus folgender Aufrufreihenfolge resultieren können:
  

      t_tree* myTree;
      myTree=tree_makeTree("Chef",0.0f);
      myTree=tree_appendTree(myTree,myTree,tree_makeTree("Eric Cartman",0.0f));
      myTree=tree_appendTree(myTree,myTree,tree_makeTree("Big Gay Al",0.0f));
      tempTree=tree_appendTree(myTree,tree_findName(myTree,"Eric Cartman"),
                               tree_makeTree("Stan Marsh",0.0f));
      tempTree=tree_appendTree(myTree,tree_findName(myTree,"Eric Cartman"),
                               tree_makeTree("Kenny McCormick",0.0f));
      tempTree=tree_appendTree(myTree,tree_findName(myTree,"Stan Marsh"),
                               tree_makeTree("Wendy Testaburger",0.0f));
      tempTree=tree_appendTree(myTree,tree_findName(myTree,"Wendy Testaburger"),
                               tree_makeTree("Kyle Broflovski",0.0f));
      tempTree=tree_appendTree(myTree,tree_findName(myTree,"Big Gay Al"),
                               tree_makeTree("Grandpa Marsh",0.0f));
      tempTree=tree_appendTree(myTree,tree_findName(myTree,"Grandpa Marsh"),
                               tree_makeTree("Mr. Garrison",0.0f));
      tempTree=tree_appendTree(myTree,tree_findName(myTree,"Grandpa Marsh"),
                               tree_makeTree("Mr. Slave",0.0f));
      tempTree=tree_appendTree(myTree,tree_findName(myTree,"Mr. Garrison"),
                               tree_makeTree("A Christina Aguilera Monster",
                                             0.0f));
      tempTree=tree_appendTree(myTree,tree_findName(myTree,"Mr. Garrison"),
                               tree_makeTree("Mr. Hankey the Christmas Poo",
                                             0.0f));
      myTree=tree_updateProfit(myTree,"Chef",100.0);
      myTree=tree_updateProfit(myTree,"Eric Cartman",200.0);
      myTree=tree_updateProfit(myTree,"Stan Marsh",400.0);
      myTree=tree_updateProfit(myTree,"Wendy Testaburger",800.0);
      myTree=tree_updateProfit(myTree,"Kyle Broflovski",1600.0);

Gutes Gelingen!

 

Download Beispiel-Lösungsvorschlag, Quelltext inkl. Projektdateien für VC6 (ZIP-Archiv, 58 KB)

 

Zur Aufgaben-Übersicht

 

Gefällt dir die C Übungsaufgabe? Schreibe doch einen Kommentar...

Kommentare 0