資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學反轉連結串列節點中的每個單詞
連結串列是一種類似鏈狀的線性資料結構，與陣列不同，其元素並非連續儲存在記憶體中。在特定的連結串列中，元素透過指標與下一個元素連結。簡單來說，連結串列是一系列資料容器，這些容器中的元素包含指向下一個節點的路徑或引用連結。連結串列的第一個元素是一個頭指標。如果該列表的第一個節點為空，則它不指向任何內容或為空。
資料結構中存在不同型別的連結串列。
單鏈表 − 它是資料結構中一種基本的連結串列型別，每個節點都包含一些資料以及指向下一個節點的相同資料型別的指標。對於此連結串列，時間複雜度和輔助空間都是 O(n)。
雙鏈表 − 這是一種複雜的雙向連結串列，包含一個指向前一個節點的序列指標。這種型別的連結串列包含三個不同的資料來源部分：資料、指標和下一個節點。透過它，我們可以反向遍歷整個列表。
迴圈連結串列 − 在迴圈連結串列中，第一個節點指標由列表的最後一個節點指示。這意味著列表沒有起點也沒有終點。要遍歷迴圈連結串列，使用者可以從任何節點開始，並根據需要向前或向後遍歷列表。
雙向迴圈連結串列 − 這是一種雙向迴圈連結串列，包含指向前一個節點和下一個節點的指標。它不包含指向第一個節點之前的空值。
在本文中，我們將為上述連結串列構建一些程式碼，透過這些程式碼，我們將學習如何在 C++ 環境中反轉連結串列節點中的每個單詞。
反轉連結串列節點中每個單詞的演算法
步驟 1 − 宣告一個臨時陣列。
步驟 2 − 遍歷連結串列。
步驟 3 − 如果當前元素是字母，則儲存該元素。
步驟 4 − 否則，將節點指標加 1。
步驟 5 − 從頭節點再次遍歷。
步驟 6 − 如果當前元素是字母，則將其複製到最後一個元素。
步驟 7 − 減少當前索引。
步驟 8 − 需要進行迭代。
步驟 9 − 否則，將其加 1。
反轉連結串列節點中每個單詞的語法
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
遵循的方法：-
方法 1 − 反轉連結串列中的每個單詞
方法 2 − 反轉連結串列中的整個句子。
方法 3 − 反轉雙向迴圈連結串列。
方法 4 − 反轉迴圈連結串列。
方法 5 − 反轉連結串列而不影響特殊字元。
使用 C++ 反轉連結串列中每個單詞
在此特定的 C++ 程式碼中，我們反轉了連結串列中存在的每個單詞。
示例 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;
}
輸出
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;
}
輸出
Kolkata And Dhaka Between Runs Train International An Is Express Maitree 13110,
反轉雙向迴圈連結串列
在此特定程式碼中，我們反轉了一個雙向迴圈連結串列。
示例 3
#include <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; }
輸出
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
反轉迴圈連結串列
在此特定程式碼中，我們反轉了迴圈連結串列的資料集。
示例 4
#include <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; }
輸出
Given circular linked list is here: 10 16 7 2022 Reversed circular linked list after method: 2022 7 16 10
反轉連結串列而不影響特殊字元
在此特定程式碼中，我們反轉了連結串列的資料集，而不影響特殊字元。
示例 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;
}
輸出
Given linked list is here: B@010ATAKLOKARDUR Reversed Linked list is here: R@010UDRAKOLKATAB
結論
在今天的文章中，我們學習瞭如何反轉連結串列節點中存在的每個單詞。我們在此構建了 C++ 程式碼以及可能的方法，以向您全面介紹連結串列節點可能的反轉過程。
更新於：2023年4月5日
259 次瀏覽
廣告