Listas Secuenciales

Estructura de Datos Lineales
Estructuras de Datos Lineales
Listas Secuenciales

Karim Guevara Puente de la Vega
kguevara72@gmail.com
UCSM, 2014

Agenda






Lista lineal
Listalineal por medio de arreglos
Lista ordenada
Colección
Conjunto

Estructuras de Datos Básicas
Lista lineal
 Secuencia de cero o más items x1,x2,…,xn en el cual
xi es de un determinado tipo yn representa el
tamaño de la lista.
 Su principal propiedad estructural envuelve las
posiciones relativas de los items en una dimensión:
 Asumiendo n  1, x1 es el primer item de la lista y xnel último
 xi precede xi+1 para i =1,2,…,n-1
 xi sucede xi-1 para i =2,…,n
 El elemento xi está en la i-ésima posición.

Lista lineal (cont)




El conjunto de operaciones a serdefinido depende
de cada aplicación
Un conjunto de operaciones necesario a una mayoría
de aplicaciones:
1.
2.
3.

4.

5.

Verificar si la lista está vacía
Verificar si la lista está llenaInsertar un nuevo item inmediatamente después del iésimo item
Localizar el i-ésimo item para examinar y/o alterar
el contenido
Retirar el i-ésimo item

Lista lineal (cont)


Un conjunto deoperaciones necesario a una mayoría
de aplicaciones:
5.
6.

7.
8.
9.

Combinar dos o más listas en una única
Partir una lista en dos o más listas
Hacer una copia de una lista
Ordenar los itemsde una lista
Buscar la ocurrencia de un item

Lista lineal (cont)


La lista lineal se puede representar por medio de un TAD Lista,
definido por:
typeName
listType
Domain
cada elementodel tipo listType es un
conjunto de hasta 1000 numeros
Operations
comprobar si la lista está vacía
comprobar si la lista está llena
buscar un elemento dado en la lista
eliminar un elemento de lalista
insertar un elemento en la lista
ordenar la lista
destruir la lista
imprimir la lista



Hay varias opciones de estructuras de datos que permiten una
implementación eficiente para...