Universidad Simón Bolívar
Departamento de Computación
CI2126 Computación II
Gabriela Ochoa
Tipos Abstractos de Datos
Abstracción.
Consiste
en ignorar los detalles de la manera particular en que está hecha una cosa,
quedándonos sólamente con su visión general.
Tipo
de dato abstracto (TAD).
Se define
como un conjunto de valores que pueden tomar los datos de ese tipo, junto
a las operaciones que los manipulan.
TAD = valores
(tipo de dato) + operaciones.
La abstracción
de datos encapsula u oculta los datos y sólo permite su utilización mediante
las operaciones que se han descrito.
Las operaciones
pueden ser de 3 tipos basicos:
(G) Operaciones
Generadoras, o costructoras
(A) Operaciones
de Acceso o Observacion
(M) Operaciones
de transformacion, Modificadores
EJEMPLO.
ESPECIFICACIÓN DEL TAD CONJUNTO.
Tipos
de datos:
Conjunto,
elemento, lógico.
Operaciones:
CONJUNTO_VACIO:
-> conjunto (g), crea un conjunto vacio
INSERTAR:
elemento x conjunto -> conjunto (g), inserta un elemento en el conjunto
g
BORRAR:
elemento x conjunto -> conjunto (m)
UNION:
conjunto x conjunto -> conjunto (m)
INTERSECCIÓN:
conjunto x conjunto -> conjunto (m)
DIFERENCIA:
conjunto x conjunto -> conjunto (m)
PERTENECE:
elemento x conjunto -> lógico (a)
ES_VACIO:
conjunto -> lógico (a)
Veremos
dos maneras (Estaticas) de implementar el tipo conjuntos
- Utilizando
un vector de valores lógicos,
- Utilizando
un vector que contine los elementos.
IMPLEMENTACIÓN
CON VECTORES DE BITS.
#define True 1
#define False 0
#define
M 100
/* Maximo elemento de un Conjunto */
Void ConjuntoVacio(int
A[M])
{
int i;
for ( i=1; i<
M; i++)
A[i] = False
}
Void Insertar(int i, int A[M])
{
A[i] = True;
}
Void Borrar(int i, int A[M])
{
A[i] = False;
}
int Pertenece(int i, int A[M])
{
return (A[i]);
}
int EsVacio(int A[M])
{
int i = 1; Vacio
= True;
for (i=1; i <
M; i++) {
if (A[i]) {
Vacio = False
break;
}
}
return (Vacio);
}
void Unión(int
A[M], B[M], C[M])
{
for ( i=1; i<
M; i++)
C[i] = A[i] || B[i];
}
void Unión(int
A[M], B[M], C[M])
{
for ( i=1; i<
M; i++)
C[i] = A[i] && B[i];
}
IMPLEMENTACIÓN
CON VECTORES CON LOS ELEMENTOS.
#define
M 100
/* Tipos
*/
struct
_Conjunto {int Elementos[M], Cardinal}
Typedef struct _Conjunto Conjunto
void ConjuntoVacio(Conjunto
*A)
{
*A.Cardinal = 0
}
int EsVacio(Conjunto A) {
return (A.Cardinal)
}
int Pertenece(int
i, Conjunto A) Variables
{
int j = 1, esta = false;
while ((j<=A.Cardinal) && !esta) {
if ( A.Elementos[j]
== i)
esta = true
else
j++;
}
return (esta)
}
void Insertar(int
i, Conjunto A)
{
if ¡Pertenece(i,A) {
if
(A.Cardinal == M)
printf(“Error. No hay sitio\n”);
else {
A.Cardinal = A.Cardinal+1
A.Elementos[A.Cardinal]
= i;
}
}
}
void Borrar(i:TipoElemento, A:Conjunto)
{ int j = 0, esta = false;
while ((j<A.Cardinal)
&& ¡está) {
if ( A.Elementos[j]
== i)
esta = true;
j++;
}
if (está) {
A.Elementos[j] = A.Elementos[A.Cardinal]
A.Cardinal = A.Cardinal – 1
}
VOID Unión
(A,B,C:Conjunto)
{
int i,j
for (i=0; i<=
A.Cardinal;i++) {
C.Elementos[i] = A.Elementos[i]
}
j= A.Cardinal
for ( i=0; j<
B.Cardinal; j++) {
if (¡Pertenece (B.Elementos[i],A) {
if (j==M entonces)
printf(“ Error. No hay sitio\n”);
else
C.Elementos[j]=B.Elementos[i]
}
}
C.Cardinal = j
}
void Intersección(Conjunto A,B, *C)
{
int i,j=0;
for(i=0; i< A.Cardinal;i++) {
if (Pertenece(A.Elementos[i],B))
{
j++;
C.Elementos[j] = A.Elementos[i]
}
}
C.Cardinal = j
}
Caracteristicas
de las dos Implementaciones
Implementación
con vectores Booleanos.