单链接列表上的快捷方式

我正在尝试在单个链表上为QUICKSORT编写一个简单的C代码。 程序将获得一个txt文件，其中包含密码和使用此密码的频率。 程序应按顺序对密码进行排序。 有人可以告诉我如何编写函数void qsort_list，因为我不明白如何获得“partiition（）”需要的3个参数。

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

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

笔记：

• 我将pivot更改为pivotKey，您只需要知道拆分列表的键。 它甚至可能是一个不存在的密钥（例如，第一个和最后一个之间的平均值）
• 基于上述说法，您必须创建分区函数，记住在从中获取元素时更新原始列表并将它们插入到一个子列表中。 分区后，您的原始列表将为空。 或者，您可以考虑删除更多元素，以便原始列表替换左侧列表。
• 您必须实现join函数，该函数在mylist中插入左右（按此顺序）的所有元素。 您不需要逐个移动元素，只需操纵第一个和最后一个指针即可。