Elemente in einer Liste sortiert einfügen

[pronix_2008]

Hallo,
ich habe ein Problem mit der Methode add, und zwar möchte ich, dass beim Einfügen direkt sortiert wird.
(z.B: hallo c plusplus forum -> c forum hallo plusplus)
Ich habe es versucht ähnlich wie insertion sort zu machen, doch es gelingt mir nicht, dies an meiner add-methode zu implementieren:
hier mein code:

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

typedef struct node{
        struct node *next;
        char *s;
}node;

typedef node *ptr;
ptr head =NULL;

void show_list(ptr l){
if(l!=NULL){    l=l->next;
        for(;l;l=l->next)
                printf("%s\n", l->s);
}
}

void delete_liste(ptr l){
        while(l){
                ptr n=l->next;
                free(l);
                l=n;
        }
}

ptr add(ptr l, char *s){
        if(head==NULL){
        l=malloc(sizeof(node));
        l->s=s;
        l->next=head;
        head=l;
        }
        ptr last=head;

          while(last->next!=NULL)
                last=last->next;
        ptr n=malloc(sizeof(node));
        n->s=s;
        n->next=NULL;
        last->next=n;

return l;
}

int main(int argc, char *argv[]){
ptr l=NULL;
int i;
for(i=1;i<argc;i++){
  l=add(l,argv[i]);
}

show_list(l);
delete_liste(l);

return 0;
}

[mcr]

Hallo pronix_2008,

in deiner add Funktion sortierst du nicht!
Du müßtest dort strcmp aufrufen, damit du entscheiden kannst,
welcher String "größer" ist.

Dazu kommt noch, dass du in deinem Programm globale Variablen
wie head verwendest. Soetwas birgt immer eine Fehlerquelle.

Deine Add-Funktion müßte etwa so aussehen: (Pseudocode)

function add(l, el) 
begin
   last = NULL;
   first = l;
   solange l != NULL und l->s nicht größer als el
   begin
       last = l
       l = l->next
   end
   n = neues element
   n->next = l;
   if (last) {
      last->next = n;
      return first;
   }
   return n;
end

und deine show_list function ist auch noch fehlerhaft.

Gruß mcr

[moagnus]

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;
	}

}