BlogWonderHowTo

Tutorial de C orientado a la seguridad 0x21 – Listas vinculadas

Bienvenido al tutorial final de la serie sobre el estándar C. Este artículo cubrirá el lista enlazada tipo de datos abstractos (ADT). Habrá mucha abstracción para tratar de entregar la comprensión de la manera más básica para una interpretación más fácil de qué son y cómo funcionan, luego entraremos en las entrañas y aprenderemos el código técnico subyacente. Para aquellos que aún no han comprendido el concepto de punteros, es aconsejable que lo hagan antes de abordar esto. Habiendo aprendido esto en mis etapas iniciales, fue una experiencia increíblemente espantosa e insoportable, por lo que si siente que está completamente perdido y no tiene la menor idea de lo que está sucediendo, entonces eso es aceptable, solo tendrá que abrocharse el cinturón e intentarlo. tu mejor. También intentaré lo mejor que pueda para que esto sea lo más comprensible que pueda. ¡Aquí vamos y buena suerte!

¿Qué es una lista vinculada?

Como se dijo anteriormente, un lista enlazada es un tipo de datos abstracto, una estructura de datos que se asemeja a algo como un línea de conga, un conjunto de datos dispuestos linealmente que representa de cerca el tipo de datos de la matriz. La lista vinculada consta de objetos llamados nodos, como los elementos de una matriz, y tienen dos secciones: los datos y los punteros. La porción de datos contiene cualquier cantidad de cualquier tipo de datos, como una cadena, un valor int, lo que sea. La parte de puntero (s) tiene un valor de puntero a otros nodos si existen. Solo usaremos un puntero para apuntar al siguiente nodo. Así es como se ve una lista enlazada:

Podemos ver las dos mitades de los nodos que contienen los datos y el puntero al siguiente nodo. Estaremos usando el X para mostrar el final de la lista, es decir, el último puntero apuntará a NULL.

Estos nodos pueden parecer familiares a partir de la descripción de la mitad de los datos; de hecho, los nodos son estructuras y, con las estructuras, podemos agrupar datos específicos en un tipo de datos definido por el usuario.

Código de ejemplo

Aquí está la base de una estructura de lista enlazada. Hemos definido la estructura de nodo y también hemos definido un tipo de datos de puntero de nodo de estructura llamado Enlace, es decir Enlace es un puntero a un nodo de estructura. Artículo se define como un valor entero y será la sección de datos del nodo. También hemos agregado una estructura diferente _lista que apuntará al primer nodo.

Antes de escribir más código, debemos comprender otra propiedad de las listas vinculadas. Es posible que ya haya notado cuando definí punteros a estas estructuras que generalmente se crean dentro del montón. Las listas vinculadas generalmente se asignan dinámicamente en tiempo de ejecución donde el usuario puede requerir una cantidad variable de nodos para contener una cantidad variable de datos, declarando un nuevo o destruyendo nodos según sea necesario. Esto es algo que las matrices no pueden hacer ya que están declaradas estáticamente en la pila y solo pueden contener tantos datos como se les dio. Usando punteros para hacer referencia a las listas, podemos pasarlas de manera eficiente sin muchos recursos, especialmente si las listas son largas y contienen mucha información.

Una aplicación que utiliza este método se puede ver en los marcadores (como en los juegos en línea) donde cuando un nuevo jugador se une a la sala, se le puede asignar un nuevo nodo y luego agregarlo a la lista. Si un jugador abandona la habitación, su nodo puede ser destruido y sus datos pueden ser liberados.

Tenga en cuenta que la fuga de datos puede ser un problema real aquí y cualquier implementación de listas vinculadas DEBER ser manejado con cuidado. Debe tener sus prioridades definidas y comprender lo que está sucediendo en su lista; de lo contrario, perderá indicadores de los datos asignados al montón y no podrá alcanzarlos para liberarlos. Si no es alguien que planifica el código antes de escribirlo, le recomiendo encarecidamente que lo haga al lidiar con esto.

Continuando con nuestro código, similar a un tutorial anterior sobre Malloc y el montón, necesitaremos definir una función para crear un nuevo nodo para facilitarnos las cosas. También necesitaremos una función para ayudar a inicializar la lista con un nodo principal.

Vemos en ambas funciones que la nueva estructura se declara con malloc con el tamaño de la estructura desreferenciando el puntero a la estructura. También necesitamos comprobar si el malloc La llamada fue exitosa, que es donde afirmar la llamada es útil. Si cuando un malloc la llamada falla en tiempo de ejecución, el afirmar La función abortará nuestro programa y nos dirá en qué línea ocurrió el error.

Para nuestro nodo principal, inicializamos el primero puntero al primer nodo como NULL porque todavía tenemos que apuntar a un nodo. Para nuestro nodo normal, necesitamos inicializar el elemento con el valor del elemento pasado como argumento y debemos establecer el Siguiente puntero a NULL, ya que todavía tenemos que apuntar a un nodo existente.

Intentemos hacer una lista de un solo nodo.

Declaramos una nueva lista con una variable. cabeza para apuntar al comienzo de la lista y un nodo llamado nodo con un dato de 42. Establecemos head’s primero puntero igual a la dirección del nodo, lo que esencialmente significa que cabeza ahora apunta a nodo al igual que:

Nosotros inicializamos nodopuntero a NULL de forma predeterminada al llamar newNode y como solo tenemos un nodo, nodo apunta a NULL, lo que significa que es el final de la lista.

También debemos asegurarnos de que nuestras variables de montón se liberen usando gratis para entregar los datos para otro uso.

Compilación y ejecución

Dado que las listas vinculadas son objetos del montón, deberíamos comprobar el estado del montón después de que finalice nuestro programa. Podemos hacer esto usando el Valgrind que descubrimos en el Tutorial 0x18 – Malloc and the Heap.

En el cuadro azul, podemos ver que cabeza está en la dirección 0x51fc040 y apunta a la dirección 0x51fc090. Nuestro nodo está en la dirección 0x51fc090, tiene el elemento 42 y apunta a NULL. Nuestro cabeza puntos a nodo y nodo apunta a NULL, por lo que todo salió según el plan. También hemos liberado todos nuestros datos del montón, lo cual es una buena señal.

Ahora que hemos cubierto los conceptos básicos absolutos sobre listas vinculadas, intentemos definir más funciones para ayudarnos. Primero, haremos un freeList función para liberar todos los nodos de una lista y luego el nodo principal. ¿Cómo abordaremos esto? Comencemos un plan y clasifiquemos nuestras prioridades.

Debemos tener cuidado en esta etapa porque no queremos perder ningún puntero a los nodos como si fueran las cadenas de los globos. Si dejamos ir a alguno de ellos, perderemos el nodo y todos los demás nodos conectados a él.

Lo que podemos hacer es usar un puntero temporal a un nodo para sujetarlo a un nodo y poder alcanzarlo. Asi es como debería de hacerse:

Como puede ver, la priorización es imprescindible cuando se trata de listas vinculadas. Si algo pequeño saliera mal, podríamos estar perdiendo nodos inesperadamente. Veamos esto en código.

Usamos una variable de puntero temporal temperatura para apuntar al primer nodo. Después de establecer el primer puntero de la cabeza en el nodo después del nodo temporal, podemos liberar de forma segura el primer nodo sin perder ningún nodo, ya que hemos asegurado el segundo nodo con la cabeza. primero puntero. También podemos liberar temperaturael nodo como al mismo tiempo porque todavía podemos alcanzarlo con el temperatura puntero. Usando temperatura como iterador, podemos repetir este proceso hasta que se hayan liberado todos los nodos, lo que nos permite finalmente liberar la cabeza.

Probemos con otra función que nos ayude a agregar un nodo al final de la lista llamado appendNode. La función tomará dos argumentos, el encabezado y un nodo. Pero, ¿cómo agregamos un nodo a una lista? Bueno, tendremos que acceder al último nodo y luego configurarlo. Siguiente puntero para apuntar al nodo que queremos sin embargo, no podemos llegar directamente al último nodo por lo que tendremos que atravesar la lista hasta que podamos. Una última cosa, necesitamos verificar si la lista tiene un primer nodo. Si no es así, simplemente ponemos la cabeza primero igual al nodo.

Ahora que tenemos estas funciones, intentemos hacer una lista vinculada de elementos analizando los argumentos de la línea de comandos de la siguiente manera:

./lista [1st NUMBER] [2nd NUMBER] [3rd NUMBER] …

Veamos el código con todo junto.

Veámoslo todo en acción.

Compilación y ejecución

¡Todo funcionó a la perfección! También se liberó toda la memoria del montón.

Si desea implementar más funciones, ¡hágalo! Si necesita algunas ideas, pruebe estas:

  • deleteNode: elimina un nodo en una posición específica,
  • prependNode: coloca un nodo en la primera posición,
  • removeItems: elimina todos los nodos que tienen un elemento específico.

Si quieres ir incluso Además, ¡intente implementar una función de ordenación!

También puede personalizar su lista agregando un anterior puntero para apuntar al nodo anterior, o agregar el número de nodos en la estructura principal o agregar un ultimo puntero para apuntar al último nodo.

Conclusión

La lista enlazada ADT es una excelente manera de crear una versión dinámica de una matriz. Podemos agregar o destruir nodos a pedido simplemente liberando y moviendo punteros sin la necesidad de cambiar elementos como los que necesitamos en las matrices.

Además, la lista enlazada es una forma de implementación básica de un árbol o gráfico. Si ampliamos nuestra estructura, podemos crear estas estructuras de datos más avanzadas y hacer algunas cosas realmente interesantes. Si desea ir más allá de las listas y crear estos ADT de nivel superior, deberá investigar por su cuenta a partir de ahora porque esto es todo para la serie C estándar, espero que todos hayan disfrutado y aprendido algo y posiblemente salir y adentrarse más en el idioma!

dtm.

Publicaciones relacionadas

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Mira también
Cerrar
Botón volver arriba
Cerrar