Estructuras Básicas de Datos:
Introducción:Dato: Cualquier información correspondiente a una entidad susceptible de un tratamiento informático. Ej.: (Entidad: Empresa / Datos: Nombre, Dirección, Nº Empleados…)
Para un ordenador la información que maneja es numérica (ceros y unos) “binario”, aún así, los datos tienen que estar clasificados para poder tratarlos de forma conveniente.
La clasificación de los datos determina las
ESTRUCTURAS DE DATOS de un lenguaje.
Un dato se caracteriza por llevar asociado los siguientes elementos:
Identificador: nombre que permite referenciar el dato.
Los identificadores de los datos deben cumplir una serie de condiciones:
a- Pueden estar constituidos por letras, dígitos y el carácter “_”
b- No pueden contener espacios.
c- El nº de caracteres y dígitos máximos dependen del compilador utilizado.
d- Deben comenzar por una letra
e- Deben dar alguna pista para reconocer el dato que van a referenciar.
Tipo: Determina el rango de valores que van a ser posibles para ese dato.
Ej.: EDAD: Nº entero.
Valor inicial: Valor perteneciente al rango determinado por el tipo asociado al identificador.
Tipos de datos:Clasificación de los datos:
Datos Básicos
Numéricos: Entero, Real
No Numéricos: Carácter, Lógico
Derivados: Puntero
Datos Estructurados:
Internos:
Estáticos lineales: Tablas
Dinámicos Lineales: Listas, Pilas, Colas
No lineales: Árboles, Grafos
Externos: Ficheros, Bases de Datos
Compuestos: Estructura de Datos, Registro
Puntero: Funciona con direcciones de memoria asociadas.
Existe un operador que permite obtenerlas, pero ya lo trataremos más adelante.
Datos estructurados: Compuestos de datos básicos.
(Internos: Memoria Temporal / Externos: Dispositivos de Almacenamiento)
Datos dinámicos: Reservas de memoria en tiempo de ejecución.
Lista: Se accede y llena en cualquier orden.
Pila: Se insertan los datos en orden, se extraen en orden inverso.
Cola: Obligatorio insertarlos en orden y extraerlos en ese mismo orden.
Datos estáticos: Reservan una cantidad fija de memoria (En tiempo de compilación)
Datos Básicos:Datos numéricos: Se utilizan para contener magnitudes y se dividen en enteros y reales.
a- Enteros: Se emplean para representar números enteros, el rango de representación depende del compilador y del ordenador. Los datos de tipo entero aparecen representados por los dígitos decimales, que pueden ir precedidos por los signos + o -. Ej.: -35 +3200.
b- Reales: Se emplean para representar números con parte fraccionaria o números Enteros muy grandes o muy pequeños que están fuera del rango establecido para los enteros.
Para su representación se utilizan dos formatos:
•
Decimal: Dígitos del 0 a 9 y el punto decimal que separa la parte entera de la fraccionaria.
•
Formato Científico o Exponencial: <mantisa><E><característica>
Mantisa: Nº real decimal.
E: Base 10
Característica: Exponente.
La representación interna viene determinada por la precisión:
•
Para simple precisión (32 bits)o Signo - 1bit - (posición 31)
o Exponente - 8bits - (posiciones 23 a 30)
o Mantisa - 23bits - (posiciones 0 a 22)
•
Para doble precisión (64 bits)o Signo - 1bit - (posición 63)
o Exponente - 11bits - (posiciones 52 a 62)
o Mantisa - 52bits - (posiciones 0 a 51)
Datos No numéricos:a- Carácter: Se emplea para representar un carácter dentro de un conjunto definido por el fabricante del ordenador, de tal manera que cada carácter se corresponda con un nº entero, según un determinado código. Ej.: Código ASCII.
Se representan encerrando el carácter entre comillas simples, existen los siguientes tipos de caracteres:
o Dígitos: ‘1’,’0’,’9’…
o Alfabéticos: ‘A’,’a’,’b’…
o Especiales: ‘*’,’_’…
La representación interna depende del código utilizado, los códigos más empleados son los que utilizan 8 bits, como por ejemplo el
ASCII (American Standard Code for Information Interchange) o el EBCDIC (Extended Binary Coded Decimal Interchange Code)
Ej.: A = 65 = 01000001
En algunos lenguajes como el COBOL se considera tipo de dato básico a las cadenas alfanuméricas. Estas se representan encerradas entre dobles comillas.Ej.: “I.E.S Dr. Fleming Nº25”
En C no es un tipo de dato básico (Se usan tablas)b- Lógico: Es un tipo de dato que solo puede tomar dos valores, se pueden representar como Cierto y Falso, True y False, V y F.
Internamente se representa con un ‘0’ para false y un ‘1’ para true.
En C ‘0’ es false, mientras que cualquier otra cosa se considera como true.
Variables y Constantes:Memoria Central: Dispositivo de almacenamiento temporal de:
• Datos
• Instrucciones
• Resultados de un programa:
o Intermedios
o Finales
Consideremos la memoria como una caja dividida en compartimentos. Cada compartimento es del mismo tamaño y está identificado por una dirección de memoria. Los compartimentos se suelen denominar celdas, las direcciones, posiciones de memoria.
Cada celda tiene una dirección distinta que permite identificarla. Esto nos permite almacenar y recuperar datos de la Memoria Central.
Nota: Las cadenas no se pueden meter en una sola dirección de memoria, sino que usan varias simultáneamente.Almacenar algo en una posición usada
sobrescribe lo anterior por lo tanto:
La escritura en memoria es destructiva, mientras que la lectura no lo es.Las zonas de memoria no están vacías a menos que se sobrescriban intencionadamente.
Las direcciones de memoria se pueden identificar con un nombre, el sistema se encarga de asignar una dirección concreta a ese nombre.
(En lenguajes de programación de alto nivel)[C o superior].Variable: Zona de memoria referenciada con un nombre de variable que va a contener un dato.
Nota: Una variable NO es un dato, contiene un dato.Para que una variable esté perfectamente definida hay que indicarle:
• Un nombre (identificador)
• Un tipo de dato
• Un valor inicial
Para introducir un valor en una variable se realiza lo siguiente:
A este hecho se le llama Asignación de Variables.
Para recuperar el valor basta con nombrar la variable:
(
haciendo esto la máquina tomará <valor> de la memoria y sustituirá la variable por dicho valor en la ejecución)
En función del dato asignado a la variable, se pueden clasificar en numéricas, enteras, reales, alfanuméricas, caracteres y lógicas.
Asignación: Introducción de un valor o del contenido de otra variable en una zona de memoria referenciada por ese nombre de variable. = se usa tanto como asignación, como para preguntar al sistema si es igual.
Nota: Se aconseja usar ‘==’ para preguntar si es igual y ‘=’ para asignar, esto ayudará a diferenciar ambas tareas de forma sencilla a la hora de revisar el código.Tanto la variable receptora como la otra tienen que ser del mismo tipo para realizar la asignación del valor de una variable a otra.
<variable1> = <variable2>
: Es una zona de memoria referenciada con un nombre de constante, cuyo valor no puede cambiar a lo largo de la ejecución de un programa.
Las constantes pueden ser numéricas, enteras o reales, alfanuméricas o de carácter.
Las constantes lógicas no tienen sentido.
Operadores:Operadores: Símbolos que permiten conectar datos, variables y constantes con el fin de realizar una operación determinada.
Operador - Símbolo - Significado
Paréntesis - () - Paréntesis
Aritméticos - **,^ - Potencia
* - Producto
/ - División Real
DIV,\ - División Entera
%,mod - Resto de una división entera
+ - Suma
- - Resta
+ - Concatenación
- - Concatenación eliminando espacios en blanco
Relacionales - ==,= - Igual, Asignación
!=,<> - Distinto
< - Menor
<= - Menor o Igual
> - Mayor
>= - Mayor o Igual
Lógicos - !,NOT,NO - Negación
ff,AND,Y - Conjunción
||,OR,O - Disyunción
AB AND AB OR A NOT
00 0 00 0 0 1
01 0 01 1 1 0
10 0 10 1
11 1 11 1
Existen
reglas de prioridad entre los distintos operadores, dependen de los lenguajes de programación, pero en general son los siguientes:
1. Paréntesis
2. Signo
3. Potencia
4. Producto, División y Módulo (Resto)
5. Suma y Resta
6. Concatenación
7. Relacionales
8. Negación
9. Conjunción
10. Disyunción
Expresiones:Expresiones: Son un conjunto de valores variables (operandos) y operadores relacionados o combinados entre si, según unas reglas establecidas. Los operandos pueden ser también valores retornados por funciones.
En función del resultado obtenido, las expresiones se clasifican en:
•
Aritméticas: El resultado de la evaluación de la expresión es numérico.
•
Relacionales: Utilizan operadores relacionales y el resultado es un valor lógico.
•
Lógicas: Utilizan operadores lógicos y se aplican expresiones relacionales. El resultado de la evaluación es un valor lógico.
•
Alfanuméricas: Utilizan operandos y operadores alfanuméricos.
--
ESTRUCTURAS ESTÁTICAS DE DATOS:Tablas: Está formada por un número fijo de elementos (variables) todos ellos del mismo tipo de datos y situados en posiciones contiguas de memoria.
Elemento: Es cada uno de los datos que constituyen la tabla.
Nombre de Tabla: Es un nombre de variable que permite referenciar toda la tabla de forma global y nos permitirá acceder a cada elemento de forma individual.
Tipo de Tabla: Es el tipo de dato de todos los elementos de la lista.
Índices: Un entero positivo que nos permite identificar cada elemento de una tabla.
Tamaño de Tabla: Número máximo de elementos que componen la tabla.
ACCESO A LOS ELEMENTOS: Los elementos de una tabla tratados individualmente son variables que reciben el mismo trato que cualquier otra variable simple, con un tipo de dato que coincide con el tipo de la tabla y una denominación propia que la distingue de los diversos elementos. Para acceder o referenciar un elemento en particular es suficiente con
indicar el nombre de la tabla seguido por el índice correspondiente entre paréntesis.
Dimensión: El número de índices que necesitamos para referenciar una tabla.
CLASIFICACIÓN DE LAS TABLAS:•
Unidimensionales: (Vectores) En este caso, solo es necesario un índice para acceder a los elementos de la misma.
•
Bidimensionales: (Matrices) Son aquellas que necesitan dos índices para acceder a cada uno de sus elementos.
<Nombre> (<índice1><índice2>)
Desde el nacimiento de la informática, se han ido desarrollando métodos y herramientas con el objetivo de facilitar y mejorar el diseño y resolución de programas. Hay dos clases:
Programación estructurada: Conjunto de técnicas que incorporan:
a- Diseño descendente (Top-Down) “Diseño por capas”
b- Descomposición de tareas en tareas más simples
c- Solo se pueden utilizar 3 tipos de estructuras
a. Alternativa
b. Repetitiva
c. SecuencialProgramación modular: Consiste en la división de un programa en módulos, de tal forma que cada uno de ellos se encargue de la ejecución de una tarea. Los módulos pueden ser subprogramas, subrutinas, funciones o procedimientos.
Partes de un programa:Todo programa está constituido por un conjunto de instrucciones o de órdenes capaces de manipular los datos. Estas órdenes pueden ser divididas en tres grandes grupos que determinan las partes de un programa.
Entrada de datos -> Proceso -> Salida de resultados•
Instrucciones de entrada de datos: Conjunto de instrucciones que permiten llevar datos desde el exterior (tomar datos a través de un dispositivo de entrada y almacenarlos en la memoria central).
•
Instrucciones de proceso: Conjunto de instrucciones encargadas de procesar o realizar un tratamiento de datos obteniendo unos resultados que se almacenan en la memoria central.
•
Instrucciones de salida: Permiten extraer datos (resultados) de la memoria central mostrándolos a través de un dispositivo de salida.
Datos ->
Dispositivo Externo <-> Memoria Principal <-> Proceso o algoritmo
<- Resultados
Algoritmo:Es la descripción abstracta de todas las acciones u operaciones que debe realizar un ordenador de forma clara y detallada así como el orden en el que estas deberán ejecutarse junto con la descripción de todos aquellos datos que deberán ser manipulados por dichas acciones y que nos conducen a la solución del problema. Un algoritmo deberá reflejar las 3 partes de un programa (entrada, proceso, salida) es importante tener en cuenta que todo algoritmo debe ser totalmente independiente del lenguaje de programación utilizado. Las características que debe cumplir el diseño de todo algoritmo son las siguientes.
a-
Debe ser conciso y detallado. Debe reflejar con el máximo detalle el orden de ejecución de cada acción u operación que vaya a realizar el ordenador.
b-
Debe ser flexible, permitiendo y facilitando así las futuras modificaciones o actualizaciones del diseño realizado.
c-
Debe ser finito, tener comienzo y final.d-
Ser lo más claro y sencillo posible.Diagramas de Flujo:Son representaciones gráficas que mediante símbolos estandarizados permiten describir las acciones y la lógica que ha de seguir un algoritmo junto con el flujo de datos para la obtención de los resultados convenidos.
Ordinogramas: Diseño
Organigramas: Análisis
Pseudocódigo: Lenguaje
intermedio entre el natural y el lenguaje de programación (el cual vamos a tratar en este tutorial). Todo algoritmo en pseudocódigo debe reflejar las distintas partes de un programa.
Tipos de Instrucciones:Instrucción: Hecho o suceso de duración limitada que permite generar unos cambios previstos en la ejecución de un programa.
Instrucciones de definición de datos: Permiten reservar la memoria necesaria para almacenar los datos que se van a manejar en el programa. Mediante el uso de variables simples o complejas.
Las instrucciones de definición consisten únicamente en dar un nombre y un tipo de dato a las zonas de memoria que quiero reservar.
Instrucciones primitivas:
•
Instrucciones de Entrada: Permiten almacenar un dato en la memoria central durante el uso de una o más variables procedentes de un dispositivo externo (generalmente el teclado).
Leer <variable>
Leer <lista de variables
Esta instrucción para el proceso de ejecución hasta que se introduzcan tantos datos como variables aparezcan en la lista de variables.
•
Instrucciones de Asignación: Consiste en introducir en una variable el resultado de evaluar una expresión.
•
Instrucciones de Salida: Permiten recuperar un dato de la memoria central para mostrarlo desde un periférico de salida.
visualizar <expresión> (Pantalla)
imprimir <expresión> (Impresora)
Se utilizan para controlar la secuencia de ejecución de un programa y también para determinar si se ejecutan o no bloques de instrucciones:
•
Alternativas:
o
Simple: Permite la ejecución de un grupo de instrucciones en función de que se cumpla o no una condición.
Si <condición>
<instrucción1>
<instrucción2>
<instrucciónn>
Fin Si
o
Doble: Permite decidir por un grupo de instrucciones u otro en función de si se cumple la condición o no.
Si <condición>
<instrucción11>
<instrucción12>
<instrucción1n>
Sino
<instrucción21>
<instrucción22>
<instrucción2n>
FinSi
o
Múltiple: Ejecuta distintos grupos de instrucciones en función del resultado de la evaluación de una expresión.
Según_Valor: <expresión>
<valor1>: <bloque de instrucción 1>
<valor2>: <bloque de instrucción 2>
<valorn>: <bloque de instrucción n>
Por_Defecto: <bloque de instrucción por defecto>
Fin_Según_Valor
Nos permiten variar o alterar la secuencia normal de ejecución de un programa haciendo posible que un grupo de acciones se ejecute más de una vez de forma consecutiva, también se denomina bucles o lazos.
-
Estructura Mientras: Se caracteriza por la repetición de un conjunto de instrucciones en función de que se cumpla o no la condición, pueden repetirse de 0 a n veces.
Mientras <condición>
<Instrucción1>
<Instrucción2>
<Instrucciónn>
Finmientras
o Se evalúa la condición, si se cumple, se ejecutan las instrucciones comprendidas entre el mientras y el fin mientras y de nuevo se evalúa. El proceso termina cuando la condición se cumple.
-
Estructura Repetir: Permite la repetición de un proceso mientras se cumpla una condición evaluando la condición al final de cada repetición, el proceso se repite de 1 a n veces.
Repetir
<Instrucción1>
<Instrucción2>
<Instrucciónn>
Mientras <condición>
o El conjunto de instrucciones entre repetir y mientras, se ejecuta (al menos una vez) evaluando la condición y volviendo a repetir en caso de que se cumpla.
-
Estructura Para: Repetición de un proceso un número determinado de veces
Para <variable> = <valor_inicial> hasta <valor_final> Inc = <valor_incremento>
<Instrucción1>
<Instrucción2>
<Instrucciónn>
Finpara
Donde el incremento indica la cantidad a aumentar la variable dentro del proceso repetitivo.
Contadores y Acumuladores:Contador: Es una variable que se incrementa o decrementa en una cantidad constante.
<variable> = <variable> + 1
: Variable que se incrementa en un valor no constante.
<variable1> = <variable1> + <variable2>
Tenéis disponibles en este otro post varios ejercicios resueltos de pseudocódigo con los que podéis poner en práctica lo aprendido en este.
Ejercicios de PseudocódigoIré actualizando ambos post según me vaya siendo posible.
Mostrar Temas
