Быстрое сортирование по одинарному списку ссылок

Я пытаюсь написать просто код C для QUICKSORT в одном связанном списке. Программа получит txt-файл с паролем и частотой использования этого пароля. Программа должна сортировать пароли по порядку. Может ли кто-нибудь сказать мне, как написать функцию void qsort_list, потому что я не понимаю, как получить 3 параметра, которые необходимы «partiition ()».

#include  #include  #include  typedef struct list_element{ char passwort[100]; int haufigkeit; struct list_element *next; } list_element; typedef struct list{ list; void init_list(list* mylist) { mylist->first=NULL; mylist->last=NULL; } void insert_front(list_element* le, list* mylist) { // HIER Code einfügen if(mylist->first == NULL){ le->next = mylist-> first; mylist->first=le; mylist->last=le; } else { le->next = mylist-> first; mylist->first= le; } } // Speicher für Listenelemente wieder freigeben void free_list(list* mylist) { // HIER Code einfügen } // Namen, Zahlen Paare in Liste einlesen void read_data(char* filename, list* mylist) { assert(mylist != NULL); FILE* f=fopen(filename,"rb"); assert(f != NULL); while (1) { list_element* temp = malloc(siezof(list_element))// * Speicher allozieren fscanf(f,"%s %d",temp->passwort, &temp-> haufigkeit)// * Daten in list_element einlesen insert_front(temp, mylist) // * insert_front benutzen um list_element in Liste einzufügen } fclose(f); } // Pivot finden, das die Liste aufteilt list_element* partition( list* input, list* left, list* right ) { list_element* pivot= list->last; input= mylist; while(mylist->first != mylist->last) { // HIER Code einfügen list_element* list_right = list* right; list_element* list_left = list* left; list_element *i; for(i=list->first; i != NULL; i=i->next){ if ((i -> haufigkeit)  haufigkeit)){ insert_front(i, list_left); } else{ insert_front(i,list_right); } } } } return pivot; } /* void partition1(){ list* pivot= list->last; }return pivot; } */ void qsort_list(list* mylist) { list left = mylist; list first; // = list mylist->first: list pivot= list* last; partition(list* left, list* first, list* pivot); pivot = } // Liste ausgeben void print_list(list* mylist) { // HIER Code einfügen: } // Argumente einlesen, Liste kreieren, verarbeiten und ausgeben int main(int argc, char** args) { if (argc != 2) { printf("Nutzung: %s \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; } 

Общая идея алгоритма быстрой сортировки по связанному списку:

1 – Для выбора ключевого ключа, в вашем случае вы выбираете последний ключ в списке.

2 – Разбить список элементов в 2 подсписках: один с элементами = поворот (или>). Вы вызываете этот список влево и вправо.

3 – заказать левый и правый списки. Это рекурсивная часть: вы используете quicksort для упорядочивания каждого подсписок, если только этот список не пуст или с одним элементом.

4 – Объединение элементов левого и правого списков.

Таким образом, ваш qsort_list должен быть чем-то вроде:

 void qsort_list(list* mylist) { list left,right; int pivotKey= mylist->last->haufigkeit; /* stop condition: mylist empty or with 1 element*/ if( (mylist->first == 0) || (mylist->first == mylist->last) ) return; init_list(left); init_list(right); partition(mylist, &left, &right, pivotKey); /* recursive part: */ qsort_list(&left); qsort_list(&right); join(mylist, &left, &right); } 

Заметки:

  • Я изменил поворот на pivotKey, вам просто нужно знать ключ, чтобы разбить список. Это может быть даже несуществующий ключ (например, средний между первым и последним)
  • Основываясь на сказанном, вы должны создать свою функцию раздела, не забудьте обновить исходный список, когда вы берете из него элементы и вставляете их в один подсписчик. После раздела ваш исходный список будет пустым. Кроме того, вы можете подумать о том, как просто удалить большие элементы, чтобы исходный список заменил левый список.
  • Вы должны реализовать функцию join, которая вставляет все элементы слева и справа (в указанном порядке) в mylist. Вам не нужно перемещать элементы по одному, просто манипулируйте первым и последним указателями.