Estructuras básicas de datos

De Wiki Alfonso Morcuende

Contenido

Sistemas y códigos de numeración

El ordenador se expresa con el sistema binario (0 y 1). Por lo que hay que traducir toda la información que se desea procesar a 0 y 1, para que esta sea entendida por el ordenador.

En los circuitos de origen electrónico viaja corriente eléctrica, por ello la ausencia o presencia de tensión se representa desde el punto de vista lógico:

  1. Mediante una lógica positiva.
    • La presencia de tensión se prepresenta por medio de un 1
    • La ausencia de tensión se prepresenta por medio de un 0
  2. Mediante una lógica negativa.
    • La presencia de tensión se prepresenta por medio de un 0
    • La ausencia de tensión se prepresenta por medio de un 1

Sistemas de numeración

Es un conjunto de símbolos y reglas que se utilizan para la representación de datos numéricos.

Todo sistema de numeración se caracteriza por su base. La base determina el número de símbolos que se utiliza para la representación de cantidades.

El coeficiente determina el valor de cada símbolo dependiendo de la posición que ocupe con respecto al punto decimal. Este tipo de sistemas de numeración reciben el nombre de sistemas posicionales o sistemas ponderados.

Sistema decimal

Es un sistema posicional o ponderado que consta de 10 símbolos, llamados dígitos, para la representación de cantidades.

0,1,2,3,4,5,6,7,8,9

Según el Teorema fundamental de la Numeración en un sistema posicional cualquiera, cualquier número puede expresarse mediante su polinomio equivalente. 

Numero(B = Xi(base i)*Bi(elevado a i) + Xi-1 * Bi-1 + ...... X2 * B2 + X1 * B1 + X0 * B0

B es la base

Xi son los coeficientes

i es el índice (posición relativa con respecto al punto decimal)

Ejemplo:

Representación de 1997 mediante su polinomio equivalente 

1997(10 = 1*10(3 + 9*10(2 + 9*10(1 + 7*10(0
1997(10 = 100 + 900 + 90 + 7
1997(10 = 1997


El número de símbolos que tiene un determinado sistema de numeración viene dado por la siguiente desigualdad: 

0 <= Xi < B

Ejemplo:

El sistema decimal cumple la desigualdad anterior. Y por lo tanto estos símbolos son los que constituyeb el sistema de numeración en el sistema decimal. 

0 <= 0 < 10
0 <= 1 < 10
0 <= 2 < 10
0 <= 3 < 10
0 <= 4 < 10
0 <= 5 < 10
0 <= 6 < 10
0 <= 7 < 10
0 <= 8 < 10
0 <= 9 < 10

Sistema bianrio

Es un sistema posicional o ponderado que consta de dos únicos símbolos, llamados dígitos, para la representación de cantidades

0,1

El número de combinaciones que podemos realizar en el sistema de numeración binario es 2n, siendo n el núero de dígitos binarios utilizados en cada combinación.

Ejemplo: 

2(3 = 8 combinaciones
Cantidad representada en binario Valor equivalente en decimal
000 0
001 1
010 2
011 3
100 4
101 5
110 6
111 7

Para la medida de cantidades de información representada en binario, se utilizan una serie de unidades multiplos del bit que reciben nombre propio.

  1. Nibble o cuarteto: conjunto de 4 bits
  2. Byte u octeto: conjunto de 8 dígitos binarios
  3. Kilobyte: conjunto de 1024 bytes
  4. Megabyte: conjunto de 1024 Kilobytes
  5. Gigabyte: conjunto de 1024 Megabytes
  6. Terabyte: conjunto de 1024 Gigabytes

Ejemplo:

¿Que número decimar representa la cantidad 1011.1? 

1011.1 = 1*2(3 + 0*2(2 + 1*2(1 + 1*2(0 + 1*2(-1
1011.1 = 8 + 0 + 2 + 1 + 0.5
1011.1 = 11.5

Suma binaria

La suma binaria se realiza de forma similr a la suma decimal a excepción de que solo se utilizan dos dígitos 0 y 1.

Cuando el resultado excede de los símbolos utilizados, se agrega el exceso a la izquierda. Para sumar en binario debemos tener en cuenta la siguiente tabla:

  • Tabla del O
    • 0 + 0 = 0
    • 0 + 1 = 1
  • Tabla del 1
    • 1 + 0 = 1
    • 1 + 1 = 10

Sistema octal

Es un sistema posicional o ponderado que consta de ocho símbolos, para la representación de cantidades.

0,1,2,3,4,5,6,7

Sistema hexadecimal

Es un sistema posicional o ponderado que consta de 16 símbolos, para la representación de cantidades, 0 - 9 y a - f.

0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f

Conversión entre bases

Para realizar la conversión de una base a otra debemos utilizar como intermediario la base 10, realizando los siguientes pasos:

  1. Pasar Número(B a Número(10
    • Mediante el desarrollo del polinomio equivalente.
    • Operando en decimal
  2. Pasar Número(10 a Número(C
    • Tomamos la parte entera del número en base 10 y lo pasamos a su equivalente en la base C mediante divisiones sucesibas.
    • Tomamos la parte decimal del número en base 10 y lo pasamos a su equivalente en la base C mediante multipliaciones sucesibas.

Ejemplo:

Pasar el número 78.3 de base 9 a base 2

  1. En primer lugar pasamos el número a su equivalente en B10 
    78.3(9 = 7*9[1 + 8*9[0 + 3*9[-1
78.3(9 = 63+8+0.333
78.3(9 = 71.333 (10
  2. En segundo lugar pasamos el resultado obtenido en B10 a su equivalente en B2
    • Divisiones sucesivas de la parte entera 
      71/2 %=1 res=35
35/2 %=1 res=17
17/2 %=1 res=8
8/2 %=0 res=4
4/2 %=0 res=2
2/2 %=0 res=1

71(10 = 1000111(2
    • Multiplicaciones sucesivas de la parte decimal 
      0.333 * 2 = 0.666 (0)
0.666 * 2 = 1.332 (0)
0.332 * 2 = 0.664 (0)

0.333(10 = 0.010(2
  3. El resultado final de la operación es 
    78.3(9 = 1000111.010(2

Clasificación de datos

Para el diseño de un programa es importante estableces cuáles son las estructuras de los datos que se van a utilizar, con el objeto de establecer las operaciones que sobre dichos datos se pueden realizar.

Los datos manejados en un programa deben llevar asociados un identificador, un tipo y un valor.

Identificador

Es el nombre utilizado en un programa para referenciar un dato. Existen ciertas normas:

  • Pueden estar constituidos por letras y dígitos y en algunos casos por el carácter subrayado (_).
  • Deben comenzar por una letra
  • No deben contener espacios

Tipo

Establece el rango o intervalo de valores que pueden tomar el dato. El tipo determina el espacio de memoria que se reserva para el dato.

Valor

Este elemento tiene que pertenecer al intervalo según el tipo definido

Datos básicos

Numéricos

Se utilizan para contener magnitudes y se clasifican en numéricos enteros y numéricos reales.

  1. Numérico Entero Se emplea para representar números enteros, pudiendo llevar o no el signo correspondiente. Se expresa mediante una serie de signos correspondientes (de 0 a 9), que pueden estar precedidos por el signo + o -.
  2. Numérico Real Se emplea para representar números con parte decimal.

Carácter

Se emplea para representar un carácter dentro de un conjunto definido por el fabricante del ordenador, de tal forma que cada carácter se corresponde con un número entero sin signo según un determinado código.

Una constante de tipo carácter se expresa encerrando el carácter entre comillas simples.

Una cosntante de tipo cadena se expresa delimitando el conjunto de caracteres entre comillas dobles.

Lógico

Se emplea para representar dos valores opuestos. Una constante de tipo lógico se puede representar como VERDADERO o FALSO.

Datos derivado (puntero)

Se emplea para contener la dirección de memoria otra variable. Este tipo de variable es de gran utilidad para realizar operaciones con estructuras dinámicas y para el paso de parámetros por dirección en una llamada a un módulo o función del programa.

Características especiales de los datos tipo puntero:

  1. Se debe definir inicialmente la variable con el mismo tipo de dato que las variables a las que puede apuntar o referenciar
  2. Una vez definida la variable puntero se le debe asignar un contenido.
  3. Se puede hacer una referencia indireta al valor de una variable a través de un puntero
  4. Se puede volver a utilizar el puntero para apuntar a otra variable, con la condición que sea del mismo tipo que el definido por el puntero

Datos estructurados

Tienen de forma general las siguientes características.

  • Datos internos Son los que residen en la memoria principal del ordenador. Ej. una tabla bidimendional de los números reales
  • Datos externos Son los que residen en un soporte externo a la memoria principal.
  • Datos estáticos Son aquellos cuyo tamaño queda definido en la compilación del programa y no se pueden modificar durante la ejecución del mismo
  • Datos dinámicos Son aquellos cuyo tamaño puede ser modificado durante la ejecución del programa
  • Datos lineales Son los que pueden estar enlazados con un solo elmento anterior y un solo elemento posterior.
  • Datos no lineales Son los que pueden enlazarse con más de un elemento anterior y posterior.
  • Datos compuestos Son los formados por el programador en base a los tipos de datos básicos.

Constantes y variables

  • Constantes: Son datos cuya información es fija durante la ejecución del programa.
  • Variables: Son datos cuya información puede variar durante la ejecución del programa

Operadores

Los operadores son símbolos que sirven para conectar los datos facilitando la realización de diversas clases de operaciones.

Tipos de operadores

  • () Parémtesis
  • Aritméticos
    • **, ^ Potencia
    • * Producto
    • / División
    • div, \ División entera
    • %, mod Módulo (resto de la división entera)
    • + Singno positivo o suma
    • - Signo negativo o resta
  • Alfanuméricos
    • + Concatenación
    • - Concatenación eliminando espacios
  • Relaciónales
    • ==, = Igual a
    • !=, < > Distinto a
    • < Menor que
    • > Mayor que
    • <= Menor o igual que
    • >= Mayor o igual que
  • Lógicos
    • !, NOT, no Negación
    • &&, AND, y Conjunción
    • ||, OR, o Disyunción

Tablas de verdad

En las operaciones lógicas, aquellas que utilizan operadores lógicos y relacionales, se determina su resultado por medio de las tablas de verdad.

  • A = V; B = V;
    • A && B = V
    • A || B = V
    • !A = F
    • !B = F
  • A = V; B = F;
    • A && B = F
    • A || B = V
    • !A = F
    • !B = V
  • A = F; B = V;
    • A && B = F
    • A || B = V
    • !A = V
    • !B = F
  • A = F; B = F;
    • A && B = F
    • A || B = F
    • !A = V
    • !B = V

Orden de prioridad de los operadores

Dentro de las expresiones hay que respeta un orden de prioridad entre los operadores que depende del lenguaje utilizado, pero de forma general se puede establecer una prioridad de mayor a menor de la siguiente forma:

  1. Paréntesis (comenzando por los más internos)
  2. Signo
  3. Potencia
  4. Producto, división y módulo (Con la misma prioridad)
  5. Suma y resta (Con la misma prioridad)
  6. Concatenación
  7. Relacionales
  8. Negación
  9. Conjunción
  10. Disyunción

Los operadores con la misma prioridad se evalúan de izquierda a derecha

Expresiones

Las expresiones son un conjunto de datos (operandos) y operadores con unas reglas específicas de construcción. En la obtención del resultado se debe tener en cuenta el orden de prioridad de los operadores.

En función del resultado que se obtiene, las expresiones se pueden clasificar en:

  • Numéricas: Su resultado es númerico y utilizan operandos y operadores aritméticos
  • Alfanuméricas: Su resultado es una cadena de caracteres y utlilizan operadores alfanumércos
  • Lógicas o booleanas: Su resultado es verdadero o falso y utilizan operadores relacionales y lógicos.
Obtenido de "http://alfonsomorcuende.com/wiki/index.php?title=Estructuras_b%C3%A1sicas_de_datos"
Herramientas personales