listas encadenadas

Download Listas encadenadas

Post on 03-Jan-2016

35 views

Category:

Documents

0 download

Embed Size (px)

DESCRIPTION

Listas encadenadas. M.C. Juan Carlos Olivares Rojas. Agenda. Concepto de nodo y encadenamiento. Operaciones de inserción, desplegado y eliminación de nodos de una lista. Aplicación integradora de conceptos del curso. Concepto de nodo y encadenamiento. - PowerPoint PPT Presentation

TRANSCRIPT

  • *Listas encadenadas M.C. Juan Carlos Olivares Rojas

  • AgendaConcepto de nodo y encadenamiento.

    Operaciones de insercin, desplegado y eliminacin de nodos de una lista.

    Aplicacin integradora de conceptos del curso.*

  • Concepto de nodo y encadenamientoLas listas ligadas es una de las estructuras de datos definidas por el usuario ms empleada.

    Las listas tienen la caracterstica de que son dinmicas por este motivo se hace uso de memoria dinmica, apuntadores (C/C++) y referencias (Java/C++).*

  • Concepto de Nodo y EncadenamientoEl nodo es el elemento fundamental de la lista.

    Si una lista no tiene nodos se dice que est vaca.

    Las listas no tienen un tamao mximo predeterminado.*

  • Concepto de Nodo y EncadenamientoUn nodo no es otra cosa que una estructura con los datos que nos van a interesar trabajar. El nodo contiene adems al menos un enlace simple (listas ligadas) o enlaces dobles (lista doblemente ligada).

    De manera interna la lista puede tener uno o ms apuntadores a los nodos de la lista (generalmente: inicio, fin y actual)*

  • Concepto de Nodo y EncadenamientoLos principales tipos de lista son dos dependiendo de la forma en como se accedan a los nodos:

    Cola (FIFO, Fist In First Out) en donde por un extremo se atienden clientes y por el otro van llegado.*

  • Concepto de Nodo y EncadenamientoPila (LIFO, Last In First Out) en este tipo de lista slo se trabaja con un extremo, el llamado cima de la pila.

    El encadenamiento consiste en enlazar nodo con nodo para poder ligarlos. Sin encadenamiento no se puede tener una lista ligada.*

  • Concepto de Nodo y EncadenamientoGeneralmente el inicio y el fin de una lista estn ligadas hacia un nodo vaco.

    struct nodo {int valor;struct nodo *izq;struct nodo *der;}*

  • Concepto de Nodo y EncadenamientoLas listas circulares son aquellas que el fin de la lista apunta hacia el inicio.

    Las reas de aplicacin de las listas son muy diversas. Se utilizan para ordenamiento, bsquedas, almacenamiento de informacin, etc.*

  • Operaciones de insercin, desplegado y eliminacin de nodos de una lista

    Las operaciones bsicas de una lista consiste en agregar elementos, borrarlos y listarlos.

    Cada una de estas operaciones debe considerar en que parte de la lista se hace: inicio, en medio o fin.*

  • Operaciones con ListaLenguajes como Java tienen de manera predeterminada objetos del tipo Lista u objetos derivados de lista.

    Otras operaciones consiste en determinar si la lista est vaca.

    Estructuras como rboles y grafos siguen el mismo principio.*

  • Operaciones con ListaCuando se agrega un nuevo elemento lo primero que hay que realizar es crear el nuevo nodo, identificar en que parte debe de ir, actualizar los apuntadores al nuevo nodo, considerar los casos especiales.

    Al borrar se sigue el procedimiento contrario, se actualizan apuntadores, desligando el nodo y liberando memoria. *

  • Aplicacin integradora de conceptos del curso

    Realizar un programa que permita sumar nmeros enteros muy grandes. Cada dgito debe pertenecer a un nodo. Se ordenan los nodos para ir sumando el nmero menos significativo. El resultado de la operacin se guarda en otra lista.*

  • *Preguntas, dudas y comentarios?