Computación 1

Tema 3 Diseño de algoritmos usando tipos de datos estructurados homogéneos

Estructura de datos.
En computación, una estructura de datos es una manera organizada de almacenar información (datos) en
un computador de modo que puedan ser usados de una forma eficiente.
Una selección cuidadosa de la estructura permitirá
usar un algoritmo más eficiente.
Una estructura bien diseñada permitirá efectuar una
variedad de operaciones, usando un mínimo de tiempo
de ejecución y espacio de memoria. A la derecha se
muestran los tipos de datos mas utilizados.

Arreglos Unidimensionales – N Dimensionales.

Un arreglo (array) es una colección de datos del mismo tipo, que se almacenan en posiciones consecu-
tivas de memoria y reciben un nombre común. Para referirse a un determinado elemento de un array se
usa un índice, que indique su posición relativa en la estructura.

Declaración y Definicion.
 Utilizando un lenguaje formal, se puede decir que una declaración es una sentencia o instrucción
que introduce un nombre de variable (identificador) en un programa. A partir de ese momento se dice
que esa variable “existe" dentro del programa.
 La declaración se completa con la definición. En esta fase se concreta la creación de la entidad. Si
es un dato se le asigna memoria física y pudiera ser inicializado.
La forma general de declaración de arreglos es indicando el tipo de dato que va a almacenar, el nombre
del arreglo y el tamaño:

 Tipo se refiere al dato que van a ser almacenado (int, float, char, etc).

 NombreArreglo permite identificar el arreglo y usualmente tiene ciertos requisitos del lenguaje de
programación. Estos requisitos pueden ser una longitud máxima del nombre, caracteres permitidos,
palabras reservadas, etc.
 Tamaño indica el número de elementos que contiene el arreglo. En lenguaje C, este valor debe ser
una constante entera y no puede ser cambiado mientras el programa se esta ejecutando. Este
parámetro se debe incluir por cada dimensión del arreglo. En los arreglos de una dimensión
(vectores, listas) se coloca una vez. En los arreglos de dos dimensiones se coloca dos veces y en
general para un arreglo de n dimensiones se coloca n veces.

Dimension.

Diseño de algoritmos usando datos homogeneos

Computación 2

Existen arreglos de 1,2,3, , n dimensiones. La forma

general de la declaración de un arreglo de más de una
dimensión es:
Pseudoc
 Tipo NombreArreglo[T1, T2, … T n]
C++
 Tipo NombreArreglo[T1][T2] …[Tn];

Ejemplo 1: Definir las estructuras de datos para almacenar los datos de las evaluaciones (3) de un
conjunto de estudiantes (12) almacenadas en una tabla como se muestra abajo.

Debido a que los tipos de dato son diferentes ya que la

cedula es de tipo entero y las notas son del tipo real no se
puede guardar todo en una sola estructura. Entonces se
pueden definir dos estructuras para almacenar los datos:
Pseudoc C++
ent CEDULA[12] int CEDULA[12];
real NOTAS[12,3] float NOTAS[12][3];
CEDULA es de una dimensión, NOTAS es de dos
dimensiones. En el arreglo de dos dimensiones el 1º valor
representa las filas y el 2º valor las columnas.

A esta forma de organizar los datos se le llama "arreglos paralelos" ya que aunque se guardan en dos
estructuras separadas existe una relación entre los dos arreglos, que debe ser respetada en la lógica del
programa que procesa los datos. O sea al estudiante de la fila 7 del arreglo CEDULA, por ejemplo, le
corresponden las notas almacenadas en la fila 7 del arreglo NOTAS.
Si suponemos que tenemos las notas por materias (3)
se puede organizar los datos usando un arreglo de
tres dimensiones para almacenar los datos de las
evaluaciones:
Pseudoc C++
ent CEDULA[12] int CEDULA[12];
real NOTAS[12,3,3] float NOTAS[12][3][3];
Si se hace una analogía con las tres dimensiones
espaciales se podría decir que el largo son las filas (1º
índice), el ancho serian las columnas (2º índice) y la
tercera dimensión sería la profundidad (3º índice)

REFERENCIAS.-
Una vez que se declara un arreglo en un programa empieza a "existir" como una estructura de datos, por
lo que podemos comenzar a utilizarlo o a hacer referencias a él dentro de las instrucciones del programa.
Podemos leerlo, mostrarlo, copiarlo, modificar uno, dos o todos sus elementos, etc. Para hacer una
referencia a un arreglo se usa el siguiente formato:

NombreArreglo[ Indice ]

Diseño de algoritmos usando datos homogeneos

Computación 3

Donde:
 NombreArreglo es el identificador con el cual fue declarado el arreglo.

 Indice corresponde a la posición de un elemento dentro del arreglo. Este valor

puede ser una constante de tipo entero, una variable de tipo entero o inclusive
una expresión que al evaluarse produce un resultado de tipo entero.
El valor del índice no puede ser mayor al tamaño del arreglo porque se estaría
intentando referenciar un elemento fuera de la estructura.
En C++ el índice comienza en 0, asi para el arreglo del ejemplo 1 CEDULA[12],
los elementos van de CEDULA[0] a CEDULA[11]. C++ no controla los límites del
arreglo, es el programador quien debe incluir las instrucciones necesarias dentro
del programa para que no haya desbordamiento.
Ejemplo:
CEDULA[6] // se refiere al 6º elemento del arreglo
CEDULA[I] // la referencia depende del valor de I
CEDULA[2*I+1] //Se resuelve la expresión, para hacer la referencia
En el caso de arreglos de dos dimensiones se tiene:

NombreArreglo[ Indice1, Indice2 ]

Donde:
 Indice1 corresponde a la FILA del elemento referenciado.
 Indice2 corresponde a la COLUMNA del elemento referenciado.
Estos dos índices tienen las mismas propiedades y requerimientos de los
arreglos de una dimensión.
Ejemplo:
NOTAS[6][1] //Se refiere al elemento ubicado en la fila 6, columna 1
NOTAS[I][J] //La referencia depende de los valores de I y J

ALMACENAMIENTO DE ARREGLOS EN MEMORIA.

La memoria de la computadora es
unidimensional por lo que el almacenamiento
de los arreglos de más de una dimensión
requiere que la posición de los elementos del
arreglo sea “linealizada".
En el caso de una dimensión hay una
correspondencia directa entre la posición del
elemento en la memoria y la posición en la
representación real del vector. En el caso de
dos dimensiones la matriz se almacena por
filas como se muestra en la figura.

La posición relativa en la memoria, de un elemento:

NOTAS[i,j] (Fila=i, Columna=j)
del arreglo NOTAS, con relación al primer elemento es:

Diseño de algoritmos usando datos homogeneos

Computación 4

P = n*(i-1) + j donde:
n: # columnas del arreglo, i: fila del elemento j: columna del elemento
Por ejemplo si deseamos saber la posición, en la memoria, del elemento NOTAS[2,3] del arreglo; se
aplicaría la formula anterior:
n=3 i=2, j=3 P=3*(2–1)+3=6 NOTAS[2,3] ocupa la posición 6 en memoria
Cardinalidad.-
Se refiere a la cantidad de elementos que tiene un arreglo. En tiempo de diseño, al momento de declarar
y definir el tamaño de un arreglo, la mayoría de las veces no se conoce la cantidad de elementos que
debe tener, por lo que se estima un valor y se chequea dentro del algoritmo este valor, para evitar
problemas en la ejecución del algoritmo.
En tiempo de ejecución, existe una función sizeof(NombreArreglo) que devuelve el tamaño, en by-
tes, del arreglo. Así por ejemplo si se hace:
cout<<sizeof(NOTAS);
se muestra en pantalla el valor 144, ya que el arreglo tiene 36 elementos y cada elemento ocupa 4 by-
tes, si se desea mostrar la cantidad de elementos que tiene el arreglo se hace:
cout<<sizeof(NOTAS)/ sizeof(float);
Cadenas de Caracteres.-
Un tipo muy común de datos es el texto (tipo char) el
cual se usa normalmente en paquetes o bloques
(Nombres, Direcciones, Mensajes, etc) por lo que se requiere una estructura para almacenarlo. Un vector
tipo char permite almacenar el mensaje "Ingrese Cedula ", por ejemplo.

Si se desea almacenar nombres, existe una amplia

variedad de longitudes, como por ejemplo:
Ana Paz o Francisco Fernández; y como es necesario especificar el tamaño para declarar el arreglo,
entonces se coloca un tamaño estimado, por ejemplo: NOMBRE[20];
El espacio reservado se ocupa con un nombre,
ANA PAZ por ejemplo, y el resto queda con
cualquier cosa &%4VK?....., que no es útil.
El dato almacenado de esta manera se le llama una cadena de caracteres (string), si no tiene fin de
cadena es simplemente un arreglo de caracteres.
También es frecuente la necesidad de almacenar arreglos de cadenas de caracteres, por ejemplo una lista
de nombres, una lista de direcciones, una lista de mensajes.
A la derecha se muestra una lista de nombres,
donde cada nombre tiene diferente longitud. Cada
nombre se guarda en un vector, pero como la lista
es una estructura, se requiere in-tegrar todos los
vectores en una sola estructu-ra, así se llega a un
arreglo Lista[5][10].

LISTA[5][10] es una estructura de dos dimensiones donde el primer índice representa las filas o
cantidad de elementos de la lista y el segundo índice representa el ancho máximo o cantidad máxima de
caracteres que debe tener cada nombre, incluyendo el fin de cadena.

Diseño de algoritmos usando datos homogeneos

Computación 5

Operaciones sobre arreglos.

1. Recorrido 2. Asignación 3. Lectura / Escritura 4. Ordenación / Búsqueda.
RECORRIDO
Para usar la información almacenada es necesario
"recorrer" el arreglo. El recorrido puede incluir todo o
parte del arreglo. La operación se realiza usando
estructuras cíclicas, relacionando variables de control con
los índices del arreglo. De esta manera se pueden hacer
acciones (leer, mostrar, asignar valores, etc) sobre los
elementos referenciados con el indice I.

Recorrido caso una dimensión.-

El diseño del recorrido depende del enunciado del

problema a resolver, o sea que no existe una receta
para recorrer un arreglo o vector.
Un vector declarado como int A[12] pudiera ser
recorrido todo, desde el inicio al final, también
pudiera recorrerse por posiciones impares o por
posiciones pares

Ejemplo 1: Recorrer un vector P[10].

Usando ciclos con contador
algoritmo RecorreVector_P void main(void)
inicio { int P[10],I ;
ent P[10], I for(I=0 ;I<10 ;I++ )
repetir_desde(I=1,I<=10,I=I+1) { Accion_sobre sobre P[I];
Accion_sobre P[I] }
fin_repetir_desde }
fin
Usando ciclos con condición
algoritmo RecorreVector_P void main(void)
inicio { int P[10],I ;
ent P[10], I=1 I=0;
repetir_mientras (I ≤ 10) while(I<10)
Accion_sobre sobre P[I] { Accion_sobre sobre P[I];
I=I+1 I++;
fin_repetir_mientras }
fin }
algoritmo RecorreVector_P void main(void)
inicio { int P[10],I ;
ent P[10], I=1 I=0;
repetir do
Accion_sobre sobre P[I] { Accion_sobre sobre P[I];
I=I+1 I++;
mientras(I < 10) }while(I<10) ;
fin }

Diseño de algoritmos usando datos homogeneos

Computación 6

Recorrido caso dos dimensiones.-

El recorrido de un arreglo de dos dimensiones tiene más posibilidades. Un arreglo declarado como int
A[3][3]; se podría recorrer por filas, por columnas o por diagonales, como se muestra en la figura de la
pagina siguiente. Estas no son las únicas posibilidades, y al igual del caso unidimensional el diseño del
recorrido depende del enunciado del problema.

El recorrido de un arreglo de dos dimensiones requiere el

uso de un lazo doble (anidado).
repetir_desde(I=1,I<= N,I=I+1)
repetir_desde(J=1,J<=M,J=J+1)
Accion_sobre A[I,J]
fin_repetir_desde
fin_repetir_desde

Recorrido por FILAS Recorrido por COLUMNAS

I J A[I][J] I J A[I][J]
repetir_desde(I=1,I<=N,I=Ii+1) 1 1 A[1][1] repetir_desde(J=1,J<=M,J=J+1) 1 1 A[1][1]
repetir_desde(J=1,J<=M,J=J+1) 1 2 A[1][2] repetir_desde(I=1,I<=N,I=I+1) 2 1 A[2][1]
Accion_sobre A[I,J] 1 3 A[1][3] Accion_sobre A[I,J] 3 1 A[3][1]
fin_repetir_desde 2 1 A[2][1] fin_repetir_desde 1 2 A[1][2]
2 2 A[2][2] 2 2 A[2][2]
fin_repetir_desde 2 3 A[2][3] fin_repetir_desde 3 2 A[3][2]
N=FILAS 3 1 A[3][1] N=COLUMNAS 1 3 A[1][3]
3 2 A[3][1] 2 3 A[2][3]
M=COLUMNAS 3 3 A[3][3] M=FILAS 3 3 A[3][3]

for(I=0;I<FILAS;I++) for(I=0;I<COLUMNAS;I++)
{ for(J=0;J<COLUMNAS;J++) { for(J=0;J<FILAS;J++)
{ Accion_sobre A[I,J] { Accion_sobre A[J,I]
} }
} }
ASIGNACION.-
La asignación de valores a un elemento de un arreglo se representa con el operador "=":
En Pseudoc: A[10] = 3, ventas[2,2] = 1500 En C++: A[10]=3;, ventas[2][2] = 1500;
La asignación de valores a los elementos de un arreglo se puede hacer:
En forma individual: Usando una estructura cíclica:
float A[6]; ent B[10]
repetir_desde(i=1,i<=10,i=i+1)
A[0]=10.8; A[1]=12; A[2]=17.5;
B[i] = 0
A[3]=15.1; A[4]=14; A[5]=16;
fin_ repetir_desde

En el caso de una cadena de caracteres:

En forma individual: o Asignando la cadena completa

char nombre[15]; - En pseudocódigo: nombre="CARMEN"

nombre[1]='C'; nombre[2]='A'; nombre[3]='R'; - En C++: strcpy(nombre,"CARMEN")
nombre[4]='M'; nombre[5]='E'; nombre[6]='N';
nombre[7]='\0'; strcpy función de la librería <string.h>

Diseño de algoritmos usando datos homogeneos

Computación 7

El valor asignado puede ser:

repetir_desde(i=1, i<=10,i=i+1)
A[i] = 0 //Un valor constante ó
A[i] = random(10) // lo que devuelve una función ó
A[i] = 2*i+i^2 // una variable o expresión ó
leer (A[i]) // valor leido por teclado ó
A[i] = A[i]+1 // Un elemento del mismo arreglo
fin_repetir_desde
Para asignar valores a todos los elementos de un vector, se recorre el vector y efectuar la operación de
asignación con cada uno de los elementos del vector.
• Caso Unidimensional. Asignar el valor 6 a todos • Caso MD. Inicializar vector B[2,3] con cero
los elementos de un vector A[5] repetir_desde(i=1, i<=2,i=i+1)
repetir_desde(j=1,j<=3,j=j+1)
repetir_desde(i=1, i<=5,i=i+1)
B[i,j] = 0
A[i] = 6
fin_repetir_desde
fin_repetir_desde
fin_repetir_desde

INICIALIZACION DE ARREGLOS.-

C permite la inicialización de arreglos al

momento de declararlos usando la forma
general:
La lista de valores es una lista de constantes
separadas por comas cuyo tipo debe ser
compatible con el Tipo definido para el
arreglo.
Esto es equivalente a hacer:

Esta permitido, en la declaración, dejar en blanco el tamaño del

arreglo en el momento de la inicializacion. El tamaño se ajusta
automáticamente a la cantidad de elementos inicializados

Las declaraciones muestran como inicializar una cadena de ca-

racteres. Es importante diferenciar el uso de las comillas
simples (') y las comillas dobles("). La comilla simple se usa
cuando se maneja UN SOLO CARÁCTER, por ejemplo 'A', 'L', 'A' se guarda en un byte
'm'. La comilla doble agrega el fin de cadena. "A" se guarda en dos bytes, 'A' + '\0'
"ORINOCO" ocupa 8 bytes
Inicialización de un arreglo de dos dimensio-
nes. Cualquiera de estas formas es valida

Inicialización de un arreglo de cadenas de

caracteres.

LECTURA / ESCRITURA
Esta operación tiene la forma general:
En Pseudoc En C++
leer(NombreArreglo[indice]) cin>> NombreArreglo[indice];

Diseño de algoritmos usando datos homogeneos

Computación 8

mostrar(NombreArreglo[indice]) cout<< NombreArreglo[indice];

Ejemplo 1:
En el programa del ejemplo se declaran tres vecto-
res los cuales se cargan de tres maneras diferen-
tes, A se lee del teclado, B se inicializa en la decla-
raron y C se llena usando una función random.
Los tres vectores se muestran haciendo un recorri-
do completo usando una estructura cíclica. La sali-
da del programa es:

Ejemplo 2:
El programa del ejemplo lee los nombres de 5 rios
junto con un valor (LARGO) que representa su lon-
gitud. En el programa se muestra como se lee un
arreglo que contiene una cadena de caracteres
(RIO).
Se observa que la cadena de caracteres se referen-
cia completa (cin>>RIO) tanto en la lectura
como en la escritura (cout<<MAYOR).
Se observa que la asignación
MAS_LARGO = RIO debe hacerse en C++:
strcpy(MAYOR,RIO);

Ejemplo 3:
El ejemplo 3 muestra dos programas en los que se utilizan arreglos de dos dimensiones. El de la izquierda
lee/ muestra un arreglo A[3][5] de tipo entero. En este caso se debe recorrer el arreglo completo utilizan-
do dos estructuras cíclicas anidadas. En el programa de la derecha se lee una lista de rios (5), con una
longitud máxima de 12 caracteres para cada cadena. En este caso a pesar de que RIOS es un arreglo bi -
dimensional, no es necesario leer cada elemento, como en el caso numérico de la izquierda, ya que se lee
cada cadena completa.
void main() void main()
{ int A[3][5],i,j; { char RIOS[5][12];
for(i=0;i<3;i++) for(i=0;i<5;i++)
{ for(j=0;j<5;j++ { cin>>RIOS[i]; }
{ cin>>A[i][j]; } for(i=0;i<5;i++)
} { cout>>RIOS[i]; }
for(i=0;i<3;i++) getch();
{ for(j=0;j<5;j++ }
{ cout>>A[i][j]; }

Diseño de algoritmos usando datos homogeneos

Computación 9

}
getch();
}

Diseño de algoritmos usando datos homogeneos

Computación 10

Algoritmos básicos de ordenamiento y búsqueda.

BUSQUEDA.- Esta operación es una tarea muy común en computación y básicamente consiste en
encontrar la posición de un elemento específico en un conjunto de elementos dados.
 Búsqueda secuencial
Suponemos una lista (vector) de elementos, donde no hay elementos repetidos, la forma mas sencilla de
buscar un elemento especifico es recorriendo la lista y verificando si existe alguna coincidencia entre los
elementos de la lista y el elemento buscado. Si existe el elemento se muestra un mensaje “Fin de
búsqueda", en caso contrario mostrar “Elemento No Existe".
Ejemplo: Se desea buscar una cedula en una lista (100 valores), si se encuentra se muestra un mensaje
indicando que esta existe, en caso contrario se muestra un mensaje indicando que existe. Se supone que
no hay elementos repetidos.
Análisis.- Se requiere recorrer toda la lista y preguntar si cada elemento de la lista es el que estamos
buscando. Se requiere un ciclo con contador (I – desde 1 hasta 100) y una estructura de decisión para
confirmar la condición del elemento buscado.
Diseño del algoritmo.-
El algoritmo de la izquierda muestra un mensaje indicando que la cedula existe y muestra su posición
dentro de la lista. Si la cedula no existe el algoritmo no dice nada.
Este algoritmo puede ser mejorado ya que, en el
anterior, aunque el encuentre el elemento buscado
sigue recorriendo la lista. Una forma de evitar esto es
usando un ciclo con condición.
Cuando se encuentra el elemento buscado se
interrumpe el ciclo de búsqueda y se muestran los
resultados.

Para indicar cuando la cedula “no existe", se

debe usar una variable tipo switch (flag),
como se muestra a abajo:

Diseño de algoritmos usando datos homogeneos

Computación 11

 Búsqueda Menor / Mayor.-

El problema planteado es buscar el elemento menor/mayor de un conjunto de elementos almacenados en
un arreglo. Por ejemplo, buscar el elemento mayor del vector A mostrado:
A(1) A(2) A(3) A(4) A(5) Diseño del algoritmo:
5 6 3 2 7 algoritmo Búsqueda_Mayor
inicio
Análisis.- entero I, MAYOR, A [5]
repetir_desde(I=1, I<=5,I=I+1)
La estrategia a seguir consiste en asignar la
Leer (A[I])
condición deseada (MAYOR) al primer elemento de
fin_repetir_desde
la lista y se empieza a comparar con todos los
I=1
elementos de la lista. Si alguno de los elementos
MAYOR = A [I]
resulta mayor que el elemento al cual se le ha
repetir_mientras (I <= 5)
asignado la condición, se cambia la condición al
si A[I] > MAYOR
nuevo elemento. Al terminar de recorrer todo el
MAYOR = A[I]
vector, el valor que mantiene la condición deseada
Fin_si
es el mayor.
I=I+1
fin_repetir_mientras
mostrar(“El valor Mayor es: “, MAYOR)
fin
ORDENAMIENTO.-
Ordenar es simplemente organizar información de una manera especificada (criterio de ordenamiento).
Método de Intercambio o de burbuja:
El algoritmo se basa en el principio de comparar pares de elementos adyacentes e intercambiarlos entre
si hasta que estén todos ordenados.
Ejemplo: Se desea ordenar en forma ascendente A(1) A(2) A(3) A(4) A(5)
el vector A: 5 6 3 2 1

Los pasos a seguir son: algoritmo ordenar_burbuja

1. Comparar elementos adyacentes en parejas inicio
(A[1] y A[2] - A[2] y A[3] - A[3] y A[4] - ……. A[n- entero A[5], I, J, aux, N
N=5
1] y A[n]). Si están en el orden deseado se dejan

Diseño de algoritmos usando datos homogeneos

Computación 12

igual, en caso contrario se intercambian las repetir_desde(I=1, I<=N,I=I+1)

posiciones. Si el vector tiene n elementos, se leer (A [I])
necesitan (n-1) comparaciones para recorrer todo fin_repetir_desde
repetir_desde(I=1, I<=N-1,I=I+1)
el vector.
repetir_desde(J=1,J<=N-1,J=J+1)
2. Al finalizar un ciclo, el vector estará si A[J] > A[J+1]
parcialmente ordenado. Se debe repetir el proceso aux = A[J]
hasta que el vector quede totalmente ordenado. En A[J] = A[J+1]
A[J+1] = aux
el caso más desfavorable, que el elemento mas
fin_si
pequeño/grande se encuentre en el extremo fin_repetir_desde
opuesto al orden requerido, se requieren (n-1) fin_repetir_desde
ciclos para llevarlo a su posición correcta. fin
El total de comparaciones para ordenar todo el
vector será de (n-1)*(n-1) = (n-1)2

Para el ejemplo planteado N = 5 por lo que

se requieren 4 ciclos de 4 pasos cada uno
por lo tanto se requieren (4x4) 16
comparaciones.
En la tabla se observa que al final de cada
ciclo, el elemento ubicado en el extremo
derecho ya queda ubicado en su posición
definitiva y no es necesario incluirlo en los
chequeos posteriores.

El algoritmo se puede modificar

disminuyendo el número de ciclos
necesarios:
repetir_desde(I=1, I<=N-1,I=I+1)
repetir_desde(J=1,J<=N-I,J=J+1)
si A[J] > A[J+1]
aux = A[J]
A[J] = A[J+1]
A[J+1] = aux
fin_si
fin_repetir_desde
fin_repetir_desde
La tabla se reduce como se muestra abajo

Diseño de algoritmos usando datos homogeneos