Balikkan setiap perkataan dalam nod senarai terpaut

王林
Lepaskan: 2023-09-01 10:25:03
ke hadapan
920 orang telah melayarinya

Balikkan setiap perkataan dalam nod senarai terpaut

Senarai terpaut ialah struktur data linear yang serupa dengan rantai, di mana elemen tidak disimpan dalam ingatan dalam cara bersebelahan seperti tatasusunan. Dalam senarai terpaut tertentu, elemen disambungkan ke elemen seterusnya melalui penuding. Ringkasnya, senarai terpaut ialah satu siri bekas data di mana kita boleh mencari laluan atau pautan rujukan ke nod seterusnya. Dalam senarai terpaut, terdapat penunjuk kepala sebagai elemen pertama. Jika nod pertama senarai terpaut tertentu itu kosong, maka ia menunjuk kepada tiada atau kosong.

Terdapat pelbagai jenis senarai terpaut dalam struktur data.

  • Senarai Terpaut Tunggal − Ia ialah jenis asas senarai terpaut yang terdapat dalam struktur data, di mana setiap nod mengandungi beberapa data dengan penunjuk jenis data yang sama untuk seterusnya nod. Di sini untuk senarai terpaut ini kerumitan masa dan ruang tambahan ialah O(n).

  • Senarai terpaut berganda − Ia ialah senarai pautan berganda kompleks yang mengandungi penunjuk sebagai urutan nod sebelumnya. Senarai terpaut jenis ini mengandungi tiga bahagian berbeza: sumber data, penunjuk dan nod seterusnya. Dengan senarai terpaut ini, kita boleh melintasi keseluruhan senarai dalam susunan terbalik.

  • Senarai Berpaut Pekeliling − Dalam senarai terpaut bulat penunjuk nod pertama yang ditunjukkan oleh nod terakhir senarai Ini bermakna, senarai itu tiada permulaan dan tiada titik penamat . Untuk melintasi senarai pautan bulat, pengguna boleh bermula dari mana-mana nod dan melintasi senarai ke arah hadapan atau belakang mengikut kehendak mereka.

  • Senarai terpaut pekeliling dua hala - Ini ialah senarai terpaut pekeliling dua hala, yang mengandungi penunjuk ke nod sebelumnya dan nod seterusnya. Nod sebelumnya nod pertamanya tidak mengandungi nilai nol.

Dalam artikel ini, kami akan membina beberapa kod untuk senarai terpaut yang disebutkan di atas, melalui kod ini kami akan belajar cara untuk membalikkan setiap perkataan dalam nod senarai terpaut dalam persekitaran C++.

Algoritma untuk menterbalikkan setiap perkataan yang terdapat dalam nod senarai terpaut

  • Langkah pertama - isytiharkan tatasusunan sementara.

  • Langkah 2 − Melintasi senarai terpaut.

  • Langkah 3 − Jika elemen semasa ialah abjad maka simpan elemen tersebut.

  • Langkah 4 − Jika tidak, tingkatkan nod sebanyak 1 penuding.

  • Langkah 5 - Lintas dari kepala semula.

  • Langkah 6 − Jika elemen semasa ialah abjad maka salin ke elemen terakhir.

  • Langkah 7 - Kurangkan indeks semasa.

  • Langkah 8 - Lelaran adalah satu kemestian.

  • Langkah 9 - Jika tidak, tambah satu.

Sintaks menterbalikkan setiap perkataan dalam nod senarai terpaut

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
Salin selepas log masuk

Cara mengikuti:

  • Pendekatan 1 − Balikkan setiap perkataan yang terdapat dalam senarai terpaut

  • Pendekatan 2 − Balikkan seluruh ayat yang terdapat dalam senarai terpaut.

  • Pendekatan 3 − Balikkan senarai berpaut dua kali ganda.

  • Pendekatan 4 − Balikkan senarai pautan bulat.

  • Path 5 − Balikkan senarai terpaut tanpa menjejaskan aksara khas.

Terbalikkan setiap perkataan yang terdapat dalam senarai terpaut dengan menggunakan C++

Di sini dalam kod binaan C++ tertentu ini kami telah membalikkan setiap perkataan yang terdapat dalam senarai terpaut.

Terjemahan bahasa Cina bagi

Contoh 1

ialah:

Contoh 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;
}
Salin selepas log masuk

Output

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 
Salin selepas log masuk

Terbalikkan keseluruhan ayat dalam senarai terpaut

Dalam kod khusus ini, kami telah membalikkan keseluruhan ayat dalam senarai terpaut.

#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;
}
Salin selepas log masuk

Output

Kolkata And Dhaka Between Runs Train International An Is Express Maitree 13110,
Salin selepas log masuk

Terbalikkan senarai terpaut dua kali ganda

Di sini dalam kod khusus ini kami telah membalikkan senarai pautan dua kali ganda.

Terjemahan bahasa Cina bagi

Contoh 3

ialah:

Contoh 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>
Salin selepas log masuk

Output

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
Salin selepas log masuk

Senarai Terpaut Pekeliling Terbalik

Dalam kod khusus ini, kami telah membalikkan set data senarai pautan bulat.

Terjemahan bahasa Cina bagi

Contoh 4

ialah:

Contoh 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>
Salin selepas log masuk

Output

Given circular linked list is here: 10 16 7 2022 
Reversed circular linked list after method: 2022 7 16 10 
Salin selepas log masuk

Terbalikkan senarai terpaut tanpa menjejaskan aksara khas

Di sini dalam kod khusus ini kami telah membalikkan set data senarai terpaut tanpa menjejaskan aksara khas.

Contoh 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;
}
Salin selepas log masuk

Output

Given linked list is here: B@010ATAKLOKARDUR
Reversed Linked list is here: R@010UDRAKOLKATAB
Salin selepas log masuk

Kesimpulan

Dalam artikel ini, kami belajar cara membalikkan setiap perkataan dalam nod senarai terpaut. Kami telah membina kod C++ di sini untuk menunjukkan kemungkinan proses pembalikan supaya anda boleh mendapatkan pemahaman yang luas tentang pembalikan nod senarai terpaut.

Atas ialah kandungan terperinci Balikkan setiap perkataan dalam nod senarai terpaut. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

sumber:tutorialspoint.com
Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn
Tutorial Popular
Lagi>
Muat turun terkini
Lagi>
kesan web
Kod sumber laman web
Bahan laman web
Templat hujung hadapan