C-Uebung

Aufgabe "Structs"

← KDevelop & QtCreator | ● | elektronische Abgabe →

Präsenzübung:

Für diese Aufgabe dürfen Sie die agile Softwareentwicklungsmethode “Pair-Programming” anwenden, d.h. Sie suchen Sich einen Partner, mit dem Sie die Aufgabe jeweils abwechselnd zusammen aber trotzdem eigenständig bearbeiten.

a) Organisieren Sie Ihre Software-Entwicklung nach folgender empfohlener Vorgehensweise:

Es ist empfehelnswert, keine weiteren neuen Programme zu schreiben, sondern lieber ein bereits bestehendes Programm um ein weiteres Nebenmodul zu erweitern und das Hauptmodul entsprechend anzupassen. D.h. fügen Sie zuallererst ein neues Nebenmodul hinzu, welches fürs Erste nur eine leere neue Prozedur enthält und rufen Sie diese Prozedur im Hauptmodul auf.

Beim Entwickeln orientiert man sich in der Regel an “echten” Softwareprojekten: Bei diesen entwickelt man den jeweils aktuellen Stand des Programms im Verzeichnis trunk kontinuierlich weiter. Man committet den “trunk” regelmäßig - mindestens einmal am Tag. Ihre Ordnerstruktur sieht dann wie folgt aus: 

repository ->
              trunk ->
                       *.cpp *.h CMakeLists.txt

Ist ein gewisser Entwicklungsstand erreicht, z.B. wenn ein gewisser Meilenstein oder Versionssprung erreicht wurde, dann friert man diesen Zustand durch Anfertigen einer Kopie ein. Dies nennt man auch einen sog. tag (Kopie einer bestimmten Version des jeweiligen Entwicklungsstandes).

Bei den Ãœbungsaufgaben ist ein solcher Meilenstein bei der Abgabe der jeweiligen Aufgabe erricht. Dann fertigen sie einen tag an, indem Sie Ihren fertigen Code aus dem “trunk” in ein entsprechendes Verzeichnis, z.B. “4” für die aktuelle Aufgabe kopieren. Benutzen Sie dazu SVN:

  • cd repository
  • svn stat -v trunk
  • svn commit trunk -m “commit log”
  • svn copy trunk 4
  • svn commit 4 -m “commit log”

Danach haben Sie folgende Ordnerstruktur: 

repository ->
              trunk ->
                       *.cpp *.h CMakeLists.txt
              4     ->
                       *.cpp *.h CMakeLists.txt

b) Definieren Sie in einem neuen Nebenmodul eine Person als Struktur vom Datentyp Person mit den folgenden Komponenten:

  • Vorname, Name (max. jeweils 50 Zeichen → z.B. char name[50])
  • Geburtsdatum (als Unterstruktur mit den Komponenten Tag/Monat/Jahr)

c) Deklarieren sie ein Array mit 10 Personen und initialisieren Sie es mit folgenden Personendaten:

  • Zahara Jolie-Pitt, 8.1.2005
  • Forest Whitaker, 15.7.1961
  • Tricia Vessey, 8.10.1972
  • William H. Macy, 13.3.1950
  • Steve Buscemi, 13.12.1957
  • Frances McDormand, 23.6.1957
  • Peter Stormare, 27.8.1953
  • Jeff Bridges, 4.12.1949
  • John Goodman, 20.6.1952
  • Georg Clooney, 6.5.1961

d) Testen Sie Ihr Personen-Array, indem Sie alle 10 Geburtsjahre mit einer Funktion “person_print” ausgeben.

e) Schreiben Sie eine Suchfunktion “person_search”, welche in dem Personen-Array nach einem bestimmten Personennamen sucht und einen Zeiger auf die gefundene Person zurückgibt oder NULL wenn die Suche erfolglos war. Als Argument soll der Name der gesuchten Person (d.h. zwei Zeichenketten) übergeben werden:

Person *person_search(const char *name, const char *surname);
[Get Code]

Hinweis: Zeichenkettenvergleich mit strcmp(a,b)==0 !

f) Testen Sie Ihre Funktion, in dem sie für obigen Beispieldatensatz eine Suche nach Tricia Vessey durchführen und deren Geburtsdatum ausgeben (in main()).

Hausaufgabe:

g) Schreiben Sie den Code so um, dass Sie beliebig viele weitere Personen hinzufügen können. Sie gehen nach folgender Strategie vor:

Sie benötigen eine Einfüge-Funktion “person_add”, die ein weiteres Element an ein dynamisches Array anhängt:

void person_add(const Person &p);
[Get Code]
  • Dazu verwenden Sie einen modullokalen Zeiger auf ein Personen-Array (static Person *person_list), das mit new erzeugt wird und eine Variable n, welche die Anzahl der aktuell gespeicherten Personen beinhaltet. Anfangs ist das Personenarray leer, d.h. die Personenanzahl ist 0 und der Zeiger ist NULL.
  • Für eine neu dazukommende Person, muss ein neues größeres Array erzeugt werden, die alten Daten kopiert werden, und die neue Person muss ans Ende des Arrays kopiert werden. Vergessen Sie nicht den Speicher des alten Arrays wieder zu löschen.

h) Testen Sie Ihr dynamisches Array wiederum für die 10 obigen Beispielpersonen und zusätzlich für Ihre eigene Person, in dem Sie jede Person der Reihe nach einfügen. Suchen Sie dann nach Ihrem eigenen Geburtsdatum und geben Sie es aus!

Zusatzfragen:

i) Ist dieses Vorgehen performant? D.h. wie lange würde es dauern nicht 10 Personen, sondern die ca. 25000 Personen aus dieser Liste von berühmten Persönlichkeiten in Ihre Geburtstagsdatenbank einzufügen und nach dem Geburtsdatum von Albert Einstein zu suchen?

j) Eine Möglichkeit, obiges Verfahren zu beschleunigen, besteht darin, die vorhandenen Speicherelemente zu verdoppeln, wenn der Platz nicht mehr ausreicht. Dadurch muss nicht bei jedem Einfügen das ganze Array kopiert werden. Diese Strategie ist erheblich schneller, d.h. die Einfügeoperation geschieht im Durchschnitt in “fast konstanter Zeit”, verschwendet jedoch im Durchschnitt 50% Speicherplatz.

k) Kann man nun eine Person effizient suchen bzw. löschen?

l) Kennen Sie Datenstrukturen, welche für die obige Aufgabe besser geeignet sind, d.h. Datenstrukturen, die platzsparender und/oder effizienter sind?

Zusatzaufgabe:

  • Einlesen der Personen aus celebrity.txt und Suchen nach Albert Einstein:
#include <stdio.h>
#include <assert.h>

void read_celebrities()
{
   FILE *file = fopen("celebrity.txt", "rb");
   assert(file);

   struct Person p;

   while (fscanf(file, "%s %d/%d/%d", p.name, &p.birthday.month, &p.birthday.day, &p.birthday.year) == 4)
   {
      int len=strlen(p.name);
      for (int i=0; i<len; i++)
         if (p.name[i]==';')
         {
            p.name[i]='\0';
            strcpy(p.surname, &p.name[i+1]);
         }

      person_add(p);
   }

   fclose(file);
}

void main()
{
   read_celebrities();
   Person *p = person_search("Albert", "Einstein");
   ...
}
[Get Code]


← KDevelop & QtCreator | ● | elektronische Abgabe →

Options: