Unidad_6_-_Variables_de_Tipo_Puntero

Vista previa del material en texto

UNIDAD 6.- ABSTRACCIONES CON DATOS 
Cátedra: Algoritmos y Estructuras de Datos – Departamento Sistemas - 1 
 
UNIDAD 6.- ABSTRACCIONES CON DATOS 
 
OBJETIVOS: 
Que el alumno: 
 Comprenda el concepto de variables de tipo puntero. 
 Utilice las variables de tipo puntero con las distintas estructuras de datos. 
 Comprenda y utilice las variables de tipo puntero en una estructura dinámica. 
 
TEMAS: 
6.1. Variables de tipo puntero. 
6.2. Pilas. Implementación 
6.3. Introducción a la POO. Componentes básicos. Características. 
6.4. Implementación de estructuras. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
UNIDAD 6.- ABSTRACCIONES CON DATOS 
Cátedra: Algoritmos y Estructuras de Datos – Departamento Sistemas - 2 
 
6.1. Variables de tipo puntero. 
 
Todo programa que está siendo ejecutado por la CPU, ocupa un bloque de bytes en la 
memoria RAM del computador. Cuando un computador inicia su funcionamiento, el 
programa que toma el control es el Sistema Operativo. El mismo ocupa las direcciones 
bajas de memoria, es decir un bloque de bytes que comienza en la posición 0. 
Normalmente estas direcciones tienen un tamaño de 4 bytes (32bits) y se representan en 
Hexadecimal. De tal manera que la memoria RAM a la que se puede acceder en forma 
directa por la CPU comienza en la posición “00 00 00 00” y termina en “FF FF FF FF”. 
Cuando un programa se prepara para ejecutarse, el sistema operativo le asigna un 
bloque de memoria RAM que se divide en los siguientes sectores: CÓDIGO, DATOS, 
STACK (PILA), HEAP (MONTÍCULO). 
 El sector CÓDIGO contiene las instrucciones del programa en lenguaje de máquina 
absoluto. 
 El de DATOS contendrá las variables globales del programa. 
 En el STACK se almacenará las variables locales y los parámetros por valor de las 
funciones que utilice el programa, y la dirección del código donde deberá retornar 
cuando termine su ejecución. 
 En el HEAP, que suele ser más grande que los otros sectores, se utiliza para 
almacenar estructuras de datos que requieren cambiar su tamaño durante la 
ejecución del programa y necesitan gran cantidad de bloques de bytes. 
 
Una distribución típica de estos sectores se representa en el siguiente esquema: 
 
 
UNIDAD 6.- ABSTRACCIONES CON DATOS 
Cátedra: Algoritmos y Estructuras de Datos – Departamento Sistemas - 3 
 
En general los bloques de byte en el sector Stack, se van asignando a medida que 
se ejecutan las funciones y se liberan cuando las mismas finalizan; funcionando como una 
verdadera pila de datos, ya que el último bloque que se ocupa es el primero que se 
desocupa cuando la función correspondiente termina su ejecución. El Stack crece desde 
una posición determinada hacia la parte baja de la memoria. 
Por su parte, el Heap va creciendo desde una posición determinada, normalmente 
la que sigue a la posición de inicio del Stack, hacia la parte alta de la memoria. Los 
bloques de byte se van asignando mediante acciones del programa y su manejo es muy 
particular, ya que se va ocupando y desocupando bloques de memoria en forma 
prácticamente aleatoria tratando de aprovechar al máximo el espacio que va quedando 
liberado o disponible. 
Los tipos de datos que se almacenan en el sector DATOS y en el STACK, ocupan 
un espacio fijo de memoria que no puede cambiarse durante la ejecución del programa. 
Por ello es que se llama estos tipos “Estructuras ESTÁTICAS”, por ejemplo las variables 
simples tipo entero, real, lógicas o carácter, los arreglos, las cadenas, los registros. 
Por otro lado, los datos que se almacenan en el HEAP tienen como característica 
que el espacio de memoria ocupado por los mismos puede aumentar o disminuir durante 
la ejecución del programa. De ahí el nombre de “Estructuras DINÁMICAS”, por ejemplo 
las listas, pilas, colas, árboles y grafos. 
 
UNIDAD 6.- ABSTRACCIONES CON DATOS 
Cátedra: Algoritmos y Estructuras de Datos – Departamento Sistemas - 4 
 
Tipo Puntero y Asignación Dinámica de Memoria 
 
Un tipo puntero representa la dirección de memoria de un bloque de byte 
correspondiente a una estructura de datos cualquiera. 
Las variables de tipo puntero ocupan 4 bytes de memoria, de tal manera que 
pueden contener valores en el rango hexadecimal de “00 00 00 00” a “FF FF FF FF”. 
Estas variables se alojan en el Sector DATOS o STACK, según donde se declaren, en 
forma estática; pero, como veremos a continuación, nos permitirán acceder al Sector 
HEAP para manejar Estructuras Dinámicas de Datos. 
En lenguaje C++ se declaran las variables punteros utilizando la siguiente sintaxis: 
<tipo apuntado> *<identificador puntero> 
Para realizar la asignación dinámica de memoria en C++ se cuenta con el 
operador new, que lleva como operando el tipo de dato correspondiente al bloque y 
devuelve como resultado un puntero al mismo. Si se produce algún problema con la 
asignación de memoria en el HEAP, por ejemplo falta de espacio, se devuelve el valor 
NULL. 
La característica principal de la asignación dinámica de memoria es la de poder 
variar el tamaño de memoria que ocupa la estructura de datos. 
Es importante destacar que cuando no se necesitan más esos bloques, se puede 
desocuparlos o liberarlos y de ese modo disminuir el espacio de memoria que ocupa la 
estructura, en el lenguaje C++ se usa el operador delete que también lleva como 
operando al puntero. 
 
Ejemplos: 
Puntero a tipo int 
#include <stdio.h> 
#include <stdlib.h> 
 
main() 
{ 
 int a, *p; //declara la variable a de tipo entera y la variable p que es un puntero a una variable entero 
 
 a=15; 
 p=&a; 
 
 printf("El valor de a es: %d\n",a); 
 printf("Esta en la Direccion: %x",p); 
 
 *p=1000; 
 printf("\n\nNUEVO valor de a: %d\n",a); 
UNIDAD 6.- ABSTRACCIONES CON DATOS 
Cátedra: Algoritmos y Estructuras de Datos – Departamento Sistemas - 5 
 
 printf("Esta en la Direccion: %x",p); 
 
 getchar(); 
} 
En el próximo ejemplo se usa sólo la variable de tipo puntero. 
 
#include <stdio.h> 
#include <stdlib.h> 
 
main() 
{ 
 int *p; 
 
 p=new int; 
 
 *p=20; 
 printf("La direccion obtenida en p es: %x",p); 
 printf("\n\nEl valor almacenado es: %d\n",*p); 
 
 delete p; 
 
 getchar(); 
} 
 
Puntero con array 
En el próximo ejemplo se declara al vector v como una variable de tipo puntero. 
 
#include <stdio.h> 
#include <stdlib.h> 
 
main() 
{ 
 int *v,n,i; 
 
 printf("Ingrese el valor de n: "); 
 scanf("%d",&n); 
 
 /*crea el arreglo de n elementos en forma dinámica*/ 
 v=new int[n]; 
 
 for (i=0;i<n;i++) 
 { 
 printf("Ingrese el elemento de posicion %d: ",i); 
 scanf("%d",&v[i]); 
UNIDAD 6.- ABSTRACCIONES CON DATOS 
Cátedra: Algoritmos y Estructuras de Datos – Departamento Sistemas - 6 
 
 } 
 
 /*devuelve la memoria usada*/ 
 delete v; 
 getchar(); 
} 
 
Puntero con registros 
En el próximo ejemplo se usa un registro en forma estática y dinámica. 
 
#include <stdio.h> 
#include <stdlib.h> 
 
struct registro 
{ 
 int codigo; 
 float precio; 
}; 
 
main() 
{ 
 registro a,*p; 
 
 //en forma estática 
 a.codigo=2; 
 a.precio=2.2; 
 
 printf("Codigo: %d\n",a.codigo); 
 printf("Precio: %.2f\n",a.precio); 
 
 //en forma dinámica 
 p=&a; 
 p->codigo=4; 
 p->precio=4.4; 
 
 printf("Codigo: %d\n",p->codigo); 
 printf("Precio: %.2f\n",p->precio); 
 
 getchar(); 
} 
 
 
 
 
 
UNIDAD 6.- ABSTRACCIONES CON DATOS 
Cátedra: Algoritmos y Estructuras de Datos – Departamento Sistemas - 7 
 
Estructura Auto referenciada 
 
Se llama estructura auto referenciada a un registro que tiene al menos dos 
campos, en uno de los cuales se almacena una información determinada y en el otro un 
puntero a la misma estructura. Se dice que esta definición es recursiva, ya que para 
declarar el tipo correspondiente a este registro se debe declarar un puntero alpropio tipo 
que se está declarando. 
Ejemplo: 
 
struct nodo 
{ 
int info; 
 nodo *sig; 
}; 
Con esta clase de registros se pueden implementar estructuras dinámicas más 
complejas, como ser: listas, pilas y colas. 
A modo de ejemplo de la utilización de las mismas se ven las estructuras de pilas. 
 
6.2. Implementación de Pilas 
 
Es una estructura de datos especial en donde la inserción y el borrado de los 
nuevos elementos se realiza por sólo un extremo que se denomina frente. Esta estructura 
posee numerosas analogías en la vida real, por ejemplo imagine una pila de platos. 
 
 Dado que las operaciones de insertar y eliminar se realizan por un solo extremo (el 
superior), los elementos solo pueden eliminarse en orden inverso al que se insertan en la 
pila. El último elemento que se pone en la pila es el primero en sacar; dado a esto a estas 
estructuras se les conoce con el nombre de LIFO (Last Input First Output). 
 
 Las operaciones que se pueden realizar con una pila son: 
 INICIALIZAR (pila): Crea la estructura de pila asignando el valor NULL al puntero. 
 INSERTAR (pila, elemento): Introduce un elemento en la pila. 
 ELIMINAR (pila): Elimina un elemento de la pila. 
 RECORRER (pila): Permite recorrer la estructura de pila para ver o trabajar con 
sus elementos. 
 
 
UNIDAD 6.- ABSTRACCIONES CON DATOS 
Cátedra: Algoritmos y Estructuras de Datos – Departamento Sistemas - 8 
 
 
/*CREA UNA PILA CON ESTRUCTURA DINAMICA Y ALMACENA DE LA MISMA NUMEROS ENTEROS*/ 
 
#include <stdio.h> 
#include <stdlib.h> 
#include <conio.c> 
 
struct nodo 
{ 
 int info; 
 nodo *sig; 
}; 
 
void inicializar(nodo *&frente); 
void insertar(nodo *&frente, int x); 
int borrar(nodo *&frente); 
void recorrer(nodo *frente); 
 
main() 
{ 
 nodo *frente,*p; 
 int i,x; 
 
 inicializar(frente); 
 
 /*INGRESA TRES NODOS*/ 
 for (i=0;i<3;i++) 
 { 
 printf("Ingrese el valor de x: "); 
 scanf("%d",&x); 
 insertar(frente,x); 
 } 
 
 printf("\n\nSE BORRA EL VALOR: %d\n\n",borrar(frente)); 
 
 recorrer(frente); 
} 
 
void inicializar(nodo *&frente) 
{ 
 frente=NULL; 
} 
 
void insertar(nodo *&frente, int x) 
{ 
 nodo *p; 
 
 p=new nodo; 
UNIDAD 6.- ABSTRACCIONES CON DATOS 
Cátedra: Algoritmos y Estructuras de Datos – Departamento Sistemas - 9 
 
 
 if (p!=NULL) 
 { 
 p->info=x; 
 p->sig=frente; 
 frente=p; 
 } 
 else 
 printf("ERROR - PILA LLENA"); 
} 
 
int borrar(nodo *&frente) 
{ 
 if (frente!=NULL) 
 { 
 nodo *p; 
 int x; 
 
 p=frente; 
 x=frente->info; 
 frente=frente->sig; 
 delete p; 
 return x; 
 } 
 else 
 { 
 printf("ERROR - PILA VACIA"); 
 return 0; 
 } 
} 
 
void recorrer(nodo *frente) 
{ 
 nodo *p; 
 
 p=frente; 
 while (p!=NULL) 
 { 
 printf("%d\n",p->info); 
 p=p->sig; 
 } 
 getch(); 
}