lunes, 13 de diciembre de 2010

C/C++ para Estructuras de Datos

Para una mejor comprensión de los algoritmos que a veces posteo en el blog, me ha parecido conveniente explicar algunas partes del lenguaje C/C++ que se usan al implementar estructuras de datos tales como listas, arboles, grafos, etc. Así, cuando la complejidad del código presente dificultades al lector, éste siempre podrá volver a este contenido para disipar sus dudas.

Aunque trataré explicar los temas sin que haya necesidad de mucho conocimiento previo, este texto no ha sido pensado para alguien que empieza desde cero. Si ese es tu caso es muy probable que no vayas a entender nada, así que no te desanimes por ello.

Este post estará sujeto a modificaciones a fin de añadir contenido, corregir errores, hacer mejoras, etc. Puedes ayudar con tus comentarios y sugerencias. Tu opinión importa ;)

C/C++ para Estructuras de Datos

1. Estructuras.

Las estructuras o registros son un conjunto de variables no necesariamente de tipos iguales cuyos valores están relacionados para poder definir un elemento. Por ejemplo el elemento “Punto” esta definido por dos variables reales x e y. Una estructura se declara usando la palabra reservada struct seguida del nombre de la estructura y entre llaves la declaración de las variables que la conforman. Ejemplo:

//Estructura Punto
struct Punto {
 double x; //coordenada x
 double y; //coordenada y
};

Luego de definir la estructura podemos instanciar variables de ella de la siguiente manera:

Punto unPunto; //variable del tipo Punto

Para acceder a un campo de la estructura se usa el operador “.” (punto) colocado después del nombre de la variable y seguido por el nombre del campo. Por ejemplo:

unPunto.x = 0; //asigna 0 al campo x
unPunto.y = 1; //asigna 1 al campo y

2. Punteros.

Los punteros son variables especiales que guardan la dirección de memoria de otras variables. Un puntero se declara escribiendo el tipo de la variable referida seguido del operador “*” (asterisco) y el identificador del puntero.

int *puntero; //declara un puntero a variable entera

Para que un puntero haga referencia a una variable se usa el operador “=” (asignación) después del identificador del puntero y seguido por la dirección de memoria de la variable. La dirección de memoria se obtiene mediante el operador “&” (dirección) seguido del identificador de la variable.

int var = 1; //declara un entero var
int *p;  //declara un puntero p
p = &var; //asigna a p la dirección de var

Para acceder al valor de la variable referida se usa el operador “*” (indirección) seguido del identificador del puntero.

int var=10, *p=&var; 
cout<<*p; //muestra el valor de var
*p = 20; //asigna 20 a var

2.1 Punteros a estructuras.

Se puede declarar punteros que hagan referencia a estructuras de la misma forma que se hace para las variables simples.

struct Punto {
 double x;
 double y;
};

Punto unPunto; //variable del tipo Punto
Punto *p; //puntero a una estructura del tipo Punto 
p = &unPunto; //p hace referencia a la variable unPunto

La sintaxis para acceder a los campos de una estructura mediante un puntero es algo especial. Por ejemplo la siguiente sintaxis produce error:

Punto unPunto, *p=&unPunto;
*p.x = 0; //produce error
*p.y = 1; //produce error

La intención del código anterior era que mediante “*p” referirnos a la estructura apuntada y mediante “.x” acceder a su campo x para asignarle 0. Pero ¿por qué produce error? El error se debe a la precedencia de operadores es decir a la jerarquía con que el compilador interpreta los operadores “.” y “*”. El operador “.” tiene mayor jerarquía y se interpreta primero y luego el “*” por lo tanto lo que entiende el compilador es que p es una estructura (no un puntero a estructura) y que mediante “p.x” queremos acceder a su campo x además su campo x debe ser un puntero y mediante “*” queremos referir a la variable apuntada por x. Como eso no es cierto produce error. Entonces para solucionar este problema tenemos que darle mayor precedencia al operador “*” para ello usaremos el operador de jerarquía “()”.

Punto unPunto, *p=&unPunto;
(*p).x = 0; //asigna 0 al campo x de la estructura unPunto
(*p).y = 1; //asigna 1 al campo y de la estructura unPunto

Ahora ya no produce error pues “(*p)” hace que el compilador interprete primero “*p” y luego “.x” y logra acceder correctamente al campo x. Sin embargo existe una sintaxis mas sencilla para lograr el mismo efecto y es mediante el operador “->” (flecha). Nota: al operador “.” también se le llama selector directo y al operador “->” también se le llama selector indirecto. Y ambos sirven para acceder a los miembros de una estructura.

Punto unPunto, *p=&unPunto;
p-­>x = 0; //asigna 0 al campo x de la estructura unPunto
p-­>y = 1; //asigna 1 al campo y de la estructura unPunto
cout<<p­>x; //muestra 0
cout<<p­>y; //muestra 1

Lo correcto es usar el operador flecha para acceder a los campos de una estructura desde un puntero pues fue creado para ese propósito. Sin embargo no esta mal aprender una forma alternativa.

2.2 Punteros a punteros.

Un puntero a puntero es un puntero que guarda la dirección de memoria de otro puntero. Ejemplo:

int var=10, *p=&var;
int **pp; //declara un puntero a puntero
pp = &p; //asigna a pp la dirección de p

Para acceder al puntero referido o a la variable referida usamos “*” o “**”. Ejemplo:

int var1=10, var2=20, *p=&var1, **pp=&p;
cout<<*pp; //muestra el valor de p (dirección de var1)
cout<<**pp; //muestra el valor de var1
*pp = &var2 //asigna a p la dirección de var2
**pp = 30; //asigna 30 a var2

Podemos declarar punteros a punteros a varios niveles. Ejemplo:

int var=10, *p1=&var, **p2=&p1, ***p3=&p2, ****p4=&p3;
cout<<*p1; //muestra el valor de var (10)
cout<<**p2; //muestra el valor de var (10)
cout<<***p3; //muestra el valor de var (10)
cout<<****p4; //muestra el valor de var (10)
if(****p4 == var){cout<<”son iguales”<<endl;}
if(***p4 == p1){cout<<”son iguales”<<endl;}
if(**p4 == p2){cout<<”son iguales”<<endl;}
if(*p4 == p3){cout<<”son iguales”<<endl;}

3. Gestión dinámica de memoria.

Cuando se declara una variable el compilador reserva espacio para esa variable automáticamente y lo libera cuando considera conveniente. A este tipo de gestión de memoria se le conoce como gestión automática. La gestión dinámica de memoria nos permite reservar y liberar memoria cuando nosotros consideremos que es necesario, nos hace responsables por los espacios de memoria que reservamos. Para reservar memoria dinámica usamos la palabra reservada new que devuelve la dirección de memoria del espacio reservado. Usamos un puntero para almacenar esa dirección. Ejemplo:

int *p = new int; //asigna a p la dirección de memoria de
   //un espacio reservado para un int

Para manejar el espacio de memoria reservado lo hacemos a través del puntero como ya se explicó anteriormente. Veamos:

int *p = new int;
*p = 10; //asigna 10 al espacio reservado

Para liberar memoria dinámica usamos la palabra reservada delete seguida de la dirección del espacio a liberar. Esa dirección es representada por un puntero. Ejemplo:

int *p = new int;
delete p; //libera el espacio reservado referido por p

4. Funciones

Una función es un conjunto de lineas de código que se encarga de realizar una tarea especifica. Las funciones pueden recibir un conjunto de parámetros y devolver un resultado. A las funciones que no devuelven ningún resultado se les dice procedimientos. Ejemplo de función:

int main(){
 int a=1, b=2, c;
 c = suma(a, b);  //c recibe el valor devuelto por suma()
 return 0;
}

//Función que recibe dos enteros y devuelve su suma.
int suma(int sum1, int sum2) {
 return sum1 + sum2;
}

Las funciones pueden recibir parámetros por valor o por referencia. Decimos que se esta pasando un parámetro por valor cuando la función recibe una copia del valor de la variable que se pone como argumento en la llamada a la función. El ejemplo anterior es también un ejemplo de paso de parámetros por valor. Se dice que se esta pasando un parámetro por referencia cuando la función recibe la dirección de memoria de la variable que se pone como argumento en la llamada a la función. Esta ultima forma de pasar parámetros nos permite modificar el valor de las variables que no están en el ámbito de la función, el anterior no. Ejemplo de paso por parámetros por referencia:

int main(){
 int a=1, b=2, c=0;
 suma(a, b, &c);  //se pasa la dirección de c
 return 0;
}

//Procedimiento que recibe dos valores enteros y la dirección de 
//una variable entera. Modifica el valor de la variable
//asignandole la suma de los enteros.
void suma(int sum1, int sum2, int *rpta) {
 *rpta = sum1 + sum2;
}

Ahora ricemos el rizo, ¿cómo pasamos un puntero por referencia? Para ello nuestra función debe recibir la dirección del puntero ello se hará mediante un puntero a puntero. Veamos:

int main(){
 int *p;
 iniciar(&p); //pasamos la dirección del puntero
 return 0;
}

//Procedimiento que asigna un espacio de memoria a un puntero.
//Se recibe la dirección del puntero en un puntero a puntero y
//se modifica el puntero para que apunte al nuevo espacio de
//memoria reservado.
void iniciar(int **pp) {
 *pp = new int;
}

Nos va a interesar pasar punteros por referencia cuando queramos modificar la dirección a la que apuntan fuera del ámbito donde se declaro el puntero.

Para terminar con el tema de funciones veamos funciones que devuelven una dirección de memoria, es decir que devuelven un puntero. Para declarar una función que retorna un puntero se debe anteponer el operador * al nombre de la función. Veamos:

int main(){
 int *p;
 p = iniciar(); //p recibe el espacio reservado
 return 0;
}

//Función que reserva un espacio de memoria para entero y
//devuelve su dirección 
int *iniciar() {
 int *p = new int;
 return p;
}

3 comentarios:

  1. exelente muchas gracias me ha aclarado mucho en la parte de punteros

    ResponderEliminar
  2. Gracias hermano , yo tambien estudio en la fisi(UNMSM) espero te puedas dejar tu facebook para estar en contacto.

    ResponderEliminar
  3. Hola tío...

    Disculpa que no deje datos de contacto en los comentarios, pero es para evitar el spam.

    Si necesitas ponerte en contacto conmigo puedes mandarme un mensaje usando este formulario:

    http://alguienenlafisi.blogspot.com/p/contacto.html

    (así tampoco tienes que dejar tus datos expuestos)

    Un saludo y gracias por visitar el blog :)

    ResponderEliminar