Application des fonctions récursives C++ dans les algorithmes de recherche ?

Les fonctions récursives sont utilisées dans les algorithmes de recherche pour explorer des structures de données arborescentes. La recherche en profondeur utilise une pile pour explorer les nœuds, tandis que la recherche en largeur utilise une file d'attente pour parcourir couche par couche. Dans des applications pratiques, telles que la recherche de fichiers, les fonctions récursives peuvent être utilisées pour rechercher un fichier donné dans un répertoire spécifié.

Application de la fonction récursive C++ dans l'algorithme de recherche

Une fonction récursive est une fonction spéciale qui s'appelle à l'intérieur de la fonction. Cette approche est particulièrement utile lors de la résolution de problèmes liés aux structures de données arborescentes telles que la recherche et le parcours.

Depth First Search (DFS)

L'algorithme Depth First Search (DFS) utilise une pile pour explorer les nœuds, rechercher en profondeur dans toutes les branches possibles d'un nœud, puis revenir au nœud précédent du nœud pour continuer l'exploration. . Une branche jusqu'à ce que l'arbre entier soit parcouru.

// 执行深度优先搜索
void DFS(Node* node) {
  // 访问当前节点
  Visit(node);

  // 递归遍历所有子节点
  for (Node* child : node->children) {
    DFS(child);
  }
}

Breadth First Search (BFS)

L'algorithme de recherche en largeur (BFS) utilise une file d'attente pour explorer les nœuds et parcourir l'arborescence dans l'ordre hiérarchique. Il ajoute tous les nœuds de la couche actuelle à la file d'attente, puis accède à ces nœuds dans l'ordre. Après avoir visité tous les nœuds enfants d’un nœud, passez au niveau suivant.

// 执行广度优先搜索
void BFS(Node* root) {
  // 创建队列并添加根节点
  Queue<Node*> queue;
  queue.push(root);

  // 当队列不为空时，继续遍历
  while (!queue.empty()) {
    // 取出队首节点
    Node* node = queue.front();
    queue.pop();

    // 访问当前节点
    Visit(node);

    // 将子节点添加至队列
    for (Node* child : node->children) {
      queue.push(child);
    }
  }
}

Cas pratique : Rechercher des fichiers

Supposons qu'il existe un système de fichiers dans lequel chaque fichier ou répertoire peut contenir des sous-fichiers et des sous-répertoires. Nous pouvons utiliser des fonctions récursives pour rechercher un fichier donné.

// 在指定目录中搜索文件
bool SearchFile(string directory, string filename) {
  // 获取当前目录的所有子文件和子目录
  vector<string> entries = GetEntries(directory);

  // 遍历子项
  for (string entry : entries) {
    // 如果文件是目录，则递归搜索
    if (IsDirectory(entry)) {
      if (SearchFile(entry, filename)) {
        return true;
      }
    } else {
      // 如果文件是目标文件，则返回 true
      if (entry == filename) {
        return true;
      }
    }
  }

  // 如果未找到文件，则返回 false
  return false;
}

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!