Fandom

Scratchpad

PLE:Unidad7

216,178pages on
this wiki
Add New Page
Discuss this page0 Share

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.

Punteros

La memoria está constituída por celdillas, cada una de las cuales tiene asignada una dirección única. Los punteros constituyen un tipo especial de datos que almacenan direcciones de memoria. Podemos emplear punteros para acceder al contenido de una determinada posición de memoria. Para declarar un puntero debemos especificar el tipo de dato hacia el que apunta además de utilizar el operador de indirección '*' delante de la variable de tipo puntero.

Ejemplo:

int *p1, n=1;
char *p2, c='a';
...
p1=&n;
p2=&c;


Veamos el contenido de meroria del fragmente de código anterior:

DirecciónVariableContenido
0012FDE0p10012FDE4
0012FDE4n1
0012FDE6p20012FDEA
0012FDEAca


El operador dirección '&'

El operador dirección (&) devuelve la dirección de memoria de una variable. Este operador puede ser utilizado para asignar una direccióna un puntero, permitiendo posteriormente el acceso al contenido apuntado por dicho puntero.

DirecciónVariableContenido
0012FDE0p10012FDE4
0012FDE4n1
0012FDE6p20012FDEA
0012FDEAca
&p1 == 0012FDE0
&n == 0012FDE4
&p2 == 0012FDE6
&c == 0012FDEA

Mediante este operador asignamos valor a un puntero.

p1 = &n;
p2 = &c;

Debemos tener en cuenta que puede ser necesaria una conversión de tipo, por que no se corresponda el tipo apuntado por el declarado para dicho puntero.

int *p1; char c;
p1 = &c; // ERROR
p1 = (int *) &c;

El operador indirección '*'

El operador indirección (*) devuelve el contenido un puntero. Esto nos va a permitir acceder al contenido apuntado por dicho puntero.

DirecciónVariableContenido
0012FDE0p10012FDE4
0012FDE4n1
0012FDE6p20012FDEA
0012FDEAca

Ejemplo:

*p1 == 1
*p2 == 'a'

Mediante este operador asignamos valor a la variable apuntada por el puntero.

*p1 = 5;
*p2 = 'b';
DirecciónVariableContenido
0012FDE0p10012FDE4
0012FDE4n5
0012FDE6p20012FDEA
0012FDEAcb

Aritmética de punteros

Podemos utilizar los operadores de incremento y decremento para acceder a direcciones contiguas de meoria. Esto nos permite hacer recorridos secuenciales de una determinado trozo de memoria:

Se puede utilizar: ++, --, +, -

int *p, n1=8,n2=9,n3=10;
p = &n1;
DirecciónVariableContenido
0012FDE0p10012FDE4
0012FDE4n18
0012FDE6n29
0012FDE8n310
p++;             // p = 0012FDE6
p + = 1;         // p = 0012FDE8
p = p – 1;         // p = 0012FDE6
cout << *p         // Muestra 9
cout << *(p--) // Muestra 8


Arrays y punteros

Los arrays son punteros constantes, lo que significa que una vez declarados, no pueden cambiar la dirección de memoria que le asigna el compilador:


int num[10]; // num es un puntero a num[0]
int *p;
...
p = &num[0]; // p = num;


Podemos aplicar aritmética de punteros a los arrays:

num == &num[0];
num + 1 equivale a &num[1];
num + 2 equivale a &num[2];

Podemos usar índices en variables de tipo puntero:

p = &num[0];
p[0] equivale a *(p);
p[1] equivale a *(p + 1);
p[2] equivale a *(p + 2);

Tambien podemos acceder a los elementos de un array mediante punteros:

*p equivale a vect[0], a *vect y a p[0]
*(p+1) equivale a vect[1], a *(vect+1) y a p[1]
*(p+2) equivale a vect[2], a *(vect+2) y a p[2]

Veamos varios ejemplo de acceso a los elementos de un array.

Acceso a los elementos del array mediante indice:

//suma los N elementos del array a
int a[N], suma, i, *p;
for(i=0, suma=0; i<N; ++i) // forma 1
    suma += a[i];


Acceso a los elementos del array mediante aritmética de punteros:

int a[N], suma, i, *p;
for(i=0, suma=0; i<N; ++i) // forma 2
    suma += *(a+i);

Acceso mediante indice usando un puntero

int a[N], suma, i, *p;
for(p=a, i=0, suma=0; i<N; ++i) // forma 3
    suma += p[i];

Acceso mediante aritmética de punteros usando un puntero

int a[N], suma, i, *p;
for(p=a, suma=0; p<&a[N]; ++p) // forma 4
    suma += *p;


Punteros genéricos

Podemos especificar punteros genéricos indicando que son de tipo void. Los punteros genéricos pueden apuntar a cualquier tipo de dato

Ejemplo

void *ptr;
int n=1;
char *cadena="Hola";
ptr = cadena;
ptr = &n;

Puntero Nulo

El Puntero nulo "NULL" es utilizado para asignar un valor que apunta a ninguna parte. Puede ser utilizado para inicializar punteros.

void *ptr = NULL;

Podemos crear punteros que apunten a otro puntero

int x, *p, **q;
x = 2;
p = &x;
q = &p;

cout << **q;

De igual manera podemos crear un array de punteros

int *x[2], n1=1, n2=2;
x[1] = &n1;
x[2] = &n2;
cout << *x[1];
cout << *x[2];

Accediendo a estructuras con punteros

Al igual que ocurre con otros tipos de datos, una variable de tipo estructura puede ser accedida mediante punteros

struct agenda {
  char nombre[30];
  char tlf[10];
};

agenda a;
agenda *pa;

En este caso "a" es una variable de tipo agenda, y "pa" es un punteros que apunta a una variable de tipo agenda.

pa = &a;

Ahora podemos acceder a los datos desde el puntero "pa", usando el operador -> como se muestra a continuación

pa->nombre
pa->tlf

Veamos un ejemplo completo de acceso mediante puntero a una estructura:

#include <iostream>
using namespace std;

struct agenda {
  char nombre[30];
  char tlf[10];
};


int main ()
{
	agenda *pa;

	pa = new agenda;

	cout << "Introduzca un nombre: ";
	cin >> pa->nombre;

	cout << "Introduzca un teléfono: ";
	cin >> pa->tlf;

	cout << "\nValores:\n";
	cout << pa->nombre;
	cout << pa->tlf << "\n";
	delete pa;
}

El operador -> utilizado en el código anterior:

pa->nombre

Es equivalente a:

(*pa).nombre

Estructuras dinámicas

Hasta la fecha hemos trabajado con estructuras estáticas. Estas se denominan así porque no cambian de tamaño a lo largo de la ejecución de un programa. Por contra las estructuras dinámicas si cambian de tamaño, lo cual les permite adaptarse a las necesidades de almacenamiento del programa en cada momento. Para crear estructuras dinámicas necesitamos usar mecanismos de asignación dinámica, además para acceder a las estructuras dinámicas necesitamos punteros.

Tipos de estructuras dinámicas:

  • Listas
  • Pilas
  • Colas
  • Árboles.

Asignación de memoria dinámica operador new y new[]

Para asignar memoria námica empleamos el operador new, que nos devuelve la dirección de la zona de memoria asignada.

#include <stdlib.h>
#include <stdio.h>
int main()
{
    char *c;
    c = new char;
    cout << "Introduca un caracter: ";
    cin >> *c;
    cout << *c;
    delete c;
}

Para la assignación de varias celdillas de memoria consecutivas (un array), se utiliza el operador new[].

#include <stdlib.h>
#include <stdio.h>
int main()
{
    char *c;
    c = new char[80];
    cout << "Introduca una cadena: ";
    cin >> c;
    cout << c;
    delete[] c;
}

Desasignación de memoria dinámica operador delete y delete[]

Para desasignar memoria dinámica empleamos el operador delete. Si se trata de un array asignado mediante new[], entonces empleamos delete[].

Listas enlazadas

Está formada por un conjunto de nodos enlazados en la que cada nodo contiene información del nodo y una referencia al siguiente elemento de la lista

   _______      _______       _______        _______
  |  Raiz |---->|  Inf  |     |  Inf  |     |  Inf  |
  |_______|     |_______|     |_______|     |_______|
                |  Sig  |     |  Sig  |     |  Sig  |
                |_______|---->|_______|---->|_______|----> NULL


Una lista enlazada contiene un número variable de nodos. Cuando se insertan o eliminan nuevos elementos se deben actualizar los enlaces Los nodos se definen como estructuras:

struct nodo {
    struct nombre_estructura  información;
    struct nodo *siguiente;
};

Nodo de una lista doblemente enlazada:

struct nodo {
    struct nombre_estructura  información;
    struct nodo *anterior;
    struct nodo *siguiente;
};


Los nodos se crean asignándoles memoria dinámica

nodo *n;
n = new nodo;


Inserción de elementos

1º. Asignamos memoria al nuevo nodo:

nuevo=new nodo;
   _______       _______
  | Nuevo |---->|  Inf  |
  |_______|     |_______|
                |  Sig  |
                |_______|

2º. Buscamos la posición en la que insertaremos el nodo:

    • Esta puede ser al principio, al final o en una posición intermedia. Vamos a suponer que se inserta al principio
   _______       _______       _______       _______
  |  Raiz |---->|  Inf  |     |  Inf  |     |  Inf  |
  |_______|     |_______|     |_______|     |_______|
   _______      |  Sig  |     |  Sig  |     |  Sig  |
  |NodoSig|---->|_______|---->|_______|---->|_______|----> NULL
  |_______|     


3º. Enlazamos el nuevo nodo con el siguiente:

nuevo->siguiente = nodoSig;
       _______       _______       _______       _______
      |  Raiz |---->|  Inf  |     |  Inf  |     |  Inf  |
      |_______|     |_______|     |_______|     |_______|
       _______      |  Sig  |     |  Sig  |     |  Sig  |
      |NodoSig|---->|_______|---->|_______|---->|_______|----> NULL
      |_______|          ^
                         |
 _______       _______   |
| Nuevo |---->|  Inf  |  |
|_______|     |_______|  |
              |  Sig  |  |
              |_______|__|


4º. Enlazamos el nodo anterior con el nuevo:

raiz = nuevo;
   _______       _______       _______       _______       _______
  |  Raiz |---->|  Inf  |     |  Inf  |     |  Inf  |     |  Inf  |
  |_______|     |_______|     |_______|     |_______|     |_______|
                |  Sig  |     |  Sig  |     |  Sig  |     |  Sig  |
                |_______|---->|_______|---->|_______|---->|_______|----> NULL

Ejemplo: Lista enlazada. Elementos insertados al inicio de la lista

struct nodo{
    int n; nodo *ps;
};
int main()
{
    int num; nodo *raiz=NULL,*nuevo=NULL;
    cout << "\nIntroduce un numero a insertar:"; cin >> num;
    while(num != 0)
    {
        // insertamos el nodo al principio
        nuevo=new nodo;
        nuevo->n = num;
        // Enlazamos con la lista
        nuevo->ps = raiz;
        raiz = nuevo;
        // Leemos el siguiente número
        cout << "\nIntroduce un numero a insertar:"; cin >> num;
    }
    // imprimir lista
    nuevo=raiz;
    while(nuevo!=NULL)
    {
        cout << nuevo->n << " ";
        nuevo = nuevo->ps;
    }
}

Ej: Modificamos el código anterior para insertar al final de la lista.

struct nodo{
    int n; nodo *ps;
};
int main()
{
    int num; nodo *raiz=NULL,*nuevo=NULL, *ultimo;
    cout << "\nIntroduce un numero a insertar:"; cin >> num;

    while(num != 0)
    {
        // insertamos el nodo
        nuevo=new nodo;
        nuevo->n = num;
        // Buscamos el último nodo
        if(raiz == NULL){
            nuevo->ps = NULL;
            raiz = nuevo;
        }else {
            ultimo = raiz;
            while(ultimo->ps != NULL){
                ultimo = ultimo->ps;
            }
            nuevo->ps = ultimo->ps;
            ultimo->ps = nuevo;
        }
        // Leemos el siguiente número
        cout << "\nIntroduce un numero a insertar:";
        cin >> num;
    }
    // imprimir lista
    nuevo=raiz;
    while(nuevo!=NULL)
    {
        cout << nuevo->n << " ";
        nuevo = nuevo->ps;
    }
}

Ej: Modificamos el código anterior para insertar elementos en orden.

struct nodo{
    int n; nodo *ps;
};
int main()
{
    int num; nodo *raiz=NULL,*nuevo=NULL, *anterior;
    cout << "\nIntroduce un numero a insertar:"; cin >> num;
    while(num != 0)
    {
        // insertamos el nodo
        nuevo=new nodo;
        nuevo->n = num;
        // Buscamos el nodo anterior
            if(raiz==NULL || raiz->n >= num){
                nuevo->ps = raiz;
                raiz = nuevo;
            }else {
                anterior = raiz;
                while(anterior->ps != NULL && anterior->ps->n < num){
                       anterior = anterior->ps;
                }
                nuevo->ps = anterior->ps;
                anterior->ps = nuevo;
            }
        // Leemos el siguiente número
        cout << "\nIntroduce un numero a insertar:";
        cin >> num;
    }
    // imprimir lista
    nuevo=raiz;
    while(nuevo!=NULL)
    {
        cout << nuevo->n << " ";
        nuevo = nuevo->ps;
    }
}

Ejemplo: Función que inserta un nodo en orden:

void inserta_en_lista(nodo **raiz, int n)
{
    nodo *nuevo, *ant=*raiz;
    // Primero creamos el nodo nuevo
    nuevo=new nodo;
    nuevo->numero=n;
    if(*raiz==NULL || ant->numero >= n) //Insertamos al principio
    {
        nuevo->ps = *raiz;
        *raiz = nuevo;
    }
    else //Buscamos posicion
    {
        while(ant->ps!=NULL && ant->ps->numero<n)
        {
            ant = ant->ps;
        }
        nuevo->ps = ant->ps;
        ant->ps = nuevo;
    }
}

Borrado de elementos en una lista enlazada

1º. Buscamos la posición del nodo a eliminar: Esta puede ser al principio, al final o en una posición intermedia. Vamos a suponer que se elimina el nodo que se encuentra al principio de la lista

pos = raiz;
   _______       _______       _______       _______
  |  Raiz |---->|  Inf  |     |  Inf  |     |  Inf  |
  |_______|     |_______|     |_______|     |_______|
   _______      |  ps   |     |  ps   |     |  ps   |
  |  pos  |---->|_______|---->|_______|---->|_______|----> NULL
  |_______|     


2º. Enlazamos el nodo anterior con el siguiente:

raiz = pos->ps;
             ______________
            |              |
   _______  |    _______   |   _______       _______
  |  Raiz |_|   |  Inf  |  |->|  Inf  |     |  Inf  |
  |_______|     |_______|     |_______|     |_______|
   _______      |  ps   |     |  ps   |     |  ps   |
  |  Nodo |---->|_______|---->|_______|---->|_______|----> NULL
  |_______|     


3º. Liberamos memoria del nodo a borrar:

delete pos;
   _______                     _______       _______
  |  Raiz |------------------>|  Inf  |     |  Inf  |
  |_______|                   |_______|     |_______|
                              |  ps   |     |  ps   |
                              |_______|---->|_______|----> NULL


Ejemplo: Función que elimina un nodo de una lista ordenada de números

void borra_en_lista(nodo **raiz, int n)
{
    nodo *pos=*raiz;
    nodo *ant=pos;
    if(*raiz!=NULL)
    {
        while(pos!=NULL && pos->numero<n)
        {
            ant=pos;
            pos=pos->ps;
        }
        if(pos!=NULL && pos->numero==n) // lo hemos encontrado
        {
            if(pos!=*raiz)
                ant->ps=pos->ps;
            else
                *raiz=pos->ps;
            delete pos;
        }
    }
}

Ejemplo de recorrido de una lista:

struct nodo{
    int n; nodo *ps;
};

void imprime_lista(nodo *pl)
{
    while(pl!=NULL)
    {
        cout << pl->numero;
        pl = pl->ps;
    }
    cout << "\nPulse una tecla para continuar";
    cin.get();
}

Tipos de lista

  • Lista simplemente enlazada.
   _______       _______       _______       _______
  |  Raiz |---->|  Inf  |     |  Inf  |     |  Inf  |
  |_______|     |_______|     |_______|     |_______|
                |  Sig  |     |  Sig  |     |  Sig  |
                |_______|---->|_______|---->|_______|----> NULL
  • Lista circular.
      _______       _______       _______       _______
     |  Raiz |---->|  Inf  |     |  Inf  |     |  Inf  |
     |_______|     |_______|     |_______|     |_______|
                   |  Sig  |     |  Sig  |     |  Sig  |
              ---->|_______|---->|_______|---->|_______|----|
              |                                             |
              |_____________________________________________|
  • Lista doblemente enlazada.
   _______       _______       _______       _______
  |  Raiz |---->|  Inf  |     |  Inf  |     |  Inf  |
  |_______|     |_______|     |_______|     |_______|
                |  Sig  |     |  Sig  |     |  Sig  |
                |_______|---->|_______|---->|_______|----> NULL
                |  Ant  |     |  Ant  |     |  Ant  |
     NULL <-----|_______|<----|_______|<----|_______|
  • Lista circular doblemente enlazada.
   _______       _______       _______       _______
  |  Raiz |---->|  Inf  |     |  Inf  |     |  Inf  |
  |_______|     |_______|     |_______|     |_______|
                |  Sig  |     |  Sig  |     |  Sig  |
          |---->|_______|---->|_______|---->|_______|----| NULL
          |     |  Ant  |     |  Ant  |     |  Ant  |    |
          |   |-|_______|<----|_______|<----|_______|<-| |
          |   |________________________________________| |
          |______________________________________________|

Pilas

Se pueden implementar con listas enlazadas. Se trata de una estructura LIFO (Last In First Out), en la que el último elemento insertado será el último en salir. Los elementos son introducidos y extraídos por un extremo de la lista. Dispone de dos operaciones:

  • Push (insertar elementos en la lista)
  • Pop (extraer elementos de la lista).

Para implmentar una pila mediante listas debemos definir un nodo:

struct nodo{
	int n; nodo *ste;
};

Operacion push

Inserción de un nuevo elemento en la pila.

void push(nodo **pila, int num) 
{
	nodo *nuevo;
 
	// nodo nuevo
	nuevo = new nodo;
	nuevo->n = num;
   
	// Insertamos el nuevo nodo
	nuevo->ste = *pila;
	*pila = nuevo;
}

Operación pop

Extracción de un elemento de la pila.

struct nodo{
	int n; nodo *ste;
};


int pop(nodo **pila) 
{
	nodo *nodopop;
	int num;
   
	nodopop = *pila;
	if(nodopop == NULL)
		num = -1; // Si pila vacía devolvemos -1
	else
	{
		*pila = nodopop->ste;
		num = nodopop->n; 
		delete nodopop;
	}
	return num;
}

Colas

Se pueden implementar con listas enlazadas.Se trata de una estructura FIFO (First In First Out), en la que el primer elemento insetado será el primero en salir.Los elementos son introducidos por un extremo y extraídos por el contrario. Dispone de dos operaciones:

  • insertar elementos en la cola
  • extraer elementos de la cola.

operación insertar

Para facilitar las operaciones se utilizan dos punteros, uno apunta al primer elemento y otro al último.

struct nodo{
	int n; nodo *ste;
};


void insertar(nodo **cola, int num)
{
	nodo *nuevo, *ultimo = *cola;
	nuevo = new nodo;
	nuevo->n = num;

        //Si la cola esta vacía, insertamos al principio
        if(ultimo == NULL)
        {
        	nuevo->ste = ultimo;
        	*cola = nuevo;
        }
        else // Insertamos por el final
        {
                while(ultimo->ste != NULL)
                        ultimo = ultimo->ste;
        	nuevo->ste = NULL;
                ultimo->ste = nuevo;
        }
}

Operación Extraer

struct nodo{
	int n; nodo *ste;
};

int extraer(nodo **cola)
{
	nodo *elemento;
	int num;

	elemento = *cola;
	if(elemento == NULL)
		num = -1; // Si cola vacía devolvemos -1
	else
	{
                // Localizamos el elemento a extraer que es el primero
		*cola = elemento->ste;
		num = elemento->n;
		delete elemento;
	}
	return num;
}

Ejercicios

  1. Crea un programa en el que se acceda a variables de diferente tipo mediante punteros. Solución.
  2. Crea un programa en el que se defina un array dinámico aleatorio, ordenalo y muestralo. El acceso al array se llevará a cabo mediante un puntero. Solución.
  3. Almacena en un array dinámico una lista de nombres y teléfonos. Ordénala y la guardas en un fichero. Solución.
  4. Crea un array dinámico en el que almacenarás el nombre y nota de 20 alumnos. Almacenalos en formato HTML.Solución.
  5. Lista enlazada. Inserta elementos por el inicio de la lista. Solución.
  6. Lista enlazada. Inserta elementos ordenadamente. Solución.
  7. Lista enlazada. Inserta elementos por el final de la lista.Solución.
  8. Lee un fichero de texto y construye una lista enlazada de palabras ordenadas alfabéticamente. Finalmente almacena la lista en un fichero HTML. Solución.
  9. Modifica el ejemplo anterior evitando palabras duplicadas. Debes almacenar el numero de apariciones de cada palabra.Solución.
  10. Lista enlazada. Se permitirá insertar elementos por el principio, por el final y de manera ordenada mediante el uso de funciones. Solución.
  11. Lista enlazada. Se permitirá insertar y eliminar elementos por el principio, por el final y de manera ordenada mediante el uso de funciones. Solución.
  12. Lee una lista de alumnos de uns clase (nombre y nota). Almacenalas en una lista enlazada ordenadamente. Calcula la nota media y escribe el la lista ordenada en otro fichero
  13. Agenda electrónica mediante una lista enlazada
  14. Crea un programa que analice una página web y extraiga los enlaces que continene.
  15. Crea un programa que permita jugar al tres en raya entre dos jugadores. El programa almacenará las jugadas mediante una lista enlazada.
  16. Crea un programa que lea las definiciones y soluciones de un crucigrama almacenado en un fichero. Se debe utilizar una lista enlazada para almacenar las definiciones.
  17. Crea un programa que lea una partida de ajedrez almacenada en un fichero de texto y la guarde en una lista enlazada.
  18. Crea un programa que implemente una pila mediante una lista enlazada.
  19. Crea un programa que implemente una cola mediante una lista enlazada.

Also on Fandom

Random wikia