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++
- Implementa il distruttore e la funzione membro per inserire nuovi elementi all’inizio della lista in C++
![Implementare una struttura dati di elenchi collegati circolari in C++](/img/Cpp/feature-image---circular-linked-list-in-cpp.webp)
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
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