Invertire la lista collegato in C++

Jinku Hu 12 ottobre 2023

C++ C++ Data Structure

Questo articolo dimostrerà come invertire una struttura di dati di elenchi collegati in C++.

Usa la funzione iterativa per invertire la lista collegato in C++

Supponiamo che l’oggetto di destinazione sia un elenco collegato singolarmente e implementiamo frammenti di codice di conseguenza. Per prima cosa, dobbiamo esaminare le utilità delle funzioni di base nel codice del driver implementato per dimostrare l’esempio.

Il nodo della lista concatenata è una semplice struct con un singolo oggetto dati stringa e un puntatore al nodo successivo. Abbiamo anche la funzione addNewNode che accetta due argomenti, Node* e un riferimento alla string. La funzione addNewNode viene invocata più volte nella routine main per costruire un nuovo oggetto elenco e memorizzare stringhe dal vettore data_set. La funzione alloca ogni nodo sulla memoria dinamica e restituisce il puntatore al nodo appena creato.

Un’altra funzione utile per la nostra struttura dati della lista collegata è printNodes, che viene utilizzata per inviare dati da ogni nodo al flusso cout. Quest’ultimo ci aiuterà a verificare vagamente la correttezza della funzione di inversione. Nota che printNodes mantiene il conteggio dei nodi durante l’attraversamento della lista e stampa l’indice per ogni elemento. Infine, dobbiamo deallocare tutti i nodi prima che il programma esca. Questo passaggio non è necessario per la dimostrazione della funzione di inversione, ma è importante per qualsiasi progetto del mondo reale ripulire tutta la memoria allocata durante l’esecuzione.

#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;
}

Produzione:

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

Una volta inizializzata una nuova lista collegata e salvata l’intestazione della lista in un puntatore separato, possiamo usarla per invertire il contenuto. In questo caso, abbiamo implementato la funzione reverseList, che accetta un singolo argomento Node* e restituisce un nuovo nodo radice. All’inizio, duplichiamo il puntatore passato e lo memorizziamo come variabile head. Abbiamo anche bisogno di altri due puntatori di tipo Node per fare la contabilità interna durante il cicli while.

L’algoritmo di inversione può essere descritto come segue: memorizziamo il puntatore del nodo successivo in una variabile temporanea (next) e assegniamo il valore nullptr a quello originale. Di conseguenza, il nodo head originale punterà al nullptr come nodo successivo nella lista. Successivamente, aggiorniamo la variabile head per memorizzare il prossimo (il secondo) nodo nella lista originale e salviamo anche l’indirizzo del nodo head originale in una variabile temporanea separata.

Ripetiamo i passaggi precedenti finché il puntatore head non restituisce nullptr, il che significherebbe che è stata raggiunta la fine della lista. Alla fine, restituiamo l’indirizzo del nuovo nodo di testa memorizzato nella variabile temporanea n. Di conseguenza, il programma main chiama la funzione printNodes per consentire all’utente di confrontare i contenuti della lista collegata modificata.

#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;
}

Produzione:

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

Autore: 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

Usa la funzione iterativa per invertire la lista collegato in C++

Articolo correlato - C++ Data Structure