Ordena la lista vinculada C ++

Lista enlazada

Una lista vinculada es una especie de estructura de datos. Los elementos dentro de la lista vinculada están conectados utilizando punteros. Es una colección de nodos. Un nodo contiene dos partes. Uno incluye los datos, y la segunda parte consiste en el puntero. Este puntero se utiliza para almacenar la dirección de memoria del elemento de nodo adyacente en la lista vinculada. La ventaja de la lista vinculada de una matriz es que tiene un tamaño dinámico.

Representación de una lista vinculada

El primer nodo de la lista vinculada se llama por delante. Su valor es nulo en el caso de una matriz vacía. En C ++, usamos una estructura para representar un nodo.

Este es un código C ++ simple de creación de listas vinculadas. Hemos creado una clase en la que su parte pública, una variable de datos del tipo entero, se crea con una variable de tipo de puntero 'Siguiente' que almacenará la dirección del nodo.

Se crean tres nodos dentro del programa principal, con el primer nodo superior declarado como el nodo 'Head'. Los triples de estos nodos están vacíos, por lo que se declaran como NULL inicialmente. Después de hacer esto, los tres nodos se asignan en un montón. 'Cabeza' segundo, y tercero se asigna con el nuevo nodo.

Ahora asignaremos datos y los datos pueden ser cualquier valor aleatorio. Primero, asignaremos datos en el primer nodo.

Head-> Data = 1;

Esta demostración de la asignación de datos muestra que la parte de datos del primer nodo contendrá datos en ella. Después de asignar datos, vincularemos el primer nodo con el segundo

Head-> next = segundo;

Conectamos la porción de puntero 'siguiente' con el otro nodo para vincular dos nodos. Asignaremos datos almacenados en la parte de datos del primer nodo. Mientras que la porción 'Siguiente' contendrá la dirección de memoria del nodo presente después de él. Del mismo modo, ahora asignaremos datos al segundo nodo, y el segundo nodo estará vinculado con el tercer nodo. Ahora agregue datos en el tercer nodo. Como hemos creado solo tres nodos, no hay otro nodo, por lo que la siguiente parte del tercer puntero se declarará como nula; Esto indica que la lista vinculada está terminado.

Tercero-> next = null;

Ejemplo

Ordenar lista

Aquí hemos declarado una estructura que representa un nodo de una sola lista vinculada. Como se describió anteriormente, el concepto de declaración de lista vinculada, la variable de datos y las variables del puntero se toman en la estructura. Al igual que la parte del puntero 'Siguiente' que almacena la dirección, también hemos declarado dos variables de tipo de puntero más: cabezal de nodo y cola de nodo. Ambos se declaran inicialmente como nulos.

Como el nodo de inserción trata de insertar el nodo de datos en la lista vinculada, utilizaremos una función de agregar un nodo. Los datos también asignarán este nodo. Entonces, el parámetro de esta función contendrá datos como argumento. Antes de la inserción, el nodo se creará con la asignación de memoria utilizando una función MALLOC (). La parte de datos del nuevo nodo se asignará con los datos aprobados.

Newnode-> data = data;

Y de manera similar, la siguiente porción se asigna como nula, ya que no hay conexión entre este nodo con ningún otro. A medida que se declaran las variables de la cabeza y la cola para ayudar en el orden de inserción. Ahora los utilizaremos aquí. Primero, al usar una declaración if-else, verificaremos si la cabeza es nula, como hemos declarado como nulo arriba, lo que significa que toda la lista está vacía. Es por eso que la cabeza está vacía, por lo que las variables de la cabeza y la cola apuntarán al nodo recién creado. De lo contrario, en la parte del otro, si la lista no está vacía, suponga que al crear la lista también hemos ingresado datos, entonces, en este caso, el nuevo nodo se agregará en el último lugar.

Tail-> next = newnode;

Y ahora, este nuevo nodo actuará como un nuevo cuento.

Cola = newnode;

Para una adición adicional, continúa el mismo proceso, pero necesitamos ordenar la lista vinculada. Por lo tanto, hemos agregado un solo nodo que actúa como un nodo temporal para almacenar datos en él temporalmente.

Después de agregar el nuevo nodo, utilizaremos una función para clasificar/ organizar la lista. Como el tipo de clasificación no se menciona aquí, por defecto, la lista se ordenará en orden ascendente.

Volviendo hacia el ejemplo, otro puntero actual apunta a la cabeza, como declaramos anteriormente. Esto se usa para ordenar los elementos de la lista. Otra variable de tipo de puntero se utilizará aquí y luego se declarará como nulo. Más uso estará en el programa más tarde.

Aquí aplicaremos un cheque para identificar si el puntero de la cabeza está en la posición nula y luego volver al programa principal. De lo contrario, aplicaremos una lógica aquí que seguirá un bucle de tiempo. El puntero de índice apuntará a la siguiente parte del nodo actual. Dentro de ese bucle, se usa otro bucle mientras se usa, y esto también durará hasta que el nodo actual no sea nulo. Aquí usaremos una declaración IF para verificar si los datos en el nodo actual son mayores que los datos dentro del nodo del índice, entonces se intercambian los datos entre ellos.

La variable temperatura desempeñará un papel importante aquí en el intercambio de datos. Primero, los datos del nodo actual se transfieren a TEMP, y luego el nodo actual ahora está vacío. Este nodo se le asignará el valor de los datos de índice. Y al final, el nodo de índice vacío es asignado por los datos presentes en la variable TEMP.

Fuera de la declaración IF, el nodo de índice también se incrementa con el nuevo valor de un índice. Del mismo modo, fuera del bucle while, el nodo actual también es asignado por el nuevo valor.

A continuación, hemos utilizado una función de visualización aquí para mostrar el valor de todos los nodos. El puntero actual apuntará hacia la cabeza. En otro caso, un bucle de tiempo muestra todos los valores hasta que el nodo actual no sea nulo.

Ahora considere el programa principal, la función de addNode () se llama con los valores para agregar nuevos valores dentro de la lista. Entonces la función de visualización mostrará todos los valores ingresados ​​antes de clasificar. Luego llame a la función sort (). Y luego, nuevamente, llame a la función de visualización para mostrar toda la lista ordenada.

Guarde el archivo de código y luego ejecútelo en el terminal Ubuntu con la ayuda de un compilador G ++.

archivo de archivo $ g ++ -o.C

ps./archivo

Del valor resultante, puede observar que los valores se organizan en orden ascendente, ya que se ingresaron al azar en la lista vinculada.

Conclusión

'Ordena la lista vinculada C ++' contiene la descripción de los conocimientos básicos sobre la lista vinculada y su creación. Un código de muestra es suficiente para demostrar la creación del nodo y el funcionamiento de todos los nodos en la lista vinculada. Los elementos dentro de la lista vinculada se organizan en orden ascendente utilizando un proceso detallado agregando nuevos nodos y luego clasificando una variable TEMP. La explicación con el código se realiza para ayudar al usuario.