Estructuras con Punteros

1. Operador "sizeof" con estructuras

Cuando se aplica el operador sizeof a una estructura, el tamaño obtenido nosiempre coincide con el tamaño de la suma de sus campos. 

Por ejemplo:

#include <iostream>
using namespace std;
struct A {int x; char a; int y; char b;};
struct B {int x; int y; char a; char b;};
int main(){
   cout << "Tamaño de int: " << sizeof(int) << endl;
   cout << "Tamaño de char: " << sizeof(char) << endl;
   cout << "Tamaño de estructura A: " << sizeof(A) << endl;
   cout << "Tamaño de estructura B: " << sizeof(B) << endl;
   cin.get();
   return 0;
}

El resultado, usando Anjuta , es el siguiente:Tamaño de int: 4Tamaño de char: 1Tamaño de estructura A: 16Tamaño de estructura B: 12Si hacemos las cuentas, en ambos casos el tamaño de la estructura deberíaser el mismo, es decir, 4+4+1+1=10 bytes. Sin embargo en el caso de laestructura A el tamaño es 16 y en el de la estructura B es 12, ¿por qué?La explicación es algo denominado alineación de bytes (byte-aling). Paramejorar el rendimiento del procesador no se accede a todas las posiciones dememoria. En el caso de microprocesadores de 32 bits (4 bytes), es mejor sisólo se accede a posiciones de memoria múltiplos de 4, y el compiladorintenta alinear las variables con esas posiciones.

En el caso de variables "int" es fácil, ya que ocupan 4 bytes, pero con lasvariables "char" no, ya que sólo ocupan 1.Cuando se accede a datos de menos de 4 bytes la alineación no es tanimportante. El rendimiento se ve afectado sobre todo cuando hay que leerdatos de cuatro bytes que no estén alineados.En el caso de la estructura A hemos intercalado campos "int" con "char", demodo que el campo "int" "y", se alinea a la siguiente posición múltiplo de 4,dejando 3 posiciones libres después del campo "a". Lo mismo pasa con elcampo "b"

En el caso de la estructura B hemos agrupado los campos de tipo "char" alfnal de la estructura, de modo que se aprovecha mejor el espacio, y sólo sedesperdician los dos bytes sobrantes después de "b".

2. Campos de Bit

Existe otro tipo de estructuras que consiste en empaquetar los campos de la estructura en el interior de enteros, usando bloques o conjuntos de bits paracada campo.

Por ejemplo, una variable char contiene ocho bits, de modo que dentro de ella podremos almacenar ocho campos de un bit, o cuatro de dos bits, o dosde tres y uno de dos, etc.

En una variable int de 16 bits podremos almacenar16 bits, etc.Debemos usar siempre valores de enteros sin signo, ya que el signo sealmacena en un bit del entero, el de mayor peso, y puede falsear los datos almacenados en la estructura.

Sintaxis:

struct [<nombre de la estructura>] {   unsigned <tipo_entero> <identifcador>:<núm_de_bits>;   } [<lista_variables>];

Hay algunas limitaciones, por ejemplo, un campo de bits no puede ocupar dos variables (miembros) distintos, todos sus bits tienen que estar en el mismo valor entero

Por ejemplo:

struct mapaBits {
unsigned char bit0:1;
unsigned char bit1:1;
unsigned char bit2:1;
unsigned char bit3:1;
unsigned char bit4:1;
unsigned char bit5:1;
unsigned char bit6:1;
unsigned char bit7:1;
};
struct mapaBits2 {
unsigned short int campo1:3;
unsigned short int campo2:4;
unsigned short int campo3:2;
unsigned short int campo4:1;
unsigned short int campo5:6;
};
struct mapaBits3 {
unsigned char campo1:5;
unsigned char campo2:5;
};

En el primer caso se divide un valor char sin signo en ocho campos de un bit cada uno:

En el segundo caso dividimos un valor entero sin signo de dieciséis bits en cinco campos de distintas longitudes:

Los valores del campo5 estarán limitados entre 0 y 63, que son los números que se pueden codificar con seis bits. Del mismo modo, el campo4 sólo puede valer 0 ó 1, etc.

En este ejemplo vemos que como no es posible empaquetar el campo2 dentro del mismo char que el campo1, se añade un segundo valor char, y se dejan sin usar los bits sobrantes.
También es posible combinar campos de bits con campos normales.

struct mapaBits2 {
   int numero;
   unsigned short int campo1:3;
   unsigned short int campo2:4;
   unsigned short int campo3:2;
   unsigned short int campo4:1;
   unsigned short int campo5:6;
   float n;
};

#include <iostream>
using namespace std;
struct mapaBits2 {
   unsigned short int campo1:3;
   unsigned short int campo2:4;
   unsigned short int campo3:2;
   unsigned short int campo4:1;
   unsigned short int campo5:6;
};
int main()
{
   mapaBits2 x;
   x.campo2 = 12;
   x.campo4 = 1;
   cout << x.campo2 << endl;
   cout << x.campo4 << endl;
   cin.get();
   return 0;
}

No es normal usar estas estructuras en programas, salvo cuando se relacionan con ciertos dispositivos físicos, por ejemplo, para configurar un puerto serie en MS-DOS se usa una estructura empaquetada en un unsigned char, que indica los bits de datos, de parada, la paridad, etc, es decir, todos los parámetros del puerto. En general, para programas que no requieran estas estructuras, es mejor usar estructuras normales, ya que son mucho más rápidas.

Otro motivo que puede decidirnos por estas estructuras es el ahorro de espacio, ya sea en disco o en memoria. Si conocemos los límites de los campos que queremos almacenar, y podemos empaquetarlos en estructuras de mapas de bits podemos ahorrar mucho espacio.

3. Instancias en forma dinámica.

El operador new, se usa en estructuras y permite como ya vimos solicitar dinámicamente en tiempo de ejecución un espacio en memoria.

Como dijimos anteriormente una estructura es como un tipo de datos.. es por eso que la sintaxis sería :

struct registro {int x; float y; bool a; float fecha[3]}; //Defino la estructura.
struct registro *p; //Declaro puntero a la plantilla de datos llamada registro.
int n; //cantidad de instancias.
cin>>n;
p=new struct registro[n]; // Solicito n instancias dinámicamente, ubicadas de manera contígua en memoria

//Ejemplo de nothrow
#include <iostream>    
using namespace std;
int main () 
{
cout << "Intentando solicitar un mega... ";
char* p = new (nothrow) char [1048576];//Pido 1Mega de datos tipo char.
if (!p)
{ // Puedo preguntar si el puntero es null (por que usé nothrow)
cout << "Falla!\n"; //Quiere decir que NO hay espacio
   }
else
{ //Si NO es nulo.. hay espacio!!
cout << "Existoso!\n";
>    delete[] p;
}
return 0;
}

4. Listas Simples

Listas Simples 

Existe varias aplicaciones derivadas de incorporar un puntero como miembro de una estructura.. en particular mucho mas cuando el puntero  apunta a una estructura del mismo tipo !! esto crea lo que se conocen como listas Enlazadas y las mismas pueden ser :Simples, Dobles , Circulares.. etc. 

Veamos el caso de Lista enlazada simple o simplemente enlazada.

Vemos que *pdato es un puntero que tiene el mismo tipo de la estructura, es por eso que CONOCE, la estructura y PUEDE apuntar a un miembro, como en este caso el puntero *pdato que contiene E6, y E6 es la dirección de la próxima instancia (2da). Para saber cuando termina el contenido del último miembro puntero contiene NULL, con esto sabemos que termina aquí la Lista.

Observación:

Ver que para recorrer la lista utilizando los punteros SOLO puedo hacerlo en UN SOLO SENTIDO ( en la imagen sería de izquierda a derecha) .

Veamos un ejemplo:

Código:

#include <iostream>
using namespace std;

struct datos{
    int Tel;
    int legajo;
    struct datos *pprox;
};

void cargar(datos *puntero);
void agregar(datos *puntero);
void eliminar(datos *&puntero);

int main(){
    datos *punterodato = new datos;  	//creo un puntero y solicito la 1er instancia (en main())
    cargar(punterodato);		//cargo la 1er instancia
    while(#condición#){			//agregar más instancias
        agregar(punterodato);		//siempre paso el puntero a la 1er instancia
    }
    eliminar(punterodato);
    return 0;
}

// cargo la ultima instancia 
void cargar(datos *puntero){
    cout<<"ingrese telefono"<<endl;
    cin>>puntero->Tel;		//cargo los datos
    cout<<"ingrese legajo"<<endl;
    cin>>puntero->legajo;
    puntero->pprox=NULL;		//la nueva instancia es la última
}

void agregar(datos *puntero){		//al pasar por valor la función crea una copia del puntero. No modifico el de main
    while(puntero->pprox!=0){		//me posiciono en la última instancia utilizando los enlaces
        puntero=puntero->pprox;
    }
    puntero->pprox=new datos; //solicito una nueva instancia 
                             // y de paso enlazo el puntero a la próxima instancia TODO en la misma línea !!
    cargar(puntero->pprox); //cargo la última instancia.
}

void eliminar(datos *&puntero){
    datos *pt2=puntero;
    while(puntero!=0){        //no es la última instancia
        pt2=puntero->pprox;
        delete puntero;
        puntero=pt2;
    }
}

5. Lista Simple, ejemplo básico.

6. Listas Dobles.

Listas Dobles.

Las listas enlazadas dobles incorporan UN PUNTERO MAS. Con dos punteros formado parte de la estructura un puntero se utiliza para apuntas a la próxima instancia ( como en la lista Enlazada Simple) y el orto para apuntar la instancia anterior.

Esto nos permite recorrer en ambas direcciones la lista, enlazada DOBLE en este caso.

Observación:

En los extremos se deberá indicar con NULL 

• el puntero que apuntan a la siguiente instancia en la última instancia
• el puntero que apunta a la instancia anterior en la primer instancia
• Se pueden  recorrer en los DOS sentidos!!

Código:

#include <iostream>
using namespace std;
struct datos  //Estructura Global
{
int Tel;
int legajo
struct datos *p_siguiente; //puntero a la proxima instancia
struct datos *p_anterior;// puntero a la instancia anterior.
};
void cargar(datos *);//Ver que al agrumento datos se declaró antes
void agregar(datos *);//Ver que al agrumento datos se declaró antes
int main()
{   
  datos  *p, *puntero_inicio= new datos; //creo un puntero temporal p y 
  //otro al inicio y solicito la 1er instancia en main()

  puntero_inicio->p_anterior=NULL;
  cargar(puntero_inicio); //cargo la 1er instancia
  //Cargo segunda instancia
  agregar(puntero_inicio); //siempre paso el puntero a la 1er instancia
  //Cargo tercer instancia
  agregar(puntero_inicio); //siempre paso el puntero a la 1er instancia
//Muestro la lista enlazada doble de tres instancias
  p=puntero_inicio; //inicializo puntero temporal
  bool primera=true;// variable de uso temporal
  do
     {
     if (primera)primera=false; //la primera vez no apunto a la proxima instancia
     else p=p->p_siguiente;//si no es la primera vez apunto a la proxima instancia

     cout<<p<<"-"<< p->legajo << "-" << p->Tel << "-" <<"siguiente: "
     << p->p_siguiente << "-" <<"anterior: "<< p->p_anterior << endl;
     }while (p->p_siguiente != 0);
  delete []puntero_inicio;
  return 0;
}


void cargar(datos *puntero)//ver que puntero es una COPIA de puntero_inicio
{ 
    cout << "ingrese telefono" << endl;
    cin >> puntero->Tel; //cargo los datos
    cout << "ingrese legajo" << endl;
    cin >> puntero->legajo;
    puntero->p_siguiente = NULL; 
  }


void agregar(datos *puntero)//ver que puntero es una COPIA de puntero_inicio
{ //al pasar por valor la función crea una copia del puntero. No modifico el de main
   while (puntero->p_siguiente != 0)
   { //me posiciono en la última instancia utilizando los enlaces
      puntero = puntero->p_siguiente;
   }
   puntero->p_siguiente = new datos; //solicito una nueva instancia 
   //y asigno la dirección en el puntero al prox de la última
   (puntero->p_siguiente)->p_anterior = puntero;// esta línea es importante!!
   cargar(puntero->p_siguiente);
}

Observación : 

En la línea :

(puntero->p_siguiente)->p_anterior = puntero;// esta línea es importante!!

Aprovecho para inicializar el puntero de anterior de la instancia siguiente,  antes de pasar a completar los datos de la instancia siguiente. Esto se puede hacer de otras formas, solo me pareció oportuno hacerlo ya que tengo almacenado el valor de la dirección anterior en ese momento.

La salida del código anterior es:

7. Listas Circulares.

Las listas circulares nos son otra cosa que un caso particular de una  la lista doble enlazada o doblemente enlazada.

En este tipo de lista los punteros en los extremos que antes ( Lista enlazada doble) que antes se inicializaban en NULL ahora se inicializan a las instancias de manera de logra que NO tenga fin.

• el puntero que apuntan a la siguiente instancia en la última instancia DEBE apuntar a la primera.
• el puntero que apunta a la instancia anterior en la primer instancia DEBE apuntar a la última instancia.

Veamos un ejemplo gŕaficamente.

Observación:

• La lista NO tiene FIN.
• Si perdemos el inicio no podemos Recorrerla.
• Se puede recorrer en AMBOS sentidos.

Consigna: Crear una lista Circular doblemente enlazada a partir de una Lista Enlazada Simple.

Código:

#include <iostream>
using namespace std;

struct datos{     //Estructura global
   int Tel;
   int legajo;
   struct datos *p_siguiente;   //puntero a la proxima instancia
   struct datos *p_anterior;   // puntero a la instancia anterior.
};

void cargar (datos *);
void agregar (datos *);

int main (){
   datos *puntero_inicio = new datos;   //creo un puntero y solicito la 1er instancia (en main())
   puntero_inicio->p_anterior=puntero_inicio;
   puntero_inicio->p_siguiente=puntero_inicio;
cargar (puntero_inicio); //cargo la 1er instancia
//Cargo segunda instancia
agregar (puntero_inicio); //siempre paso el puntero a la 1er instancia
//Cargo tercer instancia
agregar (puntero_inicio); //siempre paso el puntero a la 1er instancia
//Muestro la lista enlazada doble de tres instancias
datos *p = puntero_inicio;
bool primera = true;
do {
if (primera) {
primera = false;
cout << p << "-" << p->legajo << "-" << p->Tel << "-" << "siguiente: " << p->p_siguiente << "-" << "anterior: " << p->p_anterior << endl;
}
else {
p = p->p_siguiente;
cout << p << "-" << p->legajo << "-" << p->Tel << "-" << "siguiente: " << p->p_siguiente << "-" << "anterior: " << p->p_anterior << endl;
}
} while (p->p_siguiente != 0);
//Ahora hago la lista Circular.
p = puntero_inicio;
//Busco la última instancia donde el puntero era NULL
while (p->p_siguiente != 0) { //me posiciono en la última instancia utilizando los enlaces
p = p->p_siguiente;
}
// Cambio el puntero a anterior de la primer instancia para que apunte a la ultima instancia
puntero_inicio->p_anterior = p;
// Cambio el puntero a proximo de la ultima instancia a puntero_inicio
p->p_siguiente = puntero_inicio;
// para demostrar que es cirular uso un for, por que como es circular no terminaría..
cout << "Muestar de Lista Circular: " << endl;
p = puntero_inicio;
for (int i = 0; i < 10; i++) {
cout << p << "-" << p->legajo << "-" << p->Tel << "-" << "p_siguiente: " << p->p_siguiente<< "-" << "p_anterior: " << p->p_anterior << endl;
p = p->p_siguiente;
}
delete[]puntero_inicio;
return 0;
}

void cargar (datos * puntero){ //ver que puntero es una COPIA de punterodato
cout << "ingrese telefono" << endl;
cin >> puntero->Tel; //cargo los datos
cout << "ingrese legajo" << endl;
cin >> puntero->legajo;
puntero->p_siguiente = NULL;
}

void agregar (datos * puntero){ //ver que puntero es una COPIA de punterodato
//al pasar por valor la función crea una copia del puntero. No modifico el de main
while (puntero->p_siguiente != 0) { //me posiciono en la última instancia utilizando los enlaces
puntero = puntero->p_siguiente;
}
puntero->p_siguiente = new datos; //solicito una nueva instancia y asigno la dirección
//en el puntero al prox de la última
puntero->p_siguiente->p_anterior = puntero;
cargar (puntero->p_siguiente);
}

Observación : 

El código mostrado es el mismo que para Lista Doble Enlazada, solo se agregaron las líneas 26 a 35 que reemplan los punteros a NULL de la primer y utlima instancia para hacer una lista circular.

La salida del código anterior es:

8. Ejemplo 1

Vamos a mostrar una serie de ejemplos, en los cuales pordrán ver líneas comentadas.

Consigna:

Gestionar un lista enlazada simple. Desde un menú se invocan a distintas funciones. Una función da de alta UNA instancia por vez. . Otra función deben mostras todas las instancias. Otra función borrar de a una las instancias (la última) y otra función borrar todas las instancias juntas. Esto se logra mendiante el menú. Cada punto del menú invoca una función.

#include <iostream>
using namespace std;
struct lista{float x;lista *pt;};// estructura global.
//Prototipos.
void cargar(lista *&p);
void mostrar(lista *p);
void borrar_ultima(lista *p);
void borrar_todo(lista *&p);
char menu(void);


int main(int argc, char *argv[]) {
    lista *p_inicio=NULL;//inicializo a null un puntero a lista
    char opc;
    do{
    opc=menu();
    switch(opc)
    {
    case '1':
        cargar(p_inicio);
        break;
    case '2':
        mostrar(p_inicio);
        break;
    case '3':
        borrar_ultima(p_inicio);
        break;
    case '4':
        borrar_todo(p_inicio);
        break;
    case 'f':
    case 'F':
        cout<<"Finalizando...";
        break;
    default:
        cout<<"Opcion no valida..";
    }}while(!(opc=='f'|| opc=='F'));
 //   borra(p);   
	return 0;
}


void cargar(lista *&p)//recibo puntero como argumento por referecia
{
if (p==NULL) //p es null=> primer instancia.
    {
    p=new lista;// Creo la primer instancia.
    cout<<"Ingrese: ";cin>>p->x;
    p->pt=NULL; //Cierro la lista enlazada con null
    }
else // si p no es null=> no es la primer instancia.
    {
    lista *p_temp=p;// p_temp puntero local.
    //creo una copia del p, para no perder el inicio.
    //ver que como paso por referencia si cambio el valor de p se cambia el inicio.
    while((p_temp->pt)!=NULL)//mientras p->pt no sea null no llegue al final
        {
        p_temp=p_temp->pt;
        } //recorro hasta la ultima instancia.
    p_temp->pt=new lista;// solicito espacio para una nueva instancia.
                    //reemplazando null por la nueva instancia (enlazando)
    p_temp=p_temp->pt; //me traslado hasta la proxima instancia
    cout<<"Ingrese valor de instancia:";
    cin>>p_temp->x;
    p_temp->pt=NULL;//cierro la lista.
    /*Las lineas anteriores tambien se pueden escribir.
    p_temp->pt=new lista;
    cin<<p_temp->pt->x; //ser�a como cin<<(p_temp->pt)->x;
    p_temp->pt->pt=NULL;
    */

    }
}

void mostrar(lista *p)//p es una copia NO es por referencia
{   int contador=0;
    if (p==NULL)cout<<"Nada que mostrar..no hay nada cargado"<<endl;
    
    else
    {while(p!=NULL)
        {
        contador++;//Solo con fines est�ticos para ver la cantidad de instancias
        cout<<"Instancia "<<contador<<": "<<p->x<<endl;
        p=p->pt;//paso a la proxima instancia.
        }
    }
}

void borrar_ultima(lista *p)// ver que p es local una copia,pasaje por valor.
{//borrar la ultima instancia...
    lista *p_ant;//para salvar la direcci�n de una ante ultima instancia
    if (p==NULL)cout<<"Nada que borrar..no hay nada cargado"<<endl;
    else
    {
        while((p->pt)!=NULL){ 
            p_ant=p;//guardo el puntero de la ante �tlima
            p=p->pt;//paso a la siguiente
        }// avanzo hasta la �ltima instancia
        p_ant=p;//guardo el puntero de la ante �tlima
        delete p; //borro la �ltima instancia
                  //aqui no van [] por que es una instancia.
        p=p_ant;//me ubico en la ultima( la que seguia se elimino!)
        p->pt=NULL;//dejo como NULL la nueva ultima instancia.
    }
    
}


void borrar_todo(lista *&p)
{//Libera borrar Todas las instancias...
 //por facilidad borro de la primera a la ultima.
lista *p_prox;
p_prox=p; //guardo una copia local p_temp
    if (p==NULL)cout<<"Nada que borrar..no hay nada cargado"<<endl;
    else
    {while(p!=NULL)
    {   p_prox=p->pt;
        delete p; //aqui no van [] por que es una sola instancia.
        p=p_prox;
    }
    }
    
}

char menu()
{
char opc;
cout<<"Menu:"<<endl;
cout<<"1-Cargar una instancia"<<endl;
cout<<"2-Mostrar instancias"<<endl;
cout<<"3-Borrar ultima instancia"<<endl;
cout<<"4-Borrar TODAS las instancias"<<endl;
cout<<"f o F Finaliza"<<endl;
cout<<"Ingrese su eleccion:";
cin>>opc;
return opc;
}

Este código, tiene una falla la cual se observa cuando se tiene cargada una sola instancia y  se pretende usar la opcion 3 del menú, que borra la última instancia. Se deja al alumno buscar la solución.

9. Ejemplo 2

Consigna.

Cargar 3 instancias de una lista Enlazada simple sin pasar punteros por referencia. La primer instancia se solicita en main. 

Crear una función listar y otras que sean necesarias.

Observación:

Se puede observar que NO es suficiente una sola función carga para hacer la primer carga y luego las otras. Se pide al alumno pensar en este planteo. Es por eso que en la resolución de este ejercicio se crean 2 funciones. Una que carga la 1er Instancia y otra que carga las demás instancias. Veamos si podemos graficar la situación.

Al crea la primer instancia, usando new en main , el puntero a la primer instancia NO es NULL lógicamente, pero el miembro  puntero  p de la primer instancia es NULL, por lo tanto no se puede, o al menos yo no pude encontrar una manera elegante de utilizar una sola función carga para hacer TODAS las cargas si paso una copia del puntero a la primer instancia.  Así que se crean dos funciones cargas, una para la primer instancia y otra para las demás.

#include <iostream>
using namespace std;
struct datos{int x; struct datos *p;};
void carga(struct datos *p1);
void primer_carga(struct datos *p1);
void listar(struct datos *p_inicio);
    
int main(int argc, char *argv[]) {
    //voy a trabajar SIN pasar por Referencia.
    struct datos *p_inicio=new struct datos;//Primer instancia
    //apenas se crea la instancia.
    cout<<"Valores del entero en la estructura antes de Incicializar:"<<p_inicio->x<<endl;//ver que el contenido es NULL, 
    cout<<"Valores del puntero de la estructura antes de Incicializar:"<<p_inicio->p<<endl;//ver que el contenido es NULL
    //1er Carga.
	primer_carga(p_inicio);
    listar(p_inicio);
    carga(p_inicio);
    listar(p_inicio);
    carga(p_inicio);
    listar(p_inicio);
    return 0;
}

void primer_carga(struct datos *p1)
{   cout<<"Carga 1er Instancia..."<<endl;
    cout<<"Ingese entero:  ";cin>>p1->x;//cargo un valor
    //ver que p1->x es NULL de la pimer instancia
    // por eso NO necesito inicizar a NULL la 1er Instancia.
}

// carga agrega una instancia al final
void carga(struct datos *p1)
{  cout<<endl<<"Inicia Carga de otra instancia..."<<endl;
   // Si no es la primer instancia.
    while((p1->p)!=0)//me dezplazo hasta la última instancia
        {p1=p1->p;}//buscando la instancia que tiene puntero NULL
    struct datos *p_proxima=new struct datos; // creo una nueva instancia
    p1->p=p_proxima; // antes NULL, ahora apunta a la proxima instancia.
    p1=p_proxima;//me paro en la proxima instancia.
    cout<<"Ingese un entero: ";cin>>p1->x;//cargo un valor
    p1->p=NULL;//pongo NULL la última instancia.
}

void listar(struct datos *p1)
{   int contador=0;
    
    cout<<endl<<"-------Ingresando a listar-------"<<endl;
    while((p1!=0))
    {
    cout<<"Instancia: "<<contador<<endl;
    cout<<"valor de x:"<<p1->x<<endl;
    cout<<"valor de puntero:"<<p1->p<<endl;
    p1=p1->p;
    }
    cout<<"Ver que el ultimo puntero es NULL!";
    cout<<endl<<"--------Saliendo de Listar---------"<<endl;
}

10. Ejemplo integrador

//     EJEMPLO DE LISTA ENLAZADA SIMPLE      //
//     ================================      //
// Se agregan instancias de a una dinámicamente.
// Se eliminan de a una.
// Ing. Germán Andrés Xander 2018.

#include<iostream>
using namespace std;

struct data{
    int orden;
    struct data *pprox;
};

void agregar_final(data *&pt);
void agregar_principio(data *&pt);
void listar(data *pt);
void eliminar_final(data *&pt)
void eliminar_principio(data *&pt);

int main() {
    char opcion;
    data *lista=NULL;            //creo el puntero en main()
    do{
        cout<<"\t a para agregar al final"<<endl
            <<"\t A para agregar al principio"<<endl
            <<"\t l para listar"<<endl
            <<"\t e para eliminar del final"<<endl
            <<"\t E para eliminar del principio"<<endl;
        cin>>opcion;
        switch(opcion){
            case 'a':
                agregar_final(lista);
                break;
            case 'A':
                agregar_principio(lista);
                break;
            case 'l':
                listar(lista);
                break;
            case 'e':
                eliminar_final(lista);
                break;
            case 'E':
                eliminar_principio(lista);
                break;
        }
    }while(opcion!='s');
    return 0;
}

void agregar_final(data *&pt){            //paso por referencia para poder modificar "a dónde apunta"
    if(!pt){                    //la primer vez el puntero es NULL y evalua por true.
                                //"...the null pointer is implicitly converted into boolean false
                                //while non-null pointers are converted into true..."
        pt=new data;            //para la primer instancia debo modificar "a dónde apunta" el puntero original (lista)
        cout<<"ingrese orden"<<endl;
        cin>>pt->orden;
        pt->pprox=NULL;
    }else{                        // para las instancia posteriores debo trabajar sobre una copia del puntero
        data *pt2=pt;            // para no perder la dirección de la 1er instancia
        while(pt2->pprox!=0){        //me posiciono en la última instancia
            pt2=pt2->pprox;
        }
        pt2->pprox=new data;        //solicito una nueva instancia y asigno la dirección en el puntero al prox de la última
        cout<<"ingrese orden"<<endl;
        cin>>pt2->pprox->orden;
        pt2->pprox->pprox=NULL;
    }
}

void agregar_principio(data *&pt){            //paso por referencia para poder modificar "a dónde apunta"
    if(!pt){                    //la primer vez el puntero es NULL y evalua por false.
                                //"...the null pointer is implicitly converted into boolean false
                                //while non-null pointers are converted into true..."
        pt=new data;            //para la primer instancia debo modificar "a dónde apunta" el puntero original (lista)
        cout<<"ingrese orden"<<endl;
        cin>>pt->orden;
        pt->pprox=NULL;
    }else{
        data *pt2=pt;            // para no perder la dirección de la, hasta ahora, 1er instancia
        pt=new data;            //solicito una nueva instancia y asigno la dirección al puntero original
        cout<<"ingrese orden"<<endl;
        cin>>pt->orden;
        pt->pprox=pt2;            // apunto a la antigua 1ra instancia
    }
}

void listar(data *pt){  //como no pasa por referencia no se alterar el original
    while(pt!=0){
        cout<<"orden: "<<pt->orden<<"\t dirección al próximo: "<<pt->pprox<<endl;
        pt=pt->pprox;
    }
    cout<<endl<<endl;
}

void eliminar_final(data *&pt){
    data *pt2=pt,*pt3=pt;
    if(!pt){
        cout<<"no hay instancias"<<endl;
    }else{
        while(pt2->pprox!=0){        //me posiciono en la última instancia
            pt3=pt2;
            pt2=pt2->pprox;
        }
        if(pt2==pt3){             //nunca entro al while anterior. es la última
            delete pt;            //libero la memoria original
            pt=NULL;              //para saber que ya no apunta a memoria mía
            cout<<"ya no quedan instancias"<<endl<<endl;
        }else{
            delete pt2;
            pt3->pprox=NULL;
        }
    }
}

void eliminar_principio(data *&pt){
    data *pt2=pt;
    if(!pt){
        cout<<"no hay instancias"<<endl;
    }else{
        if(pt->pprox!=0){        //no es la última instancia
            pt2=pt->pprox;
            delete pt;
            pt=pt2;
        }else{
            delete pt;            //libero la memoria original
            pt=NULL;            //para saber que ya no apunta a memoria mía
            cout<<"ya no quedan instancias"<<endl<<endl;
        }
    }
}

11. Ejercicio 1

Consigna:

Gestionar un lista enlazada simple con un menú. Se debe dar de alta de a N instancias por vez. Se agregan al final de la lista. N es variable y se ingresa por teclado. La lista está formada por instancias de estructuras que contiene un miembro entero y un char[10]. Implementar Funciones que:

• agregar N instancias
• muestre todas las instancias
• borre la última instancias
• otra que borre todas las instancias de la lista.
  

11.1. ejemplo de solución

//  Ing. Germán Andrés Xander 2022.  //

#include<iostream>
using namespace std;
 
struct datos{
    int orden;
    char texto[10];
    struct datos *pprox;
};
 
void agregar(datos *&pt);
void agregar_final(datos *&pt);
void mostrar(datos *pt);
void eliminar_una(datos *&pt);
void eliminar_todas(datos *&pt);
 
int main() {
    char opcion;
    datos *lista=NULL;            //creo el puntero en main()
    do{
        cout<<"\t         Menu"<<endl
            <<"\t a para agregar instancias"<<endl
            <<"\t m para mostrar"<<endl
            <<"\t e para eliminar una instancia"<<endl
            <<"\t E para eliminar todas las instancias"<<endl
            <<"\t s salir"<<endl;
        cin>>opcion;
        switch(opcion){
            case 'a':
                agregar(lista);
                break;
            case 'm':
                mostrar(lista);
                break;
            case 'e':
                eliminar_una(lista);
                break;
            case 'E':
                eliminar_todas(lista);
                break;
        }
    }while(opcion!='s');
    return 0;
}
 
void agregar(datos *&pt){            //paso por referencia para poder modificar "a dónde apunta"
    int instancias;
    cout<<"ingrese cantidad de instancias a agregar"<<endl;
    cin>>instancias;
    cout<<endl;
    for (int i=0; i<instancias; i++){
        agregar_final(pt);
    }
}

void agregar_final(datos *&pt){            //paso por referencia para poder modificar "a dónde apunta"
    if(!pt){                    //la primer vez el puntero es NULL y evalua por true.
                                //"...the null pointer is implicitly converted into boolean false
                                //while non-null pointers are converted into true..."
        pt=new datos;            //para la primer instancia debo modificar "a dónde apunta" el puntero original (lista)
        cout<<"ingrese orden"<<endl;
        cin>>pt->orden;
        cout<<"ingrese texto"<<endl;
        cin>>pt->texto;
        pt->pprox=NULL;
    }else{                        // para las instancia posteriores debo trabajar sobre una copia del puntero
        datos *pt2=pt;            // para no perder la dirección de la 1er instancia
        while(pt2->pprox!=0){        //me posiciono en la última instancia
            pt2=pt2->pprox;
        }
        pt2->pprox=new datos;        //solicito una nueva instancia y asigno la dirección en el puntero al prox de la última
        cout<<"ingrese orden"<<endl;
        cin>>pt2->pprox->orden;
        cout<<"ingrese texto"<<endl;
        cin>>pt2->pprox->texto;
        pt2->pprox->pprox=NULL;
    }
    cout<<endl;
}

void mostrar(datos *pt){  //como no pasa por referencia no se alterar el original
    while(pt!=0){
        cout<<"orden: "<<pt->orden<<"\t texto: "<<pt->texto<<"\t dirección al próximo: "<<pt->pprox<<endl;
        pt=pt->pprox;
    }
    cout<<endl<<endl;
}
 
void eliminar_una(datos *&pt){
    datos *pt2=pt,*pt3=pt;
    if(!pt){
        cout<<"no hay instancias"<<endl;
    }else{
        while(pt2->pprox!=0){        //me posiciono en la última instancia
            pt3=pt2;
            pt2=pt2->pprox;
        }
        if(pt2==pt3){             //nunca entro al while anterior. es la última
            delete pt;            //libero la memoria original
            pt=NULL;              //para saber que ya no apunta a memoria mía
            cout<<"ya no quedan instancias"<<endl<<endl;
        }else{
            delete pt2;
            pt3->pprox=NULL;
        }
    }
}
 
void eliminar_todas(datos *&pt){
    while(pt){
        eliminar_una(pt);
    }
}

12. Ejercicio 2

Consigna

12.1. ejemplo de solución

//  Ing. Germán Andrés Xander 2022  //

#include<iostream>
using namespace std;
 
struct datos{
    int orden;
    char texto[10];
    struct datos *pprox;
};
 
void agregar_final(datos *&pt);
void mostrar(datos *pt);
 
int main() {
    char opcion;
    datos *lista=NULL;            //creo el puntero en main()
    do{
        cout<<"\t         Menu"<<endl
            <<"\t a para agregar instancias"<<endl
            <<"\t m para mostrar"<<endl
            <<"\t s salir"<<endl;
        cin>>opcion;
        switch(opcion){
            case 'a':
                agregar_final(lista);
                break;
            case 'm':
                mostrar(lista);
                break;
        }
    }while(opcion!='s');
    return 0;
}
 
void agregar_final(datos *&pt){
    if(!pt){
        pt=new datos;
        cout<<"ingrese orden"<<endl;
        cin>>pt->orden;
        cout<<"ingrese texto"<<endl;
        cin>>pt->texto;
        pt->pprox=pt;    // para que sea lista circular el puntero al próximo
                        // de la última instancia debe apuntar a la primera
    }else{
        datos *pt2=pt;
        while(pt2->pprox!=pt){
            pt2=pt2->pprox;
        }
        pt2->pprox=new datos;
        cout<<"ingrese orden"<<endl;
        cin>>pt2->pprox->orden;
        cout<<"ingrese texto"<<endl;
        cin>>pt2->pprox->texto;
        pt2->pprox->pprox=pt;
    }
    cout<<endl;
}

void mostrar(datos *pt){  //como no pasa por referencia no se alterar el original
    cout<<endl<<"\tpresione v para volver"<<endl<<endl;
    cin.ignore();
    do{
        cout<<"orden: "<<pt->orden<<"\t texto: "<<pt->texto;
        pt=pt->pprox;
    }while(cin.get()!='v');
    cout<<endl<<endl;
}

13. Ejercicio 3

Crear una lista enlazada doble a base de una estructura con un float y un char[10]

menú: