Implementare una struttura dati di elenchi collegati circolari in C++

1. Implementare un elenco con collegamento singolo circolare con funzioni membro per aggiungere nuovi elementi alla fine e stampare elementi in C++
2. Implementa il distruttore e la funzione membro per inserire nuovi elementi all’inizio della lista in C++

Questo articolo spiegherà come implementare una struttura dati di elenchi collegati circolari in C++.

Implementare un elenco con collegamento singolo circolare con funzioni membro per aggiungere nuovi elementi alla fine e stampare elementi in C++

Una lista concatenata circolare può essere caratterizzata come una lista concatenata in cui l’ultimo nodo punta all’inizio della lista. Essenzialmente, i nodi nella lista formano un cerchio e non c’è alcun nullptr per delimitare la fine della lista. È possibile utilizzare elenchi collegati circolari per creare strutture di dati in stile coda. La funzione di circolarità può essere aggiunta sia all’elenco a doppio collegamento che a un elenco a collegamento singolo.

In questo caso, implementeremo quest’ultimo. Ricorda che abbiamo bisogno di definire una struttura del nodo che includa un puntatore al nodo successivo e un elemento dati per costruire un elenco concatenato singolarmente. L’oggetto struct ListNode rappresenta un singolo nodo per la nostra implementazione e memorizza un singolo oggetto string denominato data, che servirà come dati dell’elemento per questo esempio. Si noti che è possibile memorizzare qualsiasi oggetto definito dall’utente in un nodo e, se l’oggetto è relativamente più grande, è meglio includerlo come puntatore.

Una volta che abbiamo una struttura di un singolo nodo, possiamo definire una classe CircularList, che ha solo due funzioni membro per i principianti. In genere, una lista concatenata circolare dovrebbe tenere traccia della testa della lista o della sua fine; tuttavia, l’implementatore di solito è libero di prendere la decisione di progettazione della classe in base alle proprie esigenze. Inoltre, la classe CircularList memorizza due puntatori separati per rappresentare l’inizio e la fine della lista.

Il puntatore che memorizza l’inizio/fine della lista può essere un nodo fittizio o un nodo effettivo con i dati. In questo esempio, abbiamo scelto di progettare la classe CircularList in modo che non abbia puntatori fittizi. Abbiamo definito un costruttore per accettare un parametro string per inizializzare il primo nodo nella lista circolare. Si noti che le scelte progettuali durante la definizione della classe di solito influenzano diverse variabili, che dovrebbero essere considerate in base al problema sottostante. Pertanto, la seguente implementazione è pensata solo per essere semplice per spiegare il concetto di elenchi concatenati circolari.

Una volta che l’oggetto CircularList è stato inizializzato utilizzando il costruttore, possiamo aggiungere nuovi elementi utilizzando la funzione membro insertNodeEnd. Quest’ultimo accetta il parametro stringa e costruisce un nuovo elemento alla fine della lista. La funzione insertNodeEnd alloca nuovi elementi con l’operatore new e modifica di conseguenza i puntatori per inserire il nodo subito dopo la fine della lista. Aggiorna anche il membro dei dati end in modo che punti a un nuovo nodo allocato.

Un’altra funzione membro definita nel prossimo esempio è printNodes, che scorre la lista per stamparne il contenuto e non accetta alcun argomento. Ora, per dimostrare meglio l’utilizzo di questa struttura, abbiamo bisogno del codice del driver nella funzione main. Abbiamo scelto di inizializzare un vettore di stringhe arbitrarie da inserire successivamente nell’oggetto CircularList utilizzando il cicli for. Infine, invochiamo una funzione printNodes per visualizzare il contenuto della lista al terminale.

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

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

struct ListNode {
  struct ListNode *next = nullptr;
  string data;
} typedef ListNode;

class CircularList {
 public:
  explicit CircularList(string data) {
    head = new ListNode;
    head->next = head;
    head->data = std::move(data);
    end = head;
  };

  ListNode *insertNodeEnd(string data);
  void printNodes();

 private:
  ListNode *head = nullptr;
  ListNode *end = nullptr;
};

ListNode *CircularList::insertNodeEnd(string data) {
  auto new_node = new ListNode;
  new_node->next = end->next;
  new_node->data = std::move(data);

  end->next = new_node;
  end = end->next;
  return new_node;
}

void CircularList::printNodes() {
  auto count = 0;
  auto tmp = head;
  while (tmp != end) {
    cout << "node " << count << " - data: " << tmp->data << endl;
    tmp = tmp->next;
    count++;
  }
  cout << "node " << count << " - data: " << tmp->data << endl;
}

int main() {
  vector<string> data_set = {"Precise", "Quantal", "Saucy", "Raring"};

  CircularList clist("Xenial");

  for (const auto &item : data_set) {
    clist.insertNodeEnd(item);
  }

  clist.printNodes();

  return EXIT_SUCCESS;
}

Produzione:

node 0 - data : Xenial node 1 - data : Precise node 2 - data : Quantal node 3 -
                                                               data
    : Saucy node 4 -
      data : Raring

Implementa il distruttore e la funzione membro per inserire nuovi elementi all’inizio della lista in C++

Nota che il frammento di codice precedente ha un grosso problema nel non avere un distruttore definito; ciò implica che il programma che utilizza la classe CircularList perderà memoria poiché i nodi creati sulla memoria dinamica non vengono liberati fino all’uscita del programma.

La soluzione a questo problema è implementare un distruttore che attraversi l’intera lista e dealloca tutti i nodi usando l’operatore delete. Pertanto, non dobbiamo preoccuparci di liberare manualmente la memoria della lista. Verrà automaticamente liberato una volta che l’oggetto CircularList raggiungerà la fine dell’ambito.

Un’altra funzione utile da implementare è quella che inserisce un nuovo elemento in testa alla lista; il comando insertNodeHead è progettato proprio per fare questo. Richiede solo un argomento string da memorizzare e restituisce il puntatore al nodo appena allocato. Si noti che il valore restituito per le funzioni insertNodeEnd e insertNodeHead è un’altra scelta di progettazione, che viene implementata in modo diverso a seconda delle decisioni del programmatore. Il seguente frammento di codice include il codice del driver simile nella funzione main per testare e mostrare l’utilizzo della classe CircularList.

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

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

struct ListNode {
  struct ListNode *next = nullptr;
  string data;
} typedef ListNode;

class CircularList {
 public:
  explicit CircularList(string data) {
    head = new ListNode;
    head->next = head;
    head->data = std::move(data);
    end = head;
  };

  ListNode *insertNodeEnd(string data);
  ListNode *insertNodeHead(string data);
  void printNodes();

  ~CircularList();

 private:
  ListNode *head = nullptr;
  ListNode *end = nullptr;
};

ListNode *CircularList::insertNodeEnd(string data) {
  auto new_node = new ListNode;
  new_node->next = end->next;
  new_node->data = std::move(data);

  end->next = new_node;
  end = end->next;
  return new_node;
}

ListNode *CircularList::insertNodeHead(string data) {
  auto new_node = new ListNode;
  new_node->next = end->next;
  new_node->data = std::move(data);

  end->next = new_node;
  head = end->next;
  return new_node;
}

CircularList::~CircularList() {
  while (head != end) {
    auto tmp = head;
    head = head->next;
    delete tmp;
  }
  delete head;
}

void CircularList::printNodes() {
  auto count = 0;
  auto tmp = head;
  while (tmp != end) {
    cout << "node " << count << " - data: " << tmp->data << endl;
    tmp = tmp->next;
    count++;
  }
  cout << "node " << count << " - data: " << tmp->data << endl;
}

int main() {
  vector<string> data_set = {"Precise", "Quantal", "Saucy", "Raring"};

  CircularList clist("Xenial");

  for (const auto &item : data_set) {
    clist.insertNodeEnd(item);
  }

  clist.printNodes();
  cout << " ----------------------------------- " << endl;

  clist.insertNodeHead("Bionic");
  clist.insertNodeEnd("Zeisty");
  clist.printNodes();

  return EXIT_SUCCESS;
}

Produzione:

node 0 - data : Xenial node 1 - data : Precise node 2 - data : Quantal node 3 -
                                                               data
    : Saucy node 4 -
      data
    : Raring-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -node 0 -
      data : Bionic node 1 - data : Xenial node 2 - data : Precise node 3 -
                                                           data
    : Quantal node 4 -
      data : Saucy node 5 - data : Raring node 6 - data : Zeisty