Ayudantía 1 (Estructura de datos)

De Departamento de Informatica
(Redirigido desde Ayudantía 1)
Saltar a: navegación, buscar

Contenido

¡Otra vez no!: Lo básico de C

"The only way to learn a new programming language is by writing programs in it" - Kernighan, Brian and Rithchie, Dennis - The C programming language 2ed

En este capitulo se realizará un rápido recuento de todo lo básico visto en el ramo de programación. Esto servirá para aquellos que vengan de Pascal (u otro lenguaje) y aún no se familiarizan con C. Aquellos que se están iniciando en este lenguaje deberán ampliarlo por sí mismos, escribiendo y probando con programas cortos, muy similares a los que aquí se exponen. Para aquellos que manejan el lenguaje, deberán ser capaces de adaptar los puntos a tratar según sus propias necesidades.

Introducción

Un programa en C, cualquiera que sea su tamaño, consta de una o más "funciones" que especifican las operaciones de cálculo que han de realizarse. Normalmente, puedes dar a las funciones cualquier nombre que sea de tu agrado, pero el main es un nombre especial (el programa comienza a ejecutarse al principio del main). Esto quiere decir que todos los programas deben tener una función main en algún sitio. Esta casi siempre hará uso de otras funciones para efectuar su trabajo.

Uno de los objetivos de diseño del lenguaje C es que sólo sean necesarias unas pocas instrucciones en lenguaje máquina para traducir cada elemento del lenguaje, sin que haga falta un soporte intenso en tiempo de ejecución. Es muy posible escribir C a bajo nivel de abstracción; de hecho, C se usó como intermediario entre diferentes lenguajes.

Dentro de las ventajas del lenguaje C, podemos listar algunas como:

  • Un núcleo de lenguaje simple, con funcionalidades añadidas importantes, como funciones matemáticas y de manejo de archivos, proporcionado por bibliotecas.
  • Es un lenguaje flexible que permite programar con múltiples estilos. Uno de los más empleados es el estructurado "no llevado al extremo" (permitiendo ciertas licencias de rupturas).
  • Un sistema de tipos que impide operaciones sin sentido.
  • Acceso a memoria de bajo nivel mediante el uso de punteros.
  • Interrupciones al procesador a través de uniones.
  • Un conjunto reducido de palabras claves.
  • Por defecto el paso de parámetros a una función, se realiza por valor. El paso por referencia se consigue pasando explícitamente a las funciones las direcciones de memoria de dichos parámetros.

entre muchas otras ventajas, que no viene al caso (dado a que escapan del foco del curso) mencionar.

Pero también es importante reconocer las desventajas que posee este lenguaje de programación, entre las cuales podemos listar las siguientes:

  • Falta de soporte para programación orientada a objetos, aunque la implementación original de C++ fue un preprocesador que traducía código fuente de C++ a C.
  • Encapsulación.
  • Polimorfismo en tiempo de código en forma de sobrecarga, sobrecarga de operadores y sólo dispone de un soporte rudimentario para programación genérica (Programación más centrada en los algoritmos que en los datos, esto se consigue parametrizando lo máximo posible el desarrollo del programa y expresados o devueltos de la forma más simple posible - fuente: [[1]])
  • Soporte nativo para programación multihilos y redes de computadores.

Sin embargo la lista de características útiles de las que carece C es larga, este factor ha sido importante para su aceptación, dado a que mantiene lo que realmente hace el programa bajo el control directo del programador, lo que se traduce en que C sea más eficiente que otros lenguajes de programación.

En algunos casos, una característica inexistente puede aproximarse. Por ejemplo, la implementación original del C++ consistía en un preprocesador que traducía código fuente a C. La mayoría de las funciones orientadas a objetos incluyen un puntero especial, que normalmente recibe el nombre de this, que se refiere al objeto al que pertenece la función. Mediante el paso de este puntero como argumento de función, esta funcionalidad puede desempeñarse en C, así por ejemplo en C++ se puede escribir:

stack.push(val);

Mientras que en C, se podría escribir como:

push(stack,val);

Los tipos de Datos

Una vez teniendo claro lo anterior es posible comenzar con lo básico de C. Dentro de los tipos de datos soportados de C, reconoceremos dos clasificaciones importantes, los tipos de datos básicos y los calificadores de tipos.

Tipos Básicos

Como ya se sabe desde IWI-131, los tipos de datos básicos soportados por C son:

  • int: Estos corresponden a los números enteros, normalmente del tamaño natural de los enteros en la maquina en la que se ejecuta (del orden de 16 bits)
  • float: Corresponde a los números punto flotante con precisión normal, el tamaño de estos es del orden de 32 bits
  • double: Corresponde a los números punto flotante con doble precisión, el tamaño de este tipo de datos es del orden de 64 bits
  • char: Corresponde a los caracteres o a un conjunto de estos, el tamaño de este tipo de datos es de 1 Byte por cada carácter que contenga.(Más adelante será más

claro al observar los arreglos)

Como se podrá inferir desde aquí, el estándar ANSI, los tipos de datos deben cumplir con lo siguiente: char < int < float \leq double

Los tamaños de float y double dependerán en gran medida de la máquina en la cual se compile, puede que en algunas máquinas un tipo de dato float ocupe menos bits que un double o puede darse el caso que ocupe el mismo número, para fines prácticos consideraremos esta noción del tamaño de los datos.

C, a diferencia de Pascal u otros lenguajes de programación, no posee un tipo predefinido para los valores lógicos (generalmente identificados como bool o boolean y cuyos valores pueden ser true o false). Aquí se interpreta los 0 como false y cualquier valor distinto de 0 como true.

Así un ejemplo para clarificar la diferencia sería el siguiente:

Pascal

var:
    x: boolean;
begin:
    readln(x);
    if x then
        writeln('X es verdad')
    else
        writeln('X es falsa');
end.

C

int main()
{
    int x;
    scanf("%d", &x);
    if (x)
        printf("X es verdad");
    else
        printf("X es falso");
    return 0;
}

En ambos casos, podemos modificar el valor de \textbf{x} para obtener resultados distintos. Para el caso de Pascal, solo bastará cambiar el valor por \textbf{false} para que se ejecute la segunda acción, en cambio en el caso de C, basta con colocar cualquier valor distinto de 0 para que se ejecute la segunda instrucción.

Calificadores de tipo

Una vez que logramos entender los tipos de datos básicos, es hora de ocupar algunas características avanzadas de C que nos permiten modificar la cantidad de bits que utilizan los tipos de datos para el almacenamiento de las variables (Para aquellos interesados en saber como funciona, se recomienda la sección extra representación de la información).

Los calificadores de tipo alteran la cantidad de bits utilizados en la representación de un tipo de dato y por lo tanto permite utilizar alguno de los bits extras utilizados muchas veces en los signos de los datos. Esto nos otorga un espectro mayor de valores posibles de nuestras variables a declarar.

Dentro de los calificadores de tipo, encontraremos los siguientes:

  • Short: La intención de este calificador es acortar la longitud de enteros donde sea práctico. A menudo short es de 16 bits.
  • Long: Al igual que short, este calificador permite modificar la longitud de los enteros, con la diferencia que este extiende el largo del número a representar, así un tipo de dato con calificador long posee cerca de 32 bits.
  • Unsigned: Los números o tipos de datos \textit{unsigned} son siempre positivos o cero, y obedecen las leyes de la aritmética módulo 2n, donde n es el número de bits en el tipo.
  • Signed: Los números o tipos de datos signed, corresponden a los números enteros con signo.

A menudo para los calificadores de tipo no se poseen claras garantías que realizan las modificaciones deseadas, dado a que cada compilador (o sistema operativo) puede seleccionar libremente los tamaños apropiados para su propio hardware, sujeto a la restricción de que los short e int son de por lo menos de 16 bits, los long de 32 bits y el short no es mayor que el int, el cual a su vez no deberá ser mayor que el long, en otras palabras, se deberá respetar la siguiente regla de orden:

short \leq int < long

El calificador signed o unsigned puede aplicarse a un char o un entero. Así por ejemplo, si aplicamos el calificador unsigned a los 8 bits de un char, los valores que podrá tomar estarán entre el 0 y 255, en tanto que las variables signed char tienen valores entre -128 y 128 (representación en una máquina complemento dos)(véase sección Representación de la información). Claramente el hecho que los char ordinarios sean con signo o sin él depende de la máquina, pero los caracteres que se pueden imprimir son siempre positivos.

El tipo long double especifican puntos flotantes de precisión extendida. Igual que con los enteros, los tamaños de los punto flotante se definen en la implantación, así float, double y long double pueden representar uno, dos o tres tamaños distintos.

Entonces, entendiendo lo anterior y considerando que posiblemente el calificador no haga la pega correctamente, se tiene una implementación típica como:

  • Short int: 16 bits.
  • int: 16 bits.
  • long int: 32 bits.
  • float: 32 bits.
  • double: 64 bits.
  • long double: 64 bits.

El lenguaje C, nos proporciona además las herramientas para conocer el tamaño de Bytes (Recuerde que: 1 Byte = 1B = 8 bits) de un determinado tipo de dato o variable. Esto es posible con el operador sizeof, el cual retorna el número de Bytes que posee una variable (o tipo de dato) especifico.

Representación de la Información

En informática, la unidad básica para representar información es el bit. Utilizamos el sistema binario (en base 2) para representar combinaciones de estados de estos bits, de manera que dicha combinación represente la información deseada, como un código fuente de un programa, una gran base de datos o un documento como este.

Sistema numérico posicional

Es un sistema donde el valor de un dígito depende de la posición en la cual se encuentra, en general es posible representarlo mediante la siguiente ecuación:

d_{m-1}d_{m_2}\dots d_1d_0 = \sum_{i=0}^{m-1}d_i\cdot b^i

Donde d_0,d_1\dots d_m son los dígitos. Si la base es b, existen b dígitos representables.

El sistema numérico comúnmente utilizado es el sistema decimal, el cual corresponde a un polinomio en base 10, esta base posee 10 dígitos (0,1,2\dots,9), así por ejemplo, es posible representar el número 1234 como:

 1234 = 1\cdot 10^3 + 2\cdot 10^2 + 3 \cdot 10^1 + 4\cdot 10^0

Tal como se inferirá, en este sistema la notación decimal es fácilmente representable como:

 d_0\cdot b^0 + d_1\cdot b^1 + \dots + d_{m-2}\cdot b^{m-2} + d_{m-1}\cdot b^{m-1} + d_{-1}\cdot b^{-1}+ d_{-2}\cdot b^{-2}+\dots+d_{-k}\cdot b^{-k}

Si la base es 2, el sistema numérico se denomina binario. El conjunto de dígitos representables en este sistema es {0,1}. Este conjunto se denomina bits.

Existen otras bases numéricas interesantes en informática (no las trataremos en profundidad puesto a que serán examinadas posteriormente en ramos como Arquitectura de Computadoras con más detalle) como la hexadecimal (base 16) o la octal (base 8), cada una de ellas de gran importancia a la hora de hablar de la arquitectura de computadores, dado a que permiten expresar la información binaria en forma más compacta.

Como dato rosa, en C es posible representar dichas bases (octales y hexadecimales) anteponiendo un prefijo en el valor para indicar la base en la que se encuentren:

const int i = 056; //prefijo 0 indica que es valor octal
const int i = 0xA9;  //prefijo 0x indica que es valor hexadecimal

Nos enfocaremos ahora en la forma de que representemos datos decimales en datos binarios con el siguiente procedimiento:

  1. Se divide el número en base decimal por 2 y se registra el resto de la división.
  2. Se considera como nuevo número el cociente entre el número y 2.
  3. Repetir paso 1 y 2 hasta que el número sea 0.
  4. El número final en binario será el registro de los restos.

Veámoslo en código, este procedimiento quedaría como:

C

int numero,i=0,base=2;
int resto[5];  
scanf("%d", &numero);
do
{
    resto[i] = numero % base;
    numero /= base;
    i++;
}
while(numero != 0);
for(i=4;i>=0;i--)
    printf("% d",resto[i]);

Pascal

var
    numero, i, base: integer;
    resto: array [1..5] of integer;
begin
    i:=1;
    base:=2;
    readln(numero);
    repeat
        resto[i] := numero mod base;
        numero := numero div base;
        i:= i + 1;
    until numero = 0;
    for i:=5 downto 1 do
        write(resto[i]);

Este es un ejemplo generalizado para la conversión desde base decimal a una base cualquiera. Para el caso particular de decimal a binario, el valor de base es de 2.

Extra: Introducción a la aritmética computacional

Los computadores actuales son binarios, la información que maneja el computador es almacenada en dispositivos de hardware llamados Registros, se denomina ancho del registro al número de bits que pueden almacenar. Actualmente los procesadores poseen un ancho de registro de 32, 64 o 128 bits, y este número es variable de un procesador a otro.

Un registro de 16 bits, quiere decir que consiste en un conjunto de 16 dígitos en base 2, cuyas combinaciones de 0 o 1 permiten almacenar información.

1  0  0  1  1  1  0  1  0  1  1  1  0  0  0  1

Se denomina Byte al conjunto formado por 8 bits, así usaremos como notación b para bits y B para Bytes. Así el registro anterior posee 16b o 2B.

La información máxima que puede manejar un procesador esta limitada por el tamaño de los registros o de un conjunto de registros. Con el registro anterior de 16b, el mayor entero representable es:

1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1

Actualmente la mayoría de los procesadores son de 32b o de 64b, esto quiere decir que el entero más grande que pueden representar es 232 ó 264, respectivamente.

Números negativos en binario

Dado lo anterior, es fácil determinar que la aritmética de los computadores es finita, debido a que se encuentra limitada por el tamaño de los registros. Es ahora entonces cuando surge el primer problema.

De nuestra formación matemática primigenia, sabemos que la resta de números no es más que una suma de enteros, por lo tanto nuestro interés se centra en como representar los números negativos utilizando el sistema binario.

Por convención se utiliza el bit más significativo (el bit de potencia más alta) para representar el signo. Así los números positivos poseen el bit más significativo en 0 y los números negativos en 1.

Existen tres formas para representar números negativos: Signo Magnitud (S-M), Complemento Uno (C-1), Complemento Dos (C-2); los números positivos se representan de la misma manera en las 3 formas. Todos los computadores modernos utilizan la forma Complemento Dos para la representación numérica.

Números Negativos: Representación Signo Magnitud

Se considera la magnitud del número (el cual corresponde al valor absoluto de este) y luego observamos el signo (o bit más significativo) para determinar si el número es o no negativo.

Así por ejemplo, consideremos un registro de 5b.

1  0  0  1  1 

Si observamos el ejemplo, el bits más significativo corresponde a un 1 el cual indica que el número es negativo, a continuación observamos la magnitud de los 4 dígitos restantes, con lo cual sabemos que corresponde al número 3. Por lo tanto esa sería la representación del número -3 en binario utilizando signo-magnitud.

Desde aquí se puede observar el principal problema de esta representación. En este tipo de representación existen dos 0, +0 y -0. Esto puede traer serias complicaciones al realizar cálculos aritméticos.

En general si el ancho de los registros es de n, el rango representable esta dado por:

-(2^{n-1}-1) \leq N \leq (2^{n-1}-1)

Números Negativos: Representación Complemento Uno

En la representación \textit{complemento uno} de un número se obtiene complementado cada bit en NOT. Por ejemplo para representar el registro del ejemplo anterior en complemento uno se debe seguir el siguiente procedimiento:

  1. Consideramos el número positivo (en este caso la representación binaria de 3).
  2. Luego complementamos cada bit, con lo que se obtiene la representación en C-1.
1  1  1  0  0 

Al igual que en Signo-Magnitud, esta representación presenta dos tipos de 0, +0 y -0. En general si el ancho de un registro es de n, el rango representable esta dado por:

-(2^{n-1}-1)\leq N \leq (2^{n-1}-1)

Números Negativos: Representación Complemento Dos

Existen dos formas para encontrar el Complemento Dos de un número N en un registro de ancho n.

  1. Calculando \(2^n-N\).
  2. Calcular el C-1 del número y luego sumar 1.
1  1  1  0  1

Se puede observar desde aquí, que existe sólo una representación del número 0, además existe una asimetría ya que el valor absoluto de máximo número negativo es mayor que el máximo positivo, así en la tabla siguiente se puede observar un ejemplo en un registro de 5 bits

1  0  0  0  0 

0  1  1  1  1 

En general, si el ancho de los registros es n, el rango representable está dado por:

-2^{n-1} \leq N \leq (2^{n-1} - 1)

Está es la notación que los computadores actuales utilizan para representar los números enteros, así la suma en complemento dos es el caso más frecuente en los procesadores actuales, de modo que para sumar dos números en C-2, se suman los números en forma binaria. El problema sucede con los números del mismo signo, donde pudiese suceder rebalse (overflow), pero para detectarlo se utiliza un bit especial llamado Carry (Para aquellos que deseen interiorizar más, recomiendo ver las diapositivas de Arquitectura de Computadores del profesor Xavier Bonnaires).

Herramientas personales
Espacios de nombres
Variantes
Acciones
Navegación
Herramientas