Dada una array arr[] que contiene N alfabetos ingleses en minúsculas, la tarea es ordenar esta array arr[] usando una lista enlazada.
Ejemplos:
Entrada: arr[] = [‘b’, ‘b’, ‘c’, ‘c’, ‘d’, ‘e’, ’f’, ‘b’, ‘b’, ‘a’, ‘a’ ]
Salida: a->a->b->b->b->b->c->c->d->e->f->NULLEntrada: arr[] = [‘g’, ‘e’, ’e’, ’k’, ‘s’, ‘f’, ‘o’, ‘r’, ‘g’, ‘e’, ’e’ , ‘k’, ‘s’]
Salida: e->e->e->e->f->g->g->k->k->o->r->s->s-> NULO
Enfoque: para resolver este problema, primero cree la lista vinculada a partir de la array de caracteres. Después de que se haya formado la lista enlazada, ordénela usando la ordenación de burbuja .
A continuación se muestra la implementación del enfoque anterior:
C++
#include <iostream>
using namespace std;
// Structure for a node
struct Node {
int data;
Node* next;
} Node;
// Function to swap the nodes
struct Node* swap(struct Node* ptr1, struct Node* ptr2)
{
struct Node* tmp = ptr2->next;
ptr2->next = ptr1;
ptr1->next = tmp;
return ptr2;
}
// Function to sort the list
void bubbleSort(struct Node** head, int count)
{
struct Node** h;
int i, j, swapped;
for (i = 0; i <= count; i++) {
h = head;
swapped = 0;
for (j = 0; j < count - i - 1; j++) {
struct Node* p1 = *h;
struct Node* p2 = p1->next;
if (p1->data > p2->data) {
// Update the link after swapping
*h = swap(p1, p2);
swapped = 1;
}
h = &(*h)->next;
}
// Break if the loop ended
// without any swap
if (swapped == 0)
break;
}
}
// Function to print the list
void printList(struct Node* n)
{
while (n != NULL) {
cout << char(n->data) << " -> ";
n = n->next;
}
cout << "NULL" << endl;
}
// Function to insert a struct Node
// at the end of a linked list
void insert(struct Node** head, int data)
{
struct Node* ptr = new struct Node();
ptr->data = data;
ptr->next = NULL;
if (*head == NULL) {
*head = ptr;
}
else {
struct Node* ptr1 = *head;
while (ptr1->next != NULL) {
ptr1 = ptr1->next;
}
ptr1->next = ptr;
}
}
// Driver Code
int main()
{
int arr[] = { 'b', 'b', 'c', 'c', 'd', 'e',
'f', 'b', 'b', 'a', 'a' };
int list_size, i;
// start with empty linked list
struct Node* start = NULL;
list_size = sizeof(arr) / sizeof(arr[0]);
// Create linked list from the array arr[]
for (i = 0; i < list_size; i++)
insert(&start, arr[i]);
// sort the linked list
bubbleSort(&start, list_size);
// Print list after sorting
printList(start);
return 0;
}
a -> a -> b -> b -> b -> b -> c -> c -> d -> e -> f -> NULL
Complejidad del tiempo: O(N 2 )
Publicación traducida automáticamente
Artículo escrito por akshitsaxenaa09 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA