estructura de datos y algoritmos repaso tipos de datos

Estructura de Datos y Algoritmos

Repaso Tipos de Datos

¿Qué es un dato?

Información en bruto, sin ningún significado

Dado un enunciado, evento o acción, los datos Permiten representar sus actores o participantes

Analizándolos, se podrá obtener resultados deseados

Analicemos el siguiente hecho: El estudiante Juan Paz de edad 23 años, tiene promedio 8.3 en sus

calificaciones

Podemos tomar los siguientes datos Nombre: Juan Paz -> Conjunto de Caracteres

Edad: 23 -> entero

Promedio: 78,3 -> real

Como representar los datos

Los seres humanos: Usamos lenguaje natural o símbolos Ejemplo:

Para representar números, usamos el sistema decimal Para representar palabras, usamos el abecedario

La computadora: Usa conjuntos de 1s y 0s El dato mas pequeño en el computador es

Un 1 o un 0 -> bit

El conjunto de 8 bits -> 1 byte

Como representar los datos

Los datos se clasifican en TIPOS Son los diferentes dominios existentes.

Ejemplo: Edad, Año de Nacimiento, Numero de multas

Tienen dominio numérico

Nombre, Dirección, Num. Cedula, Caen en el dominio de la información tipo texto

Y las operaciones permitidas para dicho dominio

Tipos de Datos Básicos

NOMBRE CONJUNTO DE VALORES OPERACIONES

Enteros Negativos y positivos sin decimal Sumar, restar, dividir, multiplicar, residuo

Reales Negativos y positivos, con decimal

Sumar, restar, dividir, multiplicar

Lógicos Verdadero o Falso(1 o 0) And, Or, Not

Caracteres Letras, números, especiales, juntos forman una cadena

Sumar carácter + entero restar, multiplicar por entero

En la computadora1000

1001

1002

1003

Solo vienen integrados los tipos de datos básicos En la computadora

Cada byte es un casillero y tiene una dirección en memoria

Los datos (números y letras) se almacena en estos casilleros

¿Cuantas casilleros ocupa un dato? Depende de su tipo y del hardware de la computadora Un entero puede ocupar casillas de hasta 4 bytes Un doble siempre ocupara mas, por su mayor precisión

PERO, un carácter SIEMPRE ocupara casillas de 1 byte

Declaración de variables en C

Una declaración de variables en C incluye Tipo de dato y Nombre de variable(identificador) Ejemplo:

int a, b;float c;

¿Para que se declaran variables? Especifica cuanta memoria debe reservarse y Como se van a interpretar dichos datos

f = a + b Es una suma de enteros, que al final se convierte a real

int a;4 bytes,dir: 100

1 byte,dir: 104

100101102103104

char c;

Direcciones de Memoria

1000

1001

1002

1003

&a es 1000

Las variables Tienen direcciones de memoria

Si deseamos conocer dicha dirección En lenguaje C Se usa el operador & de dirección

Ejemplo:int a;a = 3;printf(“Valor:%d Dir: %d”, a, &a);

Un puntero Es una variable que puede almacenar dirección

de memoria


Repaso Estructuras de Datos

¿Qué es una Estructura de Datos?

Una estructura de datos es una forma de organizar un conjunto de datos elementales con el objetivo de facilitar su manipulación. Un dato elemental es la mínima información que se tiene en un programa.(ejemplos de datos elementales serían int, float, char,etc…)

Lo que se pretende con las estructuras de datos es facilitar un esquema lógico para manipular los datos en función del problema que haya que tratar y el algoritmo para resolverlo.

¿Qué es una Estructura de Datos?

En algunos casos la dificultad para resolver un problema radica en escoger la estructura de datos adecuada. Y, en general, la elección del algoritmo y de las estructuras de datos que manipulará estarán muy relacionadas.

Ejemplos de estructuras de datos

Vectores (matriz o array) Listas Enlazadas Pilas (stack) Colas (queue) Árboles

Árboles Binarios Árboles finitarios

Conjuntos (set) Grafos Tablas Hash


Tipos Inductivos

Tipos Inductivos ("Recursivos")

tienen en general cardinalidad infinita

contienen valores de "tamaño arbitrario"

Ejemplos: números naturales listas


Tomemos por ello un problema para representar estos tipos en computadoras Concretamente: ¿Cómo se implementan las variables de estos tipos ?

T x;//T es el tipo de la variable x un espacio fijo en memoria con una dirección

(secuencia de bits ubicada en cierta posición de la memoria)

El espacio debe ser suficiente para contener cualquier valor de tipo T


Si los valores de tipo T pueden ser de tamaño arbitrariamente grande, entonces no hay espacio finito suficiente para contener cualquier valor de tipo T.

Por ello: sólo un rango de los naturales es representable:

([MinNat, MaxNat])

El caso de las listas

¿Cómo tendría que ser una variable capaz de contener cualquier lista?

infinita de tamaño ajustable

(Cada lista es finita; pero la variable debería poder crecer y contraerse al agregar y quitar elementos de la lista)


Solución:

La lista se extiende "hacia afuera" a lo largo de la memoria ocupando un número de variables.


¿ Cómo ? Ejemplo: Consideramos [1, 2, 3] Cada elemento es representable en una variable

común (ej.: de tipo CARDINAL)


A esta información, hay que agregar otra, que representa la estructura (lineal) de la lista:

¿ Dónde está el primer elemento ? ¿ Dónde está el siguiente de cada elemento ?


Si llamamos a la lista en cuestión, podemos representarla con una variable que: indique dónde está el primer elemento, o sea que

apunte a la variable que contiene el primer elemento, que es lo mismo que

contenga como valor la dirección (un nombre, una referencia a) de la variable que contiene el primer elemento


¡¡¡Necesitamos un nuevo “tipo” de valores !!! Direcciones Referencias Nombres indicadores (indicaciones) punteros

Debe poderse representar la lista vacía, cuyo primer elemento no existe. Necesitamos un valor que “no apunte”.Este valor se conoce como NULL . Operación: es la variable a la que señala

(apunta) Notar que no está definida para l = NULL


Además necesitamos representar la estructura secuencial.

Para ello, hacemos que cada componente de la lista apunte al siguiente:


Tenemos NODOS formados por dos componentes (campos): El elemento propio de la lista (información) El puntero al siguiente nodo (posiblemente

no existente)

En C podemos representar los nodos como estructuras (struct)


Debe poderse crear y destruir variables en forma dinámica (mediante instrucciones de programa, durante la ejecución de los programas)

¿ Por qué ?


Debemos poder implementar asignaciones (abstractas) como:

S = x.S (operación que agrega un elemento a la lista)

(comparar con n = n + 1)

En tal caso, la lista contenida en la variable S se

agrandaría en un elemento


En la representación con nodos y punteros, corresponde a crear un nuevo nodo y agregarlo a la lista.

Por ejemplo, a la asignación abstracta l = 0.l (antes de la asignación l=[1,2,3]) corresponde:


El nuevo nodo: debe ser creado debe cargársele información l debe ser actualizada

Igualmente, deben poderse destruir nodos, correspondientemente con las operaciones que borran elementos de listas

Tenemos pues ESTRUCTURAS DINÁMICAS.Su tamaño es gobernado por instrucciones dePrograma. Esto no pasa con estructuras estáticas como

son los arreglos.

Listas Encadenadas


Repaso Punteros

Punteros en C

Para cada tipo T existe el tipo de los punteros a variables de tipo T:

POINTER TO T

(que en C se declararía: T *variable;)

Punteros en C

Notar que si p es una variable de tipo POINTER TO T, entonces los estados posibles de p son: Estar apuntando a una variable de tipo T Contener el valor NULL (tiene valor, pero no

apunta) No tener valor (no haber recibido todavía valor)

Punteros en C

El único literal (constante primitiva) de cada tipo de puntero es NULL

Las operaciones asociadas a cada tipo de puntero son: (puntero a variable) + - == (verificación de igualdad de dos punteros, y solo

de punteros) = (asignación)

Punteros en C

Un tipo de dato El puntero solo podrá almacenar direcciones de

memoria de variables del tipo especificado Se pueden definir punteros de cualquier tipo:

float *pf; char *pc;

Un identificador que siempre va antecedido del operador *

pt almacena la dirección de x, se

dice que pt apunta a x

x

pt

10001001

1003

10051000

int *pt, x;x = 3;pt = &x;

3

1000

Punteros en C

Un puntero apunta a una variable A través del puntero se puede llegar a conocer todo sobre la

variable Ejemplo:

c = ‘A’

printf(“%c”, *pc1);

*pc1 = ‘N’

printf(“%c”,c);

Es equivalente a :printf(“%c”, c);

Es equivalente a :c = ‘N’

Imprime ‘N’ pues c ya cambio

char c, *pc1, *pc2;pc1 = &c;

Si quiero conocer la dirección, uso el punteroprintf(“%d”, pc1); //Imprimo la dir. Almacenada por pc1pc2 = pc1; //pc2 almacena la misma dir. que pc1

Si quiero conocer el contenido al que apunta un puntero, uso el operador *, sobre dicho puntero

Punteros en C

A éstas operaciones deben agregarse las operaciones que permiten crear y destruir variables dinámicamente

En todo contexto en que sea válida la importación:

#include <stdio.h>

Punteros en C

Tomemos disponibles las siguientes funciones (C extendido), para cualquier tipo T: T *variable = new(T); delete(variable); delete [] variable (si variable es un

arreglo creado dinamicamente)

Punteros en C

El funcionamiento de estos procedimientos es como sigue:

p = new(T) Crea una variable de tipo T (siendo p una variable de

tipo POINTER TO T) deja p apuntando a esa nueva variable no importando cuál era el estado previo de p

delete(p) Tiene como precondición que p esté apuntando a

alguna variable La variable apuntada por p desaparece p queda "sin valor"

Punteros en C

1. Los tipos de punteros son atómicos. Pueden ser retornados como valores de funciones. Son usados para formar estructuras encadenadas.

2. Dada una variable T *p hay tres formas de asignarle valor

1. p = NULL;2. p = q;3. P = new(T);

Asignar un valor a un puntero

p = NULL, hace que p "no apunte"


p = q, donde q es otra variable del mismo tipo que p. Entonces q debe tener valor. Luego de esta asignación, o bien p y q son NULL (no apuntan) o bien apuntan a la misma variable.


p = new(T), es la manera de crear punteros efectivos a variables.

Luego, necesariamente, si un puntero apunta a una variable, ésta es una variable creada dinámicamente (usando new)

Punteros en C Observaciones Complementarias

3. Dada la siguiente situación:

Decimos que p, q (sus punteros) son alias de la misma variable.

Punteros en C

¿ Qué ocurre al ejecutarse delete(p)?

q queda apuntando a una variable inexistente (lo cual es diferente de contener el valor NULL, es decir: "NO APUNTAR")

De hecho, ocurre que los contenidos de ambas variables son inútiles. O sea, la situación es análoga al caso en que no tienen valor asignado.

Punteros en C

¿ Qué ocurre al ejecutarse DELETE(p)?

Ejecutar p o q en esta situación conduce a un error de ejecución (el mensaje suele ser “SEGMENTATION FAULT" o algo que sugiera "ausencia de variable alojada en la dirección en cuestión")

En presencia de alias, la ejecución de DELETE puede tener, como efecto lateral, que más de un puntero quede "apuntando a una variable inexistente“ OJO

Punteros en C

4. Sean p, q variables de tipo char*, tal que:

Punteros en C

¿Que pasa si hacemos …?

[1]p = q [2]*p = *q (esta es la notación en C para p y q

respectivamente)


Luego de ejecutar [1], tenemos:

(Notar también el desperdicio posible de memoria luego de ejecutar [1], ‘a’ queda inaccesible y “gastando memoria”)


Luego de ejecutar [2], tenemos:

Punteros en C

NEW y DELETE son traducidos en términos de los procedimientos (más primitivos) malloc y free.

Esto explica porqué importamos los últimos pero usamos los primeros.

Referencias

http://www.fing.edu.uy/inco/cursos/prog2

www.dspace.espol.edu.ec/bitstream/.../1.Tipos%20de%20Datos.ppt

Bibliografía

Wirth, N. Algoritmos y Estructuras de Datos. Prentice-Hall. 1987.

FIN

¿Preguntas?

estructura de datos y algoritmos repaso tipos de datos

Documents