Die meisten guten Sortieralgorithmen gehen davon aus, dass man wahlfrei auf alle Elemente der zu sortierenden Datenstruktur zugreifen kann. Für Listen ist das nicht der Fall. Wir wollen dennoch unsere Liste direkt sortieren und implementieren dazu ein Selection Sort:
Idee des Selection Sort ist, einfach immer das kleinste Element aus der Menge der noch nicht sortierten Elemente zu suchen und es an das Ende es bereits sortierten Teils der Liste zu setzen. Letztere Operation ist für Listen sehr einfach, erstere auch nicht schwieriger als bei Arrays.
static Node *findAndRemSmallest(Node **toSortPtr)
{
Node *smallest=*toSortPtr,
**smallestChaining=toSortPtr;
Node *curNode=*toSortPtr,
**curChaining=toSortPtr;
while (curNode) {
if (strcoll(curNode->cont, smallest->cont)<0) {
smallest = curNode;
smallestChaining = curChaining;
}
curChaining = &(curNode->next);
curNode = curNode->next;
}
*smallestChaining = smallest->next;
return smallest;
}
void list_sort(List *l) /* Selection Sort */
{
Node **curElPtr=&(l->first);
Node *smallest=NULL;
while (*curElPtr) {
smallest = findAndRemSmallest(curElPtr);
smallest->next = *curElPtr;
*curElPtr = smallest;
curElPtr = &(smallest->next);
}
l->last = smallest;
}
Wir haben unser Sortierproblem in zwei Funktionen unterteilt: Einerseits findAndRemSmallest, das einfach beim übergebenen Node anfängt, die Liste nach dem kleinsten Element zu druchsuchen. Dazu muss es natürlich immer bis zum Ende der Liste laufen. Es führt dabei Buch über den Verweis auf das kleinste Element, weil es das kleineste Element aus der Liste aushängen soll. Dafür muss man bei einfach verketteten Liste eben den Vorgänger kennen – doppelt verkettete Listen (es gibt jeweils noch einen Zeiger auf den Vorgänger) haben dieses Problem natürlich nicht.
Schließlich gibt findAndRemSmallest einen Zeiger auf das – mittlerweile nicht mehr in der Liste befindliche – kleinste Element zurück. In diesem Moment ist das die einzige Referenz auf den Node, wir sollten sie also nicht verlieren. Die Funktion list_sort nun hängt dieses Element an die richtige Stelle, nämlich an das Ende der schon sortierten Daten. Das tut es ein wenig raffiniert, nämlich, indem es jeweils den next-Pointer des Vorgängers dieses Zielelements speichert (im Node **curElPtr). Am Anfang ist dies ein Pointer auf l->first, danach jeweils ein Pointer auf das next-Feld des zuletzt bearbeiteten Knotens. Auch dies ist vor allem nötig, weil wir in der doch recht simplen einfach verketteten Liste arbeiten und könnte mit doppelter Verkettung etwas durchsichtiger gelöst werden.
Das Sortieren wird fortgesetzt, bis das Ende der Liste erreicht ist – die Funktion merkt das, in dem sie nachsieht, ob curElPtr auf einen Nullpointer zeigt. Dieser Nullpointer ist dann das next-Feld des aktuellen Elements, und dies war gerade unser Endemarker.
Die verwendete Vergleichsfunktion strcoll übrigens vergleicht zwei Strings gemäß den Regeln des augenblicklichen Locales. Wer das mit dem de_DE-Locale macht, kriegt die Umlaute an der richtigen Stelle einsortiert.
Mögliche Anwendung:
int main(void)
{
FILE *inF=fopen("test.txt", "r");
List *words=list_new();
char *w;
setlocale(LC_ALL, "");
while ((w=getNextWord(inF))) {
list_append(words, w);
}
list_sort(words);
printList(words);
return 0;
}
Dabei soll getNextWord das nächste Wort aus der Datei oder NULL am Dateiende zurückgeben. Eine mögliche Implementation (die überlange Wörter abschneidet) wäre
char *getNextWord(FILE *src)
{
static char buf[TOKENS_WORDLEN];
char *cp=buf;
int ch;
do {
ch = fgetc(src);
} while (!isalpha(ch) && ch!=EOF);
if (ch==EOF) {
return NULL;
}
while (isalpha(ch) && ch!=EOF &&
cp-buf<TOKENS_WORDLEN-1) {
*cp++ = ch;
ch = fgetc(src);
}
*cp = 0;
return buf;
}
– diesen Code gab es auf einer der vorigen Folien als tokens.c.
Die Funktion printList soll einfach die komplette Liste ausgeben und ist in einer naiven Implementation trivial.
Man kann das Programm mit einem Text von 6200 Wörtern ausprobieren; auf meiner Maschine ergibt sich eine Laufzeit von rund 4 Sekunden. Das ist ziemlich viel.