Clase Modelo Listas Enlazadas Pilas Y Colas

UNIVERSIDAD TECNOLOGICA DE LOS ANDES FACULTAD DE INGENIERÍA CARRERA PROFESIONAL DE INGENIERIA DE SISTEMAS E INFORMATICA

SÍLABO DE LA ASIGNATURA: ALGORITMOS Y ESTRUCTURA DE DATOS SEMESTRE ACADÉMICO 2009-I I. DATOS GENERALES 1.1. Nombre de la asignatura 1.2. Nombre de la Facultad 1.3. Carrera Profesional 1.4. Nivel de estudios 1.5 Código de la Asignatura 1.6. Pre_requisito 1.7. Semestre Académico 1.8. Nro. de hrs. semanales 1.9. Duración de la Asignatura 1.10. Créditos 1.11. Categoría de la asignatura 1.12. Profesor 1.13. Horario

: Algoritmos y Estructura de Datos I : Facultad de Ingeniería : Ingeniería de Sistemas e Informática : III semestre : SI032 : SI021 : 2009-I : 5 hrs. : 17 semanas : 4 créditos : FICI : Ing. Reynaldo Miranda Pomacondor : LU – MA 07:00 – 9:00; Vi 09:00 – 10:00

II. SUMILLA Definiciones básicas: Dato, Tipo de Datos, Operadores e Identificadores. Algoritmos: Concepto, características, representaciones. Desarrollo de algoritmos en pseudocódigo. Estructuras de Control: secuenciales, selectivas y repetitivas. Datos estructurados: Arreglos y operaciones. Subprogramas: funciones, procedimientos y recursividad. Registros y Archivos. Programación Dinámica: punteros, operaciones, listas (pilas, colas) y árboles. III. OBJETIVOS General: Los alumnos al finalizar el curso estarán en la capacidad de elaborar algoritmos que resuelvan problemas de propósito general. Específicos: 1. Presentar la diversidad de los algoritmos y sus aplicaciones. 2. Aplicar los Algoritmos Estructurados (Programación Estructurada) para la solución de problemas. 3. Optimizar los algoritmos estructurados de forma que sean más simples y eficientes. IV. DESARROLLO DE CONTENIDOS PRIMERA UNIDAD: Conceptos Básicos Conceptos necesarios para iniciar el desarrollo de algoritmos. Primera Semana: Introducción. Definiciones Básicas: • Concepto de Datos – Tipos de datos. • Operadores: Aritméticos, Lógicos y de Comparación. • Identificadores: Concepto, Constantes, Variables. Operador de Asignación, Acumulador y Contador.

Algoritmos: Concepto, características y ejemplos. Representaciones de los algoritmos. Aplicaciones simples de los algoritmos.

SEGUNDA UNIDAD: Programación en Pseudocódigo Desarrollo de algoritmos estructurados en pseudocódigo mediante las estructuras Control.

de

Segunda Semana: Estructuras de Control: • Secuenciales. • Selectivas: Simples y Múltiple. • Estructuras Selectivas Anidadas. Tercera Semana: • Repetitivas (Bucles): Bucle con número de repeticiones pre-establecido, Bucle con entrada controlada y Bucle con salida controlada. • Estructuras Repetitivas Anidadas. • Aplicaciones. TERCERA UNIDAD: Estructuras de Datos y Subprogramas Construcción y empleo de datos estructurados de tipo estático. Diseño de subprogramas. Cuarta Semana: Arreglos: • Vectores: Creación, asignación, lectura y escritura. • Operaciones con vectores: Búsqueda, Ordenamiento, Eliminación e Inserción. Quinta Semana: • Matrices: Creación, asignación, lectura y escritura. • Operaciones con matrices. Sexta Semana: Cadenas: • Creación y uso. • Operaciones con cadenas. • Arreglo de cadenas. Aplicaciones. Séptima Semana: Subprogramas: • Funciones: Creación y uso. • Variables globales y Locales. • Aplicaciones. Octava Semana: Examen Parcial Novena Semana: • Procedimientos: Creación y uso. • Parámetros por referencia o valor. • Aplicaciones. Décima Semana: Recursividad: • Funciones recursivas. • Procedimientos recursivos. • Aplicaciones. Décimo Primera Semana: Registros: • Creación y uso. • Operaciones con registros. • Arreglo de registros. Aplicaciones.

2

Décimo Segunda Semana: Archivos de Acceso Aleatorio: • Creación y uso. • Operaciones con archivos: Lectura – escritura, búsqueda y ordenamiento. • Aplicaciones. CUARTA UNIDAD: Programación Dinámica Construcción y empleo de datos dinámicos para generar listas dinámicas y árboles de búsqueda. Décimo Tercera Semana: Punteros: • Creación y uso. • Operaciones con punteros. Listas enlazadas: • Creación de nodos. • Creación y recorrido de una Pila. • Creación y recorrido de una Cola. Décimo Cuarta Semana: Operaciones con listas: • Búsqueda. • Eliminación • Inserción. Décimo Quinta Semana: Árboles: • Creación de un árbol binario de búsqueda. • Recorridos de un árbol binario de búsqueda. • Aplicaciones Décimo Sexta Semana : Examen Final Décimo Séptima Semana : Examen Sustitutorio V. METODOLOGÍA Las clases serán desarrolladas en forma teórico – práctica, induciendo en el alumnos los conceptos mediante comparación de hechos reales. Se pondrá énfasis en la participación de los alumnos en la resolución de problemas planteados en clase.

VI. MEDIOS Y MATERIALES Para el desarrollo de las clases se utilizará por lo general pizarra y tizas. Se entregará una serie de ejercicios relacionados con los temas del curso Las actividades que realiza el alumno son: a) Copiar los archivos lógicos que el profesor prepara desde el blog de la asignatura correspondiente. b) Preparar su exposición y exponer el tema de clase. c) Asistir al 100% a los laboratorios. Cada Laboratorio es calificado. Las actividades que realiza el docente son: a) Preparar el material correspondiente a cada tema. b) Publicar en blog: www.gestionutea.blogspot.com los archivos correspondientes con la antelación previa c) Realizar la retroalimentación correspondiente devolviendo y resolviendo las evaluaciones escritas. d) Facilitar los equipos necesarios para exposición de temas. Actuar de moderador en los temas de discusión en clase

3

VII. EVALUACIÓN La evaluación busca identificar, valorar e interpretar los conocimientos generados (examen de conocimientos), el dominio de conceptos así como el trabajo en equipo (trabajo de aplicación) y el esfuerzo individual (participación en clase y trabajo individual). Los criterios anteriores mencionados tendrán la siguiente ponderación: PF = ((P1+ P2+ P3)+Trabajos + EP1+ EP2)/6 PF = Promedio final P1 = Primera evaluación parcial P2 = Segunda evaluación parcial P3 = Tercera evaluación parcial EP1 = Promedio de la evaluación de proceso de la primera parte EP2 = Promedio de la evaluación de proceso de la segunda parte VIII.BIBLIOGRAFIA 1. Fundamentos de Programación. “Algoritmos y Estructura de Datos”. Luis Joyanes Aguilar. 2da. Edición 1999. Editorial Mc. Graw Hill. 2. Metodología de la Programación: Algoritmos, Diagrama de Flujo y Programas. Tomo I y II. Oswaldo Cairó. Editorial Computec 1996. 3. Algorítmica, Diseño y Análisis de Algoritmos, Funciones e Imperativos. Javier Galvéz / Juan C. Gonzáles / Ángel Sánchez / J. Ángel Velásquez. Editorial RAMA 1993. 4. Metodología de la Programación. Luis Joyanes Aguilar. Editorial Mc. Graw Hill. 5. Estructura de Datos y Organización de Archivos. Mary E. S. Loomis. 2da. Edición 1991. Editorial Prentice Hall Hispanoamericana. 6. Programación Estructurada: Un enfoque algorítmico. Leobardo López R. Editorial Computec. 7. Estructuras de Datos y Diseño de Programas. Robert L.Kruse. Editorial Prentice Hall. 8. Estructuras de Datos. Cairó – Guardate. Editorial Mc. Graw Hill 2001.

4

UNIVERSIDAD TECNOLOGICA DE LOS ANDES FACULTAD DE INGENIERÍA CARRERA PROFESIONAL DE INGENIERIA DE SISTEMAS E INFORMATICA Apuntadores. (Inicialización dinámica) Todas las variables tienen una dirección de memoria única que indica el inicio del área de la memoria ocupada por su valor. La cantidad de memoria utilizada depende del tipo de dato involucrado, en el caso de un int el área son dos bytes, un float utiliza 4 bytes. En un arreglo, el área es igual al número de elementos multiplicado por el área que requiere uno de los elementos del arreglo. En una estructura, el área es igual a la suma de las áreas que requieren cada miembro de la estructura. Los datos son almacenados en forma ordenada y predecible, de tal manera que es posible accesarlos utilizando una variable que contiene la dirección de este dato, a esa variable se le llama apuntador. Los apuntadores tienen la ventaja de que permiten manipular estructuras de datos fácilmente, sin tener que mover los datos en memoria. Al colocarse en la dirección del primer elemento de un arreglo, el apuntador puede ser usado para inicializar los elementos o para ver los valores de los elementos del arreglo. Sumando o restando del apuntados se puede mover sobre los elementos del arreglo. Los apuntadores se pueden usar para permitir que una función reciba y cambie el valor de una variable. Esto permite evitar la necesidad de declarar variables globales. Los apuntadores también son utiles para asignar memoria mientras el programa esta corriendo. Un apuntador se declara de la siguiente manera: type * name. donde type es cualquier tipo de dato. Ejemplos de declaraciones de apuntadores int * apEntero; //Apunta a un entero float *apFloat; //Apuntador a un dato tipo float char * cadena; //Apuntador a datos de tipo caracter Se pueden declarar apuntadores a cualquier objeto en memoria, incluyendo arreglos, estructuras, funciones e incluso otros apuntadores. Ojo, para accesar el valor de una variable a través del apuntador a ella, precede el apuntador con un asterisco. Por ejemplo, cout<<*cadena , nos va a mostrar el valor del caracter almacenado en esa dirección. Este valor es alcanzado en forma indirecta a través de un apuntador, a este proceso se le llama indirección o deferenciación. El siguiente programa declara un apuntador y lo usa para ver el valor de la variable. Inicialización dinámica. En JAVA no hay apuntadores, sin embargo si hay inicialización dinámica, veamos un ejemplo En C++ y en java las variables pueden ser inicializadas dinámicamente, usando una expresión válida en el momento que la variable es declarada. El siguiente ejemplo es un pequeño programa que calcula la longitud de la hipotenusa de un triángulo rectángulo dadas las longitudes de sus dos lados opuestos:

**************************** IDinam.java Demostración de Inicialización Dinámica en programación orientada a objetos con JAVA. Programa que calcula la hipotenusa de un triángulo dados los otros dos catetos. ****************************/ //--------------------------------------------------------------------------class IDinam{ public static void main(String args[ ]) { /* Demostración de inicialización dinámica*/ double cOpuesto=3.0, cAdyacente=4.0; System.out.println("\nSe tiene un tri"+'\u00A0'+"ngulo cuyos lados son :"+cOpuesto+" y "+cAdyacente); /* La hipotenusa se inicializa en forma dinámica */ cOpuesto *=cOpuesto; cAdyacente *=cAdyacente; double hipotenusa = Math.sqrt(cOpuesto + cAdyacente); System.out.println("\nLa hipotenusa es: "+hipotenusa); } } Los Punteros de Java Hay un par de ideas sobre java muy extendidas: java no tiene punteros y en java todo se pasa por referencia. La realidad, es que java se entiende mucho mejor si lo pensamos exactamente al revés. En java sólo hay punteros (con excepción de los tipos primitivos) y en java todo se pasa por valor (por copia). Por ejemplo, en C++ hacemos esto MiClase a; y ya está todo correcto. La variable a está perfectamente inicializada. Si en java hacemos eso, tenemos una variable a sin inicializar. Es necesario hacerle un new, exactamente igual que un puntero en C++ MiClase a = new MiClase(); // Esto en Java MiClase *a = new MiClase(); // Esto en C++ // o este otro tipo de inicialización extrañamente parecida ... MiClase a = null; // en java MiClase *a=NULL; // en C++ La única diferencia es la notación con el asterisco. Si pensamos que en java TODO son punteros, no es necesario poner el asterisco para distinguir lo que es puntero de lo que no lo es, por lo que símplemente lo han quitado. Ahora imaginemos un método que recibe una clase y que le hacemos una llamada // en java... void medodo (MiClase a) { a = new MiClase(); } .MiClase b = null; metodo (b); Bueno, pues cuando salimos del método b sigue valiendo null, "apuntando a null". Eso quiere decir que a y b son variables disintas, es decir, se ha pasado la variable b por valor al método.

¿Cómo podemos crear una nueva instancia y devolverla?. En java no queda más remedio que hacerlo en el return, es imposible hacerlo a través de parámetros. Sin embargo, en C++ tenemos más posibilidades. Podemos usar un puntero al puntero, es decir, hacer esto void metodo (MiClase **a) { *a = new MiClase(); } MiClase *b=NULL; metodo (&b); o bien, incluso usar referencias de verdad // El & en la declaración es lo que hace que realmente sea una referencia. void metodo (MiClase * &a) { a=new MiClase(); } MiClase *b=NULL; metodo (b); // Aqui b apunta al MiClase creado dentro del método. Haciéndolo así, el puntero b de fuera del método y el puntero a del parámetro son exactamente la misma variable. Ojo, no quiero decir que sean dos punteros distintos que apunten al mismo lado, sino que son realmente el mismo puntero. Cuando hacemos que a apunte a otro sitio, b también apuntará al mismo sitio. Esto es lo que yo entiendo realmente por referencia

UNIVERSIDAD TECNOLOGICA DE LOS ANDES FACULTAD DE INGENIERÍA CARRERA PROFESIONAL DE INGENIERIA DE SISTEMAS E INFORMATICA

Estructuras de Datos: Listas Enlazadas Introducción La lista enlazada es un TDA que nos permite almacenar datos de una forma organizada, al igual que los vectores pero, a diferencia de estos, esta estructura es dinámica, por lo que no tenemos que saber "a priori" los elementos que puede contener. En una lista enlazada, cada elemento apunta al siguiente excepto el último que no tiene sucesor y el valor del enlace es null. Por ello los elementos son registros que contienen el dato a almacenar y un enlace al siguiente elemento. Los elementos de una lista, suelen recibir también el nombre de nodos de la lista. struct lista { gint dato; lista *siguiente; }; Representa el dato a almacenar. Puede ser de cualquier tipo; en este ejemplo se trata de una lista de enteros. Es un puntero al siguiente elemento de la lista; con este puntero enlazamos con el sucesor, de forma que podamos construir la lista. Figura 1. Esquema de un nodo y una lista enlazada.

Para que esta estructura sea un TDA lista enlazada, debe tener unos operadores asociados que permitan la manipulación de los datos que contiene. Los operadores básicos de una lista enlazada son: • Insertar: inserta un nodo con dato x en la lista, pudiendo realizarse esta inserción al principio o final de la lista o bien en orden. • Eliminar: elimina un nodo de la lista, puede ser según la posición o por el dato. • Buscar: busca un elemento en la lista. • Localizar: obtiene la posición del nodo en la lista. • Vaciar: borra todos los elementos de la lista Después de esta breve introducción, que sólo pretende servir como recordatorio, pasaremos a ver cómo es la estructura GSList que, junto con el conjunto de funciones que la acompañan, forman el TDA lista enlazada en GLib™.1 GSList

1

Manual de Referencias GNOME Documentation Library http://library.gnome.org/devel/glib/unstable/index.html

La definición de la estructura GSList o, lo que es lo mismo, un nodo de la lista, está definido de la siguiente manera: struct GSList { gpointer data; GSList *next; }; Representa el dato a almacenar. Se utiliza un puntero genérico por lo que puede almacenar un puntero a cualquier tipo de dato o bien almacenar un entero utilizando las macros de conversión de tipos. Se trata de un puntero al siguiente elemento de la lista. Las macros de conversión disponibles son las siguientes: GINT_TO_POINTER () GPOINTER_TO_INT () GUINT_TO_POINTER () GPOINTER_TO_UINT () Más adelante, en esta misma sección, se verán ejemplos del uso de estas macros. Las funciones que acompañan a la estructura GSList y que implementan los operadores básicos de las listas enlazadas, son las siguientes: Tabla 1. Operadores de inserción en listas enlazadas. Operador Funciones asociadas a GSList. Insertar al principio. GSList* g_slist_prepend (GSList *list, gpointer data) Insertar al final. GSList* g_slist_append (GSList *list, gpointer data) Insertar en la posición GSList* g_slist_insert (GSList *list, gpointer data, gint position) indicada. GSList* g_slist_insert_sorted (GSList *list, gpointer data, Insertar en orden. GCompareFunc func) Las funciones de inserción al principio de la lista, g_slist_prepend, y al final, g_slist_append, son sencillas de usar. Sólo hay que pasarles como parámetros la lista donde queremos añadir el dato así como el dato a insertar y la función devuelve una lista con el nuevo dato insertado. La función g_slist_insert inserta el dato en la posición indicada. Su uso también es sencillo como puede verse en el siguiente ejemplo. Ejemplo 1. Insertar un nuevo dato en una posición determinada. /* obtiene el numero de nodos de la lista */ length = g_slist_length (list); g_print ("\nEscribe el nº de indice donde se insertara el dato (el indice maximo es %d): ", length);

scanf ("%d", &index); /* inserta el valor en la posicion indicada */ if (index < length) { list = g_slist_insert (list, GINT_TO_POINTER (value), index); print_list (list); }

En este ejemplo se utiliza la función g_slist_length para obtener el número de nodos que contiene la lista. A esta función hay que pasarle como parámetro la lista de la que se desea obtener el número de nodos y devuelve como resultado el número de nodos de ésta. guint * g_slist_length ( list ); GSList * list ; La función g_slist_insert_sorted inserta los elementos a la lista de forma ordenada. Esta función utiliza el parámetro GCompareFunc para insertar el dato en la posición correcta. GCompareFunc es una función que se utiliza para comparar dos valores y saber así cual de ellos hay que insertar primero. En los dos ejemplos que hay a continuación, se puede observar una función de tipo GCompareFunc y su uso para insertar datos en una lista en orden creciente. Ejemplo 2. Parámetro GCompareFunc para insertar en orden creciente. gint compare_value1 (gconstpointer a, gconstpointer b) { gint *value1 = (gint *) a; gint *value2 = (gint *) b; return value1 > value2; } Ejemplo 3. Insertar elementos en orden creciente. gint values[ ] = {8, 14, 5, 12, 1, 27, 3, 13}; gint i;/* insertando valores en orden creciente */ for (i = 0; i < 8; i++) { list = g_slist_insert_sorted (list, GINT_TO_POINTER (values[i]), compare_value1); } Tabla 2. Operadores de eliminación en listas enlazadas. Operador Funciones asociadas a GSList. Eliminar un nodo. GSList* g_slist_remove (GSList *list, gconstpointer data) Eliminar nodos según un GSList* g_slist_remove_all (GSList *list, gconstpointer data) patrón. Las dos funciones expuestas para la eliminación de nodos, si bien tienen una definición prácticamente idéntica, el resultado obtenido es distinto. En el caso de g_slist_remove, se eliminará el nodo que contenga el valor data.Si hay varios nodos con el mismo valor, sólo se eliminará el primero. Si ningún nodo contiene ese valor, no se realiza ningún cambio en el GSList. En el caso de g_slist_remove_all, se eliminan todos los nodos de la lista que contengan el valor data y nos devuelve la nueva lista resultante de la eliminación de los nodos. Ejemplo 4. Elimina un elemento de la lista. if (list2 != NULL) { g_print ("\nEl dato %d sera eliminado de la lista.\n", list2->data); /* eliminando un elemento de la lista */ g_slist_remove (list, list2->data); }

Tabla 3. Operadores de búsqueda en listas enlazadas. Operador Funciones asociadas a GSList. Buscar un nodo según un valor. GSList* g_slist_find (GSList *list, gconstpointer data) GSList* g_slist_find_custom (GSList *list, gconstpointer Buscar un nodo según un criterio. data, GCompareFunc func) Localizar el índice de un nodo. GSList* g_slist_index (GSList *list, gconstpointer data) Localizar la posición de un nodo. GSList* g_slist_position (GSList *list, GSList *llink) Obtener el último nodo. GSList* g_slist_last (GSList *list) Obtener el siguiente nodo. g_slist_next (slist) Obtener un nodo por su posición. GSList* g_slist_nth (GSList *list, guint n) Obtener el dato de un nodo según gpointer g_slist_nth_data (GSList *list, guint n) su posición. Todas estas funciones, a excepción de g_slist_nth_data, devuelven un nodo de la lista o NULL si el elemento no existe. La función g_slist_nth_data devuelve el valor del elemento según la posición que se le pasa como argumento en el parámetro n o NULL si la posición que se le pasa está más allá del final de la lista. La función g_slist_next, es una macro que nos devuelve el siguiente nodo. Esta macro la podemos utilizar para recorrer la lista. Ejemplo 5. Función que imprime una lista. void print_list (GSList *list) { gint i = 0; while (list != NULL) { g_print ("Node %d content: %d.\n", i, list->data); /* apunta al siguiente nodo de la lista */ list = g_slist_next (list); i++; } } Tabla 4. Operador para vaciar la lista. Operador Funciones asociadas a GSList. Funciones asociadas a Funciones asociadas a GSList. GSList. La función g_slist_free libera la memoria de la lista que se le pasa como parámetro. Con estas funciones, quedan definidos los operadores básicos del TDA lista enlazada. GSList trae otras funciones además de los operadores básicos. Para más información sobre estas, está disponible el manual de referencia de GLib™2.

2

Idem 1

Listas Doblemente Enlazadas. Introducción. El TDA lista doblemente enlazada, al igual que la lista enlazada, es un TDA dinámico lineal pero, a diferencia de este, cada nodo de la lista doblemente enlazada contiene dos punteros, de forma que uno apunta al siguiente nodo y el otro al predecesor. Esta característica, permite que se pueda recorrer la lista en ambos sentidos, cosa que no es posible en las listas simples.

La declaración del tipo lista doblemente enlazada de enteros es la siguiente: struct lista_doble { gint dato; lista_doble *siguiente; lista_doble *anterior; }; Representa el dato a almacenar, que puede ser de cualquier tipo. En este ejemplo se trataría de una lista de enteros. Se trata de un puntero al siguiente elemento de la lista. Con este puntero se enlaza con el sucesor, de forma que podamos construir la lista. Es un puntero al elemento anterior de la lista. Este puntero enlaza con el elemento predecesor de la lista y permite recorrerla en sentido inverso. Sobre este TDA se definen los mismos operadores básicos que en las listas simples.

GList La definición de la estructura GList, que es un nodo de la lista doblemente enlazada, está definido de la siguiente manera: struct GList

{

gpointer data; GList *next; GList *prev; };

Representa el dato que se va a almacenar. Se utiliza un puntero genérico por lo que puede almacenar un puntero a cualquier tipo de dato o bien almacenar un entero utilizando las macros de conversión de tipos. Se trata de un puntero al siguiente elemento de la lista. Se trata de un puntero al elemento anterior de la lista.

Las funciones que acompañan a la estructura GList, que implementan los operadores básicos de las listas enlazadas, son las siguientes:

Tabla 5. Operadores de inserción en listas doblemente enlazadas. Operador Funciones asociadas a GList. Insertar al principio. GList* g_list_prepend (GList *list, gpointer data) Insertar al final. GList* g_list_append (GList *list, gpointer data) Insertar en la posición GList* g_list_insert (GList *list, gpointer data, gint position) indicada. GList* g_list_insert_sorted (GList *list, gpointer data, Insertar en orden. GCompareFunc func) Como puede observarse en la definición de las funciones, su uso es el mismo que en las listas simples, al igual que las macros de conversión, por lo que todo lo explicado en esa sección es válido en el caso de las listas doblemente enlazadas.

Ejemplo 6. Insertar un nuevo dato en una posición determinada. /* obtiene el numero de nodos de la lista */ length = g_list_length (list); g_print ("\nEscribe el numero de indice donde se insertara el dato (el indice maximo es %d): ", length);

scanf ("%d", &index); /* inserta el valor en la posicion indicada */ if (index < length) { list = g_list_insert (list, GINT_TO_POINTER (value), index); print_list (list); } Ejemplo 7. Insertar elementos en orden creciente. gint values[ ] = {8, 14, 5, 12, 1, 27, 3, 13}; gint i; for (i = 0; i < 8; i++) { list = g_list_insert_sorted (list, GINT_TO_POINTER (values[i]), compare_value1); } Tabla 6. Operadores de eliminación en listas doblemente enlazadas. Operador Funciones asociadas a GList. Eliminar un nodo. GList* g_list_remove (GList *list, gconstpointer data) Eliminar nodos según GList* g_list_remove_all (GList *list, gconstpointer data) un patrón.

Ejemplo 8. Eliminar un elemento de la lista. if (list2 != NULL) { g_print ("\nEl dato %d sera eliminado de la lista.\n", list2->data); /* eliminando un elemento de la lista */ g_list_remove (list, list2->data); print_list (list); } Tabla 7. Operadores de búsqueda en listas doblemente enlazadas. Operador Funciones asociadas a GSList. Buscar un nodo según un valor. GList* g_list_find (GList *list, gconstpointer data) GList* g_list_find_custom (GList *list, Buscar un nodo según un criterio. gconstpointer data, GCompareFunc func) Localizar el índice de un nodo. GList* g_list_index (GList *list, gconstpointer data) Localizar la posición de un nodo. GList* g_list_position (GList *list, GSList *llink) Obtener el último nodo. GList* g_list_last (GList *list) Obtener el siguiente nodo. g_slist_next (slist) Obtener un nodo por su posición. GList* g_list_nth (GList *list, guint n) Obtener el dato de un nodo según gpointer g_list_nth_data (GSList *list, guint n) su posición.

Ejemplo 9. Busca un valor dado en la lista. g_print ("\nEntra un valor entero a buscar: "); scanf ("%d", &value); g_print ("\n"); /* buscando un elemento en la lista */ list2 = g_list_find (list, GINT_TO_POINTER (value)); if (list2 != NULL) { index = g_list_index (list, list2->data); g_print ("\nEl valor %d esta en el nodo %d.\n", list2->data, index); Tabla 8. Operador para vaciar la lista Operador Vacía la lista y libera la memoria usada

Funciones asociadas a GSList. void g_list_free (GList *list)

Con estas funciones, quedan definidos los operadores básicos del TDA lista enlazada. Al igual que GSList, GList trae otras funciones además de los operadores básicos. Para más información sobre estas, está disponible el manual de referencia de GLib3.

3

Idem 1

ListaSimple /********************************************************* * Archivo: ListaSimple.java * Lenguaje: Java * UNIVERSIDAD TECNOLOGICA DE LOS ANDES * Notas: *********************************************************/ //Definicion de la clase de excepciones class EmptyListException extends RuntimeException{ public EmptyListException(String nombre){ super ("La " + nombre+ " esta vacia"); } } //Definicion de la clase Nodoslista class NodosLista{ //datos amigables para que la clase lista tenga un acceso directo Object datos; NodosLista siguiente; //Constructor crea un nodo de tipo Object NodosLista(Object valor){ datos=valor; siguiente=null; } //Constructor Crea un nodo de tipo Object y al siguiente nodo de la lista NodosLista (Object valor,NodosLista signodo){ datos=valor; siguiente=signodo; //siguiente se refiere al siguiente nodo } //Retorna el dato que se encuentra en ese nodo Object getObject(){ return datos; } //Retorna el siguiente nodo NodosLista getnext(){ return siguiente; } } //Definicion de la clase ListaSimple class ListaSimple{ NodosLista PrimerNodo; NodosLista UltimoNodo; String Nombre; //Constructor public boolean VaciaLista(){ return PrimerNodo ==null; } //Contructor public ListaSimple(String s){ Nombre=s; PrimerNodo=UltimoNodo=null; } //Constructor public ListaSimple(){ this ("Lista"); } //Imprime el contenido de la lista public void Imprimir(){ if (VaciaLista()){ System.out.println("Vacia" + Nombre); } else{ System.out.print("La "+Nombre + " es: "); Página 1

ListaSimple NodosLista Actual=PrimerNodo; while(Actual != null){ System.out.print(Actual.datos.toString()+" "); Actual=Actual.siguiente; } System.out.println(); System.out.println(); } } //Inserta un elemento al frente de la lista void InsertaInicio(Object ElemInser){ if(VaciaLista()) PrimerNodo=UltimoNodo=new NodosLista(ElemInser); else PrimerNodo=new NodosLista(ElemInser, PrimerNodo); } //Inserta al final de la lista public void InsertaFinal(Object ElemInser){ if(VaciaLista()){ PrimerNodo= UltimoNodo = new NodosLista (ElemInser); } else{ UltimoNodo=UltimoNodo.siguiente=new NodosLista(ElemInser); } } //Inserta elemento en posicion dada public void InsertaMedio(Object ElemInser,int Posicion){ if(VaciaLista()) PrimerNodo=UltimoNodo=new NodosLista (ElemInser); else{ if(Posicion<=1){ NodosLista Nuevo=new NodosLista(ElemInser); Nuevo.siguiente=PrimerNodo; PrimerNodo=Nuevo; } else{ NodosLista Aux=PrimerNodo; int i=2; while((i != Posicion) & (Aux.siguiente != null)){ i++; Aux=Aux.siguiente; } NodosLista Nuevo=new NodosLista(ElemInser); Nuevo.siguiente=Aux.siguiente; Aux.siguiente=Nuevo; } } } //Elimina al Inicio public void EliminaInicio(){ if(VaciaLista()) System.out.println("No hay elementos"); else if(PrimerNodo.equals(UltimoNodo)) PrimerNodo=UltimoNodo=null; else PrimerNodo=PrimerNodo.siguiente; } //Retorna si un elemento es miembro public boolean Miembro(Object ele){ boolean enc=false; NodosLista aux=PrimerNodo; Página 2

ListaSimple while((aux != null) && (enc==false)){ if(ele.equals(aux.datos)){ enc=true; } else{ aux=aux.siguiente; } } return enc; } //Elimina un elemento public void EliminaEle(Object ele){ NodosLista aux=PrimerNodo; NodosLista p=PrimerNodo; NodosLista ant=null; boolean enc=false; while((aux != null) && (enc==false)){ if(ele.equals(aux.datos)) enc=true; else{ ant=aux; aux=aux.siguiente; } } if(enc==true){ if (aux.equals(PrimerNodo)){ PrimerNodo=aux.siguiente; } else{ if (aux.equals(UltimoNodo)){ UltimoNodo=ant; ant.siguiente=null; } else{ NodosLista i=aux.siguiente; aux=ant; aux.siguiente=i; PrimerNodo=p; } } } } //Obtiene el menor de los elementos public Object Menor(){ NodosLista aux=PrimerNodo,p=PrimerNodo; Object men1,sig1; men1=aux.datos; int men,sig; men=Integer.parseInt(aux.datos.toString()); while(aux != null){ sig1=aux.datos; sig=Integer.parseInt(aux.datos.toString()); if(men>sig){ men=sig; men1=sig1; } aux=aux.siguiente; } PrimerNodo=p; return men1; } //Ordena la lista public void Ordenar(){ NodosLista aux=PrimerNodo; Página 3

ListaSimple ListaSimple j=new ListaSimple(); Object m; while (!VaciaLista()){ m=Menor(); j.InsertaFinal(m); EliminaEle(m); } j.Imprimir(); } //Invierte la lista public void Invertir(){ NodosLista sig = PrimerNodo; NodosLista anterior = null; while(!(VaciaLista())){ sig = PrimerNodo.siguiente; PrimerNodo.siguiente = anterior; anterior = PrimerNodo; PrimerNodo = sig; } PrimerNodo= anterior; } } class ListaSimpleA{ public static void main (String [] args){ ListaSimple l=new ListaSimple(); //Crea la lista l.InsertaInicio("7"); l.InsertaInicio("3"); l.InsertaInicio("16"); l.InsertaInicio("2"); l.InsertaInicio("5"); l.InsertaInicio("8"); l.InsertaInicio("10"); l.InsertaInicio("15"); l.InsertaInicio("1"); l.Imprimir(); } }

Página 4

FUENTES DE CONSULTA BIBLIOGRAFIA DALE, Nell / WEEMS, Chip. PROGRAMACIÓN Y RESOLUCIÓN DE PROBLEMAS CON C++. Cuarta edición. Editorial McGraw Hill, México, 2007. BRONSON, Gary J. C++ PARA INGENIERIA Y CIENCIAS. Segunda edición. Editorial InternationalThomson, México 2007. CAIRO, Osvaldo. METODOLOGIA DE LA PROGRAMACION. Segunda edición. Editorial Alfaomega,México 2003. DEITEL, Harvey M. / DEITEL, Paul J. CÓMO PROGRAMAR EN C++ Y JAVA. Cuarta Edición. Editorial Pearson Prentice Hall, México, 2004. JOYANES Aguilar, Luís. PROGRAMACIÓN EN C++ - ALGORITMOS, ESTRUCTURAS DE DATOS Y OBJETOS. Editorial McGraw Hill, España, 2000. SITIOS WEB http://www.romalo.250x.com/contenido/ci/index15.htm

http://www.infonet.com.ve/informaciongeneral/tecnologiagsm/default.aspx http://microasist.com.mx/noticias/internet/fimin271003.shtml http://www.ericsson.com.mx/press/referencias/tec_gsm.html