Tema 6

Tema 6

Estructura de datos estáticos

Tipos definidos por el usuario
En pocas ocasiones, los tipos que ofrece un lenguaje de programación como tipos predefinidos, se le quedan cortos al programador para almacenar en ellos las información que tiene que manejar.
Los lenguajes de programación ofrecen mecanismos para que el programador pueda definirse tipos.
Concretamente, es raro que un lenguaje de programación no ofrezca la posibilidad de hacer uso de:
- vectores.
- registros.

Definición de tipos
Antes de declarar una variable de un tipo de datos definido por el usuario, será necesario declarar el tipo de datos en cuestión. Hay lenguajes de programación (C por ejemplo) donde esto no es necesario.
Una vez declarado un tipo de datos nuevos, podemos declarar variables de ese tipo y usarlas posteriormente en el algoritmo.

Estructura de un algoritmo
algoritmo ejemplo
{comentarios}
"Declaración de constantes"
"Declaración de tipos"
"Declaración de variables"
Principio
     "instrucción 1"
     "instrucción 2"
             ..
     "instrucción n"
fin

Vectores
Un vector es un tipo de datos que nos permite guardar una secuencia de datos de un tipo determinado.
Hay problemas en los que tengo que guardar una secuencia de datos de un mismo tipo y donde el orden podría ser importante, incluso el poder acceder directamente a un elemento determinado de una secuencia.
Por ejemplo, yo con lo que conozco hasta ahora no podría resolver un problema como este: "Pedir una secuencia de enteros por teclado terminada en 0 (de longitud desconocida pero finita y acotable), e invertirla mostrando por pantalla la secuencia en orden inverso". Disponía hasta ahora de variables enteras, pero no de una forma de poder almacenar 20, 50 o 100 enteros y poderlos manipular posteriormente a mi antojo.
Otro ejemplo podría ser el siguiente:"Contar el número de apariciones de cada letra de alfabeto de un texto que es introducible una sola vez en el computador"

Vectores: definición formal
Un vector v, es una aplicación de un conjunto finito I e valores escalares, ordenados y consecutivos, denominado conjunto de índices del vector, en otro conjunto D de datos variables de un mismo tipo, conjunto de base del vector.
Los valores escalares del conjunto I, podrían ser de un tipo entero, carácter, o definido por enumeración. Se puede poner el tipo completo (si es definido por enumeración) o un subrango.
El tipo de datos para los datos variables, podría ser cualquiera.
En los ejemplos:
- vector[1..15] de ral;
- vector ['A'...'Z'] de entero;
- vector [tipo-días] de carácter; (siendo tipo_días=(lunes, martes, miercoles, jueves, viernes, sabado, domingo);)

Definición de vectores
algoritmo vectores
tipos
     vector_reales=vector[1..20] de real;
     vector_frecuencias= vector ['a'..'z'] de entero;
variables
     v: vector_reales;
     w: vector_reales;
     f: vector_frecuencias;
principio
     ...
fin

Uso de vectores
Una variable de tipo vector es una estructura de datos conpuesta de un número fijo de componentes del tipo de datos del vector.
Cada comopnente puede denotarse explícitamente y puede accederse a su valor, escribiendo el nombre de la variable del tipo vector, seguido del valor de su índice, encerrado entre corchetes:
- <nombre_vector>[<expresión>]
- La evaluación de <expresión> da como resultado el valor índice del elemento considerado.
Una componente de un valor, puede usarse exactamente igual que una variable de ese mismo tipo, y puede aparecer en cualquier expresión del mismo modo.
Ejemplos:
- v[17]:=1;
- w[i]:=w[i+1]+1;
- f['a']:=f['b']+f[chr(ord('c')+9)]-7;
- si (v[i]>v[i+1]) entonces...

Vectores: representación interna
La representación interna de un dato de tipo vector, se realiza de forma contigua en memoria, es decir, representando una tras otra todas las componentes del vector.
Por consiguiente, lo que el vector ocupará en memoria dependerá del tipo del que sean las componentes y del número de componentes.
El tiempo de acceso a cualquiera de las componentes será lógicamente el mismo, y podemos acceder directamente a la componente que nos interese.

Vectores: operaciones
Asignación
- Al igual que con cualquier variable podemos asignarle a un vector otro vector que sea exactamente del mismo tipo.
- El resultado de la instrucción es la asignación, a todas y cada una de las componentes del vector del lado izquierdo, de todos los valores de las componentes del vector del lado derecho.
Recorrido del vector
para indice:=<valor incial> hasta <valor final> hacer
     <accion afectado a la componente indice>
fpara

Ejemplo
algoritmo invertir_secuencia
{Algoritmo que lee una secuencia de datos de tipo entero, terminada con un cero, y la escribe en orden inverso (la secuencia es de longitud menor que 1000}
constantes
     N=1000;
tipos
     tvec=vector [1..N] de entero;
variables
     v: tvec;
     cont, numero, i:entero;
principio
     cont:=0;
     leerEntero(teclado, numero);
     mientras que numero <>0 hacer
          cont:=cont+1;
          v[cont]:=numero;
          leerEntero(teclado, numero);
    fmq
    para i:=cont descendiendo hasta 1 hacer
          escribirEntero(pantalla, v[i]);
    fpara
fin

Ejercicios
Escribe un procedimiento que lea de teclado una secuencia de N caracteres y los alcacene en el vector secuencia de tipo tsec. N y secuencia son parámetros del procedimiento:
constante maxN=1000; {máxima longitud de la secuencia}
tipo tsec=vector[1...maxN] de carácter;
procedimiento leer_secuencia(E N: entero, S secuencia: tsec)
Escribe un procedimiento que escriba por pantalla los N primeros elementos del vector secuencia:
procedimiento escribir_secuencia (E N: entero, E secuencia: tsec)