Estructura de datos

Apuntes para el curso de “Estructuras de datos en C/C++ ”
Dr. Abdiel E. C´ceres Gonz´lez a a
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´sitos, y por eso es importante saber sus ventajas y desventajas. Este documeno to es unacolecci´n de apuntes para el curso de Estructuras de Datos. Los apuntes o se han tomado de algunas fuentes que son detalladas en la secci´n de bibliograf´ o ıa.

´ Indice 1. Preliminares de programaci´n en C/C++ o 3 3 10 15 19 21 21 24 25 26 27 29

1.1. Arreglos 1.2. Apuntadores 1.3. Estructuras C/C++ 1.4. Ejercicios de programaci´n o 2. La pila

2.1. Definici´n y ejemplos o 2.2. Operacionesb´sicas a 2.3. Ejemplo: N´mero de par´ntesis u e 2.4. La estructura de datos Pila en C/C++ 2.5. La representaci´n en C/C++ de las operaciones de una pila o 2.6. Problemas de programaci´n o

1

3.

Colas

31 32 33 34 36 39 40 42 42 44 51 54 56 57 57 57 64 66 69 71 71 73

3.1. Estructura de las colas en C/C++ 3.2. Colas con prioridad 3.3. Ejercicio de programaci´n o 4. Recursi´n o

4.1.Peligros en la recursividad 4.2. Ejercicios de programaci´n o 5. Listas

5.1. Grafos 5.2. Listas simplemente encadenadas 5.3. El uso de memoria din´mica en C/C++ a 5.4. Listas ligadas usando memoria din´mica a 5.5. Ejercicios de programaci´n o 6. ´ Arboles

6.1. Concepto general de ´rbol a ´ 6.2. Arboles binarios 6.3. Representaci´n en C/C++ de los ´rboles binarios o a ´ 6.4. Arboles 6.5.Ejercicios de programaci´n o 7. Grafos

7.1. Recordatorio de las definiciones 7.2. Aplicaci´n ejemplo o

2

1.

Preliminares de programaci´n en C/C++ o

En esta secci´n recordaremos tres temas de programaci´n en C/C++ que son o o 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´n 1 Un arreglo se compone de elementos de igual tama˜o almaceo n nados 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´ndar; es un tipo agregado compuesto de cualquier otro a tipo dedatos. Los arreglos se pueden definir usando tipos de datos mixtos debido a que se supone que todos los elementos son del mismo tama˜o. Puesto que todos los n elementos son del mismo tama˜o y ya que este hecho se utiliza para ayudar n a determinar c´mo localizar un elemento dado, resulta que los elementos son o almacenados en localidades de memoria contiguas. Lo m´s importante a tener en cuenta es:El nombre de un arreglo es visto por el a 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´s a espec´ ıficamente, b) un puntero constante -significa una direcci´n de memoria o bloqueada para el primer elemento de un arreglo-. Por ejemplo, aunque una declaraci´n de arreglo toma la f´rma gen´rica: oo e Tipo_ElementoArray NombreArray [ NumeroDeElementos ] El compilador ve la declaraci´n como o Tipo_ElementoArray * const NombreArray = &NombreArray[0]; Por esta raz´n, un identificador de arreglo no puede ser usado nunca como un o valor-i (valor izquierdo). Los valores izquierdos representan variables que su contenido puede ser alterado por el programa; frecuentemente aparecen a la izquierda delas sentencias de asignaci´n. o Si los nombres de arreglo fueran variables izquierdos permitidos, el programa podr´ cambiar sus contenidos. ıa 3

float SalariosDeEmpleados[Max_empleados]; . . . SalariosDeEmpleados = 45739.0; El efecto har´ cambiar la direcci´n inicial del propio arreglo. ıa o

1.1.1.

Declaraciones de un arreglo

La sintaxis de declaraci´n de arreglos es: o tipo...