Dynamische Datenstrukturen

[Back]    [Einfach verkette Liste]    [Doppelt verkette Liste]    [Baeume]

In der Realität werden Strukturen geschaffen, die der Verwaltung von Einzeldaten oder gar Klassen dienen. Zum Beispiel dient Einwohnerkartei eines kleinen Ortes der Erfassung von Wohndaten, Familiengröße ,-stand ...etc.
Als Verwaltung würde sich eine z.B. ein Arraystruktur anbieten. Diese hat aber eine maximale Zahl von Einträgen. Damit würde Sie der Anforderung an eine Kartei deren Datenmenge ständig wächst oder schrumpft nicht gerecht werden. Definiert man, um sicher zu sein, eine große Anzahl von Listenplätzen, würde unter Umständen unnötig viel Speicherplatz trotz einer potenziellen Unterbelegung zur Verfügung gestellt werden müssen. Der Ausweg ist die Schaffung von dynamischen Datenstrukturen. Solche Datenstrukturen stellen zum Beispiel verkettete Listen dar.

Einfach verkettete Liste


Um eine einfache verkettete Liste zu erzeugen, ist die Schaffung von Elementen einer Liste erforderlich. Die Elemente der Liste sind Knoten. Ein Knoten besteht aus einen Wert (value) und einem Zeiger (pointer). Der Zeiger enthält dabei keinen Wert, sondern dient der Referenzierung von Variablen. Die referenzierten Variablen heißen Bezugsvariablen und werden zur Laufzeit des Programms dynamisch erzeugt. Es ist durchaus möglich und für die Implementierung wichtig, dass verschiedene Referenzen auf die gleiche Bezugsvariable verweisen können.

01   class Knoten :
02 
03   def __init__(self,value) :
04                  self.value = value
05                  self.next  = None
05 
06   def get_value (self)   :
07                  return self.value
08 
09   def set_next (self, node)    :
10                  self.next  = node
11 
12   if __name__=="__main__" :
13 
14 	            test = Knoten (5)
15                  test.set_next (Knoten (3))
16                  print text.get_value ()
17                  print text.next.get_value()

Die Klasse Liste kann nun die Instanzen der Klasse Knoten verwenden und und diese nacheinander in die Liste einfügen. Am Beispiel des Anfügens eines Knotens append an eines bestehende Liste soll diese Prinzip verdeutlicht werden.

01 class Liste :
02 
03 def __init__(self) :
04                  self.liste = None
05 
06 def append (self, elem)   :
07               M = self.liste
08               K = Knoten (elem)
09               if M is None :
10                    self.liste = K
11                    return
12               else         :
13                    while M.next is not None : M = M.next
14 	         M.next = K

Um die Klasse Liste zu implementieren sind neben den gegebenen weitere Methoden zu implementieren. Die wichtigsten sind dabei :


Doppelt verkettete Liste


Der Vorteil einer doppelt verketteten Liste besteht in der Möglichkeit, sich nicht nur vorwärts durch die Liste zu bewegen, sondern auch in die entgegengesetzte Richtung. Dadurch werden Suchfunktionen erheblich verkürzt, gleichzeitig ist die dynamische Verwaltung der Daten gesichert.
Es besteht hier allerdings die Notwendigkeit einer Neuimplemntierung des Knotenmoduls und einer Anpassung der Methoden. Auch für diesen Fall das entsprechende Bespiel.

01   class DKnoten :
02 
03   def __init__(self,value) :
04                  self.value = value
05                  self.left  = None
06 		   self.right = None
07 
08   def get_value (self)   :
09                  return self.value
10 
11   def set_left (self, node)    :
12                  self.left  = node
13 
14   def set_right (self, node)    :
15                  self.right  = node

Die append Methode gestaltet sich mit dem entsprechenden Import ähnlich.

02 from DKnoten import *
02 
01 class DListe :
02 
03 def __init__(self) :
04                  self.liste = None
05 
06 def append (self, elem)   :
07               M = self.liste
08               K = DKnoten (elem)
05 
09               if M is None :
10                    self.liste = K
11                    return
12               else         :
13                    while M.right : M = M.right
14 	         K.left  = M
14 	         M.right = K

     [Protected]