Tda lista estructuras de datos objetivos



Descargar 31,1 Kb.
Fecha de conversión20.03.2017
Tamaño31,1 Kb.

TDA LISTA

OBJETIVOS

  • Aprovechar la abstracción para definir comportamiento y luego operaciones en nivel de implementación
  • Visualizar las posibles implementaciones de un TDA ya definido
  • Utilizar con seguridad el concepto de puntero en implementaciones dinámicas
  • Reconocer la importancia de usar solo el comportamiento de un TDA, y no su estado

LISTAS: DEFINICION

  • Una lista es
    • Una colección de 0 o mas elementos
      • Si la lista no tiene elementos, se dice que esta vacía
    • En una lista, todos los elementos son de un mismo tipo
  • Son estructuras lineales, es decir
    • Sus elementos están colocados uno detrás de otro
    • Cada elemento de una lista se conoce con el nombre de NODO
  • Las listas
    • Son mucho más flexibles que los arreglos
    • Permiten trabajo “dinámico” con un grupo de elementos

TIPOS

  • De acuerdo a su comportamiento, los conjuntos lineales se clasifican en
    • Listas, Pilas y Colas
  • De acuerdo a su implementación, las listas se clasifican en
    • Simples
    • Doblemente Enlazadas
    • Circulares

LISTAS SIMPLES

  • Se define como un conjunto de nodos
    • Uno detrás de otro
    • Del cual siempre se puede conocer al nodo inicial y al final
  • De cada nodo de la lista, se conoce
    • Un contenido, que es la información que almacena dentro
      • Puede ser de cualquier tipo de dato
    • Un sucesor único
      • Excepto el ultimo nodo de la lista

LISTA SIMPLE: NIVEL LOGICO

  • Comportamiento (a/con una lista se puede)
    • Crear y Eliminar
    • Conocer si esta vacía
    • Añadir elementos y removerlos
    • Consultar el primer y al ultimo elemento
    • Imprimir sus elementos en pantalla
    • Buscar un elemento con cierta información en la lista
  • Estado:
  • ::= + {} +
  • ::=
  • ::=

TDA NODO: NIVEL LOGICO

  • Una lista esta compuesta de nodos, y por eso es importante definir el TDA Nodo
  • Un nodo de una lista
    • Almacena información de cualquier tipo dentro y
    • Es capaz de “viajar” o conocer otro nodo(el nodo siguiente)
  • Comportamiento
    • Crear y Eliminar
    • Consultar y modificar la información que almacena
    • Consultar y modificar el enlace que mantiene con otro nodo
  • ::= +
  • ::= {}
  • ::= |

LISTAS SIMPLES: NIVEL DE IMPLEMENTACION

  • Tenemos el concepto claro de lo que debe ser una lista
  • Ahora debemos ir al detalle: como darle vida a una lista
  • Hay varias posibilidades de implementación
    • Estática o Contigua, usando arreglos de longitud “variable”
    • Dinámica, utilizando punteros

IMPLEMENTACION CONTIGUA

  • Se utilizan arreglos, por lo tanto
    • Tiene limites, que no pueden ser rebasados al añadir nuevo elementos
    • Los “nodos” son adyacentes en memoria
      • Cada nodo es realmente un elemento del arreglo
      • Entonces, el enlace con el siguiente nodo seria simplemente el indice del siguiente elemento dentro del arreglo
      • OJO: En este tipo de implementación no es necesario crear el TDA Nodo
  • Al crearla se debe indicar el tamaño máximo del arreglo
  • Al insertar o remover un elemento,
    • Todos los elementos restantes avanzarán o retrocederán
  • No es la implementacion ideal para las listas simples
  • 10
  • 0
  • 5
  • 1
  • 8
  • 2
  • 2
  • 3
  • 31
  • 4
  • 5
  • 6
  • 7
  • 8
  • En uso
  • Desperdicio
  • 25
  • Al insertarse un nuevo elemento, en una cierta posición, todos los elementos restantes ruedan
  • 25
  • 3
  • 2
  • 4
  • 5
  • 6
  • 7
  • 8
  • 31

CONTIGUAS: OPERACIONES

  • Creación y Eliminación
    • LSCont *LSCont_Crear(int n);
    • void LSCont_Vaciar(LSCont *L);
  • Añadir y Remover elementos
    • void LSCont_InsertarNodoInicio(LSCont *L, Generico G);
    • void LSCont_InsertarNodoFin(LSCont *L, Generico G);
    • Generico LSCont_SacarNodoInicio(LSCont *L);
    • Generico LSCont_SacarNodoFin(LSCont *L);
  • Consultar indice del Ultimo
    • int LSCont_ConsultarUltimo(LSCont L);
  • Consultar estado de la lista, puede llenarse
    • bool LSCont_EstaVacia(LSCont L);
    • bool LSCont_EstaLlena(LSCont L);
  • Busqueda y Recorrido
    • int LSCont_BuscarNodo(LSCont L, Generico G, Generico_ComoComparar fn);
    • bool LSCont_EsNodoDeLista(LSCont L, int i);
    • void LSCont_Recorrer(LSCont L, Generico_ComoImprimir fn);

CONTIGUAS: DECLARACION

  • La lista contigua
    • Es un arreglo de elementos de cualquier tipo  realmente es un ARRAYU
    • No olvidemos que hay que predefinir el máximo de nodos de la lista
  • Para lograr mantener control sobre la cantidad de elementos en la lista
    • Debe existir una referencia que controle el ultimo elemento
    • La referencia al ultimo se moverá de acuerdo a las inserciones y eliminaciones
    • La primero nunca se mueve, siempre será 0
  • typedef struct{
  • int ultimo;
  • ArrayU Elementos;
  • }LSCont;
  • 10
  • 0
  • 5
  • 1
  • 8
  • 2
  • 25
  • 3
  • 2
  • 4
  • 5
  • 6
  • 7
  • 8
  • 31
  • header=0
  • MAX
  • Elementos
  • last

CONTIGUA: BASICAS

  • void LSCont_VaciarLista(LSCont *L){
    • L->ultimo = -1;
  • }
  • LSCont *LSCont_CrearLista(int max){
    • LSCont *nuevalista;
    • nuevalista->Elementos =
    • ArrayU_Crear(max, 0);
    • nuevalista->ultimo = -1;
    • return nuevalista;
  • }
  • void LSCont_EliminarLista(LSCont *L){
    • ArrayU_Eliminar(&(L->Elementos));
    • LSCont_VaciarLista(L);
  • }
  • bool LSCont_EstaVacia(LSCont L){
  • return(L.ultimo<0);
  • }
  • bool LSCont_EstaLlena(LSCont L){
  • return (L.ultimo == ArrayU_Tamanio(L.Elementol)-1);
  • }
  • 0
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • last
  • El índice del último elemento debe ser un índice inválido, un valor negativo. No importara que el arreglo tenga elementos pues no serán tomados en cuenta.
  • -1
  • 0
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • last
  • MAX-1
  • Si la lista está llena es porque el índice del último ha llegado al verdadero último índice posible en el arreglo: MAX -1

CONTIGUA: BUSQUEDA

  • int LSCont_BuscarNodo(LSCont L, Generico G,
  • Generico_Comparacion fn){
  • int i;
  • Generico elemento;
  • for(i = 0; i <=L.ultimo;i++){
  • elemento = ArrayU_ElemC(L.Elementos, i);
  • if(f(elemento, G) == 0) return (i)
  • }
  • return(-1);
  • }

CONTIGUA: INSERTAR

  • bool LSCont_Insertar(LSCont *L, int P, Generico G){
  • int i,
  • Generico ele1;
  • if(LSCont_EstaLlena(L)) return FALSE;
  • if(P<=-1) return FALSE;
  • //MOVER TODOS
  • for(i = L->ultimo; i >=P ;i--){
  • ele1 = ArrayU_ElemC(L->Elementos,i);
  • ArrayU_ElemM(L->Elementos,i+1, ele1);
  • }
  • ArrayU_ElemM(L->Elementos, P, G);
  • L->utlimo ++;
  • return TRUE;
  • }
  • bool LSCont_InsertarInicio(LSCont *L, Generico G){
  • int i;
  • Generico ele1, ele2;
  • //No insertar si ya esta llena
  • if(LSCont_EstaLlena(L)) return FALSE;
  • //Mover todo hacia delante
  • for(i = L->ultimo; i >=0 ;i--){
  • ele1 = ArrayU_ElemC(L->Elementos,i);
  • ArrayU_ElemM(L->Elementos,i+1, ele1);
  • }
  • ArrayU_ElemM(L->Elementos, 0, G);
  • L->ultimo++;
  • return(TRUE);
  • }
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 9
  • 0
  • 1
  • 2
  • 8
  • 3
  • 5
  • 1
  • 10
  • 1
  • 2
  • 3
  • 8
  • 4
  • 5
  • 1
  • 10
  • 0
  • 9
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 0
  • 1
  • 2
  • 8
  • 3
  • 5
  • 1
  • 10
  • 9
  • last
  • last
  • last
  • last
  • 1
  • 2
  • 3
  • 8
  • 4
  • 5
  • 1
  • 1
  • 1
  • 9

CONTIGUA: SACAR

  • bool LSCont_EliminarNodo(LSCont *L, int P){
  • int i;
  • Generico ele1;
  • if(LSCont_EstaVacia(L)) return FALSE;
  • if(P<=-1) return FALSE
  • //RETROCEDER TODOS
  • for(i = P; i < L->ultimo;i++){
  • ele1 = ArrayU_ElemC(L->Elementos, i+1);
  • ArrayU_ElemM(L->Elementos, i, ele1);
  • }
  • L->last --;
  • return TRUE;
  • }
  • bool LSCont_EliminarxInfo(LSCont *L, Generico G){
    • int pos;
    • if(LSCont_EstaVacia(L)) return FALSE;
    • pos = LSCont_Localizar(L, G);
    • if(pos >= 0)
      • return(LSCont_EliminaNodo(L, pos););
  • }
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 0
  • 1
  • 2
  • 8
  • 3
  • 5
  • 1
  • 10
  • 0
  • 1
  • 2
  • 8
  • 3
  • 8
  • 5
  • 10
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • last
  • last
  • Eliminar por Info, dada una cierta información, buscar el elemento que la tenga y eliminarlo

LSE: LISTAS SIMPLES ENLAZADAS

  • Es una implementación flexible y potente
  • Los nodos ya no son adyacentes en memoria
    • Un nodo A logra un enlace con otro B,
    • Almacenando dentro la dirección de memoria de B
  • Al insertar o eliminar un nodo ya no hay que “mover” al resto de elemento, solo enlazarlo con la lista
  • 10
  • 5
  • 8
  • 2
  • 31
  • 25
  • 25
  • Contenido
  • Enlace
  • C
  • S
  • 2
  • 31
  • 25
  • C
  • S
  • NODO A
  • NODO B

TDA LSE_NODO: NIVEL DE IMPLEMENTACION

  • Contenido: Datos enteros, reales, o incluso, de Estructuras: Estudiante, Auto, etc....
  • Y además, el nodo también contiene un enlace con su nodo siguiente
      • Este enlace, puede no enlazar el nodo con nadie, el nodo esta solito, no forma parte de ninguna lista

TDA LSE_NODO: OPERACIONES

  • Crear y Eliminar
    • LSE_nodo *LSE_Nodo_Crear(Generico G);
    • void LSE_nodo_Eliminar (LSE_nodo *p);
  • Consultar y Modificar Contenido
    • Generico LSE_nodo_GetContenido(LSE_nodo *p);
    • void LSE_nodo_SetContenido(LSE_nodo *p, Generico G);
  • Consultar y Modificar Enlaces
    • LSE_nodo *LSE_nodo_Siguiente(LSE_nodo *p);
    • void LSE_nodo_SetSiguiente(LSE_nodo *p, LSE_nodo *Enlace);

TDA LSE_NODO: DECLARACION

  • typedef struct TLSE_Nodo{
  • Generico G;
  • struct TLSE_Nodo *sig;
  • } LSE_Nodo;
  • typedef LSE_Nodo * LSE_NodoPtr;
  • Un nodo dinámico almacena dentro
    • Un contenido de cualquier tipo de dato, entero, real, estructuras, etc......
    • Un enlace, que es la referencia al nodo siguiente, la dirección del nodo siguiente

LSE_NODO: CREAR Y DESTRUIR

  • Al crear un nodo se le asignara un valor inicial
  • Al eliminar un nodo se liberara la memoria que este ocupa
  • LSE_nodo *LSE_CrearNodo(Generico G)
  • {
  • LSE_nodo *p;
  • p = (LSE_nodo *)malloc(sizeof(LSE_nodo));
  • if(p)
  • {
  • p->G = G;
  • p->sig = NULL;
  • }
  • return p;
  • }
  • void LSE_EliminarNodo(LSE_nodo *p)
  • {
  • if(p)
  • {
  • free(p);
  • p = NULL;
  • }
  • }

LSE: NIVEL DE IMPLEMENTACION

  • En una lista hay que llevar control de las posiciones al primer y el último elemento
  • En la lista, las posiciones son direcciones de memoria: punteros
  • La posición de un nodo estará dada por un puntero a dicho nodo
  • Una lista enlazada no tiene datos predefinidos
    • Los elementos o Nodos van siendo creados y eliminados a medida que se va necesitando

LSE: OPERACIONES

  • Crear y Eliminar
    • LSE * LSE_CrearLista();
    • void LSE_Eliminar(LSE **L);
  • Consultar Primer y Ultimo
    • LSE_nodo *LSE_NodoInicio(LSE L);
    • LSE_nodo *LSE_NodoFin(LSE L);
  • Conocer Estado
    • bool LSE_EstaVacia(LSE L);
  • Añadir y Remover
    • bool LSE_InsertarNodoInicio(LSE *L, LSE_nodo *pNodo);
    • bool LSE_InsertarNodoFin(LSE *L, LSE_nodo *pNodo);
    • bool LSE_Insertar(LSE *L, LSE_nodo *p, LSE_nodo *nuevo);
    • LSE_nodo *LSE_SacarNodoInicio(LSE *L);
    • LSE_nodo *LSE_SacarNodoFin(LSE *L);
    • bool LSE_EliminarxPos(LSE *L, LSE_nodo *p);
  • Busqueda y Recorrido
    • LSE_nodo *LSE_BuscarNodo(LSE L, Generico G, Generico_fnComparar f);
    • bool LSE_ExisteNodo(LSE L, LSE_nodo *p);
    • void LSE_Recorrer(LSE L, Generico_fnImprimir f);

LSE: DECLARACIÓN

  • Hay varias formas de definir una lista
    • Solo a través del primer elemento a la misma
  • O llevando control del primero y el último elemento
  • typedef struct{
  • LSE_Nodo *header;
  • LSE_Nodo *last;
  • }LSE;
  • typedef LSE_Nodo * LSE;

LSE: CREAR y DESTRUIR

  • Al crear una lista, esta estará vacía, su primero y ultimo no apuntaran a nadie
  • Al Eliminar una lista, cada uno de los nodos debe ser liberado
  • void LSE_Vaciar(LSE *L){
  • LSE_nodo *p;
  • while(!LSE_EstaVacia(*L)){
  • p = LSE_SacarNodoFin(L);
  • LSE_Nodo_Eliminar(p);
  • }
  • }
  • LSE *LSE_CrearLista(){
  • LSE *lnueva;
  • lnueva = malloc(sizeof(LSE));
  • lnueva->header = lnueva->last = NULL;
  • return lnueva;
  • }
  • header
  • last

LSE: BUSQUEDA

  • Hay que ubicarse en el inicio: header
  • E ir avanzando hasta
    • Encontrar el nodo con la información buscada o
    • Que ya no haya mas nodos
  • Como no se usan índices, se usan punteros:
    • Un puntero se ubicara en el header
    • Y luego irá avanzando al siguiente, y al siguiente y al siguiente
  • Al encontrar al nodo buscado, no se retorna su posición como índice, esta no importa
  • Se retorna la dirección de este nodo(puntero)
  • LSE_nodo *LSE_BuscarNodo(LSE L,
  • Generico G, Generico_fnComparar f){
  • LSE_nodo *p;
  • for(p = L.header; p!= NULL; p = LSE_Nodo_Siguiente(p)){
  • if(f(LSE_Nodo_Contenido(p),G) ==0) return(p);
  • }
  • return(NULL);
  • }
  • 10
  • 5
  • 8
  • 2
  • 31
  • 25
  • last
  • header
  • Busco 25
  • p
  • p
  • p
  • p
  • p
  • Busco 30
  • p
  • p
  • p
  • p
  • p
  • p
  • Recomendación:
  • Usemos el comportamiento de LSE_Nodo, no el estado

LSE: ANTERIOR

  • Dada la dirección de un nodo(pos), esta función retorna la dirección del nodo anterior
  • Hay que “buscar” desde el header
  • El nodo buscado es aquel cuyo siguiente es igual a pos
  • Si el elemento buscado es el primero en la lista, no hay anterior
  • LSE_nodo * LSE_Anterior(LSE L, LSE_nodo *p){
  • LSE_nodo *q;
  • if(LSE_EstaVacia(L)) return NULL;
  • if(L.header == p) return NULL;
  • for(q=L.header; q!=NULL;q=q->sig){
  • if(q->sig ==p) return(q);
  • }
  • return(NULL);
  • }
  • 10
  • 5
  • 8
  • 2
  • 31
  • 25
  • last
  • header
  • p
  • q
  • q
  • q
  • 7
  • p
  • La posición p es la de un nodo fuera de la lista
  • q
  • q
  • q
  • q
  • q
  • q
  • q
  • Ejemplo al usar el estado de LSE_Nodo

LSE: PRIMERO Y ULTIMO

  • Se pueden obtener siempre y cuando la lista no este vacía
  • Retornaran la información del elemento apuntado por header y last respectivamente.
  • LSE_nodo *LSE_NodoInicio(LSE L){
  • return (L.header);
  • }
  • LSE_nodo *LSE_NodoFin(LSE L){
  • return (L.last);
  • }

LSE: INSERTAR

  • La operación de insertar recibirá
  • Hay varios tipos de inserción
    • Insertar al inicio o al final
    • Insertar en medio de la lista

INSERCION AL INICIO/FINAL

  • bool LSE_InsertarNodoInicio(LSE *L, LSE_nodo *nuevo){
  • if (!nuevo) return FALSE;
  • if(LSE_EstaVacia(*L)){
  • L->header = L->last = nuevo;
  • } else{
  • LSE_Nodo_ModificarEnlace(
  • nuevo, L->header);
  • L->header = nuevo;
  • }
  • return(TRUE);
  • }
  • bool LSE_InsertarNodoFin(LSE *L, LSE_nodo *nuevo){
  • if(!nuevo) return FALSE;
  • if(LSE_EstaVacia(*L)){
  • L->header = L->last = nuevo;
  • } else{
  • LSE_Nodo_ModificarEnlace(L->last,, nuevo);
  • L->last = nuevo;
  • }
  • return(TRUE);
  • }
  • 10
  • 5
  • 8
  • 2
  • 31
  • 25
  • last
  • header
  • 9
  • nuevo
  • header
  • nuevo->sig = header;
  • header = nuevo;
  • 18
  • nuevo
  • last->sig = nuevo;
  • last
  • last = nuevo;
  • Si la lista esta vacía, tanto header como last apuntan al nuevo nodo
  • Si no, si es al inicio el nuevo header, es el nuevo nodo
  • Si no, si es al final, el nuevo last es el nuevo nodo

INSERTAR EN MEDIO

  • Debe recibir la posición donde se va a insertar
  • Insertemos después
    • Si Lista Vacía, el nuevo header y last, es el nuevo nodo
    • Si la posición no existe no efectuar la inserción
    • Si la lista solo tiene un elemento, el nuevo last es el nuevo nodo
  • bool LSE_Insertar(LSE *L,
  • LSE_nodo *p,
  • LSE_nodo *nuevo){
  • if(L->last==p){//Insertar al final
  • return(LSE_InsertarNodoFin(L, nuevo));
  • }else{
  • if(!p || ! LSE_ExisteNodo(*L,p))
  • return FALSE;
  • if(LSE_EstaVacia(*L))
  • L->header = L->last = nuevo;
  • else{
  • LSE_Nodo_ModificarEnlace(
  • nuevo, LSE_Nodo_Siguiente(p));
  • LSE_Nodo_ModificarEnlace(p, nuevo);
  • }
  • }
  • return(TRUE);
  • }
  • 10
  • 5
  • 8
  • 2
  • 31
  • 25
  • header
  • last
  • p
  • 18
  • nuevo
  • Nuevo->sig = p->sig;
  • p->sig = nuevo;
  • header
  • last
  • 18
  • nuevo
  • header
  • last
  • header = last = nuevo:

LSE: SACAR DE LA LISTA

  • LSE_nodo *LSE_SacarNodoInicio(LSE *L){
  • LSE_nodo *tmp = L->header;
  • if(LSE_EstaVacia(*L)) return NULL;
  • if(L->header == L->last)
  • LSE_InicializarLista(L);
  • else {
  • L->header = L->header->sig;
  • }
  • return(tmp);
  • }
  • LSE_nodo *LSE_SacarNodoFin(LSE *L){
  • LSE_nodo *tmp=L->header;
  • if(LSE_EstaVacia(*L)) return NULL;
  • if(L->header == L->last)
  • LSE_InicializarLista(L);
  • else{
  • tmp = L->last;
  • L->last = LSE_Anterior(*L, L->last);
  • L->last->sig = NULL;
  • }
  • return(tmp);
  • }
  • 10
  • 5
  • 8
  • 2
  • 31
  • 25
  • header
  • last
  • tmp
  • Tmp = header;
  • header
  • Header = header->sig;
  • free(tmp);
  • tmp
  • tmp = last;
  • last
  • Last = Anterior(Last);
  • free(tmp);
  • Last->sig = NULL;

LSE: SACAR JUSTO UN NODO

  • Lista no debe estar vacía
  • La posición enviada debe existir en la lista
  • Revisar si se desea eliminar el header o el last
  • bool LSE_EliminarxPos(LSE *L, LSE_nodo *p){
  • LSE_nodo *p_ant;
  • if(LSE_EstaVacia(*L)) return 0;
  • if(!p || !LSE_ExisteNodo(*L, p))
  • return FALSE;
  • if(p==L->header)
  • LSE_SacarNodoInicio(L);
  • else if(p == L->last)
  • LSE_SacarNodoFin(L);
  • else{
  • p_ant = LSE_Anterior(*L,p);
  • p_ant->sig = p->sig;
  • p->sig = NULL;
  • }
  • return(TRUE);
  • }
  • 10
  • 5
  • 8
  • 2
  • 31
  • 25
  • header
  • last
  • p
  • pant
  • p_ant = Anterior(p);
  • p_ant->sig = p->sig;
  • free(p);

VISUALIZAR

  • Imprimir todos los nodos de la lista
  • void LSE_Recorrer(LSE L, Generico_fnImprimir fn){
  • LSE_nodo *p;
  • for( p = L.header; p!=NULL; p = p->sig)
  • fn(p->G);
  • }


La base de datos está protegida por derechos de autor ©absta.info 2016
enviar mensaje

    Página principal