將鍊錶節點中的每個單字反轉
- 王林轉載
- 2023-09-01 10:25:03889瀏覽
鍊錶是一種類似鍊式的線性資料結構，其中元素不像陣列那樣以相鄰的方式保存在記憶體中。在特定的鍊錶中，元素透過指標與下一個元素相連。簡單來說，鍊錶是一系列資料容器，我們可以在這些元素中找到一條路徑或引用連結到下一個節點。在鍊錶中，有一個頭指標作為第一個元素。如果該特定鍊錶的第一個節點為空，則它不指向任何內容或為空。
在資料結構中存在不同類型的鍊錶。
Singly Linked list − It is a basic type of linked list present in data structure, where every node contains some data with a pointer of the same data type for the next node. Here for this linked list both the time complexity and auxiliary space is O(n).
雙向鍊錶 − 它是一個複雜的雙向鍊錶，其中包含一個指標作為前一個節點的序列。這種類型的鍊錶包含三個不同的部分：資料來源、指標和下一個節點。透過這種鍊錶，我們可以以反向的方式遍歷整個清單。
Circular Linked List − In a circular linked list the first node pointer indicated by the last node of the list. It means, the list has no start and no ending point. To traverse a circular linked list, the user can start from any node and traverse the list in forward or backward direction as their wish.
雙向循環鍊錶 - 這是一個雙向循環鍊錶，它包含了前一個節點和後一個節點的指標。它的第一個節點的前一個節點不包含空值。
在本文中，我們將為上述提到的鍊錶建立一些程式碼，透過這些程式碼，我們將學習如何在C 環境中反轉鍊錶節點中的每個單字。
Algorithm to reverse each word present in a linked list node
第一步 - 宣告一個暫存數組。
Step 2 − Traverse a linked list.
Step 3 − If the current element is an alphabet then store the element.
#Step 4 − Else, increase node by 1 pointer.
#第五步 - 再次從頭部遍歷。
Step 6 − If the current element is alphabet then copy it to the last element.
步驟 7 - 減少目前索引。
第8步 - 必須進行迭代。
第9步 - 否則，將其增加一。
將鍊錶節點中的每個單字反轉的語法
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
跟隨的方法：
Approach 1 − Reverse each word present in a linked list
Approach 2 − Reverse the whole sentence present in a linked list.
Approach 3 − Reverse a doubly circular linked list.
Approach 4 − Reverse a circular linked list.
#途徑5 − 在不影響特殊字元的情況下反轉鍊錶。
Reverse each word present in a linked list by using C
Here in this particular C build code we have reversed each word present in a linked list.
Example 1
的中文翻譯為：範例 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;
}
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
反轉鍊錶中的整個句子
在這個特定的程式碼中，我們已經將鍊錶中的整個句子進行了反轉。
#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;
}
Output
#Kolkata And Dhaka Between Runs Train International An Is Express Maitree 13110,
Reverse a doubly circular linked list
Here in this particular code we have reversed a doubly circular linked list.
Example 3
的中文翻譯為：範例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>
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
反轉循環鍊錶
在這個特定的程式碼中，我們已經反轉了一個循環鍊錶的資料集。
Example 4
的中文翻譯為：範例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>
Output
#Given circular linked list is here: 10 16 7 2022 Reversed circular linked list after method: 2022 7 16 10
反轉一個鍊錶而不影響特殊字元
Here in this particular code we have reversed the data set of linked list without affecting special characters.
Example 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;
}
Output
#Given linked list is here: B@010ATAKLOKARDUR Reversed Linked list is here: R@010UDRAKOLKATAB
Conclusion
在本文中，我們學習如何反轉鍊錶節點中的每個單字。我們在這裡建立了C 程式碼，以展示可能的反轉過程，以便您對鍊錶節點的反轉有一個廣泛的了解。
以上是將鍊錶節點中的每個單字反轉的詳細內容。更多資訊請關注PHP中文網其他相關文章！