我正在尝试在单个链表上为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; }
在链表上快速排序算法的一般概念是:
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); }
笔记:
以上就是c/c++开发分享单链接列表上的快捷方式相关内容,想了解更多C/C++开发(异常处理)及C/C++游戏开发关注计算机技术网(www.ctvol.com)!)。
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/519419.html