단일 링크 목록의 Quicksort

Question

단일 링크 목록에 QUICKSORT에 대한 C 코드를 작성하려고합니다. 프로그램은 암호와 사용 빈도가있는 txt 파일을이 암호로받습니다. 프로그램은 암호를 순서대로 정렬해야합니다. 어떤 사람들은 "partiition()"이 필요로하는 3 개의 매개 변수를 얻는 방법을 이해하지 못하기 때문에 qsort_list 함수를 작성하는 방법을 알려줄 수 있습니까?

#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 개의 하위 목록에있는 요소 목록을 분할하려면 : 하나의 요소는 < 피벗 (또는 < =)이고 다른 하나는 요소> = 피벗 (또는>)입니다. 이 목록을 왼쪽 및 오른쪽으로 불러옵니다.

3 - 왼쪽 및 오른쪽 목록을 정렬하려면. 이것은 재귀적인 부분입니다. 목록이 비어 있거나 하나의 요소가 아니라면 quicksort를 사용하여 각 하위 목록을 정렬합니다.

4 - 왼쪽 및 오른쪽 목록의 요소를 연결합니다. 그냥 목록을 분할하는 키를 알 필요가

• 내가 pivotKey에 피벗을 변경 :

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

  주 :

  그래서 qsort_list 같은 것을해야합니다. 존재하지 않는 키 (예 : 첫 번째 키와 마지막 키 사이의 평균)가 될 수도 있습니다.

• 위에서 말한 바에 따르면 파티션 함수를 만들어야하며, 원래의 목록을 업데이트해야합니다 하나의 하위 목록에 삽입하십시오. 원래 목록은 파티션 이후에 비어 있습니다. 또는 더 큰 요소를 제거하는 방법을 생각하면 원래 목록이 왼쪽 목록을 대체하게됩니다.
• 왼쪽과 오른쪽의 모든 요소를 ​​mylist에 순서대로 삽입하는 조인 기능을 구현해야합니다. 요소를 하나씩 이동하지 않고 첫 번째 포인터와 마지막 포인터 만 조작하면됩니다.