Programación I
MC José Andrés Vázquez Flores
Definición
 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.
51
Definición
 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.
52
Representación
0
n-1
n elementos
 Los arreglos pueden contener un mínimo de cero
elementos hasta un máximo de n elementos.
53
Clasificación
 Los arreglos se clasifican en:
 Unidimensionales (Vectores): un sólo índice
 Bidimensionales (Tablas o Matrices): dos índices
 Multidimensionales: más de dos índices
54
Programación I
MC José Andrés Vázquez Flores
Características
 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.
56
Definición
 Para definir en lenguaje C un arreglo. Se tiene:
 Tipo nom_var[TAM];
 El arreglo que se define inicia en 0, y termina en
TAM-1, con un total de TAM elementos del tipo
definido
 Ejemplo:
 int A[100];
 float X[N];
57
Operaciones
 Asignación
 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] = 2.56;
 precio[3] = precio[2]+10.5;
58
Operaciones
 Lectura
 La lectura se realiza de la siguiente manera:
for (i=0; i<n; i++)
scanf(“%d ”, &A[i]);
 Escritura
 Consiste en asignarle un valor a cada elemento del
arreglo:
for (i=0; i<n; i++)
printf (“\n %d ”, A[i]);
59
Programación I
MC José Andrés Vázquez Flores
Conceptos Básicos
 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.
61
Conceptos Básicos
 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 “”.
 El último carácter de la cadena marca el fin de la
cadena, que corresponde al carácter ‘\0’.
 Este carácter ocupa un espacio en el arreglo.
62
Instrucciones
 Se hace uso de la biblioteca <string.h>.
 strcpy (cadena1, cadena2): Copia el contenido de
la cadena2 en la cadena1, si las dos cadenas se
superponen, el resultado es impredecible. La copia
se realiza aún cuando las cadenas no sean de la
misma longitud.
 strcat (cadena1, cadena2): Anexa la cadena2 al
final de la cadena1. El terminador nulo de cadena1
se reemplaza por el primer carácter de cadena2.
63
Instrucciones
 compara strcmp (cadena1, cadena2): Compara la
cadena1 con la cadena2, y devuelve:
 0
 entero mayor a cero
 entero menor a cero
si cadena1=cadena2
si cadena1>cadena2
si cadena1<cadena2
 tamaño strlen (cadena): Devuelve la longitud de
la cadena sin contar el terminador nulo.
64
Programación I
MC José Andrés Vázquez Flores
Clasificación por intercambio directo
 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.
66
Clasificación por intercambio directo
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
67
Clasificación por intercambio directo
 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.
68
Procedimiento shakeSort
Clasificación
por intercambio directo
Inicio
l2
rn
k n
Repetir
Para jr a l decrementos 1 hacer
Si A[j-1] > A[j] entonces
temp  A[j]
A[j]  A[j-1]
A[j-1]  temp
kj
Fin_si
Fin_para
l  k+1
Para j l a r hacer
Si A[j-1] > A[j] entonces
temp  A[j]
A[j]  A[j-1]
A[j-1]  temp
kj
Fin_si
Fin_para
r  k-1
Hasta l > r
Fin
69
Clasificación por inserción
 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.
2.
Se encuentra un elemento A[j] que tiene una llave menor
que la de A[i].
El extremo izquierdo de la secuencia destino es alcanzado.
70
Clasificación por inserción
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
71
Clasificación por inserción
 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.
72
Clasificación por inserción
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
73
Clasificación por selección directa
 Este método se basa en los siguientes principios:
1.
2.
3.
Seleccionar el elemento que tenga la llave menor.
Intercambiarlo con el primer elemento 1.
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).
74
Clasificación por selección directa
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
75
Métodos de clasificación avanzados
 Inserción por decremento decreciente
 Un refinamiento de la inserción directa fue propuesto
por D.L. Shell en 1959.
76
Métodos de clasificación avanzados
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
77
Programación I
MC José Andrés Vázquez Flores
Búsqueda Lineal
 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.
79
Búsqueda Lineal
 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.
80
Búsqueda Lineal
Procedimiento busquedaLineal (elemento)
Inicio
i0
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.
81
Búsqueda Binaria
 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.
82
Búsqueda Binaria
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
83
Descargar

Arreglos,Cadenas,Ordenamientos y Busquedas