Atelier 801
Atelier 801 
| Cómo crear una lista simplemente enlazada en C |
| | ||
| Cómo crear una lista simplemente enlazada en C, sin morirte en el intento Cosas que vas a necesitar:
Lo básico básico (básico al cuadrado) En ciencias de la computación, el concepto de una lista no varía mucho del concepto que tenemos los seres humanos de una lista en la vida real. Una lista común y corriente (como la que usamos para ir de compras) es una serie de "cosas" en la cual a cada "cosa" le sigue otra. Esta misma lista puede respetar un cierto orden (Leche -> Manzanas -> Papas), o estar completamente desordenada (Manzanas -> Papas -> Leche). Este mismo concepto es el que se intenta (en realidad, se intentó y se logró, y ya está mucho más que establecido) trasladar a todo el ámbito de la computación. ¿Por qué? Porque las listas son algo que utilizamos muy a menudo para resolver problemas en la vida real, y si pudiésemos llevar esa herramienta a una computadora, y que la computadora se encargue de resolver esos problemas en vez de nosotros, estaríamos ahorrándonos trabajo (...que es en realidad la historia de la computación, resumida en una oración). Lo no tan básico (raíz de básico al cuadrado) La mayoría de los programadores, incluidos los principiantes, trabajaron con listas. Probablemente no lo supiesen, pero las listas están ahí. Y es que, el tipo más básico de lista, es un array, un vector de elementos. Recordemos que un vector no es nada más que un conjunto de espacios de memoria contiguos. Es decir, son pedacitos de memoria cada uno al lado del otro. Esto hace sonar una alarma: los vectores, sospechosamente, se parecen a una lista. Porque lo son. Los vectores son listas estáticas. 1 2 3 4 5 //Declaramos el vector... ==> Momento que soy lento. ¿Cómo que listas estáticas? ¿Qué es eso? En programación hay dos grandes formas de manejar la memoria. Para un programador principiante, la forma más conocida que tendrá es la de manejarla estáticamente. En el ejemplo de arriba se ve cómo declaramos un vector de enteros de 10 posiciones. Lo que estamos haciendo, en realidad, es (decirle al compilador que reserve) reservar 10 bloques de memoria contiguos del tamaño de un entero. Esta memoria tiene la particularidad de que va a permanecer reservada durante toda la ejecución del programa. La vamos a poder usar como queramos mientras nuestro programa se ejecute. Esto es genial. Quiere decir que el problema ya está solucionado: ya se trasladaron las listas de la vida real a la computación. ¿Qué más se podría hacer? A pesar de que los vectores son hermosos y solucionan el problema de las listas, traen una gran desventaja: necesitamos conocer la cantidad de elementos que queremos que existan dentro del vector al momento de reservarlo en memoria. A simple vista no parece un desafío, pero, ¿y si no conocemos la cantidad de elementos? ¿O si la cantidad es variable? Una solución a esto sería reservar un vector de una gran cantidad de elementos, y rezar porque nunca lleguen más elementos de los que tenemos disponibles. Lo cual es horrible y más ineficiente que calentar café dejándolo en la luz del sol por 3 años. Estaríamos reservando muchísima memoria que quizás el sistema necesite para otras cosas, y además nos estaríamos arriesgando a quedarnos cortos con la cantidad. Acá es donde entra en juego la memoria dinámica. Lo no tan básico menos uno Una de las diferencias que tiene la memoria dinámica con la estática es que podemos reservarla cuando nosotros realmente queramos y la necesitemos. Si necesitamos solamente ingresar 1 elemento, reservaremos memoria para ese elemento y nadie más. Con esto, solo vamos a estar reservando memoria cuando realmente tengamos que usarla, y no reservaremos 500 espacios de memoria que quizás se usen alguna vez. Otra diferencia, es que es posible que la memoria dinámica no necesariamente se reserve en espacios contiguos. Podemos reservar memoria para dos elementos y que el primero quede en China, y el otro en Jujuy... Con la ayuda de la memoria dinámica es donde entran en juego las listas dinámicas. Estas listas tienen la gran ventaja de que su cantidad de elementos es variable, pudiendo tener tantos elementos como memoria tengamos, y pudiendo liberar la memoria de aquellos elementos que ya no necesitemos. Entonces... ¿cómo hacemos una de estas? (¡volteá la pestaña!) (¿se puede hacer eso?) (bueno ni idea, vos solo andá a la otra) Lo no tan básico, tendiendo al infinito negativo Para poder hacer una lista, primero tenemos que definir cómo va a estar formada la misma. Sabemos que necesitan ser capaces de albergar algún tipo de contenido, pero además de eso, necesitamos saber cuál es el elemento que le sigue al actual. Debido a que no estamos trabajando en memoria dinámica, no podemos asumir que todos los elementos de la lista estén pegaditos uno al lado del otro en la memoria. Por eso sí o sí, necesitamos que cada elemento de nuestra lista, además de tener un contenido, tenga un algo que apunte hacia el elemento que le sigue. En programación, este tipo de estructura recibe el nombre de nodo. El nodo no es más que una estructura que se divide en dos: la primera parte es el dato, el contenido que guardamos. La segunda parte es lo que "apunta al siguiente" nodo.
Pasar esto a C no sería tan complicado, ¿no? Necesitaríamos declarar una estructura que sea algo más o menos así: 1 2 3 4 5 typedef struct Esto no sirve. Más que nada porque estamos cometiendo el error de "llamar" al tipo de dato t_nodo antes de que siquiera lo terminemos de definir. Una forma de solucionar esto es poniéndole un nombre a la estructura para poder hacer referencia a la misma. 1 2 3 4 5 typedef struct s_nodo Tenemos los nodos declarados y su estructura definida. Una parte fundamental de la lista está hecha. Pero necesitamos tener la lista en sí. Es decir: necesitamos crear un tipo de dato lista, con el cual podamos declarar y utilizar listas. Definimos el tipo de dato t_lista como un puntero a nodo. 1 typedef t_nodo * t_lista;
Lo no tan básico, ahora en el conjunto de los complejos Un par de cuestiones a tener en cuenta:
Veamos el código que aparece en la imagen del principio de todo: 1 2 3 4 5 6 int main() Analizándolo, podemos ver que reservamos una variable estática del tipo de dato t_lista, y que inmediatamente después llamamos a una función crearLista(). El porqué de esto reside en la siguiente cuestión: cuando reservamos memoria (de cualquier tipo), no podemos asegurarnos de que el bloque que hayamos reservado esté vacío. Lo más probable es que ese bloque tenga basura dentro. Por eso lo primero que tenemos que hacer es remover esa basura seteando al contenido de lista en NULL. 1 2 3 4 void crearLista(t_lista * pl) //Recibimos la dirección de memoria de lista, ergo, un puntero a lista Tenemos nuestra lista creada y sin ningún elemento. Podemos empezar a llenarla. Si queremos ingresar un elemento al principio de la lista, lo podemos hacer de la siguiente forma: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 //Inserta elementos siempre al principio de la lista De esta forma, pudimos agregar un elemento a la lista. Y también, todos los elementos que sean agregados con esta función se pondrán automáticamente al comienzo de la lista. Draw some circles, draw the rest of the fucking owl ¿Pero y qué pasa si queremos insertar nuestros datos de forma ordenada? Esto implica que necesitaremos recorrer la lista e ir comparando el dato que queremos ingresar con los datos ya presentes en la lista.
Para esto nos será conveniente utilizar una función parametrizada, y además de eso, abusar de que en C, los parámetros solo pueden pasarse por copia. Por esto mismo podemos empezar a recorrer la lista cambiando simplemente el contenido de pl. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 int insertarOrdenado(t_lista * pl, const t_dato *d, t_cmp comparar) Habiendo aprendido el concepto de listas simplementes enlazadas en C, sírvase de resolver estos ejercicios para perfeccionar sus conocimientos. Ejercicio 1: El banco “CBCI”, mantiene el estado de las cuentas de sus clientes en el archivo cuentas.dat (ordenado por el nro. de cuenta), que actualiza todos los días con los movimientos provenientes del archivo de texto movimientos.txt (ordenado por fecha y hora del movimiento) de la siguiente manera: • Si el movimiento es un débito (D): se le debe restar al saldo de la cuenta cliente el importe del movimiento. • Si el movimiento es un crédito (C): se debe sumar el importe del movimiento al saldo de la cuenta cliente. El archivo de texto de movimientos tiene registros de longitud fija, con 8 caracteres para el código de cuenta, un carácter para el tipo de movimiento y 9 caracteres (con 2 decimales) para el importe del movimiento. Se pide: Realizar la actualización del archivo de cuentas con la información de los movimientos. Debe minimizar el acceso a disco, debe valerse de una lista simplemente enlazada para ello. Resuelva la función insertar_lista que inserta los elementos de manera ordenada y en caso de que esté duplicado, los acumula. Resuelva la función sacar_primero_lista que saca el primero de la lista. Ejercicio 2: Una materia de una Universidad mantiene un archivo de alumnos inscriptos a la materia (alumnos.bin), que contiene el dni y el apellido y nombre del alumno, y otro archivo con las notas de cada alumno (notas.txt), que contiene el dni del alumno, el tipo de examen (P1, P2, R1, R2) y la nota que se sacó el alumno en el examen, los ausentes no se encuentran en este archivo. El archivo de alumnos está ordenado por dni, y el archivo de notas está ordenado por dni del alumno y tipo de examen. Al finalizar el cuatrimestre se realiza el proceso de generación de acta, del cual sale el archivo acta.txt con los datos de los alumnos y todas sus notas parciales, la nota final (que debe ser calculada según el criterio que se detalla a continuación) y la condición final (Pro, Apr, Rec, Aus, Err). Debe quedar ordenada por apellido y nombre del alumno. Cálculo de nota final: Las notas se dividen en 4 grupos: - Ausente - las de reprobación (1 a 3), - las de cursada (4 a 6) - las de promoción (7 a 10) Las notas de los recuperatorios pisan la nota parcial (salvo que estén ausentes). Entonces, si las notas parciales están en el mismo grupo, la nota final es el promedio de las mismas (7 y 8 = 8). Si están en distinto grupo, queda la nota del grupo inferior (4 y 9 = 4). Si la nota de alguno de los 2 parciales queda en ausente (teniendo en cuenta los recuperatorios) la nota final es ausente (A y 7 = A). Los errores deben ser informados en un archivo de texto (observaciones.txt) y los que se pueden dar son: - que un alumno tenga notas en los 2 recuperatorios. En este caso la nota debe quedar como Err y también debe ser informada en un archivo de texto, - que una nota en el archivo notas.txt NO tenga su correspondiente alumno en alumnos.bin, - también deben ser informadas en el archivo de observaciones, aunque no sea un error, si algún alumno recuperó un parcial en el que tenía 7 o más. |
Obemice
Profil
Derniers messages
Tribu
 Zayde7
| | ||
Sebastianes
| | ||
| Karim_uwu03 « Censeur »
| | ||
