miércoles, 29 de julio de 2009

INTRODUCCIÓN A LOS ARREGLOS

Un arreglo es una estructura homogénea, compuesta por varios componentes, todos del mismo tipo y almacenados consecutivamente en memoria. Cada componente puede ser accesado directamente por el nombre del arreglo seguido de un subindice encerrado en corchetes.
Arreglos Unidimensionales
Un arreglo unidimensional es un tipo de datos estructurado que está formado de una colección finita y ordenada de datos del mismo tipo. Es la estructura natural para modelar listas de elementos iguales.
El tipo de acceso a los arreglos unidimensionales es el acceso directo, es decir, podemos acceder a cualquier elemento del arreglo sin tener que consultar a elementos anteriores o posteriores, esto mediante el uso de un índice para cada elemento del arreglo que nos da su posición relativa.
Para implementar arreglos unidimensionales se debe reservar espacio en memoria, y se debe proporcionar la dirección base del arreglo, la cota superior y la inferior.
DECLARACIÓN
La declaración de un arreglo unidimensional consiste en establecer las características del arreglo y sus elementos, por medio de la siguiente sintaxis:
[ ] < identificador > ;
Donde:
tipo indica el tipo correspondiente a los elementos del arreglo ,
identificador es el nombre del arreglo, y
el par de corchetes, [ ], representa la dimensión del arreglo y encierra un número entero que corresponde al número de elementos del arreglo.
Ejemplos:
int [ ] a ;
float [ ] distancia ;
Artículo [ ] art = new Artículo[ 3];
Observe que, en la declaración, el espacio entre los corchetes está vacío. Esto se debe a que, durante dicha operación, no se reserva espacio en la memoria.
CREACIÓN.
La creación de un arreglo unidimensional consiste en reservar espacio de memoria para todos sus elementos, utilizando la siguiente sintaxis:
< identificador > = new [ tamaño ] ;
Donde:
new es el operador para gestionar espacio de memoria, en tiempo de ejecución,
tamaño es un número entero que representa el número de elementos del arreglo.
Ejemplos:
a = new int [10] ; // Se crea el arreglo a , con 10 elementos de tipo entero.
distancia = new float[ 5] ; // Se crea el arreglo distancia , con 5 elementos de punto flotante y precisión sencilla .Artículo [] art = new Artículo[3];
Artículo [ ] art = new Artículo[ 3]; // Se crean 3 referencias a objetos de la clase Artículo
art[0]= new Artículo(); // Se crea el primer objeto del arreglo art
art[1]= new Artículo(); // Se crea el segundo objeto del arreglo art
art[2]= new Artículo(); // Se crea el tercer objeto del arreglo art

Las dos primeras operaciones de declaración y creación anteriores se pueden agrupar en una sola instrucción, como se muestra enseguida:
int [ ] a = new int [10] ;
float [ ] distancia = new float[5] ;
INICIALIZACIÓN.
Un arreglo es un objeto que,cuando es creado por el compilador, se le asignan automáticamente valores iniciales predeterminados a cada uno de sus elementos, de acuerdo a los siguientes criterios:
• Si el tipo del arreglo es numérico, a sus elementos se les asigna el valor cero.
• Si el tipo del arreglo es char, a sus elementos se les asigna el valor '\u0000'.
• Si el tipo del arreglo es bool, a sus elementos se les asigna el valor false.
• Si el tipo del arreglo es una clase, a sus elementos se les asigna el valor null.
Cuando se requiere asignar valores iniciales diferentes de los predeterminados, es posible agrupar las operaciones de declaración, creación e inicialización en una sola instrucción, por ejemplo:
int [ ] a = { 1, 0,4,-6, 2,9, 23,455, 90,35 };
float [ ] distancia = { 2.50F, 286.45F, 46.75F, 30.62F, 93.00F };
string [ ] pato = { "Hugo", "Paco", "Luís" };
ACCESO.
Se puede acceder a los valores de los elementos de un arreglo a través del nombre del arreglo y un subíndice. El subíndice debe escribirse entre corchetes y representa la posición del elemento en el arreglo. Así, podemos referirnos a un elemento del arreglo escribiendo el nombre del arreglo y el subíndice del elemento entre corchetes. Los valores de los subíndices empiezan en cero para el primer elemento, hasta el tamaño del arreglo menos uno.
Ejemplo:
float [ ] distancia = new float[5] ; // Crea el arreglo distancia con 5 elementos.

float x = 25F, y = 10F ; // Crea dos variables de punto flotante y precisión sencilla.

Distancia [0] = x + y; // El valor asignado al primer elemento es 35.

Distancia [1] = ++distancia [0]; // Asigna 36 al segundo elemento.

Distancia [2] = distancia [1] - distancia [0] + 4; // Asigna 5 al tercer elemento.

Distancia [3] = distancia [2]--; // Asigna 5 al cuarto elemento
// y disminuye en 1 el valor del tercero.

distancia[4] = distancia[3] * distancia[2] ; // Asigna 20 al quinto elemento.

y = distancia[4] ; // Asigna a y el valor almacenado en el quinto elemento.

Arreglos Bidimensionales
Este tipo de arreglos al igual que los anteriores es un tipo de dato estructurado, finito ordenado y homogéneo. El acceso a ellos también es en forma directa por medio de un par de índices.
Los arreglos bidimensionales se usan para representar datos que pueden verse como una tabla con filas y columnas. La primera dimensión del arreglo representa las columnas, cada elemento contiene un valor y cada dimensión representa una relación


DECLARACIÓN.
La declaración de un arreglo consiste en establecer las características del arreglo y sus elementos, por medio de la siguiente sintaxis:
[ , ] < identificador > ;
Donde:
tipo indica el tipo correspondiente a los elementos del arreglo ,
identificador es el nombre del arreglo, y
el par de corchetes y la coma, [ , ], representan las dimensiones del arreglo y encierra dos números enteros, cuyo producto corresponde al número de elementos del arreglo.
Ejemplos:
double [ , ] matriz ;
int [ , ] ubicación ;
Rama [ , ] árbol; // Rama es una clase.
Observe que, en la declaración, el espacio entre los corchetes está vacío. Esto se debe a que, durante dicha operación, no se reserva espacio en la memoria.
CREACIÓN.
La creación de un arreglo bidimensional consiste en reservar espacio en la memoria para todos sus elementos, utilizando la siguiente sintaxis:
< identificador > = new [ dim1, dim2 ] ;
Donde:
new es el operador para gestionar espacio de memoria, en tiempo de ejecución,
dim1 y dim2 son valores enteros que representan las dimensioes del arreglo.
El tamaño del arreglo es el resultado de multiplicar los valores de las dimensiones y representa el número de elementos del arreglo.
Ejemplos:
matriz = new double [2, 3] ; // Se crea el arreglo matriz, con 6 elementos de tipo
//punto flotante y precición doble .
ubicación = new int[ 4,2] ; // Se crea el arreglo ubicación, con 8 elementos de
//tipo entero de 32 bits .
árbol = new Rama[5,2] ; // Se crea el arreglo arbol, con 10 objetos
//de la clase Rama.
Las operaciones de declaración y creación anteriores se pueden agrupar en una sola instrucción, como se muestra enseguida:
double [ , ] matriz = new double [2,3] ;
int [ , ] ubicación = new int[4, 2] ;
Rama [ , ] alumno = new Rama[5,2] ;
INICIALIZACIÓN.
Un arreglo es un objeto que,cuando es creado por el compilador, se le asignan automáticamente valores iniciales predeterminados a cada uno de sus elementos, de acuerdo a los siguientes criterios:
• Si el tipo del arreglo es numérico, a sus elementos se les asigna el valor cero.
• Si el tipo del arreglo es char, a sus elementos se les asigna el valor '\u0000'.
• Si el tipo del arreglo es bool, a sus elementos se les asigna el valor false.
• Si el tipo del arreglo es una clase, a sus elementos se les asigna el valor null.
Cuando se requiere asignar valores iniciales diferentes de los predeterminados, es posible agrupar las operaciones de declaración, creación e inicialización en una sola instrucción, por ejemplo:
double [ , ] matriz = { {1.5, 0, 4, -6.5, 2 } , {2.3, 9, 3.5, 4.8, 6.2} };
int [ , ] ubicación = { {2, 4} , {6, 8} , {9, 10}, {5 , 1}};
string [ , ] funcionario = { {"Hugo", "jefe"} ,
{ "Paco", "operador "},
{ "Luís","ayudante"} };
ACCESO.
Se puede acceder a los valores de los elementos de un arreglo bidimensional a través del nombre del arreglo y dos subíndices. Los subíndices deben escribirse entre corchetes y representa la posición del elemento en el arreglo. Así, podemos referirnos a un elemento del arreglo escribiendo el nombre del arreglo y los subíndices del elemento entre corchetes. Los valores de los subíndices empiezan en cero para el primer elemento, hasta el tamaño del arreglo menos uno.
Ejemplo:
int [ , ] posición = new int[5, 10] ; // Crea el arreglo posición , con 50 elementos de tipo entero.
int x;

posición[ 3, 5] = 3 ;
x = posición[ 3, 5] ;

INTRODUCCIÓN A LOS ARREGLOS

ORDENAMIENTO Y BÚSQUEDA DE ARREGLOS
MÉTODOS DE ORDENAMIENTO INTERNO (EN MEMORIA PRINCIPAL)

Para todos los algoritmos se cuenta con la siguiente estructura de datos
Const MAX = 100
A = arreglo[1..MAX] de enteros
Variable N:entero

ORDENAMIENTO DIRECTO. MÉTODO DE BURBUJA.
Ordena los elementos del arreglo usando el método de burbuja. Transporta en cada pasada el elemento más pequeño a la parte izquierda del arreglo A de N elementos.
Burbuja1(A,N)
Inicio
Declarar i,j,aux:entero
Para iß 2 hasta N haga
Para j ß i hasta 2 inc (–1) haga
Si (A[j-1]>A[j]) entonces
Aux ß A[j-1]
A[j-1] ß A[j]
A[j] ß aux
Fin si
Fin para
Fin para
Fin
ORDENAMIENTO DIRECTO. METODO DE LA BURBUJA. CONTRARIO AL ANTERIOR.
La lógica de este algoritmo cambia con el anterior, en el hecho de que en cada pasada se lleva el valor mas grande a hacia la parte derecha del arreglo A de N elementos.




Burbuja2(A,N)
Inicio
Declarar i,j,aux:entero
Para iß 1 hasta N-1 haga
Para j ß 1 hasta N-i haga
Si (A[j]>A[j+1]) entonces
Aux ß A[j]
A[j] ß A[j+1]
A[j+1] ß aux
Fin si
Fin para
Fin para
Fin

ORDENAMIENTO DIRECTO CON SEÑAL
Algoritmo que usa el principio de ordenamiento del método de la burbuja, usando una señal para saber si en cada pasada hubo intercambios. Arreglo A de N elementos enteros.
Burbujaconseñal(A, N)
Inicio
Declarar i,j,aux:entero
Declarar band:booleano
i ß 1
Band ß FALSO
Mientras Que (i<= N-1) y (band = FALSO) haga
Band ß VERDADERO
Para j ß 1 hasta N-i haga
Si (A[j]>A[j+1]) entonces
Aux ß A[j]
A[j] ß A[j+1]
A[j+1] ß aux
Band ß FALSO
Fin si
Fin para
Fin MQ
Fin

ORDENAMIENTO POR EL MÉTODO DE LA SACUDIDA (SHAKER SORT)
Este método es una optimización del método de la burbuja. Consiste en mezclar las dos formas como se puede realizar el método de ordenamiento directo. En cada pasada hay dos etapas, el la primera etapa se trasladan los elementos más pequeños hacia la izquierda almacenando en una variable el último elemento intercambiado. En la segunda etapa, se trasladan los elementos más grandes hacia la parte derecha del arreglo almacenando en otra variable la posición del último elemento intercambiado.
Algoritmo que ordena los elementos del arreglo A, de N elementos, por el método de la sacudida.
Shakersort(A,N)
Inicio
Declarar i, izq, der, k, aux: entero
izq ß 2
der ßN
k ß N
Repetir
Para i ß der hasta izq inc (-1) haga
Si (A[i-1]>A[i]) entonces
Aux ß A[i-1]
A[i-1] ß A[i]
A[i] ß aux
k ß i
Fin si
Fin para
Izq ß k + 1
Para i ß izq hasta der haga
Si (A[i-1] > A[i]) entonces
Aux ß A[i-1]
A[i-1] ß A[i]
A[i] ß Aux
k ß i
Fin si
Fin para
Der ß k-1
Hasta que izq>der
Fin

MÉTODO DE ORDENAMIENTO POR INSERCIÓN DIRECTA
El objetivo de este método es copiar la forma como los jugadores de cartas ordenan la baraja en una mano. El objetivo de este método es insertar un elemento en la parte izquierda del arreglo que ya se encuentra ordenada. El proceso se repite desde el segundo hasta el n-esimo elemento.

Algoritmo que ordena los elementos del arreglo usando el método de inserción directa. Arreglo A de N elementos.
insercion(A,N)
Inicio
Declarar i, aux, k: entero
Para i ß 2 hasta N haga
Aux ß A[i]
k ß i-1
Mientras Que ((k>=1) y (auxA[k+1] ß A[k]
k ß k -1
Fin MQ
A[k+1] ß aux
Fin para
Fin



ORDENAMIENTO POR MÉTODO DE INSERCIÓN BINARIA
Es una mejora del método de inserción directa, ya que se hace una búsqueda binaria en lugar de una búsqueda secuencial para insertar el elemento a la izquierda del arreglo, que ya se encuentra ordenado. Y el proceso se repite hasta el n-esimo elemento.
Algoritmo que ordena los elementos del arreglo usando el método de inserción binara. Arreglo A de N elementos.
insercionbinaria(A,N)
Inicio
Declarar i, aux, izq, der, m, j: entero
Para i ß 2 hasta N haga
Aux ß A[i]
Izq ß 1
Der ß i-1
Mientras Que (izq<=der) haga
m ß parteentera((izq+der)/2)
Si (aux <= A[m]) entonces
Der ß m-1
Sino
Izq ß m+1
Fin si
Fin MQ
j ß i-1
Mientras Que (j>=izq) haga
A[j+1] ß A[j]
j ß j-1
Fin MQ
A[izq] ß aux
Fin para
Fin





ORDENAMIENTO POR SELECCIÓN DIRECTA
La idea de este algoritmo es buscar el menor elemento del arreglo y colocarlo en la primera posición, luego se busca el segundo elemento más pequeño del arreglo y se coloca en la segunda posición y así. El algoritmo se basa en:
1. Seleccionar el menor elemento del arreglo.
2. Intercambiar dicho elemento con el primero.
3. Repetir los pasos anteriores con los (n-1), (n-2)... elementos y así sucesivamente hasta que solo quede el elemento mayor.
Algoritmo que ordena los elementos de un arreglo usando el método de selección directa. A arreglo de N elementos.
seleccion(A,N)
Inicio
Declarar i, menor, k, j: entero
Para i ß 1 hasta N-1 haga
Menor ß A[i]
k ß i
Para j ß i+1 hasta N haga
Si (A[j]Menor ß A[j]
k ß j
Fin si
Fin para
A[k] ß A[i]
A[i] ß menor
Fin para
Fin







ORDENAMIENTO CON EL MÉTODO DE SHELL (INSERCIÓN CON INCREMENTOS DECRECIENTES)
Este algoritmo compara cada elemento del arreglo para su ubicación correcta, con los elementos que se encuentran en la parte izquierda del mismo. Este método propone que las comparaciones entre los elementos se efectúen con saltos de mayor tamaño, pero con incrementos decrecientes.
Algoritmo que ordena los elementos de un arreglo usando el método de shell. A arreglo de N elementos.
shell(A,N)
Inicio
Declarar int, i, aux: entero
Declarar band: booleano
Int ß N+i
Mientras Que (int>1) haga
int ß parteentera(int/2)
band ß VERDADERO
Mientras Que (band=VERDADERO) haga
Band ß FALSO
i ß 1
Mientras Que ((I+int)<=N) haga
Si (A[i]>A[i+int]) entonces
aux ß A[i]
A[i] ß A[i+int]
A[i+int] ß aux
Band ß VERDADERO
Fin si
i ß i+1
Fin MQ
Fin MQ
Fin MQ
Fin


ORDENAMIENTO POR EL MÉTODO DE QUICKSORT (MÉTODO RÁPIDO DE ORDENACIÓN POR PARTICIÓN)
Este algoritmo es el mas eficiente y veloz de los métodos de ordenación interna. La idea central del algoritmo es:
1. Se toma un elemento X de una posición cualquiera del arreglo
2. Se trata de ubicar a X en la posición de correcta del arreglo, de tal forma que todos los elementos que se encuentran a su izquierda sean menores o iguales a X y todos los elementos que se encuentran a su derecha sean mayores o iguales a X.
3. Se repiten los pasos anteriores, pero con los conjuntos de datos que se encuentran a la izquierda y a la derecha de la posición correcta de X en el arreglo.
4. El proceso termina cuando todos los elementos se encuentran en su posición correcta en el arreglo.
El paso 3 se puede hacer de forma iterativa o recursiva. En este ejemplo, se hará de forma iterativa, dejando el método recursivo para más adelante en el curso.
Se necesitan dos algoritmos. Quicksortitera y reduceitera.
Algoritmo que ordena los elementos de un arreglo A de N elementos, usando el método Quicksort iterativo.




Quicksortitera(A, N)
Inicio
Declarar top, ini, fin, pos: entero
Pilamayor: Arreglo[1..MAX] de entero
Pilamenor: Arreglo[1..MAX] de entero

Top ß 1
Pilamenor[top] ß 1
Pilamayor[top] ß N
Mientras Que (top>0) haga
Ini ß pilamenor[top]
Fin ß pilamayor[top]
Top ß top-1
Pos ß Reduceitera(ini, fin)
Si (ini<(pos-1)) entonces
Top ß top+1
Pilamenor[top] ß ini
Pilamayor[top] ß pos-1
Fin si
Si (fin>(pos+1)) entonces
Top ß top+1
Pilamenor[top] ß pos+1
Pilamayor[top] ß fin
Fin si
Fin MQ
Fin







Reduceitera(INI, FIN)
/* INI y FIN representa las posiciones de los extremos izquierdo y derecho respectivamente del conjunto de elementos a evaluar. En POS es una variable donde se almacenará el resultado de este algoritmo */
Inicio
Declarar izq, der, aux, pos: entero
Declarar band: booleano
Izq ß ini
Der ß fin
Pos ß ini
Band ß VERDADERO
Mientras Que (band=VERDADERO) haga
Mientras Que ((A[pos]<=A[der]) y (pos<>der)) haga
der ß der-1
Fin MQ
Si (Pos=der) entonces
Band ß FALSO
Sino
Aux ß A[pos]
A[pos] ß A[der]
A[der] ß aux
Pos ß der
Mientras Que ((A[pos]>=A[izq])y(pos<>izq)) haga
Izq ß izq+1
Fin MQ
Si (pos=izq) entonces
Band ß Falso
Sino
Aux ß A[pos]
A[pos] ß A[izq]
A[izq] ß aux
Pos ß izq
Fin si
Fin si
Fin MQ
Retornar Pos
Fin
MÉTODOS DE BÚSQUEDA INTERNA (BÚSQUEDA EN MEMORIA PRINCIPAL)
Para todos los algoritmos se cuenta con la siguiente estructura de datos
Const MAX = 100
V = arreglo[1..MAX] de enteros
Variable N:entero
Existen 4 métodos principales de búsqueda interna:
• Secuencial líneal
• Binaria
• Por transformación de Claves (Solo se menciona, después se añadirán los algoritmos)
• Árboles de búsqueda (no se tratan aquí)

BÚSQUEDA SECUENCIAL LINEAL.
Consiste en la revisión elemento por elemento del arreglo hasta encontrar el dato buscado, o hasta llegar al final del arreglo, sin haberlo encontrado. Se puede diferenciar entre buscar en un arreglo desordenado y buscar en un arreglo ordenado.
Búsqueda en arreglos desordenados
Algoritmo que busca secuencialmente el elemento X en el arreglo desordenado V, con N elementos.
Secuencialdesordenado(V, N, X)
Inicio
Declarar i:entero
Declarar bandera: booleano

i ß 1
Bandera ß FALSO
Mientras Que ((i<=N) y (Bandera=FALSO)) haga
Si (V[i]=X) entonces
Bandera ß VERDADERO
Sino
i ß i+1
Fin si
Fin MQ
Si (bandera=VERDADERO) entonces
Imprimir(“El elemento está en la posición i”);
Sino
Imprimir(“El elemento no está en el arreglo”)
Fin si
Fin

Búsqueda en arreglos ordenados
Este algoritmo es similar al anterior, pero se agrega una nueva condición basada en el orden de los elementos. Busca secuencialmente un elemento X en un arreglo ordenado V de N elementos. El orden de V es creciente. {V[1]≤V[2] ≤...≤V[N]}
Secuencialordenado(V, N, X)
Inicio
Declarar i:entero
Declarar bandera: booleano

i ß 1
Bandera ß FALSO
Mientras Que ((i<=N) y (Bandera=FALSO) y (X>=V[i]) haga
Si (X=V[i]) entonces
Bandera ß VERDADERO
Sino
i ß i+1
Fin si
Fin MQ
Si (bandera=VERDADERO) entonces
Imprimir(“El elemento está en la posición i”);
Sino
Imprimir(“El elemento no está en el arreglo”)
Fin si
Fin

BÚSQUEDA BINARIA
La búsqueda binaria, sirve exclusivamente para arreglos ordenados, consiste en dividir el intervalo de búsqueda en dos partes, comparando el elemento buscado con el central, , en caso de no ser iguales se redefinen los extremos del intervalo (según si el elemento central es mayor o menor que el buscado). El proceso termina cuando se encuentra el elemento o cuando se anula el intervalo de búsqueda.
Algoritmo que busca el elemento X mediante búsqueda binaria en el arreglo ordenado V con N elementos.
binaria(V, N, X)
Inicio
Declarar izq, cen, der: entero
Declarar bandera: booleano

Izq ß 1
Der ß N
Bandera ß FALSO
Mientras Que ((izq<=der) y (Bandera=FALSO)) haga
Cen ß parteentera((izq+der)/2)
Si (X=V[cen]) entonces
Bandera ß VERDADERO
Sino
Si (X>V[cen]) entonces
izq ß cen+1
Sino
der ß cen-1
Fin si
Fin si
Fin MQ
Si (bandera=VERDADERO) entonces
Imprimir(“El elemento está en la posición cen”);
Sino
Imprimir(“El elemento no está en el arreglo”)
Fin si
Fin

Arreglos Bidimensionales

Los arreglos bidimensionales se usan para representar datos que pueden verse como una tabla con filas y columnas. La primera dimensión del arreglo representa las columnas, cada elemento contiene un valor y cada dimensión representa una relación

La representación en memoria se realiza de dos formas : almacenamiento por columnas o por renglones.

Aarreglo Unidimensional

Un arreglo unidimensional es un tipo de datos estructurado que está formado de una colección finita y ordenada de datos del mismo tipo. Es la estructura natural para modelar listas de elementos iguales.

El tipo de acceso a los arreglos unidimensionales es el acceso directo, es decir, podemos acceder a cualquier elemento del arreglo sin tener que consultar a elementos anteriores o posteriores, esto mediante el uso de un índice para cada elemento del arreglo que nos da su posición relativa.

ARREGLOS

Los arreglos son las estructuras de datos más sencillas.

Definición: Los arreglos son un grupo de posiciones en memoria relacionadas entre sí por el hecho de que todas tienen el mismo nombre y los datos que contiene son todos del mismo tipo.

Son entidades estáticas ya que conservan el mismo tamaño durante toda la ejecución del programa.

Para poder referirnos a una posición en particular o al datos dentro de esa posición del arreglo, se especifica el nombre del arreg lo y el número de posición del elemento. Las posiciones generalmente se cuentan a partir del cero como primera posición.

ESTRUCTURAS REPETITIVAS

Son operaciones que se deben ejecutar un número repetido de veces. El conjunto de instrucciones que se ejecuta repetidamente cierto número de veces, se llama Ciclo, Bucle o Lazo.
Fases de un Programa Cíclico :
1. Entrada de datos e instrucciones previas
2. Lazo o bucle
3. Instrucciones finales o resto del proceso
4. Salida de resultado

ESTRUCTURAS DE DESICION

Permite probar condiciones y realizar diferentes operaciones en función de los resultados de la prueba. Puede comprobar si una condición es verdadera o falsa, los distintos valores de una expresión o las diferentes excepciones que se generan al ejecutar una serie de instrucciones.