Pascal listas

INSTITUTO POLITECNICO NACIONAL ESCUELA SUPERIOR DE INGENIERIA MECANICAY ELECTRICA UNIDAD ZACATENCO

ASIGNATURA: ESTRUCTURAS Y BASES DE DATOS

PROFESORA: CORTES HERNANDEZ LILIA

ALUMNOS: JUAREZ PEREZ MIGUEL RAMIREZ TOFOLLA JOSUE

GRUPO: 3CV4

“LISTAS ENLAZADAS”

Listas enlazadas 1. Introducción 2. Memoria dinámica 2.1 Malloc y free 3. ¿En qué consisten las listas enlazadas? 3.1.Ejercicios 4. Paso de punteros a funciones 4.1 Paso por valor 4.2. Paso por referencia 5. Liberar la memoria de una lista enlazada 6. Solución a los ejercicios 6.1. Ejercicio de números primos 7. Eliminar un elemento de una lista enlazada 7.1. Suprimir por cabeza 7.2. Suprimir por el final 7.3. Eliminación de un elemento cualquiera de una lista enlazada 8. Ventajas y desventajas de las listas enlazadasrespecto a los arrays 9. Acabando Introducción En esta segunda entrega vamos a ver lo que son las listas enlazadas y para ello trataremos la memoria dinámica. Es un tema muy utilizado en la práctica. Antes de empezar hago una pequeña aclaración que seguramente es innecesaria: Arrays = tabla = vector (si es de una dimensión) Tupla = estructura = record Lo dejo claro desde el principio por si osencontráis con alguna de estos términos, aunque intentaré no mezclarlos para no liar al personal. Memoria dinámica Cuando queremos utilizar una variable la declaramos al principio del código y como ya sabemos tenemos varios tipos de variables. También sabemos que podemos agrupar estas variables en arrays. El inconveniente es que necesitamos saber el tamaño del array cuando lo declaramos. Esto es unalimitación muy grande, por ejemplo, si programamos una agenda deberemos saber a cuanta gente tendremos como máximo, o si nos diera por hacer un programa que calculase números primos tendríamos que poner un máximo (lamentablemente hay infinitos números primos J ); si reservábamos mucha memoria para curarnos en salud y nunca agotar una tabla, estamos desperdiciando mucha memoria; si por elcontrario reservamos poca memoria podemos agotar la memoria que tenemos reservada.

Para optimizar la memoria, lo ideal sería reservar memoria en el momento que la necesitásemos y no como hasta la fecha, que lo hacíamos al principio del programa. Malloc y free Estas dos funciones nos servirán para asignar dinámicamente memoria. Estas 2 funciones se encuentran en la librería Reserva memoria y devuelvela posición de memoria del comienzo de ésta, por lo que deberemos guardar el resultado en un puntero (más información de punteros en el número 13 malloc(); de la revista de hackxcrack) . Si no se ha podido reservar memoria, malloc devolverá el valor NULL, así que el puntero apuntará a NULL. Es importante asegurarnos de que se ha podido reservar la memoria, haremos algo así:
PUNTERO

= (T IPO_VARIABLE *) = ( INT *)
MALLOC

MALLOC

(BYTES _RESERVAR );

IF ( PUNTERO

(SIZEOF (CHAR )))

{PUTS (“C ORRECTO ”);}

free() Cuando ya no necesitemos el espacio que habíamos reservado, liberaremos la memoria, haremos:
FREE ( PUNTERO );

Donde el puntero que pasamos como parámetro apunta al principio de la memoria que habíamos reservado. Veremos un ejemplo:
#include #include voidmain() { unsigned long int bytes; char *texto; printf("Cuantos bytes quieres reservar: "); scanf("%li",&bytes); texto = (char *) malloc(bytes); /* Comprobamos si ha tenido éxito la operación */ if (texto) { printf("Memoria reservada: %li bytes = %li kbytes = %li Mbytes\n", bytes, bytes/1024,bytes/(1048576)); printf("El bloque comienza en la dirección: %p\n", texto); /* Ahora liberamos la memoria */free( texto ); } else printf("No se ha podido reservar memoria\n"); }

Si queremos reservar un número muy grande de bytes el programa nos dará error. ¿En qué consisten las listas enlazadas? Aquí entran en juego varios temas, se trata de combinar las estructuras con los punteros para acabar por fin con la limitación de los arrays, ya no hará falta indicar el tamaño del array al principio....