Comment écrire une fonction dans une fonction (list_map)

Question

Bonjour J'ai récemment posé des questions sur les listes liées à C.
The link was found here

D'abord, je tiens à remercier tout le monde pour me aider avec cela. Mais j'ai un problème que je ne peux pas comprendre. J'ai même demandé au professeur mais il m'a envoyé un courriel avec peu d'informations. Fondamentalement, j'écris une liste liée en C (voir lien ci-dessus). L'une des choses que le professeur nous donne dans le fichier d'en-tête est la suivante:

void list_map(INTLIST *list, void (*f)(void *)); 
/*Applies a function to each element of the list */ 

Alors je lui ai envoyé un courriel à ce sujet et dit:

Une autre question, dans le fichier d'en-tête que vous n'avez pas défini le tri fonction, avons-nous besoin d'écrire une fonction de tri avec le prototype et enfin ce qui est list_map

et il m'a répondu avec:

Vous êtes invité à implémenter une fonction de tri f, appelée via list_map (list, f). J'espère que cela efface vos doutes.

Mes seuls doutes sont ce n'était pas entièrement enseigné. Je peux comprendre comment trier la liste chaînée en fait un code de pseudo ici:

tmp=head; 

while(tmp!=NULL) 
{ 
    tmp2=tmp->next; //pointer to next node 
    while(tmp2!=NULL) 
    { 
    if (tmp2->data < tmp->data) 
     { 
     int x = tmp2->data; 
     tmp2->data = tmp->data; 
     tmp2->data = x; 
     } 
    tmp2=tmp2->next; 
    } 
    tmp=tmp->next; 
} 

Je sais que les experts pourraient dire que ce ne sont pas les plus efficaces, et je comprends que je suis en ce moment en train d'apprendre et d'essayer de faire fonctionner les choses. Je peux nettoyer après les mots ... ainsi de suite à ma question.

Ma question est donnée J'ai la fonction de tri (dans le cas du professeur il l'appelle f). Comment puis-je appeler cette fonction de tri lorsque la signature est:

void list_map(INTLIST* list, void (*f) (void*)); 

Est-ce que je peux dire simplement:

list_map(myList, f()); //apply function f to the current linked list 

Ou dois-je vraiment besoin de définir quelque part list_map? Je ne suis pas l'étudiant typique à la recherche de quelqu'un pour faire mon travail. J'essaie vraiment de comprendre cela du mieux que je peux.

Merci à vous tous.

[EDIT PORTION]

Je voulais ajouter que l'une des affiches Kaleb P. dit

« Ainsi, votre travail consiste à créer une fonction de tri que vous passerez . à list_map Notez que la syntaxe correcte pour passer en sera: »

donc, si mon code simplement th est:

dans le fichier .h I prototyper la fonction:

void myCustomSort(void*); 

Et puis dans le.cpp il devient:

void myCustomSort(void*f) 
{ 
tmp=f->head; 

while(tmp!=NULL) 
{ 
    tmp2=tmp->next; //pointer to next node 
    while(tmp2!=NULL) 
    { 
    if (tmp2->data < tmp->data) 
     { 
     int x = tmp2->data; 
     tmp2->data = tmp->data; 
     tmp2->data = x; 
     } 
    tmp2=tmp2->next; 
    } 
    tmp=tmp->next; 
} 
} 

Et pour l'appeler dans le principal, je voudrais juste faire:

list_map(myListPointer, &myCustomSort); 

Mais ne pas avoir besoin de définir list_map quelque part? Parce que c'est dans le fichier .h ne dois-je pas le définir?

Answer 1

En supposant list_map est mis en œuvre comme celui-ci, donnant f chaque noeud dans un ordre séquentiel,

void list_map(INTLIST *list, void (*f)(void *)) { 
    INTLIST *node; 
    for (node = list; node; node = node->next) 
     f(node); 
} 

vous pouvez mettre en œuvre un selection sort

void list_sort(INTLIST *list) { 
    list_map(list, swap_head_with_smallest); 
} 

où void swap_head_with_smallest(void *) swaps la donnée d'un noeud donné avec le plus petit des données de tous les nœuds qui le suivent dans la liste.

---

Comme c'est le devoir, j'essaye de ne pas donner toute la solution.

void swap_head_with_smallest(void *list) { 
    INTLIST *head = list; 
    INTLIST *smallest; 

    /* set smallest the smallest node of 
     head, head->tail, head->tail->tail, etc. */ 

    /* swap head->datum and smallest->datum */ 
} 

Answer 2

Je crois que la fonction list_map appelle le pointeur de fonction f() qui est un pointeur vers une fonction qui prend un pointeur vide et renvoie void. Si tel est le cas, c'est une manière folle de mettre en œuvre un tri mais faisable.

Définition d'une fonction comme

void Test(void *) 
{...} 

et passer dans la list_map() comme si

list_map(listptr,Test); 

Je suppose que votre fonction de test est appelée pour chaque élément dans la liste.

Answer 3

Le deuxième paramètre à list_map est un pointeur pour fonctionner renvoyer void et en prenant un pointeur vide. Puisque list_map semble être une fonction map, je suppose qu'il appellera f (le pointeur vers une fonction) pour chaque élément de la liste.

Ainsi, votre travail consiste à créer une fonction de tri que vous passerez à list_map. Notez que la syntaxe correcte pour le passage en sera:

void yourCustomSort(void*); 
list_map(myList, yourCustomSort); 

Je suppose que cela que le void* étant passé dans votre fonction de tri sera probablement à un noeud dans la liste chaînée.

MergeSort est un bon choix pour le tri des listes liées.

Answer 4

Votre professeur essaie de vous enseigner un concept qui est commun dans la programmation fonctionnelle, qui est l'idée d'une fonction d'ordre supérieur . Une fonction d'ordre supérieur peut prendre d'autres fonctions en tant que paramètres, un peu comme

list_of_cosines = map(cos, list_of_inputs) 

où list of inputs est une série de valeurs à virgule flottante, et cos est la fonction cosinus normal.La fonction map appellera cos pour chaque valeur dans list_of_inputs et retournera une liste des résultats correspondants.

fonctions C ne peuvent pas prendre d'autres types de fonction en tant que paramètres, mais ils peuvent prendre pointeurs aux fonctions en tant que paramètres (habituellement appelé un rappel); l'exemple canonique est la fonction de bibliothèque qsort(), qui prend comme un de ses paramètres un pointeur vers une fonction qui accepte deux pointeurs vers void et renvoie -1, 0 ou 1 selon que v1 < v2, v1 == v2 ou v1 > v2, respectivement. Par exemple:

int compareIntValues(const void *v1, const void *v2) 
{ 
    int lv1 = *(int *) v1; // convert inputs from pointers to void 
    int lv2 = *(int *) v2; // to the type we're actually interested in 
    if (lv1 < lv2) return -1; 
    if (lv1 > lv2) return 1; 
    return 0; 
} 

int main(void) 
{ 
    int values[] = {3, 1, 4, 5, 7, 9, 6, 2}; 
    ... 
    qsort(values,        // buffer containing items to sort 
     sizeof values/sizeof values[0], // number of items to sort 
     sizeof values[0],     // size of each item 
     compareIntValues);     // comparison function 
    ... 
} 

qsort() appellera alors compareIntValues pour commander les éléments en values. Similaire aux expressions de tableau, un désignateur de fonction aura son type implicitement converti de «fonction retournant T» en «pointeur vers la fonction retournant T» selon le contexte.

À ce stade, je devine, mais il me semble que votre professeur veut vous d'écrire la fonction list_map afin qu'il appellera une fonction de tri f avec la liste comme paramètre, quelque chose comme ce qui suit:

void list_map(INTLIST *list, void (*f)(void *)) 
{ 
    // sort the list by passing it to f 
    f(list); // or (*f)(list); 
} 

void sortListAscending(void *ptr) 
{ 
    INTLIST *ilptr = ptr; 
    /** 
    * sort the list in ascending order 
    */ 
} 

void sortListDescending(void *ptr) 
{ 
    INTLIST *ilptr = ptr; 
    /** 
    * sort the list in descending order 
    */ 
} 

int main(void) 
{ 
    INTLIST *theList; 
    ... 
    list_map(theList, sortListAscending); // sort the list in ascending order 
    ... 
    list_map(theList, sortListDescending); // sort the list in descending order 
    ... 
} 

L'interface fournie par votre professeur est un peu confuse; le pointeur de liste et le paramètre à f() doivent être void * (dans ce cas, vous pouvez utiliser list_map pour mapper des fonctions à différents types de liste) ou le pointeur de liste et le paramètre à f doivent être INTLIST * (puisque vous semblez traiter avec les types INTLIST). Si j'ai raison, alors l'exéricise est un peu inutile en surface (pourquoi ne pas appeler la fonction de tri directement?), Mais il se peut que votre professeur soit en train de construire quelque chose d'un peu plus généraliste. Après tout, il n'y a aucune raison que f doive être une fonction de tri; il peut s'agir d'une fonction permettant d'afficher la liste, ou de sauvegarder la liste dans un fichier, ou autre chose.

J'ai un autre exemple d'utilisation des rappels pour trier une liste here; cela peut aider à illustrer pourquoi cette méthode est utile.

EDIT

exemple de ephemient de ce list_map doit faire est probablement beaucoup plus proche de ce que votre professeur a l'intention que ce que je l'ai écrit.

Answer 5

Si dans votre nœud il y a un pointeur vers la tête de la liste, vous devez utiliser le pointeur de la liste comme frontière. Laisse-moi expliquer. La fonction de carte est un concept commun en programmation fonctionnelle, pour l'instant, vous devez juste savoir que c'est une fonction qui obtient une liste et appliquer une autre fonction (la fonction appliquée) à chaque nœud de la liste a été donnée à lui. Je parie que tu le savais déjà.

Le langage C n'a pas, si je me souviens bien, de fonction de carte, donc vous devez en définir un par vous-même. Ce n'est pas très difficile: il suffit de partir de la tête de la liste et marcher jusqu'à la queue. Pour chaque étape, passez le noeud de liste en cours à la fonction qui effectue l'opération que vous devez effectuer (dans ce cas, le tri).

Maintenant, il y a votre mission.

• Vous ne pouvez pas obtenir des données de la fonction appliquée (elle retourne void)
• Vous devez marcher vers le bas jusqu'à la fin de la liste qui passe chaque nœud unique à la fonction qui font le tri.
• Il est inutile de trier la liste que vous n'avez pas déjà visitée, car vous continueriez à la trier pour chaque nœud (en triant un jeu déjà trié, il n'est pas trop intelligent);)
• Votre fonction appliquée un seul pointeur. Ceci en indiquant clairement que ce pointeur (le nœud où vous vous trouvez) représente une ligne: à sa gauche (à la tête) il y a la partie de la liste déjà triée, à droite (à la queue) il y a les éléments sauvages.
• Depuis votre fonction appliquée obtenir comme entrée un simple vide *, je pense qu'il est préférable de laisser les pointeurs seul et échanger la charge utile des noeuds

dit, le pseudocode pour votre fonction de tri , l'un des plus possibile, peuvent être:

void ascendingSort(void*f) 
{ 
    cursor=f->head; 
    placed=false; 

    while(!placed and cursor!=f) { 
    if (cursor->data < f->data) { 
     cursor = cursor->next; 
    } else { 
     swap(cursor->data, f->data); 
     placed=true; 
    } 
    } 

    while(cursor!=f) { 
     cursor = cursor->next; 
     swap(cursor->data, f->data); 
    } 

}

Ou, sous une forme plus concise:

void ascendingSort(void*f) 
{ 
    cursor=f->head; 

    while(cursor!=f) { 
    if (cursor->data > f->data) { 
     swap(cursor->data, f->data); 
    } 
    cursor = cursor->next; 
    } 
}