Estructuras de datos y algoritmos: matrices
Array es un tipo de estructura de datos lineal que se define como una colección de elementos con tipos de
datos iguales o diferentes. Existen tanto en una sola dimensión como en múltiples dimensiones. Estas
estructuras de datos entran en escena cuando existe la necesidad de almacenar varios elementos de
naturaleza similar juntos en un solo lugar.
La diferencia entre un índice de matriz y una dirección de memoria es que el índice de matriz actúa como
un valor clave para etiquetar los elementos de la matriz. Sin embargo, una dirección de memoria es la
dirección inicial de la memoria libre disponible.
Los siguientes son los términos importantes para entender el concepto de Array.
Elemento : cada elemento almacenado en una matriz se denomina elemento.
Índice : cada ubicación de un elemento en una matriz tiene un índice numérico, que se utiliza para
identificar el elemento.
Sintaxis
Crear una matriz en los lenguajes de programación C y C++ :
data_type array_name[array_size] = {elements separated using commas}
or,
data_type array_name[array_size];
Crear una matriz en el lenguaje de programación JAVA −
data_type[] array_name = {elements separated by commas}
or,
data_type array_name = new data_type[array_size];
Necesidad de matrices
Las matrices se utilizan como soluciones a muchos problemas, desde pequeños problemas de clasificación
hasta problemas más complejos, como el problema del vendedor ambulante. Hay muchas estructuras de
datos además de los arreglos que brindan una complejidad de tiempo y espacio eficiente para estos
problemas, entonces, ¿qué hace que el uso de arreglos sea mejor? La respuesta está en el tiempo de
búsqueda de acceso aleatorio.
Las matrices proporcionan un tiempo de búsqueda de acceso aleatorio O(1) . Eso significa que acceder al
índice de
primer de la matriz y al índice 1000 la matriz llevará el mismo tiempo. Esto se debe al hecho de
que la matriz viene con un puntero y un valor de desplazamiento. El puntero apunta a la ubicación correcta
de la memoria y el valor de compensación muestra qué tan lejos buscar en dicha memoria.
array_name[index]
| |
Pointer Offset
Por lo tanto, en una matriz con 6 elementos, para acceder al primer elemento, la matriz apunta hacia el
índice 0. De manera similar, para acceder al sexto elemento , la matriz apunta hacia el quinto índice .
Representación de matriz
Los arreglos se representan como una colección de cubos donde cada cubo almacena un elemento. Estos
cubos están indexados de '0' a 'n-1', donde n es el tamaño de esa matriz en particular. Por ejemplo, una
matriz con tamaño 10 tendrá cubos indexados de 0 a 9.
Esta indexación también será similar para las matrices multidimensionales. Si se trata de una matriz
bidimensional, tendrá subcubetas en cada cubeta. Luego se indexará como nombre_arreglo[m][n], donde
m y n son los tamaños de cada nivel en el arreglo.
Según la ilustración anterior, los siguientes son los puntos importantes a considerar.
El índice comienza con 0.
La longitud de la matriz es 9, lo que significa que puede almacenar 9 elementos.
Se puede acceder a cada elemento a través de su índice. Por ejemplo, podemos buscar un elemento
en el índice 6 como 23.
Operaciones básicas en los arreglos
Las operaciones básicas en los arreglos son inserción, borrado, búsqueda, visualización, recorrido y
actualización. Estas operaciones generalmente se realizan para modificar los datos en la matriz o para
informar el estado de la matriz.
Las siguientes son las operaciones básicas admitidas por una matriz.
Traverse : imprime todos los elementos de la matriz uno por uno.
Inserción : agrega un elemento en el índice dado.
Eliminación : elimina un elemento en el índice dado.
Buscar : busca un elemento usando el índice dado o por el valor.
Actualizar : actualiza un elemento en el índice dado.
Display : muestra el contenido de la matriz.
En C, cuando una matriz se inicializa con tamaño, asigna valores predeterminados a sus elementos en el
siguiente orden.
Tipo de datos Valor por defecto
bool FALSO
carbonizarse 0
En t 0
flotar 0.0
doble 0.0f
vacío
wchar_t 0
Operación de inserción
En la operación de inserción, estamos agregando uno o más elementos a la matriz. Según el requisito, se
puede agregar un nuevo elemento al principio, al final o en cualquier índice dado de la matriz. Esto se hace
usando sentencias de entrada de los lenguajes de programación.
Algoritmo
El siguiente es un algoritmo para insertar elementos en una matriz lineal hasta que lleguemos al final de
la matriz:
1. Start
2. Create an Array of a desired datatype and size.
3. Initialize a variable ‘i’ as 0.
4. Enter the element at ith index of the array.
5. Increment i by 1.
6. Repeat Steps 4 & 5 until the end of the array.
7. Stop
Aquí, vemos una implementación práctica de la operación de inserción, donde agregamos datos al final de
la matriz:
Ejemplo
C C++ Java
public class ArrayDemo {
public static void main(String []args) {
int LA[] = new int[3];
[Link]("Array Before Insertion:");
for(int i = 0; i < 3; i++)
[Link]("LA[" + i + "] = " + LA[i]); //prints empty array
[Link]("Inserting Elements..");
// Printing Array after Insertion
[Link]("Array After Insertion:");
for(int i = 0; i < 3; i++) {
LA[i] = i+3;
[Link]("LA[" + i + "] = " + LA[i]);
}
}
}
Producción
Array Before Insertion:LA[0] = 0
LA[1] = 0
LA[2] = 0
Inserting Elements..
Array After Insertion:
LA[0] = 3
LA[1] = 4
LA[2] = 5
Para otras variaciones de la operación de inserción de matriz, haga clic aquí .
Operación de eliminación
En esta operación de matriz, eliminamos un elemento del índice particular de una matriz. Esta operación de
borrado se produce a medida que asignamos el valor del índice consecuente al índice actual.
Algoritmo
Considere que LA es una matriz lineal con N elementos y K es un número entero positivo tal que K<=N. A
continuación se muestra el algoritmo para eliminar un elemento disponible en la K- ésima posición de LA.
1. Start
2. Set J = K
3. Repeat steps 4 and 5 while J < N
4. Set LA[J] = LA[J + 1]
5. Set J = J+1
6. Set N = N-1
7. Stop
Ejemplo
Las siguientes son las implementaciones de esta operación en varios lenguajes de programación:
C C++ Java
#include <stdio.h>
void main(){
int LA[] = {1,3,5};
int n = 3;
int i;
printf("The original array elements are :\n");
for(i = 0; i<n; i++)
printf("LA[%d] = %d \n", i, LA[i]);
for(i = 1; i<n; i++) {
LA[i] = LA[i+1];
n = n – 1;
}
printf("The array elements after deletion :\n");
for(i = 0; i<n-1; i++)
printf("LA[%d] = %d \n", i, LA[i]);
}
Producción
The original array elements are :
LA[0] = 1
LA[1] = 3
LA[2] = 5
The array elements after deletion :
LA[0] = 1
LA[1] = 5
Operación de búsqueda
Buscar un elemento en la matriz usando una clave; El elemento clave compara secuencialmente cada valor
en la matriz para verificar si la clave está presente en la matriz o no.
Algoritmo
Considere que LA es una matriz lineal con N elementos y K es un número entero positivo tal que K<=N. A
continuación se muestra el algoritmo para encontrar un elemento con un valor de ELEMENTO mediante la
búsqueda secuencial.
1. Start
2. Set J = 0
3. Repeat steps 4 and 5 while J < N
4. IF LA[J] is equal ITEM THEN GOTO STEP 6
5. Set J = J +1
6. PRINT J, ITEM
7. Stop
Ejemplo
Las siguientes son las implementaciones de esta operación en varios lenguajes de programación:
C C++ Java
#include <stdio.h>
void main(){
int LA[] = {1,3,5,7,8};
int item = 5, n = 5;
int i = 0, j = 0;
printf("The original array elements are :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}
for(i = 0; i<n; i++) {
if( LA[i] == item ) {
printf("Found element %d at position %d\n", item, i+1);
}
}
}
Producción
The original array elements are :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 7
LA[4] = 8
Found element 5 at position 3
Operación transversal
Esta operación atraviesa todos los elementos de una matriz. Usamos declaraciones de bucle para llevar a
cabo esto.
Algoritmo
El siguiente es el algoritmo para atravesar todos los elementos presentes en una matriz lineal:
1 Start
2. Initialize an Array of certain size and datatype.
3. Initialize another variable ‘i’ with 0.
4. Print the ith value in the array and increment i.
5. Repeat Step 4 until the end of the array is reached.
6. End
Ejemplo
Las siguientes son las implementaciones de esta operación en varios lenguajes de programación:
C C++ Java
#include <stdio.h>
int main(){
int LA[] = {1,3,5,7,8};
int item = 10, k = 3, n = 5;
int i = 0, j = n;
printf("The original array elements are :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}
}
Producción
The original array elements are :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 7
LA[4] = 8
Actualizar operación
La operación de actualización se refiere a actualizar un elemento existente de la matriz en un índice dado.
Algoritmo
Considere que LA es una matriz lineal con N elementos y K es un número entero positivo tal que K<=N. A
continuación se muestra el algoritmo para actualizar un elemento disponible en la K-ésima posición de LA.
1. Start
2. Set LA[K-1] = ITEM
3. Stop
Ejemplo
Las siguientes son las implementaciones de esta operación en varios lenguajes de programación:
C C++ Java
#include <stdio.h>
void main(){
int LA[] = {1,3,5,7,8};
int k = 3, n = 5, item = 10;
int i, j;
printf("The original array elements are :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}
LA[k-1] = item;
printf("The array elements after updation :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}
}
Producción
The original array elements are :
LA[0] = 1
LA[1] = 3
LA[2] = 5 LA[3] = 7
LA[4] = 8
The array elements after updation :
LA[0] = 1
LA[1] = 3
LA[2] = 10
LA[3] = 7
LA[4] = 8
Operación de pantalla
Esta operación muestra todos los elementos de la matriz completa mediante una declaración de impresión.
Algoritmo
1. Start
2. Print all the elements in the Array
3. Stop
Ejemplo
Las siguientes son las implementaciones de esta operación en varios lenguajes de programación:
C C++ Java
#include <stdio.h>
int main(){
int LA[] = {1,3,5,7,8};
int n = 5;
int i;
printf("The original array elements are :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}
}
Producción
The original array elements are :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 7
LA[4] = 8
Imprimir página
