El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
HOME Els meus cursos Finalitzats
◄ Anterior
◄

Estructures de Dades Dinàmiques

Següent ►
►

Les estructures de dades dinàmiques són fonamentals en la programació, ja que permeten gestionar dades de manera flexible i eficient. En aquest tema, explorarem com treballar amb estructures de dades dinàmiques en ALGOL, incloent l'ús de punteres, l'assignació dinàmica de memòria i la implementació de llistes enllaçades.

Continguts

  1. Introducció a les Estructures de Dades Dinàmiques
  2. Punteres i Memòria Dinàmica
  3. Llistes Enllaçades
  4. Exercicis Pràctics
  5. Conclusió

Introducció a les Estructures de Dades Dinàmiques

Les estructures de dades dinàmiques permeten que la mida de les dades canviï durant l'execució del programa. Això és especialment útil quan no es coneix la mida de les dades en temps de compilació. Les estructures de dades dinàmiques més comunes inclouen:

  • Llistes enllaçades
  • Piles
  • Cues
  • Arbres
  • Grafos

Punteres i Memòria Dinàmica

Punteres

Un punter és una variable que emmagatzema l'adreça de memòria d'una altra variable. En ALGOL, els punteres es poden utilitzar per crear estructures de dades dinàmiques.

Assignació Dinàmica de Memòria

L'assignació dinàmica de memòria permet reservar espai en memòria durant l'execució del programa. En ALGOL, això es pot fer utilitzant la funció new.

Exemple de Punteres i Assignació Dinàmica

begin
    integer pointer p;
    integer array a;
    
    p := new integer;
    a := new integer array (1:10);
    
    p^ := 5;
    a[1] := 10;
    
    print(p^);  ! Imprimeix 5
    print(a[1]);  ! Imprimeix 10
    
    dispose(p);
    dispose(a);
end

En aquest exemple, p és un punter a un enter i a és un punter a un array d'enters. Utilitzem new per assignar memòria dinàmica i dispose per alliberar-la.

Llistes Enllaçades

Definició

Una llista enllaçada és una col·lecció de nodes on cada node conté un valor i un punter al següent node de la llista. Les llistes enllaçades poden ser simples, dobles o circulars.

Implementació d'una Llista Enllaçada Simple

begin
    record node = (integer value; node pointer next);
    node pointer head, temp;
    
    head := new node;
    head.value := 1;
    head.next := new node;
    head.next.value := 2;
    head.next.next := new node;
    head.next.next.value := 3;
    head.next.next.next := nil;
    
    temp := head;
    while temp != nil do
    begin
        print(temp.value);
        temp := temp.next;
    end;
    
    ! Alliberar memòria
    temp := head;
    while temp != nil do
    begin
        node pointer nextNode;
        nextNode := temp.next;
        dispose(temp);
        temp := nextNode;
    end;
end

En aquest exemple, creem una llista enllaçada simple amb tres nodes. Cada node conté un valor enter i un punter al següent node. Després, recorrem la llista per imprimir els valors i finalment alliberem la memòria.

Exercicis Pràctics

Exercici 1: Crear una Llista Enllaçada

Crea una llista enllaçada que contingui els valors 10, 20, 30, 40 i 50. Imprimeix els valors de la llista.

Solució

begin
    record node = (integer value; node pointer next);
    node pointer head, temp;
    
    head := new node;
    head.value := 10;
    head.next := new node;
    head.next.value := 20;
    head.next.next := new node;
    head.next.next.value := 30;
    head.next.next.next := new node;
    head.next.next.next.value := 40;
    head.next.next.next.next := new node;
    head.next.next.next.next.value := 50;
    head.next.next.next.next.next := nil;
    
    temp := head;
    while temp != nil do
    begin
        print(temp.value);
        temp := temp.next;
    end;
    
    ! Alliberar memòria
    temp := head;
    while temp != nil do
    begin
        node pointer nextNode;
        nextNode := temp.next;
        dispose(temp);
        temp := nextNode;
    end;
end

Exercici 2: Inserir un Node en una Llista Enllaçada

Modifica la llista enllaçada de l'exercici anterior per inserir un node amb el valor 25 després del node amb el valor 20.

Solució

begin
    record node = (integer value; node pointer next);
    node pointer head, temp, newNode;
    
    head := new node;
    head.value := 10;
    head.next := new node;
    head.next.value := 20;
    head.next.next := new node;
    head.next.next.value := 30;
    head.next.next.next := new node;
    head.next.next.next.value := 40;
    head.next.next.next.next := new node;
    head.next.next.next.next.value := 50;
    head.next.next.next.next.next := nil;
    
    ! Inserir el node amb valor 25
    temp := head;
    while temp != nil do
    begin
        if temp.value = 20 then
        begin
            newNode := new node;
            newNode.value := 25;
            newNode.next := temp.next;
            temp.next := newNode;
            break;
        end;
        temp := temp.next;
    end;
    
    temp := head;
    while temp != nil do
    begin
        print(temp.value);
        temp := temp.next;
    end;
    
    ! Alliberar memòria
    temp := head;
    while temp != nil do
    begin
        node pointer nextNode;
        nextNode := temp.next;
        dispose(temp);
        temp := nextNode;
    end;
end

Conclusió

En aquest tema, hem après sobre les estructures de dades dinàmiques en ALGOL, incloent l'ús de punteres i l'assignació dinàmica de memòria. També hem implementat una llista enllaçada simple i hem practicat la inserció de nodes en una llista enllaçada. Aquestes habilitats són fonamentals per gestionar dades de manera flexible i eficient en els programes.

En el següent mòdul, explorarem temes avançats com la gestió d'arxius i la gestió de memòria en profunditat.

◄ Anterior
◄
Següent ►
►
El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
© Copyright 2024. Tots els drets reservats