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

Estructures de Dades Avançades

Següent ►
►

En aquest mòdul, explorarem les estructures de dades avançades en RPG. Aquestes estructures són fonamentals per a la creació de programes eficients i escalables. Aprendrem sobre les taules de hash, les cues, les piles i els arbres binaris, i com implementar-les en RPG.

Taules de Hash

Què és una Taula de Hash?

Una taula de hash és una estructura de dades que associa claus amb valors. Utilitza una funció de hash per calcular un índex en una matriu de cubetes o ranures, des d'on es pot trobar el valor desitjat.

Implementació d'una Taula de Hash en RPG

Dcl-S hashTable Pointer;
Dcl-S hashSize Int(10) Inz(10);
Dcl-S hashArray LikeDS(hashEntry) Dim(hashSize);

Dcl-DS hashEntry;
  key Char(20);
  value Char(50);
End-DS;

Dcl-Proc hashFunction;
  Dcl-Pi *N Int(10);
    key Char(20);
  End-Pi;
  Return %Rem(%CheckR('0123456789', key), hashSize);
End-Proc;

Dcl-Proc insertHash;
  Dcl-Pi *N;
    key Char(20);
    value Char(50);
  End-Pi;
  Dcl-S index Int(10);
  index = hashFunction(key);
  hashArray(index).key = key;
  hashArray(index).value = value;
End-Proc;

Dcl-Proc getHash;
  Dcl-Pi Char(50);
    key Char(20);
  End-Pi;
  Dcl-S index Int(10);
  index = hashFunction(key);
  Return hashArray(index).value;
End-Proc;

Explicació del Codi

  1. Declaració de la Taula de Hash: Declarem una matriu hashArray de tipus hashEntry amb una mida de hashSize.
  2. Funció de Hash: La funció hashFunction calcula un índex basat en la clau.
  3. Inserció en la Taula de Hash: La funció insertHash insereix una clau i un valor a la taula de hash.
  4. Recuperació de Valors: La funció getHash recupera el valor associat a una clau.

Cues

Què és una Cua?

Una cua és una estructura de dades que segueix el principi FIFO (First In, First Out). Els elements s'afegeixen al final de la cua i es treuen del principi.

Implementació d'una Cua en RPG

Dcl-S queue Pointer;
Dcl-S queueSize Int(10) Inz(10);
Dcl-S queueArray Char(50) Dim(queueSize);
Dcl-S front Int(10) Inz(0);
Dcl-S rear Int(10) Inz(0);

Dcl-Proc enqueue;
  Dcl-Pi *N;
    value Char(50);
  End-Pi;
  If rear < queueSize;
    queueArray(rear) = value;
    rear += 1;
  Else;
    // Gestió d'errors: cua plena
  EndIf;
End-Proc;

Dcl-Proc dequeue;
  Dcl-Pi Char(50);
  End-Pi;
  Dcl-S value Char(50);
  If front < rear;
    value = queueArray(front);
    front += 1;
  Else;
    // Gestió d'errors: cua buida
  EndIf;
  Return value;
End-Proc;

Explicació del Codi

  1. Declaració de la Cua: Declarem una matriu queueArray per emmagatzemar els elements de la cua.
  2. Enqueue: La funció enqueue afegeix un element al final de la cua.
  3. Dequeue: La funció dequeue treu un element del principi de la cua.

Piles

Què és una Pila?

Una pila és una estructura de dades que segueix el principi LIFO (Last In, First Out). Els elements s'afegeixen i es treuen del mateix extrem.

Implementació d'una Pila en RPG

Dcl-S stack Pointer;
Dcl-S stackSize Int(10) Inz(10);
Dcl-S stackArray Char(50) Dim(stackSize);
Dcl-S top Int(10) Inz(-1);

Dcl-Proc push;
  Dcl-Pi *N;
    value Char(50);
  End-Pi;
  If top < stackSize - 1;
    top += 1;
    stackArray(top) = value;
  Else;
    // Gestió d'errors: pila plena
  EndIf;
End-Proc;

Dcl-Proc pop;
  Dcl-Pi Char(50);
  End-Pi;
  Dcl-S value Char(50);
  If top >= 0;
    value = stackArray(top);
    top -= 1;
  Else;
    // Gestió d'errors: pila buida
  EndIf;
  Return value;
End-Proc;

Explicació del Codi

  1. Declaració de la Pila: Declarem una matriu stackArray per emmagatzemar els elements de la pila.
  2. Push: La funció push afegeix un element al cim de la pila.
  3. Pop: La funció pop treu un element del cim de la pila.

Arbres Binari

Què és un Arbre Binari?

Un arbre binari és una estructura de dades en la qual cada node té com a màxim dos fills, anomenats fill esquerre i fill dret.

Implementació d'un Arbre Binari en RPG

Dcl-DS TreeNode;
  value Char(50);
  left Pointer;
  right Pointer;
End-DS;

Dcl-S root Pointer;

Dcl-Proc insertNode;
  Dcl-Pi *N;
    node Pointer;
    value Char(50);
  End-Pi;
  If node = *Null;
    node = %Alloc(Size(TreeNode));
    node->value = value;
    node->left = *Null;
    node->right = *Null;
  ElseIf value < node->value;
    insertNode(node->left: value);
  Else;
    insertNode(node->right: value);
  EndIf;
End-Proc;

Dcl-Proc inOrderTraversal;
  Dcl-Pi *N;
    node Pointer;
  End-Pi;
  If node <> *Null;
    inOrderTraversal(node->left);
    Dsply node->value;
    inOrderTraversal(node->right);
  EndIf;
End-Proc;

Explicació del Codi

  1. Declaració de l'Arbre Binari: Declarem una estructura TreeNode per representar cada node de l'arbre.
  2. Inserció de Nodes: La funció insertNode insereix un nou node a l'arbre binari.
  3. Recorregut In-Order: La funció inOrderTraversal recorre l'arbre en ordre in-order i mostra els valors dels nodes.

Exercicis Pràctics

Exercici 1: Implementar una Taula de Hash amb Col·lisions

Implementa una taula de hash que gestioni col·lisions utilitzant l'encadenament.

Exercici 2: Implementar una Cua Circular

Implementa una cua circular per optimitzar l'ús de l'espai en la matriu.

Exercici 3: Implementar una Pila amb Capacitat Dinàmica

Implementa una pila que pugui redimensionar-se dinàmicament quan estigui plena.

Exercici 4: Implementar un Arbre Binari de Cerca

Implementa un arbre binari de cerca amb funcions per inserir, eliminar i buscar nodes.

Solucions

Solució a l'Exercici 1

Dcl-S hashTable Pointer;
Dcl-S hashSize Int(10) Inz(10);
Dcl-S hashArray LikeDS(hashEntry) Dim(hashSize);

Dcl-DS hashEntry;
  key Char(20);
  value Char(50);
  next Pointer;
End-DS;

Dcl-Proc hashFunction;
  Dcl-Pi *N Int(10);
    key Char(20);
  End-Pi;
  Return %Rem(%CheckR('0123456789', key), hashSize);
End-Proc;

Dcl-Proc insertHash;
  Dcl-Pi *N;
    key Char(20);
    value Char(50);
  End-Pi;
  Dcl-S index Int(10);
  Dcl-S newEntry Pointer;
  index = hashFunction(key);
  newEntry = %Alloc(Size(hashEntry));
  newEntry->key = key;
  newEntry->value = value;
  newEntry->next = hashArray(index);
  hashArray(index) = newEntry;
End-Proc;

Dcl-Proc getHash;
  Dcl-Pi Char(50);
    key Char(20);
  End-Pi;
  Dcl-S index Int(10);
  Dcl-S current Pointer;
  index = hashFunction(key);
  current = hashArray(index);
  While current <> *Null;
    If current->key = key;
      Return current->value;
    EndIf;
    current = current->next;
  EndWhile;
  Return *Blanks;
End-Proc;

Solució a l'Exercici 2

Dcl-S queue Pointer;
Dcl-S queueSize Int(10) Inz(10);
Dcl-S queueArray Char(50) Dim(queueSize);
Dcl-S front Int(10) Inz(0);
Dcl-S rear Int(10) Inz(0);

Dcl-Proc enqueue;
  Dcl-Pi *N;
    value Char(50);
  End-Pi;
  If (rear + 1) % queueSize <> front;
    queueArray(rear) = value;
    rear = (rear + 1) % queueSize;
  Else;
    // Gestió d'errors: cua plena
  EndIf;
End-Proc;

Dcl-Proc dequeue;
  Dcl-Pi Char(50);
  End-Pi;
  Dcl-S value Char(50);
  If front <> rear;
    value = queueArray(front);
    front = (front + 1) % queueSize;
  Else;
    // Gestió d'errors: cua buida
  EndIf;
  Return value;
End-Proc;

Solució a l'Exercici 3

Dcl-S stack Pointer;
Dcl-S stackSize Int(10) Inz(10);
Dcl-S stackArray Char(50) Dim(stackSize);
Dcl-S top Int(10) Inz(-1);

Dcl-Proc push;
  Dcl-Pi *N;
    value Char(50);
  End-Pi;
  If top < stackSize - 1;
    top += 1;
    stackArray(top) = value;
  Else;
    stackSize *= 2;
    Realloc(stackArray: stackSize);
    top += 1;
    stackArray(top) = value;
  EndIf;
End-Proc;

Dcl-Proc pop;
  Dcl-Pi Char(50);
  End-Pi;
  Dcl-S value Char(50);
  If top >= 0;
    value = stackArray(top);
    top -= 1;
  Else;
    // Gestió d'errors: pila buida
  EndIf;
  Return value;
End-Proc;

Solució a l'Exercici 4

Dcl-DS TreeNode;
  value Char(50);
  left Pointer;
  right Pointer;
End-DS;

Dcl-S root Pointer;

Dcl-Proc insertNode;
  Dcl-Pi *N;
    node Pointer;
    value Char(50);
  End-Pi;
  If node = *Null;
    node = %Alloc(Size(TreeNode));
    node->value = value;
    node->left = *Null;
    node->right = *Null;
  ElseIf value < node->value;
    insertNode(node->left: value);
  Else;
    insertNode(node->right: value);
  EndIf;
End-Proc;

Dcl-Proc deleteNode;
  Dcl-Pi *N;
    node Pointer;
    value Char(50);
  End-Pi;
  // Implementació de la funció d'eliminació
End-Proc;

Dcl-Proc searchNode;
  Dcl-Pi Pointer;
    node Pointer;
    value Char(50);
  End-Pi;
  If node = *Null Or node->value = value;
    Return node;
  ElseIf value < node->value;
    Return searchNode(node->left: value);
  Else;
    Return searchNode(node->right: value);
  EndIf;
End-Proc;

Conclusió

En aquest mòdul, hem après sobre diverses estructures de dades avançades com les taules de hash, les cues, les piles i els arbres binaris. Hem vist com implementar aquestes estructures en RPG i hem practicat amb exercicis pràctics. Aquestes estructures de dades són fonamentals per a la creació de programes eficients i escalables. En el proper mòdul, explorarem RPG IV i les seves característiques avançades.

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