Estructura de datos
-
Upload
jonatan-sanchez -
Category
Documents
-
view
520 -
download
2
Transcript of Estructura de datos
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