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++.
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.
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
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.
Di sini dalam kod binaan C++ tertentu ini kami telah membalikkan setiap perkataan yang terdapat dalam senarai terpaut.
Terjemahan bahasa Cina bagi#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; }
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
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; }
Kolkata And Dhaka Between Runs Train International An Is Express Maitree 13110,
Di sini dalam kod khusus ini kami telah membalikkan senarai pautan dua kali ganda.
Terjemahan bahasa Cina bagi#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>
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
Dalam kod khusus ini, kami telah membalikkan set data senarai pautan bulat.
Terjemahan bahasa Cina bagi#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>
Given circular linked list is here: 10 16 7 2022 Reversed circular linked list after method: 2022 7 16 10
Di sini dalam kod khusus ini kami telah membalikkan set data senarai terpaut tanpa menjejaskan aksara khas.
#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; }
Given linked list is here: B@010ATAKLOKARDUR Reversed Linked list is here: R@010UDRAKOLKATAB
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!