| Advanced Java Services | Einfach verkettete Listen |
|
Eine einfach verkettete Liste ist Reihe von Elementen (auch Knoten genannt), die durch Zeiger miteinander verbunden sind. Das erste Element wird gerne Rootelement genannt. Mit Hilfe des Zeigers kann man von einem Element zum nächsten navigieren. Da es nur einen Zeiger gibt, kann man die Liste nur in einer Richtung durchlaufen. Typische Operationen für eine Liste sind das Erstellen des Wurzelelements, das Anhängen eines Elements, das Löschen eines Elements, das Löschen der ganzen Liste.
Die Elemente einer Liste sind vom Typ struct. Wir geben uns folgendes vor:
struct node
{
int data;
struct node* next;
};
typedef struct node node;
Das folgende kleine Programm erzeugt einen Wurzelknoten und zwei Nachfolger und gibt die Daten aus.
/*
* Eine Wurzel mit zwei Nachfolgern zu Fuß
*/
void beispiel()
{
puts("beispiel");
// Erstellen von root
node *root = malloc(sizeof(node));
if (root == NULL) return;
root->data = 17;
root->next = NULL;
// Anhängen eines Knotens
node *secondNode = malloc(sizeof(node));
if (secondNode == NULL) return;
root->next = secondNode;
secondNode->next = NULL;
secondNode->data = 19;
// Anhängen eines weiteren Knotens
node* last = malloc(sizeof(node));
if (last == NULL) return;
secondNode->next = last;
last->next = NULL;
last->data = 21;
//Ausgeben der Daten
for( ; root != NULL; root = root->next)
printf("%d ", root->data);
printf("\n");
}
Im Hauptspeicher kann man sich das wie folgt vorstellen.
Der Zeiger des letzten Knotens muß explizit auf NULL gesetzt werden. Alle Algorithmen erkennen das Ende an diesem NULL-Zeiger.
Die folgenden Funktionen sind einfache Verallgemeinerungen des ersten Beispiels.
/*
* Die Funktion createroot erzeugt einen ersten Knoten mit Daten
* Falls kein Speicher angefordert werden kann, gibt die Funktion
* NULL zurück, ansonsten den Rootknoten.
*/
node* createRoot(int data)
{
node *root = malloc(sizeof(node));
if (root == NULL) return NULL;
root->next = NULL;
root->data = data;
return root;
}
/*
* Hängt am Ende an. Falls nicht der letzte Knoten übergeben wurde, wird das Ende gesucht.
* Auf diese Weise kann man einen beliebigen Knoten übergeben. Es wird nicht geprüft,
* ob die Daten bereits in der Liste sind. Wenn der erste Parameter NULL ist oder kein
* Speicher angefordert werden kann gibt die Funktion NULL zurück. Im Erfolgsfall wird
* der neue Knoten zurückgegeben.
*/
node* appendNode(node* oldtail, int data)
{
if (oldtail == NULL ) return NULL;
node *newtail = malloc(sizeof(node));
if (newtail==NULL) return NULL;
while (oldtail->next != NULL) // ans Ende
oldtail = oldtail->next;
// nun ist oldtail->next NULL
oldtail->next = newtail;
newtail->next = NULL;
newtail->data = data;
return newtail;
}
/*
* Gibt die Liste ab der Stelle root aus
*/
void printList(node* root)
{
if (root == NULL) return;
for ( ; root != NULL ; root = root->next)
printf("%d ", root->data);
printf("\n");
}
/*
* Ermittelt die Länge der Liste ab dem übergebenen Knoten
*/
int listLength(node* root)
{
if (root == NULL) return 0;
int len = 1;
for( ; root->next != NULL; len++)
root = root->next;
return len;
}
/*
* Durchsucht die List nach einem übergebenen Datenelement. Wird es gefunden,
* so wird ein Zeiger auf den Knoten zurückgegeben, andernfalls NULL. Es wird
* nur das erste Auftreten des Elements gesucht
*/
node* seekList(node* root, int data)
{
if (root == NULL) return NULL;
for(; root !=NULL; root = root->next)
if (root->data == data) return root;
return NULL;
}
Beim Freigeben der ganzen Liste muß man den Zeiger auf den nächsten Knoten zwischenspeichern bevor man den aktuellen Knoten freigibt, damit man noch auf den nächsten Knoten zugreifen kann.
/*
* Gibt den Speicher ab der Stelle curr frei. Ist der übergebene
* Knoten der Wurzelknoten, so wird die ganze Liste gelöscht.
*/
void freelist(node* curr)
{
if (curr == null) return;
while (curr->next != null)
{
node *nextnode = curr->next;
free(curr);
curr = nextnode;
}
// jetzt muß noch das letzte gelöscht werden:
free(curr);
}
Beim Löschen eines Knotens sind drei Fälle zu unterscheiden, Löschen von root, Löschen innerhalb der Liste und Löschen des Endes der Liste. Im ersten Fall muß root neu gesetzt werden, aus diesem Grund wird ein Zeiger auf den Zeiger auf root übergeben. In den letzten beiden Fällen muß der Vorgänger bekannt sein und dessen Zeiger neu gesetzt werden, daher ist die Funktion aufwendiger.
/*
* Löschen eines Elements der Liste
* Returnwert:
* 0 falls nichts gelöscht wurde.
* 1 falls root gelöscht wurde (und es somit eine neue wurzel gibt)
* 2 falls innen gelöscht wurde
* 3 falls am ende gelöscht wurde
*/
int delete(node** pRoot, int data)
{
if (pRoot == null || *pRoot == NULL) return 0; // Nichts gelöscht
// pRoot löschen
if ( data == (*pRoot)->data )
{
node* newRoot = (*pRoot)->next;
free(*pRoot);
*pRoot = newRoot;
return 1; // neue root
}
/* Beginnend mit pRoot->next wird geprüft, ob ein Knoten die übergebenen daten enthält
* Der Vorgänger wird gespeichert, damit man im Falles des Findens den Knoten aushängen kann
* Falls nichts gefunden wird, ist curr->next = NULL und man ist am Ende angekommen
* Nun wird noch curr untersucht und evtl abgehängt. Kommen Daten mehrmals vor, so wird
* nur das erste Vorkommen gelöscht. Da ein Löschen am Anfang eine neue Wurzel ergibt,
* wird immer die Wurzel zurückgegeben.
*/
node* prev = *pRoot;
node* curr = (*pRoot)->next;
for (; curr->next != null; prev = prev->next, curr = curr->next)
{
if ( curr->data == data )
{
// curr aushängen, curr löschen
prev->next = curr->next;
free(curr);
return 2; // innen gelöscht
}
// else weitersuchen
}
// da nichts gefunden ist hier curr->next = NULL
if ( curr->data == data )
{
prev->next = curr->next; // NULL
free(curr);
return 3; // am ende gelöscht
}
// else nichts gefunden
return 0;
}
Der Aufbau einer geordneten Liste funktioniert ähnlich wie das Löschen eines Knotens, man unterscheidet die gleichen drei Fälle: Einhängen vor root, Insert nach root und vor dem Ende, und Anhängen am Ende.
/*
* Geordnetes einfügen
* Erhält einen Zeiger auf root, damit root über die parameterliste
* aktualisiert werden kann.
* Returnwert:
* 0 falls nichts eingefügt wurde.
* 1 falls vor root eingefügt wurde (und es somit eine neue wurzel gibt)
* 2 falls ein echtes insert stattfindet
* 3 falls am ende angehängt wird
*/
int insert(node** pRoot, int data)
{
if (pRoot == null || *pRoot == NULL) return 0;
// "einhängen" vor pRoot
if ( data < (*pRoot)->data )
{
node *newroot = malloc(sizeof(node));
if (newroot != NULL)
{
newroot->next = *pRoot;
newroot->data = data;
*pRoot = newroot;
return 1; // neue root
}
return 0;
}
/* Beginnend mit pRoot wird geprüft, ob man zwischen
* pRoot und und pRoot->next einhängen kann. falls
* diese prüfung positiv ausfällt wird eingehängt
* und mit return beendet. falls nicht, kommt man ans Ende der liste
* (curr->next == null) und die Schleife wird normal beendet.
* In diesem Fall wird am Ende angehängt.
*/
node* curr = *pRoot;
for (; curr->next != null; curr = curr->next)
{
if ( curr->data < data && data <= curr->next->data)
{
node *newnode = malloc(sizeof(node));
if (newnode != null)
{
newnode->next = curr->next;
curr->next = newnode;
newnode->data = data;
}
return 2; // echtes insert
}
//else weitersuchen
}
// falls kein einfügestelle gefunden, ist hier curr->next = NULL, also append
node *newnode = malloc(sizeof(node));
if (newnode != null)
{
newnode->data = data;
newnode->next = curr->next;
curr->next = newnode;
return 3; // append
}
return 0;
}
|
|
|