jcvargas@isis.uniandes.edu.co
En la vida diaria estamos en permanente contacto con las listas. En los almacenes vemos listas de precios, en la universidad listas de estudiantes y cursos, en las huelgas listas de peticiones. Nos debemos preguntar cuáles características tienen en común estos objetos, para así poder construir un modelo de todos ellos y poder simular su funcionamiento y operación.
Pensemos, por ejenplo, en una lista de compras. En ella debe existir un primer elemento, un segungo elemento y un último elemento. Además, debemos poder borrar cualquier nombre de la lista de compras e, igualmente, agregar uno nuevo en cualquier punto.
Definimos una lista 1st como una secuencia de cero o más elementos de un mismo tipo, y la representamos como:
1st = <e1 e2 ...en>
donde cada ei representa un elemto de la lista.
La longitud de una lista se define como el numero de elementos que la componen. Si la lista no tiene ningun elemento, lalista se encuentra vacía y su longitud es cero.
La posición de un elemento dentro de una lista es el lugar ocupado por dicho elemento dentro de la secuencia de valores que componen la estructura. Podemos hablar entonces del elemento que ocupa la i-ésima posición dentro de la lista 1st y hacerlo explícito en la representación mediante la siguiente representación:
1st = <X1 X2 ..... Xi .... XN>
que indica que Xi es el elemento que se encuentra en la posición
i de la lista 1st y que dicha lista consta de N elementos.
De acuredo con lo visto anteriormente una lista es una estructura muy flexible en la cual debe ser posible eliminar o consultar cualquiera de sus elementos e insertar un nuevo componente en cualquier punto.
El tipo abstracto se encuentra definido en función del tipo Elemento, el cual representa la clase de elementos que contendrá la lista. De esta manera estamos definiendo un TAD Lista, independiente del tipo de elemntos que contenga y únicamente abstrayendo lo escencial del comportamiento de estos objetos
La primera definición a considerar aquí es la de cuando dos lista son iguales. Dos listas 1st1 y 1st2 son iguales si ambas estructuras tienen el mismo número de componentes y, además, sus elementos son iguales uno a uno. Esto implica que el primer elemento de la primera lista debe ser igual primer elemento de la segunda, los segundos elementos de cada secuencia deben ser iguales y así sucesivamente hasta completar todas las posiciones válidas de ambas listas.
Debe ser claro que no es suficiente tener en las dos listas los mismos elementos, sino que, además , es necesario encontrarlos en el mismo orden.
La segunda definición se refiere a cuándo consideremos una lista incluida en otra. Se dice que 1st2 es una sublista de 1st1 si todos los elemtos de 1st2 se encuentran en 1st1, consecutivos y en el mismo orden.
Por último, una lista 1st1 es ordenada cuando definimos una relación de orden R entre sus elementos . En este caso, los elementos menores deben ir al comienzo de la secuencia e ir aumentando hacia el final de la misma.
1st = <e1 e2 ... en>
Para ser ordenada, debe cumplir que(ei <= ei+1) para todos los valores de i entre 1 y n-1. De ahí, se concluye que una lista ordenada se cumple : ei<= ej <= j .
Cualquier sugerencia o comentario enviarlo a:
jcvargas@isis.uniandes.edu.co
Tomado del libro:
"Estructuras de datos (Un enfoque desde tipos
abstractos)"
Jorge Villalobos, Alejandro Quintero, Mario Otero
Ediciones Uniandes