• Author / Uploaded
• Daniel Quispe

Citation preview

UNIVERSIDAD SALESIANA DE BOLIVIA CARRERA INGENIERIA DE SISTEMAS

DOSSIER PROGRAMACION II Tercer Semestre

  

Lic. Katya Maricela Pérez Martínez Lic. Gladys Francisca Chuquimia Mamani Lic. Juan Vito Condori

   

2012

       

INDICE 1. Capítulo I. Introducción a las Estructuras de Datos 1.1. Introducción 1.2. Estructuras Fundamentales

1 1 1

1.3. Abstracción 1.4. Definición de Estructuras de datos

2 2

1.5. T.D.A. (Tipo de Dato Abstracto) 1.6. Clasificación de las Estructuras de Datos

2 2

1.7. Estructuras de Datos Estáticas 1.8. Registros

4 18

1.9. Conjuntos 1.9.1. Definición de Conjuntos 1.10. Matrices poco densas

24 24 24

1.11. 1.12.

26 32

Archivos Ejercicios propuestos

2. Capítulo II: Pilas 2.1. Introducción

36 36

2.2. Representación de las Pilas

37

2.3. Operaciones con pilas 2.4. Operaciones adicionales

38 39

2.5. Aplicaciones 2.5.1. Llamadas a subprogramas

43 43

2.5.2. Recursión 2.6. Ejercicios Propuestos

45 46

3. Capitulo III: Colas 3.1. Introducción 3.2. Características

47 47 48

3.3. Representación de las colas 3.4. Estructura de una cola

48 48

3.5. Operaciones con colas 3.6. Colas circulares

49 53

3.7. Operaciones con colas circulares 3.8. Aplicación de Pilas y Colas

54 55

3.9. Ejercicios

56

4. Capitulo IV: Recursividad 4.1. Introducción

[Estructura de Datos]  Lic. Katya Perez Martinez &Lic. Gladys Chuquimia

58 58

Page 2

4.2. Ámbito de aplicación 4.3. Razones de uso

58 58

4.4. ¿En qué consiste la recursividad? 4.5. Forma de Enfrentar problemas recursivos

59 59

4.6. Tipos de recursividad 4.7. La pila de recursion

61 62

4.8. La llamada a una función 4.9. Ejercicios

63 63

5. Listas Enlazadas 5.1. Introducción a las Estructuras de datos dinámica

65 65

5.2. Mecanismos para enlazar información 5.3. El tipo puntero

66 67

5.4. Tipo de dato abstracto Nodo

72

5.5. Punteros 5.5.1. Operador ->

72 72

5.6. Operaciones básicas sobre listas enlazadas 5.7. Ejercicios

73 78

6. Capítulo IV: Árboles y Grafos 6.1. Introducción

79 79

6.2. Conceptos Básicos 6.3. Árboles Binarios

79 81

6.4. Representación de árboles binarios 6.5. Recorridos

82 83

6.6. Árboles Binarios de Búsqueda (Abb) 6.7. Operaciones sobre árboles binarios de búsqueda 6.8. Árboles ordenados

86 86 90

6.9. Grafos 6.9.1. Definiciones Básicas

91 91

6.10.

95

Ejercicios

7. Lecturas Complementarias

97

8. Glosario

102

[Estructura de Datos]  Lic. Katya Perez Martinez &Lic. Gladys Chuquimia

Page 3

Capítulo I Introducción a las Estructuras De Datos

Asamblea en la carpintería     Cuentan  que  en  la  carpintería  hubo  una  vez  una  extraña  asamblea.  Fue  una  reunión  de  herramientas  para  arreglar  sus  diferencias. El martillo ejerció la presidencia, pero la asamblea le notificó que tenía que renunciar.  ¿La causa? ¡Hacía demasiado  ruido! Y, además, se pasaba el tiempo golpeando.     El martillo aceptó su culpa, pero pidió que también fuera expulsado el tornillo; dijo que había que darle muchas vueltas para que  sirviera de algo.     Ante el ataque, el tornillo aceptó también, pero a su vez pidió la expulsión de la lija. Hizo ver que era muy áspera en su trato y  siempre tenía fricciones con los demás.     Y la lija estuvo de acuerdo, a condición de que fuera expulsado el metro que siempre se la pasaba midiendo a los demás según  su medida, como si fuera el único perfecto.     En eso entró el carpintero, se puso el delantal e inició su trabajo.  Utilizó el martillo, la lija, el metro y el tornillo.   Finalmente, la  tosca madera inicial se convirtió en un lindo mueble.     Cuando la carpintería quedó nuevamente  sola, la asamblea reanudó la deliberación. Fue  entonces cuando tomó la  palabra el  serrucho, y dijo: "Señores,  ha  quedado demostrado que tenemos defectos, pero el carpintero  trabaja con nuestras cualidades.  Eso es lo que nos hace valiosos. Así que no pensemos ya en nuestros puntos malos y concentrémonos en la utilidad de nuestros  puntos buenos".     La asamblea encontró entonces que el martillo era fuerte, el tornillo unía y daba  fuerza, la lija era especial para afinar y limar  asperezas y observaron que el metro era preciso y exacto.     Se  sintieron entonces  un  equipo  capaz  de  producir muebles  de  calidad.  Se sintieron  orgullosos  de  sus  fortalezas  y  de trabajar  juntos. 

Anónimo

1.1. Introducción Para procesar información en un computador es necesario hacer una abstracción de los datos que tomamos del mundo real, abstracción en el sentido de que se ignoran algunas propiedades de los objetos reales, es decir, se simplifican. Se hace una selección de los datos más representativos de la realidad a partir de los cuales pueda trabajar el computador para obtener unos resultados. Cualquier lenguaje suministra una serie de tipos de datos simples, como son los números enteros, caracteres, números reales. En realidad suministra un subconjunto de éstos,

pues la memoria del ordenador es finita. Los punteros (si los tiene) son también un tipo de datos. El tamaño de todos los tipos de datos depende de la máquina y del compilador sobre los que se trabaja.

1.2. Estructuras Fundamentales Los datos a procesar por una computadora se clasifican en: 9 Simples 9 Estructurados Los datos simples ocupan sólo una casilla de memoria, por tanto una variable simple hace referencia a un único valor a la vez. Los datos Estructurados o Compuestos se caracterizan por el hecho de que con un nombre (identificador de variable estructurada) se hace referencia a un grupo de casillas de memoria. Tiene varios componentes.

Cabe hacer notar que en el presente texto, se tomará como herramienta para los programas y representar las diferentes estructuras de datos el Lenguaje C++ y Java.

Ejemplos: Dato Simple Declaramos una variable A de tipo entero y asignamos el valor 25. A Å Identificador int

A;

A = 25;

25

Dato Estructurado Declaramos un dato compuesto o estructurado A que tendrá 5 elementos de tipo entero.

[Estructura de Datos]  Lic. Katya Perez Martinez &Lic. Gladys Chuquimia

Page 2

int A[5] ; A = {20,30,40,50,60};

A =

20 30 40 50 60

Identificador

1.3. Abstracción Una abstracción es un proceso mental donde se extraen rasgos esenciales de algo para representarlos por medio de un lenguaje gráfico o escrito.

1.4. Definición de Estructuras de Datos Una estructura de datos es cualquier colección de datos organizados de tal forma que tengan asociados un conjunto de operaciones para poder manipularlos.

1.5. T.D.A. (Tipo de Dato Abstracto) Al diseñar una estructura de datos con la técnica de abstracción pasa a ser un TDA, que: 9 Puede implementarse en cualquier lenguaje 9 Puede aplicarse en cualquier concepto Ejemplo: Abstraemos el concepto Estudiante Nombre del TAD Elementos

Operaciones o métodos

              ESTUDIANTE   Ru: entero  Nombre: Cadena  Sexo: carácter  Direccion: Cadena    LeerDatosEstudiante ()  ImprimirDatosEstudiante ()  ModificarDireccion()  CalcularNotaFinal() 

Como se puede notar existe una operación No Permitida denominada: CalcularNotaFinal(); que no debiera estar presente en el TAD, debido a que no se cuenta con elementos que nos permitan realizar esta operación.

[Estructura de Datos]  Lic. Katya Perez Martinez &Lic. Gladys Chuquimia

Page 3

Recuerda en todo momento que sólo deben incluirse las operaciones que puedan trabajar con los elementos que contiene el TAD.

1.6. Clasificación de las Estructuras de Datos Las estructuras de datos desde el punto de vista de asignación de memoria, se clasifican en: 9 Estructuras de datos estáticas 9 Estructuras de datos dinámicas

También pueden ser clasificadas en: 9 Estructuras Lineales 9 Estructuras No Lineales

1.6.1.

Estructuras de Datos Estáticas

Son aquellas en las que el tamaño ocupado en memoria se define antes de que el programa se ejecute y no puede modificarse dicho tamaño durante la ejecución del programa. Por ejemplo tenemos a los Arreglos, Registros y Conjuntos.

1.6.2.

Estructuras de Datos Dinámicas

Las estructuras dinámicas de datos son estructuras que cuya dimensión puede crecer o disminuir durante la ejecución del programa. Por ejmplos: Listas Enlazadas, Árboles y Grafos.

1.6.3.

Estructuras de Datos Lineales

Las estructuras de datos lineales se derivan del concepto de secuencia. Primero se definen las secuencias como conjuntos de elementos entre los que se establece una relación de predecesor y sucesor. Los diferentes TADs basados en este concepto se diferenciaran por las operaciones de acceso a los elementos y manipulación de la estructura. Desde el punto de vista de la informática, existen tres estructuras lineales especialmente importantes: vectores, las pilas, las colas y las listas.

1.6.4.

Estructuras de Datos No Lineales

Se denominan estructuras de datos No Lineales porque a cada elemento le pueden seguir varios elementos o puede estar rodeado de elementos. Por ejemplo: Árboles, Grafos y Matrices

[Estructura de Datos]  Lic. Katya Perez Martinez &Lic. Gladys Chuquimia

Page 4

1.7. Estructuras de Datos Estáticas 1.7.1.

Arreglos

Definición: Colección finita, homogénea y ordenada de elementos. Finita: Porque todo arreglo tiene un límite. Homogénea: Porque todos los elementos son del mismo tipo. Ordenada: Porque se puede determinar cuál es el enésimo elemento. Un arreglo tiene dos partes: Componentes e índices C1

C2

…

Cn

i0

i1

…

iN

Componentes Indices

Componentes: Hacen referencia a los elementos que forman el arreglo. Índices: Permiten referirse a los componentes del arreglo en forma individual.

1.7.2.

Arreglos Unidimensionales (Vectores)

Son los arreglos más simples y constan de un solo índice, también se llaman vectores. Notación: Podría ser de diferentes maneras. Por ejemplo: Array [0...9] de enteros: Vector Vector: C componente 30 50 70 60 C= 0 1 2 … 8 Identificador Indice Donde, C hace referencia a todo el vector, mientras que los índices hacen referencia a los elementos en forma individual.

1.7.3.

Declaración de vectores

En Java Para declarar un Array se utilizan corchetes para indicar que se trata de un Array y no de una simple variable de tipo especificado. Su sintaxis es: Tipo_dato identificador[ ];

[Estructura de Datos]  Lic. Katya Perez Martinez &Lic. Gladys Chuquimia

Page 5

O bien: Tipo_dato [ ] identificador; Donde: Tipo_dato: es el tipo de datos de los elementos del vector. Identificador: es el nombre del vector.

Luego, se debe crear el Array con el operador new, de la siguiente manera: Identificador = new tipo [ cantidad_de_elementos ]; Por ejemplo:

public class Array { public static void main (String arg []) { int losValores []; losValores = new int [10]; losValores [0] = 100; System.out.println (losValores [0]); } }

Archivo: Array.java

El programa: Array.java, trabaja con el vector losValores, que almacena un máximo de

VECTOR

10 elementos enteros.

V[15]: Entero N: Entero

Implementación del TAD Vector Este es el diseño del TAD vector que maneja números enteros.

leedim() leervector() mostrarvector()

Ejercicios A continuación se muestra la implementación de este TAD en Java. En lenguaje java:

[Estructura de Datos]  Lic. Katya Perez Martinez &Lic. Gladys Chuquimia

Page 6

//ARCHIVO VECTOR.JAVA import java.io.*; public class Vector { static int v[]; static int n; static InputStreamReader Caracteres; static BufferedReader Buffer; static String dato; static void leedim () throws IOException { System.out.println ("Cuantos elementos insertara en el Vector? "); dato = Buffer.readLine (); n = Integer.parseInt (dato); } static void leervector () throws IOException { int i; for(i=0; i < n; i++) { System.out.println("Ingrese elemento "+ i + " = "); dato = Buffer.readLine(); v[i] = Integer.parseInt(dato); } } static void mostrarvector () throws IOException { int i; for(i=0; i < n; i++) { System.out.print(v[i] + "

");

} } public static void main (String [] args) throws IOException { v = new int[15]; Caracteres = new InputStreamReader (System.in); Buffer = new BufferedReader(Caracteres); leedim (); leervector(); mostrarvector(); } }

[Estructura de Datos]  Lic. Katya Perez Martinez &Lic. Gladys Chuquimia

Page 7

EJERCICIOS EN LENGUAJE C 1. Queremos efectuar estadísticas con una serie de valores (las edades de 15 personas). En una primera versión, solicitaremos las edades de todas las personas y, a continuación, calcularemos y mostraremos por pantalla la edad media, la desviación estándar, la moda y la mediana. Las fórmulas para la media y la desviación estándar son:

∑ x=

15 i =1

xi

15

∑

15

δ=

i =1

( xi − x) 2 15

Donde Xi es la edad del individuo número i.

Se diseña a continuación el TAD.

ESTADISTICA E[15]: Entero LeerEdades() ImprimirEdades() CalculaMedia() CalculaDesviacion()

//ARCHIVO EJERCICIO1.CPP #include #include #include #define PERSONAS 15 struct ESTADISTICA { int E[PERSONAS]; void void void void

LeerEdades(void); ImprimirEdades(void); CalculaMedia(void); CalculaDesviacion(void);

}; void ESTADISTICA::LeerEdades(void) { //Lectura de edades for (int i=0; i