8. ANSI-C-Aufgabe: Dynamische Listen

Aufgabenstellung:

Listen für Strings und Zahlen

Wir wollen in dieser Übung eine einfach verkettete Ringliste zum Speichern von Texten und Zahlen entwickeln. Damit wir diese Liste weiterverwenden können, werden wir diese als Bibliothek erzeugen.


Wie wir Bibliotheken erzeugen, haben wir in der letzten Übung schon gelernt, deshalb können wir dieses Wissen gleich wieder anwenden.

Unsere Liste soll nach folgender Grafik aufgebaut sein:


Das heißt, unsere Liste besteht aus x Elementen, das letzte Element zeigt immer auf das erste Element, und unser Listen-Zeiger zeigt immer auf das letzte Element. Auf diese Art haben wir immer das letzte und erste Element zugreifbar (listenpointer == letzes Element, listenpointer->next == erstes Element).

Anforderungen

• Es sollen folgende Datenstrukturen verwendet werden:
  
  • Daten-Element
    

    typedef struct {
      char* text;
      int num;
    } t_data;

  • Listen-Element
    

    typedef struct t_node {
      t_data data;
      struct t_node* next;
    } t_list;

• Es sollen folgende Funktionen implementiert werden:
  
  • t_list* list_mkEmpty(void)
    Erstellt eine neue, leere Liste und liefert diese zurück.
    
    
  • t_list* list_append(t_list* list, int num, char* text)
    Hängt ein neues Listenelement an die Liste list an und liefert die Liste zurück.
    
    
  • t_list* list_insert(t_list* list, t_list* after, int num, char* text)
    Fügt ein Element hinter das Element after in die Liste list ein. Diese Funktion soll durch geschicktes Aufrufen von list_append realisiert werden.
    
    
  • int list_inList(t_list* list, t_list* elem)
    Wenn das Element elem in der Liste list enthalten ist, liefert diese Funktion 1 zurück, sonst 0.
    
    
  • t_list* list_findText(t_list* list, char* text)
    Prüft, ob es ein Element mit dem Text text in list gibt. Gibt einen Zeiger auf das Element zurück, oder NULL. Existieren mehrere Elemente mit diesem Text, so wird das Element zurückgeliefert, das sich am weitesten vorne in der Liste befindet.
    
    
  • t_list* list_exchange(t_list* list, t_list* x, t_list* y)
    Tauscht die Reihenfolge der Elemente x und y in list und gibt den Listenzeiger zurück.
    
    
  • void list_extendElement(t_list* element, char* extratext)
    Hängt an den Text in dem Listenelement element den Text extratext an.
    
    
  • t_list* list_concat(t_list* list1, t_list* list2)
    Diese Funktion fügt die Listen list1 und list2 zusammen und liefert einen Listenzeiger zurück.
    
    
  • t_list* list_remove(t_list* list, t_list* element)
    Entfernt das Element element aus der Liste list und gibt dann den Listenzeiger zurück.
    
    
  • void list_destroy(t_list* list)
    Löscht die gesamte Liste list. Benutzt die Funktion list_remove um das zu realisieren.
    
    
• Der Rückgabewert t_list soll immer ein Zeiger auf das letzte Element der Liste sein (bei einer leeren Liste natürlich NULL).
  
  
• Erstellt aus eurer Lösung eine Bibliothek libmylist.a (unter Unix) bzw. mylist.lib (unter Windows) und stellt eine Headerdatei mylist.h mit den Prototypen der o.g. Funktionen zur Verfügung. Die Quelltextdatei für eure Lösung muß mylist.c heißen.
  
  
• Zum Bestehen dieser Aufgabe müßt ihr neben einem Makefile auch einen eigenen Test vorweisen der alle Listenfunktionen demonstriert.

Hinweise

• Die leere Liste wird durch einen NULL-Zeiger repräsentiert.
  
  
• Da unser Listenzeiger ja per Definition auf das letzte Element der Liste zeigen soll, und wir eine Ringliste haben, brauchen wir für einen Zugriff auf das erste Element lediglich listpointer->next zu verwenden. Denkt aber trotzdem an eine Gültigkeitsprüfung (leere Liste!)
  
  
• Bei der Funktion list_exchange ist folgendes zu beachten:
  
  • Die Elemente x und y müssen in der Liste nicht direkte Nachbarn sein.
  • Bevor irgendetwas getauscht wird, soll erst mit list_inList geprüft werden, ob beide Elemente in der Liste vorhanden sind.
  • Sollte ein Element nicht in der Liste vorhanden oder ungültig sein, dann wird nichts getauscht und nur der Listenzeiger zurückgegeben.
• Die Funktion list_extendElement soll den übergebenen Text an den Text im übergebenen Element anhängen. Ihr müßt also den reservierten Speicher mit Hilfe von realloc vergrößern.
  
  
• Nachträglicher Hinweis: 23.05.2003 (kn)
  Die Funktion list_insert ruft intern die Funktion list_append auf. Das heißt, daß in jedem Fall eine gültige Liste zurückgegeben wird - nur die Position des Listenzeigers, den diese Funktion liefert, muß beachtet werden!
  
  

Gutes Gelingen!

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

 

Zur Aufgaben-Übersicht

 

 

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

Kommentare 0