listas simples en c++ - Aprende a programar!

Breaking

ads

ads

martes, 16 de junio de 2015

listas simples en c++


Ni más ni menos, es hora de empezar:
Comenzaremos con las explicaciones en pseudocodigo pero todo será
llevado a C++.
Una lista no es más que un conjunto de nodos referenciados entre sí.
¿Qué es un nodo?
Sin tantas palabras extrañas, un nodo no es más que una cajita que
almacena datos (en campos) y tiene apuntadores.
Ej:







Definiendo un poco los apuntadores: es como un campo que almacena
una dirección de memoria Ej: la dirección de tu casa, cualquiera que la
conozca puede llegar a ella.


Para crear una estructura (nodo) en
pseudocodigo utilizamos malloc (nombre de
la estructura)


Ej: Malloc (Nodo) //Esto solamente crea el
espacio de memoria


Para acceder a sus campos seria:



Nodo->nombre = “Hernán”
Nodo->edad = “Castilla”
Nodo->apellido = “18”


Por el momento no tocaremos los apuntadores.
Ni más ni menos, es hora de crear nuestra estructura (nodo) en C++:
Los ejemplos están mostrados en Dev-C++ y Code Blocks






Manos a la obra:

Con los comentarios quizás este de sobra la explicación pero bueno:
Como se puede observar para crear nuestra estructura nodo hacemos
uso de


Struct (nombre de la estructura) {
//Código...
};


En este caso creamos el nodo del ejemplo anterior.





Ya tenemos lista la estructura nodo, ahora creemos un espacio de
memoria, un nodo:


Como ya se mencionó en pseudocódigo se utiliza Malloc (nodo)
Aquí es un poco diferente:


Aquí se crea un nodo p el cual tiene los campos ya mencionados y se
les dan valores.
Con esta información ya es hora de entrar con las listas *-*:
Bueno existen varios tipos:
Simples
Dobles
Circulares


Listas Simples:
Ya sabemos que las listas son un conjunto de nodos, estas tienen
un apuntador principal llamado cabeza (PTR).

Ej:

Describamos un poco lo que está pasando:


PTR (la cabeza) está apuntando al primer nodo, este nodo a otro nodo y
el último nodo en las listas simples y dobles apunta a Null.


El problema principal de la listas radica en cómo ligar todos nuestros
nodos de forma correcta, insertar nuevos nodos, recorrerlos y
eliminarlos sin que la lista se dañe.
Entonces las operaciones básicas con las listas simples son:
Insertar por cabeza
Insertar por cola
Recorrer
Buscar
Eliminar


Insertar por cabeza:
Cuando la lista está vacía se vera de esta manera:




Es muy obvio puesto que la lista a un no contiene nodos, lo que
queremos lograr con la inserción por cabeza es que cada vez que
ingresemos un nodo en la lista siempre quede en la primera posición.


Ej:


Llevemos esto al pseudocodigo *-*:
En los ejemplos trabajaremos el campo info, pero puede ser cualquiera
como ya lo explicamos:




Explicando un poco lo que pasa en la imagen:

Creamos el nodo con Malloc (p), le ingresamos cualquier información
con


P->info = información, preguntamos si la lista está vacía, si la lista está
vacía a la cabeza le asignamos el nuevo nodo, y apuntamos el nuevo
nodo a Null (Este proceso es la primera imagen).


Si la lista no está vacía, apuntamos el nuevo nodo hacia la cabeza y
después colamos la cabeza en el nuevo nodo.


En el siguiente vídeo se explica de una manera más clara:
https://www.youtube.com/watch?v=6FEwFsA3shM



Dentro de poco les mostrare un pequeño programa en C++ pero antes
vamos a explicar el procedimiento de recorrido.




Al momento de crear nuestro nodo con Malloc (p) esto igual nos crea un
puntero del tipo nodo (hago referencia a la estructura creada), este
puntero lo podemos colocar en cualquier parte de nuestra lista.


La idea del recorrido es colocar el puntero P en nuestro primer nodo e ir
rodándolo por todos los nodos, por ser del tipo de nuestra estructura,
obtendremos acceso a todos los campos donde se encuentre el puntero.


Entonces colocar el puntero en el primer nodo están sencillo como:
P = PTR
Como podemos acceder a los campos para correrlo solo es entrar en el
apuntador del nodo y ubicarlo en esa dirección de memoria.
P = P -> apuntador


Ahora solo nos queda poner esto en un ciclo while para recorrer el
puntero hasta NULL, recordemos que nuestro último nodo apunta a
NULL entonces al acceder a su apuntador y colar a P, este quedara en
NULL (en la imagen de arriba se puede apreciar mejor).


Ej:


P = PTR
While (P != NULL) {
P = P -> apuntador;
}


Ni más ni menos hagamos un programa en C++, creemos una lista,
insertemos nodos por cabeza, démosle unos nombres y mostrémoslo
por pantalla.


Primero creemos la estructura:







Creo que con los comentarios y con lo explicado al comienzo debe estar
claro, ¿Cómo el agua del lago?


Sigamos con el ciclo principal de nuestro programa:






La única línea a explicar aquí es struct nodo *p = new nodo;


Recuerdan lo que os explique sobre el puntero el procedimiento buscar,
bueno era para esto.


Struct nodo *p // lo que hacemos aquí es crear un apuntador de esta
estructura.


P = new nodo // aquí llamamos al constructor new y le pasamos el
nombre de nuestra estructura. En pocas palabras, lo que decimos es,
crea el nodo en este apuntador de tipo nodo.


El programa terminado quedaría de la siguiente forma:






Lo que hacemos ahora es agregar el proceso de inserción por cabeza y
el proceso de recorrido, la verdad es que la sintaxis en pseudocodigo es
igual que C++ para estos dos.


Al final utilizamos system(“Comando a ejecutar”) // esto nos permite
ejecutar cualquier comando del cmd, en este caso si estas en Windows
cls si estas en Linux clear , nos sirve para limpiar la pantalla.


Aquí les dejo un video explicando todo el proceso de creación:
https://www.youtube.com/watch?v=-_S6XQyB-Jk

No hay comentarios:

Publicar un comentario

..