Inversez chaque mot dans le nœud de liste chaînée

Une liste chaînée est une structure de données linéaire similaire à une chaîne, dans laquelle les éléments ne sont pas stockés en mémoire de manière adjacente comme un tableau. Dans une liste chaînée spécifique, un élément est connecté à l'élément suivant via un pointeur. En termes simples, une liste chaînée est une série de conteneurs de données dans lesquels nous pouvons trouver un chemin ou un lien de référence vers le nœud suivant. Dans une liste chaînée, il y a un pointeur de tête comme premier élément. Si le premier nœud de cette liste chaînée particulière est vide, alors il ne pointe vers rien ou est vide.

Il existe différents types de listes chaînées dans les structures de données.

• Liste chaînée unique - Il s'agit d'un type de base de liste chaînée présente dans la structure de données, où chaque nœud contient des données avec un pointeur du même type de données pour le nœud suivant. Ici pour cette liste chaînée à la fois la complexité temporelle et. l'espace auxiliaire est O(n).

• Liste double chaînée - Il s'agit d'une liste complexe doublement chaînée qui contient un pointeur comme une séquence de nœuds précédents. Ce type de liste chaînée contient trois parties distinctes : la source de données, le pointeur et le nœud suivant. Avec cette liste chaînée, nous pouvons parcourir la liste entière dans l'ordre inverse.

• Liste chaînée circulaire - Dans une liste chaînée circulaire, le premier pointeur de nœud indiqué par le dernier nœud de la liste. Cela signifie que la liste n'a ni début ni point de fin. Pour parcourir une liste chaînée circulaire, l'utilisateur peut commencer. à partir de n'importe quel nœud et parcourez la liste vers l'avant ou vers l'arrière selon leur souhait.

• Liste chaînée circulaire bidirectionnelle - Il s'agit d'une liste chaînée circulaire bidirectionnelle, qui contient des pointeurs vers le nœud précédent et le nœud suivant. Le nœud précédent de son premier nœud ne contient pas de valeur nulle.

Dans cet article, nous allons créer du code pour la liste chaînée mentionnée ci-dessus, grâce à ces codes, nous apprendrons comment inverser chaque mot dans le nœud de liste chaînée dans un environnement C++.

Algorithme pour inverser chaque mot présent dans un nœud de liste chaînée

• Étape 1 - Déclarez un tableau temporaire.

• Étape 2 - Parcourez une liste chaînée.

• Étape 3 - Si l'élément actuel est un alphabet, stockez l'élément.

• Étape 4 - Sinon, augmentez le nœud de 1 pointeur.

• Étape 5 - Traversez à nouveau depuis la tête.

• Étape 6 - Si l'élément actuel est l'alphabet, copiez-le dans le dernier élément.

• Étape 7 - Réduisez l'indice actuel.

• Étape 8 - L'itération est indispensable.

• Étape 9 - Sinon, augmentez-le de un.

Syntaxe pour inverser chaque mot dans un nœud de liste chaînée

insertEnd(head, new_node)
Declare last
   if head == NULL then
      new_node->next = new_node->prev = new_node
      head = new_node
      return
   last = head->prev
   new_node->next = head
   head->prev = new_node
   new_node->prev = last
   last->next = new_node
reverse(head)
   Initialize new_head = NULL
   Declare last
   last = head->prev
   Initialize curr = last, prev
   while curr->prev != last
      prev = curr->prev
      insertEnd(&new_head, curr)
      curr = prev
   insertEnd(&new_head, curr)
return new_head

Comment suivre :

• Approche 1 − Inversez chaque mot présent dans une liste chaînée

• Approche 2 − Inversez la phrase entière présente dans une liste chaînée.

• Approche 3 − Inversez une liste chaînée doublement circulaire.

• Approche 4 − Inverser une liste chaînée circulaire.

• Chemin 5 - Inversez la liste chaînée sans affecter les caractères spéciaux.

Inversez chaque mot présent dans une liste chaînée en utilisant C++

Ici, dans ce code de construction C++ particulier, nous avons inversé chaque mot présent dans une liste chaînée.

La traduction chinoise de

Exemple 1

est :

Exemple 1

#include <bits/stdc++.h>
using namespace std;
struct Node {
   string c;
   struct Node* next;
};
struct Node* newNode(string c){
   Node* temp = new Node;
   temp->c = c;
   temp->next = NULL;
   return temp;
};
void reverse_word(string& str){
   reverse(str.begin(), str.end());
}
void reverse(struct Node* head){
   struct Node* ptr = head;
   while (ptr != NULL) {
      reverse_word(ptr->c);
      ptr = ptr->next;
   }
}
void printList(struct Node* head){
   while (head != NULL) {
      cout << head->c << " ";
      head = head->next;
   }
}
int main(){
   Node* head = newNode("Train number 13109");
   head->next = newNode("Maitree Express");
   head->next->next = newNode("is an international train");
   head->next->next->next = newNode("runs between");
   head->next->next->next->next = newNode("Kolkata");
   head->next->next->next->next->next = newNode("and");
   head->next->next->next->next->next->next = newNode("Dhaka");
   cout << "The list here present before reverse: \n";
   printList(head);
   reverse(head);
   cout << "\n\nList after reverse we can see like: \n";
   printList(head);
   return 0;
}

Sortie

The list here present before reverse: 
Train number 13109 Maitree Express is an international train runs between Kolkata and Dhaka 

List after reverse we can see like: 
90131 rebmun niarT sserpxE eertiaM niart lanoitanretni na si neewteb snur atakloK dna akahD 

Inversez la phrase entière dans la liste chaînée

Dans ce code particulier, nous avons inversé la phrase entière dans la liste chaînée.

#include <bits/stdc++.h>
using namespace std;
string reverseString(string str){
   reverse(str.begin(), str.end());
   str.insert(str.end(), ' ');
   int n = str.length();
   int j = 0;
      for (int i = 0; i < n; i++) {
      if (str[i] == ' ') {
         reverse(str.begin() + j,
         str.begin() + i);
         j = i + 1;
      }
   }
   str.pop_back();
   return str;
}
int main(){
   string str = "13110, Maitree Express Is An International Train Runs Between Dhaka And Kolkata";
   string rev = reverseString(str);
   cout << rev;
   return 0;
}

Sortie

Kolkata And Dhaka Between Runs Train International An Is Express Maitree 13110,

Inverser une liste chaînée doublement circulaire

Ici, dans ce code particulier, nous avons inversé une liste chaînée doublement circulaire.

La traduction chinoise de

Exemple 3

est :

Exemple 3

#include <bits/stdc++.h><bits stdc++.h="">
using namespace std;
struct Node {
   int data;
   Node *next, *prev;
};
Node* getNode(int data){
   Node* newNode = (Node*)malloc(sizeof(Node));
   newNode->data = data;
   return newNode;
}
void insertEnd(Node** head, Node* new_node) {
   if (*head == NULL) {
      new_node->next = new_node->prev = new_node;
      *head = new_node;
      return;
   }
   Node* last = (*head)->prev;
   new_node->next = *head;
   (*head)->prev = new_node;
   new_node->prev = last;
   last->next = new_node;
}
Node* reverse(Node* head) {
   if (!head)
   return NULL;
   Node* new_head = NULL;
   Node* last = head->prev;
   Node *curr = last, *prev;
   while (curr->prev != last) {
      prev = curr->prev;
      insertEnd(&new_head, curr);
      curr = prev;
   }
   insertEnd(&new_head, curr);
   return new_head;
}
void display(Node* head){
   if (!head)
   return;
   Node* temp = head;
   cout << "Forward direction data source: ";
   while (temp->next != head) {
      cout << temp->data << " ";
      temp = temp->next;
   }
   cout << temp->data;
   Node* last = head->prev;
   temp = last;
   cout << "\nBackward direction data source: ";
   while (temp->prev != last) {
      cout << temp->data << " ";
      temp = temp->prev;
   }
   cout << temp->data;
}
int main(){
   Node* head = NULL;
   insertEnd(&head, getNode(16));
   insertEnd(&head, getNode(10));
   insertEnd(&head, getNode(07));
   insertEnd(&head, getNode(2001));
   insertEnd(&head, getNode(1997));
   cout << "Current list here present:\n";
   display(head);
   head = reverse(head);
   cout << "\n\nReversed list here present:\n";
   display(head);
   return 0;
}
</bits>

Sortie

Current list here present:
Forward direction data source: 16 10 7 2001 1997
Backward direction data source: 1997 2001 7 10 16

Reversed list here present:
Forward direction data source: 1997 2001 7 10 16
Backward direction data source: 16 10 7 2001 1997

Liste chaînée circulaire inversée

Dans ce code particulier, nous avons inversé un ensemble de données de liste chaînée circulaire.

La traduction chinoise de

Exemple 4

est :

Exemple 4

#include <bits/stdc++.h><bits stdc++.h="">
using namespace std;
struct Node {
   int data;
   Node* next;
};
Node* getNode(int data){
   Node* newNode = new Node;
   newNode->data = data;
   newNode->next = NULL;
   return newNode;
}
void reverse(Node** head_ref){
   if (*head_ref == NULL)
   return;
   Node* prev = NULL;
   Node* current = *head_ref;
   Node* next;
   do {
      next = current->next;
      current->next = prev;
      prev = current;
      current = next;
   } while (current != (*head_ref));
   (*head_ref)->next = prev;
   *head_ref = prev;
}
void printList(Node* head){
   if (head == NULL)
   return;
   Node* temp = head;
   do {
      cout << temp->data << " ";
      temp = temp->next;
   } while (temp != head);
}
int main(){
   Node* head = getNode(10);
   head->next = getNode(16);
   head->next->next = getNode(07);
   head->next->next->next = getNode(2022);
   head->next->next->next->next = head;
   cout << "Given circular linked list is here: ";
   printList(head);
   reverse(&head);
   cout << "\nReversed circular linked list after method: ";
   printList(head);
   return 0;
}
</bits>

Sortie

Given circular linked list is here: 10 16 7 2022 
Reversed circular linked list after method: 2022 7 16 10 

Inversez une liste chaînée sans affecter les caractères spéciaux

Ici, dans ce code particulier, nous avons inversé l'ensemble de données de la liste chaînée sans affecter les caractères spéciaux.

Exemple 5

#include <iostream>
using namespace std;
struct Node {
   char data;
   struct Node* next;
};
void reverse(struct Node** head_ref, int size){
   struct Node* current = *head_ref;
   char TEMP_ARR[size];
   int i = 0;
   while (current != NULL) {
      if ((current->data >= 97 && current->data <= 122) ||
      (current->data >= 65 && current->data <= 90)) {
         TEMP_ARR[i++] = current->data;
         current = current->next;
      }
      else
      current = current->next;
   }
   current = *head_ref;
   while (current != NULL) {
      if ((current->data >= 97 && current->data <= 122) ||
      (current->data >= 65 && current->data <= 90)) {
         current->data = TEMP_ARR[--i];
         current = current->next;
      }
      else
      current = current->next;
   }
}
void push(struct Node** head_ref, char new_data){
   struct Node* new_node = new Node();
   new_node->data = new_data;
   new_node->next = (*head_ref);
   (*head_ref) = new_node;
}
void printList(struct Node* head){
   struct Node* temp = head;
   while (temp != NULL) {
      cout << temp->data;
      temp = temp->next;
   }
}
// Driver program to test above function
int main() {
   struct Node* head = NULL;
   push(&head, 'R');
   push(&head, 'U');
   push(&head, 'D');
   push(&head, 'R');
   push(&head, 'A');
   push(&head, 'K');
   push(&head, 'O');
   push(&head, 'L');
   push(&head, 'K');
   push(&head, 'A');
   push(&head, 'T');
   push(&head, 'A');
   push(&head, '0');
   push(&head, '1');
   push(&head, '0');
   push(&head, '@');
   cout << "Given linked list is here: ";
   printList(head);
   reverse(&head, 13);
   cout << "\nReversed Linked list is here: ";
   printList(head);
   return 0;
}

Sortie

Given linked list is here: B@010ATAKLOKARDUR
Reversed Linked list is here: R@010UDRAKOLKATAB

Conclusion

Dans cet article, nous avons appris comment inverser chaque mot dans un nœud de liste chaînée. Nous avons construit le code C++ ici pour montrer le processus d'inversion possible afin que vous puissiez avoir une compréhension globale de l'inversion des nœuds de liste chaînée.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!