C Piscine — C 01

El módulo de punteros: nueve ejercicios para interiorizar que en C todo es memoria con dirección, y que un puntero no es más (ni menos) que esa dirección guardada en una variable.

Por qué un módulo entero de punteros — C pasa todo por valor: cuando llamas f(x), la función recibe una copia y no puede tocar tu variable. La única forma de que una función modifique algo del que llama es darle la dirección de ese algo. De esa limitación — deliberada, C es de 1972 y mapea casi directo a ensamblador — nace todo este módulo: los punteros no son un tema avanzado de C, son el mecanismo del lenguaje para compartir memoria entre funciones. (El prólogo del enunciado atribuye a "Una noche en la ópera de los Hermanos Marx" el diálogo de la Royale con queso… que es de Pulp Fiction. Error a propósito: comprobar las fuentes también es parte del oficio.)

GGlosario de teoría

C01 es el módulo en el que aparecen de golpe las palabras que vas a oír el resto del cursus: dirección, puntero, desreferenciar, paso por valor… Aquí está cada una explicada desde cero y con un ejemplo sacado de los propios ejercicios. En el resto de la página, la primera vez que sale uno de estos términos en cada tarjeta lleva un enlace a su entrada.

Memoria y punteros

Memoria, dirección y el operador &

La memoria del programa es una fila enorme de casillas de un byte, numeradas. El número de una casilla es su dirección. Cada variable ocupa unas cuantas casillas seguidas (un int suele ocupar 4) y su dirección es la de la primera.

El operador & delante de una variable da su dirección: si tienes int n;, &n es «dónde vive n». Es lo que hace el main de prueba de ex00: ft_ft(&n) no le pasa el valor de n, sino el sitio donde está guardado.

Puntero

Una variable que guarda una dirección. int *nbr se lee «nbr es un puntero a int»: lo que contiene no es un entero, sino la dirección de un entero. El tipo (int *, char *…) le dice al compilador qué hay en esa dirección y cuántos bytes leer cuando vaya allí.

En C01 todos los prototipos llevan punteros: ft_ft(int *nbr), ft_swap(int *a, int *b), ft_putstr(char *str). Un puntero ocupa lo mismo apunte a lo que apunte (8 bytes en un sistema de 64 bits).

Desreferenciar e indirección (el * al usar)

El * tiene dos papeles. En una declaración (int *nbr) dice «esto es un puntero». Al usarlo (*nbr = 42) significa «ve a la dirección que guarda nbr y trabaja con lo que hay allí». Eso es desreferenciar, y acceder a algo a través de su dirección se llama indirección.

& y * son opuestos: *&n es n. En ex00, *nbr = 42 escribe 42 en la variable del que llama, no en nbr.

Puntero a puntero (varios niveles de indirección)

Un puntero es una variable más, así que también tiene dirección, y esa dirección se puede guardar en otro puntero: int **pp apunta a un int *, que apunta a un int. Cada * del tipo es un salto; cada * al usarlo deshace uno.

ex01 lo lleva a nueve: int *********nbr. Para probarlo hacen falta un int y ocho punteros intermedios, cada uno con la dirección del anterior; al final se llama ft_ultimate_ft(&p8). El uso real de verdad es el doble puntero (t_list ** en C12): una función que tiene que cambiar el puntero del que llama, no lo apuntado.

Paso por valor

Cuando llamas a una función, C copia cada argumento en el parámetro correspondiente. La función trabaja con esa copia: si la cambia, la variable original no se entera. Es la única forma de pasar argumentos que tiene C.

Por eso un swap(int a, int b) no sirve: intercambia sus copias y, al volver, todo sigue igual. Con punteros también se pasa por valor, pero lo que se copia es la dirección, y con una copia de la dirección se llega a la misma variable. Otros lenguajes tienen «paso por referencia» (C++ con int &a); C lo imita así.

Parámetro de salida

Un parámetro puntero que no sirve para darle datos a la función, sino para que la función deje ahí un resultado. Es como C devuelve más de un valor: return solo puede devolver uno.

En ex03, div y mod son de salida: quien llama declara dos int, pasa sus direcciones y la función los rellena. En ex04 a y b son de entrada y salida a la vez: se leen y luego se sobrescriben.

Aliasing

Hay aliasing cuando dos nombres llegan a la misma memoria: dos punteros con la misma dirección, o un puntero y la variable a la que apunta. Si escribes por uno, cambia lo que lees por el otro, y el orden de las operaciones pasa a importar.

ex04 es el ejemplo pequeño: *a se usa para calcular el cociente y el resto, y además es donde se guarda el cociente. Si se escribiera *a = *a / *b antes de calcular el resto, el resto saldría del valor nuevo. Otro caso: ft_swap(&x, &x) funciona con la temporal, pero el truco del swap con XOR sin temporal dejaría x a 0.

Puntero nulo y segfault

NULL es un puntero que no apunta a nada (vale 0). Desreferenciarlo, o desreferenciar cualquier dirección que no es del programa, hace que el sistema mate el proceso con la señal SIGSEGV: el famoso segmentation fault.

Ninguna función de C01 comprueba si le pasan NULL: ft_putstr(NULL) o ft_strlen(NULL) revientan, igual que las de la libc. El enunciado lo admite: las funciones no deben terminar de forma inesperada «excepto en el caso de comportamientos indefinidos», y pasar NULL donde se espera una cadena lo es.

Arrays y cadenas

Array

Un bloque de elementos del mismo tipo, uno detrás de otro en memoria. int tab[5] reserva 5 int seguidos; tab[0] es el primero y tab[4] el último. C no comprueba los límites: tab[5] compila y lee la memoria de al lado.

ex07 y ex08 reciben un array de enteros y lo modifican: {1, 2, 3, 4, 5} pasa a {5, 4, 3, 2, 1} con ft_rev_int_tab.

Indexar y aritmética de punteros: tab[i] es *(tab + i)

Sumar un entero a un puntero avanza esa cantidad de elementos, no de bytes: tab + 1 con int *tab avanza 4 bytes, y con char *str, 1. Los corchetes son solo otra forma de escribirlo: tab[i] significa exactamente *(tab + i).

Por eso en ex05 &str[i] es la dirección del carácter i, lo que write necesita. Se podría escribir igual str + i.

Un array «degenera» a puntero

Cuando pasas un array a una función, no se copia el array: se pasa la dirección de su primer elemento. Dentro de la función el parámetro es un puntero, y por mucho que escribas int tab[] en el prototipo, el compilador lo trata como int *tab.

La consecuencia: la función no puede saber cuántos elementos hay. sizeof(tab) dentro de ft_rev_int_tab daría 8 (lo que ocupa un puntero), no el tamaño del array. Por eso ex07 y ex08 reciben size aparte.

Cadena en C (string)

C no tiene tipo cadena. Una cadena es un array de char que termina en un byte 0, y se maneja con un char * que apunta a su primer carácter. Una cadena literal como "Hola" ocupa 5 bytes: las cuatro letras y el 0 final.

Los literales son de solo lectura: char *s = "Hola"; s[0] = 'h'; compila pero suele acabar en segfault. Para una cadena que se pueda modificar hay que usar un array: char s[] = "Hola";. En C01 no importa porque ft_putstr y ft_strlen solo leen.

Terminador nulo ('\0')

El byte con valor 0 que marca el final de una cadena. Se escribe '\0' y es el número 0; no tiene nada que ver con el carácter '0', que vale 48.

Como el 0 es «falso» en C, while (str[i]) se lee «mientras no haya llegado al terminador». ft_strlen("Hola") devuelve 4: cuenta las letras, no el terminador. Si a una cadena le falta el 0, cualquier función que la recorra sigue leyendo memoria hasta encontrar uno por casualidad.

write y la salida estándar

write(fd, dir, n) es una llamada al sistema: pide al sistema operativo que escriba n bytes, empezando en la dirección dir, en el descriptor de fichero fd. El descriptor 1 es la salida estándar (normalmente la terminal); el 2, la salida de errores. Está en <unistd.h>.

ft_putstr llama a write(1, &str[i], 1) una vez por carácter: un byte cada vez. Es la única función autorizada del módulo, y solo en ex05.

Aritmética

División entera y resto (/ y %)

Entre dos int, / da el cociente sin decimales y % el resto: 10 / 3 es 3 y 10 % 3 es 1. Desde C99 el cociente se trunca hacia cero (se tira la parte decimal), y el resto lleva el signo del dividendo, de forma que siempre se cumple (a / b) * b + a % b == a.

Con negativos sale lo que no todo el mundo espera (ejecutado con el ft_div_mod de ex03):

a, bdivmod
-10, 3-3-1
10, -3-31
-10, -33-1

El test de test/ prueba justo esos tres casos, además de INT_MAX e INT_MIN entre 7.

Comportamiento indefinido

Lo que el estándar de C no define: el compilador puede hacer cualquier cosa y el programa puede fallar, dar basura o parecer que funciona. No es un error de compilación; se descubre al ejecutar, o no se descubre.

En C01: dividir entre 0 (ft_div_mod(10, 0, …)), INT_MIN / -1 (el resultado, 2147483648, no cabe en un int), desreferenciar NULL o leer fuera de un array. En este ordenador, las dos divisiones matan el programa con SIGFPE («Floating point exception», estado de salida 136), aunque no haya ningún número decimal por medio.

Algoritmos

Intercambio (swap) y variable temporal

Para intercambiar dos valores hace falta un tercer sitio: si haces *a = *b primero, el valor de *a se pierde. La receta es guardar uno en una temporal, copiar el otro encima y poner la temporal en el segundo:

tmp = *a;
*a = *b;
*b = tmp;

Es ex02, y las mismas tres líneas vuelven dentro de ex07 y ex08, con tab[i] en vez de *a.

In place (en el sitio)

Un algoritmo trabaja in place cuando modifica los datos donde están, usando solo unas pocas variables extra, en lugar de construir el resultado en otra memoria. Se dice que usa memoria constante, O(1), porque lo que gasta de más no depende del tamaño de la entrada.

ft_rev_int_tab y ft_sort_int_tab son in place: no hay array auxiliar, solo i y tmp. Además, sin malloc (no autorizado) tampoco habría otra opción.

Complejidad: O(n), O(n²), O(n³)

La complejidad dice cómo crece el trabajo cuando crece la entrada, sin contar constantes. O(n) (lineal): el doble de datos, el doble de trabajo; es ft_strlen, que mira cada carácter una vez. O(n²) (cuadrático): el doble de datos, cuatro veces el trabajo; suele ser un bucle dentro de otro. O(n³): el doble de datos, ocho veces el trabajo.

Medir lo confirma. ft_rev_int_tab hace size / 2 intercambios: O(n). ft_sort_int_tab se comenta en la entrada siguiente.

Ordenación por intercambio de vecinos (gnome sort y la versión de ex08)

La familia de ordenaciones más sencilla: mirar parejas de vecinos y, si están al revés, cambiarlas. La burbuja recorre el array entero una y otra vez; el gnome sort («ordenación del gnomo», por un gnomo que ordena macetas) avanza mientras todo va bien y, cuando cambia una pareja, retrocede una posición para ver si el que ha bajado sigue mal colocado. Las dos son O(n²).

La solución de ex08 se parece, pero tras cada intercambio vuelve a i = 0, al principio del array, no una posición atrás. Eso la hace más lenta: cada intercambio puede costar un recorrido entero. Contando comparaciones con el mismo código, un array al revés de 100 elementos necesita 166 749 y uno de 1000, 166 667 499 (unas n³/6): es O(n³) en el peor caso. Para los arrays pequeños de la Moulinette no se nota; el resultado es correcto igualmente.

Invariante

Una afirmación que es cierta cada vez que el programa pasa por un punto del bucle. Sirve para convencerse de que el código es correcto sin probar todas las entradas.

En ex08: «cuando i vale k, tab[0..k] está ordenado». Al empezar (i = 0) es cierto; avanzar solo ocurre si tab[i] <= tab[i + 1], así que sigue siéndolo; y tras un intercambio se vuelve a 0, donde vuelve a ser cierto. Cuando el bucle acaba, i vale size - 1 y todo el array está ordenado. Y acaba porque cada intercambio quita una pareja desordenada.

La piscine

La Norma y norminette

Las reglas de estilo obligatorias en 42. Entre otras: funciones de 25 líneas como mucho, como mucho 5 funciones por archivo, las declaraciones al principio de la función y una por línea, y prohibidos for, do…while, switch y el operador ternario. Por eso todos los bucles de la página son while con i = 0; antes.

norminette es el programa que comprueba buena parte de esas reglas, incluida la cabecera de 42 en cada archivo. El enunciado avisa de que no es exhaustivo: si quien te evalúa ve una falta de Norma, es un 0 aunque norminette no diga nada.

Moulinette

El corrector automático de 42. Después de la evaluación entre compañeros, compila tus archivos con cc -Wall -Wextra -Werror junto a su propio main de pruebas y compara los resultados. No se discute con ella: un aviso del compilador, un archivo de más o un fallo en un caso límite, y el ejercicio cuenta como suspendido.

Si tu archivo trae su propio main, choca con el suyo y no enlaza. El runner de test/ de este pack avisa de eso mismo: «el fuente todavía define main(): quítalo antes de entregar».

ex00ft_ft

Entrega: ft_ft.cAutorizado: nada
void	ft_ft(int *nbr)
{
	*nbr = 42;
}
Qué te obliga a aprender — La pareja de operadores que define C: & ("dame la dirección de") y * ("ve a esta dirección"). Escribir *nbr = 42 es: toma la dirección que te han pasado, ve a esa celda de memoria y escribe 42 en ella. El que llama ve su variable cambiada sin que se la hayas "devuelto". Una línea de código, pero es el modelo mental completo de la indirección.

ex01ft_ultimate_ft

Entrega: ft_ultimate_ft.cAutorizado: nada
void	ft_ultimate_ft(int *********nbr)
{
	*********nbr = 42;
}
Qué te obliga a aprender — Nadie usa nueve niveles de indirección; el absurdo es el mensaje. Cada * del tipo añade un salto ("puntero a puntero a…"), y cada * al usarlo deshace exactamente uno. Si entiendes que *********nbr son nueve saltos encadenados hasta llegar al int del fondo — y que el main de prueba necesita nueve variables intermedias, cada una guardando la dirección de la anterior — los dobles punteros de C12 (t_list **) te parecerán triviales. Es vacunación por sobredosis.

ex02ft_swap

Entrega: ft_swap.cAutorizado: nada
void	ft_swap(int *a, int *b)
{
	int	tmp;

	tmp = *a;
	*a = *b;
	*b = tmp;
}
Qué te obliga a aprender — El ejercicio canónico de "por qué existen los punteros": un swap por valor (void swap(int a, int b)) compila, corre y no hace nada visible — intercambia las copias. Solo con direcciones el efecto sobrevive al return. También introduce el patrón de la variable temporal: no puedes pisar un valor sin guardarlo antes. Este swap reaparecerá dentro de rev_int_tab, sort_int_tab y todos los sorts que escribas.

ex03ft_div_mod

Entrega: ft_div_mod.cAutorizado: nada
void	ft_div_mod(int a, int b, int *div, int *mod)
{
	*div = a / b;
	*mod = a % b;
}
Qué te obliga a aprender — C solo puede devolver UN valor con return. ¿Y si una operación produce dos (cociente y resto)? El idioma clásico: parámetros de salida — el llamador reserva las variables y te pasa sus direcciones para que las rellenes. Así funcionan media libc y todas las APIs de sistema (pipe(int fd[2]), waitpid(&status)…). Los lenguajes modernos devuelven tuplas; C te enseña qué hay debajo de esa azúcar.

ex04ft_ultimate_div_mod

Entrega: ft_ultimate_div_mod.cAutorizado: nada
void	ft_ultimate_div_mod(int *a, int *b)
{
	int	div;
	int	mod;

	div = *a / *b;
	mod = *a % *b;
	*a = div;
	*b = mod;
}
Qué te obliga a aprender — Ahora los punteros son entrada y salida a la vez, y aparece un peligro nuevo: el orden. Si escribes *a = *a / *b y después calculas el resto, ya has destruido el valor original de *a — el resto saldrá mal. Hay que leer todo antes de escribir nada (de ahí las temporales). Es la primera lección de aliasing: cuando lees y escribes a través de punteros, el orden de las operaciones es parte de la corrección.

ex05ft_putstr

Entrega: ft_putstr.cAutorizado: write
void	ft_putstr(char *str)
{
	int	i;

	i = 0;
	while (str[i])
	{
		write(1, &str[i], 1);
		i++;
	}
}
Qué te obliga a aprender — Que en C no hay tipo cadena. Una "string" es solo la dirección de su primer carácter, y la convención de que termina donde aparezca el byte 0 ('\0'). La condición while (str[i]) es literalmente "mientras el byte no sea cero". De esa decisión de diseño de 1972 — comprometida pero baratísima en memoria — salen strlen, los buffer overflows, y medio siglo de bugs; conviene entenderla bien porque es la base de los módulos C02-C04 y de C07.

ex06ft_strlen

Entrega: ft_strlen.cAutorizado: nada
int	ft_strlen(char *str)
{
	int	i;

	i = 0;
	while (str[i])
		i++;
	return (i);
}
Qué te obliga a aprender — La consecuencia directa del diseño de ex05: como la longitud no se guarda en ninguna parte, medirla cuesta recorrer la cadena entera, O(n). En lenguajes con la longitud almacenada, len() es O(1). Entender este coste explica patrones de todo el C real: por qué no se llama strlen dentro de la condición de un bucle, por qué las APIs pasan la longitud junto al puntero, por qué existen strlcpy/strlcat. Primer ejercicio del módulo que devuelve algo: `return (i);`.

ex07ft_rev_int_tab

Entrega: ft_rev_int_tab.cAutorizado: nada
void	ft_rev_int_tab(int *tab, int size)
{
	int	i;
	int	tmp;

	i = 0;
	while (i < size / 2)
	{
		tmp = tab[i];
		tab[i] = tab[size - 1 - i];
		tab[size - 1 - i] = tmp;
		i++;
	}
}
Qué te obliga a aprender — Dos cosas. (1) Un array que entra en una función degenera a puntero: dentro solo tienes la dirección del primer elemento, y por eso el tamaño viaja como parámetro aparte — C no lo sabe. Perder el tamaño = leer memoria ajena. (2) El patrón de los dos índices que avanzan desde los extremos (i y size-1-i) intercambiando — parar en size/2 para no des-invertir, y comprobar que el elemento central impar se queda quieto solo. Invertir in place, sin array auxiliar, es la primera vez que piensas en memoria constante.

ex08ft_sort_int_tab

Entrega: ft_sort_int_tab.cAutorizado: nada
void	ft_sort_int_tab(int *tab, int size)
{
	int	i;
	int	tmp;

	i = 0;
	while (i < size - 1)
	{
		if (tab[i] > tab[i + 1])
		{
			tmp = tab[i];
			tab[i] = tab[i + 1];
			tab[i + 1] = tmp;
			i = 0;
		}
		else
			i++;
	}
}
Qué te obliga a aprender — Tu primer algoritmo de verdad: no hay receta en el enunciado, solo "ordena". La solución de arriba (gnome sort) cabe en la Norma y se razona con un invariante simple: si encuentro un par desordenado, lo arreglo y vuelvo a empezar; si llego al final, está ordenado. Es O(n²) — y está bien que lo sea: la piscine quiere que primero escribas un sort correcto y después, cuando ordenar 100.000 elementos duela, tengas motivo para aprender quicksort. También es el cierre del módulo: swap (ex02) + recorrido con índices (ex07) + mutación in place = ordenación.

?Preguntas probables de la evaluación

Lo que es fácil que pregunte quien te evalúe en C01, con una respuesta corta y el enlace a donde está explicado. Están agrupadas en: punteros, casos límite y entrega. Antes de mirar la respuesta, intenta contestar tú.

Punteros

¿Qué es un puntero? ¿Qué hacen & y *?

Una variable que guarda una dirección de memoria. &n da la dirección de n; *p va a la dirección que guarda p. En ex00, *nbr = 42 escribe en la variable del que llama. → puntero, ex00

¿Por qué ft_swap recibe punteros y no dos int?

Porque C pasa los argumentos por valor: con int a, int b la función intercambia sus copias y al volver no ha cambiado nada. Con las direcciones llega a las variables originales. → paso por valor, ex02

¿Cómo pruebas ft_ultimate_ft?

Con un int n y ocho punteros encadenados: p1 = &n, p2 = &p1… hasta p8 = &p7, y se llama ft_ultimate_ft(&p8). Los nueve * de la función deshacen los nueve saltos y llegan a n. → puntero a puntero, ex01

En ft_ultimate_div_mod, ¿por qué usas div y mod en vez de escribir directamente en *a?

Porque *a hace falta para calcular el resto. Si se escribe el cociente en *a antes, *a % *b ya usa el valor nuevo y el resto sale mal. Primero se lee todo, después se escribe. → aliasing, ex04

Casos límite

¿Qué pasa si b vale 0 en ft_div_mod?

Dividir entre 0 es comportamiento indefinido; aquí el programa muere con SIGFPE. El enunciado no pide comprobarlo y el prototipo no tiene forma de avisar del error, así que no se comprueba. Lo mismo con INT_MIN entre -1. → comportamiento indefinido

¿Qué da ft_div_mod(-10, 3, &div, &mod)?

div = -3 y mod = -1: el cociente se trunca hacia cero y el resto lleva el signo del dividendo. No hay que hacer nada especial: es lo que dan / y % en C. → división entera

¿Y si te pasan NULL a ft_putstr o ft_strlen?

Segfault, como con las de la libc. Pasar NULL donde se espera una cadena es comportamiento indefinido, y el enunciado solo exige no reventar fuera de esos casos. → segfault

¿Funcionan ft_rev_int_tab y ft_sort_int_tab con size 0 o 1, o con un tamaño impar?

Sí. Con 0 o 1, size / 2 es 0 y size - 1 es -1 o 0, así que no se entra en el bucle y no se toca memoria. Con tamaño impar, el bucle de ex07 para en size / 2 y el del medio se queda en su sitio. El test de test/ prueba size 0 y 1. → ex07, ex08

¿Qué algoritmo es tu ft_sort_int_tab y qué complejidad tiene?

Intercambio de vecinos: si una pareja está al revés, se cambia y se vuelve a empezar desde i = 0. Es correcto por su invariante, pero por volver al principio y no un paso atrás cuesta O(n³) en el peor caso, no O(n²): 166 749 comparaciones para 100 números al revés. Un gnome sort de verdad haría i--. → gnome sort, invariante

Entrega

¿Puedes entregar el archivo con un main de pruebas?

Solo comentado. El enunciado dice que el main se entrega únicamente si se pide un programa; aquí se piden funciones, y la Moulinette las compila con su propio main. Un segundo main no enlaza. → Moulinette

¿Por qué no hay ni un for?

Porque la Norma lo prohíbe, igual que do…while, switch y el ternario. Todos los bucles son while con el contador inicializado antes, y las declaraciones van al principio de la función. → la Norma

¿Podrías usar printf en ft_putstr?

No: la única función autorizada en ex05 es write, y en el resto del módulo, ninguna. Usar otra es un ejercicio suspendido aunque la salida sea la misma. → write, ex05