Ingeniero

Apuntes para el curso de
“Estructuras de datos en C/C++ ”
Dr. Abdiel E. C´aceres Gonz´alez
ITESM-CCM
2 de junio de 2005
Resumen
Una estructura de datos es una manera de almacenar y organizar datos para facilitar
el acceso y modificaciones. No hay una estructura de datos que sirva para todos los
prop´ositos, y por eso es importante saber sus ventajas y desventajas. Este documento
es unacolecci´on de apuntes para el curso de Estructuras de Datos. Los apuntes
se han tomado de algunas fuentes que son detalladas en la secci´on de bibliograf´ıa.
´Indice
1. Preliminares de programaci´on en C/C++ 3
1.1. Arreglos 3
1.2. Apuntadores 10
1.3. Estructuras C/C++ 15
1.4. Ejercicios de programaci´on 19
2. La pila 21
2.1. Definici´on y ejemplos 21
2.2. Operaciones b´asicas 24
2.3.Ejemplo: N´umero de par´entesis 25
2.4. La estructura de datos Pila en C/C++ 26
2.5. La representaci´on en C/C++ de las operaciones de una pila 27
2.6. Problemas de programaci´on 29
1
3. Colas 31
3.1. Estructura de las colas en C/C++ 32
3.2. Colas con prioridad 33
3.3. Ejercicio de programaci´on 34
4. Recursi´on 36
4.1. Peligros en la recursividad 39
4.2. Ejercicios de programaci´on 40
5.Listas 42
5.1. Grafos 42
5.2. Listas simplemente encadenadas 44
5.3. El uso de memoria din´amica en C/C++ 51
5.4. Listas ligadas usando memoria din´amica 54
5.5. Ejercicios de programaci´on 56
6. ´Arboles 57
6.1. Concepto general de ´arbol 57
6.2. ´Arboles binarios 57
6.3. Representaci´on en C/C++ de los ´arboles binarios 64
6.4. ´Arboles 66
6.5. Ejercicios de programaci´on 69
7.Grafos 71
7.1. Recordatorio de las definiciones 71
7.2. Aplicaci´on ejemplo 73
2
1. Preliminares de programaci´on en C/C++
En esta secci´on recordaremos tres temas de programaci´on en C/C++ que son
fundamentales para estudiar estructuras de datos; estos temas son los arreglos,
los registros y los punteros. Los tres temas han sido tomados fundamentalmente
de [MP97]
1.1. Arreglos
Definici´on 1Un arreglo se compone de elementos de igual tama˜no almacenados
linealmente en posiciones de memoria consecutiva.
Se puede acceder a cada elemento de datos individual utilizando un sub´ındice,
o ´ındice, para seleccionar uno de los elementos. En C/C++ , un arreglo no es
un tipo de datos est´andar; es un tipo agregado compuesto de cualquier otro
tipo de datos.
Los arreglos se pueden definirusando tipos de datos mixtos debido a que se
supone que todos los elementos son del mismo tama˜no. Puesto que todos los
elementos son del mismo tama˜no y ya que este hecho se utiliza para ayudar
a determinar c´omo localizar un elemento dado, resulta que los elementos son
almacenados en localidades de memoria contiguas.
Lo m´as importante a tener en cuenta es: El nombre de un arreglo es vistopor el
compilador como un puntero-constante al primer elemento del arreglo. Esto es
muy importante: a) El nombre del arreglo es visto como un tipo puntero, y m´as
espec´ıficamente, b) un puntero constante -significa una direcci´on de memoria
bloqueada para el primer elemento de un arreglo-. Por ejemplo, aunque una
declaraci´on de arreglo toma la f´orma gen´erica:
Tipo_ElementoArrayNombreArray [ NumeroDeElementos ]
El compilador ve la declaraci´on como
Tipo_ElementoArray * const NombreArray = &NombreArray[0];
Por esta raz´on, un identificador de arreglo no puede ser usado nunca como un
valor-i (valor izquierdo). Los valores izquierdos representan variables que su
contenido puede ser alterado por el programa; frecuentemente aparecen a la
izquierda de las sentencias deasignaci´on.
Si los nombres de arreglo fueran variables izquierdos permitidos, el programa
podr´ıa cambiar sus contenidos.
3
float SalariosDeEmpleados[Max_empleados];
.
.
.
SalariosDeEmpleados = 45739.0;
El efecto har´ıa cambiar la direcci´on inicial del propio arreglo.
1.1.1. Declaraciones de un arreglo
La sintaxis de declaraci´on de arreglos es:
tipo nombre_arreglo [numero_de_elementos];...