Comment puis-je trouver récursivement le plus gros élément d'une liste chaînée avec le nœud principal?

Question

int findLargest (ListNode *p) 
// -------------------------------------------------------------------------- 
// Preconditions: list head pointer is passed as a parameter. 
// Postconditions: returns the largest value in the linked list. 
// -------------------------------------------------------------------------- 
{ 
    if (p->item != NULL) 
    { 
     int largest = p->item; 
     if (largest > p->next->item) 
      ... 
    } 

    ... 
} 

Est-il possible d'écrire cette fonction récursive en ne passant qu'un pointeur en paramètre? Je ne peux pas comprendre comment faire ceci sans ajouter plus de paramètres. Des idées? Je n'utilise que la recherche séquentielle. Rien d'extraordinaire.

Voici la partie de la liste des classes qui seront nécessaires:

struct ListNode 
    { 
     ListItemType item; // A data item on the list. 
     ListNode *next; // Pointer to next node 
    }; // end ListNode 

    ListNode *head; // Pointer to linked list of items. 

Je suis surtout inquiet de la faisabilité du problème. Cela peut-il être fait avec seulement un pointeur comme paramètre?

Answer 1

Ceci est certainement réalisable, même si je suis d'accord que la récursivité n'est pas la meilleure solution pour résoudre ce problème. Dans ce cas, le code non récursif serait plus facile à lire (récursivité), plus rapide (surcharge de l'appel de fonction) et plus efficace en mémoire (évidemment plus de cadres de pile).

Chaque appel récursif renvoie le plus élevé de sa valeur ou de la valeur du reste de la liste.

int findLargest (ListNode *p) { 
    int current = p->item; 
    int next; 

    if (p->next == NULL) { 
     //The value at this node is obviously larger than a non-existent value 
     return current; 
    } else { 
     //Recur to find the highest value from the rest of the LinkedList 
     next = findLargest(p->next); 
    } 

    //Return the highest value between this node and the end of the list 
    if (current > next) { 
     return current; 
    } else { 
     return next; 
    } 
} 

arrête récursivité lorsque l'élément next est nulle.

Answer 2

je trouve que la plupart des problèmes récursifs peuvent être résolus en utilisant le cadre/modèle de réflexion sur:

• Quelles informations dois-je à portée de main en ce moment?
• Quelles informations obtiendrai-je si je fais un appel récursif?
• Comment puis-je combiner ces deux pour obtenir un résultat final?
• (Aussi, assurez-vous d'être clair sur le « scénario de base ».)

Dans ce cas, les réponses sont

• la valeur dans le nœud actuel
• le plus grand élément dans le 'suffixe' de la liste qui vient après ce noeud
• hmmm, c'est à vous de comprendre
• (Que devriez-vous retourner pour la liste vide? Est-ce que les devoirs disent?)

Amusez-vous. :)

Answer 3

Si vous cherchez à retourner juste la plus grande valeur, alors oui vous l'avez déjà écrit.

int FindLargest(ListNode* node){ 
    if (node != NULL){ 
    int downTheListLargest = FindLargest(node->next); 
    if (downTheListLargest > node->item){ 
     return downTheListLargest; 
    } 
    return node->item; 
    } 
    return //?? some max negative value 
} 

Si vous cherchez à retourner un pointeur vers le noeud le plus grand, le paramètre doit être un double pointeur (**), ou la fonction doit retourner un pointeur.

ListNode* FindLargest(ListNode* node){ 
    if (node == NULL){ 
    return NULL; 
    } 
    ListNode* downTheListLargestNode = FindLargest(node->next); 
    if (downTheListLargestNode && downTheListLargestNode->item > node->item){ 
    return downTheListLargestNode; 
    } 
    return node; 
} 

Il n'y a vraiment aucune raison de le faire récursivement. Je suppose que c'est juste un exercice pour apprendre la récursivité, mais je pense que c'est un mauvais exemple d'apprentissage.

Answer 4

Pas besoin de récursion, et votre exemple n'est pas récursif (il devrait s'appeler lui-même).

Il est possible de le faire avec seulement un pointeur comme paramètre.

Conseil: Affectez p à p-> suivant pour avancer dans la liste.

Answer 5

Toujours briser les problèmes de récurrence en deux étapes: la condition d'arrêt et "le reste du problème". Commencez par penser à la condition d'arrêt. Dans les listes liées, c'est généralement le noeud nul. Mais dans votre cas, pensez à ce qui se passe lorsque le nœud donné est nul. Que voulez-vous retourner? La vérité est que vous devez retourner la valeur max n'importe quoi, et quand il n'y a aucun élément dans la liste, il n'y a pas aucun élément max. Dans ce cas, vous pouvez peut-être simplement supposer qu'une liste doit avoir au moins un élément.

Alors, quelle est la condition d'arrêt? La condition d'arrêt est quand il y a un seul élément dans la liste; et dans ce cas la valeur max est la valeur de ce noeud.

L'étape suivante est l'étape récursive. Supposons que vous ayez un élément lié à une liste. Et faites attention comment je décris une liste chaînée: un nœud lié à une liste chaînée. La valeur max est la valeur de ce noeud si elle est plus grande que la plus grande valeur de la liste, ou la plus grande valeur de la liste sinon.

Answer 6

Bien que l'optimisation de la récurrence de queue ne soit pas requise par C, si vous pouvez la transformer en récursion de queue (et vous pouvez le faire sans beaucoup de travail ici), vous pouvez maintenir la lisibilité , la clarté et la concision de récursivité avec mêmes performances (temps et espace) comme la meilleure solution non récursive.

J'ai légèrement modifié les conditions de la fonction afin qu'elle puisse fonctionner sur une liste vide sans nœuds (où p est nulle) et retournera null dans ce cas. C'est récursive, et nécessite un autre paramètre:

ListNode* findLargestRecurse(ListNode* p, ListNode* largest) { 
    // this is an implementation detail, and would not be called directly 
    // requires that largest is not null, but p may be null 
    if (!p) return largest; 
    if (p->item > largest->item) largest = p; 
    return findLargestRecurse(p->next, largest); 
} 

// preconditions: list head pointer is passed as a parameter, and may be null 
// postcondition: returns the node with the largest value, or null 
ListNode* findLargest(ListNode* p) { 
    if (!p) return 0; // mark A, see below 
    return findLargestRecurse(p->next, p); 
} 

avis vous utilisez l'entrée principale, findLargest, pour configurer les conditions initiales/contexte de la récursion réelle, findLargestRecurse.

Cependant, je vous écris cette queue-récursion comme une itération en boucle pour compter moins sur ce qui est actuellement à la fois très compilateur spécifique et généralement peu familiers en C, ce qui est difficile à faire:

// preconditions: list head pointer is passed as a parameter, and may be null 
// postcondition: returns the node with the largest value, or null 
ListNode* findLargest(ListNode* p) { 
    ListNode* largest = 0; 
    for (; p; p = p->next) { 
    if (!largest || p->item > largest->item) { 
     largest = p; 
    } 
    } 
    return largest; 
} 

Vous pouvez séparer la condition !largest de la boucle en la faisant au préalable, en vérifiant un cas de base comme le premier findLargest fait ("marque A").

Et en regardant cela maintenant, vous pouvez vous demander pourquoi j'ai appelé la version récursive plus concise: ce n'est vraiment pas pour cet exemple trivial. C'est en partie parce que C est conçu pour favoriser l'itération (notez la boucle for en particulier), un peu parce que j'ai essayé d'être verbeux dans la récursion au lieu de l'écraser comme je le ferais normalement. parce que c'est juste un problème simple.

Answer 7

J'ai vu un code affiché et ne pouvait pas ne pas ajouter mon ... parce que je pense vraiment que cela pourrait se faire plus simplement :)

Je suppose que item est d'un type numérique.

#include <algorithm> // std::max 
#include <limits> // std::numeric_limits 

ListItemType findLargest(const ListNode* p) 
{ 
    if (p == 0) 
    return std::numeric_limits<ListItemType>::min(); 
    else 
    return std::max(p->item, findLargest(p->next)); 
} 

Comme vous pouvez le voir, beaucoup plus simple, et je pris la liberté d'ajouter un const puisque nous ne sommes certainement pas devoir modifier la liste elle-même!

Answer 8

Voici une autre solution récursive idiomatique, similaire à celle de Matthieu. Contrairement à sa solution, celle-ci exige une liste vide - sans doute, en prenant le plus petit élément d'une liste vide est pas une opération significative:

// Precondition: list is non-empty. 
int find_largest(ListNode const* n) { 
    assert(n != 0 && "find_largest requires non-empty list."); 
    return n->next == 0 ? n->item 
         : max(n->item, find_largest(n->next)); 
} 

Celui-ci lit un peu comme une définition mathématique, en utilisant la notation « cas » :

   { item(i),     if i is the last node 
largest(i) = { 
      { max{item(i), largest(i+1)} else. 

Answer 9

Java version

return max(head, head.value); 
int max(Node node, int currentMax) 
{ 
    if(node==null) 
     return currentMax; 
    if(node.value>currentMax) 
     return max(node.next, node.value); 
    else 
     return max(node.next, currentMax); 
}