Embed Size (px)
Citation preview
Karim Guevara Puente de la Vega
UNSA, 2013
Estructura de Datos Lineales
Estructuras de Datos Lineales Listas Secuenciales
Estructura de Datos I 2
Agenda
Lista lineal
Lista lineal por medio de arreglos
Lista
Colección
Conjunto
Estructura de Datos I 3
Lista lineal
Secuencia de cero o más items x1,x2,…,xn en el cual xi es de un determinado tipo y n 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, xi es el primer item de la lista y xn el ú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.
Estructuras de Datos Básicas
Estructura de Datos I 4
Lista lineal (cont)
El conjunto de operaciones a ser definido depende de cada aplicación
Un conjunto de operaciones necesario a una mayoría de aplicaciones:
1. Verificar si la lista está vacía
2. Verificar si la lista está llena
3. Insertar un nuevo item inmediatamente después del i-ésimo item
4. Localizar el i-ésimo item para examinar y/o alterar el contenido
5. Retirar el i-ésimo item
Estructura de Datos I 5
Lista lineal (cont)
Un conjunto de operaciones necesario a una mayoría
de aplicaciones:
5. Combinar dos o más listas en una única
6. Partir una lista en dos o más listas
7. Hacer una copia de una lista
8. Ordenar los items de una lista
9. Buscar la ocurrencia de un item
Estructura de Datos I 6
Lista lineal (cont)
La lista lineal se puede representar por medio de un TAD Lista, definido por:
Hay varias opciones de estructuras de datos que permiten una implementación eficiente para listas (p.e. el tipo estructurado array).
typeName
listType
Domain
cada elemento del 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 la lista
insertar un elemento en la lista
ordenar la lista
destruir la lista
imprimir la lista
Estructura de Datos I 7
Implementación de Listas Lineales
Varias estructuras de datos pueden ser utilizadas
para representar una lista lineal.
Las dos representaciones más utilizadas son las
implementaciones son:
Por medio de arreglos
Por medio de punteros
Estructura de Datos I 8
Listas por medio de arreglos
Los items de la lista son almacenados en posiciones
continuas de la memoria.
La lista puede ser recorrida en cualquier dirección
La inserción de un nuevo item puede ser realizada
después del último item con costo constante
La inserción de un nuevo item en el medio de la lista
requiere una translación de todos los items
localizados después del punto de inserción.
Estructura de Datos I 9
Listas por medio de arreglos
Retirar un item del inicio de la lista requiere una
translación de los items para rellenar el espacio vacío
dejado.
x1
x2
xlongitud
. . .
. . .
xn
0
1
Primero =
Longitud - 1
Tamaño máximo - 1
Los items son almacenados en un
arreglo
Longitud apunta a la posición siguiente a
la del último elemento de la lista
El i-ésimo item de la lista está
almacenado en la i-ésima-1 posición del
arreglo, 0 i < longitud
Estructura de Datos I 10
Implementación de TAD Lista
La implementación puede ser por medio de un arreglo estático
de 1000 elementos (listType.h)
Template <class T> class ListType{
bool isEmpty();
//Precondition: La lista debe de existir.
//Postcondition: retorna true si la lista esta
vacía, false en otro caso.
bool isFull();
int search(T searchItem);
void insert(T newitem);
void remove(T removeitem);
void destroy();
void printList();
ListType();
private:
T list[1000];
int length;
};
Estructura de Datos I 11
Implementación de TAD Lista
listTypeImp.cpp
#include ”listType.h”
template<class T> bool listType::isEmpty(){
return(lenght==0)
}
template<class T> void listType::insert(T newitem){
if(!isFull())
list[lenght++]=newitem
}
template<class T> void listType::remove(T newitem){
if(!isEmpty()){
int i=search(newitem);
if(i>=0){
list[i]=list[lenght-1];
lenght--;
}
}
}
Si la lista está implementada utilizando arreglos dinámicos, la
declaración sería: (listDinamicType.h)
Estructura de Datos I 12
template <class X>
class listDinamicType {
listDinamicType(int = 1000);
~listDinamicType( );
bool isFull();
bool isEmpty();
void printList( );
bool insert(X );
X remove( int);
private:
X *list:
int lenght;
int size;
};
Implementación de TAD Lista dinámica
listDinamicTypeImp.cpp
Estructura de Datos I 13
template<class X>
listDinamicType::listDinamicType(int psize ) {
size = psize;
list = new X [size];
lenght=0;
}
template<class X> listDinamicType::~listDinamicType( ) {
if (list != NULL) {
delete[] list;
list=NULL;
lenght=0;
}
}
Implementación de TAD Lista dinámica
listDinamicTypeImp.cpp
Estructura de Datos I 14
template<class X> bool listDinamicType::isFull( ) {
return(length==size);
}
template<class X> bool listDinamicType::insert(X newitem) {
if (isFull()){
cout<<“Error! Lista llena \n”;
return false;
}
else {
list[lenght++] = newitem;
return true:
}
}
Implementación de TAD Lista dinámica
Estructura de Datos I 15
template<class X> X listDinamicType::remove(int position ) {
int item = -1;
if ( isEmpty() || position >= lenght)
cout<<“List is empty \n”;
else {
item = list[position];
for (int i = position; i < length-1; i++ )
list[i] = list[i+1];
lenght--:
}
return item;
}
template<class X> bool listCircleType::isEmpty( ){
return(length==0);
}
Implementación de TAD Lista dinámica
listDinamicTypeImp.cpp
listDinamicTypeImp.cpp
Estructura de Datos I 16
template<class X> void listDinamicType::printList( ) {
if ( isEmpty())
cout<<“Lista vacia \n”;
else {
for (int i = 0; i < lenght; i++ )
cout<< list[i];
}
}
Implementación de TAD Lista dinámica
Estructura de Datos I 17
Ventajas y desventajas
Ventaja:
Los apuntadores son implícitos en esta estructura.
Acceso directo al elemento i-ésimo por su posición
Desventajas:
Costo de la eliminación e inserción puede ser alta
(translación de todos los items).
No existe previsión sobre el crecimiento de la lista
Listas
Una lista es una secuencia de objetos ordenados, en la
que se dispone de un iterador especial, con el que se
puede:
insertar o eliminar elementos en cualquier posición
recorrer los elementos de la lista hacia adelante y
opcionalmente, hacia atrás
etc.
Algunas listas (Vectores) disponen de acceso posicional
eficiente
El orden es el que define la secuencia de elementos; no
necesariamente es su orden natural
Estructura de Datos I 18
Ejemplos de uso de listas
Escribir un método que reemplace todos los elementos de una lista que coincidan con un elemento, por otro elemento
Escribir una clase que represente una baraja de cartas españolas, con las siguientes operaciones:
constructor: inicialmente la baraja contiene las 40 cartas ordenadas
barajar: para cada carta i desde la última hasta la segunda se intercambia esa carta con la de la casilla de índice aleatorio entre 0 e i
Repartir: retorna una lista que contiene las num últimas cartas de la baraja, y las elimina de la baraja
Estructura de Datos I 19
Colecciones (collection) o bolsas (bag)
La colección es un ADT que permite almacenar grupos
de objetos llamados elementos:
pueden estar repetidos
no es preciso almacenar ninguna relación de orden o
secuencia
También se llaman bolsas
Estructura de Datos I 20
Operaciones básicas de las colecciones
Estructura de Datos I 21
Operaciones básicas de las colecciones
constructor: Crea la colección con cero elementos
añade: Añade el parámetro elElemento a la colección. Si elElemento es incompatible con los elementos que se almacenan en esta colección lanza una excepción
borra: Si existe en la colección al menos una instancia de elElemento, la borra de la colección y retorna true. En otro caso, retorna false
hazNula: Elimina todos los elementos de la colección, dejándola vacía
pertenece: Si existe en la colección al menos una instancia de elElemento, retorna true. En otro caso, retorna false
estaVacia: Si la colección está vacía retorna true. En otro caso, retorna false
tamaño: Retorna un entero que dice cuántos elementos hay en la colección
Estructura de Datos I 22
Ejemplo de usos
Una aplicación de una colección es almacenar una
lista de visitas a un lugar
una misma persona puede visitar el lugar varias veces
no interesa el orden en el que se hacen
interesa si alguien ha visitado el lugar o no, y cuántas
veces
Estructura de Datos I 23
Ejercicio
Crear una clase capaz de almacenar en un atributo
una colección de nombres de personas (Strings)
Escribir un método para añadir una visita
Escribir un método para saber cuántas visitas ha
hecho una persona (que deje la colección igual que
estaba)
Estructura de Datos I 24
Conjuntos (set)
Un conjunto es un ADT que permite almacenar grupos
de objetos llamados elementos de modo que:
no pueden estar repetidos
no es preciso almacenar ninguna relación de orden o
secuencia
Además suelen tener operaciones para operar con
ellos:
Intersección
Unión
diferencia
Estructura de Datos I 25
Operaciones básicas de los conjuntos
Estructura de Datos I 26
Estructura de Datos I 27
Operaciones básicas de los conjuntos
Las operaciones básicas son idénticas a las de las colecciones, con la excepción de añade:
constructor: Crea el conjunto con cero elementos
añade: Si elElemento ya pertenece al conjunto retorna false. En caso contrario, añade el parámetro elElemento al conjunto y retorna true. Si elElemento es incompatible con los elementos que se almacenan en este conjunto lanza una excepción
borra: Si existe en el conjunto al menos una instancia de elElemento, la borra del conjunto y retorna true. En otro caso, retorna false
hazNulo: Elimina todos los elementos del conjunto, dejándolo vacío
pertenece: Si existe en el conjunto al menos una instancia de elElemento, retorna true. En otro caso, retorna false
estaVacio: Si el conjunto está vacío retorna true. En otro caso, retorna false
tamaño: Retorna un entero que dice cuántos elementos hay en el conjunto
Estructura de Datos I 28
Operaciones básicas de los conjuntos
intersección: Retorna un conjunto que contiene los elementos comunes al conjunto actual y a otroConjunto.
unión: Retorna un conjunto que contiene los elementos del conjunto actual y los de otroConjunto.
diferencia: Retorna un conjunto que contiene los elementos del conjunto actual que no pertenecen a otroConjunto.
incluidoEn: Retorna true si todos los elementos del conjunto original pertenecen a otroConjunto, y false en caso contrario.
Estructura de Datos I 29
Ejemplo de uso
En el ejemplo anterior, añadir un método para mostrar
todos los elementos duplicados (aquellos con más de una
visita).
Hacer un método para obtener un conjunto con todas las
visitas, pero sin duplicidades.
