Estructuras de datos - Arreglos
Los arreglos (Array) son una de las estructuras de datos más básicas y más utilizadas.
Un arreglo es un conjunto de elementos del mismo tipo almacenados de forma contigua en memoria.
Definición de arreglos y disposición en memoria
En C, después de declarar un arreglo, se asigna un bloque contiguo de memoria, y cada elemento puede accederse directamente mediante un índice.
La figura anterior muestra la disposición en memoria de un arreglo de 5 elementos int. Supongamos que la dirección inicial es 0x1000 y cada int ocupa 4 bytes; entonces:
- arr[0]Se encuentra en la dirección 0x1000
- arr[1]Se encuentra en la dirección 0x1004 (0x1000 + 4)
- arr[i]Se encuentra en la dirección 0x1000 + i × 4
Es precisamente por esta característica de almacenamiento contiguo que el arreglo puede, mediantedirección inicial + desplazamientoacceder a cualquier elemento en tiempo O(1).
Arreglos unidimensionales
Ejemplo
int main() {
/* Declarar e inicializar un arreglo unidimensional */
int arr[5] = {10, 20, 30, 40, 50};
/* Recorrer y acceder a cada elemento */
printf("Elementos del arreglo: ");
for (int i = 0; i < 5; i++) {
printf("%d ", arr[i]);
}
printf("\n"); /* Salida: Elementos del arreglo: 10 20 30 40 50 */
/* Acceso directo mediante índice, complejidad temporal O(1) */
printf("arr[2] = %d\n", arr[2]); /* Salida: 30 */
return 0;
}
Arreglos multidimensionales
C admite arreglos multidimensionales; el más común es el arreglo bidimensional, utilizado a menudo para representar datos tabulares como matrices.
Los arreglos bidimensionales se almacenan de forma contigua por filas en memoria (almacenamiento en orden de filas); mediante el cálculo de índices de fila y columna se mapean como una vista bidimensional.
Ejemplo
int main() {
/* Declarar un arreglo bidimensional de 3 filas y 4 columnas */
int matrix[3][4] = {
{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12}
};
/* Recorrer el arreglo bidimensional: el bucle externo recorre las filas, el bucle interno recorre las columnas */
printf("Arreglo bidimensional (matriz 3×4):\n");
for (int i = 0; i < 3; i++) { /* i es el índice de fila */
for (int j = 0; j < 4; j++) { /* j es el índice de columna */
printf("%2d ", matrix[i][j]);
}
printf("\n");
}
/* Acceder a un elemento específico: matrix[fila][columna] */
printf("matrix[1][2] = %d\n", matrix[1][2]); /* Salida: 7 */
return 0;
}
Fórmula de cálculo de dirección de memoria para arreglos bidimensionales:
元素地址 = 起始地址 + (i × 列数 + j) × sizeof(元素类型). Donde i es el índice de fila y j es el índice de columna.
Operaciones básicas con arreglos
La figura anterior muestra los pasos clave de las operaciones de inserción y eliminación en un arreglo: al insertar, los elementos posteriores a la posición objetivo deben desplazarse hacia atrás para hacer espacio; al eliminar, los elementos posteriores a la posición objetivo deben desplazarse hacia adelante para llenar el vacío.
Recorrido
Ejemplo
/* Recorrer e imprimir todos los elementos del arreglo
Complejidad temporal: O(n), donde n es la longitud del arreglo */
void traverse(int arr[], int n) {
printf("Resultado del recorrido: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {15, 28, 43, 56, 71};
int n = sizeof(arr) / sizeof(arr[0]); /* Calcular la longitud del arreglo */
traverse(arr, n);
return 0;
}
Inserción
Ejemplo
/* Insertar un elemento en una posición determinada del arreglo
Parámetros: arr arreglo, n número actual de elementos, pos posición de inserción (basada en 0),
value valor a insertar, capacity capacidad total del arreglo
Complejidad temporal: O(n); en el peor caso es necesario mover n elementos
Valor de retorno: número de elementos después de la inserción; devuelve -1 si la capacidad es insuficiente */
int insert(int arr[], int n, int pos, int value, int capacity) {
if (n >= capacity) {
printf("El arreglo está lleno, no se puede insertar\n");
return -1;
}
if (pos < 0 || pos > n) {
printf("Posición de inserción no válida\n");
return -1;
}
/* De atrás hacia adelante, desplazar una posición hacia atrás los elementos desde pos en adelante */
for (int i = n; i > pos; i--) {
arr[i] = arr[i - 1];
}
arr[pos] = value; /* Escribir el dato en la nueva posición */
return n + 1; /* Incrementar en 1 el número de elementos */
}
int main() {
int arr[10] = {10, 20, 30, 40}; /* Capacidad de 10; actualmente hay 4 elementos */
int n = 4;
printf("Antes de insertar: "); for (int i = 0; i < n; i++) printf("%d ", arr[i]);
printf("\n"); /* Salida: Antes de insertar: 10 20 30 40 */
n = insert(arr, n, 2, 25, 10); /* Insertar 25 en el índice 2 */
printf("Después de insertar: "); for (int i = 0; i < n; i++) printf("%d ", arr[i]);
printf("\n"); /* Salida: Después de insertar: 10 20 25 30 40 */
return 0;
}
Eliminación
Ejemplo
/* Eliminar el elemento de una posición determinada del arreglo
Parámetros: arr arreglo, n número actual de elementos, pos posición de eliminación (basada en 0)
Complejidad temporal: O(n); en el peor caso es necesario mover n elementos
Valor de retorno: número de elementos después de la eliminación */
int delete(int arr[], int n, int pos) {
if (n <= 0) {
printf("El arreglo está vacío, no se puede eliminar\n");
return 0;
}
if (pos < 0 || pos >= n) {
printf("Posición de eliminación no válida\n");
return n;
}
/* De adelante hacia atrás, desplazar una posición hacia adelante los elementos posteriores a pos */
for (int i = pos; i < n - 1; i++) {
arr[i] = arr[i + 1];
}
return n - 1; /* Decrementar en 1 el número de elementos */
}
int main() {
int arr[10] = {10, 20, 30, 40, 50};
int n = 5;
printf("Antes de eliminar: "); for (int i = 0; i < n; i++) printf("%d ", arr[i]);
printf("\n"); /* Salida: Antes de eliminar: 10 20 30 40 50 */
n = delete(arr, n, 2); /* Eliminar el elemento en el índice 2 (30) */
printf("Después de eliminar: "); for (int i = 0; i < n; i++) printf("%d ", arr[i]);
printf("\n"); /* Salida: Después de eliminar: 10 20 40 50 */
return 0;
}
Búsqueda
Para buscar un valor objetivo en un arreglo desordenado, el método más directo es recorrer todo el arreglo y comparar uno por uno; esto se conoce como búsqueda lineal.
Ejemplo
/* Búsqueda lineal: buscar un valor objetivo en el arreglo
Complejidad temporal: O(n); en el peor caso hay que recorrer todo el arreglo
Valor de retorno: índice del elemento buscado; devuelve -1 si no se encuentra */
int search(int arr[], int n, int target) {
for (int i = 0; i < n; i++) {
if (arr[i] == target) {
return i; /* Encontrado, devolver el índice */
}
}
return -1; /* No encontrado */
}
int main() {
int arr[] = {43, 17, 89, 25, 61};
int n = 5;
int idx = search(arr, n, 89);
if (idx != -1) {
printf("Valor objetivo 89 encontrado, índice %d\n", idx); /* Salida: Valor objetivo 89 encontrado, índice 2 */
} else {
printf("Valor objetivo no encontrado\n");
}
return 0;
}
Ventajas y desventajas de los arreglos
| Ventajas | Descripción |
|---|---|
| Acceso aleatorio O(1) | Se puede acceder a cualquier elemento en tiempo constante mediante el índice; esta es la mayor ventaja de los arreglos. |
| Memoria contigua | El almacenamiento contiguo favorece el acierto de la caché de la CPU (localidad espacial), mejorando la eficiencia de acceso. |
| Implementación sencilla | Sintaxis intuitiva; es un tipo compatible de forma nativa en la mayoría de los lenguajes de programación. |
| Desventajas | Descripción |
|---|---|
| Tamaño fijo | En C, los arreglos estáticos tienen su tamaño definido en tiempo de compilación y no pueden expandirse dinámicamente. |
| Inserción/eliminación lentas | Al insertar o eliminar elementos en el medio de un arreglo, es necesario mover muchos elementos; la complejidad temporal es O(n). |
| Desperdicio de espacio | Si el arreglo declarado es demasiado grande y se utiliza poco, se produce un desperdicio de memoria. |
Precisamente estas limitaciones dan lugar a una estructura dinámica más flexible que se estudiará en el siguiente capítulo:listas enlazadas。
Resumen de complejidad de operaciones
| Operación | Complejidad temporal | Descripción |
|---|---|---|
| Acceso por índice | O(1) | Cálculo directo de la dirección |
| Inserción al final | O(1) | No es necesario mover elementos |
| Inserción al inicio/en el medio | O(n) | Es necesario mover los elementos posteriores |
| Eliminación del último elemento | O(1) | No es necesario mover elementos |
| Eliminación del primer elemento/central | O(n) | Es necesario mover los elementos posteriores |
| Búsqueda lineal | O(n) | Comparar uno por uno |
| Búsqueda binaria (arreglo ordenado) | O(log n) | Requiere que el arreglo esté ordenado |