PDF de programación - Punteros

PUNTEROS

Francisco Javier Gil Chica

dfists, marzo 2010

ii

Índice general

Prólogo

1. Fundamentos

v

1.1. Qué es un puntero . . . . . . . . . . . . . . . . . . . . . . . .
1.2. Valor inicial de un puntero . . . . . . . . . . . . . . . . . . . .
1.3. Punteros a punteros . . . . . . . . . . . . . . . . . . . . . . . .
1.4. Aritmética de punteros . . . . . . . . . . . . . . . . . . . . . .
1.5. Punteros a bloques . . . . . . . . . . . . . . . . . . . . . . . .
1.6. Punteros a estructuras y estructuras auto-referenciadas . . . .
1.7. Punteros a funciones . . . . . . . . . . . . . . . . . . . . . . .
1.8. Declaraciones complejas

1
1
2
4
5
6
6
8
. . . . . . . . . . . . . . . . . . . . . 11

2. Punteros, cadenas y matrices

13
2.1. Cadenas de caracteres
. . . . . . . . . . . . . . . . . . . . . . 13
2.2. Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

3. Listas

19
Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.1.
Iniciar la lista . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.2.
3.3.
Insertar y eliminar nodos . . . . . . . . . . . . . . . . . . . . . 20
3.4. Fusión de listas . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.5.
Intercambio de elementos y ordenación de listas . . . . . . . . 26
. . . . . . . . . . . . . . . . . . . . . 28
3.6. Extracción de sub-listas

4. Árboles

31
Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
. . . . . . . . . . . . . . . . . . . . . . . . 33
Inserción de nodos
. . . . . . . . . . . . . . . . . . . 36

4.1.
4.2.
4.3. Encontrar y eliminar nodos

5. Punteros en otros contextos

41
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

5.1. Concepto

iii

iv

ÍNDICE GENERAL

5.2. FAT e i-nodos . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
5.2.1. FAT . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
5.2.2.
i-nodos . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
5.3. Gestión de memoria . . . . . . . . . . . . . . . . . . . . . . . . 45
5.4. Conclusión . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

Prólogo

Estas notas están dirigidas a mis alumnos de la asignatura de Periféricos,
de las titulaciones de Informática en la EPS de la Universidad de Alicante.
Aunque dicha asignatura no trata ni de programación, ni de estructuras de
datos ni de algorítmica, cada vez se ha hecho más evidente en los últimos años
la necesidad de estas notas con vistas a la realización de las prácticas de la
asignatura, que por tratar de cuestiones de bajo nivel requieren el manejo de
puertos, punteros, operaciones de bits y algunas pocas cosas más que tienden
a quedar relegadas debido a la evolución de la programación hacia lenguajes
de más alto nivel. Aquí he pretendido cubrir las posibles lagunas por lo que
respecta al uso de punteros en el contexto del lenguaje de programación C,
al tiempo que realzar la importancia que tiene manejarlos con soltura en
relación con aspectos fundamentales de la programación y estructuras de
datos.

A medida que se desciende de nivel, acercándonos a la máquina, la com-
putación se simplifica más y más. Al nivel más bajo, el del procesador, las
cosas son tremendamente sencillas (lo que no impide que puedan complicarse
si hay empeño en ello). Puesto que un programa es una secuencia de símbolos
que una vez compilada queda reducida a una larga serie de instrucciones de
procesador, podría pensarse en que nada de interés se encontrará allí. Pero
ocurre que la diferencia entre unos niveles y otros no es cuantitativa, sino
cualitativa. A bajo nivel, una secuencia de instrucciones de procesador es
algo aburrido y monótono. A muy alto nivel, todas esas abstracciones mod-
ernas son un estorbo que aleja de las soluciones eficientes. Y hay un nivel
intermedio, el que se encuentra entre ambos, donde ocurren cosas muy in-
teresantes. Las dos más interesantes son estas: la recursión y los punteros.
Estas notas tratan de los segundos.

v

vi

0. Prólogo

Capítulo 1

Fundamentos

1.1. Qué es un puntero

Cuando declaramos una variable entera, por ejemplo mediante

int i;

esta variable, una vez compilado el programa, se encontrará, en tiempo
de ejecución, en alguna parte de la memoria, y contendrá el valor que le
hayamos asignado, por ejemplo mediante

i=10;

Ocurre igual con los caracteres y los números reales, con las estructuras
y con las uniones: se encuentran en algún lugar de la memoria, y en ese lugar
de la memoria se almacena un valor. En el caso de la variable i, llamemos
m a la posición de memoria que ocupa. En la posición m de la memoria se
encontrará entonces el valor 10. Pues bien, un puntero es una variable como
cualquier otra, y contiene un número entero. Pero ese número no representa
unidades de algo (por ejemplo, con i=10; podríamos indicar un número de
pares de zapatos, los botones de una caja, los escalones de una escalera...)
sino la posición en memoria de otra variable.

En C, un puntero a entero se declara en la forma

int *p;

Un puntero a un número real

float *q;

1

2

1. Fundamentos

Un puntero a carácter como

char *c;

y así sucesivamente. Cuando escribimos

p=&i;

el operador & devuelve la dirección de la variable i, que en nuestro caso
es m. De manera que la variable p va a contener el valor m. Se dice que
p ((apunta)) a i, ya que indica en qué lugar se encuentra i. A su vez, p
se encuentra también en algún lugar. Puesto que p apunta a un lugar de
memoria donde está almacenado el valor 10, el ((valor apuntado)) por p es
precisamente 10. Este valor apuntado se escribe como

*p

1.2. Valor inicial de un puntero

Cuando declaramos una variable como en

int j;

no podemos suponer que j vaya a contener ningún valor particular. Sólo
sabremos qué contenga cuando pongamos allí un valor concreto. Por ejemplo,
después de hacer

j=20

sabemos que la variable j contiene el valor 20, de modo que la expresión

j+4 vale 24. De la misma manera, cuando declaramos un puntero como

int *p;

no podemos suponer que contiene ningún valor en concreto, es decir,
que apunta a ninguna dirección en particular. Pues bien, existen tres formas
distintas de asignar un valor a un puntero:

1. Llamando al gestor de memoria, que buscará un hueco libre y de-

volverá su dirección. Así, al escribir

int *p=(int *)malloc(sizeof(int));

1.2. Valor inicial de un puntero

3

estamos asignando a p la dirección de un hueco cuyo tamaño es sufi-
ciente para contener un entero. El gestor de memoria habrá buscado
un hueco libre del tamaño adecuado y la dirección de ese hueco que-
da asignada a p. En principio, no sabemos cual es esa dirección, de la
misma forma que cuando declaramos un entero no sabemos dónde se
localizará, lo cual no impide usarlo almacenando y recuperando en él
valores.

2. Asignándole la dirección de una variable ya declarada. Por ejemplo

int j=10;
int *p=&j;

Ahora p contiene la dirección de j (apunta a j), de forma que *p vale
10

3. Asignándole manualmente una dirección. Por ejemplo

char *p=0xb8000000;

hace que p apunte a una posición particular de la memoria de vídeo. En
concreto, al primer carácter de la pantalla (esquina superior izquierda)
en el modo texto a color de 25 filas por 80 columnas del adaptador
VGA.

Puesto que un puntero declarado no tiene asignado ningún valor, si le es
asignado ninguno (por error) antes de ser usado, cuando llegue ese momento
no habrá forma de saber si la dirección apuntada es o no lícita. Por eso
es buena práctica de programación asignar un valor a un puntero cuando
es declarado, o bien asignarle el valor NULL, de forma que, en un momento
posterior, pueda saberse si el puntero fue asignado o no:

char *p=(char *)NULL;
...
if (p==NULL){
...
}

4

1. Fundamentos

1.3. Punteros a punteros

Los punteros apuntan a variables. Pero un puntero es una clase de vari-
able, luego nada impide que un puntero apunte a otro. Así que podemos
tener punteros que apuntan a punteros, punteros que apuntan a punteros
que apuntan a punteros y así sucesivamente. Véase el siguiente programa:

#include <stdio.h>
main()
{

int j=10;
int *p=(int *)&j;
int **q=(int **)&p;
int ***r=(int ***)&q;
printf("%d %d %d\n",*p,**q,***r);
return;

}

p es un puntero que apunta a un entero; q es un puntero que apunta a
p, y es por tanto un puntero a un puntero; r es un puntero que apunta a
q; *p, **q y ***r son tres formas distintas de referirnos al mismo valor 10
almacenado en j.

En este punto, dado un puntero p declarado como

int *p;

y apuntado ya algún lugar, por ejemplo

int j=10;
....
p=(int *)&j;

no ha de haber dificultad en comprender la diferencia que existe entre p,
&p y *p. p es una variable, que contiene un número, que es una dirección.
Así que

printf("%p",p);

imprimirá el contenido de la variable p de la misma forma que

printf("%d",j);

imprime el contenido de la variable j. Puesto que p es una variable como
otra cualquiera, &p indica su dirección. No la dirección del lugar al que apunta
p, sino la dirección de la misma p. Finalmente, *p proporciona el contenido
que se haya almacenado en la dirección a la que apunta p.

1.4. Aritmética de punteros

5

1.4. Aritmética de punteros

Considérese el siguiente programa:

#include <stdio.h>
main()
{

int j;
char *p=(char *)&j;
int *q=(int *)&j;
long *r=(long *)&j;
printf("%p %p %p\n",p,q,r);
p+=1;
q+=1;
r+=1;
printf("%p %p %p\n",p,q,r);
return;

}

Se declaran tres punteros. Los tres apuntan a la misma dirección de memo-
ria, que es la de la variable j. A continuación incrementamos en una unidad
cada puntero y volvemos a imprimirlos. En efecto, el puntero p queda in-
crementado en una unidad, pero los punteros q y r se han incrementado en
cuatro unidades, no en una. El motivo es el siguiente: cuando un puntero se
incrementa en una unidad, el resultado no apunta a la siguiente dirección
de memoria, sino al siguiente objeto del tipo al que apunte el punt