Tutorial, in dem erklärt wird, wie eine verknüpfte Liste in C mit Hilfe einer einfachen Bubble-Sort-Technik alphabetisch geordnet werden kann; ideal für neue und fortgeschrittene Programmierer.

Einführung

Das Sortieren ist eine der schwierigsten Aufgaben in der Computerprogrammierung, aber auch eine der nützlichsten. Es gibt viele verschiedene Arten und Algorithmen, aber um die Dinge einfach zu halten, werden wir eine einfache Alphabetisierung mit einem Bubble-Sort-Algorithmus betrachten.

Davon gehen wir aus:

• Jedes Wort ist klein geschrieben
• Jedes Wort ist ein Array von Zeichen mit Null-Terminierung

Außerdem verwenden wir die Programmiersprache C, was bedeutet, dass wir keinen der abstrakten Datentypen in einer Klasse kapseln können. C++-Programmierer und angehende C-Programmierer, die zu C++ wechseln möchten, werden die Unterschiede zwischen diesem Tutorial und einer klassenbasierten Implementierung zu schätzen wissen.

Die Theorie bleibt jedoch die gleiche.

Theorie der Alphabetisierung

Um eine Liste von Wörtern in alphabetisch aufsteigender Reihenfolge zu sortieren, müssen wir in der Lage sein, sie zu vergleichen. Da C eine Bibliothek namens string.h bereitstellt, sollten wir diese verwenden. In string.h gibt es eine einfache Vergleichsfunktion namens strcmp. Die Funktion strcmp nimmt zwei Zeichenketten entgegen und gibt sie zurück:

• -1, wenn Zeichenkette A kleiner ist als Zeichenkette B
• 0, wenn die Zeichenketten gleich sind
• 1, wenn die Zeichenfolge B kleiner ist als die Zeichenfolge A

Mit anderen Worten: Wenn die Zeichenkette A vor der Zeichenkette B in einem Wörterbuch stehen würde, würde strcmp -1 zurückgeben. Damit ist die meiste harte Arbeit beim Alphabetisieren für uns erledigt. Es gibt jedoch eine Einschränkung – wenn die Zeichenketten nicht beide in der gleichen Groß-/Kleinschreibung sind, sollte strcmpi (das i steht für insensitive) verwendet werden.

Alphabetisierung in der Praxis : Blase sortieren

Ein Bubble-Sort-Algorithmus ist eine der einfachsten Formen des Sortierens, die Programmierer kennen. Er ermöglicht es im Grunde, hohe Werte durch den Rest zu “blubbern”, indem er wiederholt benachbarte Werte vergleicht und sie austauscht. Betrachten Sie die Liste:

• D
• B
• C
• A

Wenn wir diese Liste so sortieren wollten, dass sie “ABCD” ergibt, könnten wir eine Blasensortierung verwenden und die Nachbarn vergleichen und die Werte vertauschen, wenn einer “kleiner” ist als der andere. Im ersten Durchgang würden wir folgendes Ergebnis erhalten:

• B
• C
• A
• D

Diese Liste ist das Ergebnis des sukzessiven Austauschs von Nachbarn, beginnend mit dem ersten Eintrag in der Liste, bis das letzte Paar verglichen worden ist. Das “D” hat sich durch die Werte nach oben (oder unten) bewegt und wurde jedes Mal ausgetauscht, weil jeder andere Wert “kleiner” war als “D”:

• D B C A : Tausch D & B
• B D C A : Tausch D & C
• B C D A : Tausch D & A
• B C A D : Ende

Das ist jedoch noch nicht das Ende der Geschichte, denn die Liste ist jetzt besser sortiert als vorher, aber noch nicht ganz korrekt sortiert. Tatsächlich müssen wir den Bubble-Sort-Algorithmus wiederholt anwenden, bis keine Vertauschungen mehr stattfinden.

In C könnte dies etwa so aussehen:

do{
Swap = 0;
for (i = 1, i < nStrings; i++)
{
if (swap(szStrings[i-1], szStrings[i], -1) == 1)
{
nSwap++;
}
}}
while (nSwap == 0);

Wir nehmen an, dass die Swap-Funktion einen Vergleich und eine Vertauschung auf der Grundlage von zwei Strings und einer Richtung durchführt. Diese Funktion würde je nach den Elementen der Liste, die wir sortieren möchten, unterschiedlich sein.

Die Implementierung der Verknüpften Liste

Die obige Lösung ist gut, aber sie bietet nur eine Möglichkeit, eine zweidimensionale Liste zu sortieren: eine Liste von Zeichenketten. Was wir brauchen, ist eine verknüpfte Liste, und deshalb müssen wir die Datenstrukturen und Algorithmen, die zur Bearbeitung der Liste verwendet werden, neu definieren.

Zu diesem Zweck erstellen wir eine Knotenstruktur in C, die Folgendes enthält:

• Die Zeichenfolge
• Ein Zeiger auf den nächsten Knoten

Jeder Knoten wird dann mit der Zeichenkette, die er enthalten soll, und einem NULL-Zeiger initialisiert. Wenn wir einen Knoten hinzufügen wollen, müssen wir nur einen neuen Knoten erstellen und das Mitglied “next” auf den Kopf der bestehenden Liste verweisen.

Das Vertauschen wird dann zu einem Fall von Umleitung dieser Zeiger, so dass die Knoten in ihrer Reihenfolge innerhalb der Liste umgekehrt werden. Dies erfordert zwei Schritte:

• Zeigen Sie das nächste Mitglied von Knoten A auf den Knoten nach Knoten B
• Zeigen Sie das nächste Mitglied von Knoten B auf Knoten A

Beachten Sie, dass im Gegensatz zur Verarbeitung eines Arrays keine Kopie der auszutauschenden Daten erstellt wird, sondern nur ein Verweis auf das Datenelement erhalten bleibt. Dadurch wird der Bubble-Sortiervorgang geringfügig effizienter, aber immer noch weit weniger effizient als andere, speziellere Sortieralgorithmen.