Arreglos


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 posición ordinal.
Un arreglo es una colección finita,
homogénea y ordenada de elementos del
mismo tipo.
90

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 XAn.
91

Ambas definiciones reconocen los siguientes
conceptos:
◦ 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.
◦ 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.
◦ Ordenada: Se debe determinar cuál es el primer
elemento, el segundo, el tercero..... y el n-ésimo
elemento.
92




Tienen un único nombre de variable, que
representa todos los elementos.
Contienen un índice, los cuales diferencian
a cada elemento del arreglo.
Se pueden realizar ciertas operaciones como
son: recorridos, ordenaciones y búsquedas de
elementos.
El número total de elementos del arreglo
(NTE) es igual al límite superior (LS), menos
límite inferior NTE = LS - LI + 1.
93




El tipo de índice puede ser cualquier tipo
ordinal.
El tipo de los componentes puede ser
cualquiera.
Se utilizan [ ] para indicar el índice de un
arreglo. Entre los [ ] se debe escribir un valor
ordinal (puede ser una variable, una
constante o una expresión que dé como
resultado un valor ordinal).
Si un arreglo tiene n componentes, la última
localidad está dada por n.
94
1
n
n elementos

Los arreglos pueden contener un mínimo de
cero elementos hasta un máximo de n
elementos.
95

A continuación se muestra un arreglo llamado
EDADES, que contiene las edades de la clase
de natación en la BUAP.
Límite inferior
16
17
Límite superior
EDADES
18
19
20
21
22
23
24
25
EDADES[3]
EDADES[1]
EDADES[5]
EDADES[9]
EDADES[7]
EDADES[6]
EDADES[4]
EDADES[2]
EDADES[8]
EDADES[10]
96

Los arreglos se clasifican en:
◦ Unidimensionales (Vectores): un sólo índice
◦ Bidimensionales (Tablas o Matrices): dos índices
◦ Multidimensionales: más de dos índices
97
Arreglos unidimensionales

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.
◦ 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.
99

Dado un arreglo unidimensional denominado
PRECIO cada uno de sus elementos se designará
por
ese
mismo
nombre
diferenciándose
únicamente por su correspondiente subíndice.
PRECIO
Longitud = 6
Nombre del arreglo
15.4
PRECIO[1]
12.5
PRECIO[2]
14.8
PRECIO[3]
9.7
PRECIO[4]
6.5
PRECIO[5]
4.5
PRECIO[6]
Índices
100

Asignación
◦ 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:
<NombreVector>[subíndice]  <Valor>

Ejemplo:
◦ A[1] 10
◦ PAIS[2]  ‘Francia’
◦ PRECIO[3]  PRECIO[2]+10.5
101

Lectura
◦ Este proceso de lectura de un arreglo consiste en leer un
valor de cada elemento del arreglo y asignarlo a una
variable. La lectura se realiza de la siguiente manera:
Para i  1 hasta N hacer
leer(ARREGLO[i])
Fin_Para

Escritura
◦ Consiste en asignarle un valor a cada elemento del
arreglo.
Para i 1 hasta N hacer
escribir(ARREGLO[i])
Fin_Para
102

Leer un arreglo de N precios y obtener el
promedio:
1.
2.
3.
4.
5.
6.
7.
8.
Inicio
Leer(n)
prom 0
Para i1 hasta n hacer
leer(precio[i])
promprom+precio[i]
Fin_para
promprom/n
Escribir(«El promedio es:»,prom)
Fin
103
Cadenas


Una cadena es un conjunto de caracteres
incluido el espacio en blanco.
Por ejemplo:
◦ “Hola”
◦ “123vb”
◦ “v bg%.”

Generalmente una cadena va encerrada entre
comillas.
105



La longitud de una cadena es el número de
caracteres que contiene.
La cadena vacía es la que no tiene ningún
carácter y se representa como “”.
Una constante de tipo cadena es un conjunto
de caracteres válidos encerrados entre
comillas, por ejemplo:
◦ “numero1”
◦ “&/ #$%”
106

Una variable de cadena es aquella cuyo
contenido es una cadena de caracteres, por
ejemplo:
◦ cadena=”una cadena”
◦ str=”-23.56”.

El último carácter de la cadena marca el fin de
la cadena, en este caso utilizaremos el
carácter ‘\0’ para denotar fin de cadena.
107
•
Asignación.
– Apellido”Juarez”
•
Entrada/ Salida
– Leer (nombre, estado_civil)
– Escribir (nombre, apellido)
•
•
Para el cálculo de la longitud de una cadena
se da el número de caracteres que hay en
una.
Para la comparación de cadenas se comparan
caracteres o para ver si son iguales o no.
108



La concatenación se define como la unión de
varias cadenas de caracteres en una sola,
conservando el orden.
La extracción de subcadenas es una
subcadena que es una porción de la cadena
original.
La búsqueda de información, consiste en
buscar una subcadena o cadena dentro de
otra mayor. Devuelve el número de la
posición donde inicia la subcadena buscada,
o -1 si no la encuentra.
109







Encontrar el punto medio, este nos devuelve
la mitad de la posición de la cadena.
Truncar cadenas, se pretende quedarse con
los primeros n caracteres de la cadena.
Convertir cadenas a números o viceversa, si
los caracteres son dígitos.
Insertar una cadena dentro de otra.
Borrar cadenas.
Sustituir una cadena por otra.
Invertir el orden de una cadena.
110

El siguiente algoritmo sustituye las ‘e’ por ‘*’.
1.
2.
3.
4.
Inicio
Escribir (“Escriba una palabra")
Leer (str)
Para i=1 hasta len(str) hacer
4.1 Si str[i] = `e´ entonces
str[i]  `*´
4.2 Fin_si
5. Fin_para
6. Escribir (str)
7. Fin
111

El siguiente algoritmo imprime una cadena de
manera invertida:
1.
2.
3.
4.
Inicio
Escribir (“Escriba una palabra")
Leer (str)
Para i=len(str) hasta 1, con decrementos hacer
4.1 Escribir (str[i])
5. Fin_para
6. Fin
112

El siguiente algoritmo realiza lo siguiente, dada
una cadena en minúsculas, la convierte en
mayúsculas
1.
2.
3.
4.
Inicio
Escribir ("Escriba una palabra")
Leer (str)
Para i=1 hasta len(str) hacer
4.1 Si ‘a’>=str[i]<=’z’ entonces
Valor(str[i]) Valor(str[i])-32
4.2 Fin_si
5. Fin_para
6. Escribir ("La cadena es:",str)
7. Fin
113
Ordenamiento


Uno de los métodos de clasificación más
simples que puede haber es el llamado
“clasificación de burbuja” (bubblesort).
La idea básica de este algoritmo es imaginar
que los elementos están como burbujas en
un
tanque
de
agua
con
pesos
correspondientes a sus claves, cada pase
sobre el arreglo produce el ascenso de una
burbuja hasta su nivel adecuado de peso.
115
Procedimiento burbuja
Inicio
Para i 1 a n-1 hacer
Para j  n a i+1 con decrementos de 1 hacer
Si A[j] < A[j-1] entonces
temp  A[j]
A[j]  A[j-1]
A[j-1]  temp
Fin_si
Fin_para
Fin_para
Fin
116



Este algoritmo admite un poco de
mejoramiento.
El algoritmo por vibración es una variante
del algoritmo burbuja pero mejorado.
Este algoritmo consiste en “recordar” cuál
fue el último intercambio realizado y en qué
momento.
117
Procedimiento shakeSort
Inicio
Para j l a r hacer
l2
r  n k n
Si A[j-1] > A[j] entonces
Repetir
temp  A[j]
Para jr a l decrementos 1 hacer
A[j]  A[j-1]
Si A[j-1] > A[j] entonces
A[j-1]  temp
temp  A[j]
kj
A[j]  A[j-1]
Fin_si
A[j-1]  temp
Fin_para
kj
r  k-1
Fin_si
Hasta l > r
Fin_para
Fin
l  k+1
118


Este método consiste en reubicar en el lugar
correcto cada uno de los elementos a ordenar, es
decir, en el i-ésimo recorrido se “inserta” el iésimo elemento A[i] en el lugar correcto, entre
A[1], A[2], ..., A[i-1], los cuales fueron ordenados
previamente.
Existen dos condiciones distintas que podrían
dar terminado el proceso de clasificación:
1. Se encuentra un elemento A[j] que tiene una llave
menor que la de A[i].
2. El extremo izquierdo de la secuencia destino es
alcanzado.
119
Procedimiento insercionDirecta
Inicio
Para i 2 a n hacer
A[0]A[i]
j i
Mientras A[j] < A[j-1] hacer
temp  A[j]
A[j]  A[j-1]
A[j-1]  temp
j  j-1
Fin_mientras
Fin_para
Fin
120



Si notamos que la secuencia destino
A[2]...A[i-1] donde se debe insertar el
elemento, ya está ordenada.
Este
algoritmo
puede
ser
mejorado
determinando rápidamente el punto de
inserción.
La elección es una búsqueda binaria que
prueba la secuencia destino en la mitad y
continúa buscando hasta encontrar el punto
de inserción.
121
Procedimiento insercionBinaria
Inicio
Para i 2 a n hacer
x A[i] L1
Ri
Mientras L < R hacer
m  (L+R) div 2
Si A[m] <= x entonces
L  L+1
Sino R  m
Fin_si
Fin_mientras
Para ji a R+1 (decremento en 1) hacer
A[j]  A[j-1]
Fin_para
A[R]  x
Fin_para
Fin
122

Este método se basa en los siguientes
principios:
1. Seleccionar el elemento que tenga la llave menor.
2. Intercambiarlo con el primer elemento 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).
123
Procedimiento selecciónDirecta
Inicio
Para i1 a n-1 hacer
k i
xA[i]
Para j  i+1 a n hacer
Si A[j] < x entonces
k j
x A[k]
fin_si
fin_para
A[k]  A[i] A[i]  x
fin_para
Fin
124

Inserción por decremento decreciente
◦ Un refinamiento de la inserción
propuesto por D.L. Shell en 1959.
directa
fue
125
Procedimiento shellSort
Inicio
h[1]9
h[2]5 h[3] 3 h[4] 1
Para m 1 a t hacer // t es el tamaño del arreglo h
k h[m]
sk
Para i  k+1 a n hacer
xA[i]
ji-k
Si s=0 entonces
sk
fin_si
ss+1
A[s]x
Mientras x<A[j] hacer
A[j+k]A[j] jj-k
fin_mientras
A[j+k]x
fin_para
fin_para
Fin
126
Búsqueda



La tarea de búsqueda es una de las más
frecuentes en programación.
Para los siguientes algoritmos vamos a
suponer que la colección de los datos en
donde vamos a buscar, es fija, y que es de
tamaño n.
La tarea consiste en hallar un elemento cuya
clave sea igual al argumento de búsqueda.
128


Cuando los elementos no llevan un orden y
no existe información sobre ellos se utiliza la
búsqueda lineal, es decir, comparar uno a
uno los elementos hasta encontrar el
deseado.
Existen dos condiciones que ponen fin a la
búsqueda.
◦ Se encuentra el elemento.
◦ Se ha rastreado toda la colección y no se encuentra
el elemento.
129
Procedimiento busquedaLineal (elemento)
Inicio
i1
Mientras (i <= N) y (A[i] <> elemento) hacer
ii+1
Fin_mientras
Fin

Si i al final es N entonces el elemento no fue
encontrado, pero sino entonces quiere decir
que el elemento esta en la posición i-ésima
del arreglo.
130


Para utilizar este algoritmo es necesario que
la colección este ordenada.
La idea clave consiste en inspeccionar el
elemento medio y compararlo con el
elemento de búsqueda x.
◦ Si es igual a x, la búsqueda termina; si es menor
que x, inferimos que todos los elementos con
índices menores que o iguales a m pueden ser
eliminados, y nuestra búsqueda ahora se centra en
los demás elementos.
◦ Esto se repite mientras el índice inicial sea menor o
igual que el final y el elemento no sea encontrado.
131
Procedimiento busquedaBinaria(x)
Inicio
L 0
RN
found  false
Mientras L< R y not (found) hacer
m(L+R) div 2
Si A[m]=x entonces
foundtrue
Sino
Si A[m] < x entonces L  m+1
Sino
R m
fin_si
fin_si
fin_mientras
Fin
132
Descargar

Arreglos y cadenas