Iniciar sesiónCerrar
Correo:
Contraseña:
Entrar
Recordar sesión en este navegador
Iniciar sesiónIniciar sesiónCrear cuentaCrear cuenta
LWP » Foros » C/Visual C » ayuda de c

C/Visual C - ayuda de c

Volver
Nuevo Tema
<<>>
 
Vista:

ayuda de c

Publicado por javier (1 intervención) el 12/08/2002 20:29:12
hola soy estudiante de informatica y tengo una pregunta para alguien que sepa programar en C para un trabajo, haber si podriais ayudarme y decirme un algoritmo que haga lo siguiente: si tengo una lista donde cada elemento de la lista tiene tres variables una origen, otra destino y otra un puntero al elemento siguiente, cual seria el algoritmo para calcular si se produce un ciclo entre "n" elementos de la lista suponiendo que haya elementos que no tienen porque estar en el ciclo y si en la lista.
Contestar al correo [email protected]
Gracias.
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 para detectar ciclos en una lista enlazada

Publicado por Alejandro (913 intervenciones) el 14/03/2025 17:33:03
Para detectar ciclos en una lista enlazada donde cada elemento tiene tres variables (origen, destino y un puntero al siguiente elemento), puedes utilizar el algoritmo de Floyd, también conocido como el algoritmo del "tortuga y la liebre". Este algoritmo utiliza dos punteros que se mueven a diferentes velocidades para determinar si hay un ciclo en la lista.

Estructura de datos



Primero, definamos la estructura de la lista enlazada:

1
2
3
4
5
6
7
8
#include <stdio.h>
#include <stdlib.h>
 
typedef struct Node {
    int origen;
    int destino;
    struct Node* siguiente;
} Node;

Algoritmo para detectar ciclos



A continuación, implementaremos el algoritmo para detectar ciclos en la lista enlazada:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int detectarCiclo(Node* cabeza) {
    if (cabeza == NULL) {
        return 0;// La lista está vacía, no hay ciclo
    }
 
    Node* tortuga = cabeza; // Puntero lento
    Node* liebre = cabeza;  // Puntero rápido
 
    while (liebre != NULL && liebre->siguiente != NULL) {
        tortuga = tortuga->siguiente;          // Mueve tortuga un paso
        liebre = liebre->siguiente->siguiente; // Mueve liebre dos pasos
 
        if (tortuga == liebre) {
            return 1; // Se encontró un ciclo
        }
    }
 
    return 0; // No se encontró ciclo
}

Función principal



Aquí tienes un ejemplo de cómo usar la función `detectarCiclo` en la función principal:

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
int main() {
    // Crear una lista enlazada de ejemplo
    Node* nodo1 = (Node*)malloc(sizeof(Node));
    Node* nodo2 = (Node*)malloc(sizeof(Node));
    Node* nodo3 = (Node*)malloc(sizeof(Node));
    Node* nodo4 = (Node*)malloc(sizeof(Node));
 
    nodo1->origen = 1;
    nodo1->destino = 2;
    nodo1->siguiente = nodo2;
 
    nodo2->origen = 2;
    nodo2->destino = 3;
    nodo2->siguiente = nodo3;
 
    nodo3->origen = 3;
    nodo3->destino = 4;
    nodo3->siguiente = nodo4;
 
    nodo4->origen = 4;
    nodo4->destino = 1; // Crea un ciclo apuntando de vuelta a nodo1
    nodo4->siguiente = nodo1; // Descomentar esta línea para crear un ciclo
 
    // Detectar ciclo
    if (detectarCiclo(nodo1)) {
        printf("Se encontró un ciclo en la lista.\n");
    } else {
        printf("No se encontró ciclo en la lista.\n");
    }
 
    // Liberar memoria (en caso de no tener ciclo)
    free(nodo1);
    free(nodo2);
    free(nodo3);
    free(nodo4);
 
    return 0;
}

Notas adicionales



1. Complejidad: Este algoritmo tiene una complejidad de tiempo de O(n) y una complejidad de espacio de O(1), ya que solo utiliza dos punteros.
2. Ciclo: Puedes probar el código comentando o descomentando la línea que crea el ciclo en la lista para ver cómo funciona el algoritmo.
3. Liberación de memoria: Asegúrate de liberar la memoria de los nodos si no hay ciclo, o si decides no usar la lista después de la detección.

Con este algoritmo, podrás detectar si hay un ciclo en la lista enlazada que has descrito. ¡Buena suerte con tu trabajo, Javier!
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