verkette liste ausgeben sortiert nach einen String



  • hallo,
    ich habe eine verkettete liste von computer einträge.
    struct computereintrag
    {
    int key;
    char * computername;
    int typ;//laptop(2) oder desktop(1)
    }

    die Liste ist sortiert nach dem key.

    jetzt möchte ich die Liste ausgeben aber sortiert nach dem computername(char*)
    ich weiss dass ich strcmp verwenden soll aber es fehlt mir den algorithmus

    danke im voraus





  • sort() klappt aber nur mit arrays. für das sortieren von verketteten listen gibts in der stdlib leider keine funktion. die muß man selber programmieren. ist aber ein bißchen knifflig. insbesondere, wenn die liste nur einfach verkettet ist.

    EDIT
    wär vielleicht mal wieder ein fall für einen code-post von mir *hihi*



  • hier mal ne runde code:

    #include <stdio.h>
    #include <stdlib.h>
    #include <stddef.h>
    
    struct list_elm
    {
      struct list_elm *next;
      int num;
    };
    
    struct list_elm
    *make_list_elm (int num, struct list_elm *next)
    {
      struct list_elm *elm;
    
      elm       = (struct list_elm*)malloc(sizeof(struct list_elm));
      elm->next = next;
      elm->num  = num;
    
      return elm;
    }
    
    struct list_elm
    *make_random_list (void)
    /* make list of 10 elements with a random value in the num field */
    {
      struct list_elm *elm;
      int i;
    
      srand(0);
    
      elm=make_list_elm(rand(),NULL);
    
      for(i=1; i<10; i++)
        elm=make_list_elm(rand(),elm);
    
      return elm;
    }
    
    void
    print_list (struct list_elm *elm)
    {
      for(; elm; elm=elm->next)
        printf("%d\n",elm->num);
    }
    
    void
    *sort_list (void *first_elm, int nextp_offs, int (*cmp)(void*,void*))
    {
      void *elm,
           *prev_elm,
           *next_elm,
           *old_elm;
      int   modified=1;
    
      /* just bubblesort, ascending order */
    
      while(modified)
      {
        modified=0;
    
        prev_elm = NULL;
        elm      = first_elm;
        next_elm = *(void**)((char*)elm+nextp_offs);
    
        while(next_elm)
        {
          if((*cmp)(elm,next_elm)>0)
          {
            if(prev_elm)
              *(void**)((char*)prev_elm+nextp_offs)=next_elm;
            else
              first_elm=next_elm;
    
            *(void**)((char*)     elm+nextp_offs)=*(void**)((char*)next_elm+nextp_offs);
            *(void**)((char*)next_elm+nextp_offs)=elm;
    
            modified=1;
    
            old_elm  = elm;
            elm      = next_elm;
            next_elm = elm;
          }
    
          prev_elm = elm;
          elm      = next_elm;
          next_elm = *(void**)((char*)elm+nextp_offs);
        }
      }
    
      return first_elm;
    }
    
    int
    cmp_list_elm (void *elm1, void *elm2)
    {
      return ((struct list_elm*)elm1)->num-((struct list_elm*)elm2)->num;
    }
    
    int
    main()
    {
      struct list_elm *elm;
    
      elm=make_random_list();
    
      puts("unsorted list:");
      print_list(elm);
    
      elm=(struct list_elm*)sort_list((void*)elm,offsetof(struct list_elm,next),cmp_list_elm);
    
      puts("\nsorted list:");
      print_list(elm);
    
      return EXIT_SUCCESS;
    }
    

    die funktion sort_list() sortiert einfach verkettete listen. ist zwar nur bubble-sort, sollte aber reichen. natürlich könnte man einen noch wesentlich schnelleren sortier-algorithmus verwenden, wär mir aber est mal zu viel arbeit gewesen. vielleicht reich ich ihn ja noch nach 🕶



  • Kleiner Tipp, verwende doch gleich char* anstatt dauernd über void** dorthin zu casten, sieht ja schlimm aus.


Anmelden zum Antworten