Laboratorio 5

Introducción

En este laboratorio trabajaremos con arreglos unidimensionales, bidimensionales y strings (cadenas de caracteres), que son un
caso particular de arreglos unidimensionales

Arrays

Un array es básicamente un conjunto de datos de un mismo tipo, que están adyacentes en memoria.
Para ver una definición más técnica, click aquí.

Para declarar un array, lo que se hace es definir su nombre, tipo y cantidad de elementos que contendrá, por ejemplo:
int array[5]

Dicho array contendrá 5 elementos de tipo entero y su nombre será "array". Si se desea inicializar un array, se puede
de la siguiente forma:

int array[5] = {0, 1, 2, 3, 4}

Ello significa que el primer elemento será array[0] = 0
el segundo elemento será array[1] = 1
El tercer elemento será array[2] = 3
El cuarto elemento será array[3] = 4
El quinto elemento será array[4] = 5

De aquí, podemos concluir:

array[0] // Acceder al primer elemento del array
array[N - 1] // Acceder al ultimo elemento de un array de tamanho N

Cabe destacar que los array pueden ser de mayores dimensiones, como por ejemplo una matriz. Una matriz
podría considerarse como un array de arrays. Por ejemplo, si quisieramos la siguiente matriz de enteros:

Matriz Ejemplo

En c se declararía de la siguiente forma:

int matriz[3][3] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};

Puede observarse que se declara como un array, donde cada elemento del array, es un array de por sí.
Y podríamos acceder al elemento de la fila i y la columna j mediante matriz[i][j].

Strings (o cadenas de caracteres)

Ahora que entendemos arrays, podemos entender lo que es un string o cadena.
Básicamente, una cadena es un array de caracteres, donde el último elemento es el caracter nulo '\0'
Este caracter, le sirve al computador para saber dónde termina el string. Tener este caracter extra
trae como consecuencia que para almacenar una frase o palabra de N caracteres, se necesita un array
tipo char de N + 1 elementos, pues se requiere un espacio extra para el caracter nulo. Por ejemplo suponga
el siguiente string: hola mundo
Para que esté correctamente definido, debiese estar de la siguiente forma:

char[11] = "hola mundo\0";

Algunos comentarios aparte, para leer un string como entrada, tiene las siguientes opciones:

char string[40];
scanf("%s", string);
gets(string);
fgets(string, 40, stdin);

La primera es la que menos sirve, pues hay problemas con los espacios. Existen formas de solventar este problema y utilizar
scanf, pero requiere uso de expresiones regulares (concepto más avanzado y no es recomendable para un curso introductorio y tampoco es buena solución).
La segunda forma, permite solventar el problema de los espacios que tiene scanf, pero es mala práctica, pues no asegura que se lea
una cantidad de caracteres limitada al tamaño del string. Esto podría traer consecuencias desastrozas para los programas.
La última forma es la "aceptada" en la práctica, debido a que la función fgets, leerá N - 1 caracteres, si es que no se encuentra
un salto de línea o EOF. Ello permite asegurar que no ocurran errores como "salirse de los límites del array". Cabe destacar
que la función puede agregar un salto de línea al final del string (el cual es simple de eliminar). Para más información de fgets
Click aquí.

Algunos Ejercicios Resueltos

Ejercicio 1

Dados los arreglos: a {0, 1, 2, 3, 4} y b {5, 6, 7, 8, 9}, escriba un programa en C que:

Muestre en pantalla dichos arreglos utilizando un ciclo for.
Genere un nuevo arreglo llamado c, a partir de los arreglos a y b.

#include <stdio.h>

int main(void)
{
    int a[5] = {0, 1, 2, 3, 4}, b[5] = {5, 6, 7, 8, 9}, c[2][5], i, j;

    /* Mostrar arreglos */
    printf("El arreglo a: ");
    for (i = 0; i < 5; i++)
    {
        printf("%5d ", a[i]);
    }

    printf("\nEl arreglo b: ");
    for (i = 0; i < 5; i++)
    {
        printf("%5d ", b[i]);
    }

    /* Llenar arreglo c */
    for (i = 0; i < 5; i++)
    {
        c[0][i] = a[i];
        c[1][i] = b[i];
    }

    /* Mostrar arreglo c*/
    printf("\n\nMostramos arreglo c: \n");
    for (i = 0; i < 2; i++)
    {
        for (j = 0; j < 5; j++)
        {
            printf("%5d ", c[i][j]);
        }
        printf("\n");
    }
    return 0;
}

Ejercicio 2

Escriba un programa que calcule el producto escalar de 2 arreglos de largo 3. Ingrese cada uno de los valores
de los dos arreglos por teclado e imprima el resultado en pantalla.

#include <stdio.h>

int main(void)
{
    int v1[3], v2[3], prod, i;

    printf("Ingrese los elementos del arreglo 1: ");
    scanf("%d %d %d", &v1[0], &v1[1], &v1[2]);

    printf("Ingrese los elementos del arreglo 2: ");
    scanf("%d %d %d", &v2[0], &v2[1], &v2[2]);

    for (i = 0, prod = 0; i < 3; i++)
        prod += v1[i]*v2[i];

    printf("El producto escalar es: %d.\n", prod);
    return 0;
}

Ejercicio 3

Escriba un programa que implemente la multiplicación de matrices. Para ello defina 2 matrices A y B,
ambas de 3x3, inicialice sus valores, y luego guarde el resultado de la multiplicación en una tercera
matriz C. Imprima las matrices y verifique sus resultados.

#include <stdio.h>

/**
 * Funcion para imprimir matrices en dispositivo de salida.
 * @param: m, es la matriz de 3x3 a imprimir.
*/
void imprimir_matriz(int m[3][3])
{
    int i, j;
    for (i = 0; i < 3; i++)
    {
        for (j = 0; j < 3; j++)
        {
            printf("%5d ", m[i][j]);
        }
        printf("\n");
    }
}

int main(void)
{
    int A[3][3] = {{1, 2, 3},
                   {4, 5, 6},
                   {1, 0, 3}};

    int B[3][3] = {{1, 4, 3},
                   {10, 2, 6},
                   {1, 0, 3}};

    int C[3][3], i, j;

    for (i = 0; i < 3; i++)
    {
        for (j = 0; j < 3; j++)
        {
            /* Queda de ejecicio pensar como seria para matrices de tamanho arbitrario */
            C[i][j] = A[i][0]*B[0][j] + A[i][1]*B[1][j] + A[i][2]*B[2][j];
        }
    }

    /* Imprimir matrices */
    imprimir_matriz(A);
    printf("\n\n");
    imprimir_matriz(B);
    printf("\n\n");
    imprimir_matriz(C);
    return 0;
}

Ejercicio 4

Escriba una función en C que dado un arreglo de enteros, un valor X y el largo del arreglo, busque X
en el arreglo. La función debe imprimir en pantalla si encontró X y en qué posición.

#include <stdio.h>

/**
 * Buscar un elemento en un arreglo
 * @param: arreglo[] es un array tipo int, en el cual se realizara la busqueda
 * @param: n, es el largo del arreglo
 * @param: valor, es el valor a buscar (int)
 */
void buscar_elemento(int arreglo[], int n, int valor)
{
    int i;
    for (i = 0; i < n; i++)
    {
        if (valor == arreglo[i])
        {
            printf("Se encontro %d en la posicion %d.\n", valor, i);
            return;
        }
    }
    printf("No se encontro %d.\n", valor);
}

int main(void)
{
    int v[10] = {2, 4, 6, -5, 8, 10, 15, 18, 101, 42};

    /* Testear funcion */
    buscar_elemento(v, 10, 2);
    buscar_elemento(v, 10, 3);
    buscar_elemento(v, 10, -5);
    buscar_elemento(v, 10, 19);
    buscar_elemento(v, 10, 42);
    return 0;
}

Ejercicio 5

Implemente un programa que:

Ordene un vector de manera ascendente.
Implemente Binary Search para encontrar X en un arreglo ordenado.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stdbool.h>

// Prototipo de funciones
void imprimirArray(int[], int);
void sort(int[], int);
bool binarySearch(int[], int, int);
bool search(int[], int, int, int);
bool recursiveBinarySearch(int[], int, int);

int main(void)
{
    // array de 15 elementos para testear funciones
    int array[15], i;

    // Seed para llamar a la funcion random
    srand((unsigned int)time(NULL));

    // Inicializar un array con elementos aleatoreos
    for (i = 0; i < 15; i++)
    {
        array[i] = rand() % 119;
    }


    // Mostrar array y array ordenado
    printf("El arreglo inicialmente es:\n\n");
    imprimirArray(array, 15);
    sort(array, 15);
    printf("\nEl arreglo ordenado: \n\n");
    imprimirArray(array, 15);
    printf("\n\n*********************\n");
    printf("Buscando elementos\n");
    printf("*********************\n");

    // Buscar que elementos se encuentran en el array e imprimirlos
    for (i = 0; i <= 118; i++)
    {
        if (binarySearch(array, 15, i))
        {
            printf("%d esta en el vector.\n", i);
        }

        if (recursiveBinarySearch(array, 15, i))
        {
            printf("%d esta en el vector.\n\n", i);
        }
    }
    return 0;
}

/**
 * Muestra un array en consola
 * @array: Es el array a mostrar
 * @N: es el largo del array
 */
void imprimirArray(int array[], int N)
{
    int i;
    for (i = 0; i < N; i++)
    {
        printf("%3d ", array[i]);
    }
    printf("\n");
}

/**
 * Ordena un array en forma ascendente usando estrategia min-sort (O(n^2))
 * @array: Es el array a ordenar
 * @N: es el largo del array
 */
void sort(int array[], int N)
{
    int i, j, min;
    for (i = 0; i < N; i++)
    {
        min = i;
        for (j = i; j < N; j++)
        {
            // Busca la posicion del elemento con el minimo valor entre i y N-1
            if (array[j] < array[min])
            {
                min = j;
            }
        }

        // Pone el valor minimo en la posicion i.
        int tmp = array[i];
        array[i] = array[min];
        array[min] = tmp;
    }
}

/**
 * Busca un valor en el array, con binary search iterativo
 * @array: Es el array
 * @N: es el largo del array
 * @value: es el valor a buscar
 */
bool binarySearch(int array[], int N, int value)
{
    int lo = 0, hi = N - 1, mid;
    while (lo <= hi)
    {
        mid = (lo + hi) / 2;
        if (value > array[mid])
        {
            lo = mid + 1;
        }
        else if (value < array[mid])
        {
            hi = mid - 1;
        }
        else
        {
            return true;
        }
    }
    return false;
}

/**
 * Funcion auxiliar para aplicar binary search recursivo
 * @array: Es el array
 * @value: es el valor a buscar
 * @lo: Es el limite inferior de la busqueda
 * @hi: Es el limite superior de la busqueda
 */
bool search(int array[], int value, int lo, int hi)
{
    if (lo > hi) return false;

    int mid = (lo + hi) / 2;
    if (value > array[mid])
        return search(array, value, mid + 1, hi);
    else if (value < array[mid])
        return search(array, value, lo, mid - 1);
    else
        return true;
}

/**
 * Busca un valor en el array, con binary search recursivo
 * @array: Es el array
 * @N: es el largo del array
 * @value: es el valor a buscar
 */
bool recursiveBinarySearch(int array[], int N, int value)
{
    return search(array, value, 0, N - 1);
}

Ejercicio 11

Escriba un programa donde se pida ingresar una palabra (nombre de persona, nombre de objeto, etc.) y
que invierta el orden los elementos e imprime la palabra invertida.

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    char palabra[20], invertida[20], i, size;

    fgets(palabra, 20, stdin);

    // Calcular el largo del string ingresado
    for (size = 0; palabra[size] != '\0'; size++);

    // fgets se detiene hasta leer n - 1 caracteres o '\n'.
    // Podemos eliminar el salto de linea de la sgte forma
    if (palabra[size - 1] == '\n')
    {
        palabra[size - 1] = '\0';
        size--;
    }


    for (i = size - 1; i >= 0; i--)
    {
        invertida[size - 1 - i] = palabra[i];
    }
    invertida[size] = '\0';
    printf("Ud. ingreso:\n%s\nEl largo de su string es %d. Su string invertido es\n%s\n", palabra, size, invertida);
    return 0;
}

Ejercicio 12

Escriba un programa donde se ingrese una frase y esta sea dividida en sus palabras e imprima cada una por separado:

#include <stdio.h>
#include <string.h>

int main(void)
{
    char buffer[100];

    printf("Ingrese un texto:\n");
    // Leer string desde stdin (basicamente input del usuario)
    fgets(buffer, 100, stdin);

    // strlen calcula largo de string (se encuentra en string.h)
    int len = strlen(buffer);
    if (buffer[len - 1] == '\n')
    {
        buffer[len - 1] = '\0';
        len--;
    }

    for (int i = 0, first = 0; i < len; i++)
    {
        // Consumir espacios
        if (buffer[i] == ' ')
        {
            while(buffer[i++] == ' ');
            if (first != 0 && i < len) putchar('\n');
            i--;
        }
        // Imprimir caracter (comportamiento similar a printf("%c", buffer[i]);
        putchar(buffer[i]);
        first = 1;

    }
    return 0;
}