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

#include <stdio.h>

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

#include <stdio.h>

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

#include <stdio.h>

/* 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

#include <stdio.h>

/* 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

#include <stdio.h>

/* 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

#include <stdio.h>

/* 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

VentajasDescripció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 contiguaEl almacenamiento contiguo favorece el acierto de la caché de la CPU (localidad espacial), mejorando la eficiencia de acceso.
Implementación sencillaSintaxis intuitiva; es un tipo compatible de forma nativa en la mayoría de los lenguajes de programación.
DesventajasDescripción
Tamaño fijoEn 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 lentasAl insertar o eliminar elementos en el medio de un arreglo, es necesario mover muchos elementos; la complejidad temporal es O(n).
Desperdicio de espacioSi 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ónComplejidad temporalDescripción
Acceso por índiceO(1)Cálculo directo de la dirección
Inserción al finalO(1)No es necesario mover elementos
Inserción al inicio/en el medioO(n)Es necesario mover los elementos posteriores
Eliminación del último elementoO(1)No es necesario mover elementos
Eliminación del primer elemento/centralO(n)Es necesario mover los elementos posteriores
Búsqueda linealO(n)Comparar uno por uno
Búsqueda binaria (arreglo ordenado)O(log n)Requiere que el arreglo esté ordenado
Otras extensiones