unidad 4. arreglos y cadenasmtovar/doc/unidad4.pdf · 2009. 11. 10. · arreglos unidimensionales...

Unidad 4. Arreglos y Cadenas

l Definición de Arreglo:¡Un arreglo es un conjunto finito e indexado de elementos homogéneos, que se referencian por un identificador común (nombre). La propiedad indexado significa que el elemento primero, segundo, hasta el n-ésimo de un arreglo pueden ser identificados por su ésimo de un arreglo pueden ser identificados por su posición ordinal.

¡Un arreglo es una colección finita, homogénea y ordenada de elementos del mismo tipo.

¡De manera formal se define un arreglo de tamaño n de los elementos de tipo A, es un elemento del espacio n-dimensional del conjunto A, es decir, X es arreglo de tamaño n del tipo A si y solo si n

l Ambas definiciones reconocen los siguientes conceptos:l Finita: Todo arreglo tiene un límite, es decir, debe

determinarse cual será el número máximo de elementos que podrán formar parte del arreglo.

l Homogénea: Todos los elementos de un arreglo son del mismo tipo o naturaleza (todos enteros, todos

l Homogénea: Todos los elementos de un arreglo son del mismo tipo o naturaleza (todos enteros, todos booleanos, etc,), pero nunca una combinación de distintos tipos.

l Ordenada: Se debe determinar cuál es el primer elemento, el segundo, el tercero..... y el n-ésimo elemento.

Clasificación de los arreglos.

lLos arreglos se clasifican en:lUnidimensionales (Vectores): un sólo índice

lBidimensionales (Tablas o Matrices): dos lBidimensionales (Tablas o Matrices): dos índices

lMultidimensionales: más de dos índices

Arreglos unidimensionales

l Los arreglos unidimensionales deben cumplir lo siguiente: ¡Compuesto por un número de elementos finito.¡Tamaño fijo: el tamaño del arreglo debe ser conocido en tiempo de compilación. tiempo de compilación.

¡Homogéneo: todos los elementos son del mismo tipo.¡Son almacenados en posiciones contiguas de memoria, cada uno de los cuales se les puede acceder directamente.

¡Cada elemento se puede procesar como si fuese una variable simple ocupando una posición de memoria.

notación:

l Identificador_Arreglo= ARREGLO [Lim_inf..Lim_sup] DE tipo_dato

l Donde¡ Identificador_Arreglo: Es el nombre del arreglo para reconocer

a los elementos.¡ Lim_inf: es el primer elemento del arreglo¡ Lim_inf: es el primer elemento del arreglo¡ Lim_sup:es el último elemento del arreglo, para definir el

número de elementos que tendrá el arreglo¡ Tipo_dato: se declara el tipo de datos para todos los elementos

del arreglo.l Ejemplos definiciones del arreglo:

¡ A=ARREGLO [1..5] DE enteros¡ NÚMEROS=ARREGLO[1..4] DE reales ¡ LETRAS=ARREGLO[1..3] DE caracteres

Operaciones con Arreglos Unidimensionales.

lAsignaciónlLectura lEscrituraRecorridolRecorrido

lActualización (insertar, borrar, modificar)lOrdenaciónlBúsqueda

Asignaciónl En general no es posible asignar directa un valor a todo

el arreglo, sino que se debe asignar el valor deseado a cada elemento. La manera de asignar (insertar) un valor en cada elemento del arreglo unidimensional es mediante el subíndice que indica la posición, se puede utilizar la siguiente forma:mediante el subíndice que indica la posición, se puede utilizar la siguiente forma:

l <NombreVector>[subíndice] <Valor>l Ejemplos:l A[1]<- 10l PAIS[2] <- “Francia”l Numeros[10]<- 10.4l PRECIO[3] <- PRECIO[2]+10.5

Lectura

Para i <- 1 hasta N incremento 1 Hasta N hacerLeer ARREGLO[i]

Fin_Para

Problemas

l Algoritmo que presente el minimo y el maximo de un arreglo de tamaño N.

l Algoritmo que sume los cuadrados de los elementos almacenados en un arreglo

l Algoritmo que determine cuantos datos l Algoritmo que determine cuantos datos almacenados en un arreglo son pares y cuantos impares .

l Algoritmo que obtenga el producto punto de dos vectores.

l Algoritmo que obtenga la norma de un vector

Búsqueda secuencial

l A este método también se le conoce como búsqueda lineal y consiste en empezar al inicio del conjunto de elementos , e ir a través de ellos hasta encontrar el elemento indicado ó hasta llegar al final de arreglo.hasta llegar al final de arreglo.

l Este es el método de búsqueda más lento, pero si nuestro arreglo se encuentra completamente desordenado es el único que nos podrá ayudar a encontrar el dato que buscamos.

l Comparar uno a uno los elementos el arreglo (de tamaño N) hasta encontrar el deseado.

l Existen dos condiciones que ponen fin a la búsqueda.l 1. Se encuentra el elementol 2. Se ha rastreado toda la colección y no se encuentra ell 2. Se ha rastreado toda la colección y no se encuentra ell elemento

l Si i al final es N entonces el elemento no fue encontrado, pero sino

l entonces quiere decir que el elemento esta en la posición i-ésima del

Algoritmo: búsqueda_linealVariables: i, N, elemento Tipo EnteroInicio

A=ARREGLO [1..N] DE enterosEscribir “Escribe los valores del arreglo:” Para i=1 hasta N incremento 1 hacer

Leer a[i]Fin_ParaEscribir “Escribe el número a buscar en el arreglo”Leer elementoi ß 1Mientras (i< N) y (a[i] <> elemento) hacerMientras (i< N) y (a[i] <> elemento) hacer

i ß i+1Fin_mientrasSi (a[i] = elemento) entonces

Escribir “Numero encontrado en la pos ” iSino

Escribir “Número no encontrado ”Fin_si

Fin

lBuscar x = 3

0 3 5 9 15 30 40L=1 R=7 M= 4 Enc =F0 3 5 9 15 30 40L=1 R=4 M= 5/2 =2 Enc =T0 3 5 9 15 30 40

lBuscar x=400 3 5 9 15 30 40L=1 R=7 M= 4 Enc =F0 3 5 9 15 30 400 3 5 9 15 30 40L=5 R=7 M= 12/2 =6 Enc =F

0 3 5 9 15 30 40L=7 R=7 M= 14/2 =7 Enc =T

0 3 5 9 15 30 40

Algoritmo: búsqueda binaria

InicioL <- 1R <- NFound <- falseMientras (L< R y no (found)) hacer

M <- (L+R) div 2M <- (L+R) div 2Si a[m]=x entonces

found <- trueSino

si a[m] < x entonces L <- m+1Sino R <- m

Fin_siFin_mientrasFin

Ordenamiento, ejemplo 1

i=1 i=2 i=3 i=4 i=5 i=6

8 0 0 0 0 0 0

1 8 1 1 1 1 1

0 1 8 3 3 3 30 1 8 3 3 3 3

3 3 3 8 5 5 5

10 5 5 5 8 7 7

7 10 7 7 7 8 8

5 7 10 10 10 10 10

Ordenamiento, ejemplo 2

i=1 i=2 i=3 i=4 i=5 i=6

8 0 0 0 0 0 0

5 8 1 1 1 1 1

4 5 8 2 2 2 24 5 8 2 2 2 2

3 4 5 8 3 3 3

2 3 4 5 8 4 4

1 2 3 4 5 8 5

0 1 2 3 4 5 8

BurbujaInicio

Para i <- 1 hasta n-1 incremento 1 hacerPara j <- n hasta i+1 decremento 1 hacer

Si A[ j ] < A[ j-1] entoncesTemp = A[ j ]Temp = A[ j ]A[ j ] = A[ j-1]A[ j-1] = Temp

Fin_si

Fin_paraFin_para

Fin

Selección

l Este método se basa en los siguientes principios:

1. Seleccionar el elemento que tenga la llave menormenor

2. Intercambiarlo con el primer elemento a[1]3. Repetir después estas operaciones con los n-1

elementos restantes, luego con n-2 elementos hasta que no quede más que un elemento (el más grande)

i=1 i=2 i=3 i=4 i=5 i=6

8 X=8K=1

8 0 0 0 0 0 0

1 X=1K=2

1 X=1K=2

1 1 1 1 1

0 X=0K=3

0 8 8 X=8K=3

8 3 3 3 3

3 3 3 X=3 3 8=x 8 5 5 53 3 3 X=3K=4

3 8=x K=4

8 5 5 5

10 10 10 10 10 X=10K=5

10 7 7

7 7 7 7 X=7 k=6

7 X=7K=6

7 10X=10K=6

10

5 5 5 5 X=5K=7

5 8 8 x=8K=7

8

Algoritmo de selecciónInicio

Para i <- 1 hasta n-1 incremento 1 hacerK <- i X <- a[i]Para j <- i+1 hasta n incremento 1 hacer

If a[j] < x entoncesK <- j K <- j X <- a[k]

fin_sifin_paraa[k] <- a[i] a[i] <- x

fin_parafin