Algoritmos y Estructuras de Datos pdf

Vista previa del material en texto

Algoritmos y Estructuras de Datos 
Desarrollo descriptivo de los temas vistos en el Año, según plan anual de 
actividades 2014 UTN - FRT 
 
Definición de dato e información. 
Dato es todo valor, característica o atributo que recibe la computadora para su almacenamiento / 
procesamiento y posterior conversión a Información, la que es el resultado del cruce de datos, 
valoración y evaluación de estos. 
Clasificación de los tipos de datos. 
Los datos pueden clasificarse en: 
- Estáticos: los que pueden ser: 
 Simples: Integer, Boolean, Char, Real. 
 Estructurados: Arreglos. 
- Dinámicos: Punteros. 
Tipos elementales de datos: constantes y variables. 
Constante: es un espacio de memoria, con un valor asignado y estatico (no puede ser modificado), 
se utiliza comúnmente para hacer referencia a datos que no cambian en el tiempo a corto plazo. 
Ejemplo: una Alicuota de impuesto. 
Variable: es un espacio de memoria al que se asignaran valores con posibilidad de cambio muy 
frecuente. Para su declaración requiere de un Nombre, Tipo y alternativamente un Valor inicial. 
Ejemplo: el Salario de un Empleado. 
La operación de asignación y operación de transferencia. 
Decimos que asignamos un valor a una variable cuando por medio del operador de asignación ‘=’ 
cargamos un dato en dicha variable. 
Ejemplos: 
Sea ‘a’ una variable del tipo entero, decimos: 
 a = 10; 
 a = 10 + 2; 
Sean ´a´, ´b´ y ‘c’ variables del tipo entero, decimos: 
 a = 10; 
 b = 5; 
 c = a + b; 
 
Expresiones: aritméticas, de relación, lógicas y compuestas. 
Para trabajar con operaciones aritméticas o lógicas están definidos los operadores que se detallan 
a continuación: 
Operador Tipo Expresion Resultado 
+ Aritmética c = a + b La suma de a y b 
- Aritmética c = a – b La resta de b en a 
* Aritmética c = a * b El producto de a con b 
/ Aritmética c = a / b El cociente entre a y b 
Mod Aritmética c = a mod b El resto del cociente a y b 
Div Aritmética c = a div b Parte entera del cociente 
^ Aritmética c = a ^ b Potencia de a elevado a b 
= Asignacion a = b Se asigna el valor de b a a 
+= Aritmética a += b Se asigna el valor de a mas b a a 
-= Aritmética a -= b Se asigna el valor de a menos b a a 
++ Aritmética a++ Incremento en uno el valor de a 
-- Aritmética a-- Decremento en uno el valor de a 
== Lógica a == b Si a y b son iguales es ‘Verdadero’ 
>= Lógica a >= b Si a es mayor o igual a b es ‘Verdadero’ 
<= Lógica a <= b Si a es menor o igual a b es ‘Verdadero’ 
!= Lógica a != b Si a es distinto a b es ‘Verdadero’ 
! Lógica !a Negación de a (a = v entonces a = f) 
>= || <= Logica Compuesta a >= b || b <= c Operador O 
== && <= Logica Compuesta a >= b && b <= c Operador Y 
 
Las partes principales de un problema: datos, resultados y condiciones. 
Un Problema Computacional es aquella situación de la que se intenta tener solución mediante un 
algoritmo, brindando una respuesta para cada caso específico de dicha situación, o mínimamente 
indicando que no existe una solución por medio de ese algoritmo. 
 Por lo general se necesitan datos de entrada, que serán los parámetros básicos que el algoritmo 
utilizara para hallar la solución. El resultado de estos datos procesados será la información que 
describa la solución. 
Para llegar a esta solución se considera el proceso de los datos por medio de las condiciones, que 
son los pasos que el algoritmo realiza para la transformación de datos a información. 
 
Contadores, acumuladores, banderas. 
Un contador es una variable que incrementa o decrementa en un valor fijo, utilizada para obtener 
cantidades para determinada información. Ejemplo la cantidad de vueltas realizadas en un bucle, c 
= c + 1; 
Un acumulador es una variable que incrementa o decrementa su valor en relación a otro, utilizada 
para conseguir subtotales o cantidades acumulativas. Ejemplo, la suma de los salarios de una 
nómina de empleados, s = s + e; 
Una variable bandera determina si uno o varios datos están listos para algún proceso determinado, 
indicando con verdadero (1) o falso (0) dicho estado. Ejemplo, si termino de contar entonces salga: 
if (contados) exit(); 
Concepto y definición de algoritmo. 
Es el conjunto ordenado de operaciones sistemáticas, dispuestas tal que puedan hallar la solución 
a un determinado problema. 
Ejemplo: algoritmo para sacar el promedio: 1) acumulo todos los valores. 2) divido la acumulación 
en la cantidad de datos procesados. 3) muestro el resultado. 
Su representación gráfica: el diagrama de flujo lógico. 
Un algoritmo puede ser representado gráficamente mediante el uso del diagrama de flujo, el cual 
consta de una simbología descripta a continuación: 
 
 
 
 
 
 
El teorema fundamental de la programación estructurada. 
Establece que todo programa puede ser diseñado por un lenguaje de programación que convine 3 
tipos de estructuras de control: 
 Secuencial: Una instrucción bajo la otra. 
 Selección: Las instrucciones se ejecutan si y solo si la evaluación de una expresión lógica. 
 Iteración: Las instrucciones se ejecutaran un determinado número de veces mientras una 
expresión lógica se cumpla. 
Inicio / Fin 
Proceso / Asignación / 
Operación 
Decisión 
Ingreso de 
Datos 
Salida por 
Pantalla 
Salida por 
Impresora 
Estructuración de un programa: encabezamiento, bloque de declaraciones, bloque de acciones. 
Un programa en lenguaje C tiene la siguiente estructura: 
#include <stdio.h> Librerías o Cabeceras 
int v[100]; 
void carga(); 
float promedio(int a, int b, int c); 
main(){ 
float r; 
carga(); 
r = promedio(8, 5, 3); 
printf(“el promedio es %f”, r); 
} 
void carga(){ 
… 
… 
… 
} 
Representación de datos elementales. 
Entero int 98, -65, 65535 
Real float, double 30.58, 60.00, -67.25025 
Carácter char ‘a’… ’z’, ‘5’, ‘?’, ‘-’, ‘>’ 
 
Sentencias de entrada y salida. 
Funciones de ingreso de datos e impresión por pantalla: 
scanf(“%d”, &a); 
scanf(“%d/%d/%d”, &a, &b, &c); 
scanf(“%d-%f”, &a, &b); 
 
Declaración de Variables Globales, Constantes y 
Prototipos de funciones 
Cuerpo del Programa, Instrucciones de la 
función principal del programa. 
Cuerpo de una Función, instrucciones de una 
función personalizada. 
scanf lleva tantos parámetros como datos queremos obtener por teclado, el primer parámetro es 
el formato y cantidad de variables receptoras, luego tantas variables como modificadores de 
formato tengamos. 
printf(“ingrese la cantidad deseada.”); 
printf(“el resultado es: %d”, a); 
printf(“el área del triangulo es %f y su perímetro es %d”, a, b); 
la función printf puede mostrar un mensaje estatico o constante con solo un parámetro del tipo 
cadena, o bien puede mostrar el contenido de tantas variables como modificadores de formato 
tenga el primer parámetro. 
 
Implementación de las estructuras secuenciales, condicionales. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Estructura secuencial: 
printf(“ingrese un valor”); 
scanf(“%d”, &a); 
printf(“el doble de %d es %d”, a, 
a*2); 
 
Estructura condicional simple: 
if (a >= 10){ 
 printf(“el valor es mayor o igual que 10!”); 
} 
Estructura condicional compuesta o anidada: 
if (b>a){ 
 if (b<c){ 
 printf(“el valor es se encuentra dentro del rango 
(a, c)!”); 
 } 
else{ 
 printf(“el valor es excede el rango (a,b)”); 
 } 
} 
else{ 
 printf(“el valor es inferior al rango (a,b)”); 
} 
 
Estructura condicional completa: 
if (a >= 10){ 
 printf(“el valor es mayor o igual que 10!”); 
} 
else{ 
printf(“el valor es menor que 10!”); 
} 
Estructuras repetitivas en Lenguaje C. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Abstracción funcional, pautas de programación modular. 
La modularidad o abstracción funcional permite dividir el código de un programa en bloques de 
funciones, de esta manera la estructura es más ordenada, permite reutilizar el código y detectar 
errores con mayor facilidad. Una función consta de prototipo, que es la declaración de su tipo de 
retorno,nombre y parámetros, el cuerpo donde se codifican las instrucciones que realizara la 
funcion y uno o varios llamados desde alguna línea del programa. Cuando una función retorna un 
valor es necesario especificarlo por medio de la palabra reservada return. En caso de que no sea 
necesario un retorno se omite return y el tipo de la funcion será void. 
Ejemplos: 
void carga(); 
void eliminar(int posicion); 
float promedio(int a, int b, intc); 
son prototipos de funciones sin tipo y sin parámetro, sin tipo con parámetros y con tipo y 
parámetros respectivamente. 
Ciclo repetitivo while: 
while (c<n) { 
… 
… 
c++; 
} 
 
Ciclo repetitivo do…while: 
do { 
… 
… 
c++; 
} while(c<10); 
 
Ciclo repetitivo for: 
for(i=0; i<n; i++){ 
 … 
 … 
} 
 
Definición de función. 
 
Variables globales, variables locales, ámbito de validez. 
Se dice que una variable es global cuando esta es declarada en la parte superior del código. Esta 
disponible para su acceso desde cualquier línea de código y en cualquier ámbito de una función. 
Las variables locales se declaran dentro de las funciones y solo están disponibles dentro de estas 
siendo imposible su acceso desde otra línea de código externa a la función donde fue declarada. 
Recursividad. 
La recursividad es una practica bastante útil para ahorrar código y se utiliza en algoritmos donde es 
necesario realizar un mismo calculo varias veces. La función se llamara a si misma para realizar 
nuevamente un calculo en base a un resultado obtenido por ella. 
Un buen ejemplo es el Algoritmo de Euclides, que sirve para determinar el mayor común divisor 
entre dos números, siendo a > b. 
void euclides(int a, b){ 
if (b==0) printf(“el mayor comun divisor es: %d”, a); 
else euclides(b, a % b); 
} 
Definición de dato estructurado. 
A diferencia de los tipos de datos simples, que solo pueden almacenar un valor a la vez, los tipos de 
datos estructurados pueden albergar colecciones de datos, de la misma naturaleza, reservando un 
espacio de memoria fijo durante la ejecución del programa. 
Arreglos unidimensionales: definición, lectura e impresión. 
Los arreglos unidimensionales, array o vectores son colecciones de datos de la misma 
característica, diferenciados por una posición o índice unidimensional y con un tamaño fijo o tope. 
Representación en lenguaje C de vectores. 
Para definir un arreglo en lenguaje C declaramos la variable con su tipo, seguido del tamaño o tope 
del vector entre corchetes: 
Int v[100]; 
Accedemos a cada uno de los elementos del vector especificando su posición o índice: 
a = v[0]; //a es igual a la primera posición del vector; 
Operaciones con vectores. 
Para operar con un vector se debe iterar (recorrer de inicio a fin) entre los elementos de este: 
Ejemplo: búsqueda: 
void búsqueda(int x){ 
while(c<n){ 
 if (v[c] == x) printf(“se encontró el valor en la posición %d”, c); 
c++; 
} 
} 
Vectores paralelos. 
Son dos o mas vectores que están relacionados por el mismo índice, es decir cada dato de cada 
vector en un misma posición es parte de una misma relación o de un mismo criterio. 
Ejemplo: 
Int código[100]; 
Int cantidad[100]; 
float precio[100]; 
printf(“el precio del producto %d es: %f y hay %d en existencia”, código[c], precio[c], cantidad[c]); 
Métodos de ordenamiento. 
 
Arreglos bidimensionales: definición, lectura e impresión. 
Un array bidimensional o matriz esta organizado en filas y columnas, albergando datos en un 
formato de rejilla, consta de dos índices, uno para cada dimensión. 
 
 
 
 
 
Arreglos Multidimensionales: definición, lectura e impresión, operaciones, representación en 
lenguaje C. 
Para operar con matrices en lenguaje C se procede: 
int m[100][100]; //declaración del arreglo. 
int i, j; // declaracion de los contadores para los indices; 
for(i = 0; i<100; i++) //iteracion de la dimension i 
 for(j = 0; j<100; j++) //iteracion de la dimension j 
scanf(“%f”, &m[i][j]); //se lee por teclado un valor entero 
//y se almaciena en la pocicion i,j de la matriz. 
 
Complejidad Computacional. 
Orden de Complejidad. 
Cadenas de Caracteres: definición, lectura e impresión, representación en lenguaje C y funciones 
definidas en él. 
Una cadena de caracteres es un array de elementos del tipo char, es decir un conjunto 
estructurado de caracteres. 
char nombre[60]; //declaracion 
gets(nombre); //lectura por teclado 
puts(nombre);//impresión en pantalla 
Funciones para operar con cadenas de caracteres: 
 Comparación: strcmp(cad1, cad2); compara dos cadenas devolviendo 0 si son iguales, 
mayor a 0 si cad 1 es > a cad2 o menor a 0 si cad1 es < a cad2. 
 Concatenación: strcat(cad1, cad2); concatena o une dos cadenas en una sola. 
 Longitud: strlen(cad1); devuelve la longitud o cantidad de caracteres en una cadena. 
 Convertir en Mayuculas: strupr(cad1); convierte todos los caracteres en su forma 
mayuscula. 
 Convertir en Minusculas: strlwr(cad1); convierte todos los caracteres en su forma 
minuscula. 
 Copia; strcopy(cad1, cad2); copia los caracteres de cad2 en cad1. 
Registros: definición, lectura e impresión, representación en lenguaje C. 
Es un tipo de dato estructurado formado por la unión de varios elementos bajo una misma 
estructura. Se define el nuevo tipo de dato y sus miembros o propiedades, a las que se acceden 
através del operador “.” 
struct{ 
 char nombre[60]; 
 int edad; 
 float saldo; 
}persona; //declaramos la estructura del nuevo tipo de dato registro. 
persona p; //declaramos una variable del tipo de dato “persona”. 
gets(p.nombre); //ingresamos por teclado el atributo “nombre” para la variable. 
scanf(“%d”, &p.edad); //ingresamos por teclado el atributo “edad” para la variable. 
scanf(“%f”, &p.saldo); //ingresamos por teclado el atributo “saldo” para la variable. 
 
Registros jerarquizados. 
Son registros donde uno o varios de sus miembros son del tipo registro. 
struct{ 
int dia; 
int mes; 
int anio; 
}fecha; 
struct{ 
 char nombre[60]; 
 fecha nacimiento; 
}persona; 
 
 
Introducción a Archivos: Definición, Representación en lenguaje C. 
Un archivo es el almacenamiento en disco de datos. 
FILE *archivo = fopen(“nombre.extencion”, modo); 
En una variable de tipo puntero a FILE se almacena la dirección donde se encuentra el archivo fisico 
y el modo con el que se operara con el. 
Modos: 
 "r" : abrir un archivo para lectura, el fichero debe existir. 
 "w" : abrir un archivo para escritura, se crea si no existe o se sobreescribe si existe. 
 "a" : abrir un archivo para escritura al final del contenido, si no existe se crea. 
 "r+" : abrir un archivo para lectura y escritura, el fichero debe existir. 
 "w+" : crear un archivo para lectura y escritura, se crea si no existe o se sobreescribe si existe. 
 "r+b ó rb+" : Abre un archivo en modo binario para actualización (lectura y escritura). 
 "rb" : Abre un archivo en modo binario para lectura. 
 
FILE *archivo; 
archivo = fopen ( "datos.dat", "r" ); 
 if (archivo ==NULL) { 
 printf(“error al abrir el archivo”); 
} 
fclose (archivo); 
} 
Funciones de archivos: 
Abrir Archivo: fopen(ruta_del_archivo, modo_de_apertura); 
Cerrar archivo: fclose(archivo); 
Escribir: fwrite(buffer_escritura, tamanio_del_bloque_escritura, 1, archivo); 
Leer: fread(buffer_lectura, tamanio_del_bloque_lectura, 1, archivo); 
Reiniciar la lectura: rewind(archivo); 
Consultar Final del Archivo: feof(archivo); 
Escritura de Texto: fprintf(archivo, formato, dato_a_escribir); 
Lectura de Texto: fgets(buffer_lectura, tamanio, archivo); 
Variables de tipo puntero: definición, representación en lenguaje C. 
Lista: definición, tipos e implementación en lenguaje C. 
Pila: definición, tipos e implementación en lenguaje C. 
Cola: definición, tipos e implementación en lenguaje C.