数据结构
网络
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 次查看
