Guía de algoritmos y estructuras de datos: introducción y configuración del entorno

Las estructuras de datos son una forma de organizar sistemáticamente los datos para un uso eficiente. Varios tipos de estructuras de datos se utilizan de una forma u otra en casi todas las aplicaciones empresariales. Después de completar este tutorial, tendrá una sólida comprensión de las estructuras de datos, lo cual es esencial para comprender la complejidad de las aplicaciones empresariales.

Los siguientes términos son básicos para una estructura de datos:

• Una interfaz es  un conjunto de operaciones soportadas por una estructura de datos. Cada estructura de datos lo tiene. La interfaz proporciona solo una lista de operaciones admitidas, el tipo de parámetros que aceptan y el tipo de devolución de esas operaciones.
• Implementación:  proporciona la representación interna de la estructura de datos, así como la definición de los algoritmos utilizados en las operaciones de la estructura de datos.

¿Por qué estudiar estructuras de datos y algoritmos?

Con el crecimiento del volumen de datos y la complejidad de las aplicaciones modernas, existen tres desafíos principales:

• Búsqueda de datos. Digamos que necesitamos inventariar 1 millón (1⁰⁶) de elementos en un repositorio. Si se lo confías a la aplicación, cada vez la búsqueda de un elemento entre tantos será más lenta, porque la cantidad de datos es cada vez mayor.
• La velocidad del procesador, aunque muy alta, se vuelve limitada a medida que los datos crecen a mil millones de registros.
• Múltiples solicitudes. Si miles de usuarios buscan datos al mismo tiempo, incluso un servidor web rápido fallará.

Las estructuras de datos ayudan a resolver estos problemas, que están organizadas de manera que no es necesario buscar entre todos los elementos y los datos necesarios se encuentran casi al instante.

Con la ayuda de estructuras de datos, las siguientes tareas se resuelven mediante programación:

• secuencia de números de Fibonacci;
• problema de la mochila;
• Torre de Hanoi;
• encontrar el camino más corto entre todos los pares de vértices (el algoritmo de Floyd-Warshall);
• buscar los caminos más cortos desde uno de los vértices del gráfico a todos los demás (algoritmo de Dijkstra);
• planificación de proyectos.

Características de la estructura de datos

• Exactitud. La interfaz de la estructura de datos debe implementarse correctamente.
• Complejidad del tiempo. El tiempo de ejecución de las operaciones de estructura de datos debe ser lo más corto posible.
• Complejidad espacial. El uso de memoria de una operación de estructura de datos debe ser lo más bajo posible.

Casos de tiempo de ejecución

Generalmente se utilizan tres casos para comparar los tiempos de ejecución de diferentes estructuras de datos:

• El peor de los casos  es el escenario en el que una operación de estructura de datos en particular lleva el mayor tiempo posible. Si el tiempo de operación en el peor de los casos es ƒ(n) , entonces la operación tomará como máximo ƒ(n) tiempo, donde ƒ(n)  es una función de n.
• El caso promedio  es un escenario que describe el tiempo promedio para completar una operación en una estructura de datos. Si una operación toma ƒ(n) tiempo, entonces m operaciones toman mƒ(n) tiempo.
• El mejor de los casos  es el escenario que describe el tiempo de ejecución mínimo posible para una operación de estructura de datos. Si la operación tarda ƒ(n) tiempo en completarse, entonces la operación real puede tardar un tiempo, indicado por un número aleatorio, cuyo máximo será ƒ(n) .

Aplicación de estructuras de datos y algoritmos.

Un algoritmo es un procedimiento paso a paso que define un conjunto de instrucciones que se ejecutarán en un orden u otro para producir un resultado deseado. Los algoritmos generalmente se crean independientemente de los lenguajes de programación subyacentes, es decir, con la posibilidad de implementación en varios lenguajes.

En términos de estructuras de datos, las siguientes categorías de algoritmos son importantes:

• Algoritmo para encontrar un elemento en una estructura de datos.
• Un algoritmo para ordenar elementos en un orden específico.
• Algoritmo para insertar un elemento en una estructura de datos.
• Algoritmo para cambiar un elemento presente en la estructura de datos.
• Algoritmo para eliminar un elemento de una estructura de datos.

Terminología básica

• Los datos  son valores o un conjunto de valores.
• Un elemento de datos  es una sola unidad de valor.
• Los elementos de grupo  son elementos de datos divididos en subelementos denominados elementos de grupo.
• Los elementos más simples  son elementos de datos indivisibles, que se denominan primitivos.
• Atributo y esencia. Una entidad es algo que contiene ciertos atributos o propiedades a los que se les pueden asignar valores.
• Un conjunto  de entidades son entidades con atributos similares.
• Un campo  es una sola unidad elemental de información que es un atributo de una entidad.
• Un registro  es un conjunto de valores de campo de entidad.
• Un archivo  es una colección de registros de entidades en un conjunto de entidades.

las condiciones necesarias

Antes de comenzar esta serie de tutoriales, debe tener una comprensión básica del lenguaje de programación C, el editor de texto, la ejecución del programa, etc.

Configuración del entorno local.

¿Listo para configurar su entorno para el lenguaje de programación C? Entonces necesitará las dos herramientas siguientes: 1. un editor de texto y 2. un compilador de C.

Editor de texto

Un editor de texto (como el Bloc de notas de Windows, el comando de edición del sistema operativo, Brief, Epsilon, EMACS, Vim o Vi) escribirá el programa.

El nombre y la versión del editor de texto pueden variar en diferentes sistemas operativos. Por lo tanto, el Bloc de notas se usa en Windows y Vim o Vi se usan en Windows y UNIX.

Los archivos creados con el editor se denominan archivos fuente y contienen el código fuente del programa. Los archivos fuente C generalmente tienen la extensión  .c.

Para comenzar a programar, aparte de un editor de texto, debe tener suficiente experiencia para escribir un programa de computadora, guardarlo en un archivo, compilarlo y ejecutarlo.

Compilador de C

El código fuente escrito en el archivo fuente es una fuente legible por humanos del programa. Debe compilarse, traducirse a lenguaje de máquina, para que el procesador pueda ejecutar el programa de acuerdo con las instrucciones dadas.

El compilador del lenguaje de programación C se utilizará para compilar el código fuente en el programa ejecutable final Se supone que tiene un conocimiento básico del mismo.

El compilador más usado y disponible es GNU C/C++. Una opción alternativa son los compiladores de HP o Solaris si tiene el sistema operativo (SO) apropiado.

Y ahora comencemos a instalar el compilador GNU C / C ++ en varios sistemas operativos. C y C++ se enumeran juntos por una razón, porque el compilador GNU GCC funciona en ambos lenguajes de programación.

Instalación en UNIX/Linux

¿Está utilizando el sistema operativo UNIX ? Luego verifique si GCC está instalado en su computadora escribiendo:

$ gcc -v

Si el compilador GNU ya está instalado, debería aparecer un mensaje similar:

Using built-in specs.
Target: i386-redhat-linux
Configured with: ../configure --prefix = /usr .......
Thread model: posix
gcc version 4.1.2 20080704 (Red Hat 4.1.2-46)

De lo contrario, deberá instalar GCC usted mismo (las instrucciones detalladas están disponibles aquí en inglés: https://gcc.gnu.org/install/ ).

Instalación en Mac OS

La forma más sencilla de instalar GCC es descargar el entorno de desarrollo Xcode de Apple y seguir las sencillas instrucciones de instalación. Después de configurar Xcode, podrá usar el compilador GNU para C/C++.

Xcode está disponible aquí: developer.apple.com/technologies/tools/ .

Instalación en Windows

Para obtener GCC en Windows, debe instalar MinGW. Para hacer esto, vaya a la página de inicio de MinGW y siga el enlace a la página de descarga. Descargue el último instalador de MinGW llamado MinGW-<versión>.exe .

Mínimo requerido al instalar MinWG: gcc-core, gcc-g++, binutils y el tiempo de ejecución de MinGW, pero puede ir más allá e instalar algo más.

Agregue el subdirectorio bin de su instalación de MinGW a su variable de entorno PATH para hacer referencia a estas herramientas en la línea de comando por sus nombres simples.

Una vez completada la instalación, podrá ejecutar gcc , g++ , ar , ranlib , dlltool y otras herramientas GNU desde la línea de comandos de Windows.