Estructura de Datos

M. en C. Joel Omar Juárez Gambino

Temario

• Abstracción en lenguajes de programación –Tipos Abstractos de Datos –Especificación de los TAD

• Pilas–Especificación del TAD Pila –Representación estática –Representación dinámica

• Colas–Especificación del TAD Cola –Representación estática –Representación dinámica –Colas circulares –Colas de prioridades

Temario• Listas enlazadas

– Operaciones en listas enlazadas

– Listas doblemente enlazadas

• Tablas Hash

– Operaciones de una tabla hash

• Recursividad

– Directa e indirecta

– Backtracking

• Arboles binarios

– Recorridos de un árbol

– Arboles de Expresión

– Árboles de Búsqueda

Temario• Árbol Equilibrado de Búsqueda

– Rotación simple – Rotación doble

• Árboles B – Tipo Abstracto Árbol

• Ejemplos de Aplicaciones con Estructuras de Datos

• Implementación de aplicaciones – Definición y análisis del problema – Diseño y Programación

Bibliografia

Allen Weiss Mark, Estructuras y Algoritmos 2a. Ed.,. Addison -Wesley.

Cairo Osvaldo, Estructuras de Datos, Mc. Graw Hill

Heileman Gregory L., Estructuras de Datos, Algoritmos y Programación Orientada a Objetos, Mc. Graw Hill

Ros Muñoz Salvador, Estructura De Datos Y Algoritmos, Pearson Educación

Tenenbaum Aaron, Langsam Yedidyah, Estructuras de Datos en C, 2a Edición

Introducción

• Una computadora es una máquina que manipula información. Es importante para un ingeniero en sistemas comprender como se organiza, manipula y emplea la información en la computadora.

Memoria

• La memoria de una computadora esta dividida en tres secciones: la memoria principal, la memoria secundaria (persistente) y la memoria cache.

Memoria principal

• La memoria principal, también conocida como memoria de acceso aleatorio (RAM), es donde se almacenan las instrucciones (programas) y datos. Es importante recordar que esta memoria es volátil y la información se perderá una vez que se apague la computadora.

Memoria secundaria

• La memoria secundaria es un dispositivo de almacenamiento externo tal como un disco duro, la cual también almacena datos e instrucciones. La información almacenada en estos dispositivos es persistente.

Memoria cache

• La memoria cache es utilizada para almacenar instrucciones que se utilizan de manera frecuente, así como datos que han sido o serán utilizados por la unidad central de proceso.

• Un segmento de la memoria caché es conocido como registro. Un registro se utiliza para almacenar de manera temporal instrucciones y datos.

Almacenamiento

• Una unidad de memoria generalmente almacena un byte de información, sin embargo los datos usados en un programa pueden ser grandes y requerir de más bytes para su almacenamiento.

• Es por esta razón que cualquier dato que se vaya a almacenar en la computadora requiere informarle a la máquina cuanto memoria necesita reservar para el tipo de dato que utilizaremos.

Tipos de datos

• Los tipos de datos más comunes son:– Entero– Flotante– Caracter– Booleano

Organización de la memoria

• La memoria la podemos representar como una serie de cajas organizadas en grupos de 8 bits.

• A cada una de las 8 cajas se le asigna un número único llamado dirección de memoria.

• Generalmente las direcciones de memoria se representan a través de números hexadecimales.

Organización de la memoria

23FF41 23FF42 23FF43 23FF44

Abstracción

• A pesar de que todas las computadoras cuentan con arquitecturas similares (CPU, Memoria, Dispositivos E/S) difieren en la forma en la que se administran estos recursos.

• La cantidad de memoria que se reserva para un dato de tipo entero varia dependiendo de la arquitectura.

Abstracción

• Cuando se desea plantear un algoritmo no se consideran algunos detalles particulares de la arquitectura en la cual se implementará.

• Esto ayuda a que la solución propuesta pueda ser fácilmente adaptada.

• A esta característica se le llama abstracción.

Tipo de dato abstracto (TDA)

• Un tipo de dato abstracto (TDA) es un conjunto de datos u objetos al cual se le asocian operaciones.

• El TDA provee de una interfaz con la cual es posible realizar las operaciones permitidas, abstrayéndose de la manera en como estén implementadas dichas operaciones.

Especificación del TDA

• Hay dos formas de realizar la especificación.– Formal: Mediante axiomas

algebraicos– Informal: Usando el lenguaje

natural apoyándose en un conjunto de cláusulas

Especificación del TDA

Los TDA están formados por los datos (estructuras de datos) y las operaciones (procedimientos y funciones) que se realizan sobre esos datos.

El conjunto de operaciones definidas sobre el TAD debe ser cerrado, es decir, sólo se debe acceder a los datos mediante las operaciones abstractas definidas sobre ellos.

Ejemplo TDA

• Definición del tipo – Número racional: conjunto de pares de

elementos (a, b) de tipo entero, con b <> 0

• Operaciones

Nombre Forma Operación

CrearRacional a,b (a,b)

Suma (a,b) + (c,d) (a*d + b*c, b*d)

Resta (a,b) – (c,d) (a*d - b*c, b*d)

Producto (a,b) * (c,d) (a*c, b*d)

Division (a,b) / (c,d) (a*d, b*c)

Características TDA

• Un TDA es el elemento básico de la abstracción de datos

• Su desarrollo es independiente del lenguaje de programación utilizado, por lo que este debe verse como una caja negra

Características TDA

• Para construir un TDA debemos– Exponer una definición del tipo– Definir las operaciones (funciones y

procedimientos) que permitan operar con instancias de ese tipo

– Ocultar la representación de los elementos del tipo, de modo que sólo se pueda actuar sobre ellos con las operaciones proporcionadas

– Poder hacer instancias múltiples del tipo

Características TDA

• Una vez definido el TDA se escoge una representación interna utilizando los tipos que proporcionan el lenguaje y/o otros TDA ya definidos previamente

struct Tracional{ int a; int b;};typedef struct Tracional Nracional;

Apuntadores

• El manejo de apuntadores es una de las características por las que el lenguaje C es muy poderoso

• Permite manejar estructuras de datos que pueden crecer y encogerse en tiempo de ejecución

• Los apuntadores son variables cuyos valores son direcciones de memoria

• Un apuntador contiene la dirección una variable que contiene un valor específico

Operador de dirección

• Cuando se declara una variable el compilador automáticamente asigna celdas de memoria y una dirección donde almacenará los datos

• La dirección de memoria de una variable puede ser determinada mediante la expresión &identificador

• El operador & es llamado operador de dirección, que proporciona la dirección del operando

Operador de indirección

• Para poder almacenar la dirección de una variable se requiere un tipo de dato especial, un apuntador

• Para declarar un apuntador se utiliza el operador * llamado operador de indirección

• Ejemplo:

int u = 3;

int *pu;

pu = &u;

F8E

3

Dirección EC7

Dirección F8E

pu

u

Operador de indirección

• El operador & sólo puede actuar sobre operandos con dirección única, como variables ordinarias o arreglos, por lo que no actúa sobre expresiones aritméticas (2 + a)

• El operador * solo puede actuar sobre operandos que sean punteros.

• Si se utiliza la expresión *identificador tendremos acceso al valor contenido dentro de la dirección de memoria que tiene almacenada la variable apuntador

Ejemplo

#include <stdio.h>int main(){ int u1, u2, v3 = 3; int *pv; u1 = 2 * (v3 + 5);

pv = &v3; u2 = 2 * (*pv + 5);

printf (“u1=%d u2= %d”, u1, u2) return (0);}

• Una referencia indirecta puede aparecer también en la parte izquierda de una instrucción de asignación

• Esto proporciona otro método para asignar un valor a una variable o a un elemento de arreglo

• Ejemplo: int v = 3; int *pv; pv = &v; *pv = 0;

Declaración de apuntadores

• Un apuntador al igual que cualquier otra variable requiere ser declarado antes de usarlo

• Sintaxis:tipo_dato *ptrvar

• Donde:– tipo_dato: es el tipo de dato al cual estará

direccionado el apuntador– ptrvar: es el nombre de la variable apuntador

• Se puede incializar el valor de un apuntador asignando un cero (0), o la constante NULL

Paso de parámetros por referencia

• Existen dos maneras de pasar argumentos a una función: por valor y por referencia

• Los argumentos en C se pasan por valor de manera automática, sin embargo a veces es necesario modificar este comportamiento

• Para pasar argumentos por referencia se utiliza el operador de dirección y los apuntadores

Paso de parámetros por referencia

• Cuando un argumento se pasa por referencia la dirección de dicho argumento es enviada a la función

• El contenido de esta dirección puede ser accedido libremente dentro de la función y de la rutina de llamada

• Cualquier cambio que se realiza sobre el argumento será reconocido en ambas, la función y la rutina de llamada

Apuntadores y arreglos

• Cuando se utiliza el nombre de un arreglo en C, en realidad estamos utilizando un apuntador al primer elemento del arreglo

• Si x es un arreglo unidimensional, entonces la dirección al primer elemento del arreglo se puede expresar tanto como &x[0] o simplemente como x

• Se tienen dos métodos para poder escribir la dirección de cualquier elemento del arreglo, &x[i] o (x + i)

Asignación dinámica de memoria

• Debido a que un arreglo es en realidad un apuntador al primer elemento de su estructura, se puede declarar una variable de arreglo como apuntador en vez de su forma convencional

• Una variable declarada como apuntador no esta direccionada a ningún espacio de memoria inicialmente

Función malloc

• Se puede utilizar la función malloc para asignar memoria a una variable apuntador

• Sintaxis:void *malloc(size_t size)

• Esta función reserva el espacio size de bytes. Si se pudo asignar el espacio regresa un puntero al dicho espacio de memoria, en caso contrario regresa un apuntador nulo (NULL)

• Ejemplo:char* ptr = (char*)malloc(1000);

Función sizeof

• La función malloc requiere conocer cuantos bytes se desean reservar

• Si se quiere reservar una zona para diez enteros habrá que multiplicar diez por el tamaño de un entero

• La función sizeof retorna al tamaño en bytes de un elemento del tipo recibido como argumento

• Sintaxis:sizeof(tipo_dato);

• Ejemplo:int *x;x = (int *) malloc (10 * sizeof(int));

Punteros y arreglos multidimensionales

• Un arreglo unidimensional puede ser representado en términos de un apuntador y un desplazamiento

• Un arreglo multidimensional puede ser representado con una notación similar

Ejemplo

• Si se desea crear un arreglo bidimensional de enteros con 10 filas y 20 columnas se puede declarar como:

int x[10][20];

O también:

int (*x) [20];

/*apuntador a un grupo de arreglos unidimensionales de 20 elementos cada uno*/

Ejemplo

0 1 2 3 4 5 6 7 8 9 10 ....................... 19

................

0 1 2 3 4 5 6 7 8 9 10 ....................... 19

................

0 1 2 3 4 5 6 7 8 9 10 ....................... 19

................

x

(x + 1)

(x + 9)

Primer arreglo unidimensional

Segundo arreglo unidimensional

Décimo arreglo unidimensional

Acceso a datos mediante apuntadores

• Si en el ejemplo anterior queremos tener acceso al elemento de la fila 2, columna 5, se puede especificar de la siguiente manera:

x[2][5];

O también:

*(*(x+2)+5);

Apuntadores a apuntadores

• Un apuntador a un apuntador es una forma de direccionamiento indirecto múltiple, o una cadena de apuntadores

• En un apuntador a apuntador el direccionamiento es la siguiente forma:– El primer apuntador contiene la dirección del

segundo apuntador– El segundo apuntador apunta a la variable

que contiene el valor deseado

Apuntadores a apuntadoresint main(){ char ch; /* Un caracter */ char *pch; /* Un apuntador a caracter */ char **ppch; /* Un apuntador a un apuntador a

caracter */

ch = 'A'; pch = &ch; ppch = &pch; printf("%c\n",**ppch); /* muestra el valor de ch

*/

return (0);}

Apuntadores a funciones

• Anteriormente se especificó que un arreglo es en realidad la dirección de memoria al primer elemento del arreglo

• De igual manera, una función es en realidad la dirección inicial en memoria del código que realiza la tarea de la función

• Un apuntador a una función contiene la dirección de la función en memoria

Apuntadores a funciones

• Un apuntador a una función puede ser pasado como argumento a otra función

• Esto permite que una función sea transferida a otra, como si la primera función sea variable

• Sintaxis:tipo-dato (*nombre-funcion) (tipo1 arg1, ...)

Ejemplo

int procesar(int (*pf) (int a, int b));int func1(int a, int b);int func2(int a, int b);

int main (){ int i,j; i = procesar (func1); j = procesar (func2); ...}

Ejemploint procesar(int (*pf) (int a, int b)){ int a,b,c; a = 4; b= 6; c = (*pf)(a,b); return (c);}int func1(int a, int b){ int c; c = a + b; return (c);}int func2(int x, int y){ int z; z = x * y; return (z);}

ESTRUCTURAS

Estructuras

• Las estructuras son estructuras de datos cuyos elementos individuales pueden ser de tipo distinto

• Una estructura puede contener elementos enteros, flotantes y caracteres

• También puede contener apuntadores, arreglos y otras estructuras

• A los elementos individuales de una estructura se les denomina miembros

Definición de una estructura• Una estructura debe ser definida en términos de sus

miembros individuales• Sintaxis: struct marca{ miembro 1; miembro 2; ... miembro m; }Donde: struct: Es una palabra reservada miembro1,2,...,n: son declaraciones de miembros individuales

struct cuenta{ int num_cuenta; char tipo_cuenta; char nombre[80]; float saldo;};

struct cuenta cliente1, cliente2;

Acceso a miembros de una estructura

• Se utilizan dos operadores para acceder a una estructura

• El operador miembro de la estructura (.)

• El operador apuntador de la estructura (->)

Estructuras como miembro de otra estructura

• Una variable de estructura puede ser definida como miembro de otra estructura

• En tales situaciones la declaración de la estructura interna debe aparecer antes que la declaración de la estructura externa

• Para acceder a un miembro de una estructura definida dentro de otra se sigue el siguiente formato

variable.miembro.submiembro

Ejemplostruct fecha{ int mes; int dia; int anio;};

struct cuenta{ int num_cuenta; char tipo_cuenta; char nombre[80]; float saldo; struct fecha ultimopago;};

struct cuenta cliente;//cliente.ultimopago.mes

Inicialización de estructuras

• A los miembros de una variable de estructura se les pueden asignar valores iniciales

• Los valores iniciales deben aparecer en el orden en que serán asignados a sus correspondientes miembros de a estructura, encerrados entre llaves y separados por comas

struct cuenta cliente = {123, ‘R’, “Pedro Perez”, 500.50, 3, 11, 2009};

Arreglos de estructuras

• Es posible definir arreglos de estructuras

• En este tipo de arreglos cada elemento es un estructura

• Ejemplo:

struct cuenta clientes[10];• Para tener acceso a un elemento de este

arreglo:

clientes[0].saldo = 130.5;

Operaciones sobre estructuras completas

• En algunas de las versiones más antiguas de C, las estructuras debían ser procesadas miembro por miembro

• Debido a esta restricción, la única operación permisible con la estructura completa es tomar su dirección

• La mayoría de las nuevas versiones (ANSI) permiten asignar una estructura completa a otra siempre que estas tengan la misma composicióncliente1 = cliente2;

Operaciones sobre estructuras completas

• Una estructura completa se puede pasar como parámetro a una función

• Las versiones antiguas de C solo permiten pasar estructuras como apuntadores

• El estándar ANSI pasar estructuras completas

Paso de estructuras a una función

• Se pueden transferir los miembros individuales o la estructura completa a una función

• Los miembros individuales de una estructura se pueden pasar a una función como argumento y ser devueltos mediante la instrucción return

Ejemplo

void asignafecha (int *m, int *d, int *a){ *m = 11; *d = 6; *a = 2009;}

asignafecha(&cliente1.ultimopago.mes, &cliente1.ultimopago.dia, &cliente1.ultimopago.anio);

Paso de estructuras a una función

• Se puede pasar una estructura completa como argumento a una función de dos maneras

• Mediante un apuntador a la estructura

• O enviando la variable de tipo estructura directamente

Apuntadores a estructuras

• Cuando se envía un apuntador a estructura esta se pasa por referencia

• Para acceder a un miembro de la variable estructura enviada como apuntador se debe utilizar el operador flecha (->)

• Un apuntador a una estructura puede ser devuelto desde una función a la parte del programa que hizo la llamada

Ejemplo

void fun(struct cuenta *pc){ pc->nombre = “teresa”; pc->num_cuenta = 123;}

void main(){ struct cuenta cliente1; fun(&cliente1);}

• La mayoría de las versiones nuevas de C (ANSI) permiten que una estructura completa sea transferida directamente a una función y devuelta con return

• Cuando se pasa una estructura directamente a una función, la transferencia es por valor y no por referencia