TDA Lista

Este esta ocasión explicaré sobre la Lista (Que es un tipo de dato abstracto o TDA), esta estructura se estudia en una clase que se llama "Estructura de datos", sin más preámbulo pasaré a su explicación e implementación tanto en pseudo-código como en C++ (nuestro querido lenguaje de programación), recordemos que es la versión que nos enseñan en los libros, puramente de enseñanza, mas adelante postearé sobre una lista con mas métodos.

Un concepto básico de Lista, sería un conjunto o colección de datos de un mismo tipo, y puede ser implementado utilizando arreglo, cursores o cubetas. Y los métodos u operaciones que posee son los siguientes.

FIN(): Retorna la posición del último elemento, en otras palabras el “fin” de la lista, también se puede considerar con el tamaño de la lista. Sí la lista está vacía retorna una posición invalida que podría ser -1.

PRIMERO(): Retorna la posición del primer elemento, o el inicio de la lista. Sí la lista está vacía retorna una posición invalida que podría ser -1.

SIGUIENTE(pos): Retorna pos + 1, si pos es igual o mayor a FIN(), retorna FIN().

ANTERIOR(pos): Retorna pos – 1, si pos es igual o menor a PRIMERO(), retorna PRIMERO().

SUPRIME(pos): Elimina el elemento que está en la posición “pos”.

ANULA(): Digamos que limpia la lista y retorna FIN().

RECUPERA(pos): Retorna el elemento que está en la posición “pos”.

LOCALIZA(x): Busca el elemento “x” y retorna su posición, si no lo encuentra retorna -1.

INSERTA(x, pos): Inserta el elemento “x” en la posición “pos”.

IMPRIME(): Imprime la lista.

Seudocodigo

funcion FIN retornar entero
inicio
  si la lista esta vacia entonces
    retornar -1
  sino
    retornar fin
  fin si
fin


funcion INICIO retornar entero
inicio
....si la lista esta vacia entonces
........retornar -1
....sino
........retornar 1
....fin si
fin


funcion SIGUIENTE ( pos ) retornar entero
inicio
....si pos >= FIN() entonces
........retornar FIN()
....sino
........retornar pos + 1
....fin si
fin


funcion ANTERIOR ( pos ) retornar entero
inicio
....si pos <= PRIMERO() entonces
........retornar PRIMERO()
....sino
........retornar pos - 1
....fin si
fin

Implementación con Arreglo

#ifndef __LISTA__ARREGLO__H__
#define __LISTA__ARREGLO__H__

template<class Tipo>
class ArrLista {
private:
  Tipo datos[100];
  int tam;
  int fin;
  int inicio;
public:
  ArrLista(int _size): tam(_size),fin(0),inicio(0){}
  ArrLista(): tam(100),fin(0),inicio(0){}
  int FIN();
  int PRIMERO();
  int SIGUIENTE(int pos);
  int ANTERIOR(int pos);
  void SUPRIME(int pos);
  int ANULA();
  Tipo RECUPERA(int pos);
  int LOCALIZA(Tipo x);
  void INSERTA(Tipo x, int pos);
  void IMPRIME();
};
#endif


To be continue...