Quicksort on Single Связанный список

Question

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

#include <stdio.h> 
#include <stdlib.h> 
#include <assert.h> 


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) < (pivot -> 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 <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; 
} 

Answer 1

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

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

2 - Чтобы разбить список элементов в 2 подсписках: один с элементами < pivot (или < =), а другой с элементами> = поворот (или>). Вы вызываете этот список влево и вправо.

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, вам просто необходимо знать ключ, чтобы разделить список. Это может быть даже несуществующий ключ (например, средний между первым и последним)
• На основании указанного вы должны создать свою функцию раздела, не забудьте обновить исходный список, когда вы берете из него элементы и вставьте их в один подсписчик. После раздела ваш исходный список будет пустым. Кроме того, вы можете подумать о том, как просто удалить большие элементы, чтобы исходный список заменил левый список.
• Вы должны реализовать функцию соединения, которая вставляет все элементы слева и справа (в указанном порядке) в мой список. Вам не нужно перемещать элементы по одному, просто манипулируйте первым и последним указателями.