Umkehren der verknüpften Liste in C++

In diesem Artikel wird veranschaulicht, wie Sie eine verknüpfte Listendatenstruktur in C++ umkehren.

Verwenden Sie die iterative Funktion, um die verknüpfte Liste in C++ umzukehren

Wir gehen davon aus, dass das Zielobjekt eine einfach verkettete Liste ist und implementieren Codeschnipsel entsprechend. Zuerst müssen wir uns die grundlegenden Funktionsdienstprogramme im implementierten Treibercode ansehen, um das Beispiel zu demonstrieren.

Der Linked-List-Knoten ist ein einfaches struct mit einem einzelnen string-Datenobjekt und einem Zeiger auf den nächsten Knoten. Wir haben auch die Funktion addNewNode, die zwei Argumente akzeptiert, Node* und eine Referenz auf den string. Die Funktion addNewNode wird in der Routine main mehrmals aufgerufen, um ein neues Listenobjekt zu konstruieren und Strings aus dem Vektor data_set zu speichern. Die Funktion ordnet jeden Knoten im dynamischen Speicher zu und gibt den Zeiger auf den neu erstellten Knoten zurück.

Eine weitere nützliche Funktion für unsere Linked-List-Datenstruktur ist printNodes, mit der Daten von jedem Knoten an den cout-Stream ausgegeben werden. Letzteres wird uns helfen, die Korrektheit der Umkehrfunktion grob zu überprüfen. Beachten Sie, dass printNodes die Anzahl der Knoten während des Durchlaufs der Liste speichert und den Index für jedes Element ausgibt. Schließlich müssen wir alle Knoten freigeben, bevor das Programm beendet wird. Dieser Schritt ist für die Demonstration der Umkehrfunktion nicht erforderlich, aber für jedes reale Projekt ist es wichtig, den gesamten während der Laufzeit zugewiesenen Speicher zu bereinigen.

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

Ausgabe:

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

Sobald wir eine neue verknüpfte Liste initialisieren und den Kopf der Liste in einem separaten Zeiger speichern, können wir damit den Inhalt umkehren. In diesem Fall haben wir die Funktion reverseList implementiert, die ein einzelnes Node*-Argument akzeptiert und einen neuen Wurzelknoten zurückgibt. Zuerst duplizieren wir den übergebenen Zeiger und speichern ihn als head-Variable. Wir brauchen auch zwei zusätzliche Zeiger vom Typ Node, um die interne Buchhaltung während der while-Schleife zu erledigen.

Der Umkehralgorithmus kann wie folgt beschrieben werden: Wir speichern den nächsten Knotenzeiger in einer temporären Variablen (next) und weisen dem ursprünglichen den Wert nullptr zu. Als Ergebnis zeigt der ursprüngliche head-Knoten auf den nullptr als nächsten Knoten in der Liste. Als nächstes aktualisieren wir die Variable head, um den nächsten (zweiten) Knoten in der Originalliste zu speichern und speichern auch die Adresse des ursprünglichen Kopfknotens in einer separaten temporären Variablen.

Wir wiederholen die vorherigen Schritte, bis der Zeiger head zu nullptr ausgewertet wird, was bedeuten würde, dass das Ende der Liste erreicht ist. Am Ende geben wir die Adresse des neuen Kopfknotens zurück, die in der temporären Variablen n gespeichert ist. Folglich ruft das Programm main die Funktion printNodes für den Benutzer auf, um geänderte verlinkte Listeninhalte zu vergleichen.

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

Ausgabe:

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