PDF de programación - Tema 5 - Estructuras de datos: arrays y registros

Fundamentos de Programación I
Fundamentos de Programación I

Tema 5. Estructuras de datos:
arrays y registros

Luís Rodríguez Baena ([email protected])

Universidad Pontificia de Salamanca (campus Madrid)
Escuela Superior de Ingeniería y Arquitectura

1

Introducción a las estructuras de datos

Datos estructurados: colección de datos caracterizada por su
organización y las operaciones que se pueden realizar sobre
ella.

p

Están compuestos por otros tipos de datos más simples.
Están compuestos por otros tipos de datos más simples.
Según la forma de asignación de memoria:

● Estructuras de datos estáticas.

Reservan espacio de almacenamiento en tiempo de compilación
Reservan espacio de almacenamiento en tiempo de compilación.
Su tamaño y posición en memoria no cambian a lo largo de la ejecución

del programa.

● Estructuras de datos dinámicas.
Estructuras de datos dinámicas.

Reservan espacio de almacenamiento en tiempo de ejecución.
Su tamaño y posición en memoria pueden cambiar a lo largo de la

ejecución del programa.

Universidad Pontificia de Salamanca (Campus Madrid)

Luis Rodríguez Baena, Escuela Superior de Ingeniería y Arquitectura, 2011

2

2

Introducción a las estructuras de datos (II)

Datos estructurados

Estáticos

Dinámicos

Universidad Pontificia de Salamanca (Campus Madrid)

Luis Rodríguez Baena, Escuela Superior de Ingeniería y Arquitectura, 2011

Conjuntos

Arrays

Cadenas

Registros

Archivos

Lineales
(listas)

No lineales

Listas
Listas

enlazadas

Pilas

Colas

Árboles

Grafos

3

3

Arrays

Estructura de datos formada por un conjunto finito y ordenado de elementos

homogéneos
homogéneos.
● Elementos homogéneos: todos los elementos son del mismo tipo: el tipo base del

● Serie finita: tiene un tamaño limitado que habrá que definir en la declaración y que no

array.

puede cambiar.
puede ca b a

● Ordenado: cada elemento puede ser identificado por la posición que ocupa en la

estructura y ser tratado individualmente.

En todo caso, estarán ordenados por su posición dentro de la estructura.

Se trata de una estructura de acceso directo o aleatorio.

● Es posible acceder a cada elemento de forma individual.

Los elementos pueden seleccionarse arbitrariamente y son igualmente accesibles.
Para designar a un elemento se utilizará el selector.

o Uno o más índices que indican su posición dentro de la estructura.

● Dependiendo del número de índices necesario para referenciar un componente habrá:
● Dependiendo del número de índices necesario para referenciar un componente habrá:

Arrays unidimensionales (vectores).
Arrays bidimensionales (matrices)
Arrays multidimensionales.

Universidad Pontificia de Salamanca (Campus Madrid)

Luis Rodríguez Baena, Escuela Superior de Ingeniería y Arquitectura, 2011

4

4

Arrays unidimensionales: vectores

La referencia a un elemento de hace mediante un único

índice.
● Sería la repetición de una variable del tipo base del array.
¿Có
?
¿Cómo se pueden tratar de n datos homogéneos?

d t

h

d

t

t

d

é

● Solución 1: Utilizar una única variable y destruir el contenido anterior

en cada asignación.

No se puede recuperar la información.

● Solución 2: Utilizar n variables.

Impracticable.

● Solución 3: Utilizar un array de n elementos.

Repite un dato simple n veces.

Universidad Pontificia de Salamanca (Campus Madrid)

Luis Rodríguez Baena, Escuela Superior de Ingeniería y Arquitectura, 2011

5

5

Arrays unidimensionales: vectores (II)

Solución 2

Solución 3

Solución 1

Universidad Pontificia de Salamanca (Campus Madrid)

Luis Rodríguez Baena, Escuela Superior de Ingeniería y Arquitectura, 2011

6

6

Declaración de variables de tipo vector

En los tipos de datos estándar, el compilador ya conoce cómo

p

p

y

,

almacenar el dato en memoria y cómo interpretar su
contenido.

E l
En los arrays será necesario además decir cual es su tipo

á d i

ti

d

á

i

l

base, su número de elementos y cómo se hará referencia a
los componentes individuales.
● El compilador sabe lo que es un array, pero no sabe ni su tipo, ni su

número de elementos ni cómo se referenciará cada elemento.

Declaración:
Declaración:

var

array[limInf..limSup] de tipoBase : nombreArray

Universidad Pontificia de Salamanca (Campus Madrid)

Luis Rodríguez Baena, Escuela Superior de Ingeniería y Arquitectura, 2011

7

7

Declaración de variables de tipo vector (II)

tipoBase.

● Indicaría el tipo de dato de cada elemento del array.
● Puede ser cualquier tipo de dato estándar o definido por el usuario.

nombreArray.y

● Un identificador válido.

limInf..limSup.

● Doble función:
● Doble función:

Es un subrango con todos los valores posible que podrá tomar un índice de array.

o Los índices debe ser mayores o iguales a limInf y mayores o iguales a limSup.

Indica también el número de elementos del array: todos los valores posibles entre

los dos límites.

● Normalmente se tratará de valores enteros, pero en algunos lenguajes se

puede utilizar cualquier valor de tipo ordinal (como pueden ser los datos de
tipo carácter)
tipo carácter).

Universidad Pontificia de Salamanca (Campus Madrid)

Luis Rodríguez Baena, Escuela Superior de Ingeniería y Arquitectura, 2011

8

8

Declaración de variables de tipo vector
(III)
(III)

...
varvar

//Declara dos vectores con 6 elementos (entre 0 y 5) de tipo entero
array[0..5] de entero : números, otroVector
//Declara un vector de 20 elementos de tipo cadena
//Los índices podrán ir desde 1 hasta 20
array[1..20] de cadena : nombres
//Declara un vector de 6 elementos con las ventas
//realizadas entre los años 2000 y 2005.
//Los índices a utilizar para referenciar cada
//tomarán los valores de los años entre 2000 y 2005
array[2000..2005] de real : ventas

...
Operaciones con el vector.

p

● La única operación permitida con la estructura de datos es la asignación.
● Es posible asignar un array a otro siempre que sea del mismo tipo.

p

g

Mismo número de elementos, mismos límites y mismo tipo de datos.

...
//Asigna a números cada uno de los elementos de otroVector
números otroVector

9

Declaración de variables de tipo vector (IV)

En C la declaración de una variable de tipo array se hace siguiendo este

formato:
formato:
tipoDato nombreArray[númElementos]
● Hay que notar que entre corchetes no aparece ni el índice superior ni el índice

i

i

inferior, sino el número de elementos.

El í di
0
El índice inferior siempre es 0.
El índice superior sería númElementos-1.

i f

//Declara un array de enteros de 6 elementos.
//Los índices irán entre 0 y 5.
iint numeros[6];
//Declara un array 10 elementos de tipo cadena con índices entre 0 y 9
char *nombres[10];
//Declara un array de 6 elementos reales para las ventas entre el año 2005 y 2011
double ventas[6];

En C la asignación no se permite hacer asignación de arrays.

● La asignación otroVector = numeros sería errónea.

Universidad Pontificia de Salamanca (Campus Madrid)

Luis Rodríguez Baena, Escuela Superior de Ingeniería y Arquitectura, 2011

10

10

Referencia a los elementos de un vector

Cada elemento de un vector se identifica mediante su índice.

● Todos los elementos ocupan posiciones contiguas de memoria.
● Cada índice indica la posición del elemento dentro de la estructura.

Al ser todos los elementos del mismo tipo es posible acceder al elemento
Al ser todos los elementos del mismo tipo, es posible acceder al elemento

n.

o Si la variable de tipo array indica el comienzo de la estructura, para acceder al

elemento n habrá que saltar n-1 posiciones desde la posición inicial.

● El acceso a un elemento del vector se realizará mediante el selector.
El selector está formado por el nombre del array y su índice (su posición

dentro de la estructura) encerrado entre corchetes.

o números[2] hará referencia al segundo elemento del vector números

(dispositivas 6 y 9), es decir al valor entero 12.

Universidad Pontificia de Salamanca (Campus Madrid)

Luis Rodríguez Baena, Escuela Superior de Ingeniería y Arquitectura, 2011

11

11

Referencia a los elementos de un vector (II)

Cada elemento del vector es un dato del tipo base del mismo.

● números[2] será un dato de tipo entero.

Sobre él se podrá hacer cualquiera de las operaciones posibles con un número entero.

● Cualquiera de las siguientes operaciones se podrán hacer con los elementos de los

vectores declarado en la diapositiva 9
vectores declarado en la diapositiva 9.

...
números[4] 3
[4] + 1
números[1] números[4] + 1
ú
[1] ú
leer(números[3])
nombres[2] 'Pepe'
si nombres[2] > 'Juan' entonces
y
fin_si
//Llamada a la función Factorial desarrollada en el Tema 4
//La función Factorial precisa un argumento de tipo entero
//y números[5] es un dato de tipo entero
escribir(Factorial(números[5]))
[5]))
...

escribir(nombres[2], ' es mayor que Juan’

ibi (F t i l( ú

(

[ ],

q

Universidad Pontificia de Salamanca (Campus Madrid)

Luis Rodríguez Baena, Escuela Superior de Ingeniería y Arquitectura, 2011

12

12

Acceso secuencial al vector:
Recorrido

Un vector es una estructura repetitiva.

p

● Los elementos se tratarán mediante una estructura repetitiva.

El recorrido de un vector consiste en recorrer

consecutivamente (secuencialmente) todos sus elementos.
consecutivamente (secuencialmente) todos sus elementos.
● Se necesitará un contador que vaya tomando todos los valores

posibles del índice.

Lo más práctico es utilizar una estructura de tipo desde.

Para introducir por teclado todos los ele