Elemente in einer Liste sortiert einfügen



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


  • 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



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

Log in to reply