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.
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.)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.
&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.
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).
* 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.
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.
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í.
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.
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.
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.
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.
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.
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.
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.
'\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ándarwrite(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.
/ 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, b | div | mod |
|---|---|---|
| -10, 3 | -3 | -1 |
| 10, -3 | -3 | 1 |
| -10, -3 | 3 | -1 |
El test de test/ prueba justo esos tres casos, además de INT_MAX e
INT_MIN entre 7.
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.
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.
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.
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.
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.
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.
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.
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».
void ft_ft(int *nbr)
{
*nbr = 42;
}
& ("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.void ft_ultimate_ft(int *********nbr)
{
*********nbr = 42;
}
* 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.void ft_swap(int *a, int *b)
{
int tmp;
tmp = *a;
*a = *b;
*b = tmp;
}
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.void ft_div_mod(int a, int b, int *div, int *mod)
{
*div = a / b;
*mod = a % b;
}
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.void ft_ultimate_div_mod(int *a, int *b)
{
int div;
int mod;
div = *a / *b;
mod = *a % *b;
*a = div;
*b = mod;
}
*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.void ft_putstr(char *str)
{
int i;
i = 0;
while (str[i])
{
write(1, &str[i], 1);
i++;
}
}
'\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.int ft_strlen(char *str)
{
int i;
i = 0;
while (str[i])
i++;
return (i);
}
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++;
}
}
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.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++;
}
}
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ú.
& 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
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
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
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
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
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
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
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
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
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
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