Punteros
Indirectamente ya estudiamos y analizamos el uso de punteros en C. Como los strings se implementan sobre arrays de caracteres y los arrays en si mismos representan un puntero el primero de sus elementos es muy dificil avanzar en este lenguaje de programación sin pasar por algún puntero.
Para trabajar con punteros, en C utilizamos el " * " (asterisco) pero debemos tener cuidado ya que el mismo asterisco se utiliza para dos casos diferentes. Veamos un ejemplo.
testPtr1.c
1:
2:#include<stdio.h>
3:
4:void duplica(int *a)
5:{
6: *a = 2 * (*a);
7:}
8:
9:int main()
10:{
11: int n=10;
12: duplica(&n);
13: printf("n=%d\n",n);
14:}
15:
En este ejemplo definimos la función duplica cuyo objetivo es duplicar el valor del argumento que recibe como parámetro.
Recordemos que en C no existe el concepto de "parámetro por referencia". La única manera de que una función pueda modificar el valor de sus parámetros es que reciba un puntero al valor a modificar.
En primer lugar utilizamos el asterisco para indicar, en el prototipo de la función (línea 4), que se espera un parámetro de tipo "puntero a int". La expresión int *a indica que a es un puntero a entero.
En la imagen vemos como a apunta a un espacio de memoria que contiene el valor (en este ejemplo) 10.
En la línea 6 utilizamos el asterisco para referirnos a "el contenido de a". Si a es el puntero, entonces *a es el contenido direccionado por el puntero a. A ese contenido le asignamos 2 por el contenido de a con lo que estamos duplicando el contenido del puntero que recibimos como parámetro.
Reumiendo, el asterisco se utiliza en la definición de variables para indicar que cierta variable (o parámetro) es de tipo puntero y luego, se utiliza para hacer referencia al contenido de un puntero.
En la función main, en la línea 12 utilizamos el ampersand " & " para hablar de "la dirección" de la variable n y así le pasamos el parámetro (de tipo puntero a int) a la función duplica.
Alocar y Liberar Memoria
Las funciones con las que podemos alocar y liberar memoria son:
- malloc - para alocar memoria
- free - para liberar memoria
testPtr2.c
1:
2:#include<stdio.h>
3:
4:int main()
5:{
6: // defino un puntero a entero
7: int *a;
8:
9: // aloco memoria y asigno su direccion
10: a=(int*)malloc(sizeof(int));
11:
12: // al contenido de a le asigno un valor 10
13: *a=10;
14:
15: // utilizo el contenido del puntero a
16: printf("El contenido de a es: %d\n",*a);
17:
18: // libero la memoria que direccionada por a
19: free(a);
20:}
21:
La función malloc retorna un void*. Esto debe leerse como un "puntero genérico" por lo tanto, si lo que esperamos en un puntero a int debemos "castear" el resultado a int* (ver línea 10).
Punteros a Punteros
Dijimos que para que una función pueda modificar el valor de un parámetro debe recibir un puntero a dicho valor. Entonces la función está recibiendo una referencia al valor y así lo puede modificar. Pero que pasa si en una función necesitamos modificar el valor de un puntero? Por ejemplo, recibimos un puntero al primer elemento de una lista ordenada y queremos modificar su valor para que apunte a un nuevo nodo cuyo orden determinamos que debe ser anterior al que hasta ahora considerábamos como el primero. En este caso tendríamos que recibir una referencia al puntero. Esto es lo que llamamos un puntero al puntero.
testPtr3.c
1:
2:#include<stdio.h>
3:
4:// recibe un puntero a puntero a int o (lo que es
5:// lo mismo) un "puntero por referencia"
6:void asignaValor(int **p)
7:{
8: // al contenido de p le asigno la direccion
9: // de la memoria que estoy alocando con el malloc
10: // (recordemos que p es un puntero a puntero por
11: // lo tanto *p es su contenido: el puntero)
12: *p=(int*)malloc(sizeof(int*));
13:
14: // al contenido del contenido de p le asigno 10
15: *(*p)=10;
16:}
17:
18:int main()
19:{
20: // defino un puntero a entero
21: int *a=NULL;
22:
23: // la funcion le asigna una direccion al puntero
24: asignaValor(&a);
25:
26: // probamos que la funcion asigno una direccion
27: // al puntero a
28: printf("El contenido de a vale: %d\n",*a);
29:}
30:
El ejemplo de la lista ordena (la función insertaOrdenado se explica más abajo).
Estructuras Dinámicas
En este capítulo analizaremos algunas de las operaciones que explicamos para manejo de listas enlazadas. El desarrollo de las otras estructuras como ser Pilas y Colas quedará a cargo del lector.
Lista Enlazada
La estructura (o registro) Nodo la definiremos en un archivo .h para luego incluirlo y utilizarlo en los archivos .c en los que necesitemos utilizar la estructura.
listas.h
1:
2:struct Nodo
3:{
4: int info;
5:
6: // dentro de la estructura todavia no tenemos
7: // definido el typedef por lo tanto para definir
8: // el puntero al siguiente elemento debemos usar
9: // el verdadero nombre de la estructura:
10: // "struct Nodo"
11: struct Nodo *sig;
12:} typedef Nodo;
13:
Teniendo definido el tipo Nodo podemos comenzar a analizar las siguientes operaciones sobre listas.
Agregar un Elemento (función agregar)
1:
2:#include<stdio.h>
3:#include "listas.h"
4:
5:// recibe "por referencia" el puntero a la lista
6:// y el valor que se quiere agregar
7:void agregar(Nodo **lst, int valor)
8:{
9: Nodo *aux;
10:
11: // creo el nodo a insertar
12: Nodo *nuevo=(Nodo*)malloc(sizeof(Nodo));
13:
14: // cuando tenemos un puntero a una estructura
15: // podemos referirnos a los campos directamente
16: // haciendo variable->campo ("->" se lee "flecha")
17: nuevo->info=valor;
18: nuevo->sig=NULL;
19:
20: if( *lst == NULL )
21: {
22: // modifico el puntero
23: *lst = nuevo;
24: }
25: else
26: {
27: aux = *lst;
28: while( aux->sig != NULL )
29: {
30: // la expresion aux->sig es equivalente
31: // a (*aux).sig. La notacion con "flecha"
32: // es mas simple
33: aux = aux->sig;
34: }
35:
36: aux->sig = nuevo;
37: }
38:}
39:
40:// test
41:int main()
42:{
43: // creamos dos punteros, uno para la lista y
44: // uno auxiliar para recorrerla
45: Nodo *p=NULL, *aux;
46:
47: // notemos que como p es un puntero la direccion
48: // de p es un puntero al puntero, por eso en la
49: // definicion de la funcion agregar recibimos
50: // Nodo **lst (puntero a puntero de tipo Nodo)
51: agregar(&p,1);
52: agregar(&p,2);
53: agregar(&p,3);
54: agregar(&p,4);
55: agregar(&p,5);
56:
57: aux=p;
58: while( aux != NULL )
59: {
60: printf("%d\n",aux->info);
61: aux=aux->sig;
62: }
63:
64: // falta liberar la memoria
65:}
66:
La función agregar que analizamos en Pascal recibía por referencia el puntero al inicio de la lista. En C la vamos a programar exactamente igual, pero surge un problema: no podemos pasar parámetros por referencia. Si queremos que la función pueda modificar el valor de un parámetro tenemos que recibir un puntero.
Cuando invocamos por primera vez a la función agregar esta debe crear el primer nodo de la lista y hacer que el puntero que recibe como parámetro apunte al nodo recién alocado. Debe modificar el puntero para que apunte a la dirección del nuevo nodo. Para que esto sea posible tenemos que recibir un puntero al puntero, esto se define con dos asteriscos (línea 7).
En la línea 20 preguntamos si la lista está vacia. Recordemos que lst es la dirección de la dirección del primer nodo de la lista entonces *lst es la dirección del primer nodo de la lista. Si efectivamente la lista está vacia corresponde asignar la dirección del primer nodo al parámetro. La asignación la hacemos a *lst que representa al contenido de lst quien es el puntero al puntero por lo tanto el contenido del puntero al puntero es el puntero.
Para aclarar un poco más sobre el tema de "puntero a puntero" veamos el siguiente gráfico.
1 - En la función main definimos la variable Nodo *p y la inicializamos con NULL. Con esto reservamos 4 bytes en los que podremos guardar una dirección de memoria. Esa dirección de memoria no fue asignada aún por lo tanto decimos que p apunta a NULL.
2 - En la función agregar queremos modificar el valor de p (la dirección que contiene) haciendo que no contenga más NULL y que pase a contener la dirección del contenido del nuevo nodo (que en el gráfico apunta a un nodo con info=10 a modo de ejempo).
3 - Para que esto sea posible tenemos que "recibirlo por referencia". Esto implica que no trabajaremos directamente con p sino con un puntero a p.
4 - En la función main, teniendo definido p podemos facilmente obtener un puntero a p hablando de &p.
5 - Como p es un puntero, &p es un "puntero a puntero". Como la función agregar recibe un "puntero a puntero", para indicarlo en el header de la función lo hacemos con: Nodo **lst. Un "puntero a puntero a Nodo".
6 - Cuando en la línea 23 hacemos *lst = nuevo estamos asignando la dirección contenida en nuevo al contenido de lst (p en la función main) quien quedará modificado dejando de apuntar a NULL y pasando a contener el mismo valor que nuevo (la dirección del nodo con info=10 que vemos en el ejemplo).
Insertar Elementos en Orden (función insertarOrdenado)
1:
2:#include<stdio.h>
3:#include "listas.h"
4:
5:// Retorna un puntero al nodo insertado
6:Nodo* insertarOrdenado(Nodo **lst, int valor)
7:{
8: // defino tres punteros a Nodo
9: Nodo *aux, *ant, *nuevo;
10:
11: // aloco memoria para el nodo a insertar
12: nuevo = (Nodo*)malloc(sizeof(Nodo));
13: nuevo->info=valor;
14:
15: // caso 1: la lista esta vacia,
16: // el nuevo nodo sera el primero
17: if( *lst==NULL )
18: {
19: nuevo->sig=NULL; // nuevo es primero y ultimo
20: *lst=nuevo; // la lista comienza en nuevo
21: return nuevo; // retorna el puntero al
22: } // nuevo nodo y termina
23:
24: // caso 2: el valor a insertar es menor que el
25: // primero.
26: if( valor < (*lst)->info )
27: {
28: nuevo->sig = *lst;
29: *lst=nuevo;
30: return nuevo;
31: }
32:
33: aux=*lst;
34: ant=NULL;
35:
36: while( aux!=NULL && aux->info<valor )
37: {
38: ant=aux;
39: aux=aux->sig;
40: }
41:
42: if( aux==NULL ) // el nuevo nodo va al final
43: {
44: ant->sig=nuevo;
45: nuevo->sig=NULL;
46: }
47: else // el nuevo nodo va entre ant y aux
48: {
49: ant->sig=nuevo;
50: nuevo->sig=aux;
51: }
52:
53: return nuevo;
54:}
55:
56:// test
57:int main()
58:{
59: Nodo *p=NULL, *aux;
60:
61: insertarOrdenado(&p,3);
62: insertarOrdenado(&p,5);
63: insertarOrdenado(&p,1);
64: insertarOrdenado(&p,2);
65: insertarOrdenado(&p,4);
66:
67: aux=p;
68: while( aux != NULL )
69: {
70: printf("%d\n",aux->info);
71: aux=aux->sig;
72: }
73:
74: // falta liberar la memoria
75:}
76:
La implementación de esta función es practicamente idéntica a la que codificamos en Pascal. Lo único que creo conveniente resaltar es lo que vemos en la línea 26: estamos comparando valor con el valor contenido en el campo info del primer nodo de la lista. Entonces: si hablamos de *lst hablamos del puntero al primer nodo y (*lst)->info representa al campo info del contenido de dicho puntero.
Liberar La Memoria usada por la Lista (función liberar)
1:
2:void liberar(Nodo **lst)
3:{
4: Nodo *auxSig, *aux;
5:
6: aux=*lst;
7:
8: while( aux!=NULL )
9: {
10: auxSig=aux->sig;
11:
12: // liberamos la memoria con la funcio free
13: free(aux);
14: aux=auxSig;
15: }
16:
17: // no es necesario, pero no cuesta nada...
18: *lst=NULL;
19:}
20:
Como vemos practicamente no hay diferencias con la función liberar que programamos en Pascal.
En C la función que libera la memoria es la función free (ver línea 13)
El resto de las operaciones sobre listas y las otras estructuras analizadas como Pilas y Colas quedarán a cargo del lector.
Resumen y Comparación entre C y Pascal
1 - El siguiente ejemplo compara como se define un puntero, se aloca memoria y se libera la memoria direccionada por el puntero.
En Pascal
1:
2:var p: ^integer;
3:begin
4: new(p);
5: p^:=10;
6: writeln('el contenido de p es',p^);
7: dispose(p);
8:end.
9:
En C
1:
2:int main()
3:{
4: int *p;
5: p=(int*)malloc(sizeof(int));
6: *p=10;
7: printf("El contenido de p es %d\n",*p);
8: free(p);
9:}
2 - El próximo ejemplo muestra como se puede recibir un puntero como parámetro por referencia de forma tal que una función pueda alocar memoria y asignar la dirección de la memoria alocada al parámetro.
En Pascal
1:
2:type
3: // definimos un tipo "puntero a integer"
4: PInteger = ^integer;
5:
6:// la funcion recibe por referencia (con var) un
7:// puntero a integer
8:procedure f(var pp:PInteger);
9:var aux:PInteger;
10:begin
11: new(aux);
12: aux^:=10;
13: pp:=aux;
14:end;
15:
16:// programa principal
17:var p:PInteger;
18:begin
19: // dentro de la funcion f alocamos memoria y
20: // asignamos a p la direccion de la memoria
21: // alocada
22: f(p);
23: writeln('el contenido de p es: ',p^);
24: dispose(p);
25:end.
26:
En C
1:
2:// la funcion recibe un int** esto es como si fuese
3:// un parametro tipo puntero "por referencia"
4:void f(int **pp)
5:{
6: int *aux=(int*)malloc(sizeof(int));
7: *aux=10;
8: *pp=aux;
9:}
10:
11:int main()
12:{
13: int *p;
14: f(&p);
15: printf("El contenido de p es %d\n",*p);
16: free(p);
17:}
18:
.
No hay comentarios:
Publicar un comentario