Inverser la liste chaînée en C++

Jinku Hu 12 octobre 2023

C++ C++ Data Structure

Cet article montrera comment inverser une structure de données de liste chaînée en C++.

Utilisez la fonction itérative pour inverser la liste chaînée en C++

Nous supposons que l’objet cible est une liste à chaînage unique et implémentons des extraits de code en conséquence. Dans un premier temps, nous devons examiner les utilitaires de fonction de base dans le code du pilote implémenté pour illustrer l’exemple.

Le nœud de liste chaînée est une simple struct avec un seul objet de données string et un pointeur vers le nœud suivant. Nous avons également la fonction addNewNode qui prend deux arguments, Node* et une référence à la string. La fonction addNewNode est invoquée plusieurs fois dans la routine main pour construire un nouvel objet de liste et stocker les chaînes du vecteur data_set. La fonction alloue chaque nœud en mémoire dynamique et renvoie le pointeur vers le nœud nouvellement créé.

Une autre fonction utile pour notre structure de données de liste chaînée est printNodes, qui est utilisée pour sortir les données de chaque nœud vers le flux cout. Ce dernier nous aidera à vérifier vaguement l’exactitude de la fonction d’inversion. Notez que printNodes conserve le nombre de nœuds pendant le parcours de la liste et imprime l’index pour chaque élément. Enfin, nous devons désallouer tous les nœuds avant la fin du programme. Cette étape n’est pas nécessaire pour la démonstration de la fonction d’inversion, mais il est important pour tout projet réel de nettoyer toute la mémoire allouée pendant l’exécution.

#include <iostream>
#include <string>
#include <vector>

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;

struct Node {
  struct Node *next{};
  string data;
};

struct Node *addNewNode(struct Node *node, string &data) {
  auto new_node = new Node;
  if (node) node->next = new_node;
  new_node->next = nullptr;
  new_node->data = data;
  return new_node;
}

void freeNodes(struct Node *node) {
  struct Node *tmp = nullptr;
  while (node) {
    tmp = node;
    node = node->next;
    delete tmp;
  }
}

void printNodes(struct Node *node) {
  auto count = 0;
  while (node) {
    cout << "node " << count << " - data: " << node->data << endl;
    node = node->next;
    count++;
  }
}

int main() {
  struct Node *tmp, *head = nullptr;

  vector<string> data_set = {"Rocket Lake", "Alder Lake", "Tiger Lake",
                             "Meteor Lake"};

  head = addNewNode(head, data_set.at(0));
  tmp = head;
  for (auto it = data_set.begin() + 1; it != data_set.end(); ++it) {
    tmp = addNewNode(tmp, *it);
  }

  printNodes(head);

  freeNodes(head);
  return EXIT_SUCCESS;
}

Production:

node 0 - data : Rocket Lake node 1 - data : Alder Lake node 2 -
                                            data : Tiger Lake node 3 -
                                                   data : Meteor Lake

Une fois que nous avons initialisé une nouvelle liste chaînée et stocké le début de la liste dans un pointeur séparé, nous pouvons l’utiliser pour inverser le contenu. Dans ce cas, nous avons implémenté la fonction reverseList, qui accepte un seul argument Node* et renvoie un nouveau nœud racine. Dans un premier temps, nous dupliquons le pointeur passé et le stockons en tant que variable head. Nous avons également besoin de deux pointeurs supplémentaires de type Node* pour faire la comptabilité interne pendant la boucle while.

L’algorithme d’inversion peut être décrit comme suit : Nous stockons le pointeur de nœud suivant dans une variable temporaire (next) et affectons la valeur nullptr à celle d’origine. En conséquence, le nœud head d’origine pointera vers le nullptr comme son prochain nœud dans la liste. Ensuite, nous mettons à jour la variable head pour stocker le nœud suivant (le deuxième) dans la liste d’origine et enregistrons également l’adresse du nœud principal d’origine dans une variable temporaire distincte.

Nous répétons les étapes précédentes jusqu’à ce que le pointeur head évalue à nullptr, ce qui signifierait que la fin de la liste est atteinte. Au final, on retourne l’adresse du nouveau nœud de tête stockée dans la variable temporaire n. Par conséquent, le programme main appelle la fonction printNodes pour que l’utilisateur compare le contenu modifié des listes chaînées.

#include <iostream>
#include <string>
#include <vector>

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;

struct Node {
  struct Node *next{};
  string data;
};

struct Node *addNewNode(struct Node *node, string &data) {
  auto new_node = new Node;
  if (node) node->next = new_node;
  new_node->next = nullptr;
  new_node->data = data;
  return new_node;
}

void freeNodes(struct Node *node) {
  struct Node *tmp = nullptr;
  while (node) {
    tmp = node;
    node = node->next;
    delete tmp;
  }
}

void printNodes(struct Node *node) {
  auto count = 0;
  while (node) {
    cout << "node " << count << " - data: " << node->data << endl;
    node = node->next;
    count++;
  }
}

Node *reverseList(struct Node *node) {
  auto head = node;
  Node *n = nullptr;
  Node *next = nullptr;

  while (head) {
    next = head->next;
    head->next = n;

    n = head;
    head = next;
  }
  return n;
}

int main() {
  struct Node *tmp, *head = nullptr;

  vector<string> data_set = {"Rocket Lake", "Alder Lake", "Tiger Lake",
                             "Meteor Lake"};

  head = addNewNode(head, data_set.at(0));
  tmp = head;
  for (auto it = data_set.begin() + 1; it != data_set.end(); ++it) {
    tmp = addNewNode(tmp, *it);
  }

  printNodes(head);

  cout << " ----------------------------------- " << endl;
  printNodes(reverseList(head));

  freeNodes(head);
  return EXIT_SUCCESS;
}

Production:

node 0 - data : Rocket Lake node 1 - data : Alder Lake node 2 -
                                            data : Tiger Lake node 3 -
                                                   data
    : Meteor Lake-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -node 0 -
      data
    : Meteor Lake node 1 -
      data : Tiger Lake node 2 - data : Alder Lake node 3 - data : Rocket Lake

Auteur: Jinku Hu

Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.

LinkedIn Facebook

Utilisez la fonction itérative pour inverser la liste chaînée en C++

Article connexe - C++ Data Structure