IBM Estructura de Datos y Algoritmo
IBM Estructura de Datos y Algoritmo
IBM Estructura de Datos y Algoritmo
Algoritmos
Cdigo de Curso: CY330
Versin 3.0
Libro 1: Estructura de
Datos y Algoritmos
Esta publicacin ha sido producida usando Microsoft Word 2000 y Microsoft PowerPoint
2000 para Windows.
Marcas Registradas
DB2 Informix
No elimine pginas en blanco que puedan aparecer al final de cada unidad entre
unidades. Estas pginas fueron insertadas intencionalmente.
.
Gua del Estudiante Estructura de Datos y Algoritmos
Contenido
Descripcin del Curso ....................................................................................... 5
Descripcin de Unidades................................................................................... 7
Volumen 1: Estructura de Datos Simples ...................................................... 11
Unidad 1: Fundamentos de Estructura de Datos y Estructura de Datos Lista
.......................................................................................................... 13
Objetivos de Aprendizaje 13
1. Introduccin 14
2. La Necesidad de Algoritmos y Estructura de Datos 14
3. Tipos de Datos y Estructura de Datos 15
4. El Rol de las Estructuras de Datos para Resolver Problemas 17
5. Tipo de Dato Abstracto Abstract Data Type (TDA) 17
6. Estructura de Datos Lista 18
7. Implementacin de una Lista como un Arreglo 21
8. Aplicaciones que Usan la Estructura de Datos Lista 32
Resumen 34
Unidad 1: Examen de Autoevaluacin 35
Respuestas de la Unidad 1: Examen de Autoevaluacin 37
Unidad 2: Lista Enlazada ................................................................................. 39
Objetivos de Aprendizaje 39
1. Introduccin a Listas Enlazadas 40
2. Operaciones en una Lista Enlazada 42
3. Encontrar el Predecesor y Sucesor en la Lista Enlazada 50
Resumen 63
Unidad 2: Examen de Autoevaluacin 64
Respuestas al la Unidad 2: Examen de Autoevaluacin 67
Unidad 3: Laboratorio de Listas Enlazadas ................................................... 69
Objetivos de Aprendizaje 69
Ejercicio de Laboratorio 70
Unidad 4: Pila.................................................................................................... 73
Objetivos de Aprendizaje 73
1. Pilas 74
2. Tipo de Dato Abstracto Pila 75
3. Implementar Pilas Usando Arreglos 78
4. Pila como Lista Enlazada 86
i
Copyright IBM Corp. 2008
Los materiales del curso no pueden ser reproducidos total o
parcialmente sin el previo permiso escrito de IBM.
Estructura de Datos y Algoritmos Gua del Estudiante
5. Aplicaciones de Pilas 89
6. Evaluar una Expresin Postfija 103
Resumen 106
Unidad 4: Examen de Autoevaluacin 107
Respuestas de la Unidad 4: Examen de Autoevaluacin 109
Unidad 5: Laboratorio de Pila........................................................................ 111
Objetivos de Aprendizaje 111
Ejercicios de Laboratorio 112
Unidad 6: Colas .............................................................................................. 113
Objetivos de Aprendizaje 113
1. Preliminares de Cola 114
2. Implementar las Colas como Arreglos 119
3. Usar Arreglos Circulares 127
4. Colas como Listas Enlazadas 130
5. Aplicaciones de Colas 135
Resumen 137
Unidad 6: Examen de Autoevaluacin 138
Respuestas a la Unidad 6: Examen de Autoevaluacin 140
Unidad 7: Laboratorio de Colas .................................................................... 141
Objetivos de Aprendizaje 141
Ejercicio de Laboratorio 142
Volumen 2: Estructuras de Datos Avanzadas ............................................. 143
Unidad 1: Grafos ............................................................................................ 145
Objetivos del Aprendizaje 145
1. Introduccin 146
2. Preliminares de Grafos 146
3. Grafos No Dirigidos 149
4. Grafos Dirigidos 150
5. Grafos y Estructuras de Datos 152
6. Aplicaciones de Grafos 159
Resumen 162
Unidad 1: Examen de Autoevaluacin 163
Respuestas a la Unidad 1: Examen de Autoevaluacin 165
Unidad 2: rboles........................................................................................... 167
Objetivos del Aprendizaje 167
1. Introduccin 168
ii
Copyright IBM Corp. 2008
Los materiales del curso no pueden ser reproducidos total o
parcialmente sin el previo permiso escrito de IBM.
Gua del Estudiante Estructura de Datos y Algoritmos
iv
Copyright IBM Corp. 2008
Los materiales del curso no pueden ser reproducidos total o
parcialmente sin el previo permiso escrito de IBM.
Gua del Estudiante Estructura de Datos y Algoritmos
El primer volumen del curso presenta las estructuras de datos simples, comenzando
con listas implementadas como arreglos y terminando con listas enlazadas. Tambin, se
proporciona una visin general de lo que es la estructura de datos pila y cola la manera
en que pueden ser implementadas ya sea con listas o con arreglos.
El segundo volumen presenta lo que son las estructuras de datos avanzadas, el trabajo
con grafos y rboles, las diferentes aplicaciones para cada uno de ellos, as como los
diferentes recorridos para los rboles. Adicionalmente, se proporcionan las diferentes
tcnicas de ordenamiento, tanto simples como avanzadas.
Descripcin de Unidades
Volumen 1: Estructura de Datos Simples
Unidad 1: Fundamentos de Estructura de Datos y Estructura de Datos Lista
En esta unidad se explica el rol de las estructuras de datos y algoritmos como bloques
de construccin en programas de computadoras, adems de la definicin de dicha
estructura de datos. Se explicar la diferencia entre un tipo de dato y una estructura de
datos. Adicionalmente, se tocan aspectos como: definir la resolucin de problemas
utilizando estructura de datos, describir las listas como un tipo de dato, discutir toda su
estructura e implementar listas como arreglos.
Unidad 4: Pila
En esta unidad se tocan tpicos como la definicin de la estructura de datos pila y las
diferentes operaciones que se realizan sobre dicha estructura. En tal sentido, se
describen las operaciones del TDA Pila, tambin se explica la implementacin usando
un arreglo y una lista enlazada. Para finalizar, se resuelven algunos problemas usando
pilas.
Este laboratorio fue diseado con la finalidad de aplicar el concepto de pila para
resolver problemas simples, crear una pila y realizar sus operaciones en C, adems de
aplicar dichas operaciones en todo tipo de aplicaciones.
Unidad 6: Colas
En esta unidad se dispone aplicar los conceptos de TDA colas en cualquier problema,
crear cualquier tipo de cola y realizar operaciones sobre dicho TDA.
Volumen 2: Estructura de Datos Avanzadas
Unidad 1: Grafos
Unidad 2: rboles
En esta unidad se explicarn las tcnicas de merge sort (ordenamiento por fusin) y
quicksort (ordenamiento rpido), lo cual incluye escribir un algoritmo para desarrollar
cada una de estas tcnicas.
En esta unidad se deben aplicar los conceptos aprendidos sobre bsqueda en cualquier
desarrollo de aplicaciones y realizar algoritmos de bsqueda lineal y binaria.
1. Introduccin
En este curso se discutirn dos aspectos importantes del esfuerzo de programacin, los
cuales son: las estructuras de datos y los algoritmos. Una combinacin correcta de
estructuras de datos apropiada y algoritmos eficientes dan como resultado buenos
programas. Se comenzar la discusin de estructuras de datos con las listas, y se
proceder a aprender los diferentes algoritmos de bsqueda y ordenamiento. Antes de
continuar estudiando las diferentes estructuras de datos, se discutir brevemente la
necesidad de algoritmos y estructuras de datos, las diferencias entre tipo de dato y
estructuras de datos, adems del rol de las estructuras de datos para la solucin de
problemas.
En el ejemplo anterior, se trat la bsqueda del nombre de una ciudad dada en una
lista. All, se us un arreglo para almacenar la lista. En la mayora de los lenguajes de
programacin, una lista simple ser almacenada como un arreglo. Una lista de enteros
ser representada como un arreglo de enteros, una lista de valores Booleanos como un
arreglo de Boolean y as sucesivamente.
Por ejemplo, se pueden almacenar los detalles de un estudiante como sigue:
Nombre del estudiante (representado como un arreglo de caracteres).
Edad del estudiante (representada como un entero).
Notas obtenidas por el estudiante (representadas como un flotante).
Normalmente, estos se refieren como estructuras de datos, ya que se desarrolla una
estructura agrupando diferentes tipos de datos juntos. El trmino estructura de dato se
usa normalmente cuando se refiere a una coleccin de datos que estn organizados de
alguna u otra manera.
Una estructura de datos, puede as, ser definida como una coleccin de entidades
pertenecientes a tipos de datos diferentes que resulta en la organizacin de piezas de
datos interrelacionadas. Las estructuras de datos tambin tienen un conjunto de valores
y operaciones definidas en estos valores.
- Borrar un elemento.
- Encontrar un elemento.
- Mostrar elementos.
Conjunto
- Unin de dos conjuntos.
- Interseccin de dos conjuntos.
- Diferencia entre dos conjuntos.
Pila
- Insertar (push) un elemento.
- Eliminar (pop) un elemento.
- Tope de la pila.
Cola
- Aadir un elemento.
- Quitar un elemento.
- Frente de la cola.
- Longitud de la cola.
rbol
- Aadir un nodo.
- Borrar un nodo.
- Recorrer un rbol.
En los ejemplos anteriores, lista, conjunto, pila, cola y rbol son entidades de
almacenamiento de informacin. Las operaciones definidas sobre cada una de estas
entidades varan dependiendo del propsito para los cuales las entidades se crearon. A
nivel de TDA, las operaciones se especifican sin dar detalles sobre cmo se
implementan.
Las listas son estructuras de datos que se puede expandir o contraer. Se puede
insertar, eliminar y acceder elementos en una lista. Tambin, se puede dividir una lista,
o unir dos listas.
Una lista puede ser vista como un TDA al definir un conjunto de operaciones sobre ella.
Unas cuantas operaciones tpicas definidas en una lista son:
Nueva
Insertar
Borrar
Encontrar
Obtener
Esvacio
Para entender las semnticas de las operaciones anteriores, se tienen las siguientes
variables:
Lista: La lista.
elem: Elemento en la lista.
pos: Posicin donde un elemento reside en la lista.
Usando estas tres variables, se van a entender las operaciones en una lista que se dan
a continuacin:
nueva(lista): Crea y retorna una nueva lista.
insertar(lista, elem): Inserta elem en la lista.
borrar(lista, pos): Borra un elemento en una lista en la posicin pos.
Si la lista est vaca o pos no existe en la lista, entonces la operacin
resulta en un error.
encontrar(lista, elem): Busca elem en la lista y retorna la posicin en
la que elem se encuentra.
obtener(lista, pos): Obtiene el elem encontrado en la posicin pos de la
lista. Si pos es menor que 1 mayor que el nmero de elementos de la
lista, la operacin resulta en un error.
esvacio(lista): Retorna verdadero si la lista es vaco, de lo contrario
retorna falso.
Las operaciones nueva e insertar son dos operaciones bsicas de la lista que
generan todas las nuevas listas posibles. De aqu que, estas operaciones se denominen
operaciones primitivas. Una operacin primitiva es aquella que se puede usar para
definir todas las otras operaciones de una estructura de datos. Para una estructura de
lista de datos, las operaciones primitivas son nueva e insertar.
La operacin borrar no se usa como una operacin para generar todas las listas, de
all que no es una operacin primitiva. La operacin borrar no retorna una nueva lista,
solamente quita uno de los elementos existentes de la lista y retorna una lista
modificada.
Ahora se quiere borrar una ciudad de la lista, esto crea un hueco en la lista. Por esto, se
debe mover todos los elementos de abajo hacia arriba un paso. En la Figura 1.2 se ha
borrado Dayton y se han movido los elementos una celda hacia arriba.
Es una excelente prctica revisar primero por errores y luego seguir con la funcin. Si el
nmero de elementos en la lista es igual a LISTMAX retornamos 1 a la funcin que lo
invoc. La funcin llamada puede revisar este valor y si se requiere manejar el error de
la mejor manera. Si se requiere hacer una insercin, simplemente se debe copiar el
elemento de un arreglo al final. Se incrementa la variable count y se sale de la funcin.
Si pos < 0 pos > count-1, implica que es una posicin invlida. Por lo que, se
retorna de la funcin con -1.
Esto es directo. Simplemente se revisa cada elemento del arreglo con el elemento
buscado. Si el elemento es encontrado, se retorna la posicin del elemento en la lista.
Aqu, se retorna k+1, ya que el arreglo empieza en 0. Si el elemento no es encontrado,
se retorna -1.
Las dos funciones anteriores son simples de entender. Se hace una revisin para
determinar si la posicin de entrada est dentro del rango. En el caso de la funcin del
sucesor, se revisa para determinar si la posicin de entrada es la ltima posicin en la
lista y de ser as, se genera un mensaje apropiado. Si no, se retorna el elemento en la
siguiente posicin en la lista.
El campo count se puede revisar para determinar si una lista est vaca o no. Tambin,
se da a continuacin la funcin que retorna el nmero de elementos en la lista.
/* Encontrar el nmero de elementos en una lista */
int noOfElements(List_Array *list_ptr) {
return list_ptr->count;
}
Se escribe ahora la funcin main para invocar las diferentes operaciones definidas
sobre la estructura de datos lista.
1. main() {
2. List_Array words;
3. char *string = (char *) malloc(STRINGSIZE *
sizeof(char));
4. int i, position,value;
5. newList(&words); // Crea una nueva lista
6. printf("Ingrese una lista de palabras, termine con la
\
7. palabra 'over':\n");
8. do {
9. scanf("%s",string);
10. /* No se quiere almacenar la palabra over */
11. if (strcmp(string,"over"))
12. insertElement(&words, string);
13. } while (strcmp(string,"over"));
14. //Muestra todas las palabras en la lista despus de la
insercin
15. if (isEmpty(&words)) {
16. printf("No hay palabras en la lista!\n");
17. exit(0); // Sale si no hay palabras en la lista
18. }
19. else {
20. printf("\nLista de palabras despus de las
inserciones:\n");
21. for (i = 0; i < noOfElements(&words); i++)
22. printf("%s\n", words.list[i]);
23. printf("\n");
24. }
25. // Obtiene la posicin cuyos elementos van a ser
eliminados
26. do {
27. printf("\nIngrese la posicin para eliminar el \
28. elemento de: ");
29. scanf("%d", &position);
30. if (position < 1 || position >
noOfElements(&words))
31. printf("\nError de entrada: Posicin fuera
\
32. de rango!\n");
33. } while (position < 1 || position >
noOfElements(&words));
34. // Elimina un elemento
35. // Pasamos la posicin -1 a la funcin de eliminar
36. // Ya que arreglos en C++ arrays tiene ndices de 0 a
n-1
37. value = deleteElement(&words, position-1);
38. if (value == -1)
39. printf("\nError de entrada: No existe esa posicin \
en la lista\n");
40. printf("\n");
41.
42. if (isEmpty(&words)) {
43. printf("No hay palabras en la lista!\n");
44. exit(0); // Sale si no hay palabras en la lista
45. }
46. else {
47. //Muestra todas las palabras en la lista despus de la
insercin
48. printf("Lista de palabras despus de
eliminacin:\n");
49. for (i = 0; i < noOfElements(&words); i++)
50. printf("%s\n", words.list[i]);
51. }
52. // Encuentra un elemento en la lista
53. printf("\nIngrese el elemento a buscar en la lista:
");
54. scanf("%s", string);
55. value = find(&words, string);
56. if (value == -1)
57. printf("\nElemento %s no se encontra en lista!\n",
string);
58. else
59. printf("\nEl elemento se encuentra en posicin %d
\
60. en la lista!\n", value);
61. // Obtiene una posicin de predecesor y sucesor
62. // a ser encontrados
Libro 1: Estructura de Datos y Algoritmos
Unidad 1: Fundamentos de Estructura de Datos y Estructura de Datos Lista 29
63. do {
64. printf("\nIngrese la posicin en la lista cuyo \
65. predecesor y sucesor se va a encontrar: ");
66. scanf("%d", &position);
67. if (position < 1 || position >
noOfElements(&words))
68. printf("\nError de entrada: Posicin fuera
\
69. de rango!\n");
70. } while (position < 1 || position >
noOfElements(&words));
71. if (isEmpty(&words))
72. printf("\nError de entrada: No existe esa
posicin \ en la lista\n");
73. printf("\n");
74. // Encontrar el predecesor y sucesor en la lista
75. string = pred(&words, position-1);
76. if (string)
77. printf("El predecesor es: %s\n", string);
78. string = succ(&words, position-1);
79. if (string)
80. printf("El sucesor es: %s\n", string);
81. } /* Fin de la funcin main */
El cdigo C termina aqu
La funcin main contiene un simple pedazo de cdigo, para revisar cada funcin escrita
anteriormente. El programa completo de la estructura datos lista est listo cuando se
combina el main, las diferentes operaciones implementadas sobre la lista, los
#include requeridos y los prototipos de las funciones. La entrada y salida del
programa anterior es proporcionada a continuacin.
Entrada:
Ingrese una lista de palabras, termine con la palabra
'over':
program
computer
code
lines
algorithm
list
stack
over
Salida:
Lista de palabras despus de las inserciones:
program
computer
code
lines
algorithm
list
stack
Resumen
Ahora que ha completado esta unidad, Ud. debe ser capaz de:
Explicar el rol de estructuras de datos y algoritmos como bloques de
construccin en la mayora de programas de computadoras.
Introducir el concepto de estructura de datos.
Discutir las diferencias entre un tipo de dato y una estructura de datos.
Explicar el rol de estructura de datos para resolver problemas.
Discutir la estructura de datos lista.
Describir la lista como Tipo de Dato Abstracto.
Explicar cmo implementar una lista como un arreglo.
3) Cul de las siguientes son los principales ingredientes de cualquier esfuerzo para
resolver problemas?
a) Algoritmos
b) Estructura de datos
c) Ambos (a) y (b)
d) Ninguna de las anteriores
4) Una lista es una coleccin lineal de elementos de datos que pueden estar
ordenados o desordenados.
a) Verdadero
b) Falso
6) Qu operacin hace la funcin succ sobre el ltimo elemento de una lista dada?
a) El ltimo elemento
b) Un error
9) Cules de las siguientes operaciones sobre una lista pueden ser definidas usando
las operaciones primitivas nuevo e insertar?
a) esvacio
b) eliminar
c) encontrar
d) obtener
10) Para registrar los errores de un programa en C, se puede usar una estructura de
datos lista.
a) Verdadero
b) Falso
Hay otra implementacin de una estructura de datos lista llamada lista enlazada. Una
lista enlazada es una coleccin lineal de elementos de datos llamados nodos. Cada
nodo consiste de dos partes, la parte de la informacin y la parte de enlace, el cual
contiene un puntero al siguiente nodo.
El nombre lista enlazada se deriva del hecho de que cada nodo en una lista provee un
enlace al siguiente nodo. El fin de la lista se indica por un valor NULL en lugar de un
puntero al siguiente nodo. Este valor NULL es tambin referido como un puntero null.
En esta figura, la parte de informacin de cada nodo tiene dos piezas de informacin, el
nombre de la persona y la ciudad en la que la persona reside. La parte de informacin
de un nodo, en una lista, puede ser un entero simple u otra lista en s. Por ejemplo, la
parte de informacin puede contener simplemente un entero denotando la edad de una
persona, o una lista denotando las calificaciones de estudiantes en diferentes cursos en
una universidad. Esta lista puede ser un arreglo u otra lista enlazada.
La lista en la Figura 2.2 tambin es referida como lista enlazada simple, ya que el
enlace de un nodo a otro es posible en una sola direccin.
Usualmente, cada nodo en una lista enlazada est representado por una estructura que
contiene dos o ms miembros, uno de ellos definitivamente es el puntero al siguiente
nodo en la estructura. Los otros miembros de la estructura almacenan informacin
basada en la aplicacin para la cual se utiliza la lista enlazada. A continuacin se dan
unos cuantos ejemplos de estructuras en C:
Ejemplo 1
typedef struct node {
int data;
struct node *next;
} Node_type;
Ejemplo 2
typedef struct node {
int studentid;
char studentname[30];
struct node *next;
} Node_type;
Ejemplo 3
typedef struct node {
char name[30];
char city[20];
struct node *next;
} Node_type;
En todos los ejemplos anteriores, se consigue un campo en la definicin de la estructura
que se refiere a la estructura en s, struct node *next. De aqu que las listas
En una lista enlazada donde el ltimo nodo se denota por un valor null en su campo
next es fcil seguir la pista hasta el final de la lista. Normalmente, se usa para
reconocer el inicio de la lista, un puntero externo a la lista referido como cabecera
(header). Ver Figura 2.2.
Inicializar la cabecera con NULL indica que la lista est vaca, como se muestra a
continuacin.
header = NULL;
Los nodos de cabecera se les referencia algunas veces como anclas (anchors). El valor
en la variable header cambia en las siguientes instancias:
Cuando el primer nodo se aade a la lista: Se asigna a la cabecera la ubicacin
de memoria del nuevo nodo adicionado.
Cuando un nuevo nodo va a ser insertado al inicio de la lista: Se le asigna a la
cabecera la ubicacin de memoria del nuevo nodo.
Cuando el primer nodo en la lista es eliminado: Se le asigna a la cabecera el
valor del nodo siguiente al primer nodo eliminado.
Cuando la lista contiene un solo nodo y el nodo es eliminado: Se le asigna a la
cabecera NULL.
La siguiente declaracin en C se usar para un nodo en una lista enlazada, con la
finalidad de mostrar las diferentes operaciones:
El recorrido de una lista simplemente significa que se tiene que ir a travs de la lista,
visitando cada nodo en orden e imprimiendo la porcin de informacin de cada nodo.
Un nodo puede ser insertado en la lista ya sea antes o despus de un nodo existente en
la lista.
5. if (node == NULL)
6. return NULL; /*No puede insertar*/
7. ptr = getNode(elem);
8. if (ptr != NULL) {
9. ptr->next = node->next;
10. node->next = ptr;
11. }
12. return ptr; /* Retorna el nuevo nodo creado
*/
13. }
El cdigo C termina aqu
Se debe revisar si ptr == NULL antes de proceder. A ptr le ser asignado un valor
NULL cuando la funcin getNode() no es capaz de asignar memoria. Esto ocurre
cuando el sistema se queda sin memoria. Se ha incluido un if que revisa
cuidadosamente este problema. En la instancia del sistema que se queda sin memoria,
la funcin malloc retornar un valor NULL.
Paso 3: Si a ptr le es asignada la direccin del nuevo nodo, entonces se debe enlazar
a la lista. Esto se hace asignando el valor actual contenido en node->next en ptr-
>next. Al terminar esta operacin, la lista se ver como la Figura 2.6.
Una vez estudiado cmo insertar un nodo despus de un nodo dado, se discute a
continuacin cmo insertar un nodo antes de un nodo dado. Se ha visto que en una lista
enlazada simple, los punteros next siempre apuntan al siguiente nodo en la lista. Por lo
tanto, no hay manera de retroceder. Por esta razn, se necesita usar otra variable que
siempre est un paso atrs del nodo dado antes del cual el nodo debe ser insertado. Se
hacen las revisiones apropiadas al inicio de la funcin. El cdigo se presenta a
continuacin.
5. if (node == NULL)
6. return NULL;
7. if (head == NULL)
8. return NULL;
9. if (*head == NULL)
10. return NULL;
11.
12. ptr = getNode(elem);
13. if (ptr == NULL)
14. return NULL;
15. if (*head == node) {
16. ptr->next = *head;
17. *head = ptr;
18. }
19. else {
20. for (q = *head; q->next != node; q = q->next);
21. // Slo recorrido de la lista
22. ptr->next = q->next;
23. q->next = ptr;
24. }
25. return ptr; /* Retorna el nuevo nodo creado */
26. }
El cdigo C termina aqu
Ya que se necesita el puntero del nodo antes del nodo dado para que la insercin se
realice correctamente, la funcin insertBefore() (insertarAntes) toma el puntero de
la cabecera head como uno de los argumentos. El puntero de la cabecera de la lista es
pasado como un puntero a un puntero. Esto es porque cualquier cambio que afecte a la
cabeza de la lista en esta funcin, debe ser transmitido a la funcin que invoc.
Se declaran dos variables de puntero de Node_type, uno para obtener la direccin del
nuevo nodo y el otro para apuntar al nodo anterior al nodo dado. Despus de hacer
relevante las revisiones de los valores NULL, la funcin hace lo siguiente:
Si node y head son el mismo, entonces la insercin da lugar antes de la cabeza
de la lista y el nuevo nodo se convierte el primer nodo en la lista. Esto se hace
usando los dos siguientes pasos:
ptr->next = *head;
*head = ptr;
Un nodo puede ser eliminado de tres maneras: eliminar el nodo actual, eliminar el nodo
previo o eliminar el siguiente nodo.
Si el nodo previo ha de ser eliminado, el nodo de cabecera y el nodo cuyo nodo previo
debe ser eliminado se requieren como argumentos.
El cdigo para eliminar el nodo actual se presenta a continuacin. Esta funcin requiere
head y el node a ser eliminado como argumentos. head apunta al primer nodo de la
lista.
6. if (head == node) {
7. head = node->next; // Primer nodo
8. free(node);
9. return head;
10. }
11. /* Moverse en la lista */
12. for (ptr = head; ptr->next != node; ptr = ptr->next);
13. ptr->next = node->next;
14. free(node);
15. return ptr; // Retorna el nodo previo al nodo de
entrada
16. }
El cdigo C termina aqu
8. return (NULL);
9. }
10. if (node == NULL) { /* Error */
11. printf("\nPredecesor- Error de entrada: Nodo es
NULL\n");
12. return (NULL);
13. }
14. else
15. if (node == head) {/* Si es primer nodo en lista
*/
16. printf("\nNo existe predecesor para el
primer \
17. nodo en la lista!\n");
18. return (NULL);
19. }
20. else
21. for (ptr = head; ptr->next && \
22. ptr->next != node; ptr = ptr-
>next);
23. if (ptr->next == NULL) {
24. printf("\nPredecesor- Error de entrada: Nodo de
entrada no \
25. se encuentra en la lista\n");
26. return (NULL);
27. }
28. else
29. return ptr;
30. }
El cdigo C termina aqu
Se revisa para asegurar que no se est trabajando con punteros NULL. Luego se realiza
una revisin para ver si el nodo de entrada es el mismo que head. De ser as, entonces
es el primer nodo en la lista y un mensaje apropiado se imprime. De no ser as, se
recorre la lista hasta que se est un paso anterior al nodo que es pasado como
argumento de la funcin.
El siguiente cdigo presenta otra versin de la funcin predecesor que toma un valor
como entrada en vez de un nodo.
La funcin de sucesor toma como argumentos la cabecera de una lista y el nodo cuyo
sucesor debe ser encontrado. Retorna el nodo sucesor al nodo de entrada. La funcin
realiza las revisiones apropiadas. En esta unidad se proporciona como ejemplo solo una
versin de la funcin sucesor, la que toma el nodo como entrada para encontrar el
sucesor. La otra versin se deja como ejercicio al estudiante, basado en la funcin
provista para predecesor.
28. }
29. }
El cdigo C termina aqu
59. traverseList(head);
60. node1 = head->next->next->next;
61. temp = findPred(head, node1);
62. if (temp)
63. printf("\nPredecesor de %d es %d\n", node1-
>value,\
64. temp->value);
65. node1 = head->next->next;
66. temp = findSucc(head, node1);
67. if (temp)
68. printf("\nSucesor de %d es %d\n", node1->value,\
69. temp->value);
70. value = 125;
71. temp = findPredWithValue(head, value);
72. if (temp)
73. printf("\nPredecesor de %d es %d\n", value, \
74. temp->value);
75. value = 124;
76. temp = findPredWithValue(head, value);
77. if (temp)
78. printf("\nPredecesor of %d es %d\n", value, \
79. temp->value);
80. return 1;
81. }
El cdigo C termina aqu
Salida:
obtenerNodo: Creada una lista con valor 101!
101
Una lista enlazada simple permite el recorrido slo en una direccin, es decir, desde la
cabecera y de acuerdo al orden dictado por los punteros. No es posible usar una lista
enlazada simple en una aplicacin que requiera ser recorrida al revs. Se ha visto
tambin, que en la lista simplemente enlazada, la insercin de un nuevo nodo antes de
otro nodo o la eliminacin del mismo presentan problemas. Esto se debe a que se
requiere mantener dos punteros y recorrer la lista en orden para realizar estas
operaciones.
Una lista doblemente enlazada tambin es una coleccin lineal de nodos, donde el nodo
consiste de lo siguiente:
Un campo de informacin.
Un puntero next, apuntando al siguiente nodo en la lista.
Un puntero prev, apuntando al nodo anterior en la lista.
Debido a que la lista doblemente enlazada tiene dos enlaces, uno al nodo previo y otro
al siguiente nodo, permite ser recorrida en ambos sentidos, adems de acceder al
predecesor y sucesor inmediato de un nodo dado.
La Figura 2.7 muestra un nodo en una lista doblemente enlazada y la Figura 2.8
muestra un ejemplo de una lista doblemente enlazada.
Asuma que se est dando slo el ltimo nodo de una lista simplemente enlazada. No
hay manera de retroceder en la lista o ir a la cabeza de la lista.
La lista enlazada circular resuelve este problema. En una lista enlazada circular, el
ltimo nodo es conectado a la cabeza de la lista. En una lista enlazada circular, no hay
cabeza ni ltimo nodo y es posible moverse de un nodo a otro.
En la Figura 2.9, el puntero next en el ltimo nodo en la lista est apuntando al primer
nodo en la lista. Tambin se encuentra que el nodo cabeza est apuntando al ltimo
nodo de la lista. Usando esto, se puede obtener el primer nodo de la lista como sigue:
firstNode = head->next;
Las listas enlazadas circulares son tiles en aplicaciones donde el recorrido entre los
nodos es frecuente. La estructura para una lista circular es la misma que para una lista
enlazada simple. Cuando el primer nodo en la lista se crea, el puntero next se apunta a
s mismo.
head = getNode(101);
head->next = head;
Slo se necesita recordar que head apunta al ltimo nodo en la lista y head->next al
primer nodo de la lista. El resto de las operaciones permanecen las mismas como en la
lista enlazada simple.
Tcnica eficiente de Puede ser usado con cualquier Ninguna de las tcnicas de
ordenamiento tcnica de ordenamiento. Puede ordenamiento son eficientes.
usarse desde un ordenamiento Algunas tcnicas como merge
burbuja hasta un algoritmo sort o quicksort no estn
complejo como el quicksort. diseadas para ser usadas con
listas enlazadas.
Memoria Es empleada en aplicaciones que Se usa en aplicaciones que no
tienen restricciones de uso de tienen restricciones particulares
memoria. de uso de memoria y cuando la
memoria fsica es el nico lmite.
Tabla 2.1: Comparacin entre Arreglos y Listas Enlazadas
Resumen
Ahora que ha completado esta unidad, Ud. debe ser capaz de:
Explicar la necesidad de las listas enlazadas.
Describir las diferentes operaciones sobre una lista enlazada.
Discutir la implementacin de una lista simplemente enlazada.
Definir la lista doblemente enlazada y lista enlazada circulares.
Comparar la implementacin de una lista usando arreglo y lista enlazada.
8) Se tiene una lista enlazada simple que tiene los siguientes elementos:
K H I L M O P
Si head apunta a K, Cul es el resultado de head->next->next->next?
a) H
b) L
c) O
d) Null
Ejercicio de Laboratorio
Considere una lista enlazada que contiene enteros positivos.
Escribir:
Las funciones apropiadas para las operaciones en la lista enlazada.
Segmentos de programas para realizar los requerimientos especficos.
Un programa completo en C.
Tomando en cuenta las siguientes tareas:
1) Tomar tantos enteros positivos como sea posible como entrada y crear la lista
inicial hasta que el usuario ingrese el valor -9999 para terminar la entrada.
2) Imprimir la lista de la lista enlazada en el orden en que fueron ingresados.
3) Escribir una funcin llamada odd_print()que imprima slo los nmeros impares
en la lista.
4) Escribir una funcin llamada find_max()para encontrar el mximo entero en la
lista enlazada y que retorne el valor mximo.
5) Escribir una funcin llamada find_pos(x)que retorne la posicin de x en la lista
6) Mostrar el valor mximo en la lista y su posicin.
Tareas Opcionales:
Unidad 4: Pila
Objetivos de Aprendizaje
Al final de esta unidad, Usted ser capaz de:
Definir la estructura de datos de pila.
Explicar las diferentes operaciones definidas en una pila.
Describir las operaciones del TDA Pila.
Explicar la implementacin de una pila usando un arreglo y una lista enlazada.
Discutir el uso de las pilas en la resolucin de problemas.
1. Pilas
Las listas y los arreglos permiten que un elemento sea insertado o eliminado de
cualquier lugar arbitrario dentro de la estructura. Sin embargo, hay muchas situaciones
que requieren que los elementos se inserten y eliminen slo del comienzo o el final de la
lista. Una pila es una de las estructuras de datos, que permite que los elementos sean
aadidos o eliminados slo por un lado. Las pilas son comunes en la vida real; se tienen
pila de platos, pila de servilletas, pila de libros, pila de dlares, pila de peridicos. Ver
Figura 4.1.
El final donde los elementos son aadidos o eliminados se conoce como tope (top) de
la pila. En una pila, los elementos que son aadidos de ltimos son los primeros en ser
removidos. De aqu que, las pilas tambin son conocidas como listas ltimo en Entrar,
Primero en Salir (LIFO siglas en ingls).
Las dos operaciones primitivas de una pila, new y push ayudan en la definicin de las
otras operaciones. Matemticamente, todas las otras operaciones de pila pueden ser
definidas en trminos de estas dos operaciones primitivas.
La operacin new toma S como argumento, mientras que la operacin push toma los
argumentos S y element.
Habiendo discutido las operaciones a nivel TDA para la pila, se define a continuacin la
operacin pop usando las dos operaciones primitivas.
Ahora, considere push(S,element) para una pila S donde S no es una pila nueva, si
lo fuera, colocar (push) element dentro de ella la hace no-vaca. Por lo tanto, sacar
(pop) del tope de la pila S que tiene element colocado en ella, debe dar pila vaca.
element puede ser removido usando la operacin pop de la siguiente manera:
pop(push(S,element)) = S
pop(push(S,element)) da como resultado S dado que el ltimo elemento insertado en
S (ej. element) es el que se quita. Notar que esto explica la operacin claramente sin
tener que entrar en especificaciones de la implementacin.
Para explicar las tres operaciones, llamadas pop, isempty y top, se usa la pila
llamada myStack.
Ahora, se crea una nueva pila llamada myStack. Observe que cuando una pila es
creada usando la operacin new slo se crea una pila vaca
Pasando esta nueva pila a pop generar un error, ya que no se puede sacar nada de
una pila vaca.
Ahora si la pila no-vaca myStack se pasa como argumento a pop, la operacin pop
elimina el tope de la pila, la cual en esta instancia es 200, ya que es el nico elemento
en la pila. Con la extraccin (pop) del nuevo elemento insertado 200, el estado de la pila
vuelve a ser el anterior, la pila vaca.
Ahora, asuma que myStack no est vaca y tiene los siguientes elementos:
100 105 240 210
210 es el elemento tope. Sin embargo, push(myStack, 200) retornar myStack con
200 como elemento tope. Cuando esta nueva pila myStack se pasa a la operacin pop,
remueve 200, retorna una pila con los siguientes elementos:
100 105 240 210
Esta pila es la misma que fue pasada como argumento a push. El estado de myStack
vuelve a ser el estado anterior, una pila con cuatro elementos.
Una pila new no contiene elementos y por lo tanto, el elemento top no existe o no est
definido. top(new) es un error ya que no existe elemento que retorne el valor tope.
Esto se escribe de la siguiente manera:
top(new) = error
Considere la pila que resulta de push(S,element). Colocando (push) element en la
pila S significa que element se convierte en el top de la pila. As que para obtener top
de la pila, en este caso se hace lo siguiente:
top(push(S,element)) = element
La operacin anterior implica que el elemento element se inserta en el top de la pila.
Considere de nuevo el ejemplo de myStack. Cuando myStack est vaca, top retorna
un error ya que una lista vaca no puede tener ningn elemento.
top(new) = error
Ejemplo para ilustrar top usando push en una Pila Vaca
Si myStack est vaca, entonces el colocar (push) el elemento 200 en myStack resulta
en que myStack tiene slo el elemento 200. Cuando myStack con 200 se pasa a top,
sta retorna 200 que es el elemento element colocado (push) de ltimo en myStack.
Si myStack inicialmente tiene 100, 105, 240 y 210, se realiza push(myStack, 200),
donde 200 es el elemento, los elementos en la pila despus de colocarlos son:
100 105 240 210 200
200 ser el tope de la pila. Cuando esta nueva myStack se pase a la operacin top,
retornar 200, que fue el ltimo elemento element insertado (push) en myStack.
Tomando el mismo ejemplo de myStack, se puede ver que una nueva pila es vaca, as
resulta en un valor verdadero la operacin isempty.
Para definir isempty en push, se observa ambas condiciones, myStack siendo vaca
y no-vaca.
Cuando myStack es vaca, aadir un elemento 200 lo hace no-vaca. Esta pila no-vaca
se pasa a la operacin isempty, la cual retorna false.
En una pila no-vaca, aadir otro elemento no altera el estado de la pila. De aqu que
isempty retorna false.
Por lo tanto, basado en el razonamiento anterior para pop, top e isempty, se pueden
escribir reglas para las operaciones de pila como sigue:
Para todo S y element, lo siguiente ser vlido:
pop(new) = error
pop(push(S,element)) = S
top(new) = error
top(push(S, element)) = element
isempty (new) = true
isempty (push(S, element)) = false
Las reglas de las operaciones pop, top e isempty se declaran en trminos de los
operadores primitivos new y push. Estas reglas se denominan axiomas.
5.
6. // definicin de pila
7. // Contiene top que referencia el elemento top
8. // Contiene una pila de arreglo
9. typedef struct stacker {
10. int top;
11. Element_type stack[STACKMAX];
12. } Stack_type;
El cdigo C termina aqu
La Operacin pop
La Operacin top
No se est decrementando top pero slo retornando el valor de top-1. Esta operacin
es similar a la operacin pop. Sin embargo, retorna el elemento top de la pila sin
eliminarlo de la pila. Tambin note que st_ptr->top no cambia.
Hay varias ventajas para usar funciones separadas para implementar las diferentes
operaciones sobre las pilas. En la implementacin de pilas usando arreglos, la
naturaleza de las operaciones es simple. Sin embargo, se desea declarar y usar una
estructura para una pila, adems de tener funciones separadas para implementar las
operaciones. Esto es porque, en un problema grande, es mejor tenerlas como
funciones, en lugar de repetir cdigo por todos lados. Suponga que se consigue una
mejor implementacin (que arreglos), el cambio se localizar slo en estas funciones. El
uso de nombres de funciones tales como push, pop o top harn el programa ms
legible. La separacin de estructuras de datos de su implementacin tambin ayuda a
un diseo top-down.
La funcin main toma la entrada del usuario y la coloca en la pila. Luego imprime el
elemento tope de la pila y quita todos los elementos de la pila. Por lo tanto, la pila estar
vaca al final de la funcin main. Se ha definido STACKMAX a 100. Si STACKMAX es
reducido a cinco, el programa ignora las entradas despus de los primeros cinco
nmeros. Esto se toma en cuenta en la funcin push, donde se aade a la pila slo si no
est llena. A continuacin se da la entrada y salida del programa.
Entrada:
Ingrese nmeros a la pila, finalice con -9999:
-1
0
-100
201
345
10003
89
-76
-9999
Salida:
Pila completamente llena con nmeros!
El elemento tope es: -76
89
Ejemplo 4.1
Asuma que se necesita aceptar una lnea de caracteres como entrada e imprimirlos en
orden invertido. Para lograr esto, los caracteres se leen como entrada y se colocan en la
pila. Luego se quitan de la pila. Salen en orden invertido e impresos en ese orden.
Anteriormente se tena el tipo definido Element_type para ser tipo int. Para esta
funcin se necesita cambiar Element_type a:
typedef char Element_type;
El cdigo en C empieza aqu
1. void reverseAndPrint() {
2. Element_type elem;
3. /* Una pila para contener los caracteres de entrada */
4. Stack_type myStack;
5.
6. /* Crear una pila vacia */
7. newStack(&myStack);
8.
9. /* Ingreso */
10. printf("Ingrese la cadena a invertir:\n");
11. /* Bucle para tomar la entrada y colocar cada carcter
en la
12. pila */
13. scanf("%c", &elem); // Primer carcter
14. while (elem != '\n') {
15. /* Colocar el carcter en la pila */
16. push(&myStack, elem); // Siguiente carcter
17. scanf("%c", &elem);
18. }
19. /* En este punto los caracteres estn en la pila */
20.
21. /* Imprimir la cadena en orden inverso */
22. printf("\nLa cadena invertida es:\n");
23. /* Bucle para sacar elementos de la pila */
24. /* mientras la pila no este vacia */
25. while (!isEmpty(&myStack)) {
26. /* Quitar el elemento tope de la pila */
27. elem = pop(&myStack);
28. /* Imprimir el valor del elemento */
29. printf("%c",(char) elem);
30. }
31. /* Imprime una nueva lnea al final */
32. printf("\n");
33. }
El cdigo C termina aqu
Suponga que el texto PHANTOM es la entrada y se debe tener la salida como MOTNAHP.
Si la entrada es MADAM entonces la salida debe ser MADAM. Si se invoca a
reverseAndPrint() desde main, se obtiene un mensaje de ingresar una cadena. La
cadena invertida se muestra de nuevo con el mensaje que se muestra a continuacin.
Una vez aprendido cmo implementar una pila usando un arreglo, se discute cmo
implementar pilas usando listas enlazadas.
// Definir un nodo
typedef struct node {
Element_type info;
struct node *next;
} Node_type;
Una pila es un tipo especial de lista, en la que slo un lado es considerado visible.
Todas las operaciones ocurren en este lado final visible. Cuando se usan listas
enlazadas como mtodo de implementacin, se debe saber si el final o el comienzo de
la lista que representa el tope de la pila.
Una vez que se tiene top, se sabe como hay que moverse al primer elemento de una
lista enlazada, la cual tambin es el tope de la pila. Despus de eso, acceder a todos los
elementos de la pila es directo.
} Stack_type;
Los prototipos de las funciones de pila se dan a continuacin.
La funcin main escrita para la implementacin del arreglo se puede usar para la
implementacin de la lista enlazada, casi sin cambios.
5. Aplicaciones de Pilas
Hay un nmero de aplicaciones que requieren la pila como estructura de datos. Se
presenta a continuacin una lista de dichas aplicaciones en orden creciente de
complejidad.
Hay muchas aplicaciones de procesamiento de cadenas (string) donde las pilas son
estructuras de datos vitales. Un ejemplo simple es la deteccin de cadenas palndrome.
Una cadena es palndrome (o un nmero) cuando los caracteres individuales se leen
igual en ambas direcciones.
Cuando los programas son escritos en un lenguaje de alto-nivel como C o C++, se hace
uso de las expresiones aritmticas. Estas expresiones aritmticas usan parntesis. Una
de las funciones importantes del anlisis sintctico es revisar si los parntesis estn
balanceados en las expresiones aritmticas. En otras palabras, se debe revisar si los
parntesis izquierdos y los parntesis derechos concuerdan en nmero y tambin en la
forma de anidarlos. Se puede emplear una pila para realizar esta revisin.
Una expresin aritmtica que ha sido convertida a notacin postfija se puede evaluar
fcilmente usando una pila.
Cuando una funcin se invoca, los parmetros deben ser estar disponibles para el
programa que invoca. Despus de que la ejecucin de la funcin se completa, el control
debe retornar a la sentencia siguiente a la invocacin de esa funcin. Esto requiere
hacer disponible los parmetros a la funcin llamada y mantener el estado del progreso
(incluyendo direccin de retorno). Las pilas son las estructuras de datos que
principalmente se usan para soportar el mecanismo de llamada y retorno de una funcin
o procedimiento.
A continuacin se aprender el uso de las pilas en una aplicacin. Uno de los usos ms
comunes y significativos de una pila es evaluar expresiones aritmticas. Una expresin
aritmtica se representa de la siguiente forma:
a + b c * d + e / f
Una expresin aritmtica simple a+b puede ser fcilmente evaluada, ya que slo hay
dos operandos y un operador. Pero a medida que se agregan ms operandos y
operadores a la expresin, se hace ms difcil evaluarla programticamente. La
dificultad se da no slo por el nmero de operandos y operadores, sino tambin debido
a la precedencia de operadores. Por ejemplo, sea la siguiente expresin aritmtica:
a * b (c + d) * (e f)
Se sabe que las expresiones entre parntesis c+d y e-f se evalan antes que el resto
de los operadores aplicados a los operandos. As, es necesario recordar los resultados
de c+d y e-f cuando la expresin completa se evala. La evaluacin lgica entera se
vuelve cada vez ms complicada.
Las expresiones se usan normalmente en la forma llamada infija. Para dar una solucin
a la evaluacin de expresiones programticamente, estas expresiones infijas se
convierten al formato postfijo. El nombre infija viene porque los operadores se colocan
entre los operandos. En una operacin postfija, los operadores siguen a los operandos a
los cuales aplican.
Una expresin en forma infija tambin puede ser convertida en forma prefija. En este
caso, los operadores vienen antes de los operandos. La notacin prefija slo se
menciona para completar el concepto. Una discusin del tema va ms all del alcance
de este curso.
A continuacin se presentan algunos ejemplos para entender las diferencias entre las
tres formas.
Ejemplo 1
infijo - a + b
postfijo - a b +
prefijo - + a b
En la forma postfija se tiene al operador + despus de los operandos a y b.
Ejemplo 2
infijo - a + b c
postfijo - a b + c
prefijo - - + a b c
En la expresin anterior, el operador con menor precedencia es -. a+b se evala antes y
el resultado de a+b se usa en la operacin de substraccin.
Ejemplo 3
infijo - a + b * c
postfijo - a b c * +
prefijo - + a * b c
En esta expresin el operador con menor precedencia es el +, el cual ser usado sobre
a y el resultado de b*c. As, se observa al final de la forma postfija y al inicio de la
forma prefija.
Ejemplo 4
infijo - a + b * (c d)
postfijo - a b c d - * +
prefijo - + a * b c d
En esta expresin se han introducido parntesis. El orden de la operacin ser
substraccin (debido a que est dentro de los parntesis), seguido por la multiplicacin
y la adicin.
Ejemplo 4.2
108. }
109. }
110. /* Revisar tokens vlidos que siguen
111. un parntesis abierto */
112. if (prevSymbol == '(') {
113. if (token != '(' && !isOperand(token)) {
114. printf("Expresin invlida!\n");
115. return 0;
116. }
117. }
118. /* Revisar tokens vlidos que siguen
119. un parntesis cerrado */
120. if (prevSymbol == ')') {
121. if (token != ')' && !isOperator(token)) {
122. printf("Expresin invlida!\n");
123. return 0;
124. }
125. }
126. /* Revisar que los parntesis concuerden */
127. /* Colocar en la pila el token como un parntesis
128. abierto */
129. if (token == '(')
130. push(&stack,token);
131. /* Sacar el parntesis abierto de la pila si el
132. token es un parntesis cerrado */
133. if (token == ')') {
134. if (!isEmpty(&stack))
135. /* Sacar parntesis abierto */
136. pop(&stack);
137. else {
138. /* Cuando cierra parntesis ms que
abiertos */
139. printf("Expresin invlida!\n");
140. return 0;
141. }
142. }
178. i++;
179. }
180. /* Alcanzar este punto en el algoritmo significa que
181. la expresin es vlida excepto por revisin de
parntesis
182. Se hace eso a continuacin. Si la pila no esta vaca,
183. Significa que hay parntesis extras abiertos o cerrados
*/
184. if (!isEmpty(&stack)) {
185. printf("Expresin invlida!\n");
186. return 0;
187. }
188. printf("La expresin de entrada es VALIDA!\n\n");
189. /* Muestra los identificadores usados en la expresin
*/
190. /* Remueve los duplicados antes de imprimirlos */
191. removeDuplicatesChar(identifiers);
192. printf("Identificadores: ");
193. if (nIden == 0)
194. printf("Ninguno\n\n");
195. else {
196. for (j =0; j < nIden; j++)
197. // No imprime si es colocado en 0
198. if (identifiers[j] != 0)
printf("%c ", identifiers[j]);
199. printf("\n\n");
200. }
201. /* Muestra las constantes usadas en la expresin */
202. /* Remueve duplicados antes de imprimir */
203. removeDuplicatesInt(constants, nCon);
204. printf("Constantes: ");
205. if (nCon == 0)
206. printf("Ninguno\n\n");
207. else {
208. for (j = 0; j < nCon; j++)
209. if (constants[j] != 0)
210. printf("%d ", constants[j]);
211. printf("\n\n");
212. }
213. /* Muestra operandos usados en la expresin */
214. /* Remueve duplicados antes de imprimir */
215. removeDuplicatesChar(operators);
216. printf("Operadores: ");
217. if (nOp == 0)
218. printf("Ninguno\n\n");
219. else {
220. for (j = 0; j < nOp; j++)
221. printf("%c ", operators[j]);
222. printf("\n\n");
223. }
224. return 0;
225. } /* Fin del programa principal */
El cdigo C termina aqu
El cdigo principal es auto-explicativo. Las otras funciones que se escribieron para este
programa se dan a continuacin.
/* Otras funciones */
1. /* Funcin que remueve duplicados de un arreglo de
caracteres */
2. void removeDuplicatesChar(char *input) {
3. int i, j, length;
4. char value;
5. length = strlen(input);
6. for (i = 0; i < length; i++) {
7. value = input[i];
8. for (j = i + 1; j < length; j++)
9. if (input[j] == value)
10. input[j] = 0; /* Colocandolo en 0 */
11. }
12. } /* Fin de la funcin */
13.
14. /* Funcin que remueve duplicados de un arreglo de
enteros */
15. void removeDuplicatesInt(int *input, int noOfItems) {
49. int i;
50. /* Revisa si el operador de entrada es vlido */
51. /* Retorna verdadero si es vlido, de lo contrario
falso */
52. for (i = 0; i < 5; i++)
53. if (op == operators[i])
54. return verdadero;
55. return falso;
56. }/* Fin de la funcin */
El cdigo en C termina aqu
Use las funciones anteriores junto con las funciones de pila que se escribieron
anteriormente. La entrada y salida del programa se dan a continuacin:
Entrada:
Introduzca una expresin ... operadores vlidos: +,-,*,/,%
a + (b - c) + d 40
Salida:
Introduzca una expresin ... operadores vlidos: +,-,*,/,%
a + (b - c) + d - 40
Identificadores: a b c d
Constantes: 40
Operadores: + -
Fin del Ejemplo 4.2
Se observa en el ejemplo anterior que escribir una solucin para evaluar una versin
simple de una expresin aritmtica es un poco compleja. Idealmente, las formas infijas
se convierten a notacin postfija. Aunque la conversin de infija a postfija parezca
compleja, usando una pila para realizar la conversin lo hace ms fcil. Una vez que se
tiene la expresin en forma postfija, se evala (en lugar de la forma infija) para obtener
el resultado. A continuacin se presentan los pasos para convertir formas infija a
postfija. Escribir el cdigo C para esto se puede realizar como un ejercicio.
Usando una pila, se puede convertir una expresin de forma infija a postfija. Para
entender como esto se hace se asume lo siguiente:
Los operadores son +, *, /,-, y ().
+ tiene igual precedencia que .
*, / tienen mayor precedencia sobre + y .
() tiene la ms alta precedencia.
Token de
Aadido a la
la Cadena En la Pila Comentario
Cadena de Salida
de Entrada
Operando aadido a la cadena de
x1 x1
salida.
2
2 Operando colocado en la pila..
15
+ es un operador binario. Sacar (pop) los 2
+ 17 elementos del tope, realizar la operacin
15+2 y almacenar el resultado en la pila.
10
10 Operando colocado en la pila.
17
3
3 10 Operando colocado en la pila.
17
2
3
2 Operando colocado en la pila.
10
17
6 * es un operador binario. Sacar los 2
* 10 elementos del tope, realizar la operacin
17 3*2 y almacenar el resultado en la pila.
- es un operador binario. Sacar los 2
4
- elementos del tope, realizar la operacin 10
17
- 6 y almacenar el resultado en la pila.
* es un operador binaria. Sacar los 2
* 68 elementos del tope, realizar la operacin 17
* 4 y almacenar el resultado en la pila.
Sacar el contenido de la pila, ese es el
Fin de cadena
resultado de la expresin postfija.
Resumen
Ahora que ha completado esta unidad, Ud. debe ser capaz de:
Definir la estructura de datos pila.
Explicar las diferentes operaciones definidas en la pila.
Describe las operaciones del TDA Pila.
Explica la implementacin de una pila usando un arreglo y una lista enlazada.
Discutir el uso de las pilas en la resolucin de problemas.
3) Una lista de empuje hacia abajo (pushdown list) es otro nombre para cul de los
siguientes:
a) Una lista enlazada
b) Una cola
c) Una lista simple
d) Una pila
4) Cul de las siguientes son desventajas de implementar una pila como un arreglo?
a) El tamao de la pila es finito
b) El tamao de la pila es fijo
c) El tamao de la pila puede ser configurado dinmicamente
d) Ambas a y b
5) Una pila puede contener slo tipos de datos atmicos como integer, float, etc.
a) Verdadero
b) Falso
8) Sera apropiado usar una pila para almacenar elementos perecederos tales como
vegetales y carne de un supermercado?
a) Verdadero
b) Falso
9) Cuando se implementa una pila como lista enlazada, cul de los siguientes
representan una ventaja?
a) Provisin de una estructura esttica de datos
b) Provisin de una estructura dinmica de datos
c) El tamao de la pila no necesita ser determinado cuando se escribe un
programa
d) Ninguna de las anteriores
10) Las pilas son tiles en la evaluacin de expresiones aritmticas, si la entrada est
en la forma infija.
a) Verdadero
b) Falso
Ejercicios de Laboratorio
Una de las tareas que un compilador realiza para cualquier lenguaje de programacin
es determinar si las llaves que se abren { concuerdan en nmero con las llaves que se
cierran }. Esto es una revisin que cualquier compilador realiza. Escribir un programa
en C que tome una entrada de datos y revise que las llaves concuerden y muestre lo
siguiente:
Cuando las llaves que abren son ms que las llaves que cierran en el programa:
Error: No hay concordancia de parntesis que cierran
Cuando las llaves que cierran son ms que las llaves que abren en el programa:
Error: No hay concordancia de parntesis que abren
Cuando los parntesis que abren y cierran concuerdan:
Los parntesis que abren y cierran concuerdan
Tambin mostrar el nmero total de lneas ledas y el nmero de llaves que abren y
cierran encontrados en el programa, de la siguiente manera:
El nmero total de lneas ledas es 125
El nmero total de llaves que abren es 13
El nmero total de llaves que cierran es 12
Consejos tiles:
Usar la pila para proveer la estructura de datos correcta para solucionar el
problema.
Usar la pila para colocar las llaves que abren.
Cuando se encuentran llaves que cierran, sacar las llaves que abren de la pila.
Salir del programa cuando se encuentre la primera incongruencia.
Recordar los siguientes puntos:
- Una concordancia ocurre cuando las ltimas llaves que cierran se encuentran y
una operacin pop se realiza en la pila. La pila est vaca.
- Cuando un parntesis es encontrado y no hay nada para sacar de la pila,
significa que hay menor nmero de llaves que abren comparado con las llaves
que cierran.
- Al final del archivo, si la pila no est vaca, significa que hay menor nmero de
llaves que cierran comparados con las llaves que abren.
Unidad 6: Colas
Objetivos de Aprendizaje
Al final de esta unidad, usted ser capaz de:
Definir la estructura de datos de cola.
Explicar las operaciones del TDA en cola.
Discutir la implementacin de una cola como arreglo.
Explicar las implementaciones de una cola como arreglo circular.
Describir la implementacin de una cola como lista enlazada.
1. Preliminares de Cola
En el lenguaje comn, una cola es una lnea de espera. Normalmente, la primera
persona o elemento de la cola ser el primero en ser atendido. Se puede definir una
cola, en lenguaje de computacin, como una lista en la que sus elementos se insertan
en un extremo de la lista y se retiran del otro extremo. Una cola tambin se denomina
una lista primero en entrar, primero en salir o simplemente FIFO (First-In First-Out).
Debido a que una cola maneja la llegada y el retiro de elementos, ambos extremos son
importantes. Observe la Figura 6.1 que ilustra la representacin de una cola.
dequeue(new(queue)) = error
Ahora se va a comprender la operacin dequeue en trminos de enqueue(queue,
element). Se puede notar que queue puede ser cualquier cola.
Si queue est vaca, la operacin enqueue(queue, element) generar una cola
con slo un elemento denominado element. Cuando se ejecuta la operacin dequeue
sobre queue, el elemento element se retira y se devuelve la cola vaca.
Esta parte de la operacin se puede escribir como:
dequeue(enqueue(queue, element)) =
if isempty(queue) then new (queue)
Sin embargo, si queue no est vaca, entonces enqueue(queue, element)
permitir que queue resulte con element agregado al final de la cola. El resultado es el
mismo que dequeue(enqueue(queue, element)). Esto implica que enqueue y
dequeue estn operando sobre puntos independientes de la cola.
Nota: Sin este axioma, no se tendr forma de figurar que enqueue y dequeue estn
operando en puntos independientes de la cola, es decir, en la cabeza y el final de la
cola.
Por lo tanto, la operacin dequeue se puede escribir completamente como:
dequeue(enqueue(queue, element)) =
if isempty(queue) then new(queue)
else
enqueue(dequeue(queue, element))
Se intentar comprender esto con un ejemplo. Se utilizar una cola de ejemplo
denominada myQueue para explicar las operaciones sobre la cola utilizando las
operaciones bsicas.
Se va a crear una nueva cola llamada myQueue. Cuando se crea una cola utilizando la
operacin new, slo se crea una cola vaca. Aqu la operacin new sobre myQueue
devuelve un myQueue vaco. Cuando se pasa esta myQueue vaca a la operacin
dequeue devolver un error al no poder eliminar un elemento de una cola vaca.
cola, la operacin dequeue lo retira y revierte la cola a su forma original, es decir, una
cola vaca.
dequeue(enqueue(myQueue, element)) =
if isempty(myQueue) then new(myQueue)
La operacin anterior slo es un mtodo de declaracin que cuando se pasa una
myQueue vaca a enqueue y despus a dequeue, es equivalente a new(myQueue), ya
que el lado izquierdo y derecho del operador = termina en un myQueue vaco.
Suponga que myQueue no est vaca y actualmente presenta los siguientes nombres:
Se va a asumir que myQueue no est vaca y tiene los siguientes cuatro elementos:
Lydia Sam Bill Martin
Lydia est al frente de la cola. Si myQueue se pasa como argumento a enqueue, y se
agrega Christopher, la cabeza de la cola myQueue todava es Lydia. Al agregar
Christopher a myQueue, en la cabeza todava est Lydia porque la adicin se
ha llevado a cabo al final de la cola.
front(enqueue(myQueue, Christopher)) = Lydia
Tomando el mismo ejemplo de myQueue, se puede ver que una nueva pila est vaca,
as resulta el valor true con la operacin isempty.
front(new(queue)) = error
front(enqueue(queue, element)) =
if isempty(queue) then element
else
front(queue)
isempty(new(queue)) = true
isempty(enqueue(queue, element)) = false
A continuacin se va a seguir con la implementacin de colas teniendo en cuenta la
comprensin de las operaciones que se han aprendido. Primero se implementar una
cola como arreglo.
Se tienen dos variables definidas como parte de la estructura de la cola, una para
indicar el frente o cabeza de la cola y otra (rear) para indicar el final de la cola.
A continuacin se dan las implementaciones para las operaciones sobre una cola.
En seguida se dan las implementaciones para las operaciones de cola. Al nivel TDA se
utilizan enqueue y dequeue para insercin y eliminacin respectivamente.
Para insertar un elemento en una cola, se verifica primero si la cola est llena.
Dado que esto es una implementacin como arreglo, no se cambia el valor de front. El
valor de rear se incrementa en 1 cada vez que se agrega un elemento a la cola.
Se tendrn que desplazar elementos del arreglo cada vez que se retire un elemento de
la cola.
1. /* Eliminar un elemento de Q */
2. Element_type dequeue(Queue_type *q_ptr) {
3. Element_type element;
4. int i;
5. if (isempty(q_ptr))
6. return -1;
7. else {
8. element = q_ptr->queue[q_ptr->front];
9. q_ptr->rear--;
10. for (i = 0; i <= q_ptr->rear; i++)
11. q_ptr->queue[i] = q_ptr->queue[i + 1];
12. return element;
13. }
14. }
El cdigo C termina aqu
Esta funcin requiere un manejo cuidadoso. Note que cada vez que se elimina un
elemento de la cola, se desplazan los dems elementos. Por eso no se cambia el valor
de front durante las operaciones de cola. Sin embargo, el valor de rear se
decrementa.
4. return -1;
5. else
6. return q_ptr->queue[q_ptr->front];
7. }
El cdigo C termina aqu
Estas dos funciones son requeridas por otras funciones para verificar cundo la cola
est vaca o llena (Empty y Full).
sizeOfQueue es una funcin muy simple que se utiliza para encontrar la longitud de la
cola. Una sugerencia para escribir la operacin es que esta funcin verifique la
condicin isempty
3. Element_type elem;
4.
5. newQueue(&queue);
6.
7. printf("Introduzca elementos (caracteres) a almacenar
en la cola:\n");
8. while ((elem = getchar()) != '\n') {
9. enqueue(&queue, elem); // Insertar en la cola
10. printf("\tEl elemento ingresado en la cola es
:%c\n",elem);
11. }
12. printf("\nEliminando elementos de la cola:\n");
13. while (!isempty(&queue)) {
14. elem = dequeue(&queue); // Elimina de la cola
15. printf("El elemento eliminado es %c\n", elem);
16. }
17. if (dequeue(&queue) == -1)
18. printf("\nLa cola esta vaca: No puede realizar \
19. la operacin eliminar!\n");
20. return 1;
21. }
El cdigo C termina aqu
Operaciones de Cola
Insertar: lotus
Insertar: rose
Insertar: orchids
Eliminar
Insertar: hyacinth
Insertar: lily
Insertar: daisies
Eliminar
Eliminar
Insertar: marigold
Insertar: bluebells
Primer mtodo
La Figura 6.2 muestra los diferentes estados de la cola para las 11 operaciones de cola
dadas anteriormente. Se puede notar que cada eliminacin (4, 8 y 9 en la Figura 6.2)
desplaza elementos de la cola. De este modo, hay un recorrido involucrado en cada
eliminacin. En cada eliminacin front queda en la posicin 0.
Segundo Mtodo
En la Figura 6.3 se observa que las posiciones desde las que se retiran elementos,
quedan vacantes. Cada eliminacin cambia el valor de front. En esta figura, el valor
de front ha sido cambiado en 4, 8 y 9. Con dos inserciones ms, la cola estar llena
incluso aunque las posiciones del frente del arreglo estn vacantes.
De manera similar, en una representacin de arreglo circular, se considera que una cola
est llena cuando front est un paso adelante de rear. Observe la Figura 6.5.
La Figura 6.5 muestra una cola vaca y una cola llena, donde front y rear estn
exactamente en la misma situacin.
La Figura tambin muestra la desventaja inherente de arreglos circulares al describir
una cola vaca o llena.
Para distinguir entre una cola vaca y una cola llena, se pueden adoptar una de las
siguientes soluciones:
Se pueden tener variables booleanas que indiquen si la cola est llena o vaca.
Se puede dejar explcitamente una celda en blanco entre front y rear. As, la
cola estar llena cuando haya una celda vaca entre front y rear.
Se pueden usar nmeros negativos para representar front y/o rear e indicar
que una cola est vaca. Nuevamente, aqu es importante mantener el tamao
de la cola.
Nota: No se discutirn sobre cmo se implementan estas soluciones ya que esto va
ms all del alcance de este curso.
Aqu se muestran los diversos prototipos de funciones para las operaciones sobre colas.
/* Prototipos de Funciones */
Node_type *createNode(Element_type);
void newQueue(Queue_type *);
boolean isEmpty(Queue_type *);
Element_type front(Queue_type *);
void enqueue(Queue_type *, Element_type);
Element_type dequeue(Queue_type *);
La operacin newQueue crea una cola nueva colocando front y rear a NULL.
Simplemente se prueba si la cola est vaca, en cuyo caso devuelve error. Si la cola no
est vaca, devuelve directamente el front de la cola como (queue->front)->info.
Agregar un elemento a la cola depende de si la cola est vaca o no. Si est vaca, se
puede agregar al frente de la cola, sino necesita agregarse al final de la cola.
Cuando la cola est vaca, no hay nada que retirar. En este caso, se devuelve un error.
Si hay slo un elemento en la cola, entonces la cola llega a estar vaca. En caso
Se tiene una funcin main que muestra el uso de las diversas operaciones de colas. La
funcin main se parece a la que se escribi para la implementacin de una cola como
arreglo, con algunos cambios menores para manejar enteros en lugar de obtener
caracteres como entrada.
5. newQueue(&queue);
6.
7. printf("Introduzca los elementos (numeros) a almacenar
en la \
8. cola, finalice con -9999\n");
9. scanf("%d", &elem);
10. do {
11. if (elem == -9999)
12. break;
13. enqueue(&queue, elem); // Insertar en queue
14. printf("\t El elemento ingresado en la cola es
:%d\n",(&elem));
15. scanf("%d", &elem);
16. } while (elem != -9999);
17.
18. printf("\nEliminando elementos de la cola:\n");
19. while (!isempty(&queue)) {
20. elem = dequeue(&queue); // Retirar de queue
21. printf("El elemento eliminado es %d\n", elem);
22. }
23. if (dequeue(&queue) == -1)
24. printf("\nLa cola est vaca: No puede realizar \
25. la operacin eliminar!\n");
26. return 1;
27. }
El cdigo C termina aqu
A continuacin se muestra la entrada y salida del programa usando una cola como lista
enlazada:
Entrada:
Introduzca los elementos (numeros) a almacenar en la cola,
finalice con -9999
198
El elemento ingresado en la cola es :198
201
El elemento ingresado en la cola es :198
302
5. Aplicaciones de Colas
A continuacin se discuten algunas aplicaciones de colas.
Hay diversas aplicaciones en las que los dispositivos y/o procesos se comunican unos a
otros. Debido a la diferencia en las velocidades de sus operaciones, hay la necesidad
de almacenar los datos que estn siendo transferidos entre ellos. Las colas son una
opcin obvia a usarse para tales aplicaciones. De hecho, todos los buffers son
conceptualmente colas.
Las colas son estructuras de datos naturales que se usan para la simulacin de
modelos de lneas de espera. Esto puede involucrar cualquier situacin de la vida real,
como trabajos que esperan ser procesados por las maquinarias de una planta industrial,
tareas que esperan ser ejecutadas en un computador, clientes que esperan ser
atendidos en un banco, entre otros.
En los sistemas operativos, muchos procesos compiten y hacen uso de los recursos
escasos de la computadora, como CPU, memoria principal y dispositivos I/O. Por lo
tanto, cuando un proceso est usando algn recurso en particular, los dems procesos
deben esperar. Los sistemas operativos hacen uso de algoritmos de planificacin para
asignar recursos a los procesos en espera. Las colas se pueden utilizar para la
implementacin de diversos mdulos de los sistemas operativos.
Cuando los datos se transmiten a travs de redes, una cola es una excelente estructura
de datos para almacenar los datos y permitir que los elementos de datos se ordenen.
Las colas se pueden usar como estructuras de datos vitales en muchas aplicaciones
comerciales en lnea, como el procesamiento de los requerimientos del cliente, rdenes
y tareas.
Resumen
Ahora que ha completado esta unidad, Ud. debe ser capaz de:
Definir la estructura de datos cola.
Explicar las operaciones del TDA en colas.
Implementar una cola como arreglo.
Explicar las implementaciones de una cola como arreglo circular.
Describir la implementacin de una cola como lista enlazada.
4) Es correcto el axioma:
dequeue(enqueue(queue,element)) = if isempty(queue)
then new element.
a) Verdadero
b) Falso
5) Es correcto el axioma:
frontq(enqueue(queue,element)) = if isempty(queue)
then element
else front(queue).
a) Verdadero
b) Falso
6) Cuando se implementa una cola como arreglo, cul de las siguientes operaciones
es relativamente lenta?
a) Agregar un elemento a la cola
b) Encontrar el frente de la cola
c) Encontrar el ltimo elemento de la cola
d) Eliminar un elemento de la cola
8) En cules de las siguientes situaciones sern usadas las colas como una opcin
adecuada de estructura de datos?
a) Controlar los clientes que esperan al frente de un mostrador de pago en
efectivo en una tienda por departamento
b) Administrar el trfico de una red
c) Describir la estructura organizacional de una compaa
d) Todas las anteriores
10) Para cules de las siguientes aplicaciones, se utiliza una cola como estructura de
datos?
a) Imprimir documentos por la red a travs de una impresora comn
b) Mantener una lista de aviones que vuelan fuera de una ciudad
c) Determinar el nmero de personas al frente del mostrador de pagos de una
tienda por departamentos
d) Todas las anteriores
Ejercicio de Laboratorio
Considere una cola FIFO que contenga enteros. Escribir:
Funciones adecuadas para las operaciones sobre colas.
Fragmentos de programa para llevar a cabo partes especficas de los
requerimientos.
Un programa completo C que realice las siguientes tareas:
1) Tomar como entrada los diferentes enteros posibles que deben formar la cola inicial.
Tomar tantas entradas como sea posible y crear la lista inicial hasta que el usuario
ingrese el valor -9999 para terminar el ingreso. Este valor no debe ser parte de la
lista.
2) Implementar las operaciones comunes sobre colas, como NewQ (crea una cola
nueva vaca), InsertQ (inserta un elemento al final de la cola), RemoveQ (retira un
elemento del frente de la cola) y isEmptyQ (que devuelve TRUE si la cola est
vaca y FALSE en caso contrario). Escribir fragmentos en main() que muestren la
invocacin de estas operaciones con salidas relevantes.
3) Algunas personas se salen de las colas en la vida real. Este fenmeno se
denomina balking de cola. Escribir una funcin llamada balkval(x), que
encuentra el primer elemento de la cola que es x, y lo retira de la cola. Invocar a
esta funcin y mostrar la cola resultante para ilustrar el trabajo de esta funcin.
Recomendaciones:
Escribir todas las funciones de cola utilizando la implementacin como lista
enlazada.
En la funcin main, obtener la entrada de los usuarios.
Realizar la validacin de la entrada. No aceptar enteros negativos.
Garantizar que 9999 no sea parte de la cola.
Hacer un programa tan modular como sea posible.
Tareas Opcionales:
Unidad 1: Grafos
Objetivos del Aprendizaje
Al final de esta unidad, usted debe ser capaz de:
Definir grafos dirigidos y no dirigidos.
Explicar las propiedades de los grafos no dirigidos.
Definir trminos asociados con grafos.
Discutir la representacin de un grafo como un conjunto, una tabla de
adyacencia y una lista de adyacencia.
Describir las aplicaciones de los grafos.
1. Introduccin
Los grafos, como estructuras matemticas, se usan en diferentes ambientes como la
qumica, ingeniera elctrica, informtica, sociologa y geografa, as como, en modelos
matemticos. Por ejemplo, las vas de trenes, caminos o conexiones areas entre
ciudades pueden ser representadas por un grafo. En un circuito lgico digital, los
componentes y las conexiones entre estos pueden ser representados por un grafo. Las
lneas de autoridad y responsabilidad entre las personas en una compaa pueden ser
representadas por un grafo. En forma similar, existen muchos ejemplos de uso de
grafos en diversas reas de aplicacin. Otras aplicaciones de grafos se discuten en la
Unidad 6: Aplicacin de Grafos.
En esta unidad se tratarn slo los conceptos fundamentales de grafos y como estos
pueden ser representados en una computadora. No se discutir ninguna operacin o
implementacin de grafos.
2. Preliminares de Grafos
Un grafo est compuesto de un conjunto de vrtices y un conjunto de aristas. Los
vrtices y aristas tambin se denominan nodos y arcos respectivamente. Una arista es
realmente un par de vrtices dado que conecta dos vrtices cualesquiera en un grafo.
Las Figuras 1.1(a) y 1.1 (b) muestran dos ejemplos de grafos.
La Figura 1.1(a) muestra un grafo de rutas areas parciales entre cinco ciudades de
Norteamrica. En el grafo que conecta las ciudades, una arista entre Cincinnati y
Florida indica que est disponible una ruta directa. Dado que no hay una arista
directa entre Cincinnati y Puerto Rico, no existe una ruta de vuelo disponible
directa entre las dos ciudades. Note que se puede ir desde Cincinnati a Florida y
luego a Puerto Rico.
3. Grafos No Dirigidos
Un grafo no dirigido se define como un grafo donde los pares de vrtices estn
desordenados. Por desordenados, se entiende que las aristas en un grafo no dirigido no
tienen un vrtice origen ni un vrtice destino. Las Figuras 1.1(a), 1.1(b) y 1.2 son
ejemplos de grafos no dirigidos. En estos grafos, se muestra que una arista existe entre
un par de vrtices, pero no se muestra la direccin de la conexin. Se van a definir
algunos trminos bsicos usados en el contexto de grafos no dirigidos.
3.1 Adyacente:
Si existe una arista entre dos vrtices, por ejemplo, p y q, entonces se dice que son
vrtices adyacentes. En la Figura 1.2, se puede ver que los vrtices (p,q), (p,r),
(q,r) y (r,s) son adyacentes.
3.2 Camino:
Un camino es un conjunto de una secuencia de vrtices adyacentes distintos. En la
Figura 1.2, la secuencia de vrtices adyacentes distintos q,p,r,s forma un camino.
Los vrtices q y s no forman un camino. Un nodo puede tener un camino a s mismo.
En la Figura 1.2, el vrtice s tiene un camino a s mismo.
3.3 Ciclo:
Un ciclo se define como un camino que contiene un nmero n de vrtices, colocados de
forma que el vrtice 1 es adyacente al vrtice 2, el vrtice 2 es adyacente al vrtice 3, el
vrtice n-1 es adyacente al vrtice n y finalmente el vrtice n es adyacente al vrtice 1.
En la Figura 1.2, se puede ver que el camino consistente de los tres vrtices q, p, y r
forma un ciclo. Si se considera q como el vrtice 1, ste es adyacente al vrtice p, que
es adyacente al vrtice r. Finalmente, el vrtice r es adyacente al vrtice 1, que es q.
4. Grafos Dirigidos
En las Figuras 1.1(a) y 1.1(b) no haba informacin acerca de la direccin de la ruta
area o del orden de los prerrequisitos para un curso. Usar un grafo cuyas aristas
indican una direccin ayuda a obtener esa informacin.
Un grafo dirigido es definido como aquel donde los pares de vrtices son ordenados.
Por ordenados, se entiende que cada arista en un grafo dirigido tiene un vrtice origen y
un vrtice destino. Es un grafo con un arco representando las aristas y una flecha
indicando la direccin. La Figura 1.4 es el mismo grafo mostrado en la Figura 1.1(b),
pero con direcciones.
En la Figura 1.4, existe un camino dirigido entre el vrtice Linux Basics y C. El curso
que aparece al comienzo de la lnea dirigida es el prerrequisito para el curso al final de
la lnea dirigida. As, es evidente que Linux Basics es prerrequisito para C, C es
prerrequisito para C++, C++ es prerrequisito para Core Java y as sucesivamente.
Ahora que se tiene un claro entendimiento de los prerrequisitos para cada curso.
Al aadir direccin a las aristas en un grafo hace que ste sea un grafo dirigido. Algunas
de las observaciones que pueden hacerse de la Figura 1.4 son:
El curso Enterprise Java tiene dos prerrequisitos.
Para estudiar Enterprise Java, se debe haber cursado:
- Linux Basics.
- C.
- C++.
- Core Java.
- Web Programming I.
Los cursos Linux Basics y XML no tienen prerrequisitos.
Para estudiar WebSphere Commerce Suite, se debe estudiar primero todos los
otros cursos listados en la Figura.
Seguidamente, se explican las dos propiedades de un grafo dirigido con la ayuda de la
Figura 1.5.
En un grafo dirigido todas las aristas en un camino tienen la misma direccin indicada
por las flechas. Tal camino se llama un camino dirigido.
Los caminos en la Figura 1.5 se listan a continuacin:
p,q
p,q,s
p,q,s,r
p,q,s,r,q
p,r
p,r,q
p,r,q,s
p,r,q,s,r
p,s
p,s,r
p,s,r,q
q,s
q,s,r
q,s,r,q
s,r
s,r,q
s,r,q,s
r,q
r,q,s
r,q,s,r
Cada arista en el camino tiene la misma direccin. Tome, por ejemplo, el camino p,q,s,
que tiene dos aristas llamadas p,q y q,s. Ambas aristas tiene la misma direccin.
En un grafo dirigido, todas las aristas en un ciclo deben tener la misma direccin. Los
ciclos en un grafo dirigido se denominan ciclos dirigidos.
Existen muchos ciclos en la Figura 1.5. Uno de ellos es q,s,r,q. Todas las aristas en
este ciclo, llamadas q,s; s,r, y r,q tienen la misma direccin.
A fin de poder usar los grafos en aplicaciones, se debe encontrar un mtodo para
representarlos como una estructura de datos. Se ha visto que los dos elementos de
datos importantes de los grafos son los vrtices y aristas. Los dos mtodos siguientes
se usan comnmente para representar un grafo como una estructura de datos:
Representacin en conjuntos.
Tablas de Adyacencia.
5.1 Representacin de Grafos en Conjuntos
Figura 1.6 ser usada para ilustrar cmo pueden usarse los conjuntos para representar
grafos.
Primero se listarn los vrtices y las aristas del grafo de la Figura 1.6.
Vrtices
Cincinnati
New Jersey
New York
Boston
Aristas
Cincinnati, New Jersey
Cincinnati, New York
Cincinnati, Boston
New Jersey, New York
New Jersey, Boston
New York, New Jersey
New York, Boston
Boston, Cincinnati
Otro mtodo de usar conjuntos para representar un grafo involucra usar slo un
conjunto, el cul, en efecto, proporciona la misma informacin que dos conjuntos
diferentes. A continuacin se discute cmo se usa este mtodo.
En este mtodo, se usan muchas instancias del conjunto aristas. Para cada vrtice
se tiene un conjunto aristas representado por separado. Para el grafo en la Figura
1.6, se tienen los siguientes conjuntos de aristas:
Vrtice Cincinnati
{Cincinnati-New Jersey, Cincinnati-New York,
Cincinnati-Boston}
Vrtice New Jersey
{New Jersey-New York, New Jersey-Boston}
Vrtice New York
{New York-New Jersey, New York-Boston}
Vrtice Boston
{Boston-Cincinnati}
Para encontrar si un vrtice existe, se debe determinar si existe un conjunto
aristas para el vrtice de entrada. Si existe, el vrtice es parte del grafo.
Para encontrar si un camino existe, se busca en el conjunto de aristas del
vrtice origen. De las entradas del conjunto del vrtice origen, se elige el vrtice
destino, que luego se convierte en el nuevo vrtice origen, igual a lo que se hizo
en el mtodo anterior. Estos pasos se repiten hasta que se encuentre que el
vrtice destino en uno de los conjuntos aristas, corresponde con el vrtice
destino original. Tambin es posible que se agoten todas las entradas del
conjunto de aristas sin encontrar un camino entre los dos vrtices de entrada.
Esto es similar al algoritmo presentado en el primer mtodo.
A veces un tercer conjunto, llamado el conjunto adyacente, tambin es considerado.
Este conjunto contiene los vrtices adyacentes a un vrtice en el grafo. Pueden existir
varias instancias del conjunto adyacente, uno para cada vrtice, similar a las varias
instancias del conjunto aristas descritas en este mtodo. Para el grafo en la Figura
1.6, los conjuntos adyacentes son:
Cincinnati 0 1 1 1
New Jersey 0 0 1 1
New York 0 1 0 1
Boston 1 0 0 0
Para entender el uso de las listas enlazadas como mecanismo de implementacin para
listas de adyacencia, considere el grafo dirigido que se muestra en la Figura 1.7.
rp
Para representar la lista de adyacencia usando una lista enlazada, se deben tener dos
listas enlazadas conectadas entre s.
La Figura 1.8 tiene cinco listas enlazadas. Una lista se usa para representar los vrtices
en el grafo dirigido, llamados p, q, r y s. Se denomina esta lista, la lista de vrtices con
cuatro nodos. Cada nodo en la lista de vrtices representa un vrtice del grafo. Las
otras cuatro listas proceden de cada uno de los cuatro nodos de la lista de vrtices. Los
nodos en las cuatro listas enlazadas representan las aristas que proceden de cada
vrtice. Para simplificar las cosas, se muestran vrtices y aristas en la parte de
informacin de los nodos de las cinco listas enlazadas.
Figura 1.8: Representacin Grfica de una Lista de Adyacencia Usando Listas Enlazadas
El nodo cabecera ser reconocido como graph. Dado que es el nodo cabecera y tiene
un vrtice inicial p, de tal forma que se puede llegar a lo siguiente:
Al visitar p. Desde p se puede visitar q, desde q se puede visitar r, y desde r
se puede visitar s. Esto completa el recorrido de la lista enlazada que representa
los vrtices.
Al visitar p. Desde p se puede visitar pq, y desde pq se puede visitar ps. Esto
da todas las aristas que empiezan desde p.
Al visitar p. Desde p se puede visitar pq. Desde pq se puede visitar q y desde q
se puede visitar qr. Desde qr se puede visitar r y desde r se puede visitar rp.
El primer vrtice de pq es el vrtice final de rp que fue visitado finalmente. Esto
completa un ciclo en el grafo dirigido.
As, es fcil derivar estas cosas acerca de un grafo cuando las listas de adyacencia se
representan usando listas enlazadas.
6. Aplicaciones de Grafos
6.1 Representacin de una Red de Caminos
Los grafos se pueden usar para representar redes de caminos. En general, se pueden
usar para representar cualquier ruta de viaje, ya sea por tierra, mar o aire. Los
algoritmos de grafos se pueden usar para determinar si un camino de viaje existe desde
un origen a un destino. Adems, se puede calcular el camino ms corto desde un origen
a un destino usando algoritmos de grafos.
Los grafos se pueden usar para representar mapas y entidades en bases de datos
geogrficas. Sus aplicaciones se extienden a sistemas de informacin geogrficos y
cartografa.
Los grafos tienen aplicaciones en el rea de anlisis y diseo orientados a objetos. Las
herramientas UML (Unified Modeling Language) y varios CASE (Computer Aided
Software Engineering) que soportan mtodos orientados a objetos hacen uso de grafos.
Resumen
Ahora que Ud. ha completado esta unidad, debe ser capaz de:
Definir grafos dirigidos y no dirigidos.
Explicar las propiedades de los grafos no dirigidos.
Definir los trminos asociados con grafos.
Discutir la representacin de un grafo como un conjunto, una matriz de
adyacencia y una lista de adyacencia.
Describir las aplicaciones de los grafos.
2) Qu representa k = (diversin,feliz)?
a) Un grafo.
b) Un ciclo en un grafo.
c) Un vrtice en un grafo.
d) Una arista en un grafo.
a) Verdadero.
b) Falso.
8) Cules de los siguientes se pueden usar para representar un grafo como una
estructura de datos?
a) Conjuntos.
b) Matriz de adyacencia.
c) Lista de adyacencia.
d) Slo (a) y (c).
Unidad 2: rboles
Objetivos del Aprendizaje
Al final de esta unidad, Ud. debe ser capaz de:
Definir un rbol como una estructura de datos.
Discutir rboles binarios, rboles de bsqueda binaria y rboles en general.
Explicar los tres mtodos de recorrido para un rbol binario.
Definir un heap.
Distinguir entre un heap mnimo y un heap mximo.
1. Introduccin
Se han estudiado las listas, pilas, colas y grafos que se pueden usar como estructuras
de datos en aplicaciones a travs de implementaciones de arreglos o listas enlazadas.
En esta unidad, se aprendern a usar los rboles como estructuras de datos. Se
estudiarn los rboles binarios y cmo estos pueden extenderse en un rbol general.
Tambin se discute un tipo especial de rbol binario llamado heap.
2. rboles Generales
Un rbol general es aquel en que un nodo puede tener cero uno o ms de dos
subrboles. Un ejemplo de tal rbol es el 'rbol genealgico', que describe la genealoga
y estructura de una familia. Los rboles generales se usan en diversas reas de trabajo,
tales como, en matemticas y en ingeniera. En la informtica, los rboles generales se
usan para representar la estructura sintctica de programas fuentes en compiladores y
en organizar la informacin en las bases de datos.
En el caso de un rbol binario, se habla acerca de slo dos hijos, el hijo izquierdo y el
hijo derecho. En el caso de un rbol general, se habla acerca del hijo mayor y el hijo
menor. Todos los hijos restantes entre el hijo mayor y menor son conocidos como otros
hijos del nodo padre.
Las operaciones realizadas en un rbol binario tambin son vlidas en un rbol general.
Un nodo puede ser insertado o eliminado, un elemento puede ser buscado y el rbol
puede ser recorrido. Pueden existir muchas otras operaciones especficas para un rbol
general. No se darn mayores detalles al respecto en este curso.
3. rboles Binarios
Normalmente, cuando se organiza una coleccin de elementos relacionados, el orden
jerrquico de los elementos est basado en un conjunto de sus atributos. Un rbol es
una opcin natural para representar el ordenamiento jerrquico.
Un rbol puede ser definido como una coleccin de nodos representando un
ordenamiento jerrquico. El ordenamiento jerrquico puede estar basado en la
informacin presente en los nodos. Un buen ejemplo de ordenamiento jerrquico es la
estructura de directorios del sistema operativo Linux.
Los nodos son los elementos de un rbol y guardan informacin. Los nodos pueden
guardar informacin de cualquier tipo de datos, desde tipos simples de datos como
enteros, reales hasta tipos estructurados como arreglos, pilas, colas y listas. Cada rbol
tiene un nodo raz. Un nodo raz es el primer nodo e indica el inicio de un rbol.
Usando esta definicin bsica de un rbol y un nodo, se va a definir un rbol binario.
Un rbol binario es un rbol en donde cada nodo puede tener cero, uno o dos hijos.
Cuando un nodo tiene 1 2 hijos, los nodos hijos en s mismos son rboles binarios,
dado que pueden tener tambin sus propios hijos. Por ello, los hijos de un rbol binario
tambin son conocidos como subrboles. La Figura 2.1 ilustra un rbol binario.
Un rbol binario puede tener cero, uno o dos subrboles desde un nodo raz. Esto
implica que alguno o ambos subrboles pueden estar vacos. Se puede decir que un
rbol binario tiene las siguientes caractersticas:
Otro ejemplo de un rbol binario se presenta en la Figura 2.3 donde la raz no tiene un
subrbol izquierdo.
Se van a aprender algunas terminologas asociadas con un rbol binario, con la ayuda
de las Figuras 2.2 y 2.3.
Padre: Es aquel nodo que tiene al menos un hijo. Rooty es el padre de Y1 y Y2
en la Figura 2.2.
Hijo Izquierdo: Es aquel nodo o hijo que se ramifica a la izquierda desde un
nodo padre. Y1 es el hijo izquierdo de Rooty en la Figura 2.2. La Figura 2.3 no
tiene ningn hijo izquierdo.
Hijo Derecho: Es aquel nodo o hijo que se ramifica a la derecha desde un nodo
padre. Y2 es el hijo derecho de Rooty en la Figura 2.2.
Hoja: Es aquel nodo sin hijos. X1, X2, Y1, y Y2 de la Figura 2.2, y X4 de la Figura
2.3 son nodos hojas.
Nivel de un nodo: El nivel de un nodo se refiere al nivel en que existe el nodo
en el ordenamiento jerrquico. Este se denota por un nmero. Al nodo raz se le
asigna 0. A los hijos de la raz se les asigna 1. As, en un rbol, el nivel de cada
nodo se representa por el nivel de su padre ms uno. En la Figura 2.3, el nodo
X1 est en nivel 0, X2 est en nivel 1, X3 est en nivel 2, y X4 est en nivel 3.
Arista: Es la conexin entre el padre y sus hijos. En la Figura 2.3, la lnea
mostrada entre X1 y X2 es una arista.
Camino: Es una secuencia de aristas consecutivas. En la Figura 2.2, la
secuencia de nodos - The Root, Rootx, X1 - es un camino.
Longitud de camino: La longitud del camino es uno menos que el nmero de
nodos en el camino. La longitud de un camino puede ser cero. En la Figura 2.2,
la longitud del camino The Root, Rootx, X1, es dos.
Altura del rbol: La altura de un rbol denota el nmero mximo de nodos
desde la raz hasta la menor hoja en un rbol. Tambin se conoce como la
profundidad del rbol. La altura del rbol en la Figura 2.2 es tres y en la Figura
2.3 es cuatro.
4. Recorrido de rboles
El recorrido involucra visitar cada nodo en el rbol. Los nodos pueden ser visitados
usando cualquiera de estas tres clases de recorridos: recorrido preorden, recorrido
inorden y recorrido postorden. Esto es similar a las notaciones prefija, infija y postfija
para representar expresiones que se aprendieron en el Volumen 1, Unidad 4:
Estructuras de Datos Simples, Pilas.
Los nodos de un rbol binario se listan usando cualquiera de los mtodos de recorrido.
Los tres mtodos de recorrido que se realizan en un rbol binario se dan a continuacin:
Recorrido Preorden
- Visitar el nodo raz.
- Visitar el nodo izquierdo.
- Visitar el nodo derecho.
Recorrido Inorden
- Visitar el nodo izquierdo.
- Visitar el nodo raz.
- Visitar el nodo derecho.
Recorrido Postorden
- Visitar el nodo izquierdo.
- Visitar el nodo derecho.
- Visitar el nodo raz.
En la Figura 2.4, existen dos subrboles cuyas races son b y e. Cuando se visitan
estos subrboles, se aplica nuevamente las reglas del recorrido.
A continuacin se presentan ejemplos de los recorridos preorden, inorden y postorden.
El rbol ejemplo usado para estos listados es el rbol de la Figura 2.4.
Pero si el rbol binario tiene un slo nodo, el rbol se considera que est preorden,
inorden y postorden.
Preorden:
Siguiendo la regla de recorrido preorden, la sentencia printf denota la visita del nodo
raz, seguida por una llamada a preOrder con el nodo izquierdo. Esto es seguido por
una llamada a preOrder con el nodo derecho. Las llamadas a preOrder aplicarn
nuevamente la regla, imprimiendo el valor de la raz y haciendo llamadas a preOrder
con los nodos izquierdo y derecho.
Inorden:
inOrder(nodo->izquierdo);
printf("%d\n", nodo->elemento);
inOrder(nodo->derecho);
}
}
El cdigo C termina aqu
En esta funcin, primero se hace una llamada a inOrder con el nodo izquierdo,
luego se imprime el valor de la raz seguido por una llamada a inOrder con el nodo
derecho.
Postorden:
A partir de la Figura 2.5, se observa que el elemento raz es tal que todos los elementos
anteriores en orden del elemento raz estn en el subrbol izquierdo. El elemento raz
es 'Orlando, FL'. Todos los elementos en el subrbol izquierdo del rbol de bsqueda
binaria tienen valores que ocurren antes que el elemento de la raz. Como se usan
nombres de ciudades en la lista de elementos, se usa el mtodo del diccionario para
determinar los nombres que preceden a otros.
Todos los elementos que ocurren antes de 'Orlando, FL' estn en el subrbol
izquierdo. En forma similar, todos los elementos que ocurren despus de 'Orlando,
FL' en el orden estn en el subrbol derecho. Si observa en detalle la figura, tambin se
puede ver que cada subrbol tiene esta propiedad. Como ejemplo, observe 'Raleigh,
NC'. Note que todos los elementos que ocurren antes de 'Raleigh, NC' estn en su
subrbol izquierdo, mientras que todos los elementos que ocurren despus de
'Raleigh, NC' estn en su subrbol derecho.
Para buscar un elemento particular, primero se debe comparar el elemento con la raz
del rbol. Si el elemento que se busca no est en la raz, entonces se empieza a buscar
en el subrbol izquierdo o en el subrbol derecho, dependiendo si el elemento buscado
es menor o mayor que el elemento en la raz. Tpicamente, el operador igual a se
aplica tanto con el operador menor como con el mayor que. Asumiendo que el operador
igual a es aplicado con el mayor que, la bsqueda procede en el subrbol izquierdo de
la raz si el elemento buscado es menor que el elemento raz, y en el subrbol derecho
si el elemento buscado es mayor o igual que el elemento en la raz. La bsqueda
termina cuando el elemento es encontrado en el rbol. En caso contrario, la bsqueda
procede hasta el subrbol sea vaco.
Se va a entender cmo se usa el rbol de bsqueda binaria para realizar una bsqueda
con la ayuda de la Figura 2.5. Se asume que el elemento de bsqueda es
'Sacramento, CA'.
Se compara el elemento buscado con el valor en la raz, 'Orlando, FL'. Dado
que no es igual al valor en la raz, se verifica si es menor, mayor o igual que
'Orlando, FL'.
El elemento buscado es mayor que el valor en el nodo raz. Se moviliza hacia el
subrbol derecho de la raz. Esta se convierte en la nueva raz. El elemento
buscado se compara nuevamente con el valor en esta nueva raz, 'Raleigh,
NC'.
El elemento buscado no es igual a 'Raleigh, NC' y tambin es mayor que
'Raleigh, NC'. Ahora se moviliza a su subrbol derecho, que es 'San Diego,
CA'.
El elemento buscado no es igual al valor en la nueva raz. Pero se encuentra
que es menor que 'San Diego'. Ahora se mueve al subrbol izquierdo.
El elemento buscado es igual al valor en esta nueva raz, 'Sacramento, CA'.
As, la bsqueda es un xito.
Siguiendo el procedimiento anterior, cuando se alcanza un valor NULL al final, significa
que el elemento no est en el rbol de bsqueda binaria.
Usando el recorrido inorden del rbol binario creado a partir de Initial List 1, se
obtiene la lista ordenada como se muestra en la Figura 2.7.
construccin del rbol con el resto de los nodos sigue los mismos principios usados
para la bsqueda. Si el elemento a ser aadido al rbol de bsqueda es menor que la
raz, entonces se aade a la izquierda de la raz, caso contrario se aade a la derecha
de la raz. Esto se repite para todos los elementos en la lista.
Antes de aprender acerca de otra forma de usar un rbol binario llamado heap, se va a
ampliar la comprensin de rboles binarios a rboles que tienen ms de dos hijos. Tales
rboles se llaman rboles generales.
6. Aplicaciones de rboles
Algunas aplicaciones que pueden usar un rbol como una estructura de datos se
presentan a continuacin.
Una de las principales aplicaciones de los rboles es la bsqueda, esto es, buscar
informacin especifica basada en algn valor clave. Algunos tipos especiales de rboles
ayudan a acelerar el proceso de bsqueda.
Los algoritmos de compresin de datos hacen uso del rbol de codificacin de Huffman
(una forma especial de rbol). Aqu, el rbol es usado como una estructura de datos que
ayuda en la compresin de los datos de entrada dados. Otro rbol especial, llamado un
rbol sufijo, tambin se usa en las aplicaciones de compresin de datos.
Los rboles son las estructuras de datos naturales a ser usadas en las aplicaciones
genealgicas. Las representaciones de rboles genealgicos y las aplicaciones
basadas en rboles genealgicos, emplean la estructura de datos rboles. Se pueden
tener tales aplicaciones en relaciones jerrquicas para especies vivas, tribus y an
lenguajes.
Varios juegos requieren que las estrategias y reglas estn embebidas. Las decisiones
tienen que hacerse basadas en una estrategia que evale los pros y contras de una
opcin. Una de las estructuras de datos naturales que puede usarse es un rbol de
decisin. Los programas de juegos, especialmente aquellos que involucran estrategias,
tales como, ajedrez o bridge hacen uso de rboles de decisin.
Los rboles se pueden usar como estructuras de datos en todas las aplicaciones que
involucran la representacin de relaciones jerrquicas y las dependencias entre las
entidades. Ejemplos de estas son los organigramas y relaciones de autoridad de
trabajo.
En esta rea, los rboles se han usado como estructuras de datos para agrupar
expresiones genticas, caracterizacin y prediccin de estructuras protenicas, etc. Los
rboles tambin han sido aplicados como parte del proceso de clculo para el diseo de
bases de datos para recursos biolgicos, extraccin de datos, patrones de bsqueda y
descubrimiento, rboles filogenticos y agrupamiento.
Los rboles binarios tambin se usan para representar otra estructura de datos, llamada
heap. A continuacin se discuten brevemente los conceptos relacionados a la estructura
de datos heap.
7. Heaps
Un heap se define como un rbol binario que satisface ciertas propiedades especficas.
Los elementos guardados en los nodos deben satisfacer unas cuantas propiedades
especificas, que se listan a continuacin.
Todas las hojas del rbol binario deben ocurrir en dos niveles adyacentes.
Todas las hojas del menor nivel del rbol binario ocurren a la izquierda del rbol.
Todos los niveles del rbol binario estn completos, excepto en el caso del
menor nivel del rbol, que puede estar slo parcialmente completo.
El elemento guardado en la raz es mayor o igual que los elementos guardados
en sus hijos (note que el rbol puede no tener hijos) para el heap mximo.
Los subrboles izquierdo y derecho, que emanan de la raz, son heaps en s
mismos.
Las primeras tres condiciones aseguran que la representacin del rbol binario en
ubicaciones contiguas ser eficiente en trminos de espacio. Esto es conocido como la
propiedad estructural de un heap.
La Figura 2.11 muestra un rbol binario y el heap asociado. Muestra un heap mnimo.
Se ha usado ordenamiento de nivel para mostrar la lista de elementos. La raz se lista
primero (nivel 0), seguida por los elementos a la izquierda de la raz y luego a la
derecha de la raz (nivel 1). Siguiendo esto, se listan los elementos en el nivel 2 de
izquierda a derecha y as sucesivamente.
Un heap de ejemplo, con valores en los nodos que satisfacen las propiedades de heap,
se muestra en la Figura 2.12. Es un heap mnimo, dado que el valor en el nodo raz es
menor o igual que el valor de los elementos en sus hijos.
mostrado en la Figura 2.12 como heap mnimo, la Figura 2.13 muestra un heap mximo.
La creacin de un heap depende de la lista inicial de elementos.
8. Aplicacin de Heaps
El rea de aplicacin ms importante y til de un heap es la implementacin de una cola
de prioridades, que a su vez, tiene aplicacin en diferentes reas.
Un heap se usa en la implementacin de una cola de prioridad. Una cola se llama cola
de prioridad cuando la eliminacin est basada ya sea en un elemento mnimo o
mximo en la cola.
Una cola de prioridad tiene varias aplicaciones, desde aquellas en sistemas operativos
para aplicaciones de encolamiento general. Las colas de prioridad se pueden usar en
planificadores de sistemas operativos donde las tareas esperando por el CPU son
ordenadas de acuerdo a una prioridad. El almacenamiento de eventos dependientes del
tiempo emplea colas de prioridad. Las colas de prioridad se usan ampliamente en
aplicaciones de simulacin de sistemas. En la simulacin digital de eventos discretos,
existe la necesidad de mantener colas de prioridad desde las cuales las entidades sern
seleccionadas para el servicio.
Resumen
Ahora que Ud. ha completado esta unidad, debe ser capaz de:
Definir un rbol como una estructura de datos.
Discutir rboles binarios, rboles de bsqueda binaria y rboles generales.
Explicar los tres mtodos de recorrido para un rbol binario.
Definir un heap.
Distinguir entre un heap mnimo y un heap mximo.
1. Introduccin
En las unidades anteriores, se abarc principalmente el tema de estructuras de datos,
sus operaciones e implementaciones. Ahora se sabe que ordenar y buscar elementos
son dos de las actividades ms comunes en cualquier aplicacin grande. En esta
unidad, se tratarn estos dos importantes temas y se presentarn algunos algoritmos de
ordenamiento.
Las aplicaciones que manejan grandes cantidades de datos requieren de algn tipo de
ordenamiento. Se pueden tomar varios ejemplos de tales aplicaciones en la vida real,
tales como:
Ordenar libros y diarios en una biblioteca, por orden de autor, ao de publicacin
y ttulo.
Ordenamiento alfabtico de nombres en un directorio telefnico.
Listar palabras en un diccionario.
Ordenar resultados de motores de bsqueda, basados en su relevancia para el
tema buscado.
Las tcnicas de ordenamiento son principalmente de dos categoras:
Ordenamiento Interno: Se aplica cuando los elementos a ser ordenados estn
disponibles en la memoria primaria.
Ordenamiento Externo: Se aplica cuando los elementos a ser ordenados son
muchos y estn disponibles slo en dispositivos de almacenamiento secundario.
En esta unidad, se tratarn slo las tcnicas de ordenamiento interno. Se aprendern
primero tres tcnicas simples de ordenamiento.
Asuma que se tiene que ordenar un arreglo de enteros llamado InArray. Los elementos
de este InArray, deben ser ordenados en orden ascendente y guardados en otro
arreglo llamado OutArray. El arreglo de entrada InArray tiene que permanecer sin
cambios durante el proceso de ordenamiento. Inicialmente, no hay elementos en
OutArray, dado que los elementos sern guardados en l, slo despus que hayan
sido ordenados.
En cada etapa del ordenamiento por insercin, OutArray est ordenado. Cada
elemento de InArray se toma e inserta en su posicin correcta en OutArray. Cuando
se hace la insercin en OutArray, el elemento a ser insertado se compara con cada
elemento en OutArray. Cuando el elemento a ser insertado es menor que el elemento
actual en OutArray, la comparacin se detiene. Desde el elemento donde se detuvo
la comparacin hasta el ltimo elemento en Outarray, los elementos son desplazados
una posicin. El elemento desde InArray es insertado en el agujero que fue creado al
desplazar los otros elementos. Esta tcnica se conoce como ordenamiento por
insercin, dado que se crea un agujero y luego se inserta el elemento.
Se usaron dos arreglos, InArray y OutArray, slo para clarificar la ilustracin del
mtodo. Se puede realizar el ordenamiento por insercin en el mismo arreglo.
La ejecucin a travs del cdigo C se muestra en la Figura 3.3 con los valores de i, j,
tempHolder, mostrados en cada etapa. Tambin se muestra el orden de elementos en
el arreglo antes y despus del ordenamiento. La secuencia de ejecucin de sentencias
para cada i esta encerrado en un cuadro. Los elementos en el arreglo son los mismos
que los elementos iniciales en la Figura 3.1.
Antes de ordenar: 260 -15 20 30 11 -19
i = 1 tempHolder = -15
Valores actuales en el arreglo: 260 -15 20 30 11 -19
j = 0, tempHolder es menor que inArray[0], inArray[1] = inArray[0]
Despus de ciclo interno: j = -1, inArray[0] = tempHolder
Valores en el arreglo ahora son: -15 260 20 30 11 -19
i = 2 tempHolder = 20
Valores actuales en el arreglo: -15 260 20 30 11 -19
j = 1, tempHolder es menor que inArray[1], inArray[2] = inArray[1]
i = 3 tempHolder = 30
Valores actuales en el arreglo: -15 20 260 30 11 -19
j = 2, tempHolder es menor que inArray[2], inArray[3] = inArray[2]
Despus de ciclo interno: j = 1, inArray[2] = tempHolder
Valores en el arreglo ahora son: -15 20 30 260 11 -19
i = 4 tempHolder = 11
Valores actuales en el arreglo: -15 20 30 260 11 -19
j = 3, tempHolder es menor que inArray[3], inArray[4] = inArray[3]
j = 2, tempHolder es menor que inArray[2], inArray[3] = inArray[2]
j = 1, tempHolder es menor que inArray[1], inArray[2] = inArray[1]
Despus de ciclo interno: j = 0, inArray[1] = tempHolder
Valores en el arreglo ahora son: -15 11 20 30 260 -19
i = 5 tempHolder = -19
Valores actuales en el arreglo: -15 11 20 30 260 -19
j = 4, tempHolder es menor que inArray[4], inArray[5] = inArray[4]
j = 3, tempHolder es menor que inArray[3], inArray[4] = inArray[3]
j = 2, tempHolder es menor que inArray[2], inArray[3] = inArray[2]
j = 1, tempHolder es menor que inArray[1], inArray[2] = inArray[1]
j = 0, tempHolder es menor que inArray[0], inArray[1] = inArray[0]
Despus de ciclo interno: j = -1, inArray[0] = tempHolder
Valores en el arreglo ahora son: -19 -15 11 20 30 260
Nota: Para determinar si los elementos en el arreglo estn ordenados o no, el arreglo
es recorrido al menos una vez.
Por lo tanto, la ventaja de este algoritmo es que, si el arreglo de entrada est ordenado,
el arreglo se verifica slo una vez. Las vistas de cada pasada se muestran en la Figura
3.4.
En la ltima pasada, (la sexta pasada, en este caso), no se entra al ciclo for, dado que
n j debe ser 6 6 = 0. Como interchange permanece en 0, tambin termina
el ciclo while.
i = 0
Valores actuales en el arreglo: 260 -15 20 30 11 -19
Elemento mnimo inicial es 260
j = 1
inArray[1] es menor que el elemento mnimo 260
Nuevo elemento mnimo es -15
j = 2
inArray[2] es mayor o igual que el elemento mnimo -15
j = 3
inArray[3] es mayor o igual que el elemento mnimo -15
j = 4
inArray[4] es mayor o igual que el elemento mnimo -15
j = 5
inArray[5] es menor que el elemento mnimo -15
Nuevo elemento mnimo es -19
Elemento mnimo en arreglo luego de fin de ciclo interno: -19
Intercambiando elemento mnimo -19 con 260 en inArray[0]
Valores ahora en arreglo: -19 -15 20 30 11 260
i = 1
Valores actuales en el arreglo: -19 -15 20 30 11 260
Elemento mnimo inicial es -15
j = 2
inArray[2] es mayor o igual que el elemento mnimo -15
j = 3
inArray[3] es mayor o igual que el elemento mnimo -15
j = 4
inArray[4] es mayor o igual que el elemento mnimo -15
j = 5
inArray[5] es mayor o igual que el elemento mnimo -15
Elemento mnimo en arreglo luego de fin de ciclo interno: -15
Intercambiando elemento mnimo -15 con -15 en inArray[1]
Valores ahora en arreglo: -19 -15 20 30 11 260
i = 2
Valores actuales en el arreglo: -19 -15 20 30 11 260
Elemento mnimo inicial es 20
j = 3
inArray[3] es mayor o igual que el elemento mnimo 20
j = 4
inArray[4] es menor que el elemento mnimo 20
Nuevo elemento mnimo es 11
j = 5
inArray[5] es mayor o igual que el elemento mnimo 11
i = 4
Valores actuales en el arreglo: -19 -15 11 20 30 260
Elemento mnimo inicial es 30
j = 5
inArray[5] es mayor o igual que el elemento mnimo 30
Elemento mnimo en arreglo luego de fin de ciclo interno: 30
Intercambiando elemento mnimo 30 con 30 en inArray[4]
Valores ahora en arreglo: -19 -15 11 20 30 260
Resumen
Ahora que Ud. ha completado esta unidad, debe ser capaz de:
Proporcionar una visin general de las tcnicas de ordenamiento.
Explicar el algoritmo de ordenamiento por insercin.
Explicar el algoritmo de ordenamiento por burbuja.
Explicar el algoritmo de ordenamiento por seleccin.
6) Si los siguientes son los resultados intermedios, con la primera fila indicando el
arreglo de entrada, y la ltima fila indicando el arreglo ordenado. Qu algoritmo
de ordenamiento ha sido usado?
-1 0 100 -4 -34 300 210 101
-1 0 100 -4 -34 300 210 101
-1 0 100 -4 -34 300 210 101
-4 -1 0 100 -34 300 210 101
-34 -4 -1 0 100 300 210 101
-34 -4 -1 0 100 300 210 101
-34 -4 -1 0 100 210 300 101
-34 -4 -1 0 100 101 210 300
a) Ordenamiento por burbuja.
b) Ordenamiento por seleccin.
c) Ordenamiento por insercin.
Ejercicio de Laboratorio
Considere un arreglo que almacena enteros. Escriba un programa completo en C que
realice las siguientes tareas:
1) Leer de entrada n un entero positivo mayor que cero. Luego toma como entrada
n elementos enteros, nuevamente elementos enteros positivos mayores que
cero y los ingresa en el arreglo.
2) Ordenar el arreglo de tal forma que todos los nmeros impares ocurran antes
que los nmeros pares.
3) Ordenar todos los nmeros impares en orden descendente.
4) Ordenar todos los nmeros pares en orden ascendente.
Tener en cuenta los siguientes puntos en el programa:
Si no hay enteros pares en la entrada, realizar slo ordenamiento descendente.
Si no hay enteros impares en la entrada, realizar slo ordenamiento ascendente.
Si hay tanto enteros pares como impares en la entrada, realizar las tres
operaciones de ordenamiento.
Para cada tarea de ordenamiento, use una tcnica de ordenamiento diferente.
Consejos tiles
Escriba el programa modular.
Escriba tres funciones:
- ascendSort para ordenar los elementos en orden ascendente. Use el
algoritmo de ordenamiento por insercin.
- descendSort para ordenar los elementos en orden descendente. Use el
algoritmo de ordenamiento por seleccin.
- oddEvenSort para colocar todos los nmeros impares ante de los nmeros
pares en el arreglo. Use el algoritmo de ordenamiento por burbuja.
Ingrese el nmero de elementos a ser guardados en el arreglo. Asegrese que
es un entero positivo mayor que cero.
Ingrese los valores para el arreglo. Realice la validacin de entrada para
asegurarse que slo valores positivos mayores que cero se tomen como
entrada. Dado que el nmero de elementos a ser ingresados al arreglo es
conocido de la primera entrada de datos, ese valor se puede usar para iterar y
obtener los elementos para el arreglo.
Primero, realizar el ordenamiento descendente.
Luego, seguir con el ordenamiento impar-par. Al final de este ordenamiento,
todos los nmeros impares deben estar ordenados en forma descendente,
adems todos los nmeros impares deben ocurrir antes de los nmeros pares
en el arreglo.
1. Introduccin
En la Unidad 3: Tcnicas de Ordenamiento Simple, se aprendieron tres tcnicas de
ordenamiento: por insercin, por burbuja y por seleccin. En esta unidad, se discuten
dos tcnicas de ordenamiento muy usadas, el ordenamiento merge sort (por fusin) y el
ordenamiento quick sort (rpido).
La Figura 5.1 ilustra como funciona el ordenamiento merge sort (por fusin).
Est claro a partir de la Figura 5.1 que cada divisin reduce el arreglo a la mitad.
Empezando con el arreglo original consistente de 1*1 = 1 arreglo, se divide el arreglo
en 1*2 = 2 arreglos. De estos dos arreglos, se obtiene 2*2 = 4 arreglos y finalmente
de estos cuatro arreglos se obtienen 4*2 = 8 arreglos. Existen ocho elementos en el
arreglo y as observe que existen (n/2)*2 = n arreglos al final, cuando n = 8. En
esta etapa, slo existe un elemento en cada uno de los n arreglos, que est ordenado.
Note que en cada subarreglo se aplica nuevamente el ordenamiento merge sort (por
fusin) para llegar a la siguiente lista ordenada y fusionada.
Del ejemplo mostrado en la Figura 5.1, se puede ver que el algoritmo de ordenamiento
merge sort (por fusin) tiene algunas propiedades especiales. Estas son:
Despus del primer paso por el arreglo, los arreglos de un slo elemento son
fusionados en arreglos con dos elementos cada uno. Dentro de cada subarreglo
los elementos estn ordenados. En otras palabras, si el arreglo slo tiene dos
elementos a ordenar, slo tomar una pasada.
Despus del segundo paso por el arreglo, los arreglos de dos elementos son
fusionados en arreglos con cuatro elementos cada uno, esto es, 22 elementos
cada uno, y dentro de cada arreglo los elementos estn ordenados. En otras
palabras, si el arreglo slo tiene cuatro elementos a ordenar, requerir dos
pasadas.
Despus del tercer paso por el arreglo, los arreglos de cuatro elementos son
fusionados en arreglos con ocho elementos cada uno, esto es, 23 elementos
cada uno y dentro de cada subarreglo los elementos estn ordenados. En otras
palabras, si el arreglo tiene slo ocho elementos para ordenar, requerir tres
pasadas.
Despus del paso p por el arreglo, los arreglos de p/2-elementos sern
fusionados en arreglos conteniendo 2p elementos y dentro de cada subarreglo
los elementos estn ordenados. En otras palabras, si el arreglo tiene slo 2p
elementos a ordenar, tomar p pasadas. Suponga que se escribe:
2p = x
A partir de la definicin de logaritmos, se puede escribir
p = log2 x
Por lo tanto, para ordenar n elementos en un arreglo, requerir de log2 n
pasadas.
Basados en esta discusin, se puede escribir un programa para realizar el
ordenamiento por fusin usando las siguientes funciones:
MergeSort: Esta funcin toma como entrada el arreglo a ser ordenado y el
nmero de elementos en el arreglo y controla el ordenamiento merge sort (por
fusin) invocando a las funciones apropiadas. Estas funciones ayudan a crear
particiones de tamaos apropiados durante cada pasada. Tambin ayudan a
calcular el lmite superior de los subarreglos, a ordenar subarreglos, fusionarlos
y asignarlos al arreglo auxiliar.
CalculateUpperBound: Calcula el lmite superior del subarreglo que se crea.
SortAndAssign: Esta funcin ordena los subarreglos individuales y los asigna al
arreglo auxiliar, dummy.
assignSub
assignRemaining
Estas dos ltimas funciones realizan esencialmente la misma tarea, esto es,
asignar los subarreglos ordenados al arreglo auxiliar, dummy. La primera funcin
hace la asignacin de los subarreglos apropiadamente divididos mediante el
procedimiento de ordenamiento por fusin. La segunda funcin trabaja con la
parte restante del subarreglo.
Un programa completo en C que ordena un arreglo de entrada usando el ordenamiento
merge sort (por fusin) se presenta a continuacin. El algoritmo de ordenamiento merge
sort (por fusin) puede ser escrito como un algoritmo tanto iterativo como recursivo. Se
presenta la solucin iterativa.
31. }
32.
33. void assignRemaining(int lb1, int k, int n, int x[],int
dummy[]) {
34. int i;
35. for(i = lb1; k < n; i++) {
36. dummy[k++] = x[i];
37. }
38. }
39. void mergeSort(int *myArray, int n) {
40. int dummy[MAX_SIZE], i=0, j=0, targetIndex=0;
41. int loopCount = 0, lowerBound1, lowerBound2;
42. int upperBound1, upperBound2,size;
43.
44. size = 1;
45. while(size < n) {
46. lowerBound1 = 0;
47. targetIndex = 0;
48. while(lowerBound1 + size < n) {
49. lowerBound2 = lowerBound1 + size;
50. upperBound1 = lowerBound2 - 1;
51. upperBound2 = \
52.
calculateUpperBound(lowerBound2,size, n);
53. sortAndAssign(lowerBound1, \
54.
lowerBound2,upperBound1, \
55. upperBound2, &i, &j,
&targetIndex, \
56. myArray, dummy);
57. assignSub(i, upperBound1, &targetIndex, \
58. myArray, dummy);
59. assignSub(j, upperBound2, &targetIndex, \
60. myArray, dummy);
61. lowerBound1 = upperBound2 + 1;
62. }
63. assignRemaining(lowerBound1, targetIndex, n, \
64. myArray, dummy);
Pasada 2:
Ordenar y fusionar: (101 106 204 210)
Ordenar y fusionar: (168 201 203 240)
Pasada 3:
Ordenar y fusionar: (101 106 168 201 203 204 210 240)
Despus de ordenar: 101 106 168 201 203 204 210 240
Relacionando la Figura 5.2 con la Figura 5.1, se observa que las pasadas 1, 2, y 3 de la
Figura 5.1 corresponden con las pasadas 1, 2, y 3 de la Figura 5.2.
Los subarreglos ahora son divididos nuevamente usando la misma regla. Esto es, el
algoritmo se aplica nuevamente en los subarreglos en forma individual. Despus de
cada pasada, el elemento pivote elegido se mueve a su ubicacin correcta en el arreglo.
En la tercera fila 204 est en su ubicacin correcta dado que fue elegido como el
elemento pivote en la segunda pasada. Al final, se encuentra que el arreglo ha sido
ordenado dado que cada elemento pivote se ha movido a su ubicacin correcta durante
una pasada.
La eleccin del elemento pivote puede ser en forma aleatoria entre los elementos del
arreglo. Un mtodo bueno, aceptable es considerar tres elementos en el arreglo - el
elemento ms a la izquierda, el elemento ms a la derecha y el elemento en el punto
medio del arreglo. Con estos elementos, se puede elegir el elemento medio para que
acte como elemento pivote. Como ejemplo, considere la siguiente lista de elementos:
106 101 204 210 201 203 240 168
Para encontrar la mediana de la lista, se va a encontrar primero el punto medio usando
la frmula:
(posicin_ms_izquierda + posicin_ms_derecha)/2
Usando esto, se obtiene (0 + 7)/2 = 3. Se empieza en cero dado que C empieza
sus ndices de arreglo con cero. El elemento en la posicin_ms_izquierda es
106, el elemento en la posicin_ms_derecha es 168 y el elemento medio es 210.
La mediana de (106, 168, 210) es 168. 168 debe ser elegido como el elemento pivote y
los subarreglos deben ser divididos alrededor del elemento pivote 168.
A partir de la funcin main se hace una llamada a la funcin quickSort con el arreglo
a ser ordenado y el nmero de elementos como parmetros.
Antes de ordenar: 106 101 204 210 201 203 240 168
Llamada Recursiva # 1
temp: 240, k: 6, i: 7
( 210 101 204 106 201 203 [168] 240 )
temp: 210, k: 6, i: 8
( 168 101 204 106 201 203 [210] 240 )
Llamada Recursiva # 2
temp: 204, k: 5, i: 6
( 203 101 168 106 201 [204] ) 210 240
Llamada Recursiva # 3
temp: 203, k: 2, i: 3
( 168 101 [106] 203 201 ) 204 210 240
temp: 168, k: 2, i: 5
( 106 101 [168] 203 201 ) 204 210 240
Llamada Recursiva # 4
temp: 106, k: 1, i: 2
( 101 [106] ) 168 203 201 204 210 240
Llamada Recursiva # 5
temp: 203, k: 4, i: 5
101 106 168 ( 201 [203] ) 204 210 240
Para las siguientes pasadas de este ejemplo, se debe ejecutar la funcin recursiva:
doQuickSort(myArray, pivotElementIndex+1, right_pos, len_array);
A pesar de que la lista suministrada ha sido ordenada (para este ejemplo en particular).
Lista despus de ordenar: 101 106 168 201 203 204 210 240
En todos los mtodos de ordenamiento que se aprendieron en esta unidad, los arreglos
fueron ordenados en orden ascendente. Para ordenar en orden descendente, slo se
debe cambiar la condicin de verificacin que decide si es un ordenamiento ascendente
o descendente. Por ejemplo, en el ordenamiento por insercin, se debe cambiar la
condicin en el ciclo while como sigue:
while(j >= 0 && tempHolder > myArray[j]) {
myArray[j + 1] = myArray[j];
j--;
}
Para el ordenamiento ascendente, se usa la siguiente condicin:
tempHolder < myArray[j])
5. Algoritmos y Complejidad
Cuando se debe resolver un problema, pueden usarse cierto nmero de algoritmos
diferentes. Raramente se encuentra un problema especfico para el cul solo existe un
Por otra parte, se ver luego en esta unidad que las estructuras de datos juegan un rol
vital al lograr las cualidades deseables de algoritmos.
A continuacin se explican los factores que afectan el tiempo de ejecucin de un
programa.
Es til conocer los diferentes factores que afectan el tiempo de ejecucin de los
programas. Algunos de estos factores se listan a continuacin:
La naturaleza y tamao de los datos que se ingresan al programa.
La naturaleza y velocidad de ejecucin de instrucciones en la computadora
usada para ejecutar los programas.
La calidad del cdigo ejecutable generado por el compilador particular del
lenguaje de programacin.
La complejidad de tiempo del algoritmo, basada en la cual fue desarrollado el
programa.
Se explican brevemente cada uno de estos factores.
como Y. Suponga que se quiere que |y-y| < 0.01 entonces el tiempo de
ejecucin ser relativamente corto, comparado con un requerimiento de |Y-Y| <
0.000001. Si se acepta un Y, tal que |Y-Y| < 0.01, entonces 0.01 es la
tolerancia de aceptacin. Claramente, una entrada que busca una tolerancia de
aceptacin ms estricta tomar un mayor tiempo de ejecucin del algoritmo, que una
entrada que tiene una tolerancia de aceptacin relativamente baja.
Una forma de comparar T(n) con estas funciones estndar es usando la notacin
funcional O, llamada la notacin Big-Oh. En vez de proporcionar una definicin
matemtica rigurosa y su explicacin asociada, se proporcionar una explicacin simple
de esta notacin.
Cuando se dice que T(n) es O(f(n)) se sabe que f(n) es un lmite superior en la tasa
de crecimiento de T(n). Tambin se puede especificar el lmite inferior en la tasa de
crecimiento de T(n) usando la notacin Big-Omega.
3
T(n) = 25n + 7n es (n ).
3 2
Para empezar, se asume que los programas se evalan comparando T(n)e ignorando
las constantes de proporcionalidad. As un programa con O(n3) es mejor que uno con
O(2n). El primero tiene un crecimiento cbico mientras que el segundo tiene un
crecimiento exponencial. Tambin es posible que el primer programa tome 50n3
milisegundos para una ejecucin, mientras el segundo toma 3*2n milisegundos.
Existe la tentacin de pensar que no hay que preocuparse por asegurar tasas de
crecimiento menores. Dado que la velocidad de ejecucin de las computadoras se
incrementa, se pueden resolver problemas grandes con igual rapidez debido al
incremento en la velocidad de ejecucin de las computadoras. Sin embargo, esto es
incorrecto.
Se puede tener una idea de la complejidad del algoritmo calculando cuntas veces se
ejecuta un ciclo. En todos los algoritmos de ordenamiento, los ciclos iterativos son
establecidos basados en una condicin que involucra una comparacin de dos
elementos del arreglo. Es por esto, que se puede obtener una idea de la complejidad
mirando cuntas veces se hacen comparaciones en el algoritmo. El nmero promedio
de comparaciones realizadas en el algoritmo es una medida indirecta de la complejidad.
Para el mejor caso, el ciclo externo se ejecutar slo una vez para asegurar que la lista
est ordenada. El ciclo interno compara cada par. Esto significa que existen n-1
comparaciones. La complejidad en este caso es O(n).
El algoritmo de ordenamiento merge sort (por fusin) puede ser escrito como un
algoritmo recursivo o como uno iterativo. Se escribi un algoritmo iterativo. Usualmente,
se escribe como un algoritmo recursivo dado que es simple de desarrollar. El algoritmo
de ordenamiento merge sort (por fusin) requiere un arreglo adicional de n elementos.
Ya se ha visto en esta unidad que para que el ordenamiento merge sort (por fusin)
ordene un arreglo completo, requiere de a lo ms log2 n pasadas. Ahora, el programa
que se ha implementado en esta unidad para el algoritmo de ordenamiento merge sort
(por fusin). Especficamente observe la funcin sortAndAssign, que tiene la
sentencia para la comparacin de elementos del arreglo. Durante cada pasada puede
requerir de n comparaciones. As, el nmero total de comparaciones requerir n log2 n,
que es O(n log2 n).
El rendimiento del ordenamiento merge sort (por fusin) es el mismo tanto en el mejor
como el peor de los casos, dado que el arreglo necesita ser dividido, ordenado y
fusionado. Por lo tanto, el ordenamiento merge sort (por fusin) no es tan bueno para el
mejor de los casos como si lo es para el peor caso.
El peor caso para quicksort ocurre cuando la lista dada ya est ordenada. El algoritmo
tomar n comparaciones slo para obtener que el primer elemento ya est en su
posicin correcta. En este caso, el primer subarreglo contendr slo un elemento. El
segundo subarreglo contiene n-1 elementos. Aqu nuevamente, el segundo subarreglo
requiere de n-1 comparaciones para obtener que el siguiente elemento permanecer
en su posicin correcta. De esta forma el nmero total de comparaciones requerido es:
n + (n-1) + (n-2) + ... + 3 + 2 + 1 = n(n+1)/2
La complejidad del algoritmo es O(n2). El algoritmo quicksort tambin trabaja con dos
subarreglos, como el ordenamiento por fusin.
El mejor caso ocurre cuando el elemento pivote divide la lista dada en exactamente dos
mitades del mismo tamao en cada ocasin. En este caso, se requieren n
comparaciones para colocar el elemento pivote en su ubicacin correcta. El mtodo
quicksort es aplicado en forma recursiva en estos dos subarreglos. Quicksort requiere
de n/2 comparaciones (debido a que en el mejor caso se asume que la lista est
dividida en dos mitades iguales) para cada subarreglo, para colocar los elementos
Note que existen muchas versiones de los algoritmos merge sort (de fusin) y quicksort,
por esto, los nmeros de comparaciones requeridas son aproximados pero tpicos. En
implementaciones particulares, estas figuras pueden ser diferentes.
Una observacin interesante que se puede hacer es que mientras que los
ordenamientos por insercin y burbuja trabajan mejor para una lista ordenada que para
una desordenada, la complejidad algortmica del quicksort para una lista ordenada es
peor que su complejidad para una lista desordenada.
Usualmente
Merge Sort recursivo, pero
Si O(n log2 n) O(n log2 n)
(por Fusin) aqu se usa una
versin iterativa
No, pero pueden
Usualmente
Quicksort implementaciones O(n log2 n) O(n2)
recursivo
especficas
Los algoritmos ms usados en listas grandes son tanto los algoritmos merge sort (por
fusin) y quicksort (rpido). El ordenamiento quicksort (rpido) se usa en muchas
aplicaciones que usan ordenamientos intensamente, dado que es ms eficiente que el
ordenamiento merge sort (por fusin). El ordenamiento quicksort (rpido) tiene en
general un mejor rendimiento.
Resumen
Ahora que Ud. ha completado esta unidad, debe ser capaz de:
Explicar acerca de la tcnica de ordenamiento merge sort (por fusin).
Describir cmo escribir un algoritmo para desarrollar la tcnica de ordenamiento
merge sort (por fusin).
Explicar acerca de la tcnica de ordenamiento quicksort (rpido).
Describir cmo escribir un algoritmo para desarrollar la tcnica de ordenamiento
quicksort (rpido).
3) El ordenamiento merge sort (por fusin) requiere de log2n pasadas para ordenar
un arreglo.
a) Verdadero.
b) Falso.
Preguntas Opcionales
Las preguntas presentadas aqu cubren los temas de Algoritmos, Complejidad y
Comparacin de Algoritmos. Slo debe intentar resolverlas si ha estudiado estos dos
temas.
6) Cul de los siguientes afecta el tiempo de ejecucin de un programa?
a) Tamao de los datos de entrada.
b) Velocidad de ejecucin de las instrucciones.
c) Naturaleza de los datos de entrada.
d) Complejidad en tiempo de los algoritmos.
9) Cul de las siguientes tcnicas de ordenamiento tiene O(n log2 n) para el peor
de los casos?
a) Ordenamiento por Insercin.
b) Ordenamiento Quicksort (Rpido).
c) Ordenamiento Merge sort (por Fusin).
d) Todos los anteriores.
10) Cul de las siguientes tcnicas de ordenamiento tiene O(n) para el mejor de los
casos?
a) Ordenamiento Merge sort (por Fusin).
b) Ordenamiento por Insercin.
c) Ordenamiento por Burbuja.
d) Ordenamiento por Seleccin.
Ejercicio de Laboratorio
Considerar un arreglo que contenga nombres de libros y sus autores. Cada fila en el
arreglo contiene el nombre de un libro, seguido de una coma, un espacio y el nombre
del autor. Un ejemplo de ello se muestra a continuacin:
The Ultimate Guitar Book, Bacon Tony
La sintxis por defecto es:
<nombre de libro>, <nombre de autor>
Se toma la entrada del usuario usando la misma sintaxis. Si no se encuentra ninguna
coma en la entrada, se asume que la entrada es solamente el nombre del libro. Para
simplificar el ejercicio, se asumir que slo se incluye el nombre de un autor, que es el
autor principal del libro.
1) Lea una lista de nombres de libros y sus autores en un arreglo. El final de la fila se
indica con '\n' y el final de la entrada con 'END'.
2) Usando ambas tcnicas de ordenamiento explicadas en la Unidad 5: Tcnicas de
Ordenamiento Avanzado, ordene el arreglo de caracteres y muestre los elementos
ordenados como se muestra:
Data Structures and Program Design in C, Robert L. Kruse
David Brin
Foundation's Triumph
Just For Fun, David Diamond
The Ultimate Guitar Book, Bacon Tony
Twelve Red Herrings, Jeffrey Archer
Recomendaciones
1) Crear dos arreglos que contengan los nombres de los libros y de los autores.
3) Leer la informacin dada por el usuario, lnea por lnea, hasta el final de la nueva
lnea. Cada lnea ingresada por el usuario se sobreentiende que contendr el
nombre del libro y el autor.
4) Guardar cada lnea de entrada como una fila en el primer arreglo.
5) Verificar si la palabra 'END' ha sido ingresada. Si es as, finalizar el ingreso y
guardar el nmero de elementos en una variable. En caso contrario, continuar
leyendo la siguiente lnea de entrada del usuario.
6) Al terminar el ingreso de todas las lneas del usuario, copiar el contenido del primer
arreglo hacia el segundo.
7) Mostrar el mensaje Antes de utilizar el ordenamiento quicksort: y
mostrar los elementos del primer arreglo.
8) Ordenar usando quicksort. Recordar realizar los cambios a la funcin de quicksort
para que trabaje con arreglos de caracteres. A continuacin se muestra cmo la
funcin findPivotElement ha sido modificada para manejar arreglos de
caracteres:
char * findPivotElement(Element_type \
elements[ROWSIZE][COLSIZE], int left_pos, \
int right_pos) {
int mid_point;
Element_type temp[COLSIZE];
mid_point = (left_pos + right_pos)/2;
// Intercambiar el elemento ms a la izquierda con l
que
// est a la mitad. Devolver el elemento ms a la
izquierda
// como elemento pivote para la funcin invocada
strcpy(temp, elements[left_pos]);
strcpy(elements[left_pos], elements[mid_point]);
strcpy(elements[mid_point], temp);
return (elements[left_pos]);
}
9) Mostrar el mensaje Despus de utilizar el ordenamiento quicksort:
y mostrar los elementos del arreglo ordenado.
10) Mostrar el mensaje Antes de utilizar ordenamiento merge sort: y
mostrar los elementos del segundo arreglo copiado del primero anteriormente.
11) Ordene usando merge sort. Recordar realizar los cambios a la funcin de merge
sort para que trabaje con arreglos de caracteres. Se muestra a continuacin una
funcin de muestra la cual necesita el cambio:
1. Introduccin
En esta unidad, se aprender acerca de otra actividad comn en las aplicaciones
conocida como bsqueda. Localizar informacin es una de las operaciones clave en
muchas aplicaciones. Ejemplos abundan en la vida real, como son:
Localizar sinnimos de una palabra en un diccionario.
Localizar la direccin de un alumno de la base de datos universitaria.
Localizar del nmero de cuenta del cliente de un banco.
Localizar todos los agentes de comercio Ferrari en Europa.
Localizar los empleados que han estado trabajando en una organizacin por
ms de 20 aos y estn ganando un salario anual de $1M.
La bsqueda se lleva a cabo basada un elemento particular, el cual es generalmente
una entrada. Este elemento, es la base de la bsqueda, es el llamado elemento de
bsqueda. Tambin se le conoce como elemento clave. El procedimiento usado en
buscar elementos que concuerden con la clave es un aspecto importante de la
bsqueda.
8. int k;
9. /* leer n, el nmero de elementos en array */
10. printf("Enter integers elements to fill the array
...\n\n");
11. k = 0;
12. do {
13. printf("Enter an integer ... end with -9999\n");
14. scanf("%d", &element);
15. if (element != -9999)
16. elements[k++] = element;
17. } while (element != -9999);
18.
19. printf("\n\nEnter the integer to search ...\n");
20. scanf("%d", &element);
21. if (linearSearch(elements,k,element))
22. printf("Element %d found in array\n",element);
23. else
24. printf("Element %d not found in
array\n",element);
25. }
El cdigo C termina aqu
3. Bsqueda Binaria
En la Unidad 2 - rboles, se aprendi acerca del rbol de bsqueda binaria y se
present brevemente el concepto de bsqueda binaria. El rbol de bsqueda binaria
sigue el algoritmo binario. A continuacin se va a aprender ms acerca de este
algoritmo.
Paso 3: El ndice 0 del arreglo se llamara top, y el ndice n-1 se llamara bot.
Paso 4: Encontrar el elemento central. Para realizar esto se debe encontrar el punto
medio en el arreglo. Se puede hacer usando la frmula:
mid = (top + bot) /2
En este ejemplo, considere que el nmero de elementos, n es 9. Entonces el valor de
bot es 8, y el valor de mid es:
(0 + 8) / 2 = 4
Si el nmero de elementos fuese 10 y bot fuese 9, el valor de mid ser fijado en 4,
como resultado de la divisin entera.
Paso 5: Verificar si el elemento a buscar es igual al elemento en mid. Si es as,
entonces tomar la accin apropiada. Ir al paso 8.
Paso 6: Si el elemento a buscar no es igual al elemento en mid, verificar si este es
menor que el elemento en mid. Si es as, entonces en la mitad superior del arreglo
ser necesario hacer la bsqueda. Fije un nuevo valor a bot, as:
bot = mid 1
Si el elemento a buscar es mayor que el elemento en mid, entonces ser necesario
hacer la bsqueda en la mitad inferior del arreglo. Fije un nuevo valor a top, as:
top = mid + 1;
En todos los casos, se ha reducido el nmero a la mitad el nmero de elementos a
comparar.
Paso 7: Verificar s top > bot. Si es cierto, entonces el elemento a buscar no se
encontr. Tomar la accin apropiada. Si es falso, entonces ir al paso 4.
Paso 8: Fin del algoritmo.
Del algoritmo presentado anteriormente, note que los valores de top y mid van
cambiando durante el proceso de bsqueda, basados en el elemento a buscar y el
elemento en mid. Mientras que top sea menor o igual a bot, la bsqueda contina.
top llegar a ser ms grande que bot ya sea cuando el valor de bot alcance 1, o
cuando el valor de top alcance n.
Para ms ejemplos de bsqueda binaria, ver las Figuras 5.2 y 5.3. Use el algoritmo
dado anteriormente para comprender estos ejemplos claramente. Recorrer el algoritmo,
cambiando los valores de mid, top y bot para todas las iteraciones. Los valores de
mid, top y bot despus de cada iteracin se muestran claramente en las figuras.
Figura 5.2 muestra una bsqueda sin xito, donde el elemento a buscar es 200.
El valor de bot finalmente alcanza1, y la condicin top > bot llega a ser cierta.
La Figura 5.3 tambin muestra una bsqueda sin xito, donde el elemento a buscar es
100007.
En este ejemplo, el valor de bot finalmente alcanza a n, y la condicin top > bot
llega a ser cierta.
Elemento a buscar200:
Nmero de elementos en la bsqueda: 18
Elementos del arreglo:-100 -4 0 30 30 81 100 101
200 467
3213 43555 50000 60000 90000 100001 100006
La bsqueda binaria del elemento 100007 en el mismo arreglo se ejecuta como sigue:
Elemento a buscar 100007:
Nmero de elementos en la bsqueda: 18
Elementos del arreglo:-100 -4 0 30 30 81 100 101
200 467
2001 3213 43555 50000 60000 90000 100001 100006
Suponga que el elemento que se busca est en la primera posicin. En tal caso, solo se
realiza una comparacin antes de encontrar el elemento. Si el elemento que se est
buscando est en la segunda posicin, entonces se necesitan dos comparaciones antes
de encontrar el elemento.
La bsqueda binaria, por otro lado, es ms rpida que la bsqueda lineal, dado que en
cada comparacin se reduce el tamao de bsqueda a la mitad. Suponga que el
nmero de elementos en el arreglo es 16, y no se encuentra el elemento que coincida
en la primera comparacin. La bsqueda binaria prosigue dividiendo el arreglo en otros
ms pequeos de ocho, cuatro, dos y finalmente un elemento.
As, si el nmero de elementos fuera n, se divide el arreglo en otros conteniendo n/2,
n/4, n/8, n/16, y as sucesivamente elementos. En cada arreglo se hacen dos
verificaciones.
Para n = 32, en lugar de hacer 32 comprobaciones para una bsqueda sin xito, se
harn solamente 6*2 = 12 verificaciones. En todos, solamente se verifican seis
arreglos:
Arreglo con 32 elementos
Arreglo con 32/2 elementos
Arreglo con 32/4 elementos
Arreglo con 32/8 elementos
Arreglo con 32/16 elementos
Arreglo con 32/32 elementos
De esta forma, es claro que la bsqueda binaria es ms rpida que la lineal.
Ahora se aprender otro mtodo de bsqueda que usa tablas hash y hashing.
4. Tablas Hash
Una tabla hash es una estructura de datos que proporciona un mtodo rpido y ms
eficiente para buscar los elementos de un arreglo. Para entender la importancia de una
tabla, considere la siguiente lista de palabras:
complexity
tree
node
while
method
sentence
rephrased
wrong
dictionary
word
explanation
probing
binary
linear
paragraph
Imagine encontrar el elemento linear realizando una sola verificacin, o un par de
verificaciones sin ordenar o dividir. Esto es posible si se hace corresponder (map) cada
elemento a un nico entero, el cual acta como valor ndice del arreglo donde la palabra
se encuentra. Por ejemplo, si linear se hace corresponder a 12 (por algn mtodo),
entonces se encontrar a linear simplemente diciendo word[12], donde word es
un arreglo de palabras.
Si se adapta este mtodo para una aplicacin que requiera bsqueda extensiva, el
arreglo en tal aplicacin se conoce como tabla hash, y los mtodos usados para hacer
corresponder los valores clave en la tabla hash se denominan funciones hash o
hashing. Usando funciones hash, se puede llegar a una localidad especfica, como 207,
para el primer elemento encontrado en la lista de entrada. No importa donde el
elemento est guardado en la tabla hash con tal de que se pueda encontrar fcilmente
el elemento. El valor regresado por una funcin hash se le conoce como valor hash.
Las tablas hash se definen de tamao grande, de modo que se pueda representar un
rango grande de ndices. Para almacenar 1000 enteros en una tabla hash se puede
definir la tabla hash de un tamao de 10000 enteros, as los valores hash pueden variar
entre 0 a 9999.
Se tomar un ejemplo para comprender cmo las tablas hash y hashing mejoran el
tiempo de bsqueda. La funcin hash que se elegir ser la siguiente:
Nmero de caracteres en la palabra * valor ASCII del
primer carcter
Aplicando la funcin hash en cada palabra se obtienen los valores hash, como se
muestran a continuacin:
complexity 990 10 * 99 = 990
tree 464 4 * 116 = 464
node 440 4 * 110 = 440
while 595 5 * 119 = 595
method 654 6 * 109 = 654
sentence 920 8 * 115 = 920
rephrased 1026 9 * 114 = 1026
wrong 595 5 * 119 = 595
dictionary 1000 10 * 100 = 1000
word 476 4 * 119 = 476
La Figura 5.5 bosqueja una lista parcial de palabras. Se notan dos aspectos importantes
en la tabla hash:
El orden de almacenamiento en la tabla hash de ninguna manera es similar al
orden de entrada de las palabras. La primera palabra de la tabla hash es
Para calcular el valor hash de un elemento, la funcin hash se aplica al elemento que
ser insertado. El valor hash apunta a uno de los valores ndices del arreglo definido. Si
esa posicin en la tabla est vaca, entonces el elemento es insertado en esa posicin.
Si la posicin no est vaca, esto implica que una colisin ha ocurrido. Esta colisin
debe ser resuelta antes de ser insertado el elemento en la tabla hash. Se puede usar
una funcin rehash para resolver la colisin.
Por ejemplo, una simple funcin rehash retornar un valor mayor que aquel valor hash
obtenido cuando la colisin ocurri. As, en el ejemplo, si el valor rehash retorna 595 +
1 = 596, entonces la segunda palabra wrong, con valor hash 595, ser almacenada
en la posicin 596 en la tabla hash. La funcin rehash se usa slo cuando una posicin
especfica se encuentra ocupada.
Asuma que m ser 25. Considere los valores claves 2546, 128, 250 y 32767. El
resultado de aplicar la funcin hash se muestra a continuacin:
2546 modulo 25 = 21
128 modulo 25 = 3
250 modulo 25 = 0
32767 modulo 25 = 17
Aqu se pueden aprender algunas cosas.
Todos los valores claves se consiguen al hacer correspondencia (map) en el
intervalo 0 a 24.
Si se desea que la funcin hash haga corresponder valores en el intervalo [1,25],
entonces lo que debe hacerse es definir la funcin como
Hash(key) = (key modulo m) + 1
Usualmente, se usan enteros positivos en este tipo de funcin hash.
Si se quiere que la funcin hash haga corresponder a valores en un amplio rango,
entonces el valor de m debe ser alto. Pero escogiendo valores grandes no es suficiente.
Por ejemplo, si se selecciona un nmero tal como 24000, este no cumplir las otras
propiedades de una buena funcin hash. Especialmente, 24000 es divisible por 2, 4, 6,
8, etc. Los cuales son enteros pequeos. Por lo tanto, se espera que un gran nmero de
claves correspondan (map) a 0 1, y como resultado, ocurrir una gran cantidad de
colisiones.
Cmo se puede evitar esto? Se puede seleccionar un nmero primo grande. Dado que
un nmero primo no es divisible por ningn otro nmero que no sea el mismo y 1,
usando un nmero primo se reduce el nmero de colisiones.
Este mtodo es eficiente en cierta medida, por que es simple. Sin embargo, involucra
divisin, la cual no es tan eficiente como la suma, diferencia o desplazamiento de bit. Se
puede usar desplazamiento de bit, por que el desplazamiento de 1 bit de un entero a la
derecha es equivalente a dividir el nmero por 2. En este caso, m debe estar expresado
en potencias de 2. Si embargo, si m es expresado en potencias de 2, este ser un
nmero no primo y inevitablemente resultar en un nmero alto de colisiones.
Claramente, hay una decisin entre eficiencia y colisin al escoger el nmero.
Este mtodo asegura que cada bit de la clave esta involucrada en la transformacin del
valor hashed entre 0 y m. Esta es una caracterstica deseable. Se sabe ahora cmo
seleccionar m desde el mtodo de divisin modular. Para seleccionar k, se debe
Libro 1: Estructura de Datos y Algoritmos
Unidad 7: Tcnicas de Bsqueda 275
La parte entera de (2x)*k es relativamente primo de 2x. Lo que significa que los nicos
divisores comunes de (2x)*k y 2x son 1, y ellos mismos.
El valor de k no debe estar muy cerca de 0 1.
Valor Hash = 82
Note que se podra haber seleccionado cualquier mtodo para eliminar los de dgitos
desde cualquiera de los extremos para conseguir el valor hash. Pero una vez que los
dgitos a ser eliminados son seleccionados (o los dgitos a seleccionarse para los
valores hash son seleccionados). La misma regla debe ser aplicada a todos los valores
claves. Estudios empricos muestran que el mtodo mid-square es el ms pobre, ya que
no consigue igual distribucin de claves. Debido a esta deficiencia, este mtodo es poco
usado.
Partes sumadas = 25 + 0 = 25
Valor Hash = 25
Para key = 32767
La clave (key) es fraccionada entre 32, 76 y 7 (Note que se
tienem tres partes)
Partes sumadas = 32 + 76 + 7 = 115
Se omiti un dgito de direccin, es decir, 1
Valor Hash = 15
En algunas versiones del mtodo de Plegado (Folding), en cada una de las partes
fraccionadas sus dgitos primero son invertidos antes de ser sumados. Por ejemplo, en
el caso de la clave 32767, se tienen las partes 32, 76 y 7. La parte par incluida es 76.
Se invierte a 67. Incluso la otra parte par, 32, se invierte a 23. La suma de las partes da
23 + 67 + 7 = 97. Dejando igual la parte de 1 dgito, se tiene el valor hash como 97.
Se han estudiado cuatro funciones hash. Se pueden construir otras funciones tambin.
Pero la mayor parte de las funciones no evitan las colisiones. A continuacin se
estudian los mtodos de resolucin de colisiones.
Word
Binary
Linear
Probe
Tambin asuma que se escogi la funcin hash correcta, as como los supuestos
valores hash con respecto a cada una de las palabras mencionadas anteriormente.
Tree 2
Node 7
While 11
Method 2
Sentence 6
Dictionary 1
Word 11
Binary 4
Linear 14
Probe 9
Note que hay dos colisiones aqu. Las palabras Tree y Method tienen valores hash de
2. Similarmente, las palabras While y Word tienen el mismo valor hash, 11.
Claramente, no se pueden poner Tree y Method en la misma posicin de la tabla. La
palabra Tree viene a ser la primera, as sta es colocada en la posicin 2 de la tabla.
Entonces, las otras palabras se colocan en la tabla, hasta que se alcance la palabra
Method. En este punto, la tabla luce como se muestra a continuacin.
1 -
2 Tree
3 -
4 -
5 -
6 -
Nod
7
e
8 -
9 -
1
-
0
1 Whil
1 e
1
-
2
1
-
3
1 -
Libro 1: Estructura de Datos y Algoritmos
Unidad 7: Tcnicas de Bsqueda 279
4
1
-
5
Dado que Tree est en la posicin 2, no se puede colocar Method all. El mtodo
anlisis lineal (linear probing) busca ms all de la posicin hasta una posicin libre. En
esta tabla, la posicin 3 est libre. As, se puede colocar Method all. Las otras palabras
en la lista pueden ser colocadas en la tabla usando este mtodo de resolucin de
colisiones. Se muestra la tabla final despus de haber colocado todas las palabras.
Dictionar
1
y
2 Tree
3 Method
4 Binary
5 -
Sentenc
6
e
7 Node
8 -
9 Probe
1
-
0
1
While
1
1
Word
2
1
-
3
1
Linear
4
1
-
5
Note como la colisin de While y Word son manejadas por anlisis lineal (linear
probing).
Este mtodo tiene algunas desventajas. Asuma que la tabla est llena. Entonces, as se
irn insertando valores en la tabla a travs de anlisis lineal (linear probing), basados en
la ocurrencia de las colisiones, se descubrir que hay una tendencia de los registros a
agruparse juntos. El agrupamiento no es deseable, dado que esto indica que las claves
no estn distribuidas uniformemente.
Otro mtodo que evita el agrupamiento (clustering) es el de determinar cun lejos desde
el punto de la colisin se mantendr este registro. Esto puede ser dado por una funcin
increment. No se entrar en detalles sobre la funcin increment en este curso. As con
rehashing, la funcin increment se calcula cuando ocurre una colisin y determina la
nueva posicin.
Ambos mtodos trabajan con un grado de xito limitado en tablas grandes. La debilidad
del anlisis lineal (linear probing) es que requiere hacer pruebas secunciales para
determinar la prxima ubicacin libre. Cuando algunas claves hacen corresponder
(map) a la misma ubicacin, esto llega a ser una desventaja.
5 -
6 -
7 Node
Sentenc x+1
8
e
9 Probe
1
-
0
1
While
1
1 Dictionar x+1
2 y
1
-
3
1
Linear
4
1 x+4
Word
5
Es necesario sealar el valor probado antes de insertarlo en la tabla hash.
Quadratic probing es superior a Anlisis Lineal (Linear probing), dado que reduce el
agrupamiento (clustering). Observe que las palabras While, Dictionary, Word y
Linear son agrupadas en la tabla de anlisis lineal. Por lo tanto, con el anlisis
cuadrtico (quadratic probing) se prueban menos posiciones.
Hay algunas otros mtodos de resolucin de colisiones, algunos de los cuales son muy
sofisticados. La discusin de estos mtodos va ms haya del alcance de este curso.
Las funciones hash y rehash se implementan como simples funciones que usan
aritmtica modular.
Libro 1: Estructura de Datos y Algoritmos
Unidad 7: Tcnicas de Bsqueda 283
La siguiente funcin ayuda a insertar elementos en la tabla hash. Note cmo la funcin
rehash se utiliza repetidamente para obtener el ndice de la tabla donde est
almacenado el elemento.
A continuacin para ilustrar se escribe una funcin que invoca todas estas funciones.
Note que el programa no est diseado para hacer nada especfico, ms all de la tarea
de mostrar la manera en la que se pueda invocar a las funciones que trabajan con las
tablas hash.
Resumen
Ahora que Ud. ha completado esta unidad, debe ser capaz de:
Explicar las diversas tcnicas de bsqueda disponibles para operaciones en
arreglos y otras estructuras de datos.
Describir cmo desarrollar un algoritmo para la tcnica de bsqueda lineal.
Describir cmo desarrollar un algoritmo para la tcnica de bsqueda binaria.
Explicar el uso de hashing para insertar y localizar elementos en una tabla hash.
Discutir los mtodos de resolucin de una colisin hash.
6) El algoritmo bsico para localizar el valor de ndice en una tabla hash para
insercin y locacin de un elemento es el mismo.
a) Verdadero.
b) Falso.
7) Cul de los siguientes son mtodos para escoger una funcin hash?
a) Divisin Modular.
b) Multiplicacin.
c) De Plegado (Folding).
d) Ninguna de las anteriores.
8) Cules de los siguientes mtodos crea una parte fraccional para calcular los
valores hash?
a) Divisin Modular.
b) Multiplicacin.
c) De Plegado (Folding).
d) Mid-square.
Ejercicios de Laboratorio
La compaa XYZ es fabricante de partes de auto y produce millones de autopartes
todos los das. La compaa asigna un nmero de parte nico a cada parte. El nmero
de parte es alfanumrico y consiste de tres partes:
Un cdigo entero de dos dgitos indicando el tipo de carro al que pertenece la
parte.
Un cdigo de cinco letras de caracteres indicando el mes y da de la produccin.
Un cdigo entero de seis dgitos indicando un nmero de identificacin nica de
la parte producida.
Un ejemplo se presenta a continuacin:
09JUN22100056
Donde:
09 es el tipo de carro.
JUNE 22 es la fecha de produccin.
100056 es la identificacin nica de la parte fabricada el 22 de junio. La
identificacin nica va de un rango de 000000 a 999999.
La compaa, en muchos casos, requiere datos sobre todas las partes fabricadas en un
da especfico, pertenecientes a un tipo especfico de carro. Estos datos pueden ser
requeridos en orden o en desorden.
Se requiere que usted escriba un programa en C que haga lo siguiente. Asuma que los
datos son ingresados para un da y mes especfico.
1) Construya una lista de partes de carros que tengan el nmero de partes como nica
entrada en el arreglo. Para construir la lista se deben seguir los siguientes pasos a
continuacin:
a. El da y mes de la fabricacin se toma como una entrada una vez al inicio del
programa.
b. La entrada se toma para el tipo de carro y nmero de identificacin nico. El tipo
de carro debe ser ingresado como dos caracteres y la identificacin nica como
seis caracteres.
2) Mantenga un arreglo que contenga los nmeros de partes en el orden de entrada.
Imprima todos los nmeros de parte, en el orden de entrada.
3) Tomando como entrada un tipo de carro y un nmero de identificacin nico,
determine si el nmero de parte est disponible en el arreglo. Utilice una bsqueda
binaria. El orden original de entrada del nmero de partes no debe afectarse.
Consejos tiles:
Cree una estructura que contenga el arreglo de nmeros de partes y el nmero
de total de partes dado como una entrada.
Tome el da y mes de fabricacin como entrada y ejecute una validacin de la
fecha. Use el ao actual como ao. Tome la entrada del da y mes como
enteros. #define el valor. Utilice la funcin de validacin de fecha que se da a
continuacin.
Ejercicios de Laboratorio
Los compiladores que compilan programas fuente en lenguajes de alto nivel tales como
C, Pascal, etc., mantienen una estructura de datos llamada tabla de smbolos. Una de
las opciones para implementar una tabla de smbolos es a travs de tablas hash. La
tabla de smbolos contiene, entre otras cosas, el smbolo en s mismo y algunos
atributos sobre el smbolo derivado del contexto de su uso en el programa.
Escriba las siguientes funciones en C para implementar las operaciones en una tabla de
smbolos usando hashing.
createSym(s): Crea una nueva tabla de smbolos s vaca y la inicializa.
insertSym(s, x): Inserta el smbolo x en la tabla de smbolos s.
deleteSym(s, x): Elimina el smbolo x de la tabla de smbolos s, si x existe.
findSym(s, x): Encuentra la posicin del smbolo x en la tabla de smbolos s, si
existe o de otra manera devuelve un error.
Tambin, escriba un programa main que invoque las diferentes funciones para
comprobar la funcionalidad.
Consejos tiles
El smbolo de entrada debe ser un arreglo de caracteres.
Definir un arreglo para mantener los smbolos. ste actuar como la tabla hash.
Inicializar todas las filas en la tabla hash a \0 (carcter nulo). El mismo carcter
nulo puede ser usado para cualquier otra verificacin en otro programa.
Emplee cualquier funcin hash buena. Recuerde realizar rehash si la posicin se
encuentra ocupada.
Cuando un smbolo es ingresado, usando la funcin hash, derive el valor hash y
coloque el smbolo en el arreglo en la posicin equivalente al valor hash.
Para borrar un smbolo, simplemente ponga la celda en la tabla hash a \0. El
nodo puede continuar existiendo en la lista enlazada.
Para encontrar un elemento, busque a travs de la tabla hash.