Estructura de Datos - Arreglos y Registros

 

ESTRUCTURA DE DATOS

            Niklaus Wirth, inventor del lenguaje de programación PASCAL, planteo la siguiente ecuación:

Algoritmos + Estructuras de Datos = Programas

            En la que indica que un programa se obtiene tras el diseño correcto de un algoritmo y la elección adecuada de la estructura de datos.      

Una estructura de datos, es una colección de datos organizados (lógicamente) de un modo particular con el objetivo de facilitar su manipulación. Cada estructura ofrece ventajas y desventajas en relación a la simplicidad y eficiencia para la realización de cada operación. De esta forma, la elección de la estructura de datos apropiada para cada problema depende de factores como la frecuencia y el orden en que se realiza cada operación sobre los datos.

Las estructuras de datos pueden ser de dos tipos: estructura de datos estáticas y estructura de datos dinámicas:

·         Estáticas: son aquellas en las que se asigna una cantidad fija de memoria cuando se declara la estructura. Es decir, su tamaño en memoria no pueden aumentar ni reducirse  mientras que el programa se encuentra en ejecución.

·         Dinámicas: son aquellas cuya ocupación en memoria puede aumentar y disminuir en tiempo de ejecución.

El siguiente esquema muestra las diferentes estructuras de datos que se estudiaran a lo largo de la asignatura:

LOS ARRAYS

            Es una estructura de datos en la que se almacena una colección de datos del mismo tipo (por ejemplo, los salarios de los empleados de una empresa). Es decir, un array es una lista de un número finito N de elementos del mimo tipo que se caracteriza por:

1. Todos los elementos son Homogéneos, es decir, de un mismo tipo de dato.
2. Los elementos del array se almacenan en posiciones de memoria continua.
3. Posee un nombre, que representa a todos los elementos de la estructura.
4. Cada elemento dentro de la estructura se encuentran diferenciado por un índice o subíndice.
5. La estructura permite acceso directo o aleatorio a los elementos individuales del arreglo.

Los array se clasifican en Unidimensionales (Vectores o listas) y Multidimensionales (tablas o matrices)

ARRAY UNIDIMENSIONALES

            Un array de una dimensión (vector o lista), es una estructura de datos compuesta de un número finito de elementos, tamaño fijo y elementos homogéneos. Finito indica que hay un primer y último elemento, tamaño fijo significa que el tamaño del array debe ser conocido en tiempo de compilación, homogéneo significa que todos los elementos son del mismo tipo. Los elementos del array se almacenan en posiciones continuas de memoria, a cada una de las cuales se puede acceder directamente.

Ejemplo 1: Suponga que se desea almacenar en un vector de nombre NOTAS, las calificaciones de 10 estudiantes de un examen de algorítmica. La representación grafica del arreglo unidimensional seria:

En donde:

• notas: representa el nombre del arreglos
• [1], [3], [7]…: representan los índices o subíndices del arreglo empleados para accesar a cada posición.
• contenido: notas[4] = 100

Ejemplo 2: Dibujar un vector de 5 posiciones para almacenar valores reales.

DECLARACIÓN DE UN ARREGLO UNIDIMENSIONAL

            Para declarar un vector en pascal, se empleará el siguiente formato:

            En donde:

• nombre: es un identificador valido.
• tipo_dato: representa algunos de los tipos de datos de PASCAL, estos se resumen en la siguiente tabla:

Tipos de Datos
Algorítmica	PASCAL
Alfanuméricos	string
Numéricos Enteros	integer
Numéricos Real	real
Carácter	char
Lógicos (verdadero, Falso)	Boolean (trae, false)

• 1..N: indica el tamaño del arreglo. Si se quiere declarar un arreglo de 10 posiciones se cambiaria la N por 10.
• nombreVariableArreglo: representa la variable de tipo arreglo, es decir, esta es la que utilizará en el programa para manipular la estructura.

Ejemplo 3: La declaración del arreglo NOTAS de 10 posiciones del Ejemplo 1 seria:

 Ejemplo 4: La declaración del arreglo NÚMEROS de 5 posiciones del Ejemplo 2 seria:

OPERACIONES SOBRE ARREGLOS UNIDIMENSIONALES

            Las operaciones básicas  que se pueden realizar con los arreglos Unidimensionales al igual que con los Multidimensionales son:

1.    Lectura de un Vector

2.    Escritura de un Vector

3.    Copia de un Vector

4.    Búsqueda en un Vector

5.    Ordenar un Vector

1. Lectura de un Vector

            Como un vector esta conformado por finitos elementos, la lectura no puede realizarse en una sola operación o sentencia, ya que debe hacerse elemento a elemento.

            La carga o lectura de un vector se puede hacer de dos formas:

1. Por asignación
2. Utilizando Ciclos Repetitivos.

Lectura por Asignación

            Suponga que se quiere almacenar en el un vector las estaturas de 100 concursantes del Miss Venezuela.

            La declaración del vector seria:

            La carga por asignación, consiste en ir asignando a cada posición del vector Estaturas, el valor correspondiente tal y como sigue:

            De todo lo anterior se puede concluir que:

• La carga por asignación es deficiente
• La sintaxis para cargar un vector por asignación es:

Lectura utilizando Ciclos Repetitivos

En algorítmica se aprendió que un ciclo es una estructura que permite repetir un conjunto de sentencias basadas en una condición.

La carga de un vector se puede realizar implementando los ciclos Mientras, Repita – Hasta o el ciclo Para.

Siguiendo con el ejemplo anterior, en el que se desea almacenar en un vector las estaturas de 100 concursantes del Miss Venezuela; la carga con ciclos seria:

En resumen, la cargar de un vector utilizando ciclos repetitivos puede seguir uno de los formatos siguientes:

2. Escritura de un Vector

La escritura posee la misma sintaxis que la carga, con la diferencia que se sustituye la operación de leer por escribir o imprimir.

Al igual que la carga, la escritura de un vector se puede hacerse con o sin el uso de ciclos. Por ejemplo: si se quiere imprimir el vector Estaturas, del ejemplo anterior, la solución seria:

3. Copia de un Vector

            Una operación que se suele dar en ocasiones es la copia de los elementos de un vector en otro vector, para ellos ambos vectores deben de ser del mismo tipo de dato.

 Supongamos por ejemplo, que los vectores Alfa y Beta se declaran como sigue:

Si el vector Alfa tiene valores cargados, estos se pueden copiar en el vector Beta por la siguiente sentencia:

            Otra forma de copiar vectores es por medio de la asignación. Por ejemplo, la siguiente instrucción Beta:=Alfa. Esta técnica es completamente valida siempre y cuando ambos vectores tienen el mismo tamaño y tipo de dato.

 

4. Búsqueda en un vector

            Esta operación es muy utilizada con los arreglos. El método consiste es recorrer la estructura de la posición 1 a la N, e ir comparando (utilizando el condicional SI  - ENTONCES - SINO) cada valor de cada posición del arreglo con el dato a buscar. Las operaciones a realizar una vez que el dato es encontrado van a dependen del problema.

A continuación se muestran algunos ejemplos en los que se aplica el método:

Ejemplo 5: En un arreglo de nombre EDADES se almaceno las edades de 50 personas, mostrar las posiciones del arreglo en las que se encuentran las edades iguales a 20. El código seria:

Ejemplo 6: Suponga que se tiene el arreglo NOTAS con las calificaciones de 1500 estudiantes, se desea conocer la cantidad de alumnos aprobados y reprobados. El código seria:

Ejemplo 7: Dado un arreglo de 2000 posiciones que almacena los sueldos de empleados, determinar cual es el sueldo mayor. El código seria:

5. Ordenar un Vector

            Antes de conocer los diferentes algoritmos para ordenar un vector, es necesario conocer que es ordenación.

La ordenación es una operación consistente en disponer un conjunto de datos en algún determinado orden con respecto a uno de los campos que conforman el conjunto. Por ejemplo, cada elemento del conjunto de datos de un guía telefónica tiene un campo nombre, un campo dirección y un camp numero de teléfono; la guía telefónica esta dispuesta en orden alfabético de nombres. Los elementos numéricos se pueden ordenar en orden creciente o decreciente de acuerdo al valor numérico del elemento.

            Cuando los elementos a ordenar están en memoria principal (RAM) se habla de ordenamiento interno, en cambio si se encuentran en memoria secundaria (disco, cinta, cilindro magnético, etc) se habla de ordenamiento externo.

 Existen muchos algoritmos de ordenación interna entre los cuales se destacan:

1. Ordenación por Burbuja.
2. Ordenación por selección
3. Ordenación por inserción
4. Ordenación Shell
5. Ordenación rápida (Quicksort)
6. Ordenación por mezcla (mergesort)
7. Ordenación Heapsort
8. Ordenación BinSort
9. Ordenación Radix Sort

NOTA: se deja a investigación del alumno la descripción y funcionamiento de cada uno de los algoritmos.

ARRAY PARALELOS

            Partiendo del hecho de que los arreglos son homogéneos, ¿cual es la estructura de datos correcta? para almacenar la siguiente información: nombres y las notas de 10 estudiantes. La respuesta correcta es arreglos paralelos. 

            Los arreglos paralelos, son dos o más arreglos donde los valores pertenecientes a la misma posición en diferentes arreglos se relacionan entre si. Por ejemplo, suponga que se quiere almacenar en arreglos los nombres, edades y sueldos de 10 empleados. Es lógico que la información se debe de almacenar en 3 arreglos paralelos tal y como se indica a continuación:

  

            Para declarar los vectores paralelos se utiliza el mismo formato que para los arreglos unidimensionales. La declaración de los vectores nombres, edades y sueldos serian:

            De igual forma, los arreglos paralelos nombres, edades y sueldos se pueden cargar e imprimir tal se muestra a continuación:

           

ARRAY MULTIDIMENSIONALES

Son estructuras de datos que están compuestas por más de una dimensión. Se clasifican de acuerdo al número de índices o dimensiones en bidimensionales o multidimensionales.

 Los arreglos bidimensionales (tabla o matriz), es un array con dos índices. El primero indica la cantidad de filas y el segundo la cantidad de columnas. Para almacenar o localizar un valor en el array se deben especificar dos posiciones o subíndices (fila, columna).

Ejemplo 8: representar gráficamente una matriz de 4 x 3. Indicando todos sus elementos

DECLARACIÓN DE UN ARREGLO BIDIMENSIONAL

Para declarar una matriz en pascal, se empleará el siguiente formato:

La declaración de la matriz Números, seria:

OPERACIONES SOBRE ARREGLOS BIDIMENSIONALES

            Las operaciones sobre matrices son similares a las de los vectores, con la diferencia de que utilizan dos ciclos repetitivos. Es decir, uno que manipula las fila y otro las columnas.

1. Carga y escritura de una Matriz

NOTA: los formatos de carga y escritura con los mientras y repita se dejan a investigación del alumno.

REGISTROS (RECORD)

            Es un tipo de dato estructurado que consta de un conjunto de elementos que pueden ser del mismo tipo o de tipos diferentes.

            Los componentes de un registro se denominan campos. Cada campo tiene un nombre llamado identificador (nombre) de campo y un tipo de dato que indica la información a almacenar.

Es un tipo de dato estructurado formado por la unión de varios elementos bajo una misma estructura. Estos elementos pueden ser, o bien datos elementales (entero, real, carácter, otros), o bien otras estructuras de datos. A cada uno de esos elementos se le llama campo.

Un registro se diferencia de un vector en que éste es una colección de datos iguales, es decir, todos del mismo tipo, mientras que en registro los elementos que la componen, aunque podrían serlo, no tiene porque ser del mismo tipo.

Ejemplo 9: Representar gráficamente el registro EMPLEADO, formado por cuatro campos (nombre, edad, domicilio y salario)

DECLARACIÓN DE UN REGISTRO

            El siguiente es el formato para declarar un registro:

            En donde:

• nombreX: es un identificador valido
• campo 1, campo 2, campo n: son los nombres de cada uno de los campos que componen al registro
• tipo_dato: representa alguno de los tipos de datos de pascal.
• nombreVariableRegistro: representa la variable de tipo registro, es decir, esta es la que se utilizara en el programa para manipular la estructura

Ejemplo 10: Declarar el registro EMPLEADO, formado por cuatro campos (nombre, edad, domicilio y salario)

OPERACIONES SOBRE LOS REGISTRO

1. Acceso a los campos de un registro

            Para acceder a los campos de un registro se emplea el siguiente formato:

2. Carga y Escritura de un Registro

            La carga de un registro implica accesar a todos los campos de registro y almacenar información en ellos. Ejemplo: si se quiere asignar valores al registro EMPLEADO declarado anteriormente, las sentencias serian:

Otra forma de cargar el registro EMPLEADO es mediante la sentencia Leer:

           

Para escribir un registro simplemente se utiliza la sentencia Escribir tal y como aparece a continuación:

3. Asignación de un Registro

            Otra operación que se puede realizar entre registro es la asignación, es decir, copia del contenido de un registro en otro registro del mismo tipo. Ejemplo: si A y D son dos variables registro del mismo tipo, la sentencia

            A := D, Copia los valores asociados con el registro D al Registro A.

Ejemplo 11: Asignación de registros

            La sentencia de asignación de registros:

REGISTROS JERÁRQUICOS (ANIDADOS)

Es un registro en el que por lo menos unos de sus campos es también un registro. Su representación grafica es en forma de árbol.

Suponga el siguiente registro anidado empleado:

            La declaración del registro anidado Empleados es la siguiente:

 

Acceso a los Registros Anidados

            Para referenciar un campo en registros anidados se debe indicar el camino a seguir en orden jerárquico desde el nombre de la variable del registro raíz hasta el campo específico. Ejemplos:

ARREGLOS DE REGISTROS

            Los registros se utilizan raramente por sí mismos. En general se agrupan en conjuntos conocidos como arrays de registros. Por ejemplo, se dispone de un registro que contiene los datos relativos a un artículo de un stock de almacén.

            De esta manera, la Articulo solo puede almacenar la información de UN SOLO ARTICULO. Si el inventario dispone de 100 artículos y se desean procesar adecuadamente, se puede utilizar un array de registro de 100 elementos; mediante la siguiente declaración se declara el arreglo Inventario:

            Una vez declarado el arreglo de registro se puede acceder a cada registro a través de los campos de cada registro. Así, por ejemplo, la lista completa del inventario se puede leer con el siguiente segmento de código:

            En conclusión:

• Para declarar un arreglo de registro, primero se declara el registro y luego el arreglo del tipo registro.
• Las operaciones sobre arreglos de registros son las mismas que para todos los arrays, con la salvedad que cada posición del arreglos está formada por el conjunto de campos del registro, y se debe acceder empleando el siguiente formato:

Ejemplo 12 (Tipo Examen):

Suponga que se desea almacenar de 1500 personas la siguiente información: cedula, nombre, edad, sexo (M-masculino, F-femenino) y sueldo. Se pide:

1. Declarar y cargar la estructura de Datos a Utilizar
2. Promedio general de edades
3. Cantidad de hombres y mujeres
4. Mostrar la cedula, nombre y edad de las personas que ganen más de Bs. 2500.

Creador: Ing. Laur Vanegas

Descarga