Estructuras de datos en C/C++

Apuntes para el curso de
“Estructuras de datos en C/C++ ”


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 una colecci´n de apuntes para el curso deEstructuras 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

1.1. Arreglos

3
3

1.2. Apuntadores

10

1.3. Estructuras C/C++

15

1.4. Ejercicios de programaci´n
o

19

2.

21

La pila

2.1. Definici´n y ejemplos
o

21

2.2. Operacionesb´sicas
a

24

2.3. Ejemplo: N´mero de par´ntesis
u
e

25

2.4. La estructura de datos Pila en C/C++

26

2.5. La representaci´n en C/C++ de las operaciones de una pila
o

27

2.6. Problemas de programaci´n
o

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´n
o

34

4.

36Recursi´n
o

4.1. Peligros en la recursividad

39

4.2. Ejercicios de programaci´n
o

40

5.

Listas

42

5.1. Grafos

42

5.2. Listas simplemente encadenadas

44

5.3. El uso de memoria din´mica en C/C++
a

51

5.4. Listas ligadas usando memoria din´mica
a

54

5.5. Ejercicios de programaci´n
o

56

6.

´
Arboles

57

6.1. Concepto general de ´rbola

57

´
6.2. Arboles binarios

57

6.3. Representaci´n en C/C++ de los ´rboles binarios
o
a

64

´
6.4. Arboles

66

6.5. Ejercicios de programaci´n
o

69

7.

71

Grafos

7.1. Recordatorio de las definiciones

71

7.2. Aplicaci´n ejemplo
o

73

2

1.

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

En esta secci´n recordaremos tres temas de programaci´nen 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 individualutilizando 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 de datos.
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 queeste 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 tipopuntero, 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:
o
o
e
Tipo_ElementoArray NombreArray [ NumeroDeElementos ]
El compilador ve la declaraci´n como
o
Tipo_ElementoArray * const NombreArray = &NombreArray[0];
Por esta raz´n, unidentificador 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 de las sentencias de asignaci´n.
o
Si los nombres de arreglo fueran variables izquierdos permitidos, el programa
podr´ cambiar sus contenidos.
ıa
3

float...