Titel:
Verknüpfte-Liste Speicher Sortieren
Sprache:
C
Autor:
Philip J. Erdelsky
http://www.alumni.caltech.edu/~pje/
Datum:
- Juli 1998
Verwendung:
Öffentliche Domäne; keine Nutzungsbeschränkungen
Portabilität:
Irgendein C-Compiler
Schlüsselwörter:
Verknüpfte Liste, Sortieren
Abstrakt:
Eine C-Funktion zum Sortieren einer verketteten Liste im Speicher unter Verwendung einer beliebigen Vergleichsfunktion und eines Bandzusammenführungsalgorithmus, der in allen Fällen O (n log n) ist. Die Funktion ist nicht rekursiv und reentrant und ändert nur die Links.
Verknüpfte Listen und Sortierroutinen sind sehr häufig in der Programmierung.
Die Funktion sort_linked_list () sortiert praktisch jede Art von einfach verketteten Listen unter Verwendung einer Vergleichsfunktion, die vom aufrufenden Programm geliefert wird. Es hat folgende Vorteile gegenüber qsort ():
- Es sortiert Elemente variabler Größe.
- Es erfordert O (n log n) Vergleiche, unabhängig von der ursprünglichen Reihenfolge. Die Zeit zum Sortieren einer Liste ist vorhersehbar und konsistent. Diese Leistung ist bekanntlich optimal für allgemeine Sorten.
- Der Algorithmus ist iterativ, nicht rekursiv, so dass es keinen Stapelüberlauf gibt. Die Stapelanforderung ist vorhersehbar, konsistent und klein.
- Es sortiert die verknüpfte Liste durch Ändern der Zeiger, nicht durch Verschieben der Elemente selbst.
- Es kann eine Liste sortieren, die zu groß ist, um in ein Array zu passen.
Die Funktion sortiert nur einfach verknüpfte Listen. Wenn eine Liste doppelt verknüpft ist, können die Rückwärtszeiger nach der Sortierung durch einige Zeilen Code wiederhergestellt werden.
Jedes Element einer verknüpften Liste, das sortiert werden soll, muss als seine ersten Mitglieder einen oder mehrere Zeiger enthalten. Einer der Zeiger, der in jedem Element in derselben relativen Position sein muss, ist ein Zeiger auf das nächste Element. Dieser Zeiger ist im letzten Element NULL.
Der Index ist die Position dieses Zeigers in jedem Element. Es ist 0 für den ersten Zeiger, 1 für den zweiten Zeiger usw.
Lassen Sie vergleichen () eine Vergleichsfunktion sein, die zwei Elemente wie folgt vergleicht:
n = vergleichen (p, q, Zeiger);
void * p, * q; Zeiger auf zwei Listenelemente
void * Zeiger; benutzerdefinierter Zeiger, der an compare () übergeben wurde
linked_list_sort ()
int n; Ergebnis des Vergleichs von * p und * q
> 0 wenn * p nach * q in sortierter Reihenfolge sein soll
<0 wenn * p vor * q in sortierter Reihenfolge stehen soll
0, wenn die Reihenfolge von * p und * q irrelevant ist
Sei “first” ein Zeiger auf das erste Element der Liste. Dann sortiert der folgende Funktionsaufruf die Liste und gibt einen Zeiger auf das erste Element der sortierten Liste zurück:
erste_sortierte =
sort_linked_list (zuerst, index, vergleichen, zeiger, pcount);
Das vierte Argument (Zeiger) wird an compare () ohne Änderung übergeben. Das hier gegebene Beispiel macht von dem Zeiger keinen Gebrauch. Es kann jedoch ein unschätzbares Merkmal sein, wenn zwei oder mehr Vergleichsmethoden eine wesentliche Menge an Code teilen und sich nur in einem oder mehreren Parameterwerten unterscheiden.
Das letzte Argument (pcount) hat den Typ (unsigned long *). Wenn es nicht NULL ist, wird * pcount gleich der Anzahl der Datensätze in der Liste gesetzt.
Es ist zulässig, eine leere Liste zu sortieren. Wenn zuerst == NULL ist, ist der zurückgegebene Wert ebenfalls NULL.
Zum Beispiel kann ein Element sowohl einen Namen als auch eine Nummer enthalten:
Strukturelement
{
Strukturelement * next_in_alphabetical_order;
Strukturelement * next_in_numerical_order;
Char Name [9];
int-Nummer;
/ * andere Mitglieder, falls vorhanden * /
Anfangs sind die zwei Zeiger in jedem Element identisch und die Liste ist in einer beliebigen Reihenfolge, wobei “zuerst” ein Zeiger auf das erste Element ist. Die folgenden zwei Funktionsaufrufe sortieren die Liste zweimal:
first_in_alphabetical_order =
sort_linked_list (zuerst, 0, compare_names, NULL);
first_in_numerical_order =
sort_linked_list (zuerst, 1, compare_numbers, NULL);
Hier sind die Vergleichsfunktionen:
int compare_names (Strukturelement * p, Strukturelement * q,
void * Zeiger)
{
return strcmp (p-> Name, q-> Name);
}
int compare_numbers (Strukturelement * p, Strukturelement * q,
void * Zeiger)
{
zurück p-> Nummer> q-> Nummer? 1: -1;
/ * HINWEIS: Rückgabe p-> Nummer – q-> Nummer wird ausreichen, wenn es gibt
keine Gefahr eines numerischen Überlaufs * /
}
Eine frühere Version dieser Art, die in einem technischen Journal veröffentlicht wurde, erforderte, dass der Vorwärts-Link am Anfang jedes Elements war. Während dies die Art etwas effizienter machte, machte es es auch schwierig, mit mehrfach verknüpften Listen zu arbeiten.
Der Algorithmus ist ziemlich einfach. Die verkettete Liste (in Analogie zu alten Magnetbändern ein “Band” genannt) wird zunächst in zwei Bänder gleicher oder nahezu gleicher Größe unterteilt. Dies geschieht durch abwechselndes “Schreiben” von Elementen auf die zwei Bänder.
Die zwei Bänder werden dann Element für Element in sortierte Blöcke mit jeweils zwei Elementen zusammengeführt. Die Blöcke werden abwechselnd auf zwei andere Bänder geschrieben.
Die zwei Bänder werden dann blockweise in sortierte Blöcke von jeweils vier Elementen zusammengeführt, und die Blöcke werden abwechselnd auf zwei andere Bänder geschrieben.
Der Vorgang wird fortgesetzt, indem die Blockgröße jedes Mal verdoppelt wird, bis alle Elemente in einem einzelnen sortierten Block auf einem Band liegen. Die Funktion gibt einen Zeiger auf das erste Element dieses Bandes zurück.
Jede Zusammenführung erfordert O (n) Vergleiche, wobei n die Anzahl der Elemente ist. Die Anzahl der Zusammenführungen ist O (log n). Daher benötigt die gesamte Sortierung O (n log n) -Vergleiche.
Die Funktion sort_linked_list () ist reentrant, wenn die Vergleichsfunktion reentrant ist.
C-Kenner werden sich freuen, dass dieser Algorithmus in Ada oder Pascal nicht einfach codiert werden kann, da er auf Typumwandlungen beruht.
Die sort_linked_list () – Funktion kann leicht von einem C ++ – Programm mit einem Minimum an Typprüfung aufgerufen werden, wenn die Header-Datei LLMSORT.H enthalten ist. Es enthält eine Vorlage für die Inline-Generierung eines Aufrufs bei sort_linked_list (). Das Format des Anrufs lautet wie folgt:
#include “llmsort.h”
first_sorted = sort_list (zuerst, vergleichen, zeiger, pcount);
deine Klasse * zuerst;
Ihre Klasse * first_sorted;
void * Zeiger;
unsigned long * pcount;
Die Funktion compare () wird wie folgt aufgerufen:
n = vergleichen (p, q, Zeiger);
const yourclass * p;
const yourclass * q;
void * Zeiger;
int n;
Hier ist “yourclass” jede Klasse, die Sie definieren können. Der Compiler überprüft die Konsistenz der Argumenttypen und generiert den entsprechenden Aufruf von sort_linked_list ().
Quelltext im Textformat:
Source: http://www.efgh.com/software/llmsorth.txt
