Algoritmos y estructuras de datos 1

Vista previa del material en texto

Unidad I - Resolución de problemas y algoritmos
❖ Concepto de sistema y sistemas de información.
❖ Fases del desarrollo de sistemas: Análisis, Diseño e Implementación.
❖ Datos, Procesador e Información.
❖ Resolución de problemas con computadoras, Fases.
❖ Definición de Algoritmo.
❖ Técnicas para la resolución de problemas: Análisis descendente (Top – Down) y
técnica de refinamientos sucesivos.
❖ Concepto de: programa, lenguajes de programación y traductores.
❖ Resolución de problemas y Algoritmos. Introducción a la programación estructurada
con Lenguaje C.
Concepto de:
Sistema
Es un conjunto de elementos relacionados y organizados que trabajan juntos para cumplir
una función específica o un objetivo. Puede ser físico o abstracto y estar compuesto por
personas, máquinas, procesos, tecnología, información, recursos, entre otros.
Sistemas de información
Al igual que los sistemas es un conjunto de componentes que se relacionan y trabajan
juntos para recopilar, procesar, almacenar y distribuir información. Puede incluir hardware,
software, datos, procesos y personas.
Datos
Un dato es la representación de una variable que puede ser cuantitativa (de la cantidad o
relacionado con ella) o cualitativa (de la cualidad o relacionado con ella) que indica un valor
que se le asigna a las cosas y se representa a través de una secuencia de símbolos,
números o letras.
Procesador
Es el corazón de la computadora que se encarga de realizar las operaciones aritméticas y
lógicas, así como de coordinar el funcionamiento de todos los demás componentes.
Información
Se refiere a los datos que se procesan y manipulan en un programa. La información es la
materia prima que los programas utilizan para realizar sus tareas. Puede ser representada
mediante diferentes tipos de datos que pueden ser numéricos, de texto, booleanos, entre
otros. Estos son almacenados en variables que luego se utilizan en el programa para
realizar operaciones y tomar decisiones.
Algoritmo
La palabra algoritmo se deriva de la traducción al latín de la palabra Alkhô-warîzmi2,
nombre de un matemático y astrónomo árabe que escribió un tratado sobre manipulación de
números y ecuaciones en el siglo IX.
1
Un algoritmo es un método para resolver un problema mediante una serie de pasos
precisos, definidos y finitos.
Características de un algoritmo:
● Preciso: Indica el orden de realización en cada paso.
● Definido: Si se sigue dos veces, obtiene el mismo resultado cada vez.
● Finito: Tiene fin, un número determinado de pasos.
Los métodos que utilizan algoritmos se denominan métodos algorítmicos esto significa que
se pueden implementar en computadoras. Los algoritmos se pueden expresar por fórmulas,
diagramas de flujo, pseudocódigos o N-S (combinación de todas).
métodos algorítmicos ≠ métodos heurísticos.
Programa
Es una secuencia de instrucciones u órdenes basadas en un lenguaje de programación que
la computadora interpreta de modo secuencial para resolver un problema o una función en
específico.
La programación estructurada se refiere a escribir un código en funciones que a su vez se
agrupan en distintos módulos pudiendo así reutilizar el código.
Lenguajes de programación
Un lenguaje de programación podría definirse como una notación o conjunto de símbolos y
caracteres que se combinan entre sí siguiendo las reglas de una sintaxis predefinida, con el
fin de posibilitar la transmisión de instrucciones a una computadora.
● Lenguaje de bajo nivel:
➔ Lenguaje máquina: Es un conjunto de señales eléctricas representadas en
sistema binario, es decir, solo dos valores: 0 y 1. También es llamado código
objeto.
➔ Lenguaje ensamblador: Constituye una evolución del lenguaje máquina. Se
basa en la utilización de mnemotécnicos. En general, los programas escritos
en ensamblador requieren mucho menos espacio de memoria y se ejecutan
más rápidamente que si se hubiesen desarrollado en un lenguaje de alto
nivel, puesto que están optimizados para una arquitectura específica. Sin
embargo, esto último es un inconveniente, pues causa que los programas no
sean portables de una computadora a otra con un procesador distinto.
● Lenguaje de alto nivel: Se engloban aquí todos los lenguajes de programación que
por sus características se asemejan más al lenguaje natural del programador. La
característica más importante de estos lenguajes es que son independientes de la
arquitectura de la computadora, por lo que un programa escrito en un lenguaje de
alto nivel puede ejecutarse sin problemas en otras computadoras con procesadores
diferentes.
2
Traductores
Pueden distinguirse varios tipos de traductores:
● Ensambladores: Los programas ensambladores son los encargados de traducir a
lenguaje máquina los programas escritos en lenguaje ensamblador. La
correspondencia entre ambos lenguajes es muy directa, por lo que los
ensambladores suelen ser programas relativamente sencillos.
● Intérpretes: El objetivo de un intérprete es procesar una a una las instrucciones de
un programa escrito en un lenguaje de alto nivel. Para cada instrucción se verifica la
sintaxis, se traduce a código máquina y finalmente se ejecuta. La principal
desventaja de los intérpretes es su lentitud para ejecutar los programas, pues es
necesario verificar la sintaxis y realizar la traducción en cada ejecución.
● Compilador: La función de un compilador consiste en traducir un programa fuente
escrito en un lenguaje de alto nivel a su equivalente en código máquina. Mientras
que un intérprete traduce y ejecuta al mismo tiempo cada una de las instrucciones,
un compilador analiza, traduce y posteriormente ejecuta todo el programa en fases
completamente separadas.
Resolución de problemas con computadoras.
Fases del desarrollo de sistemas: Análisis, Diseño e Implementación.
Las fases del desarrollo de un sistema son importantes para entender qué estamos
haciendo y cómo queremos hacerlo. El proceso de resolución de un problema con una
computadora conduce a la escritura de un programa y a su ejecución en la misma.
3
Las fases de resolución de un problema con computadora son:
➢ Análisis del problema (Pregunta clave ¿Qué hace?)
La primera fase de la resolución de un problema es el análisis del mismo. Requiere una
clara definición, donde se contemple exactamente lo que debe hacer el programa y el
resultado o solución deseada. Se precisan especificaciones detalladas de entrada y salida.
Para poder identificar y definir bien un problema es conveniente responder a las siguientes
preguntas:
1. ¿Qué entradas se requieren? (tipo de datos con los cuales se trabaja y cantidad).
2. ¿Cuál es la salida deseada? (tipo de datos de los resultados y cantidad).
3. ¿Qué método produce la salida deseada?
4. Requisitos o requerimientos adicionales y restricciones a la solución.
➢ Diseño del algoritmo (Pregunta clave ¿Cómo se hace?)
La resolución de un problema complejo se realiza dividiendo el problema en
subproblemas y a continuación dividiendo estos subproblemas en otros de nivel más bajo,
hasta que pueda ser implementada una solución en la computadora.
Cada subprograma es resuelto mediante un módulo (porción del programa) que tiene un
solo punto de entrada y un solo punto de salida.
➢ Resolución del problema con computadora (O codificación del programa)
La codificación es la escritura en un lenguaje de programación de la representación del
algoritmo desarrollada en las etapas precedentes. Ya que el diseño de un algoritmo es
independiente del lenguaje de programación utilizado para su implementación, el código
puede ser escrito con igual facilidad en un lenguaje o en otro.
Para realizar la conversión del algoritmo en programa se deben sustituir las palabras
reservadas en español por sus homónimos en inglés, y las operaciones/instrucciones
indicadas en lenguaje natural por el lenguaje de programación correspondiente.
4
Cuando el algoritmo previamente diseñado se convierte en un programa fuente debe ser
traducido a lenguaje máquina, este proceso se realiza con el compilador y el sistema
operativo que se encarga prácticamentede la compilación.
Si tras la compilación se presentan errores (errores de compilación) en el programa fuente,
es preciso volver a editar el programa, corregir los errores y compilar de nuevo. Este
proceso se repite hasta que no se producen errores, obteniéndose el programa objeto que
todavía no es ejecutable directamente. Para que sea ejecutable se debe instruir al sistema
operativo para que realice la fase de montaje o enlace (link), se carga el programa objeto
con las bibliotecas del programa del compilador. El proceso de montaje produce un
programa ejecutable. Suponiendo que no existen errores durante la ejecución (llamados
errores en tiempo de ejecución), se obtendrá la salida de resultados del programa.
Existen 3 tipos de errores al tratar de verificar nuestro programa, estos son:
1. Errores de compilación.
2. Errores de ejecución.
3. Errores lógicos.
En síntesis, las dos primeras fases conducen a un diseño detallado escrito en forma de
algoritmo. Durante la tercera fase (codificación) se implementa el algoritmo en un código
escrito en un lenguaje de programación, reflejando las ideas desarrolladas en las fases de
análisis y diseño.
Técnicas para la resolución de problemas:
Análisis descendente (Top-Down)
El método se conoce técnicamente como diseño descendente (top-down) o programación
modular.
Es el método de romper el programa en módulos más pequeños. Los módulos pueden ser
planeados, codificados, comprobados y depurados independientemente.
El proceso implica la ejecución de los siguientes pasos hasta que el programa se termina:
1. Programar un módulo.
2. Comprobar el módulo.
3. Si es necesario, depurar el módulo.
4. Combinar el módulo con los módulos anteriores.
Técnica de refinamientos sucesivos
El proceso de romper el problema en cada etapa y expresar cada paso en forma más
detallada se denomina refinamiento sucesivo.
El proceso que convierte los resultados del análisis del problema en un diseño modular con
refinamientos sucesivos que permitan una posterior traducción a un lenguaje se denomina
diseño del algoritmo. El diseño del algoritmo es independiente del lenguaje de programación
en el que se vaya a codificar posteriormente.
5
Unidad II - Estructuras de control
❖ Herramientas para la representación de algoritmos: Nociones de diagramas de flujo,
diagramas de Chapin y notación pseudocodificada.
❖ Introducción a C.
❖ Concepto y clasificación de: Tipos de datos, operadores y expresiones.
❖ Concepto y uso de: Variables y constantes.
❖ Operaciones primitivas: Enumeración, acumuladores y contadores.
❖ Estructuras de decisión condicional: If y else, Switch, case y break.
❖ Estructuras de control repetitivas: While, Do while y For.
Herramientas para la representación de algoritmos.
Nociones de diagrama de flujo
Un diagrama de flujo es un diagrama que utiliza los símbolos (cajas) estándar y que tiene
los pasos de algoritmo escritos en esas cajas unidas por flechas, denominadas líneas de
flujo, que indican la secuencia en que se debe ejecutar.
6
Diagramas de Chapin o Nassi-Schneiderman (N-S)
Es como un diagrama de flujo en el que se omiten las flechas de unión y las cajas son
contiguas. Las acciones sucesivas se escriben en cajas sucesivas y, como en los diagramas
de flujo, se pueden escribir diferentes acciones en una caja. Un algoritmo se representa con
un rectángulo en el que cada banda es una acción a realizar.
Ejemplo:
Notación pseudocodificada
El pseudocódigo es un lenguaje de especificación (descripción) de algoritmos. Se considera
un primer borrador. La ventaja del pseudocódigo es que en su uso, en la planificación de un
programa, el programador se puede concentrar en la lógica y en las estructuras de control y
no preocuparse de las reglas de un lenguaje específico dado que el pseudocódigo tiene que
traducirse posteriormente a un lenguaje de programación.
El pseudocódigo original se utiliza para representar las acciones sucesivas palabras
reservadas en inglés. Su escritura exige normalmente la indentación (sangría en el margen
izquierdo) de diferentes líneas.
El algoritmo comienza con la palabra start y finaliza con la palabra end, en inglés. Entre
estas palabras, sólo se escribe una instrucción o acción por línea y si es precedida por // se
denomina comentario.
Ejemplo:
start
//cálculo de impuesto y salarios
read nombre, horas, precio
salario← horas * precio
tasas← 0,25 * salario
salario_neto← salario – tasas
write nombre, salario, tasas, salario
end
Introducción a C.
C es un lenguaje compacto (tiene palabras reservadas), estructurado, compilado y
procedural, es decir, funciones llaman a otras a medida que se va desarrollando el
programa. Además de esto no es visual, no lleva colores, tipografías ni ningún tipo de
frontend.
7
Concepto y clasificación de:
Tipos de datos
Dentro de la programación (en C) hay distintos tipos de datos. Algunos de estos tipos de
datos admiten distintos números de cifras (rango y/o precisión), posibilidad de ser sólo
positivos o de ser positivos y negativos, etc.
● Datos enteros: Guarda en la variable números enteros.
➔ int: 2 bytes
● Datos caracter: Guarda en la variable letras o caracteres especiales.
➔ char: 1 byte
● Datos reales: Guarda en la variable números reales, es decir decimales, periódicos,
enteros y naturales.
➔ float: 4 bytes
➔ double float: 8 bytes
● Dato nulo: 0 bytes, no tiene datos.
Dentro de los tipos de datos existen sus modificadores que son:
● unsigned: Permite especificar números enteros sin signo, ampliando el rango de
alcance de positivos en los diferentes tipos de datos.
➔ unsigned int 65536;
● signed: Permite que el valor de una variable pueda ser positiva o negativa. Es
utilizado en int de forma implícita.
➔ signed char -1, 1;
● long: Se utiliza para representar números enteros, letras o palabras de 8 bytes.
➔ long int a=64bits;
● short: Se utiliza para representar números enteros, letras o palabras de 2 bytes.
➔ short int a=16bits;
Expresiones.
Una expresión es una fórmula matemática cuya evaluación especifica un valor. Los
elementos que constituyen una expresión son: constantes, variables y operadores.
Constantes
Una constante tiene un valor fijo que no puede ser modificado. C admite dos tipos diferentes
de constantes: literales y simbólicas.
● Lineales: Todo valor que aparece directamente en el código fuente cada vez que es
necesario para una operación constituye una constante literal.
➔ Toda constante que comience por un dígito distinto de 0 es interpretada como
un entero decimal (base 10). Se especifican mediante los dígitos del 0 al 9 y
el signo positivo o negativo.
➔ Si una constante comienza con el dígito 0, se interpreta como un entero octal
(base 8). Se especifican mediante los dígitos del 0 al 7 y el signo positivo o
negativo.
➔ Las constantes que comienzan por 0x o 0X se interpretan como enteros en
base hexadecimal (base 16). Se especifican mediante los dígitos del 0 al 9,
las letras de la A a la F y el signo positivo o negativo.
8
● Simbólicas: Una constante simbólica es una constante representada mediante un
nombre (símbolo) en el programa, se utiliza su nombre simbólico, de la misma forma
que lo haríamos con una variable. Se declara una sola vez, indicando el nombre y el
valor que representa.
El método más habitual para definir constantes en C es la directiva del
preprocesador #define.
#define PI 3.14159
Es decir, el nombre simbólico y a continuación el valor constante que representa.
Variables
Una variable es un objeto donde se guarda un valor, el cual puede ser consultado y
modificado durante la ejecución del programa. La declaración consiste en dar un nombre
significativo a la variable e indicar el tipo de datos a que corresponden los valores que
almacenaría.
Toda variable debe declararse antes de ser usada por primera vez en el programa.
Operadores
● Operadores de asignación: El operador de asignación permite asignar valores a
las variables. Su símbolo es un signo igual =. Este operador asigna a la variable que
está a la izquierda del operador el valor que estáa la derecha.
● Operadores aritméticos: Además de los operadores aritméticos tradicionales C
utiliza otros para realizar tareas específicas:
● Operadores relacionales: Los operadores relacionales se utilizan principalmente
para elaborar condiciones en las sentencias condicionales y repetitivas. Al relacionar
(comparar) dos expresiones mediante uno de estos operadores se obtiene un
resultado lógico, es decir: ‘CIERTO’ o ‘FALSO’.
9
C no dispone de un tipo de datos específico para los valores lógicos o booleanos. En
su lugar, C representa un resultado ‘FALSO’ como el valor numérico entero cero, y
un resultado ‘CIERTO’ como cualquier valor entero diferente de cero.
● Operadores lógicos: Los operadores lógicos se utilizan principalmente en
conjunción con los relacionales para elaborar condiciones complejas en las
sentencias condicionales y repetitivas. En C se representan como and (&& o
conjunción), or (|| o disyunción) y not (! o negación).
Operaciones primitivas.
Enumeración
Consiste en crear una lista de constantes con nombres descriptivos para representar un
conjunto de valores relacionados. Cada valor en la lista de constantes es un elemento de la
enumeración y se le asigna automáticamente un valor entero a partir de 0 (o de 1 si se
especifica explícitamente).
Ejemplo:
enum dias_semana {lunes, martes, miercoles, jueves, viernes, sabado, domingo};
Acumuladores
Es una variable que consiste en sumar o acumular un valor a medida que se procesan
datos. Se inicializa con un valor de inicio (generalmente 0) y se va actualizando a medida
que se van procesando los datos.
Ejemplo:
int lista[ ] = {1, 2, 3, 4, 5};
int n = 5;
int acumulador = 0;
Contadores
Variable utilizada para contar el número de veces que ocurre un evento en un programa. El
contador se inicializa con un valor de inicio (generalmente 0) y se va actualizando cada vez
que ocurre el evento que se desea contar.
Ejemplo:
int lista[ ] = {1, 2, 3, 4, 4, 4, 5};
int n = 7;
int contador = 0;
Estructuras de decisión condicional.
If y else
If evalúa en primer lugar la condición. A continuación, si la expresión se ha evaluado como
cierta, se ejecuta la sentencia o grupo de sentencias. En caso contrario la ejecución del
programa continúa por la siguiente sentencia en orden secuencial.
Si después de If hay un Else y la primera condición es falsa se ejecutarán las sentencias
dentro de else.
10
Ejemplo de If:
if (condición){
sentencia 1;
sentencia 2;
}
Ejemplo de If-Else:
if (condición){
grupo de sentencias 1;
}
else{
grupo de sentencias 2;
}
Switch, case y break
Esta construcción permite especificar múltiples sentencias al estilo if-else-if, pero de manera
más compacta, legible y elegante. Su forma general es la siguiente:
switch (expresión){
case constante 1:
grupo de sentencias 1;
break;
case constante 2:
grupo de sentencias 2;
break;
default:
grupo de sentencias;
break;
}
Switch primero evalúa la expresión, el valor puesto en ésta es comparado con las
constantes en case y tras comprobar que algún case es verdadero realiza las sentencias
dentro del mismo. Dentro de los case solo van constantes, si estas son letras deben ir entre
comillas simples. Default es opcional y sirve para que el programa siga funcionando si la
expresión no se puede validar. Para que case o default no realicen sentencias no deseadas
es necesario un break que corta de manera forzada las sentencias.
Ambas estructuras pueden ser anidadas con otras, es decir, poner una dentro de otra
cumpliendo sentencias diferentes.
Si pones ; estas asignando a la vez. Aunque es válido sintácticamente no es válido.
11
Estructuras de control repetitivas.
While
La sentencia o grupo de sentencias es ejecutada mientras la condición dentro de while sea
verdadera, cuando esta sea falsa la ejecución continuará fuera del bucle while. Para que el
bucle sea falso en algún momento se puede poner un modificador de la variable dentro del
grupo de sentencias.
Ejemplo:
while(condición){
grupo de sentencias;
i++;
}
Do while
Do while sirve mayormente para evaluar una condición. Primero se ejecutan las sentencias
dentro de do y luego se validan con la condición luego de while. Al igual que while, está la
opción de agregar un modificador de la variable dentro de do para que la condición sea
falsa en algún punto.
Ejemplo:
do{
grupo de sentencias;
i++;
}while (condición);
For
La primera parte de la construcción for acostumbra a ser una sentencia de asignación
donde se inicializa alguna variable que controla el número de veces que debe ejecutarse el
cuerpo del bucle. Esta sentencia se ejecuta una sola ocasión, antes de entrar por primera
vez al cuerpo del bucle.
La segunda parte corresponde a la condición que indica cuando finaliza el bucle, de la
misma forma que en las construcciones repetitivas anteriores.
La tercera parte corresponde normalmente a una sentencia de incremento o decremento
sobre la variable de control del bucle. Esta sentencia se ejecuta siempre después de la
ejecución del cuerpo del bucle.
Ejemplo:
for (sentencia inicial ; condición ; incremento/decremento){
grupo de sentencias;
}
Los dos ; siempre tienen que estar para que for pueda ejecutarse.
No siempre es necesario que esten las 3 partes: S.I., C., Inc/Dec para usar for.
En las tres estructuras repetitivas se utilizan bucles donde se desconoce a priori el número
exacto de iteraciones.
12
Unidad III - Variables dimensionadas
❖ Concepto y definición de variables dimensionadas.
❖ Tipos de tablas.
❖ Vectores, matrices y poliedros.
❖ Declaración y operaciones con matrices.
❖ Recorridos.
❖ Fórmulas de acceso a datos.
❖ Aplicación en lenguaje C.
Concepto y definición de:
Variables dimensionadas
Un array o arreglo (matriz o vector) es un conjunto finito y ordenado de elementos
homogéneos. La propiedad “ordenado” significa que el elemento primero, segundo, tercero,
..., enésimo de un array puede ser identificado. Los elementos de un array son
homogéneos, es decir, del mismo tipo de datos. Un array puede estar compuesto de todos
sus elementos de tipo cadena, otro puede tener todos sus elementos de tipo entero, etc.
El tipo más simple de array es el array unidimensional o vector (matriz de una dimensión).
Vectores
Los vectores (también llamados tablas unidimensionales) son estructuras de datos que se
caracterizan por almacenar una colección de datos del mismo tipo referenciados por un
mismo nombre. Se almacenan en posiciones de memoria físicamente contiguas, de tal
modo que la dirección de memoria más alta guarda el primer elemento (0) y la más alta el
último (n)
Ejemplo:
tipo_de_datos nombre_tabla [tamaño];
➔ tipo_de_datos: Se indica el tipo de datos que va a almacenar el vector.
➔ nombre_tabla: Se identifica el vector con un nombre, para referirnos al mismo
usaremos el nombre elegido.
➔ [tamaño]: Es una expresión entera constante que indica la cantidad de elementos
que tendrá el vector. El tamaño además es el índice representa la posición relativa
que ocupa dicho elemento dentro del vector y se especifica mediante una expresión
entera.
Ejemplo:
int contador[10];
int i, j, x;
x = contador[1];
x = contador[i];
x = contador[i *2+j];
13
Matrices
Las matrices (también llamadas tablas bidimensionales) son vectores con dos dimensiones.
El concepto de acceso, inicialización, etc son iguales que los de vectores.
Ejemplo:
tipo_de_datos nombre_tabla [tamaño_dim1 (fila)][tamaño_dim2 (columna)];
Donde tamaño_dim1 y tamaño_dim2 indican, respectivamente, el número de filas y de
columnas que componen la matriz.
Las matrices se almacenan
por fila, se sitúan en lugares
contiguos dentro de la
memoria. Ejemplo: (0,0) (0,1),
(0,2)...
Poliedros
Un array puede ser definido de tres dimensiones, cuatro dimensiones, hasta de
n-dimensiones. Los conceptos de rango de subíndices y número de elementos se pueden
ampliar directamente desde arrays de una y dos dimensiones a estos arrays de orden más
alto. En general, un array de n-dimensiones requiere que los valores de los n subíndices
puedan ser especificadosa fin de identificar un elemento individual del array. Si cada
componente de un array tiene n subíndices, el array se dice que es sólo de n-dimensiones.
14
Recorridos
Se puede acceder a los elementos de un vector para introducir datos (escribir) en él o bien
para visualizar su contenido (leer). A la operación de efectuar una acción general sobre
todos los elementos de un vector se la denomina recorrido del vector. Estas operaciones se
realizan utilizando estructuras repetitivas, cuyas variables de control (por ejemplo, i) se
utilizan como subíndices del vector (por ejemplo, S[ i ]). El incremento del contador del bucle
producirá el tratamiento sucesivo de los elementos del vector.
15
Librerías.
#include <stdio.h>: Librería estandar de C, contiene constantes, declaraciones de
funciones.
#include <conio.h>: Contiene funciones para mejorar el rendimiento de la entrada y salida.
#include <string.h>: Contiene funciones para realizar cadenas de caracteres.
#include <math.h>: Contiene las fórmulas matemáticas comunes.
#include <stdlib.h>: Contiene funciones para obtener caracteres aleatorios.
#include <time.h>: Contiene las funciones para tratamiento y conversión entre formatos de
fecha y hora.
Fórmulas de acceso a datos.
Aunque C no incorpora en su definición operadores para el manejo de cadenas de
caracteres, todo compilador de C proporciona una librería estándar (string.h) con funciones
para facilitar su utilización.
Funciones para realizar cadenas de caracteres se encuentran en la librería <string.h>:
● strlen: Para obtener la longitud de la cadena, sin contar el carácter nulo.
● strcpy: Para copiar una cadena en otra.
● strcmp: Para comparar dos cadenas, etc.
Funciones para obtener caracteres aleatorios se encuentran en la librería <stdlib.h>:
● Srand(time(NULL)): Se necesita <time.h> para que srand pueda empezar a
funcionar ya que necesita un valor inicial.
● Rand( ): Devuelve un caracter de tipo entero.
16
Unidad IV - Subprogramas: Procedimientos y funciones
❖ Concepto de módulos y de subrutinas.
❖ Parámetros: Tipos de parámetros.
❖ Parámetros actuales y formales.
❖ Pasaje de parámetros: Pasaje por valor y por referencia.
❖ Funciones y procedimientos: Prototipo, llamadas y declaraciones, encabezado.
❖ Variables locales y globales.
❖ Utilización de estructuras de control en subprogramas.
Concepto de módulos y de subrutinas.
El problema principal se soluciona por el correspondiente programa o algoritmo principal,
también denominado controlador o conductor y la solución de los subproblemas mediante
subprogramas, conocidos como procedimientos (subrutinas) o funciones. Los
subprogramas, cuando se tratan en lenguaje algorítmico, se denominan también
subalgoritmos.
Puede realizar las mismas acciones que un programa: 1) Aceptar datos, 2) Realizar algunos
cálculos y 3) Devolver resultados. Un subprograma, sin embargo, se utiliza por el programa
para un propósito específico, recibe datos y le devuelve resultados.
Por otro lado, un módulo es un archivo que contiene un conjunto de funciones, clases y
variables relacionadas que se utilizan para organizar y reutilizar el código. Los módulos se
utilizan para dividir el código en partes más pequeñas y manejables, lo que facilita su
mantenimiento y reutilización en diferentes proyectos. Los módulos pueden contener una o
varias funciones, así como otros elementos de código.
Parámetros.
Tipos
Los parámetros pueden ser clasificados como:
● Entradas: Las entradas proporcionan valores desde el programa que llama y que
se utilizan dentro de un procedimiento. En los subprogramas función, las entradas
son los argumentos en el sentido tradicional.
● Salidas: Las salidas producen los resultados del subprograma.Si se utiliza el caso
de una función, éste devuelve un valor calculado por dicha función, mientras que con
procedimientos pueden calcularse cero, una o varias salidas.
● Entradas/salidas: Un solo parámetro se utiliza para mandar argumentos a un
programa y para devolver resultados.
Parámetros actuales
Los parámetros actuales, también conocidos como argumentos, son los valores reales que
se pasan a una función cuando se la llama. Los argumentos son los valores concretos que
se utilizan para reemplazar los parámetros formales en la llamada a la función.
Por ejemplo: En la siguiente definición de función, "3" y "5" son los parámetros formales.
int main(){
suma(3,5);
}
17
Parámetros formales
También conocidos como parámetros de función o parámetros en la declaración de la
función, son nombres de variables utilizados en la definición de una función. Estos nombres
de variables representan los valores que se esperan recibir cuando la función es llamada.
Los parámetros formales actúan como marcadores de posición para los valores que se
pasarán cuando se llame a la función.
Por ejemplo: En la siguiente definición de función, "x" y "y" son los parámetros formales.
int suma(x,y){
resultado = x + y;
return resultado;
}
Pasaje de parámetros.
Existen diferentes métodos para la transmisión o el paso de parámetros a subprogramas.
Es preciso conocer el método adoptado por cada lenguaje, ya que la elección puede afectar
a la semántica del lenguaje. Dicho de otro modo, un mismo programa puede producir
diferentes resultados bajo diferentes sistemas de paso de parámetros.
Por valor
Los valores se proporcionan en el orden de cálculo de resultados. Los parámetros se tratan
como variables locales y los valores iniciales se proporcionan copiando los valores de los
correspondientes argumentos.
Los parámetros formales —locales a la función— reciben como valores iniciales los valores
de los parámetros actuales y con ello se ejecutan las acciones descritas en el subprograma.
No se hace diferencia entre un argumento que es variable, constante o expresión, ya que
sólo importa el valor del argumento.
Por referencia
Una referencia al correspondiente parámetro formal se trata como una referencia a la
posición de memoria, cuya dirección se ha pasado. Entonces una variable pasada como
parámetro real es compartida, es decir, se puede modificar directamente por el
subprograma. El área de almacenamiento (direcciones de memoria) se utiliza para pasar
información de entrada y/o salida en ambas direcciones.
En este método los parámetros son de entrada/salida y los parámetros se denominan
parámetros variables.
En el pasaje por referencia se usan los punteros & para llamar a la dirección de memoria y *
para almacenar direcciones de memoria.
18
Dentro del pasaje por referencia existe la aritmética de puntero, éste puede ser int o float y
lo que cambia es su capacidad para almacenar bytes.
Los arreglos en C son punteros a su primera posición (pasaje por referencia).
Los parámetros valor y parámetros variable se suelen definir en la cabecera del
subprograma.
Funciones y procedimientos.
Matemáticamente una función es una operación que toma uno o más valores llamados
argumentos y produce un valor denominado resultado —valor de la función para los
argumentos dados—. Todos los lenguajes de programación tienen funciones incorporadas,
intrínsecas o internas.
La declaración de una función consta de 3 partes:
● Prototipo: Puede interpretarse como el aviso al compilador para que cuando
encuentre una llamada a dicha función pueda reconocer qué función es y qué
resultado devuelve. Siempre el prototipo va seguido de un ; (punto y coma).
Por ejemplo:
#include <stdio.h>
int nombre_función(int parametro1, int parametro2);
int main(){
}
● Llamada: Es cuando se utiliza dicha función dentro del main. Al tener parámetros
establecidos, se le asigna las variables locales dentro del main y se utiliza la función.
No es necesario utilizar los mismos nombres en las variables de la función y del
main. El número y tipo de parámetros debe coincidir con la declaración y prototipo
de la función. Cuando la función devuelve un dato es necesaria una variable para
recoger el valor devuelto.
Por ejemplo:
#include <stdio.h>
int nombre_función(int parametro1, int parametro2);
int main(){
int p1,p2;
valores_p1_p2 = nombre_función(p1, p2);
}
19
● Encabezado: Consta de dos partes: una línea llamada cabecera donde se
especifica el nombre de la función, el tipo del resultado que devuelve (int, float, char)
y los parámetros que recibe y un conjunto de sentencias encerrado entre llaves
formando el cuerpo de la función.
Por ejemplo:
int nombre_función(int parametro1, int parametro2){
int grupo_de_sentencias;
return(valor);
}
En cambio, un procedimiento o subrutina es un subprograma que ejecuta un proceso
específico. Ningún valor está asociado con el nombre del procedimiento (void). Un
procedimiento se llama escribiendo su nombre para indicar que un procedimiento se va a
usar. Cuando se invoca el procedimiento, los pasos que lo definen se ejecutan y a
continuación se devuelve el control al programa que le llamó. Este tipo de subprograma no
devuelve ningún valor, es decir, no se utiliza el return.
Variables locales y globales.
Una variable local es aquella que está declarada y definida dentro de un subprograma, en el
sentido de que está dentro de ese subprograma y es distinta de las variables con el mismo
nombre declaradas en cualquier parte del programa principal. El significado de una variable
se confina al procedimiento en el que está declarada. Cuando otro subprograma utiliza el
mismo nombre se refiere a una posición diferente en memoria. Se dice que tales variables
son locales al subprograma en el que están declaradas.
Una variable global es aquella que está declarada para el programa o algoritmo principal,
del que dependen todos los subprogramas.
La parte del programa/algoritmo en que una variable se define se conoce como ámbito o
alcance (scope, en inglés).
Los lenguajes que admiten variables locales y globales suelen tener la posibilidad explícita
de definir dichas variables como tales en el cuerpo del programa, o, lo que es lo mismo,
definir su ámbito de actuación, para ello se utilizan las cabeceras de programas y
subprogramas, con lo que se definen los ámbitos. Las variables definidas en un ámbito son
accesibles en el mismo, es decir, en todos los procedimientos internos.
Utilización de estructura de control de subprogramas.
La utilización de estructuras de control en funciones y procedimientos sigue los mismos
principios generales que en cualquier otro contexto de programación. Las estructuras de
control se utilizan para controlar el flujo de ejecución dentro de una función o procedimiento,
permitiendo tomar decisiones o repetir bloques de código según ciertas condiciones.
20
Unidad V - Ordenamiento y búsqueda
❖ Métodos de búsqueda: Búsqueda secuencial (lineal) y búsqueda dicotómica
(binaria).
❖ Métodos de ordenamiento: Métodos cuadráticos y logarítmicos.
❖ Fórmulas de representación de complejidad algorítmica.
❖ Ordenamiento por Bubblesort (Burbuja) y Shell.
❖ Algoritmos fundamentales, recorrido y búsqueda.
Fórmula de representación de complejidad algorítmica.
Se refiere a una expresión matemática utilizada para describir la complejidad temporal o
espacial de un algoritmo en función del tamaño de entrada. Esta fórmula proporciona una
representación general de cómo el tiempo o espacio requerido por el algoritmo varía a
medida que el tamaño del problema aumenta.
Existen diferentes notaciones utilizadas para expresar la complejidad algorítmica, las dos
más comunes son la notación "O grande" (Big O) y la notación "Theta". Ambas notaciones
permiten representar el peor de los casos en términos de complejidad, pero con enfoques
ligeramente diferentes.
La notación "O grande" (Big O) es la más utilizada y representa la cota superior asintótica
del tiempo o espacio requerido por el algoritmo. La fórmula de complejidad algorítmica
utilizando notación "O grande" se ve así:
T(n) = O(f(n))
Donde T(n) representa el tiempo o espacio requerido por el algoritmo para una entrada de
tamaño n, y f(n) es una función que describe cómo crece la complejidad en función del
tamaño de entrada. La notación "O" se utiliza para indicar que la complejidad es menor o
igual que f(n) en términos asintóticos.
La notación "Theta" es otra notación utilizada para describir la complejidad algorítmica, pero
se enfoca en una cota ajustada tanto inferior como superior. La fórmula de complejidad
algorítmica utilizando notación "Theta" se ve así:
T(n) = Θ(f(n))
Donde T(n) representa el tiempo o espacio requerido por el algoritmo para una entrada de
tamaño n, y f(n) es una función que describe cómo crece la complejidad en función del
tamaño de entrada. La notación "Θ" se utiliza para indicar que la complejidad está acotada
tanto superior como inferiormente por f(n) en términos asintóticos.
Algoritmos fundamentales, recorrido y búsqueda.
Los algoritmos fundamentales abarcan tanto los algoritmos de búsqueda como los de
ordenamiento, así como las diferentes técnicas y variantes algorítmicas que se utilizan
dentro de cada método. Estos algoritmos son esenciales en la ciencia de la computación y
se aplican en una amplia gama de problemas y aplicaciones.
21
Métodos de búsqueda.
La búsqueda se refiere a la operación de encontrar la posición de un elemento entre un
conjunto de elementos dados: lista, tabla o fichero. La búsqueda por claves para localizar
registros es, con frecuencia, una de las acciones que mayor consumo de tiempo conlleva
por lo tanto es el modo en que los registros están dispuestos y la elección del modo
utilizado para la búsqueda pueden redundar en una diferencia sustancial en el rendimiento
del programa.
Dentro de la búsqueda existen dos tipos:
● Búsqueda interna: Los registros que se buscan se almacenan en discos o cintas
externas a la memoria de la computadora.
● Ordenación externa: Los registros que se buscan se almacenan por completo
dentro de la memoria de la computadora.
La operación de búsqueda de un elemento N en un conjunto de elementos consiste en:
➔ Determinar si N pertenece al conjunto y, en ese caso, indicar su posición en él.
➔ Determinar si N no pertenece al conjunto.
Búsqueda secuencial (lineal)
Este método es utilizado en los arreglos, se va a realizar una pasada por todo el vector
desde el primer elemento hasta el último.
La búsqueda secuencial no requiere ningún registro por parte del vector y, por consiguiente,
no necesita estar ordenado. El recorrido del vector se realizará normalmente con
estructuras repetitivas.
El método de búsqueda lineal tiene el inconveniente del consumo excesivo de tiempo en la
localización del elemento buscado. Cuando el elemento buscado no se encuentra en el
vector, se verifican o comprueban sus n elementos. En los casos en que el elemento se
encuentra en la lista, el número podrá ser el primero, el último o alguno comprendido entre
ambos.
Búsqueda dicotómica (binaria)
Este método es utilizado en matrices, por esto, los elementos están ordenados en un
determinado espacio de memoria. Con este método se examina primero el elemento central
de la lista, si este es el elemento buscado, entonces la búsqueda ha terminado. En caso
contrario se determina si el elemento buscado está en la primera o la segunda mitad de la
lista y, a continuación, se repite este proceso, utilizando el elemento central de esa sublista.
El proceso de búsqueda debe terminar normalmente conociendo si la búsqueda ha tenido
éxito (se ha encontrado el elemento) o bien no ha tenido éxito (no se ha encontrado el
elemento) y normalmente se deberá devolver la posición del elemento buscado dentro del
vector.
22
Método con éxito (a) y sin éxito (b).
Métodos de ordenamiento.
La clasificación es el proceso de organizar datos en algún orden o secuencia específica, tal
como creciente o decreciente para datos numéricos o alfabéticamente para datos de
caracteres.
Dentro del ordenamiento existen dos tipos:
● Ordenación interna: Clasificación de los valores de un vector según un orden en
memoria central (más rápida).
● Ordenación externa: Clasificación de los registros de un archivo situado en un
soporte externo (menos rápido).
Métodos cuadráticos
Son aquellos algoritmos cuyacomplejidad temporal es del orden cuadrático O(n^2). Esto
significa que el tiempo de ejecución del algoritmo aumenta proporcionalmente al cuadrado
del tamaño de entrada (n). Ejemplos de método cuadrático es el ordenamiento de burbuja
(Bubble Sort), ordenamiento por selección (Selection Sort). Aunque estos métodos son
sencillos de implementar, no son eficientes para grandes conjuntos de datos, ya que su
tiempo de ejecución crece rápidamente.
Métodos logarítmicos
Son algoritmos cuya complejidad temporal es del orden logarítmico O(log n). Estos
algoritmos tienden a ser muy eficientes y se utilizan en diversas áreas, como estructuras de
datos avanzadas y algoritmos de búsqueda. Un ejemplo prominente de un método
logarítmico es el algoritmo de búsqueda binaria (Binary Search), que busca eficientemente
un elemento en una lista ordenada dividiendo repetidamente la lista en mitades y
descartando una mitad en cada paso. La propiedad logarítmica se deriva de la naturaleza
de la búsqueda dividida y la reducción del espacio de búsqueda a la mitad en cada
iteración.
Ordenamiento por Bubblesort (Burbuja).
El algoritmo de clasificación de intercambio o de la burbuja se basa en el principio de
comparar pares de elementos adyacentes e intercambiarlos entre sí hasta que estén todos
ordenados.
23
La acción intercambiar entre sí los valores de dos elementos A[i], A[i+1] es una acción
compuesta que contiene las siguientes acciones, considerando una variable auxiliar AUX.
aux= vec[i];
vec[i] = vec[i+1];
vec[i+1] = aux;
El elemento cuyo valor es mayor sube posición a posición hacia el final de la lista, al igual
que las burbujas de aire en un depósito o botella de agua. Tras realizar un recorrido
completo por todo el vector, el elemento mencionado habrá subido en la lista y ocupará la
última posición. En el segundo recorrido, el segundo elemento llegará a la penúltima, y así
sucesivamente.
Ordenamiento de Shell.
Este método consiste en insertar un elemento en el vector en una parte ya ordenada de
este vector y comenzar de nuevo con los elementos restantes.
El método se basa en comparaciones y desplazamientos sucesivos. El algoritmo de
clasificación de un vector X para N elementos se realiza con un recorrido de todo el vector y
la inserción del elemento correspondiente en el lugar adecuado. El recorrido se realiza
desde el segundo elemento al n-ésimo.
aux = vec[i];
P = vec[0]; //primero
U = vec[i-1]; //ultimo
C = (P+U)/2;
if(aux < C){
U = C - 1;
}
else{
P = C + 1;
}
Mientras que el primero sea menor o igual al último, vamos a hacer una variable nueva (C,
cambio )que sume P+U y los divida entre dos. Lo que va a pasar es que si aux en menor a
C, U va a convertirse en C-1 y si no P va a ser igual a C+1.
24
Unidad VI - Tipos de datos estructurados
❖ Concepto de estructura de datos.
❖ Declaración.
❖ Implementación, usos y operaciones que se pueden realizar.
❖ Anidamientos de estructuras.
❖ Variables dimensionadas con estructuras de datos.
❖ Formas de acceso.
Concepto de estructura de datos.
Dentro de la programación existen datos estáticos como int, char, float, arrays y los datos
dinámicos donde entran las estructuras de datos.
Las estructuras dinámicas de datos son estructuras que «crecen a medida que se ejecuta
un programa». Una estructura dinámica de datos es una colección de elementos —llamados
nodos— que son normalmente registros. Al contrario que un array, que contiene espacio
para almacenar un número fijo de elementos, una estructura dinámica de datos se amplía y
contrae durante la ejecución del programa, basada en los registros de almacenamiento de
datos del programa.
Pueden considerarse una cajita donde se agrupa datos de diferentes tipos, la estructura no
ocupa lugar de memoria y en sí pero si los datos de adentro.
Las estructuras son tipos de datos heterogéneos.
“Una estructura es una colección de elementos finita y heterogénea.”
Declaración.
La declaración de una estructura se realiza fuera del main o de alguna función.
Se definen utilizando la palabra reservada `struct` seguida del nombre de la estructura y la
lista de campos que la componen. Cada variable dentro de una estructura es llamada
campo o miembro.
Por ejemplo:
struct Persona {
char nombre[50];
int edad;
float estatura;
};
Es muy importante el ; al final de la declaración de este tipo de dato, struct puede almacenar
variables de diferentes tipos.
25
Formas de acceso.
1. Acceso directo: Puedes acceder a los miembros de una estructura utilizando el operador
de punto (`.`). Por ejemplo:
scanf(“%d”, &persona.Persona;
2. Acceso a través de otros punteros:
Si mandamos los datos a través de un &, en vez del punto se debe utilizar * pero si quiero
usar el punto si o si se hace de la siguiente manera:
scanf(“%d”, &persona.(*valores);
El puntero -> se utiliza en el caso de querer acceder a un miembro dentro de la estructura,
combina el . y el *. Por ejemplo:
scanf(“%d”, &persona->valores);
Implementación, usos y operaciones que se pueden realizar.
Los usos que se le suelen dar a las estructuras son:
➔ Organizar datos relacionados.
➔ Pasar datos a funciones.
➔ Almacenar registros de datos.
Las operaciones que se pueden realizar con estructuras son las básicas, ordenamiento y
búsqueda, acceso y modificación de miembros, asignación y comparación de distintas
estructuras.
Variables dimensionadas con estructuras de datos.
Dentro de las estructuras se pueden poner arreglos y matrices.
Por ejemplo:
Para llamar a la estructura y al arreglo que sería la variable hay que poner la declaración de
la siguiente forma:
struct Persona {
char nombre[50];
int edad;
float estatura;
};
int main(){
struct Persona agenda[30];
scanf(“%f”, &agenda[i].edad);
}
26
Anidamientos de estructuras.
Las estructuras anidadas se presentan cuando en la declaración de una estructura, por lo
menos uno de sus componentes es una estructura.
Por ejemplo:
Para llamar a esta estructura dentro del main se deben utilizar punteros de la siguiente
forma:
#include <stdio.h>
struct EstructuraInterior {
int dato1;
char dato2;
};
struct EstructuraExterior {
struct EstructuraInterior datosInteriores;
float dato3;
};
int main() {
struct EstructuraExterior datos;
printf("Ingrese el dato1: ");
scanf("%d", &(datos.datosInteriores.dato1));
printf("Ingrese el dato2: ");
scanf(" %c", &(datos.datosInteriores.dato2));
printf("Ingrese el dato3: ");
scanf("%f", &(datos.dato3));
return 0;
}
27