Implementieren einer zirkulär verketteten Listendatenstruktur in C++

1. Implementieren Sie eine kreisförmige einfach verkettete Liste mit Elementfunktionen, um neue Elemente am Ende hinzuzufügen und Elemente in C++ zu drucken
2. Implementierung des Destruktors und der Member-Funktion zum Einfügen neuer Elemente am Anfang der Liste in C++

In diesem Artikel wird erläutert, wie Sie eine zirkuläre verknüpfte Listendatenstruktur in C++ implementieren.

Implementieren Sie eine kreisförmige einfach verkettete Liste mit Elementfunktionen, um neue Elemente am Ende hinzuzufügen und Elemente in C++ zu drucken

Eine zirkuläre verkettete Liste kann als verkettete Liste charakterisiert werden, bei der der letzte Knoten auf den Kopf der Liste zeigt. Im Wesentlichen bilden die Knoten in der Liste einen Kreis, und es gibt kein nullptr, um das Ende der Liste abzugrenzen. Sie können zirkulär verkettete Listen verwenden, um Datenstrukturen im Warteschlangenstil zu erstellen. Das Rundheitsmerkmal kann sowohl zu der doppelt verknüpften Liste als auch zu einer einfach verknüpften Liste hinzugefügt werden.

In diesem Fall werden wir letzteres implementieren. Denken Sie daran, dass wir eine Knotenstruktur definieren müssen, die einen Zeiger auf den nächsten Knoten und ein Datenelement enthält, um eine einfach verkettete Liste zu erstellen. Das Objekt struct ListNode stellt einen einzelnen Knoten für unsere Implementierung dar und speichert ein einzelnes string-Objekt namens data, das in diesem Beispiel als Elementdaten dient. Beachten Sie, dass Sie jedes benutzerdefinierte Objekt in einem Knoten speichern können, und wenn das Objekt relativ größer ist, ist es besser, es als Zeiger einzuschließen.

Sobald wir eine Struktur eines einzelnen Knotens haben, können wir eine CircularList-Klasse definieren, die für den Anfang nur zwei Member-Funktionen hat. Im Allgemeinen sollte eine zirkulär verkettete Liste den Kopf der Liste oder ihr Ende verfolgen; es steht dem Implementierer jedoch normalerweise frei, die Klassenentwurfsentscheidung basierend auf seinen Bedürfnissen zu treffen. Zusätzlich speichert die Klasse CircularList zwei separate Zeiger, um den Kopf und das Ende der Liste darzustellen.

Der Zeiger, der den Kopf/das Ende der Liste speichert, kann ein Dummy-Knoten oder ein tatsächlicher Knoten mit den Daten sein. In diesem Beispiel haben wir uns entschieden, die Klasse CircularList so zu gestalten, dass sie keine Dummy-Zeiger hat. Wir haben einen Konstruktor definiert, der einen string-Parameter akzeptiert, um den ersten Knoten in der Ringliste zu initialisieren. Beachten Sie, dass Designentscheidungen während der Klassendefinition normalerweise verschiedene Variablen beeinflussen, die basierend auf dem zugrunde liegenden Problem berücksichtigt werden sollten. Daher soll die folgende Implementierung nur eine einfache sein, um das Konzept der zirkulären verketteten Listen zu erklären.

Nachdem das CircularList-Objekt mit dem Konstruktor initialisiert wurde, können wir mit der Member-Funktion insertNodeEnd neue Elemente hinzufügen. Letztere akzeptiert den Parameter string und baut ein neues Element am Ende der Liste auf. Die Funktion insertNodeEnd weist neue Elemente mit dem Operator new zu und modifiziert die Zeiger entsprechend, um den Knoten direkt nach dem Ende der Liste einzufügen. Es aktualisiert auch das Datenelement Ende, um auf einen neu zugewiesenen Knoten zu verweisen.

Eine weitere im nächsten Beispiel definierte Memberfunktion ist die printNodes, die die Liste durchläuft, um ihren Inhalt zu drucken, und keine Argumente akzeptiert. Um die Verwendung dieser Struktur besser zu demonstrieren, benötigen wir nun Treibercode in der Funktion main. Wir haben uns entschieden, einen Vektor aus beliebigen Strings zu initialisieren, um ihn später mit der for-Schleife in das CircularList-Objekt einzufügen. Schließlich rufen wir eine printNodes-Funktion auf, um den Listeninhalt auf dem Terminal anzuzeigen.

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

Ausgabe:

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

Implementierung des Destruktors und der Member-Funktion zum Einfügen neuer Elemente am Anfang der Liste in C++

Beachten Sie, dass im vorherigen Codeausschnitt ein großes Problem besteht, dass kein Destruktor definiert ist. dies impliziert, dass das Programm, das die Klasse CircularList verwendet, Speicher verliert, da die auf dem dynamischen Speicher erstellten Knoten erst beim Beenden des Programms freigegeben werden.

Die Lösung für dieses Problem besteht darin, einen Destruktor zu implementieren, der die gesamte Liste durchläuft und alle Knoten mit dem Operator delete freigibt. Daher müssen wir uns nicht darum kümmern, den Listenspeicher manuell freizugeben. Es wird automatisch freigegeben, sobald das Objekt CircularList das Ende des Gültigkeitsbereichs erreicht.

Eine weitere nützliche zu implementierende Funktion ist diejenige, die ein neues Element am Anfang der Liste einfügt; der Befehl insertNodeHead ist dafür gedacht. Es braucht nur ein zu speicherndes string-Argument und gibt den Zeiger auf den neu zugewiesenen Knoten zurück. Beachten Sie, dass der Rückgabewert für die Funktionen insertNodeEnd und insertNodeHead eine weitere Designentscheidung ist, die je nach Entscheidung des Programmierers unterschiedlich implementiert wird. Der folgende Codeausschnitt enthält den ähnlichen Treibercode in der Funktion main, um die Verwendung der Klasse CircularList zu testen und zu demonstrieren.

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

Ausgabe:

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