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 ElementsNULL
ist?