Hier mal einen Weg wie man das machen kann:
struct ListElement
{
char name[14];
ListElement* next;
};
const int LIST_SIZE = 32;
ListElement myFiles[LIST_SIZE];
ListElement* first; //Zeiger auf Anfang der Liste
byte fileCount; //Anzahl der eingefügten Datei-Namen
//Prototyp explizit, weil dass die IDE nicht selbst schafft (sie schreibt den Prototyp über die struct Deklaration wo dann das struct unbekannt ist)
void sortedInsert(ListElement** first, ListElement* element);
void setup()
{
Serial.begin(9600);
resetList();
addElement("AAAA.txt");
addElement("aaaaa.txt");
addElement("DDDD.txt");
addElement("BBBB.txt");
addElement("EEEE.txt");
addElement("CCCC.txt");
addElement("jjjj.txt");
addElement("FFFF.txt");
addElement("BAAA.txt");
addElement("BZZZ.txt");
addElement("Bggg.txt");
Serial.println("unsortiert:");
printList();
sortList();
Serial.println("sortiert:");
printList();
}
void loop()
{
}
//Element hinten einfügen
void addElement(const char* name)
{
if (fileCount < LIST_SIZE)
{
strlcpy(myFiles[fileCount].name, name, sizeof(ListElement::name)); //Inhalt kopieren
myFiles[fileCount].next = NULL;
//vorherigen next Zeiger auf aktuelles Element setzen
if (fileCount > 0)
myFiles[fileCount - 1].next = &myFiles[fileCount];
fileCount++;
}
}
//Liste zurücksetzen
void resetList()
{
first = myFiles;
first->name[0] = '\0';
first->next = NULL;
fileCount = 0;
}
void printList()
{
ListElement* current = first;
//Liste traversieren und ausdrucken
while (current != NULL)
{
Serial.println(current->name);
current = current->next;
}
Serial.println();
}
//von hier leicht angepasst: http://quiz.geeksforgeeks.org/insertion-sort-for-singly-linked-list/
void sortList()
{
ListElement* sorted = NULL;
ListElement* current = first;
//Liste traversieren
while (current != NULL)
{
ListElement* next = current->next;
sortedInsert(&sorted, current); //übergibt einen Zeiger auf die sortierte Liste und das aktuelle Element
current = next;
}
first = sorted;
}
void sortedInsert(ListElement** first, ListElement* element)
{
ListElement* current;
//Fallunterscheidung für erstes Element
if (*first == NULL || strcmp((*first)->name, element->name) >= 0)
{
//neuen Listenanfang setzen
element->next = *first;
*first = element;
}
else
{
current = *first;
//richtigen Platz für jedes Element finden. Hört auf wenn der Nachfolger(!) eines Elements "größer" als das aktuelle ist
while (current->next != NULL && strcmp(current->next->name, element->name) < 0)
current = current->next;
//neues Element zwischen aktuelles Element und Nachfolger des aktuellen Elements einfügen
element->next = current->next;
current->next = element;
}
}
Liefert:
unsortiert:
AAAA.txt
aaaaa.txt
DDDD.txt
BBBB.txt
EEEE.txt
CCCC.txt
jjjj.txt
FFFF.txt
BAAA.txt
BZZZ.txt
Bggg.txt
sortiert:
AAAA.txt
BAAA.txt
BBBB.txt
BZZZ.txt
Bggg.txt
CCCC.txt
DDDD.txt
EEEE.txt
FFFF.txt
aaaaa.txt
jjjj.txt
Da sieht man auch mal wie man mit strcmp() alphabetisch sortieren kann (und warum die Funktion bei Gleichheit 0 zurück gibt). Beachte aber dass strcmp() auf Basis der ASCII Tabelle sortiert. Also kommen alle Groß-Buchstaben vor allen Klein-Buchstaben. Das ist nicht immer gut so.
Betrachte die Sortier-Funktion als Magie wenn du es nicht verstehst. Also einfach verwenden und darauf vertrauen dass es klappt. Ist etwas kompliziert und ich hätte mir das auch nicht auf die schnelle aus dem Arm schütteln können. Also habe es von einer Webseite kopiert und ganz leicht angepasst.
Da sind dann auch nicht nur Zeiger drin, sondern auch ein Zeiger auf einen Zeiger (weil eine Änderung am Zeiger in der aufrufenden Funktion sichtbar sein muss)
Im Prinzip ist es aber fast ein normaler Insertion Sort. Anders als bei einer Array-basierenden Implementierung muss man aber bei einer verketten Liste nicht jedes Element immer um 1 weiter verschieben. Sondern kann gleich die richtige Position suchen und dann nur die Zeiger anpassen.
Man legt sich einen Zeiger ListElement* sorted an der den Anfang der sortierten Liste darstellt. Dann übergibt man den Zeiger und danach jedes Element an eine weitere Funktion, die für dieses Element die korrekte Position bestimmt. Dazu wird die Liste traversiert bis man ein Element findest dessen Nachfolger größer als das neue Element ist. Dann wird das neue Element dazwischen eingefügt.
Das ursprüngliche Erstellen ist vielleicht etwas unorthodox. Wenn du im Internet nach verketteten Listen suchst findest du erst mal hauptsächlich Beispiele wie jedes Element dynamisch angelegt wird. Hier ist aber ein Array vorhanden. Also muss man beim Einfügen nicht über die Zeiger traversieren. Das geschieht erst beim Ausdrucken. Die Strings liegen also sequentiell im Speicher (mit den Zeigern dazwischen), aber beim Sortieren und der Ausgabe wird entsprechend der Verkettung herumgesprungen
Für Extra-Punkte macht man daraus noch eine Klasse 
... siehe unten ...
