資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究使用連結串列排序給定的字元陣列
在這個問題中，我們需要使用連結串列對給定的字元陣列進行排序。我們可以使用氣泡排序、選擇排序、歸併排序等技術對陣列進行排序。
在這裡，我們將首先將陣列轉換為連結串列，然後使用選擇排序和氣泡排序技術對陣列進行排序。
問題陳述 - 我們給定一個長度為 N 的陣列 arr[]。該陣列包含小寫字母字元。我們需要使用連結串列對陣列進行排序。
示例
輸入
arr[] = {'e', 's', 'a', 'x', 'c', 'e','f', 'p', 'b', 'n', 'a'};
輸出
a -> a -> b -> c -> e -> e -> f -> n -> p -> s -> x -> NULL
解釋 - 我們已經按升序對陣列進行了排序。
輸入
arr[] = {'g', 'g', 'h', 'i', 'j', 'k', 'k', 'l', 'm', 'n', 'o'};
輸出
g -> g -> h -> i -> j -> k -> k -> l -> m -> n -> o -> NULL
解釋 - 陣列 arr[] 和輸出與陣列相同，因為陣列已經排序。
方法 1
在這種方法中，我們將使用氣泡排序演算法對連結串列進行排序。首先，我們將陣列轉換為連結串列，然後使用氣泡排序技術。在氣泡排序技術中，我們進行總共 N 次迭代來交換所有大於下一個元素的列表元素。
演算法
步驟 1 - sortLinkedList() 函式用於對連結串列進行排序，它以起始節點和列表長度作為引數。
步驟 2 - 定義 'curr' 節點和 'swapped' 布林變數以跟蹤單次迭代中是否發生了任何交換。
步驟 3 - 使用迴圈遍歷連結串列。將 'start' 節點分配給 'curr' 並將 'swapped' 初始化為 false。
步驟 4 - 現在，使用另一個巢狀迴圈進行迭代，直到 len − p −1。定義 'temp1' 和 'temp2' 變數並將它們分別初始化為 'curr' 節點及其下一個節點。
步驟 5 - 如果 temp1 −> ch 大於 temp2 −> ch，則交換它們並更新 'curr' 節點和 'swapped' 變數的值。
步驟 6 - 將 'curr' 移動到下一個節點。
步驟 7 - 如果 'swapped == false' 並且在使用巢狀迴圈進行迭代時未更新，則中斷外迴圈，因為列表已排序。
示例
在這個例子中，我們使用了結構來建立連結串列。此外，我們定義了 addNode() 函式將節點插入到當前列表中。我們獲取陣列的每個元素並使用 addNode() 函式將字元新增到列表中。
addNode() 函式遍歷列表，直到獲取最後一個節點，並在最後新增新節點。
#include <iostream>
using namespace std;
// creating the struct listNode
struct listNode {
int ch;
listNode *next;
} listNode;
// Swapping the nodes of the linked list
struct listNode *swap(struct listNode *pointer1, struct listNode *pointer2) {
struct listNode *tmp = pointer2->next;
pointer2->next = pointer1;
pointer1->next = tmp;
return pointer2;
}
// Sorting the linked list
void sortLinkedList(struct listNode **start, int len) {
// storing the current node
struct listNode **curr;
int p, q;
bool swapped = false;
for (p = 0; p <= len; p++) {
// store the current node address in curr
curr = start;
swapped = false;
// traverse the list
for (q = 0; q < len - p - 1; q++) {
struct listNode *temp1 = *curr;
struct listNode *temp2 = temp1->next;
// If temp1 > temp2 swap them
if (temp1->ch > temp2->ch) {
// Update the link after swapping
*curr = swap(temp1, temp2);
swapped = true;
}
// Move the current pointer to the next node
curr = &(*curr)->next;
}
// If any pair of elements is not swapped, break the loop.
if (swapped == false)
break;
}
}
// adding nodes to the linked list
void addNode(struct listNode **start, int ch) {
// creating a new node
struct listNode *temp = new struct listNode();
// add ch to the node
temp->ch = ch;
temp->next = NULL;
// If the list is empty, add a node to the list
if (*start == NULL) {
*start = temp;
} else {
// If the list has some nodes, append the node at the end of the list
struct listNode *pointer1 = *start;
while (pointer1->next != NULL) {
pointer1 = pointer1->next;
}
pointer1->next = temp;
}
}
// print nodes
void printLinkedList(struct listNode *head) {
cout << "The sorted list is " << endl;
while (head != NULL) {
cout << char(head->ch) << " -> ";
head = head->next;
}
cout << "NULL" << endl;
}
int main() {
int arr[] = {'e', 's', 'a', 'x', 'c', 'e', 'f', 'p', 'b', 'n', 'a'};
int len, p;
// create an empty linked list
struct listNode *start = NULL;
len = sizeof(arr) / sizeof(arr[0]);
// inserting characters of the array to a linked list
for (p = 0; p < len; p++)
addNode(&start, arr[p]);
// Sort the list
sortLinkedList(&start, len);
printLinkedList(start);
return 0;
}
輸出
The sorted list is a -> a -> b -> c -> e -> e -> f -> n -> p -> s -> x -> NULL
時間複雜度 - O(N^2)，因為我們使用了兩個巢狀迴圈。
空間複雜度 - O(1)，因為我們沒有在 sortLinkedList() 函式中使用動態空間。但是，當我們將陣列轉換為列表時，我們使用了 O(N) 空間，但這不屬於排序的一部分。
方法 2
在這種方法中，我們將使用選擇排序演算法對連結串列進行排序。在選擇排序演算法中，我們從 len − p 的字尾中找到包含最小值的節點。之後，我們將最小節點與第 p 個索引處的節點交換。
演算法
步驟 1 - 定義並初始化 'current' 節點為 'start' 節點。
步驟 2 - 使用 while 迴圈進行迭代，直到 'current' 節點不為空。
步驟 3 - 將 'minNode' 初始化為 'current' 節點，並將 'traverse' 初始化為下一個 current，因為我們需要找到最小節點。
步驟 4 - 使用巢狀 while 迴圈查詢最小節點並將其與 'current' 節點交換。
步驟 5 - 將 current 節點移動到下一個。
示例
#include <iostream>
using namespace std;
struct listNode {
int ch;
listNode* next;
};
void swapNodes(struct listNode* node1, struct listNode* node2) {
int temp = node1->ch;
node1->ch = node2->ch;
node2->ch = temp;
}
void sortLinkedList(struct listNode* start) {
struct listNode* current = start;
while (current != nullptr) {
struct listNode* minNode = current;
struct listNode* traverse = current->next;
while (traverse != nullptr) {
if (traverse->ch < minNode->ch) {
minNode = traverse;
}
traverse = traverse->next;
}
swapNodes(current, minNode);
current = current->next;
}
}
void addNode(struct listNode** start, int ch) {
struct listNode* newNode = new struct listNode();
newNode->ch = ch;
newNode->next = nullptr;
if (*start == nullptr) {
*start = newNode;
} else {
struct listNode* current = *start;
while (current->next != nullptr) {
current = current->next;
}
current->next = newNode;
}
}
void printLinkedList(struct listNode* head) {
cout << "The sorted list is " << endl;
while (head != nullptr) {
cout << char(head->ch) << " -> ";
head = head->next;
}
cout << "NULL" << endl;
}
int main() {
int arr[] = {'e', 's', 'a', 'x', 'c', 'e', 'f', 'p', 'b', 'n', 'a'};
int len = sizeof(arr) / sizeof(arr[0]);
struct listNode* start = nullptr;
for (int p = 0; p < len; p++) {
addNode(&start, arr[p]);
}
sortLinkedList(start);
printLinkedList(start);
return 0;
}
輸出
The sorted list is a -> a -> b -> c -> e -> e -> f -> n -> p -> s -> x -> NULL
時間複雜度 - O(N^2)，因為我們使用了兩個巢狀 while 迴圈。
空間複雜度 - O(1)，因為我們沒有使用動態空間。
187 次檢視
