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

Llistes Enllaçades

Següent ►
►

Les llistes enllaçades són una estructura de dades fonamental que permet emmagatzemar una col·lecció d'elements de manera dinàmica. A diferència dels arrays, les llistes enllaçades no requereixen una mida fixa i poden créixer o disminuir segons sigui necessari. En aquest tema, aprendrem com crear i gestionar llistes enllaçades en Fortran.

Continguts

  1. Introducció a les Llistes Enllaçades
  2. Definició d'un Node
  3. Creació d'una Llista Enllaçada
  4. Inserció d'Elements
  5. Eliminació d'Elements
  6. Recórrer una Llista Enllaçada
  7. Exercicis Pràctics

  1. Introducció a les Llistes Enllaçades

Una llista enllaçada és una col·lecció de nodes on cada node conté un element de dades i un punter al següent node de la llista. Les llistes enllaçades poden ser de diversos tipus:

  • Llista enllaçada simple: Cada node apunta al següent node.
  • Llista enllaçada doble: Cada node apunta tant al següent com al node anterior.
  • Llista enllaçada circular: L'últim node apunta al primer node, formant un cercle.

  1. Definició d'un Node

En Fortran, podem definir un node utilitzant tipus derivats. Un node típic per a una llista enllaçada simple es defineix de la següent manera:

type :: Node
    integer :: data
    type(Node), pointer :: next => null()
end type Node

  1. Creació d'una Llista Enllaçada

Per crear una llista enllaçada, necessitem inicialitzar el primer node (capçalera) de la llista. Aquí teniu un exemple de com fer-ho:

program LinkedListExample
    implicit none
    type(Node), pointer :: head

    ! Inicialitzem la capçalera de la llista
    allocate(head)
    head%data = 10
    head%next => null()

    print *, 'Primer node creat amb valor: ', head%data
end program LinkedListExample

  1. Inserció d'Elements

Per inserir un nou element a la llista, hem de crear un nou node i ajustar els punters adequadament. Aquí teniu un exemple d'inserció al principi de la llista:

subroutine insertAtBeginning(head, value)
    type(Node), pointer :: head
    integer, intent(in) :: value
    type(Node), pointer :: newNode

    allocate(newNode)
    newNode%data = value
    newNode%next => head
    head => newNode
end subroutine insertAtBeginning

  1. Eliminació d'Elements

Per eliminar un element de la llista, hem de trobar el node a eliminar i ajustar els punters dels nodes adjacents. Aquí teniu un exemple d'eliminació del primer element:

subroutine deleteFirst(head)
    type(Node), pointer :: head
    type(Node), pointer :: temp

    if (associated(head)) then
        temp => head
        head => head%next
        deallocate(temp)
    end if
end subroutine deleteFirst

  1. Recórrer una Llista Enllaçada

Per recórrer una llista enllaçada, podem utilitzar un bucle que segueixi els punters fins arribar al final de la llista. Aquí teniu un exemple:

subroutine traverseList(head)
    type(Node), pointer :: head
    type(Node), pointer :: current

    current => head
    do while (associated(current))
        print *, 'Node value: ', current%data
        current => current%next
    end do
end subroutine traverseList

  1. Exercicis Pràctics

Exercici 1: Inserció al Final de la Llista

Escriu una subrutina insertAtEnd que insereixi un nou node al final de la llista.

Exercici 2: Cerca en la Llista

Escriu una subrutina searchList que cerqui un valor específic en la llista i retorni si el valor es troba o no.

Exercici 3: Eliminació d'un Element Específic

Escriu una subrutina deleteValue que elimini un node amb un valor específic de la llista.

Solucions

Solució a l'Exercici 1

subroutine insertAtEnd(head, value)
    type(Node), pointer :: head
    integer, intent(in) :: value
    type(Node), pointer :: newNode, current

    allocate(newNode)
    newNode%data = value
    newNode%next => null()

    if (.not. associated(head)) then
        head => newNode
    else
        current => head
        do while (associated(current%next))
            current => current%next
        end do
        current%next => newNode
    end if
end subroutine insertAtEnd

Solució a l'Exercici 2

logical function searchList(head, value)
    type(Node), pointer :: head
    integer, intent(in) :: value
    type(Node), pointer :: current

    current => head
    searchList = .false.
    do while (associated(current))
        if (current%data == value) then
            searchList = .true.
            return
        end if
        current => current%next
    end do
end function searchList

Solució a l'Exercici 3

subroutine deleteValue(head, value)
    type(Node), pointer :: head
    integer, intent(in) :: value
    type(Node), pointer :: current, previous

    current => head
    previous => null()

    do while (associated(current))
        if (current%data == value) then
            if (associated(previous)) then
                previous%next => current%next
            else
                head => current%next
            end if
            deallocate(current)
            return
        end if
        previous => current
        current => current%next
    end do
end subroutine deleteValue

Conclusió

Les llistes enllaçades són una eina poderosa per gestionar col·leccions de dades de manera dinàmica. Hem après a definir nodes, crear llistes, inserir i eliminar elements, i recórrer la llista. Amb aquests coneixements, estàs preparat per abordar problemes més complexos que requereixin estructures de dades dinàmiques en Fortran.

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