Tipos de Datos Abstractos - Páginas Personalesprofesores.fi-b.unam.mx/.../EDAI07TiposDeDatosAbstractos.pdfEstructuras de Datos y Algoritmos I Tipos de Datos Abstractos Página 3 de

Estructuras de Datos y Algoritmos I Tipos de Datos Abstractos Página 0 de 31

ESTRUCTURAS DE DATOS Y

ALGORITMOS I.

Tipos de Datos Abstractos.


Concepto de Abstracción.

• La Abstracción en Computación es un mecanismo que

permite utilizar un objeto cualquiera sin necesidad de conocer

los detalles de su implementación.

• Los objetos abstractos deben proporcionar una interfaz

pública fácil de usar y de entender, que es la que permite

manipular el objeto sin necesidad de conocer su

funcionamieno interno.


Tipos de Datos Abstractos.

• Un tipo de dato abstracto (TDA) o Abstract Data Type (ADT)

es un grupo de elementos creado de manera específica por

un desarrollador para cierto fin.

• Un tipo de dato abstracto es una abstracción que permite

modelar las características de un grupo de elementos como si

se tratara de un solo elemento.

• Un tipo de dato abstracto se puede manipular de forma

similar a los tipos de datos predefinidos dentro de un lenguaje

de programación.


Implementación de TDAs en C.

• La implementación de un tipo de dato abstracto depende

directamente del lenguaje de programación que se utilice.

• En el lenguaje C, los tipos de datos abstractos se

implementan mediante estructuras (palabra reservada

struct) o uniones (palabra reservada union).


Estructuras.

• Las estructuras en C son un tipo de dato que puede contener

varios elementos, pero a diferencia de los arreglos los

elementos pueden ser de diferentes tipos.

• Las estructuras se emplean para representar registros, por

ejemplo si se desea mantener la información de los libros de

una biblioteca, se podría crear una estructura con los

siguientes elementos:

❖ Título.

❖ Autor.

❖ Materia.

❖ Código ISBN.

ISBN International Standard Book Number


Declaración de Estructuras.

• La sintaxis para declarar una estructura es la siguiente:.

struct [structure name] {

member definition;

member definition;

...

member definition;

} [one or more structure variables] ;

Nótese el

punto y coma;

al final de la

declaración


Ejemplo.

• La sintaxis para declarar la estructura del ejemplo anterior

sería:

struct Books {

char title[50];

char author[50];

char subject[100];

int book_id;

} book;


Acceso a Miembros de Estructuras.

• Para accesar cualquier miembro de una estructura se usa el

operador punto (.).

• El operador se especifica como un punto entre el nombre de

la variable de la estructura y el miembro de la estructura que

se desea accesar.

• Por ejemplo para accessar el título del libro en el ejemplo se

codificaría:

struct Books book1;

book1.title;


Ejemplo.

#include <stdio.h>

#include <string.h>

struct Books {

char title[50];

char author[50];

char subject[100];

int book_id;

};

int main( ) {

struct Books book1; /* Declare book1 of type Book */

struct Books book2; /* Declare book2 of type Book */

/* book 1 specification */

strcpy( book1.title, "C Programming");

strcpy( book1.author, "Sara Lee");

strcpy( book1.subject, "C Programming Tutorial");

book1.book_id = 6495407;

continúa…


Ejemplo (2).


strcpy( book2.title, "Telecom Billing");

strcpy( book2.author, "Lili Ledi");

strcpy( book2.subject, "Telecom Billing Tutorial");


/* print Book1 info */

printf( "Book 1 title : %s\n", book1.title);

printf( "Book 1 author : %s\n", book1.author);

printf( "Book 1 subject : %s\n", book1.subject);

printf( "Book 1 book_id : %d\n", book1.book_id);

/* print Book2 info */

printf( "Book 2 title : %s\n", book2.title);

printf( "Book 2 author : %s\n", book2.author);

printf( "Book 2 subject : %s\n", book2.subject);

printf( "Book 2 book_id : %d\n", book2.book_id);

return 0;

} Ejemplo01.c


Estructuras como Argumentos de

Funciones.

• Se pueden pasar estructuras a una función como argumentos

de la misma manera que cualquier otro tipo de dato

• Recuerde que las estructuras son tipos de datos abstractos.


Ejemplo.

#include <stdio.h>

#include <string.h>

struct Books {

char title[50];

char author[50];

char subject[100];

int book_id;

};

/* function declaration */

void printBook( struct Books book );

int main( ) {

struct Books book1; /* Declare book1 of type Books */







continúa…


Ejemplo (2).






/* print book1 info */

printBook( book1 );

/* Print book2 info */

printBook( book2 );

return 0;

}

void printBook( struct Books book ) {

printf( "Book title : %s\n", book.title);

printf( "Book author : %s\n", book.author);

printf( "Book subject : %s\n", book.subject);

printf( "Book book_id : %d\n", book.book_id);

}

Ejemplo02.c


Pointers a Estructuras.

• Se pueden definir pointers a estructuras de la misma manera

que se definen pointers a otra variable.

struct Books *struct_pointer;

• Después se puede guardar la dirección de la estructura en el

pointer.

struct_pointer = &book1;

• Para accesar a los miembros de la estructura utilizando un

pointer se usa el operador −>:

struct_pointer −>title;


Ejemplo.

#include <stdio.h>

#include <string.h>

struct Books {

char title[50];

char author[50];

char subject[100];

int book_id;

};

/* function declaration */

void printBook( struct Books *book );

int main( ) {








continúa…


Ejemplo (2).





/* print book1 info by passing address of book1 */

printBook( &book1 );

/* print Book2 info by passing address book2 */

printBook( &book2 );

return 0;

}

void printBook( struct Books *book ) {

printf( "Book title: %s\n", book->title);

printf( "Book author: %s\n", book->author);

printf( "Book subject: %s\n", book->subject);

printf( "Book book_id: %d\n", book->book_id);

}

Ejemplo03.c


Uniones.

• Una union (sin acento) es un tipo especial de dato abstracto

disponible en C, que permite almacenar diferentes tipos de

datos en la misma localidad de memoria.

• Se puede definir una union con varios miembros pero

solamente un miembro puede contener un valor en un

momento dado.

• Las uniones proporcionan un medio eficiente de usar la

misma localidad de memoria para varios propósitos.


Declaración de Uniones.

union [union name] {

member definition;

member definition;

...

member definition;

} [one or more union variables] ;

La sintaxis para declarar una union es la siguiente:

Nótese el

punto y coma;

al final de la

declaración


Diferencia entre union y struct.

• En las estructuras struct, cada miembro de la misma ocupa

su localización en la memoria y por tanto el tamaño de la

estructura es igual a la suma de los tamaños de sus

miembros.

• En las uniones union, los miembros ocupan la misma

localidad de memoria y por tanto su tamaño es el tamaño del

mayor de los miembros.


Ejemplo.

#include <stdio.h>

#include <string.h>

struct Books {

char title[50];

char author[50];

char subject[100];

int book_id;

};

union UBooks {

char title[50];

char author[50];

char subject[100];

int book_id;

};

int main( ) {


union UBooks book2; /* Declare book2 of type UBooks */

printf("Tamaño de la estructura = %d bytes\n", sizeof(book1));

printf("Tamaño de la union = %d bytes", sizeof(book2));

} Ejemplo04.c


Acceso a Miembros de una Union.

• Para accesar cualquier miembro de una union se usa, al

igual que en las estructuras, el operador punto.

• El operador punto se codifica entre la variable de la union

y el miembro al que se quiere tener acceso.

• Se debe usar la palabra clave union para definir variables

de tipo union.


Ejemplo.

#include <stdio.h>

#include <string.h>

union Data {

int i;

float f;

char str[20];

};

int main( ) {

union Data data;

data.i = 10;

data.f = 220.5;

char *p = "C Programming";

strcpy( data.str, p);

printf( "data.i : %d\n", data.i); /* data.i is corrupted */

printf( "data.f : %f\n", data.f); /* data.f is corrupted */

printf( "data.str : %s\n", data.str);

return 0;

} Ejemplo05.c

Cuando se ejecuta este ejemplo se verá que los resultados no son correctos

porque las variables de la union comparten localidades de memoria.


Ejemplo.

#include <stdio.h>

#include <string.h>

union Data {

int i;

float f;

char str[20];

};

int main( ) {

union Data data;

data.i = 10;

printf( "data.i : %d\n", data.i);

data.f = 220.5;

printf( "data.f : %f\n", data.f);

char *p = "C Programming";

strcpy( data.str, p);

printf( "data.str : %s\n", data.str);

return 0;

} Ejemplo06.c

Este ejemplo funciona correctamente porque se despliegan las variables una a una.


Bit Fields.

• Los bit fields son un tipo especial de campos de estructuras en donde se especifica la longitud del campo en bits, con lo cual se ahorra espacio en memoria.

• Por ejemplo, la estructura:

struct date {

unsigned int d;

unsigned int m;

unsigned int y;

};

requiere 12 bytes de memoria (4 para cada variable int) pero si

sabemos que para representar el día basta con 5 bits y el mes con 4

bits, podemos reescribir la estructura como se muestra en la siguiente

lámina.


Un Bit Field.

Estructura con bit fields.

struct date {

unsigned int d : 5; // 5 bits bastan para el día

unsigned int m: 4; // 4 bits bastan para el mes

unsigned int y;

};

Esta estructura requiere solamente 8 bytes porque los 9 bits de

los 2 bit fields caben en un solo int de 4 bytes.


Ejemplo.

#include <stdio.h>

struct date {

unsigned int d: 5; // 5 bits son suficientes para el día

unsigned int m: 4; // 4 bits son suficientes para el mes

unsigned int y; // el año sigue usando 4 bytes

};

int main() {

printf("Size of date is %d bytes\n", sizeof(struct date));

struct date dt = {31, 12, 2018};

printf("Date is %d/%d/%d", dt.d, dt.m, dt.y);

return 0;

}

Ejemplo07.c


Declaración de Bit Fields.

• La sintaxis para declarar un bit field es la siguiente:

struct {

type member_name : width;

};

en donde:

• type es un tipo de dato que puede ser int, signed int, or unsigned

int.

• member_name es el nombre del bit field.

• width es el número de bits en el campo. Debe ser menor o igual al

número de bits que normalmente ocupa el tipo de dato type.

Nota. No se permite asignar a un miembro del bit field un valor que

ocupe más bits de los mencionados en width:


Ejemplo.

#include <stdio.h>

#include <string.h>

struct {

unsigned int age : 3;

} Age;

int main( ) {

Age.age = 4;

printf( "Sizeof( Age ) : %d\n", sizeof(Age) );

printf( "Age.age : %d\n", Age.age );

Age.age = 7;


Age.age = 8;


return 0;

} Ejemplo08.c

En este ejemplo, el compilador marcará un warning al tratar de asignar

el valor 8 a la variable age, porque 8 necesita más de 3 bits para

representarse en binario.


typedef.

• El lenguaje C proporciona la palabra clave typedef que sirve para darle un nuevo nombre (alias) a un tipo de dato.

• Por ejemplo, el siguiente postulado define el término BYTE para el tipo unsigned char:

typedef unsigned char BYTE;

• Después de esta definición se puede usar BYTE para definir variables que en realidad son de tipo unsigned char:

BYTE b1, b2;

• Por convención, se usan nombres en mayúsculas para recordar al usuario que estos tipos son alias del tipo real.


typedef para Tipos Abstractos.

• También es posible asignar un nuevo nombre a tipos de

datos abstractos.

• Por ejemplo, se puede usar typedef con una estructura para

definir un nuevo tipo de dato abstracto y usar ese tipo de dato

para definir las variables de la estructura directamente.


Ejemplo.

#include <stdio.h>

#include <string.h>

typedef struct Books {

char title[50];

char author[50];

char subject[100];

int book_id;

} Book;

int main( ) {

Book book;

strcpy( book.title, "C Programming");

strcpy( book.author, "Sara Lee");

strcpy( book.subject, "C Programming Tutorial");

book.book_id = 6495407;

printf( "Book title : %s\n", book.title);

printf( "Book author : %s\n", book.author);

printf( "Book subject : %s\n", book.subject);

printf( "Book book_id : %d\n", book.book_id);

return 0;

} Ejemplo09.c


typedef vs #define.

• #define es una directiva al compilador de C que también se

usa para asignar alias a elementos del lenguaje.

• Sin embargo, tienen las siguientes diferencias.

– typedef está limitado a asignar alias a tipos de datos.

– #define se puede usar para definir alias también a

valores, por ejemplo, se puede definir el valor 1 como

UNO.

– La interpretación de typedef es hecha por el compilador.

– #define es procesado por el preprocesador.


Ejemplo.

#include <stdio.h>

#define TRUE 1

#define FALSE 0

int main( ) {

printf( "Value of TRUE : %d\n", TRUE);

printf( "Value of FALSE : %d\n", FALSE);

return 0;

}

Ejemplo10.c

Documents

Tipos de Datos Abstractos - Páginas Personalesprofesores.fi-b.unam.mx/.../EDAI07TiposDeDatosAbstractos.pdfEstructuras de Datos y Algoritmos I Tipos de Datos Abstractos Página 3 de