Download Tipos Abstractos de Datos (TAD) - Itsp

Tipos Abstractos de Datos
(TAD)
Estructuras de Datos y Algoritmos
Mtr. Ing. Nancy López
¿Qué son los TAD?
• Con los lenguajes de programación
estructurados (años ‘60) surge el concepto de
tipo de datos.
• En los ‘70 aparece el concepto de TAD: un
tipo de datos no sólo es el conjunto de
valores, sino también sus operaciones con sus
propiedades.
¿Pero qué son los TAD?
• El concepto de TAD ya existe en los lenguajes
de programación estructurados: los tipos
predefinidos.
• Por ejemplo:
• Tipo de dato int
• Valores: -32767 al +32768
• Operaciones: +, - , *, /, %
• Propiedades de las operaciones: a+b=b+a
Definición de TAD
• Un Tipo Abstracto de Datos es un conjunto de
valores y de operaciones definidos mediante
una especificación independiente de
cualquier representación.
• TAD = valores + operaciones
Ejemplo de TAD
• En c++ no existe el tipo de dato fecha, pero
podríamos crearlo:
Estructura fecha{dia, mes, anio: enteros};
• Operaciones válidas:
Crear (entero, entero, entero): fecha
Incrementar(fecha, entero, char): fecha
Diferencia(fecha1, fecha2,char): entero
Mes(fecha):entero
TAD Lista
typedef struct nodo
{
int valor;
nodo *siguiente;
} tipoNodo;
valor
Sigui
ente
//tipoNodo es el tipo para declarar nodos
typedef tipoNodo *pNodo; //tipo para declarar punteros a un
nodo
typedef tipoNodo *Lista; //tipo para declarar listas
En el main:
Lista L=NULL; //creo la variable tipo Lista
TAD Lista
• Lista vacía
L
NULL
Agregar nodo a lista vacía
L
valor
Sigui
ente
NULL
L apunta al nuevo nodo y siguiente apunta a NULL.
TAD Lista
• Insertar al final
L
•valor
•Sigui
ente
NULL
valor
Sigui
ente
NULL
TAD Lista
• Insertar al principio en lista no vacía.
L
•valor
•Sigui
ente
NULL
valor
Sigui
ente
NULL
TAD Lista
• Insertar al medio en lista no vacía.
L
•valor
•Sigui
ente
valor
valor
Sigui
ente
Sigui
ente
NULL
typedef struct nodo{
TAD Lista
int valor;
nodo *siguiente;
} tipoNodo;
//tipoNodo es es el tipo para declarar nodos
typedef tipoNodo *pNodo; //tipo para declarar
punteros a un nodo
typedef tipoNodo *Lista; //tipo para declarar listas
En el main:
Lista lista=NULL; //creo la variable tipo Lista
TAD Lista
pNodo crearNodo(int); //devuelve el nodo a insertar
bool listaVacia(Lista); //devuelve true si la lista está
vacía
void insertarFinal(Lista &, pNodo); //inserta nodo al
final
void insertarInicio(Lista &, pNodo); //inserta nodo al
inicio
void insertarOrdenado(Lista &, pNodo); //inserta nodo
ordenadamente
void mostrarLista(Lista); //muestra el contenido de la
lista
TAD Lista
Operación crearNodo
pNodo crearNodo(int val) //si hubiera más valores, recibo más valores
{
pNodo n=new tipoNodo;
n->valor=val;
n->siguiente=NULL;
return n;
}
TAD Lista
Operación listaVacia
bool listaVacia(Lista lista)
{
return (lista == NULL);
}
• //recibe como parámetro el puntero al primer
valor de la lista
TAD Lista
void insertarOrdenado(Lista &lista, pNodo nuevo) {
pNodo anterior;
if(listaVacia(lista) || (lista)->valor > nuevo->valor) {
nuevo->siguiente = lista;
lista = nuevo; }
else {
anterior = lista;
while(anterior->siguiente && anterior->siguiente->valor
<= nuevo->valor)
{anterior = anterior->siguiente;}
nuevo->siguiente = anterior->siguiente;
anterior->siguiente = nuevo;
}
}
TAD Lista
void mostrarLista(Lista lista) {
pNodo aux= lista;
if(listaVacia(lista)) cout<< "Lista vacía“<<endl;
else {
while(aux) {
cout<<" -> "<< aux->valor;
aux = aux->siguiente;
}
cout<<endl;
}
TAD Lista
int main (int argc, char *argv[]) {
Lista lista = NULL;
int valor;
char seguir;
do
{cout<<"Ingrese valor ";
cin>>valor;
insertarOrdenado (lista, crearNodo(valor));
cout<<"Desea seguir ingresando datos?";
cin>>seguir;
}while (seguir=='s');
mostrarLista(lista);
return 0;
}
TAD Lista
Ejercicio
• Implemente insertar al inicio e insertar al final.