QuickSort mit einfach verfetteterer Liste



  • Guten Morgen!

    Ich muss für ein Projekt einen Code schreiben, welcher eine txt Datei einliest, in welcher 30 Passwörter stehen, welche am häufigsten verwendet werden und deren Häufigkeit. Nun soll ich diese in eine einfach verkettete Liste einlesen und danach mit QuickSort nach der Häufigkeit sortieren. Wichtig dabei ist, dass es QuickSort ist. Mit dem einlesen etc. bin ich sehr gut klargekommen. Doch ich weiß überhaupt nicht, wie ich nun an den QucikSort Code rangehen soll.

    Hier mal mein Code, wie ich die Datei einlese und in die verkettete Liste packe:

    [code]
    #include <stdio.h>
    #include <stdlib.h>
    #include <assert.h>
    #include <string.h>
    
    typedef struct list_element {
        char password[100];
        int frequency;
        struct list_element *next;
    } list_element;
    
    typedef struct list {
        list_element *first;
        list_element *last;
    } list;
    
    void init_list(list* mylist)
    {
        mylist->first=NULL;
        mylist->last=NULL;
    }
    
    // Diese Funktion fügt Listenelemente am Anfang der Liste an
    void insert_front(list_element* le, list* mylist)
    {
    
       if (mylist->first){
    		le->next = mylist->first;
    	}
    	if(mylist->last==NULL){
            mylist->last = le;
    	}
    
    	mylist->first = le;
    }
    
    // Speicher für Listenelemente wieder freigeben
    void free_list(list* mylist)
    {
      list_element *curr = mylist->first;
      while (curr != NULL)
      {
        list_element *next = curr->next;
        free (curr);
        curr = next;
      }
    }
    
    // Namen, Zahlen Paare in Liste einlesen
    void read_data(char* filename, list* mylist)
    {
        assert(mylist != NULL);
        FILE* f=fopen(filename,"rb");
        assert(f != NULL);
        char temp_pass[100];
        int temp_freq;
        while (fscanf(f,"%s %d", temp_pass, &temp_freq) == 2)
        {
            list_element *new_element = malloc (sizeof (list_element));
            assert (new_element != NULL);
            strcpy(new_element->password, temp_pass);
            new_element->frequency = temp_freq;
            insert_front(new_element, mylist);
        }
        fclose(f);
    }
    list_element* partition(list* input, list* left, list* right)
    {
    
    //Hier soll eigentlich das Pivot element gefunden werden und dann die Liste geteilt werden...
    
    }
    
    void qsort_list(list* mylist)
    {
    
    //Hier der QuickSort
    
    }
    
    // Liste ausgeben
    void print_list(list* mylist)
    {
      list_element *curr_element = mylist->first;
    
      while (curr_element != NULL)
      {
        printf ("%s %d\n",curr_element->password, curr_element->frequency);
        curr_element = curr_element->next;
      }
      printf ("\n");
    }
    
    // Argumente einlesen, Liste kreieren, verarbeiten und ausgeben
    int main(int argc, char** args)
    {
        if (argc != 2)
        {
            printf("Nutzung: %s <Dateiname>\n",args[0]);
    	return 1;
        }
        list mylist;
        init_list(&mylist);
        read_data(args[1],&mylist);
        qsort_list(&mylist);
        printf("Sortierte Liste:\n");
        print_list(&mylist);
        free_list(&mylist);
        return 0;
    }
    

    Ich hoffe hier einfach auf Hilfe, da ich gar keine Ahnung habe... 😞

    Mit freundlichen Grüßen

    Mark



  • Der Tippfehler im Titel ist super - LOL!

    Eine einfach verkettete Liste und Quicksort widersprechen sich aber ein wenig, da du ja beim Quicksort jeweils von beiden Enden die Werte vergleichst (und bei einer einfach verketteten Liste kannst du ja nicht rückwärts iterieren).

    Ich habe aber gerade bei QuickSort für verkettete Listen gelesen, daß es wohl doch eine Variante dafür gibt (wenn auch sehr ineffektiv), mußt jetzt nur den den Psuedocode auf deinen Code übertragen.



  • Eine Möglichkeit wäre ein Array mit Zeigern auf list_element

    - Lege die Adressen von deiner Liste in dem Array ab.
    - Sortiere das Array
    - Baue die Liste anhand des sortierten Arrays neu zusammen



  • Sorry für OT, aber wo wird eigentlich sichergestellt, dass der next pointer des letzten Elements NULL ist?


Log in to reply