El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
HOME Mis cursos Finalizados
◄ Anterior
◄

Estructuras de Datos Dinámicas

Siguiente ►
►

En este módulo, exploraremos las estructuras de datos dinámicas en ALGOL. Las estructuras de datos dinámicas son aquellas que pueden cambiar de tamaño durante la ejecución del programa, lo que las hace muy útiles para una variedad de aplicaciones donde el tamaño de los datos no es conocido de antemano.

Conceptos Clave

  1. Memoria Dinámica: La capacidad de asignar y liberar memoria durante la ejecución del programa.
  2. Listas Enlazadas: Una estructura de datos donde cada elemento (nodo) contiene un valor y un puntero al siguiente nodo.
  3. Pilas y Colas: Estructuras de datos que siguen el principio LIFO (Last In, First Out) y FIFO (First In, First Out), respectivamente.
  4. Árboles: Estructuras jerárquicas donde cada nodo tiene un valor y punteros a nodos hijos.

Memoria Dinámica en ALGOL

ALGOL permite la asignación dinámica de memoria mediante el uso de punteros. A continuación, se muestra cómo se puede declarar y utilizar un puntero en ALGOL:

begin
    integer pointer p;
    integer array a[1:10];
    p := new integer array[1:10];
    p[1] := 5;
    p[2] := 10;
    ! Liberar memoria
    dispose p;
end;

Explicación del Código

  • integer pointer p;: Declara un puntero p que puede apuntar a un entero.
  • p := new integer array[1:10];: Asigna memoria para un arreglo de 10 enteros y hace que p apunte a este arreglo.
  • p[1] := 5;: Asigna el valor 5 al primer elemento del arreglo.
  • dispose p;: Libera la memoria asignada al arreglo.

Listas Enlazadas

Las listas enlazadas son una de las estructuras de datos dinámicas más comunes. Cada nodo en una lista enlazada contiene un valor y un puntero al siguiente nodo.

Ejemplo de Lista Enlazada en ALGOL

begin
    record node(
        integer value;
        ref(node) next;
    );
    ref(node) head, temp;
    
    ! Crear el primer nodo
    head := new node;
    head.value := 10;
    head.next := nil;
    
    ! Crear el segundo nodo
    temp := new node;
    temp.value := 20;
    temp.next := nil;
    head.next := temp;
    
    ! Imprimir los valores de la lista
    temp := head;
    while temp /= nil do
    begin
        print(temp.value);
        temp := temp.next;
    end;
end;

Explicación del Código

  • record node: Define un registro node con un entero value y un puntero next al siguiente nodo.
  • ref(node) head, temp;: Declara dos punteros a nodos, head y temp.
  • head := new node;: Asigna memoria para el primer nodo y hace que head apunte a él.
  • head.value := 10;: Asigna el valor 10 al primer nodo.
  • temp := new node;: Asigna memoria para el segundo nodo y hace que temp apunte a él.
  • head.next := temp;: Hace que el primer nodo apunte al segundo nodo.
  • while temp /= nil do: Itera a través de la lista e imprime los valores de cada nodo.

Pilas y Colas

Pila (Stack)

Una pila sigue el principio LIFO (Last In, First Out). A continuación se muestra un ejemplo de implementación de una pila en ALGOL:

begin
    record stackNode(
        integer value;
        ref(stackNode) next;
    );
    ref(stackNode) top;
    
    procedure push(integer val);
    begin
        ref(stackNode) newNode;
        newNode := new stackNode;
        newNode.value := val;
        newNode.next := top;
        top := newNode;
    end push;
    
    integer procedure pop();
    begin
        integer val;
        if top /= nil then
        begin
            val := top.value;
            top := top.next;
        end;
        pop := val;
    end pop;
    
    ! Uso de la pila
    push(10);
    push(20);
    print(pop()); ! Imprime 20
    print(pop()); ! Imprime 10
end;

Explicación del Código

  • record stackNode: Define un nodo de la pila con un valor y un puntero al siguiente nodo.
  • ref(stackNode) top;: Declara un puntero top que apunta al nodo superior de la pila.
  • procedure push(integer val);: Define el procedimiento push para agregar un valor a la pila.
  • integer procedure pop();: Define el procedimiento pop para eliminar y devolver el valor superior de la pila.

Cola (Queue)

Una cola sigue el principio FIFO (First In, First Out). A continuación se muestra un ejemplo de implementación de una cola en ALGOL:

begin
    record queueNode(
        integer value;
        ref(queueNode) next;
    );
    ref(queueNode) front, rear;
    
    procedure enqueue(integer val);
    begin
        ref(queueNode) newNode;
        newNode := new queueNode;
        newNode.value := val;
        newNode.next := nil;
        if rear /= nil then
            rear.next := newNode;
        else
            front := newNode;
        rear := newNode;
    end enqueue;
    
    integer procedure dequeue();
    begin
        integer val;
        if front /= nil then
        begin
            val := front.value;
            front := front.next;
            if front = nil then
                rear := nil;
        end;
        dequeue := val;
    end dequeue;
    
    ! Uso de la cola
    enqueue(10);
    enqueue(20);
    print(dequeue()); ! Imprime 10
    print(dequeue()); ! Imprime 20
end;

Explicación del Código

  • record queueNode: Define un nodo de la cola con un valor y un puntero al siguiente nodo.
  • ref(queueNode) front, rear;: Declara dos punteros front y rear que apuntan al primer y último nodo de la cola, respectivamente.
  • procedure enqueue(integer val);: Define el procedimiento enqueue para agregar un valor a la cola.
  • integer procedure dequeue();: Define el procedimiento dequeue para eliminar y devolver el valor del primer nodo de la cola.

Árboles

Los árboles son estructuras jerárquicas donde cada nodo tiene un valor y punteros a nodos hijos. Un tipo común de árbol es el árbol binario, donde cada nodo tiene como máximo dos hijos.

Ejemplo de Árbol Binario en ALGOL

begin
    record treeNode(
        integer value;
        ref(treeNode) left, right;
    );
    ref(treeNode) root;
    
    procedure insert(ref(treeNode) node, integer val);
    begin
        if node = nil then
        begin
            node := new treeNode;
            node.value := val;
            node.left := nil;
            node.right := nil;
        end
        else if val < node.value then
            insert(node.left, val)
        else
            insert(node.right, val);
    end insert;
    
    procedure inorder(ref(treeNode) node);
    begin
        if node /= nil then
        begin
            inorder(node.left);
            print(node.value);
            inorder(node.right);
        end;
    end inorder;
    
    ! Uso del árbol binario
    insert(root, 10);
    insert(root, 5);
    insert(root, 15);
    inorder(root); ! Imprime 5, 10, 15
end;

Explicación del Código

  • record treeNode: Define un nodo del árbol con un valor y punteros a los nodos izquierdo y derecho.
  • ref(treeNode) root;: Declara un puntero root que apunta a la raíz del árbol.
  • procedure insert(ref(treeNode) node, integer val);: Define el procedimiento insert para agregar un valor al árbol.
  • procedure inorder(ref(treeNode) node);: Define el procedimiento inorder para realizar un recorrido en orden del árbol.

Ejercicio Práctico

Ejercicio

Implementa una lista enlazada en ALGOL que permita insertar elementos al final de la lista y recorrerla para imprimir todos sus valores.

Solución

begin
    record node(
        integer value;
        ref(node) next;
    );
    ref(node) head, temp;
    
    procedure append(integer val);
    begin
        ref(node) newNode;
        newNode := new node;
        newNode.value := val;
        newNode.next := nil;
        if head = nil then
            head := newNode
        else
        begin
            temp := head;
            while temp.next /= nil do
                temp := temp.next;
            temp.next := newNode;
        end;
    end append;
    
    procedure printList();
    begin
        temp := head;
        while temp /= nil do
        begin
            print(temp.value);
            temp := temp.next;
        end;
    end printList;
    
    ! Uso de la lista enlazada
    append(10);
    append(20);
    append(30);
    printList(); ! Imprime 10, 20, 30
end;

Explicación del Código

  • procedure append(integer val);: Define el procedimiento append para agregar un valor al final de la lista.
  • procedure printList();: Define el procedimiento printList para recorrer e imprimir los valores de la lista.

Conclusión

En esta sección, hemos explorado las estructuras de datos dinámicas en ALGOL, incluyendo listas enlazadas, pilas, colas y árboles. Estas estructuras son fundamentales para manejar datos de manera eficiente y flexible. Asegúrate de practicar los ejemplos y ejercicios proporcionados para consolidar tu comprensión de estos conceptos. En el próximo módulo, profundizaremos en el manejo de archivos en ALGOL.

◄ Anterior
◄
Siguiente ►
►
El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
© Copyright 2024. Todos los derechos reservados