UNIDAD 1: ESTRUCTURA DE DATOS Un curso de ciencias de la computación incluye el estudio de cómo se organiza la información en una computadora, como se manipula y como se emplea. Si las ciencias de la computación son fundamentales para el estudio de la información, entonces ¿Qué es la información? Esta pregunta no puede contestarse con precisión ya que es un termino indefinido acerca de los cuales puede establecerse enunciados pero no se pueden explicar en términos más elementales. En computación es posible medir las cantidades de la información. La unidad básica de información es el bit, cuyos valores establecen uno de dos posibilidades mutuamente excluyentes. Los dígitos binarios 0 y 1 se usan para representar los dos estados posibles de un bit particular. Dados n bits, se usa una cadena de unos y ceros para representar sus especificaciones. El método mas difundido para interpretar especificaciones de bits como enteros no negativos es el sistema numérico binario. En este sistema la posición del bit en el extremo derecho representa 20, lo cual es 1, la siguiente 21, lo cual es 2 y así sucesivamente. Si aparece un 1 en esa posición de bit particular, se incluye en la suma de potencia de 2 representada por la posición de tal posición de bit. Pero si aparece un 0 no se incluye en la suma. Hay dos métodos que se usan con frecuencia para representar números binarios negativos. En el primero denominado notación de complemento a uno, se representa un numero negativo cambiando cada bit en su valor absoluto a las especificaciones de bit opuesta. Ejemplo: 00100110 representa 38 11011001 representa −38 Una cadena de bits que empieza con un 0 representa un numero positivo, en tanto una cadena de bits que inicia con 1 representa un numero negativo. El segundo método se denomina notación de complemento a dos. Aquí se agrega un 1 a la representación del complemento a uno de un numero negativo. Ejemplo: Considere el 0 utilizando 8 bits: 00000000. En complemento a uno es: 11111111, lo cual es un 0 negativo en tal notación. Agregamos un 1 para realizar el complemento a dos 100000000, lo cual tiene 9 bits de longitud. Como solo se permitan 8 bits, se descarta el bit de la extrema izquierda, dejando 00000000 como menos 0. CADENAS DE CARACTERES La información no siempre se interpreta en forma numérica. Elementos tales como nombres, títulos de trabajos y direcciones también deben representarse en alguna forma dentro de una computadora. Para permitir la representación de tales objetos no numéricos, es necesario un método adicional para interpretar cadenas de caracteres.

1

Si se usan 8 bits para representar un carácter, es posible simbolizar hasta 256 caracteres diferentes. Algunas computadoras usan 8 bits y otras hasta 10( o sea hasta 1024 caracteres). La cantidad de bits necesaria para representar un carácter en una computadora particular se denomina el tamaño de byte y un grupo de bits de dicho numero se llama un byte. HARDWARE Y SOFTWARE La memoria de una computadora es sencillamente un grupo de bits. En cualquier momento de la operación de la computadora, un bit particular de la memoria esta en la posición 0 o 1. La especificación de un bit se denomina su valor o contenido. Los bits en una memoria de una computadora se agrupan en unidades más grandes denominadas bytes. En algunas computadoras se integran los bytes en unidades llamadas palabras. A cada una de estas unidades, se le asignan una dirección, que es un nombre que identifica una unidad particular de entre todas las unidades de memoria. Por lo general esta dirección es numérica. Una dirección se denomina localidad y el contenido de una localidad son los valores de los bits que forman la unidad que esta en la localidad. La computadora sabe interpretar los patrones de bits en ciertas configuraciones como enteros binarios porque el hardware que ejecuta tal instrucción particular esta diseñado para hacerlo ¿QUÉ ES UNA ESTRUCTURA DE DATOS? Cuando hablamos de tipos de datos básicos nos referimos a un conjunto de valores más sus operaciones asociadas, por ejemplo, dentro del computador un número entero se representa con un par de bytes (16 bits), con ello, sólo puede almacenar valores en un rango de [−2 16/2, +216/2] y disponer de los operadores aritméticos: +, −, *, / y mod. Extendiendo el concepto, si agrupamos un conjunto de valores de igual o distinto tipo de dato básico y enseguida definimos la manera de cómo operar sobre ellos, es decir, sus métodos de acceso, estaríamos en presencia de una ESTRUCTURA DE DATOS. La definición de una Estructura de Datos posee un primer nivel de abstracción en donde simplemente se identifica la colección de elementos a agrupar y sus operaciones de acceso. En un segundo nivel, el de implementación, ya pensamos en un lenguaje de programación específico y es ahí donde surgen preguntas como ¿cuál es la estructura óptima? o ¿qué funciones y/o procedimientos definir? Ejemplo: Suponga que se necesita implementar un juego entretenido para 2 jugadores.

Nivel #1: Lógico o de abstracción. Si sugerimos el famoso juego del "El Gato" pensemos en un nivel abstracto que se trata de una colección de casilleros en donde se deberá marcar X ó O a medida que el jugador le toque su turno. Ya tenemos la colección de elementos X ó O y la operación marcar (X ó O según sea el caso).

Nivel #2 De Implementación A nivel de implementación ¿qué estructura sería factible en este caso?. Por las características del juego, (después de analizar ventajas y desventajas) concluimos que una arreglo bidimensional de 3 x 3 de tipo carácter sería una solución más factible.Netcyrus Type TableroGato = Array [1..3, 1..3] of char; 2

Var TableroJuegoEntretenido:TableroGato;

A este arreglo se le podría asociar el procedimiento MarcaJugador(turno: integer) Define otros para poder jugar más tarde! ¿QUÉ SON LOS ARREGLOS? Son una agrupación de datos homogéneos, es decir, con un mismo tipo de dato básico asociado. Se almacenan en forma contigua en la memoria y son referenciados con un nombre común y una posición relativa. Ejemplos: Arreglo Lineal (1 dimensión ó vector) Vista gráfica [1]

[2]

[3]

[4]

[5]

Definición de tipo

Type Linea:Array [1..5] of TipoBasico; Var MiArreglo:Linea; Arreglo Bidimensional (matriz) Vista gráfica [1,1] [1,2] [1,3] [1,4]

Definición de tipo

[2,1]

Type TipoTabla:Array[1..3,1..4] of TipoBasico; Var MiTabla: TipoTabla;

[2,2] [2,3] [2,4] [3,1] [3,2] [3,3] [3,4]

3

¿QUÉ SON LOS REGISTROS?

Son un tipo de datos formado por una colección finita de elementos no necesariamente homogéneos. El acceso se realiza a través del nombre del registro seguido del campo específico al que se desea acceder. Supongamos la siguiente. vista gráfica de un registro cualquiera:

Año 1997

Marca Precio OPEL CORSA SWING 1.4 4.150.000

Definición de tipo asociada:

TYPE TipoAuto = RECORD año: integer; marca: string[35]; precio: longint; (*Para que soporte valores > MAXINT*) END; Var AUTOMOVILES: TipoAuto;

¿Cómo acceder a los campos individuales de un registro?

Para acceder a cada uno de los campos se utiliza la siguiente función de acceso:

NombreRegistro.nombre del campo Para el registro AUTOMOVILES revisado anteriormente se tiene que el acceso a cada uno de sus campos se realiza como sigue: AUTOMOVILES.año AUTOMOVILES.marca AUTOMOVILES.precio

4

La principal ventaja del uso de registros es que posibilitan modelar objetos que contienen varias características y acceder a ellas mediante un nombre único. ASIGNACIÓN DE MEMORIA DINÁMICA MÉTODOS DE ASIGNACIÓN DE MEMORIA ¿Cuáles son los métodos de asignación de memoria utilizados por el S.O.? Cabe destacar que el almacenamiento y procesamiento de todos los datos es realizado en memoria RAM, en un segmento destinado a ello (DS), por ello, es importante conocer los métodos de asignación de memoria utilizados para su almacenamiento. Por un lado, se tiene la asignación estática de memoria en donde se reserva la cantidad necesaria para almacenar los datos de cada estructura en tiempo de compilación. Esto ocurre cuando el compilador convierte el código fuente (escrito en algún lenguaje de alto nivel) a código objeto y solicita al S.O. la cantidad de memoria necesaria para manejar las estructuras que el programador utilizó, quien según ciertos algoritmos de asignación de memoria, busca un bloque que satisfaga los requerimientos de su cliente. Por otro lado se tiene la asignación dinámica en donde la reserva de memoria se produce durante la ejecución del programa (tiempo de ejecución). Para ello, el lenguaje Pascal cuenta con dos procedimientos: NEW() y DISPOSE() quienes realizan llamadas al S.O. solicitándole un servicio en tiempos de ejecución. El procedimiento NEW ,por su parte, solicita reserva de un espacio de memoria y DISPOSE la liberación de la memoria reservada a través de una variable especial que direccionará el bloque asignado o liberado según sea el caso. ESTRUCTURAS EN C Una estructura es un grupo de componentes en el cual cada componente tiene su propio identificador, cada uno de los cuales se conoce como un elemento de la estructura(En muchos otros lenguajes e programación, una estructura se denomina registro y un elemento se denomina campo). EJEMPLO: Struct{ Char first[10], Char midinit; Char last[20]; } sname, ename; Esta crea 2 variables de estructura: sname y ename cada una con 3 elementos. IMPLEMENTACION DE ESTRUCTURAS Cualquier tipo en C puede considerarse un patrón o una plantilla. Esto quiere decir que un tipo es método para interpretar una parte de la memoria. Cuando se declara una variable como de cierto tipo, estamos diciendo que el identificador hace referencia a cierta parte de la memoria y que el contenido de tal memoria se va a interpretar de acuerdo con el patrón definido mediante el tipo. El tipo especifica la cantidad de memoria que se reserva para la variable y el método mediante el cual interpreta la memoria. EJEMPLO 5

Suponga que en cierta estructura se representa un entero mediante 4 bytes, un flotante mediante 8 y una arreglo de 10 mediante 10 bytes. Entonces: int x; floaty; charz; Una vez reservados los bytes para las variables, los nombres x, y, z siempre harán referencia a estas localidades. La cantidad de almacenamiento que se reserva para cada tipo y el método mediante el cual se interpreta el contenido de la memoria como de tipo específicos, varían de una maquina a otra y de una implementación de C a otra. UNIONES C también permite otro tipo de estructuras, la unión, la cual permite que una variable se interprete de varias formas distintas. EJEMPLO: Considere Una compañía de seguros que ofrece tres tipos de pólizas de vida, de automóvil y de casa. Un numero identifica cada póliza de seguros de cualquier tipo. Para los tres tipos de seguro es necesario tener: nombre del asegurado, dirección, monto del seguro y el pago de la prima mensual. Además se necesitan: Para las pólizas de automóviles: Cantidad deducible, numero de licencia, estado y el modelo y el año del automóvil. Para la póliza de casas: Cantidad deducible, referencias acerca de la antigüedad de la casa y la presencia de dispositivos de seguridad. Para la póliza de seguro de vida: fecha de nacimiento y los beneficiarios del asegurado. La definición consta de dos partes: Una fija: Los datos que tienen en común todas las pólizas Una variable: Los datos independientes de cada tipo de póliza. IMPLEMENTACION DE UNIONES Una estructura puede considerarse como un mapa de carreteras para una área de la memoria. Define como se va a interpretar la memoria. Una unión proporciona varios mapas de carreteras distintos para la misma área de memoria y es responsabilidad del programador determinar cual mapa se usa actualmente. En la practica, el compilador asigna suficiente almacenamiento para conservar el elemento más grande de la unión. Sin embargo, es el mapa de carreteras el que determina como interpretar tal almacenamiento. ESTRUCTURAS CON PARAMETROS En el C tradicional no puede pasarse una estructura a una función por medio de una función mediante valor. 6

Para pasar una estructura a una función, debemos pasar su dirección a la función y referirse a la estructura mediante un apuntador(llamada mediante referencia) REPRESENTACIÓN DE OTRAS ESTRUCTURAS DE DATOS Agregar datos a una estructura es útil porque permite agrupar objetos dentro de una sola entidad y nombrar cada uno de estos objetos en forma conveniente, de acuerdo con su función. Para ejemplificar como se usan las estructuras en esta forma, consideremos el problema de representar números racionales. ¿Cómo podemos representar un numero racional con exactitud? Dado que un numero racional consta de un numerador y un denominador, se puede representar un numero racional rational usando estructuras como la siguiente: struct rational{ int numerador; int denominador; };

7