Menú

Introducción a las estructuras de datos en C ++

introduction data structures c

Pruebe Nuestro Instrumento Para Eliminar Los Problemas

Un tutorial introductorio sobre estructuras de datos en C ++.

“La estructura de datos se puede definir como una colección organizada de datos que ayuda a un programa a acceder a los datos de manera eficiente y rápida para que todo el programa pueda funcionar de manera eficiente. '

Sabemos que en el mundo de la programación, los datos son el centro y todo gira en torno a los datos. Necesitamos realizar todas las operaciones de datos, incluido el almacenamiento, la búsqueda, la clasificación, la organización y el acceso a los datos de manera eficiente y solo entonces nuestro programa puede tener éxito.

=> Consulte aquí para explorar la lista completa de tutoriales de C ++.

Introducción a las estructuras de datos en C ++ (1)

Lo que vas a aprender:

Visión general

Necesitamos encontrar la forma más eficiente de almacenar datos que pueda ayudarnos a construir soluciones dinámicas. La estructura de datos nos ayuda a construir tales soluciones.

Al organizar o ordenar los datos en estructuras, debemos asegurarnos de que la disposición represente casi un objeto del mundo real. En segundo lugar, esta disposición debe ser lo suficientemente simple para que cualquiera pueda acceder a ella fácilmente y procesarla cuando sea necesario.

En esta serie, aprenderemos en detalle acerca de la estructura de datos básica y avanzada. También aprenderemos en detalle sobre varias técnicas de búsqueda y clasificación que se pueden realizar en estructuras de datos.

Después de aprender esta serie de tutoriales, el lector debe familiarizarse con cada estructura de datos y su programación.

Repasemos algunos de los términos que usamos al tratar con estructuras de datos:

Por ejemplo,tomar un estudiante en particular. Un estudiante puede tener los siguientes detalles representados gráficamente.

Ejemplo: estructura de datos

  • Datos: Es el valor elemental. En la figura anterior, el número de lista de estudiantes puede ser un dato.
  • Elemento de grupo: Este es el elemento de datos que tiene más de un subelemento. En la figura anterior, Student_name tiene nombre y apellido.
  • Registro: Es una colección de elementos de datos. En el ejemplo anterior, los elementos de datos como el número de lista del estudiante, el nombre, la clase, la edad, el grado, etc. forman un registro juntos.
  • Entidad: Es una clase de registros. En el diagrama anterior, el estudiante es una entidad.
  • Atributo o campo: Las propiedades de una entidad se denominan atributos y cada campo representa un atributo.
  • Archivo: Un archivo es una colección de registros. En el ejemplo anterior, una entidad de estudiantes puede tener miles de registros. Por tanto, un archivo contendrá todos estos registros.

El lector debe conocer todos estos términos, ya que los usamos de vez en cuando cuando utilizamos varias estructuras de datos.

Las estructuras de datos son el bloque de construcción principal del programa y, como programadores, debemos tener cuidado con qué estructura de datos usar. La estructura de datos exacta que se utilizará es la decisión más difícil de tomar en lo que respecta a la programación.

Analicemos la necesidad de estructura de datos en programación.

Necesidad de estructura de datos en la programación

A medida que aumenta la cantidad de datos, las aplicaciones se vuelven cada vez más complejas, por lo que al programador le resulta difícil administrar estos datos y el software.

Por lo general, en cualquier momento, la aplicación puede enfrentar los siguientes obstáculos:

# 1) Búsqueda de grandes cantidades de datos: Con una gran cantidad de datos que se procesan y almacenan, es posible que en cualquier momento se requiera que nuestro programa busque datos en particular. Si los datos son demasiado grandes y no están organizados correctamente, llevará mucho tiempo obtener los datos necesarios.

Cuando usamos estructuras de datos para almacenar y organizar datos, la recuperación de datos se vuelve más rápida y sencilla.

# 2) Velocidad de procesamiento: Los datos desorganizados pueden resultar en una velocidad de procesamiento lenta, ya que se perderá mucho tiempo recuperando y accediendo a los datos.

Si organizamos los datos correctamente en una estructura de datos mientras los almacenamos, entonces no perderemos tiempo en actividades como recuperarlos y organizarlos cada vez. En cambio, podemos concentrarnos en el procesamiento de datos para producir el resultado deseado.

# 3) Solicitudes múltiples simultáneas: Muchas aplicaciones en estos días necesitan realizar una solicitud de datos simultánea. Estas solicitudes deben procesarse de manera eficiente para que las aplicaciones se ejecuten sin problemas.

Si nuestros datos se almacenan de forma aleatoria, no podremos procesar todas las solicitudes simultáneas. Por tanto, es una buena decisión organizar los datos en una estructura de datos adecuada para minimizar el tiempo de respuesta de las solicitudes simultáneas.

Clasificación de la estructura de datos

Las estructuras de datos utilizadas en C ++ se pueden clasificar de la siguiente manera.

Clasificación de estructuras de datos

Una estructura de datos es una forma de organizar los datos. Por lo tanto, podemos clasificar las estructuras de datos como se muestra en estructuras de datos primitivas o estándar y estructuras de datos no primitivas o definidas por el usuario.

Hemos visto todos los tipos de datos compatibles con C ++. Como también es una forma de organizar los datos, decimos que es una estructura de datos estándar.

Las otras estructuras de datos no son primitivas y el usuario debe definirlas antes de usarlas en un programa. Estas estructuras de datos definidas por el usuario se clasifican además en estructuras de datos lineales y no lineales.

Estructura de datos lineal

Las estructuras de datos lineales tienen todos sus elementos dispuestos de forma lineal o secuencial. Cada elemento en una estructura de datos lineal tiene un predecesor (elemento anterior) y un sucesor (elemento siguiente)

Las estructuras de datos lineales se dividen además en estructuras de datos estáticas y dinámicas. Las estructuras de datos estáticos generalmente tienen un tamaño fijo y una vez que se declara su tamaño en el momento de la compilación, no se puede cambiar. Las estructuras de datos dinámicas pueden cambiar su tamaño de forma dinámica y adaptarse a sí mismas.

El ejemplo más popular de estructura de datos estáticos lineales es una matriz.

Formación

Una matriz es una colección secuencial de elementos del mismo tipo. Se puede acceder a cada elemento de la matriz utilizando su posición en la matriz denominada índice o subíndice de la matriz. El nombre de la matriz apunta al primer elemento de la matriz.

formación

Lo que se muestra arriba es una matriz 'a' de n elementos. Los elementos están numerados de 0 a n-1. El tamaño de la matriz (n en este caso) también se denomina dimensión de la matriz. Como se muestra en la figura anterior, el nombre de la matriz apunta al primer elemento de la matriz.

La matriz es la estructura de datos más simple y es eficiente, ya que se puede acceder a los elementos usando subíndices directamente. Si queremos acceder al tercer elemento de la matriz, solo tenemos que decir a (2).

Pero agregar o eliminar los elementos de la matriz es difícil. Por lo tanto, usamos matrices solo en aplicaciones simples o en aplicaciones donde no se requiere la adición / eliminación de elementos.

Las estructuras de datos dinámicas lineales populares son la lista vinculada, la pila y la cola.

Lista enlazada

Una lista vinculada es una colección de nodos. Cada nodo contiene el elemento de datos y un puntero al siguiente nodo. Los nodos se pueden agregar y eliminar de forma dinámica. Una lista enlazada puede ser una lista enlazada individualmente en la que cada nodo tiene un puntero al siguiente elemento únicamente. Para el último elemento, el siguiente puntero se establece en nulo.

En la lista doblemente enlazada, cada nodo tiene dos punteros, uno al nodo anterior y el segundo al siguiente. Para el primer nodo, el puntero anterior es nulo y para el último nodo, el siguiente puntero es nulo.

Lista enlazada

Como se muestra en la figura anterior, el comienzo de la lista se llama cabeza mientras que el final de la lista enlazada se llama cola. Como se muestra arriba, cada nodo tiene un puntero al siguiente elemento. Podemos agregar o eliminar elementos fácilmente cambiando el puntero al siguiente nodo.

Apilar

La pila es una estructura de datos lineal en la que los elementos se pueden agregar o quitar solo desde un extremo conocido como 'Parte superior' de la pila. De esta manera, la pila exhibe el tipo de acceso a la memoria LIFO (Last In, First Out).

Apilar

Como se muestra arriba, los elementos de la pila siempre se agregan en un extremo y también se eliminan del mismo extremo. A esto se le llama el 'Top' de la pila. Cuando se agrega un elemento, se empuja hacia abajo en la pila y la parte superior de la pila se incrementa en una posición.

De manera similar, cuando se elimina un elemento, la parte superior de la pila disminuye. Cuando una pila está vacía, la parte superior de la pila se establece en -1. Hay dos operaciones principales, 'Push' y 'Pop', que se realizan en la pila.

Cola

La cola es otra estructura de datos lineal en la que los elementos se agregan en un extremo llamado 'posterior' y se eliminan desde el otro extremo llamado 'frontal'. Queue demuestra FIFO (First In, First Out) el tipo de metodología de acceso a la memoria.

Cola

El diagrama de arriba muestra una cola con los extremos delantero y trasero. Cuando la cola está vacía, los punteros posterior y frontal coinciden entre sí.

Estructura de datos no lineal

En las estructuras de datos no lineales, los datos no se organizan secuencialmente, sino que se organizan de forma no lineal. Los elementos están conectados entre sí en una disposición no lineal.

Las estructuras de datos no lineales son árboles y gráficos.

mejor software de clonación de disco windows 10

Árboles

Los árboles son estructuras de datos multinivel no lineales que tienen una relación jerárquica entre los elementos. Los elementos del árbol se denominan Nodos.

El nodo en la parte superior se llama raíz del árbol. La raíz puede tener uno o más nodos secundarios. Los nodos posteriores también pueden tener uno o más nodos secundarios. Los nodos que no tienen nodos secundarios se denominan nodos hoja.

Árboles

En el diagrama anterior, mostramos un árbol con 6 nodos. De estos tres nodos son los nodos hoja, un nodo superior es la raíz y los otros son nodos secundarios. Dependiendo del número de nodos, nodos secundarios, etc. o de la relación entre los nodos, tenemos diferentes tipos de árboles.

Gráficos

El gráfico es un conjunto de nodos llamado vértices conectados entre sí mediante los enlaces denominados Bordes . Los gráficos pueden tener un ciclo dentro de ellos, es decir, el mismo vértice puede ser un punto de partida y también el punto final de una ruta en particular. Los árboles nunca pueden tener un ciclo.

Gráficos

El diagrama de arriba es un gráfico no dirigido. También podemos tener gráficos dirigidos donde representamos los bordes usando flechas dirigidas.

Operaciones en la estructura de datos

Todas las estructuras de datos realizan diversas operaciones sobre sus elementos.

Estos son comunes a todas las estructuras de datos y se enumeran a continuación:

  • Buscando: Esta operación se realiza para buscar un elemento o una clave en particular. Los algoritmos de búsqueda más comunes son la búsqueda secuencial / lineal y la búsqueda binaria.
  • Clasificación: La operación de clasificación implica organizar los elementos en una estructura de datos en un orden particular, ya sea ascendente o descendente. Hay varios algoritmos de clasificación disponibles para estructuras de datos. Los más populares son Quicksort, Selection sort, Merge sort, etc.
  • Inserción: La operación de inserción se ocupa de agregar un elemento a la estructura de datos. Esta es la operación más importante y, como resultado de la adición de un elemento, la disposición cambia y debemos cuidar que la estructura de datos permanezca intacta.
  • Supresión: La operación de eliminación elimina un elemento de la estructura de datos. Las mismas condiciones que se tienen en cuenta para la inserción también deben cumplirse en el caso de la operación de eliminación.
  • Atravesando: Decimos que atravesamos una estructura de datos cuando visitamos todos y cada uno de los elementos de la estructura. Se requiere atravesar para realizar ciertas operaciones específicas en la estructura de datos.

En los temas siguientes, primero aprenderemos las diversas técnicas de búsqueda y clasificación que se realizarán en estructuras de datos.

Ventajas de la estructura de datos

  • Abstracción: Las estructuras de datos se implementan a menudo como tipos de datos abstractos. Los usuarios solo acceden a su interfaz externa sin preocuparse por la implementación subyacente. Por tanto, la estructura de datos proporciona una capa de abstracción.
  • Eficiencia: La organización adecuada de los datos da como resultado un acceso eficiente a los datos, lo que hace que los programas sean más eficientes. En segundo lugar, podemos seleccionar la estructura de datos adecuada en función de nuestros requisitos.
  • Reutilización: Podemos reutilizar las estructuras de datos que hemos diseñado. También pueden compilarse en una biblioteca y distribuirse al cliente.

Conclusión

Con esto, concluimos este tutorial sobre introducción a las estructuras de datos. Hemos presentado brevemente cada una de las estructuras de datos en este tutorial.

En nuestros tutoriales posteriores, exploraremos más sobre las estructuras de datos junto con las diversas técnicas de búsqueda y clasificación.

=> Haga clic aquí para ver la serie de capacitación Absolute C ++.

Lectura recomendada

^