PDF de programación - Estructura de Datos I - Manual del docente

ESTRUCTURA DE DATOS I MANUAL DEL DOCENTE









MANUAL DEL DOCENTE

ESTRUCTURA DE DATOS I

Objetivo de la
unidad
Introducción a la
asignatura
Desglose de
temas
Glosario
















SUBSECRETARÍA DE EDUCACIÓN SUPERIOR E INVESTIGACIÓN CIENTÍFICA

SECRETARÍA DE EDUCACIÓN PÚBLICA

SUBSISTEMA DE UNIVERSIDADES TECNOLÓGICAS

COORDINACIÓN GENERAL DE UNIVERSIDADES TECNOLÓGICAS

UNIVERSIDAD TECNOLÓGICA DE IZÚCAR DE MATAMOROS





ELABORÓ:

LIC. IVAN ANTONIO FLORES
TRUJILLO
LIC. ALEJANDRO SALVADOR
VARGAS


REVISÓ:

CUERPO COLEGIADO TIC-SI

APROBÓ:

CUERPO COLEGIADO TIC-SI

FECHA DE ENTRADA
EN VIGOR:

SEPTIEMBRE 2004














ESTRUCTURA DE DATOS I MANUAL DEL DOCENTE



I. DIRECTORIO







Dr. Reyes Taméz Guerra
Secretario de Educación Pública
Dr. Julio Rubio Oca
Subsecretario de Educación Superior e Investigación Científica
DR. Arturo Nava Jaimes
Coordinador General de Universidades Tecnológicas
Reconocimientos
Universidad Tecnológica Izúcar de Matamoros
División de TIC-SI




Estructuras de Datos D.R.  2005



ESTA OBRA, SUS CARACTERÍSTICAS Y DERECHOS SON PROPIEDAD DE LA: COORDINACIÓN

GENERAL DE UNIVERSIDADES TECNOLÓGICAS (CGUT) FRANCISCO PETRARCA No. 321, COL.

CHAPULTEPEC MORALES, MÉXICO D.F. LOS DERECHOS DE PUBLICACIÓN PERTENECEN A LA CGUT.

QUEDA PROHIBIDA SU REPRODUCCIÓN PARCIAL O TOTAL POR CUALQUIER MEDIO, SIN

AUTORIZACIÓN PREVIA Y POR ESCRITO DEL TITULAR DE LOS DERECHOS.



ISBN (EN TRÁMITE)

IMPRESO EN MÉXICO.

Estructura de Datos. UTIM

ESTRUCTURA DE DATOS I MANUAL DEL DOCENTE





ÍNDICE


Preámbulo…………………………………………………………………………………………………………5

1. Antecedentes……………………………………………………………………………9.

1.1. Introducción a la orientación a objetos……………………………………………9
1.2. Tipos de datos abstractos…………………………………………………………...11
1.3. Definición de estructuras de datos………………………………………………….14
1.4. Acceso directo y Secuencial a los datos………………………………… 16
1.5. Iteradores……………………………………………………………………………………………… 16
1.6. Apuntadores o punteros…………………………………………………………...16
1.7. Plantillas (Templates)……………………………………………………………..34
1.8. La biblioteca STL…………………………………………………………………38

2. Arreglos………………………………………………………………………………..34

2.1. Introducción…..…………………………………………………………………...34
2.2. Arreglos dinámicos………………………………………………………………..36
2.3. La clase VECTOR………………………………………………………………...36

3. Listas…………………………………………………………………………………...44

3.1. Definición de lista…………………………………………………………………44
3.2. Operaciones básicas con listas…………………………………………………….45

3.2.1. Insertar un elemento en la lista……………………………………………..45
3.2.2. Localizar un elemento en la lista…………………………………………...47
3.2.3. Eliminar elementos de la lista……………………………………………...48
3.2.4. Moverse a través de una lista………………………………………………50
3.2.5. Borrar una lista completa…………………………………………………..50
3.2.6. Ejemplo de lista Ordenada………………………………………………....50
3.2.7. Ejemplo de lista en C++ usando clases…………………………………….53

3.3. La clase LIST de STL……………………………………………………………..54

4. Pilas…………………………………………………………………………………….58

4.1. Definición de pilas……………………………………………………………...…58
4.2. Operaciones básicas con pilas……………………………………………………..59

4.2.1. Push, insertar elemento…………………………………………………….59
4.2.2. Pop, leer y eliminar un elemento…………………………………………...60

4.3. Implementación de pilas…………………………………………………………..60

4.3.1. Ejemplo de pilas en C++ usando clases……………………………………61

4.4. La clase STACK de STL………………………………………………………….62

5. Colas…...………………………………………………………………………………65

5.1. Definición de colas………………………………………………………………..65
5.2. Operaciones básicas con colas…………………………………………………….66

5.2.1. Añadir un elemento………………………………………………………...66
5.2.2. Leer un elemento…………………………………………………………..67
5.3. Implementación de colas………………………………………………………….69

5.3.1. Ejemplo de una cola en C++ usando clases………………………………..70

5.4. La clase QUEUE de STL………………………………………………………….71

6. Árboles…….…………………………………………………………………………..73

6.1. Definición de árboles……………………………………………………………...73

Estructura de Datos. UTIM



ESTRUCTURA DE DATOS I MANUAL DEL DOCENTE

6.2. Árboles binarios…………………………………………………………………...75
6.3. Árboles de Búsqueda binaria……………………………………………………...76
6.3.1. Operaciones en ABB. ……………………………………………………..76

6.3.1.1. Buscar un elemento…………………………………………………77
6.3.1.2.
Insertar un elemento………………………………………………...77
6.3.1.3. Eliminar un elemento……………………………………………….78

6.3.2. Ejemplos de eliminación en un ABB………………………………………79

6.4. Aplicaciones de árboles…………………………………………………………...81

Bibliografía……………………………...…………………………………...……………82

Estructura de Datos. UTIM



ESTRUCTURA DE DATOS I MANUAL DEL DOCENTE

Preámbulo.

Resumidamente, el ANSI define un conjunto de reglas. Cualquier compilador de C
o de C++ debe cumplir esas reglas, si no, no puede considerarse un compilador de
C o C++. Estas reglas definen las características de un compilador en cuanto a
palabras reservadas del lenguaje, comportamiento de los elementos que lo
componen, funciones externas que se incluyen, etc. Un programa escrito en ANSI
C o en ANSI C++, podrá compilarse con cualquier compilador que cumpla la
norma ANSI. Se puede considerar como una homologación o etiqueta de calidad
de un compilador.

Todos los compiladores incluyen, además del ANSI, ciertas características no
ANSI, por ejemplo librerías para gráficos. Pero mientras no usemos ninguna de
esas características, sabremos que nuestros programas son transportables, es
decir, que podrán ejecutarse en cualquier ordenador y con cualquier sistema
operativo.

Este curso es sobre C++, con respecto a las diferencias entre C y C++, habría
mucho que hablar, pero no es este el momento adecuado. Pero para comprender
muchas de estas diferencias necesitarás cierto nivel de conocimientos de C++.

Probablemente este es el lugar más adecuado para explicar cómo se obtiene un
fichero ejecutable a partir de un programa C++.

Para empezar necesitamos un poco de vocabulario técnico. Veremos algunos
conceptos que se manejan frecuentemente en cualquier curso de programación y
sobre todo en manuales de C y C++.

Archivos fuente y programa o código fuente:

Los programas C y C++ se escriben con la ayuda de un editor de textos del mismo
modo que cualquier texto corriente. Los ficheros que contiene programas en C o
C++ en forma de texto se conocen como ficheros fuente, y el texto del programa
que contiene se conoce como programa fuente. Nosotros siempre escribiremos
programas fuente y los guardaremos en ficheros fuente.

Archivos objeto, código objeto y compiladores:

Los programas fuente no pueden ejecutarse. Son ficheros de texto, pensados para
que
los
ordenadores.

los seres humanos, pero

los comprendan

incomprensibles para

Para conseguir un programa ejecutable hay que seguir algunos pasos. El primero
es compilar o traducir el programa fuente a su código objeto equivalente. Este es
el trabajo que hacen los compiladores de C y C++. Consiste en obtener un fichero

Estructura de Datos. UTIM



ESTRUCTURA DE DATOS I MANUAL DEL DOCENTE

equivalente a nuestro programa fuente comprensible para el ordenador, este
fichero se conoce como fichero objeto, y su contenido como código objeto.

Los compiladores son programas que leen un fichero de texto que contiene el
programa fuente y generan un fichero que contiene el código objeto.

El código objeto no tiene ningún significado para los seres humanos, al menos no
directamente. Además es diferente para cada ordenador y para cada sistema
operativo. Por lo tanto existen diferentes compiladores para diferentes sistemas
operativos y para cada tipo de ordenador.

Librerías:

Junto con los compiladores de C y C++, se incluyen ciertos ficheros llamados
librerías. Las librerías contienen el código objeto de muchos programas que
permiten hacer cosas comunes, como leer el teclado, escribir en la pantalla,
manejar números, realizar funciones matemáticas, etc. Las librerías están
clasificadas por el tipo de trabajos que hacen, hay librerías de entrada y salida,
matemáticas, de manejo de memoria, de manejo de textos, etc.

Hay un conjunto de librerías muy especiales, que se incluyen con todos los
compiladores de C y de C++. Son las librerías ANSI o estándar. Pero también hay
librerías no estándar, y dentro de estas las hay públicas y comerciales. En este
curso sólo usaremos librerías ANSI.

Archivos ejecutables y enlazadores:

Cuando obtenemos el fichero objeto, aún no hemos terminado el proceso. El
fichero objeto, a pesar de ser comprensible para el ordenador, no puede ser
ejecutado. Hay varias razones para eso:

1.

2.

3.

Nuestros programas usaran, en general, funciones que estarán incluidas en
librerías externas, ya sean ANSI o no. Es necesario combinar nuestro fichero
objeto con esas librerías para obtener un ejecutable.

Muy a menudo, nuestros programas estarán compuestos por varios ficheros
fuente, y de cada uno de ellos se obtendrá un fichero objeto. Es necesario unir
todos los ficheros objeto, más las librerías en un único fichero ejecutable.

Hay que dar ciertas instrucciones al ordenador para que cargue en memoria
e