PDF de programación - Estructura de datos

ESTRUCTURA DE DATOS







ESTRUCTURA DE DATOS



CESAR AUGUSTO LUNA LOPEZ



RED TERCER MILENIO






AVISO LEGAL

Derechos Reservados  2012, por RED TERCER MILENIO S.C.

Viveros de Asís 96, Col. Viveros de la Loma, Tlalnepantla, C.P. 54080, Estado de México.

Prohibida la reproducción parcial o total por cualquier medio, sin la autorización por escrito del titular
de los derechos.

Datos para catalogación bibliográfica

César Augusto Luna López

Estructura de datos

ISBN 978-607-733-129-2

Primera edición: 2012

Eduardo Durán Valdivieso



DIRECTORIO



Bárbara Jean Mair Rowberry
Directora General

Rafael Campos Hernández
Director Académico Corporativo



Jesús Andrés Carranza Castellanos
Director Corporativo de Administración

Héctor Raúl Gutiérrez Zamora Ferreira
Director Corporativo de Finanzas

Ximena Montes Edgar
Directora Corporativo de Expansión y Proyectos



ÍNDICE



Introducción

Mapa conceptual



Unidad 1. Arreglos

Mapa conceptual

Introducción

1.1. Conceptos

1.2. Arreglos unidimensionales

1.3. Arreglos bidimensionales

1.4. Arreglos de tres o más dimensiones

Autoevaluación



Unidad 2. Pilas y colas

Mapa conceptual

Introducción

2.1. Definiciones y representaciones

2.2. Notaciones infijas, prefijas, postfijas en expresiones

2.3. Inserción y remoción de datos en una pila (LIFO)

2.4. Inserción y remoción de datos en una cola simple y circular

2.5 Problemas

Autoevaluación



Unidad 3. Algoritmos de ordenamiento y búsqueda

Mapa conceptual

Introducción

3.1. Método de burbuja

3.2. Método Shell

3.3. Método de quicksort

3.4. Búsqueda secuencial

3.5. Búsqueda binaria

Autoevaluación



4

6

7

8

9

10

11

16

19

23

24

25

26

27

29

30

33

37

42

44

45

46

47

49

50

51

52

55

2





Unidad 4. Listas

Mapa conceptual

Introducción

4.1. Representación en memoria

4.2. Listas enlazadas

4.3. Listas doblemente enlazadas

4.4. Operaciones con listas

4.5. Problemas

Autoevaluación



Unidad 5. Árboles

Mapa conceptual

Introducción

5.1. Terminología

5.2. Árboles binarios y representaciones gráficas

5.3. Recorrido de un árbol

5.4. Árboles enhebrados

5.5. Árboles de búsqueda

5.6. Problemas

Autoevaluación



Unidad 6. Grafos

Mapa conceptual

Introducción

6.1. Terminología

6.2. Características generales

6.3. Representación de un grafo

56

57

58

59

59

64

66

69

73

74

75

76

77

78

81

83

85

86

107

109

110

111

112

113

114

117

118

Autoevaluación



Bibliografía

Glosario



119



3




INTRODUCCIÓN



En la actualidad, la eficiencia de un programa informático va de la mano con las

técnicas de programación que se emplean en su desarrollo, partiendo desde la

elaboración de diagramas de flujo de datos, hasta la escritura de los códigos

para el desarrollo del software. Lo anterior busca el acceso a los datos de la

información de una manera ordenada mediante

instrucciones válidas,

empleando una secuencia lógica.

La estructura de datos se refiere a un conjunto de técnicas que

aumentan considerablemente la productividad del programa, reduciendo en

elevado grado, el tiempo requerido para escribir, verificar, depurar y mantener

los programas. El término estructura de datos hace referencia a un conjunto de

datos que, por medio de un nombre, identifican un espacio en memoria,

teniendo ciertas características como

la organización y estructuración,

permitiendo realizar operaciones definidas en ellas. Las estructuras de datos

pueden ser de dos tipos:



 Estructuras de datos estáticas (las que tienen un tamaño definido).

 Estructuras de datos dinámicas (en las cuales su tamaño puede ser

cambiado en tiempo de ejecución).



La presente obra comienza su estudio, con las estructuras de datos

estáticas, analizando el concepto y fundamento de los arreglos, sus métodos

para el manejo de datos, sus variantes que pueden dar origen a estructuras de

arreglos de una o más dimensiones.

En la unidad dos analizaremos el concepto de las pilas y colas, los

métodos en que se manipulan los datos para insertarlos o eliminarlos, así como

sus reglas de uso.

En la unidad tres combinaremos lo aprendidos en las anteriores

unidades para lograr realizar prácticas más complejas, donde involucren

conceptos y métodos que permitan ordenar datos, empleando arreglos, o bien

para

realizar búsquedas de

información a

través de algoritmos

computacionales. Las últimas unidades abordarán los temas de árboles y



4




grafos, que son estructuras dinámicas que nos permitirán trabajar con

almacenamientos secundarios. Asimismo, se introducirá sobre el uso de los

grafos, su empleo y creación dentro de un lenguaje de programación.



5





MAPA CONCEPTUAL



Estructura de Datos

emplea

Técnicas

Arreglos

Pilas

Colas

Árboles

Grafos

de

Tipo

Emplean

Términos

emplean

Unidimension

al

3 o más

dimensiones

Bidimension

al

para

Manejo

de

Inserción-
Remoción

de

Binarios

Enhebrados

para

Obtener

Comprender

Para

sus

Datos

Características



6





UNIDAD 1



ARREGLOS

OBJETIVO

Analizar el uso e implementación de los arreglos para la resolución de

problemas de datos estructurados, mejorando el tiempo de desarrollo y eficacia



de los sistemas.



TEMARIO

1.1. CONCEPTOS

1.2. ARREGLOS UNIDIMENSIONALES

1.3. ARREGLOS BIDIMENSIONALES

1.4. ARREGLOS DE TRES O MÁS DIMENSIONES



7





MAPA CONCEPTUAL

Arreglos

es

Colección

se

clasifican

en

Finita

Ordenada

Unidimensional

3 o mas

Dimensiones

Homogénea

de

datos



Bidimensional

para

los

Almacenar



8





INTRODUCCIÓN

En esta unidad conoceremos uno de los tipos de datos estructurados más

empleados dentro de la programación, los arreglos. La utilidad de estos es

trascendental al momento de codificar los programas, debido a que dentro de

un programa tendemos a emplear una gran cantidad de variables, esto puede

ser un poco ortodoxo debido a que si necesitamos 10, 20 o 100 variables para

un mismo tipo de datos, la manipulación de estos se vuelve más complicada.

¿Entonces como resolvemos el manejar tantas variables? Aquí es donde

se emplean los arreglos, para formar una estructura más definida, más fácil de

procesar e implementar en nuestros códigos.

Partiremos de la conceptualización de los arreglos, como dependiendo

de la necesidad pueden emplearse de una, dos o más dimensiones. Como

escribir y leer sus datos, así como ejemplos de la codificación en el lenguaje

Java.



9




1.1. CONCEPTOS

Un arreglo es una estructura de datos lineal, “un arreglo puede definirse como
un grupo o una colección finita, homogénea y ordenada de elementos.”1 Donde

finita significa que debe tener un límite de elementos, homogénea que los

elementos deben de ser del mismo tipo de datos, y ordenada porque se puede

conocer cuál es el primer elemento, los subsiguientes o el último.

En la siguiente gráfica puede observarse cómo se representa un arreglo

y se identifican las partes que lo integran.



No. Elemento

0

1

2

3

…….



n



Elementos



Fig.1.1. Representación de un arreglo



Dentro del uso de los arreglos, se puede hacer referencia a un número

de elemento para introducir, actualizar o extraer valores, ese Número de

elemento se conoce como índice y especifica la posición del elemento en el

arreglo.

Para referirse a una posición del arreglo, es necesario conocer el

nombre del arreglo y su índice, por ejemplo, tomando la figura 1.2., tenemos un

arreglo llamado “Datos” y necesitamos extraer el valor “77”, es necesario

especificar: Datos [3]



1 Osvaldo Cairó /Silvia Guardati , Estructuras de datos, pág. 4



10





Indice



Datos

0
1
12 22

2
3
45 77



…….

n



Fig. 1.2. Arreglo Datos



Según su estructura los arreglos se clasifican en:

 Arreglos unidimensionales o de una dimensión.

 Arreglos bidimensionales o de dos dimensiones.

 Arreglos tridimensionales o de tres o más dimensiones.

1.2. ARREGLOS UNIDIMENSIONALES

El concepto de arreglo empleado en el tema anterior, se aplica también para

referirse a los arreglos de dimensión, es decir, es un tipo de datos estructurado

compuesto de un número de elementos finitos, homogéneos y ordenados.

Los elementos del arreglo se almacenan en posiciones contiguas de

memoria, a cada una de las cuales se puede acceder directamente mediante

su índice. La forma de acceder a un arreglo de una dimensión es directa, pues

se puede especificar el índice del elemento sin necesidad de conocer el

contenido de los elementos contiguos.

Esto se puede ilustrar mejor con el siguiente ejemplo: supóngase que

desea capturar las edades de un grupo de 100 personas, para conocer cuántas

están sobre el promedio de edad.

Este problema se podría resolver empleando 100 variables simples para

almacenar las edades; luego, se calcula el promedio, y por último se comparan

las 100 variables para determinar cuántas personas están sobre el promedio.

Este método consumirá muchos recursos del sistem