Verknüpfte Liste in C++ sortieren

1. Liste in C++
2. Implementieren Sie eine verkettete Liste in C++
3. Sortieren Sie eine verkettete Liste in C++

Dieses einfache Programmier-Tutorial demonstriert die Implementierung der Sortieroperation in einer Linked-List-Datenstruktur in C++.

Liste in C++

Liste oder verkettete Liste ist eine lineare Datenstruktur, die als Datencontainer dienen und die Daten im Speicher speichern kann. Im Gegensatz zu Vektoren oder Arrays benötigen Daten in der Liste keine aufeinanderfolgenden Speicherstellen; stattdessen können die Daten dynamisch wachsen und beliebigen Heap-Speicherorten zugewiesen werden.

Jedes Element in der Liste wird als Knoten bezeichnet. Jeder Knoten in einer Liste enthält einen Zeiger, der auf den allernächsten Knoten der Liste zeigt.

Das Einschließen des Zeigers auf das nächste Element in jedem Knoten kann eine lineare Verkettung erleichtern, bei der auf jedes nächste Element über den vorherigen Knoten zugegriffen werden kann. Diese lineare Verkettung zwischen den Knoten ist der Hauptgrund dafür, dieser Struktur den Namen Verkettete Liste zu geben.

An der verknüpften Liste können mehrere ADT-Operationen (Abstract Data Type) ausgeführt werden, z. B. Einfügen, Löschen, Suchen und sogar Sortieren. Wir beginnen mit der grundlegenden strukturellen Implementierung der verknüpften Liste und implementieren dann den Sortieralgorithmus in dieser Klasse.

Implementieren Sie eine verkettete Liste in C++

Jetzt beginnen wir mit der Implementierung der Linked List. Dafür müssen wir zuerst eine Klasse für Node wie folgt erstellen:

template <class T>
class Node {
 public:
  T data;
  Node<T>* next;
  Node() { next = 0; }
};

In dieser Klasse gibt es zwei Mitglieder, eines zum Speichern von Daten, d. h. info, und das andere ist der Zeiger der Klasse zum Speichern der Adresse des nächsten Knotens. Die Klasse wird mit Vorlagen erstellt, sodass eine Liste mit beliebigen Datentypen erstellt werden kann.

Jetzt erstellen wir eine Linked-List-Klasse wie diese:

template <class T>
class LSLL {
 private:
  Node<T>* head;

 public:
  LSLL() { head = 0; }
  void insertAtHead(T val) {
    Node<T>* x = new Node<T>(val);
    x->next = head;
    head = x;
  }
  void displayAll() {
    Node<T>* x = head;
    {
      while (x != 0) {
        cout << x->info << endl;
        x = x->next;
      }
    }
  }
};

In dieser Klasse gibt es einen Konstruktor und zwei weitere Elementfunktionen zum Einfügen und Anzeigen der Listenknoten.

Sortieren Sie eine verkettete Liste in C++

Wir werden den einfachsten Sortieralgorithmus, Bubble Sort, implementieren, um die verknüpfte Liste in aufsteigender Reihenfolge zu sortieren. Dieser Sortieralgorithmus tauscht benachbarte Elemente wiederholt aus, wenn sie in einer unsortierten Reihenfolge platziert werden.

Diese Operation wird wiederholt durchgeführt, bis alle Elemente an ihrer richtigen sortierten Position sind. Dies wird wie folgt umgesetzt:

void sortLinkedList() {
  Node<T> *curr = head, *temp = NULL;
  int t;
  if (head == NULL) {
    return;
  } else {
    while (curr != NULL) {
      temp = curr->next;
      while (temp != NULL) {
        if (curr->info > temp->info) {
          t = curr->info;
          curr->info = temp->info;
          temp->info = t;
        }
        temp = temp->next;
      }
      curr = curr->next;
    }
  }
}

Das Treiberprogramm wird sein:

int main() {
  LSLL<int> list;
  list.insertAtHead(50);
  list.insertAtHead(45);
  list.insertAtHead(16);
  cout << "Before sorting" << endl;
  list.displayAll();
  cout << "After Sorting: " << endl;
  list.sortLinkedList();
  list.displayAll();
  return 0;
}

Ausgabe:

Before sorting
43
65
13
After Sorting:
13
43
65