• Author / Uploaded
• Jeymis P. De la Cruz Palacios

Citation preview

ALGORÍTMIA Y ESTRUCTURA DE DATOS

Carol Roxana Rojas Moreno

Cada autor es responsable del contenido de su propio texto. De esta edición: © Universidad Continental S.A.C 2012 Jr. Junin 355, Miraflores, Lima-18 Teléfono: 213 2760 Derechos reservados Primera Edición: Noviembre 2013 Tiraje: 500 ejemplares Autor: Carol Roxana Rojas Moreno Oficina de Producción de Contenidos y Recursos Impreso en el Perú - Rebelars S.A.C Jr. Los Bosques 555 - El Tambo - Huancayo Fondo Editorial de la Universidad Continental

Todos los derechos reservados. Esta publicación no puede ser reproducida, en todo ni en parte, ni registrada en o trasmitida por un sistema de recuperación de información, en ninguna forma ni por ningún medio sea mecánico, fotoquímico, electrónico, magnético, electroóptico, por fotocopia, o cualquier otro sin el permiso previo por escrito de la Universidad.

INTRODUCCIÓN

9

DIAGRAMA DE PRESENTACIÓN DE LA ASIGNATURA

11

UNIDAD I: ALGORITMOS Y PROGRAMACIÓN ESTRUCTURADA

13

DIAGRAMA DE PRESENTACIÓN DE LA UNIDAD i Tema N° 1: Algoritmo 1 Definición del algoritmo

14

2 Características de un algoritmo

17

3 Instrucciones algorítmicas básicas

17

4 Representación del algoritmo

18

Tema N° 2: Programación Estructurada  1 Programa

26

2 Lenguaje de programación

27

3 Programas traductores

28

4 Definición programación estructurada

29

Tema N° 3: Sentencias Básicas de Programación 1 Estructura básica secuencial

31

2 Estructura básica selectiva

31

3 Estructura básica repetitiva

32

ACTIVIDAD N°1

34

Tema N° 4: Modularización de Programas 1 Definición de módulos de programa

34

2 Paso de Parámetros

34

3 Procedimientos

35

4 Funciones

36

5 Librerías de programación creadas por el usuario

40

Tema N° 5: Funciones Recursivas  1 Definición de recursividad

42

2 Recursividad de factorial

43

3 Recursividad de la multiplicación

43

4 Recursividad de torres de hanoi

43

ACTIVIDAD N°2

44

Lectura seleccionada N°1

45

GLOSARIO de la unidad i

46

BIBLIOGRAFÍA DE LA UNIDAD I

47

Autoevaluación DE LA UNIDAD i

47

UNIDAD II: ESTRUCTURA DE DATOS ESTÁTICAS

51

DIAGRAMA DE PRESENTACIÓN DE LA UNIDAD ii TEMA 1: Estructuras de Datos 1 Definición de estructura de datos

52

2 Clasificación de estructura de datos

52

Tema N° 2: Arreglos Unidimensionales 1 Definición de arreglos unidimensionales

53

2 Algoritmos de actualización

54

3 Búsqueda de arreglos unidimensionales

57

4

59

Ordenación de arreglos unidimensionales

ACTIVIDAD N°1

60

Tema N° 3: Arreglos Bidimensionales 1 Definición de arreglos bidimensionales

61

2

63

Algoritmos de actualización de arreglos bidimensionales

ACTIVIDAD N°2

65

Lectura seleccionada n° 1

65

GLOSARIO de la unidad ii

67

Bibliografía de la unidad ii

67

Autoevaluación de la unidad ii

67

UNIDAD III: ESTRUCTURAS DE DATOS DINÁMICA LINEAL

71

DIAGRAMA DE PRESENTACIÓN DE LA UNIDAD iii Tema N° 1: Registro (Estructura) y Unión 1 Definición de registro (estructura)

72

2 Módulos y estructuras

74

3 Invocación de una estructura en otra

75

4 Definición de unión: ejemplo práctico

76

Tema N° 2: Tipos de Datos Abstractos (TDA)  1 Definición de TDA 2 Clases y programación orientada a objetos

77 78

Tema N° 3: Puntero a Dirección de Memoria  1 Definición de puntero a dirección de memoria

80

2 Creación y eliminación de variables dinámicas

82

ACTIVIDAD N°1

83

Tema N° 4: Estructuras de Datos Dinámicas Lineal 1 Listas enlazadas: simple, doble, circular

84

2 Colas y pilas

90

ACTIVIDAD N°2

95

Lecturas seleccionada n° 1

95

GLOSARIO de la unidad iii

97

Bibliografía de la unidad iii

97

Autoevaluación de la unidad iii

97

UNIDAD IV: ESTRUCTURAS DE DATOS DINÁMICA NO LINEAL

101

DIAGRAMA DE PRESENTACIÓN DE LA UNIDAD iv Tema N° 1: Árbol y Grafo 1 Árbol General: Conceptos básicos y algoritmos de manipulación

102

2 Árbol binario: recorridos: preorden, inorden, postorden

106

3 Árboles binarios de búsqueda ( abb )

107

4 Grafos: Conceptos y algoritmos de manipulación

111

ACTIVIDAD N°1

118

Tema N° 2: Archivo (Fichero) 1 Archivo: conceptos y algoritmos de manipulación

119

ACTIVIDAD N°2

121

Lecturas seleccionada n° 1

122

GLOSARIO de la unidad iv

123

Bibliografía Y DIRECCIONES ELECTRÓNICAS

123

Autoevaluación de la unidad iv

124

ANEXO Clave de respuesta de Autoevaluaciones

127

INTRODUCCIÓN

A

lgoritmia y Estructura de Datos es una asignatura que

cas: Sentencias Básicas de Programación: Secuenciales, Selecti-

se desarrolla con una modalidad de educación virtual,

vas y Repetitivas y la Modularización en la Programación Estruc-

y el presente manual autoformativo es su material di-

turada, es decir, se puede dividir a un programa complejo, en

dáctico más importante.

segmentos de programa mas simples (Modularización), y poder ser reutilizados en otros programas, a través del uso de funcio-

Esta asignatura tiene como finalidad proporcionar al estudiante, los conocimientos necesarios en las técnicas y estructuras de datos para iniciarse en la programación asistida por un computador y basado en el enfoque estructurado, requeridos en su formación básica para poder desarrollar programas en otros niveles más avanzados.

nes y procedimientos, y en algunos casos usando el concepto de recursividad. Unidad II: Estructuras de Datos Estáticas, presentando los algoritmos de creación y actualización de Arreglos Unidimensionales y Bidimensionales, Unidad III: Estructuras de Datos Dinámica Lineal, donde se expone las formas de almacenamiento temporal de datos a través estructuras listas, pilas, cola. Unidad IV: Estructuras de Datos Dinámica No Lineal, en esta última unidad, se exponen otras formas de almacenamien-

La competencia a desarrollar es: Construye algoritmos en un

to de datos como árboles, grafos, archivos.

lenguaje de programación, utilizando las sentencias básicas de programación, diferenciando su uso para la propuesta de solución de un problema, y con ello construye programas computacionales utilizando módulos de programa (funciones y procedi-

Para el estudio del manual y la ejecución de las actividades, se recomienda para cada unidad:

mientos), valorando la reutilización de los módulo, y utilizando

• Realizar el estudio de los contenidos. Esta lectura será ana-

las diferentes estructuras de datos: estáticas y dinámicas para

lítica y reflexiva subrayando, resumiendo y asimilando la in-

almacenar datos temporalmente, diferenciando el uso de las

formación.

estructuras con respecto al uso de los archivos como almacenamiento de datos permanente, promoviendo el interés por otras técnicas de almacenamiento.

• Pasar al estudio de las lecturas seleccionadas, que son de estudio de profundización o ampliación. • Desarrollar las actividades programadas para cada semana en el aula virtual y asistidas por un lenguaje de programa-

El presente material consta de cuatro unidades: Unidad I: Algoritmos y Programación Estructurada, que presenta conceptos, representaciones y programación del algoritmo, con sus técni-

ción, con la asesoría del Profesor Tutor. • Desarrollar la auto evaluación, que es una preparación para la prueba final de la asignatura. .

8

Desarrollo de contenidos

PRESENTACIÓN DE LA ASIGNATURA Diagrama

Objetivos

Lecturas seleccionadas

Glosario

Recordatorio

Anotaciones

Inicio

COMPETENCIA DE LA ASIGNATURA

Desarrollo Construye de contenidos

Actividades enAutoevaluación algoritmos un lenguaje de programación, utilizando las sentencias básicas de programación, diferenciando su uso para la propuesta de solución de un problema, y con ello construye programas computacionales utilizando módulos de programa (funciones y procedimientos), valorando la reutilización de los módulo, y utilizando las diferentes estructuras de datos: estáticas y dinámicas para almacenar datos temporalmente, diferenciando el uso de las estructuras con respecto al uso de los archivos como almacenamiento Lecturas Glosario Bibliografía de datos permanente, promoviendo el interés seleccionadas por otras técnicas de almacenamiento.

UNIDADES Recordatorio DIDÁCTICAS Anotaciones UNIDAD I

UNIDAD II

UNIDAD III

UNIDAD IV

“Algoritmos y Programación Estructurada”

“Estructuras de Datos Estáticas”

“Estructuras de Datos Dinámica Lineal”

“Estructuras de Datos Dinámica No Lineal”

UNIDAD III

UNIDAD IV

TIEMPO MÍNIMO DE ESTUDIO UNIDAD I

UNIDAD II

1ª y 2ª semana

3ª y 4ª semana

5ª y 6ª semana

7ª y 8ª semana

16 horas

16 horas

16 horas

16 horas

ALGORÍTMIA Y ESTRUCTURA DE DATOS Actividades Autoevaluación MANUAL AUTOFORMATIVO

Bibliografía

9

10

Desarrollo de contenidos

Diagrama

Desarrollo de contenidos

Diagrama Lecturas seleccionadas

Objetivos

Inicio

Actividades

Glosario

Recordatorio

Anotaciones

Autoevaluación

DIAGRAMA DE PRESENTACIÓN DE LA UNIDAD Objetivos Glosario

Inicio Bibliografía

LECTURAS SELECCIONADAS

Actividades

ACTIVIDADES

Autoevaluación

Anotaciones

AUTOEVALUACIÓN Lecturas seleccionadas

Lecturas seleccionadas

UNIDAD I: ALGORITMOS Y PROGRAMACIÓN ESTRUCTURADA

CONTENIDOS Desarrollo de contenidos Recordatorio

Glosario

BIBLIOGRAFÍA

Bibliografía

ORGANIZACIÒN DE LOS APRENDIZAJES Recordatorio

ALGORÍTMIA Y ESTRUCTURA DE DATOS Actividades Autoevaluación MANUAL AUTOFORMATIVO

Anotaciones

CONOCIMIENTOS

PROCEDIMIENTOS

ACTITUDES

Tema N° 1: Algoritmo 1. Definición del Algoritmo 2. Características de un algoritmo 3. Instrucciones Algorítmicas Básicas 4. Representación del Algoritmo

1. Analiza diferentes situaciones problema para proponer un algoritmo computacional como solución

1. Asume con responsabilidad sus actividades académicas asignadas

2. Aplica el flujo de trabajo de la sentencia de programación secuencial

2. Realiza con honestidad las evaluaciones asignadas

Tema N° 2: Programación Estructurada 1. Programa 2. Lenguaje de Programación 3. Programas Traductores 4. Definición Programación Estructurada Tema Nº 3: Sentencias Básicas de Programación 1. Estructura Básica Simple o Secuencial 2. Estructura Básica Selectiva 3. Estructura Básica Repetitiva Tema Nº 4: Modularización de Programas 1. Definición de Módulos de Programa 2. Paso de Parámetros 3. Procedimientos 4. Funciones 5. Librerías de Programación creadas por el usuario Lectura seleccionada N° 1 Introducción a los Subalgoritmos o Subprogramas – Luis Joyanes Aguilar Tema Nº 5: Funciones Recursivas 1. Definición de Recursividad 2. Recursividad del Factorial 3. Recursividad de la Multiplicación 4. Recursividad de Torres de Hanoi Autoevaluación de la Unidad I

3. Aplica las sentencias de programación selectiva en la construcción de un algoritmo como solución de un problema 4. Aplica las sentencias de programación repetitiva en la construcción de un algoritmo como solución de un problema 5. Aplica los conceptos de la modularización a través de las Funciones, Procedimientos 6. Construye Librerías de Programación, para la reutilización de módulos en los programas 7. Aplica algoritmos recursivos en la construcción de programas Actividad N° 1 Elaboración de Algoritmos y programas usando las sentencias básicas de programación Actividad N° 2 Elaboración de programas usando módulos y librerías de programas, y elaboración de algoritmos recursivos Control de Lectura Nº 1 Sentencias de Programación en los Algoritmos y Módulos de Programa

Bibliografía

11

12

ollo nidos

Actividades

Autoevaluación

as nadas

Glosario

Bibliografía

torio

Anotaciones

UNIDAD I: ALGORITMOS Y PROGRAMACIÓN ESTRUCTURADA

TEMA N° 1: ALGORITMO 1 DEFINICIÓN DE ALGORITMO ¿En su quehacer diario, realiza sus actividades generalmente en un orden, organizado, finaliza y realiza otro conjunto de actividades de similar manera? Entonces quiere decir que está realizando un algoritmo, y en este caso, al desarrollarlo sin ayuda de un computador, se trata de un algoritmo no computacional. La definición de “Algoritmo” es precisamente como Ud. pensó que desarrolla sus actividades diarias, es decir: “Un algoritmo es un conjunto ordenado y finito de actividades, que generalmente, conducen a la solución de un problema”.

La palabra algoritmo se deriva de la traducción al latín del nombre árabe Al-Khuwarizmi, matemático y astrónomo árabe que escribió un tratado sobre manipulación de números y ecuaciones en el siglo IX. (Angela Carrasco Loli. Principios de Programación)

Tenemos algunos ejemplos de algoritmo: - Al instalar un equipo de sonido, ejecutamos las instrucciones (algoritmo) contenidas en el manual del equipo. - El algoritmo matemático de Euclides para la obtención del máximo común divisor de dos números. Algunos algoritmos pueden ser ejecutados con ayuda de una computadora, a esto le llamamos algoritmo computacional, donde las actividades desarrolladas se llaman instrucciones y se expresan en un lenguaje de programación. (Términos que se explican mas adelante). Todo algoritmo puede ser descompuesto en tres partes, como se muestra en la siguiente figura: E: Entrada de datos. P: Proceso. S: Salida de resultados. Figura Nro 1: Partes de un algoritmo 2 CARACTERÍSTICAS DE UN ALGORITMO

• Un algoritmo debe ser preciso e indicar el orden de realización de cada paso. • Un algoritmo debe ser definido. El algoritmo dos veces, se debe obtener el mismo resultado cada vez. • Un algoritmo debe ser finito: Si se sigue use debe terminar en algún momento, o sea, debe tener un número finito de pasos. (Luis Joyanes Aguilar. Fundamentos de Programación.)

Para que pueda escribir las instrucciones algorítmicas, necesita conocer lo que es una Variable: Es una localización o casillero en la memoria principal que almacena un valor que puede cambiar en el transcurso de la ejecución del programa. Tiene un nombre, un tipo de dato y un valor. Antes de poder utilizar una variable es necesario declararla especificando su nombre y su tipo de dato.

Desarrollo UNIDAD I: ALGORITMOS Y PROGRAMACIÓN ESTRUCTURADA de contenidos

Ejemplo 1: Entero edad

ALGORÍTMIA Y ESTRUCTURA DE DATOS Actividades Autoevaluación MANUAL AUTOFORMATIVO

Lecturas seleccionadas

Glosario

Recordatorio

Anotaciones

Ejemplo 2: Real peso, talla 3 INSTRUCCIONES ALGORÍTMICAS BÁSICAS a. Entrada: Consiste en obtener un dato de un dispositivo de entrada, como el teclado el lector óptico, etc., y almacenarlo en una variable, y se expresa en el pseudocódigo mediante la palabra LEER, de la siguiente forma: Ejemplo: LEER variable LEER edad • En lenguaje C/C++: cin>>edad; b. Salida: Consiste en mostrar el valor de una variable en un dispositivo de salida, como la pantalla del computador, se expresa en el pseudocódigo mediante la palabra ESCRIBIR,de la siguiente forma: Ejemplo: ESCRIBIR variable ESCRIBIR TotalCompra • En lenguaje C/C++: cout