Elemente sortiert in einer Liste einfügen (einfach verkettete Liste)



  • Hallo,
    ich habe hier eine einfach verkettete Liste, welche Wörter von der Kommandozeile einließt und diese in einer Liste genauso einfügt, wie sie eingelesen worden sind.
    Ich möchte, aber dass die Wörter, welche sortiert in die Liste eingefügt werden, dass heißt, dass er direkt bevor in die Liste ein Element eingefügt wird, dass an der richtigen Stelle eingefügt wird, so dass es z.B. alphabetisch eingefügt wird. z.B. -> hallo liebe community
    eingefügt soll das so: community hallo liebe

    Ich bin soweit gekommen, dass ich endlich eine Liste hinbekommen habe, die Wörter einfügt.
    In der Methode anhaengen, müsste ich etwas ändern, damit es sortiert eingefügt wird, nur ich weiß nicht wie? Mir ist schon klar, dass z.B. ich die Liste vor dem Einfügen durchgehen muss, und mit dem aktuellen Element vergleichen muss, ob großer oder kleiner, und dann dieses Element dranhängen, und die Zeiger dementsprechend korrekt setzen muss. Bin für jede Hilfe dankbar!!! 😉

    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    
    typedef struct _node{
    
      char *name;
      struct _node *next;
    
    }node;
    
    typedef node *ptr;
    
    ptr anhaengen(ptr l, char *name){
    
      ptr n=malloc(sizeof(node));
      n->name=name;
      n->next=NULL;
      if(l==NULL){
        return n;
      }
    
      ptr last=l;
      while(last->next){
        last=last->next;
      }
    
      last->next=n;
    
      return l;
    
    }
    
    void show(ptr l){
    
      while(l->next){
    
        printf("%s ", l->name);
        l=l->next;
      }
      printf("%s\n", l->name);
    }
    int main(int argc, char *argv[]){
    
      ptr l=NULL;
    
      int i;
      for(i=1;i<argc;i++){
    
        l=anhaengen(l,argv[i]);
      }
    
       show(l);
      free(l);
    
      return 0;
    
    }
    


  • Hallo,
    ich habe deine Struktur ein wenig nach meiner Nase 😃 angepasst.
    Z.B. mag ich keine führenden Unterstriche in den Bezeichnern und spendiere
    gern einen großen Buchstaben für einen Strukturnamen/Strukturtypen.

    Die anderen wichtigeren Dinge, die mir auffallen, sind:

    free(l);
    

    Damit gibst du nur den Speicher des ersten Elements der Liste frei.
    Wenn deine Liste mehr als ein Element hat, bleibt ein Speicherleck ( memory leak ).

    Zum Anhängen eines neuen Elements an deine Liste brauchst du sie nicht
    immer wieder neu von vorn zu durchlaufen. Spendiere einfach eine Variable,
    die sich das Ende der Liste merkt und hänge an sie die neuen Elemente an.

    Beim Sortieren durch Einfügen hast du allerdings keine andere Wahl - die
    Liste muss beim Einfügen eines neuen Elements von vorn durchlaufen werden.

    #include <stdio.h> 
    #include <stdlib.h> 
    #include <string.h> 
    
    typedef struct node Node;
    
    struct node
    { 
    	char *name; 
    	Node *next; 
    }; 
    
    Node* new_node()
    {
    	return calloc ( 1, sizeof ( Node ) );
    }
    
    void show ( Node* a )
    { 
    	while ( a )
    		printf ( "%s", a->name ), a = a->next;
    } 
    
    int a_less_b ( Node* a, Node* b )
    {
    	return strcmp ( a->name, b->name ) < 0;
    }
    
    Node* insert ( Node* a, Node* b )
    {
    	Node* first = a, *c = NULL;
    	if ( a == NULL ) return b;
    	while  ( a && a_less_b ( a, b ))
    		c = a, a = a->next;
    	if ( a && !c ) b->next = a, first = b;
    	else c->next = b, b->next = a;
    	return first;
    }
    
    void free_list ( Node* a )
    {
    	Node* b = a;
    	while ( b )
    		b = b->next, free ( a ), a = b;
    }
    
    enum {argc = 3};
    
    int main()
    { 
    	int i = 0;
    	char* argv[argc] = { "c", "b", "a" };
    	char a, b, c;
    
    	Node* first = NULL, *new = NULL;
    
    	while ( i < argc )
    	{
    		if ( NULL == ( new = new_node() )) break;
    		new->name = argv[i++];
    		first = insert ( first, new );
    	}
    
    	show ( first ); 
    	free_list ( first ); 
    
    	return 0; 
    }
    


  • danke 🙂
    Eine Frage, kannst du mir die Zeile (59) erklären, wieso muss dies sein?

    if ( NULL == ( new = new_node() )) break;
    


  • Mit new_node wird dynamisch Speicher angefordert und einen Pointer auf den Speicher zurückgegeben. Soetwas kann schief gehen, wenn der Speicher alle ist, der virtuelle Adressraum alle ist oder Jupiter, Saturn und Pluto in einer Linie auf Alpha Zentauri zeigen. In diesem Falle wird einfach 0 zurückgegeben, was anzeigt, dass das Speicheranfordern fehlgeschlagen ist.
    In Zeile 60 wird der Speicher dann benutzt. Wenn es ihn aber nicht gibt stürzt das Programm mit einem Segmentation Fault ab, daher wird vorher überprüft ob es geklappt hat.



  • Big Brother schrieb:

    Beim Sortieren durch Einfügen hast du allerdings keine andere Wahl - die
    Liste muss beim Einfügen eines neuen Elements von vorn durchlaufen werden.

    Man kann sich immer das zuletzt eingefügte Element merken und solange das nächste einzufügende größer ist, braucht man es nur anzuhängen. Die Liste muss also nicht in jedem Fall von vorn durchlaufen werden.
    Danke für den Monolog. 😃


Log in to reply