M
Hier mal ein wahrscheinlich höchst verbesserungswürdiger Algorithmus von mir (trivialer Ansatz ohne durchdachte Verbesserungen):
void add(NODE **list, const char *str) {
// Liste noch leer
if(*list == NULL) {
*list = malloc(sizeof(NODE));
strncpy( (*list)->str, str, SIZE);
(*list)->next = NULL;
return;
}
// Liste besitzt mindestens 1 Element
NODE *i, *j;
for(i=(*list); i != NULL; i = i->next) { // list zeigt auf erstes und einziges Element, s.o.
// Vergleich/Einordnung anhand der Zeichenfolge
int result = strcmp(str, i->str);
if(result < 0) {
if(i==(*list)) { // Element wird ganz am Anfang eingefügt
NODE *tmp = *(list); // Zwischenspeicherung
(*list )= malloc(sizeof(NODE)); // neues Element an Anfang setzen
strncpy((*list)->str, str, SIZE); // Zeichenkette kopieren
(*list)->next = tmp; // Listenanfang (neues Element) auf ehemalig Erstes zeigen lassen
return;
} else {
// Element wird in Mitte eingefügt
j->next = malloc(sizeof(NODE)); // Vorgänger zeigt auf das neue Element
strncpy(j->next->str, str, SIZE); // j->next: neues Element (s.o.). Kopieren...
j->next->next = i; // neues Element zeigt auf Nachfolger (i)
return;
}
}
else if(result == 0) { // Element direkt danach einfügen. Auch davor möglich
if(i->next == NULL) { // Einfügen am Ende
i->next = malloc(sizeof(NODE));
strncpy(i->next->str, str, SIZE);
i->next->next = NULL; // neues Element liegt am Listenende
return;
}
else {
// Einfügen in Mitte
NODE *tmp = i->next; // alten Nachfolger speichern
i->next = malloc(sizeof(NODE));
strncpy(i->next->str, str, SIZE);
i->next->next = tmp; // an Nachfolger anschließen
return;
}
}
else if(result >0) { // neues Element größer als das von i Verwiesene -> weiterlaufen in Liste,
// bis (eine der Bedingungen oben eintrifft oder) das Listenende erreicht wird
if(i->next == NULL) { // Listenende erreicht -> Einfügen am Ende
i->next = malloc(sizeof(NODE));
strncpy(i->next->str, str, SIZE);
i->next->next = NULL; // neues Element am Listenende
return;
}
else if(strcmp(str, i->next->str) <= 0) { // nur einfügen, falls kleiner oder gleich dem Nachfolger,
//ansonsten wird weitergelaufen
NODE *tmp = i->next;
i->next = malloc(sizeof(NODE));
strncpy(i->next->str, str, sizeof(str));
i->next->next = tmp; // Zeiger auf Nachfolger
return;
}
}
// Zeiger j zeigt auf das Vorgängerelement von i. j ist erst nach einem Durchlauf initialisiert,
// wird aber auch nur für Einfügen in der Listenmitte gebraucht, daher in Ordnung.
// (j wird "bereits" oben benutzt)
j = i;
}
}