Un arreglo es un conjunto de datos o una estructura de datos homogneos
que se encuentran ubicados en forma consecutiva en la memoria RAM (sirve
para almacenar datos en forma temporal).
Definicin
Un arreglo puede definirse como un grupo o una coleccin finita, homognea y
ordenada de elementos. Los arreglos pueden ser de los siguientes tipos:
De una dimensin.
De dos dimensiones.
De tres o ms dimensiones.
Clasificacin de los arreglos
Un arreglo unidimensional
Es un tipo de datos estructurado que est formado de una coleccin 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 posicin relativa.
Para implementar arreglos unidimensionales se debe reservar espacio en
memoria, y se debe proporcionar la direccin base del arreglo, la cota superior
y la inferior.
REPRESENTACION EN MEMORIA
Los arreglos se representan en memoria de la forma siguiente: x : array[1..5] of
integer
Para establecer el rango del arreglo (nmero total de elementos) que
componen el arreglo se utiliza la siguiente formula: RANGO = Ls - (Li+1)donde:
ls = Lmite superior del arreglo
li = Lmite inferior del arreglo
Para calcular la direccin de memoria de un elemento dentro de un arreglo se
usa la siguiente formula: A[i] = base(A) + [(i-li) * w]donde :
A = Identificador nico del arreglo
i = Indice del elemento
li = Lmite inferior
w = Nmero de bytes tipo componente
Si el arreglo en el cual estamos trabajando tiene un ndice numerativo
utilizaremos las siguientes frmulas: RANGO = ord (ls) - (ord (li)+1) A[i] = base
(A) + [ord (i) - ord (li) * w]
Arreglos bidimensionales
Los arreglos bidimensionales se usan para representar datos que pueden verse
como una tabla con filas y columnas. La primera dimensin del arreglo
representa las columnas, cada elemento contiene un valor y cada dimensin
representa una relacin
La representacin en memoria se realiza de dos formas : almacenamiento por
columnas o por renglones.
Para determinar el nmero total de elementos en un arreglo bidimensional
usaremos las siguientes frmulas:
RANGO DE RENGLONES (R1) = Ls1 - (Li1+1) RANGO DE COLUMNAS (R2) = Ls2 (Li2+1) No. TOTAL DE COMPONENTES = R1 * R2
REPRESENTACION EN MEMORIA POR COLUMNAS
x : array [1..5,1..7] of integer
Para calcular la direccin de memoria de un elemento se usan la siguiente
formula: A[i,j] = base (A) + [((j - li2) R1 + (i + li1))*w]
Arreglos multidimensionales
El trmino dimensin representa el nmero de ndices utilizados para referirse
a un elemento particular en el arreglo. Los arreglos de ms de una dimensin
se llaman arreglos multidimensionales.
/*
/ [Link]
*/
#include
#define numFilas 4
#define numColumnas 5
int main (int argc, char * const argv[]) {
int despFila, despColumna, desplazamiento, multiplo,
despCalculados[numFilas][numColumnas];
for(despFila=0;despFila
for(despColumna=0;despColumna
desplazamiento=numColumnas-despColumna;
multiplo=despFila;
despCalculados[despFila][despColumna]=
(despFila+1)*despColumna+desplazamiento * multiplo;
};
for(despFila=0;despFila
std::cout<<"Fila actual: "<<despfila<<"\n";
std::cout<<"Distancia relativa desde la base: "<<"\n";
for(despColumna=0;despColumna
std::cout<<" "
<
<<" ";
std::cout<<"\n\n";
}
return 0;
}
}
El programa utiliza dos ciclos for para calcular e inicial cada uno de los
elementos del arraglo a su respectiva distancia relativa desde la base. El
arreglo creado tiene 4 filas y 5 columnas por fila, haciendo un total de 20
elementos enteros.
Son almacenados de forma lineal en la memoria de la computadora. Los
elementos en los arreglos multidimensionales estn agrupados desde el ndice
ms a la derecha hacia el centro. En el ejemplo anterior, fila 1, columna 1 sera
el elemento 3 del arreglo almacenado. Aunque el clculo del desplazamiento
aparece un poco difcil, es referenciado fcilmente cada elemento del arreglo.
La salida del programa anterior es:
Fila actual: 0
Distancia relativa desde la base:
01234
Fila actual: 1
Distancia relativa desde la base:
56789
Fila actual: 2
Distancia relativa desde la base:
10 11 12 13 14
Fila actual: 3
Distancia relativa desde la base:
15 16 17 18 19
dosdim has exited with status 0. </despfila<<"\n";>
Operaciones bsicas con arreglos.
Bsqueda
Ordenacin
Insercin
Eliminacin
Bsqueda.
La bsqueda consiste en encontrar un determinado valor dentro de un conjunto
de datos, para recuperar alguna informacin asociada con el valor buscado.
Existen diferentes formas de realizar esta operacin; en otras palabras hay
distintos mtodos o tcnicas para realizar bsqueda en vectores.
Bsqueda secuencial o lineal
Bsqueda Binaria
Bsqueda Hash
Arboles de bsqueda
TAREA
a) Consulte en que consisten las bsquedas secuencial y la binaria. Cal es su
diferencia?
b) Ejemplo de enunciado y realice el seudocdigo pertinente para resolverlo
por ambos mtodos.
Ordenacin
La ordenacin se refiere a la operacin de organizar los elementos de un vector
en algn orden dado: ascendente o descendente.
Existen diferentes mtodos o tcnicas para organizar los elementos de un
arreglo. Los ms comunes son:
Mtodo de burbuja
Mtodo de burbuja mejorado.
Ordenacin por seleccin
Insercin o mtodo de la baraja
Shell
Binsort o por urnas
Por montculos o heapsort
Por mezcla o mergesot
Mtodo de la sacudida o shackersort
Rapid sort o quick sort
Por rboles.
TAREA
a) Consulte en que consisten la ordenacin por burbuja y por seleccin. Cal
es su diferencia?
b) Ejemplo de enunciado y realice el seudocdigo pertienente para
resolverlo por ambos mtodos..
Insercin
Esta operacin consiste en adicionar un nuevo elemento al arreglo. Se debe
tener en cuenta:
1. Que no sobrepase el tamao mximo declarado para el vector.
2. La operacin puede darse para un arreglo ordenado o desordenado.
3.
Si el arreglo est desordenado, se incrementa en uno el nmero de
elementos y en esa posicin N + 1 se inserta el nuevo elemento,
4. Si el arreglo est ordenado hay que
4-1 Buscar el lugar dentro del arreglo donde se debe inserta el nuevo
valor para que continue el vector ordenado.
4-2 Correr todos los elementos del vector una posicin a la derecha,
para abrirle espacio al nuevo elemento, a partir del lugar donde
debe insertarse el nuevo dato.
4-3 Insertar el nuevo elemento del vector en el espacio que le
corresponde.
Eliminacin
Consiste en eliminar un elemento del arreglo, puede darse cuando el arreglo
est desordenado u ordenado. El proceso de eliminacin sigue el paos que se
describen a continuacin:
Verificar que el arreglo no est vaco.
Buscar la posicin donde se encuentra el elemnto a borrar.
Correr los elementos una posicin a la izquierda , a partir de la posicin
siguiente donde se encuentra el valor a borrar.
Disminuir el nmero de elementos del vector en uno.
Enviar un mensaje en caso de que el elemento a borrar no est dentro
del arreglo.
Tarea
Presente un enunciado con vectores donde se encuentre los procesos de
insercin y eliminacin. Realice el seudocdigo correspondiente
