| Advanced Java Services | Doppelt verkettete Listen |
|
Eine doppelt verkettete Liste ist Reihe von Elementen (auch Knoten genannt), die durch zwei Zeiger miteinander verbunden sind. Zusätzlich zu einem Zeiger, der auf das nächste Element zeigt gibt es einen, der auf das vorhergehende Element zeigt. Eine doppelt verkettete Liste kann man also in beide Richtungen durchlaufen. Die Operationen auf einer doppelt verketteten Liste sind analog zu denen einer einfach verketteten Liste.
Die Elemente einer Liste sind vom Typ struct. Wir geben uns folgendes vor:
struct node
{
int data;
struct node* prev;
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->prev = NULL;
root->next = NULL;
// Anhängen eines Knotens
node *secondNode = malloc(sizeof(node));
if (secondNode == NULL) return;
root->next = secondNode;
secondNode->prev = root;
secondNode->next = NULL;
secondNode->data = 19;
// Anhängen eines weiteren Knotens
node* last = malloc(sizeof(node));
if (last == NULL) return;
secondNode->next = last;
last->prev = secondNode;
last->next = NULL;
last->data = 21;
//Ausgeben der Daten
for( ; root != NULL; root = root->next)
printf("%d ", root->data);
printf("\n");
//Daten rückwärts ausgeben
for( ; last != NULL; last = last->prev)
printf("%d ", last->data);
printf("\n");
}
Im Hauptspeicher kann man sich das wie folgt vorstellen.
Die Zeiger zeigen natürlich immer auf den Anfang des Speicherbereichs, die Graphik vereinfacht das. Der Zeiger des ersten und des letzten Knotens muß explizit auf NULL gesetzt werden. Alle Algorithmen erkennen den Anfang bzw. das Ende an diesem NULL-Zeiger.
Die folgenden Funktionen sind einfache Verallgemeinerungen des ersten Beispiels. Bei createRoot und appendNode müssen hier auch die prev-Zeiger gesetzt werden. printList, listLength und seekList sind wie bei der einfach verketteten Liste. printListReverse geht ans Ende der Liste und gibt sie dann rückwärts aus. seektListReverse geht ans Ende der Liste und sucht dann nach vorne.
/*
* 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->prev = 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->prev = oldtail;
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");
}
/*
* Geht ans Ende und gibt die Liste rückwärts aus
*/
void printListReverse(node* curr)
{
if (curr==NULL) return;
for ( ; curr->next != NULL ; curr = curr->next) ;
// curr->next ist NULL
for ( ; curr != NULL ; curr = curr->prev)
printf("%d ", curr->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;
}
/*
* Durchsucht vom Ende her die Liste nach einem übergebenen Datenelement. Wird es
* gefunden, so wird ein Zeiger auf den Knoten zurückgegeben, andernfalls NULL.
*/
node* seekListReverse(node* curr, int data)
{
if (curr == NULL) return NULL;
for ( ; curr->next != NULL ; curr = curr->next) ;
// curr->next ist NULL
for(; curr != NULL; curr = curr->prev)
if (curr->data == data) return curr;
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
// root löschen
if ( data == (*pRoot)->data )
{
printf("root löschen\n");
node* newroot = (*pRoot)->next; // kann NULL sein
if(newroot != NULL) newroot->prev = NULL; // wichtig !!
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.
*/
printf("löschen nach root\n");
node* prev = *pRoot;
node* curr = (*pRoot)->next;
for (; curr->next != null; prev = prev->next, curr = curr->next)
{
if ( curr->data == data )
{
printf("löschen innen\n");
// curr aushängen, curr löschen
prev->next = curr->next;
curr->next->prev = prev;
free(curr);
return 2; // innen gelöscht
}
// else // weitersuchen
}
// falls nicht gefunden ist hier curr->next = NULL
if ( curr->data == data )
{
puts("am ende");
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->prev = NULL;
(*pRoot)->prev = newroot;->prev = newroot;
newroot->data = data;
*pRoot = newroot;
return 1; // 1 = neue pRoot
}
return 0;
}
/* Beginnend mit root wird geprüft, ob man zwischen
* root und und root->next einhängen kann. falls
* diese prüfung posotiv 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)
{
//printf("insert nach curr\n");
node *newnode = malloc(sizeof(node));
if (newnode != null)
{
newnode->next = curr->next;
newnode->prev = curr;
curr->next->prev = newnode;
curr->next = newnode;
newnode->data = data;
}
return 2; // insert
}
//else weitersuchen
}
// falls kein einfügestelle gefunden, ist hier curr->next = NULL, also anhängen
node *newnode = malloc(sizeof(node));
if (newnode != null)
{
newnode->next = curr->next; // NULL
newnode->prev = curr;
curr->next = newnode;
newnode->data = data;
return 3; // append
}
return 0;
}
|
|
|