C/Visual C - algoritmo de RADIX CON pilass un favor

 
Vista:

algoritmo de RADIX CON pilass un favor

Publicado por sakuargi^ (1 intervención) el 25/11/2002 08:09:46
buenas..

un favor nesescito el algoritmo de radix en c con listas y que me grafike el procedimiento

les agradese su ayuda sakuragi
Valora esta pregunta
Me gusta: Está pregunta es útil y esta claraNo me gusta: Está pregunta no esta clara o no es útil
0
Responder
Imágen de perfil de Alejandro

Algoritmo de [i]radix sort[/i] en C utilizando listas y gráfica del procedimiento

Publicado por Alejandro (913 intervenciones) el 03/04/2025 00:54:42
Sakuargi^, a continuación, te presento una implementación del algoritmo radix sort en C utilizando listas enlazadas. Además, te proporcionaré una descripción de cómo podrías graficar el procedimiento, aunque la parte de la gráfica se explicará conceptualmente, ya que la implementación gráfica puede variar según las bibliotecas que utilices.

Implementación de radix sort en C con listas enlazadas



Primero, aquí tienes el código para implementar radix sort utilizando listas enlazadas:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
typedef struct Node {
    int data;
    struct Node* next;
} Node;
 
void append(Node** head_ref, int new_data) {
    Node* new_node = (Node*)malloc(sizeof(Node));
    Node* last = *head_ref;
    new_node->data = new_data;
    new_node->next = NULL;
 
    if (*head_ref == NULL) {
        *head_ref = new_node;
        return;
    }
 
    while (last->next != NULL) {
        last = last->next;
    }
    last->next = new_node;
}
 
void printList(Node* node) {
    while (node != NULL) {
        printf("%d -> ", node->data);
        node = node->next;
    }
    printf("NULL\n");
}
 
int getMax(Node* head) {
    int max = head->data;
    while (head != NULL) {
        if (head->data > max) {
            max = head->data;
        }
        head = head->next;
    }
    return max;
}
 
void countingSort(Node** head_ref, int exp) {
    Node* output = NULL; // Lista de salida
    int count[10] = {0};
    Node* current = *head_ref;
 
    // Contar ocurrencias
    while (current != NULL) {
        count[(current->data / exp) % 10]++;
        current = current->next;
    }
 
    // Cambiar count para que contenga la posición real de este dígito en output
    for(int i = 1; i < 10; i++) {
        count += count[i - 1];
    }
 
    // Construir la lista de salida
    current = *head_ref;
    while (current != NULL) {
        int index = (current->data / exp) % 10;
        append(&output, current->data);
        count[index]--;
        current = current->next;
    }
 
    // Copiar la lista de salida a head_ref
    *head_ref = output;
}
 
void radixSort(Node** head_ref) {
    int max = getMax(*head_ref);
 
    for (int exp = 1; max / exp > 0; exp *= 10) {
        countingSort(head_ref, exp);
        printf("Lista después de ordenar por el dígito en la posición %d: ", exp);
        printList(*head_ref);
    }
}
 
int main() {
    Node* head = NULL;
    append(&head, 170);
    append(&head, 45);
    append(&head, 75);
    append(&head, 90);
    append(&head, 802);
    append(&head, 24);
    append(&head, 2);
    append(&head, 66);
 
    printf("Lista original: ");
    printList(head);
 
    radixSort(&head);
 
    printf("Lista ordenada: ");
    printList(head);
 
    return 0;
}

Explicación del código



1. Estructura de nodo: Se define una estructura `Node` para representar cada elemento de la lista enlazada.
2. Funciones:
- `append`: Agrega un nuevo nodo al final de la lista.
- `printList`:Imprime los elementos de la lista.
- `getMax`: Encuentra el valor máximo en la lista.
- `countingSort`: Realiza el ordenamiento por conteo para un dígito específico.
- `radixSort`: Implementa el algoritmo [i]radix sort
utilizando `countingSort` para cada dígito.
3. Función principal: Se crea una lista enlazada, se añaden elementos y se llama a `radixSort` para ordenar la lista.

Gráfica del procedimiento



Para graficar el procedimiento de [i]radix sort
, puedes seguir estos pasos conceptuales:

1. Visualización de la lista: Cada vez que se realiza un paso de ordenamiento (es decir, después de cada llamada a `countingSort`), puedes graficar la lista actual. Esto puede hacerse utilizando bibliotecas gráficas como Matplotlib en Python o Graphviz para generar gráficos a partir de datos.

2. Diagrama de flujo: Puedes crear un diagrama de flujo que muestre cómo se mueve a través de los dígitos y cómo se reorganizan los elementos en cada paso.

3. Animación: Si deseas una representación más dinámica, puedes usar herramientas de visualización de algoritmos que permiten animar el proceso de ordenamiento.

Notas



- Asegúrate de tener suficiente memoria para manejar la lista enlazada, especialmente si trabajas con grandes conjuntos de datos.
- La implementación gráfica puede variar según las herramientas y bibliotecas que elijas utilizar.
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar