Título: [C] Listas enlazadas. Publicado por: The Swash en 15 Octubre 2011, 02:09 am (http://4.bp.blogspot.com/-HvS7w5kptCU/TYExe6qBpcI/AAAAAAAAAPk/VR21t8j_yZ0/s400/listas.gif) Información general: Las listas enlazadas son un recurso dinámico muy potente que nos permite realizar tareas que generalmente podríamos requerir con arrays, pero se impide en objetos estáticos y en dinámicos sería muy complicado. Una lista enlazada se basa en una estructura, la cual será el esqueleto o prototipo del contenido, y al final requerirá tener un puntero hacia la siguiente estructura del mismo tipo, es decir están enlazadas por su ubicación (dirección de memoria). Funcionamiento y estructura: Primero debemos tener la estructura o prototipo en el cual definiremos los datos que emplearemos y como debe ser, un puntero a otra estructura del mismo tipo: Código
Utilizamos typedef para evitar estar utilizando struct _nodo para todo, así abreviamos y hacemos el código más legible. Código
Hay unas bases a tener en cuenta para trabajar con listas enlazadas:
Recordemos, cada elemento tiene un apuntador al siguiente, por ello se llaman enlazados: (http://www.calcifer.org/documentos/librognome/img/lista.png) Para trabajar con listas, deberemos implementar una serie de funciones y procedimientos para el manejo de sus elementos entre ellas:
Creación de una lista nueva: Para crear una nueva lista teniendo en cuenta el prototipo lo que utilizaremos son punteros, por lo cual suele ser más cómodo utilizar un typedef para más comodidad. En cuanto a teoría para crear una nueva lista deberíamos:
Código
Inserción de elementos: Para insertar nuevos elementos deberemos tener una lista previamente creada y contar con su referencia para acceder a ella, además se deberán hacer múltiples comparaciones con fines de prevenir errores, como cuando la lista está vacía, o el lugar donde se va a ingresar el nuevo elemento, etc. Insertar elemento al final:
Código
Inserción de elementos al principio:
Código
Inserción de un elemento posterior a otro:
Código
Eliminación de elementos: La eliminación de elementos también es una función muy importante a la hora de trabajar con listas, sus implementaciones pueden ser muchas debido a la gran cantidad de casos posibles, como eliminar el primer o último elemento, eliminar un elemento según su dirección, posterior a otro, o buscando por valor (Eliminar primero, último o todos). Yo mostraré 2 casos, eliminando el primer elemento y eliminando por dirección del elemento. Eliminación del primer elemento:
Código
Eliminar elemento por su dirección:
Código
Búsqueda de elementos: La búsqueda de elementos generalmente se realiza para localizar la posición de un objeto comparando su valor, ya que si se tiene su dirección simplemente haciendo referencia podríamos acceder a su contenido. Búsqueda por valor:
Código
Bueno, espero hayan comprendido el articulo y prometo trabajar más estructuras de datos. Hasta la próxima. Saludos. Título: Re: [C] Listas enlazadas. Publicado por: BlackZeroX en 16 Octubre 2011, 03:23 am .
Estos temas apenas los estan tocando en mi facultad pero la vdd no tiene mucha ciencia. https://secure.wikimedia.org/wikipedia/es/wiki/Estructura_de_datos * Con respecto a tus codigos de ejemplo: Insisto en que no hay que dejar que las funciones creen memoria asi por que si, mejor pasarle un buffer... y si es nesesario reservar memoria mejor en una clase para evitar los malditos Memory Leak... Edito: * Los nodos al igual que siguien un punto al siguiente elemento pueden tener un puntero al elemento anterior... Doblemente enlazada, en tu ejemplo solo tocaste la simple... * Me parece mas optima la lista Doblemente enlazada!¡... aun que depende mucho de diversos criterios... P.D.: http://www.calcifer.org/documentos/librognome/glib-lists-queues.html Dulces Lunas!¡. Título: Re: [C] Listas enlazadas. Publicado por: dewolo en 21 Octubre 2011, 01:57 am si me habian enseniado sobre las listas simplemente enla<adas y las doblemente enlazadas, osea en un solo sentido o de ida y vuelta, pero casi nunca le encuentro aplicacion :-[
Título: Re: [C] Listas enlazadas. Publicado por: CeroX901 en 21 Octubre 2011, 03:21 am Estoy de acuerdo en eso, en mi U en programación básica fue el programa que me tocó hacer como proyecto final y hasta el día de hoy no le he visto ninguna aplicación ni base a las siguientes materias, he visto Prog Orientada a Objetos, Prog Avanzada y ahora estoy en Modelos I... Cosas mas importantes que deberían ser base en la carrera.
Título: Re: [C] Listas enlazadas. Publicado por: darkvidhack en 21 Octubre 2011, 19:33 pm Pienso que las listas enlazadas son una estructura de datos mucho más eficiente que los vectores (por ejemplo) en algunos aspectos, como la inserción de un elemento en algunos casos, mientras que para una lista enlazada, el tiempo del algoritmo para la inserción al principio es de O(1) (se hace directamente), para los arrays es de O(n), (hay que rrecorrer todo el vector para insertar, n=número de elementos), según para lo que las necesitemos... cada una tiene sus pros y sus contras ;)
Título: Re: [C] Listas enlazadas. Publicado por: brians444 en 26 Octubre 2011, 04:56 am Creo que las listas enlazadas son muy importantes, son la base para las colas y pilas, estructuras muy usadas, en sistemas y otros.. Las pilas se acceden de manera Last in First Out (LIFO) es decir que el primer elemento en ingresar es el primero en salir.
Dichas pilas se implementan en C en forma de lista enlazada, para las cuales hay que definir varios metodos: Push: Para insertar un elemento en la cima de la pila Pop: Para obtener un elemento de la cima Crear: Para crear la pila Destruir: Para eliminar la memoria de todos los elementos almacenados Tambien se puede implementar uno mas para saber si esta vacio, y en cuyo caso crearla. Las colas colas son similares a las pilas solo que su manera de acceder a los datos es del tipo First In First Out (FIFO), o sea que el primer elemento en entrar es el primero en salir. Para las colas se definen metodos analogos a los de pilas. Saludos :D |