Indice
1.
Punteros
2. Estructuras
dinámicas
3. Listas
Hemos visto ya cómo las variables son
las células de
memoria a las
que podemos tener acceso por un identificador. Pero estas
variables se
guardan en lugares concretos de la memoria de
la
computadora. Para nuestros programas,
la memoria de
la computadora es
solamente una sucesión de las células de
1 octeto (la talla mínima para un dato), cada una con una
dirección única.}
La memoria de
computadora
puede ser comparada con una calle en una ciudad. En una calle
todas las casas se numeran consecutivamente con un identificador
único tal que si hablamos del número 27 de la calle
Córdova, podremos encontrar el lugar sin pérdida,
puesto que debe haber solamente una casa con ese número y,
además, nosotros sabemos que la casa estará entre
las casas 26 y 28.
Una declaración de puntero consiste en un tipo base, un *
y el nombre de la variable.
La forma general de declaración de una variable puntero
es:
Tipo *nomb_var;
Donde:
Tipo: cualquier tipo valido ,ya sea primitivo o definido por el
usuario
nomb_var: es el nombre de la variable de tipo apuntador.
Los operadores de punteros
Existen dos operadores especiales de punteros: & y *.
El & devuelve la dirección de memoria de su operando. Por
ejemplo:
m=&cuenta;
pone en m la dirección de memoria de la variable cuenta.
Esta dirección es la posición interna de la
variable en la
computadora. La dirección no tiene nada que ver con el
valor de
cuenta. Se puede pensar en el operador & como devolviendo "la
dirección de".
El segundo operador de punteros, *, es el complemento de &.
Devuelve el valor de la
variable localizada en la dirección que sigue. Por
ejemplo, si m contiene la dirección de memoria de la
variable cuenta, entonces:
q=*m;
pone el valor de cuenta en q. Se puede pensar en * como "en la
dirección".
El siguiente programa ilustra
un ejemplo:
#include <stdio.h>
main()
{int cuenta, q;
int *m;
cuenta=100;
m=&cuenta; //m recibe la dirección de cuenta
q=*m; //a q se le asigna el valor de cuenta
indirectamente a través de m
print("%d,q") //imprime 100
}
Punteros estáticos
Definamos un puntero a un entero y una variable entera como
sigue:
Int *p1;
Int valor1;
Con estas definiciones es posible hacer las siguientes
asignaciones estáticas:
p1= *valor1;
*p1=25;
El apuntador p1 se define como un apuntador a un entero.
La variable valor2 se define como una variable entera. La primera
asignación hace que p1 apunte a la variable valor1, la
segunda asignación almacena en memoria el valor 25 en
donde p1 está apuntando.
Se dice que este tipo de inicialización es de tipo
estática porque la asignación de la
memoria que se utiliza para almacenar es fija. Una vez definida
la variable, el compilador establece suficiente memoria para
almacenar un valor de un tipo dado. Esta memoria permanece
reservada para esta variable y no es posible usarla para nada
más hasta que se termine la función.
Punteros Dinámicos
La segunda forma para inicializar un puntero es por medio de la
asignación dinámica de memoria. Por asignación
dinámica de la memoria se entiende que se
reserva memoria cuando se necesite para almacenar un valor de un
tipo dado. Después, una vez que no se necesite el valor,
es posible liberar la memoria y hacerla disponible para otro uso
por el sistema .
De nuevo definamos a p1 como un valor entero como sigue:
Int *p1;
Ahora es posible inicializar a p1 en forma dinámica para
apuntar a un valor de la siguiente manera:
p1=new int;
*p1=25;
Esta vez no es necesario inicializar primero p1 a la
dirección de un a variable estática.
En cambio el
operador new crea suficiente memoria para contener un valor
entero apuntado por p1. Después se almacena en esta
área de memoria el valor 25. Una vez que se asigna
dinámicamente la memoria como ésta, es posible
liberar la misma área de memoria usando el operador
delete, como sigue:
Delete p1;
Esta operación liberará la memoria apuntada por
p1.
Es importante señalar que el operador delete no elimina el
apuntador, simplemente libera el área de memoria al cual
se dirige el puntero. Por tanto luego que se ejecute el enunciado
anterior, p1 todavía existe como un puntero que no apunta
a nada, pero que es posible inicializarlo de nuevo para apuntar a
otro entero utilizando el operador new.
2. Estructuras
dinámicas
Las estructuras
dinámicas de datos son
estructuras que cuya dimensión puede crecer o disminuir
durante la ejecución del programa. Una
estructura
dinámica de datos es una
colección de elementos llamados nodos. Al contrario que un
array, que contiene espacio para almacenar un número fijo
de elementos, una estructura
dinámica de datos se amplía y contrae durante la
ejecución del programa.
Las estructuras dinámicas de datos se pueden
dividir en dos grandes grupos:
Lineales: listas enlazadas, pilas, colas
No lineales: árboles
, grafos
Las estructuras dinámicas de datos son de gran utilidad para
almacenar datos del mundo real, que están cambiando
constantemente. Por ejemplo si tenemos almacenados en un array
los datos de los alumnos de un curso, los cuales estan ordenados
de acuerdo al promedio, para insertar un nuevo alumno seria
necesario correr cada elemento un espacio: Si en su lugar se
utilizara una estructura dinámica de datos, los nuevos
datos del alumno se pueden insertar fácilmente.
Listas Enlazadas
Una lista enlazada es un conjunto de elementos llamados nodos en
los que cada uno de ellos contiene un dato y también la
dirección del siguiente nodo.
El primer elemento de la lista es la cabecera, que sólo
contiene un puntero que señala el primer elemento de la
lista.
El último nodo de la lista apunta a NULL (nulo) porque no
hay más nodos en la lista. Se usará el
término NULL para designar el final de la
lista.
La lista enlazada se muestra en la
siguiente figura:
Cabecera
Las operaciones que
normalmente se ejecutan con listas incluyen:
- Recuperar información de un nodo
específico. - Encontrar el nodo que contiene una información
específica. - Insertar un nuevo nodo en un lugar
específico. - Insertar un nuevo nodo en relación a una
información particular. - Borrar un nodo existente.
#include <iostream.h>
#include <conio.h>
#include <stdlib.h>
#include <stdio.h>
class nodo
{int num;
nodo *sgte;
public:
nodo(){sgte=NULL;}
void apns(nodo *n);
nodo *rpns();
void ingresar();
int mostrar();
};
void nodo::apns(nodo *n)
{sgte=n;}
nodo *nodo::rpns()
{return sgte;}
void nodo::ingresar()
{cin>>num;}
int nodo::mostrar()
{return num;}
/////////////////////////////////////////
class lista
{nodo *cab;
public:
lista(){cab=NULL;}
void insertar_i();
void insertar_f();
void eliminar_nodo();
void mostrar_lista();
void eliminar_i();
void eliminar_f();
void eliminar_lista();
};
void lista::insertar_f()
{nodo *a;
a=new nodo;
a->ingresar();
if(cab==NULL)
{cab=a;}
else
{nodo *temp,*temp1,*temp2;
temp=cab;
while(temp2!=NULL)
{temp1=temp->rpns();
temp2=temp1->rpns();}
temp->rpns();
temp->apns(a);
}
}
void lista::insertar_i()
{nodo *a;
a=new nodo;
a->ingresar();
if(cab==NULL)
cab=a;
else
{nodo *temp;
temp=cab;
cab=a;
cab->apns(temp);
}
}
void lista::mostrar_lista()
{nodo *t;
if (cab==NULL)
cout<<"La lista esta vacia";
else
{t=cab;
while(t!=NULL)
{//t=t->rpns();
cout<<t->mostrar();
t=t->rpns();
}
}
}
void lista::eliminar_nodo()
{nodo *temp,*temp1,*temp2;
temp1=cab;
int numero;
cout<<"ingrese numero a borrar";
cin>>numero;
if(temp1->rpns()==NULL)
cout<<"no hay elementos";
else
{do
{temp=temp1;
temp1=temp1->rpns();
if(temp1->mostrar()==numero)
{temp2=temp1->rpns();
temp->apns(temp2);
delete temp1;
}
}while(temp!=NULL); /////
}}
void lista::eliminar_i()
{if(cab==NULL)
cout<<"nno existen nodos";
else
{nodo *temp;
temp=cab;
cab=cab->rpns();
delete temp;
}
}
void lista::eliminar_f()
{if(cab==NULL)
cout<<"nno existen nodos";
else
{nodo *ptr1, *ptr2;
ptr2=cab;
ptr1=NULL;
while(ptr2->rpns()!=NULL)
{ptr1=ptr2;
ptr2=ptr2->rpns();
}
if(ptr1==NULL)
{delete cab;
cab=NULL;
}
else
{delete ptr2;
ptr1->apns(NULL);
}
}
}}
void lista::eliminar_lista()
{nodo *temp;
while(cab!=NULL)
{temp=cab;
cab=cab->rpns();
delete temp;
}
}
void main()
{int op;
lista b;
clrscr();
for(;;)
{
cout<<"nn<1> insertar al inicio";
cout<<"n<2> insertar al final";
cout<<"n<3> eliminar nodo";
cout<<"n<4> mostrar lista";
cout<<"n<5> eliminar inicio";
cout<<"n<6> eliminar final";
cout<<"n<7> eliminar lista";
cout<<"n<8> salirn";
op=getch();
switch(op)
{case '1': b.insertar_i();break;
case '2': b.insertar_f();break;
case '3': b.eliminar_nodo(); break;
case '4': b.mostrar_lista();break;
case '5': b.eliminar_i();break;
case '7': b.eliminar_lista();break;
case '8': exit(0);
}
}
}
Listas Doblemente Enlazadas
Hasta ahora se han manejado listas que se recorren en un asola
dirección. En algunas aplicaciones es práctico o
hasta indispensable poder recorrer
una lista en ambas direcciones. Para estos casos se tienen las
lista doblemente enlazadas. Esta propiedad
implica que cada nodo debe tener dos apuntadores, uno al nodo
predecesor y otro al nodo sucesor.
Cabecera
Listas Circulares
Una lista circular es una lista en la cual el último nodo
es enlazado al primer elemento de la lista. La ventaja de este
tipo de estructura es que siempre se puede llegar a cualquier
nodo siguiendo los enlaces. La desventaja es que si no se tiene
cuidado una búsqueda puede resultar en un bucle infinito.
Esto se puede evitar al determinar a un nodo como nodo-cabeza o
nodo inicial.
Pilas
Una pila es un tipo especial de lista lineal en la cual un elemento sólo puede ser añadido o eliminado por un extremo llamado cima. Esto significa que los elementos se sacan de la pila en orden inverso al que se pusieron en ella.
Las dos operaciones básicas asociadas a las pilas son:
-Poner: es añadir un elemento a la pila.
-Sacar: es extraer un elemento de la pila.
La pila es una estructura con numerosas analogías
en la vida real: una pila de platos, una pila de monedas, una
pila de bandejas, etc.
La representación consiste en un vector con espacio para
un máximo de elementos y un contador que indica el
número de elementos válidos almacenados en el
vector.
Colas
Una cola es una lista en las que las supresiones se realizan
solamente solamente al principio de la lista y las inserciones al
final de la misma. Al igual que en el caso de las pilas, hay que
prever un vector para almacenar el máximo número de
elementos que puedan presentarse en el programa. A diferencia de
las pilas, no basta con añadir un simple contador, tal que
indique el número de elementos válidos; sino hay
que prever dos índices que indiquen la posición del
comienzo y del final de la cola. Si la cola no está
vacía, en CABEZA está el primer elemento, y si la
cola no está llena, en FIN es el lugar donde se copia el
siguiente elemento que se incorpora a la misma.
Las colas se usan para almacenar datos que necesitan ser
procesados según el orden de llegada. En la vida real se
tienen ejemplos numerosos de colas: la cola de un cine, la cola
de un banco, etc; en
todas ellas el primer elemento que llega es el primero que
sale.
CABEZA FIN
Autor:
Mabel Gonzales Urmachea
Milagros Lamas Rodríguez 00110860
Ciudad Universitaria, Octubre del 2001