Índex
 
Capítol 12 Exercicis
Capítol 12

Estructures de dades

  1. Les piles
    1. Resolució de la pila amb una matriu.
    2. Resolució de la pila amb estructures dinàmiques de dades.
  2. Les cues.
    1. Solució del problema cua amb un vector
    2. Solució del problema cua amb estructures dinàmiques de dades
  3. Llistes unidireccionals
  4. Exercicis

12.1. Les piles

Una pila és una estructura de dades que simula una situació real molt comú. Una pila de plats o una pila de cartes són els exemples més comuns.

Una  pila és una estructura de dades (Objecte en la terminologia de OOP) que es composa d'elements del mateix tipus i podem dir que funciona  de la següent manera:

  1. Tenen una funció que inicialitza la pila.
  2. Tenen una funció que ens indica si la pila està buida.
  3. Tenen una funció que permet afegir elements a la pila. En una pila només es pot afegir un element al cim de la pila.
  4. Tenen una funció que ens retorna l'element que està al cim de la pila i que el treu de la pila.

 

12.1.1. Resolució de la pila amb una matriu.

Farem una pila de nombres enters.


Tipus de dades
En primer lloc definim un nou tipus de dades que anomenarem PilaEnters. 		 typedef struct PilaEnters
{
   int PunterACim;
   int Element[MAX];
}; 
La funció InicialitzaPila.
Segons veiem en la figura si la pila no està buida, el PunterACim està apuntant a l'últim element de la pila. Prendrem el conveni de que la pila està buida se el PunterACim té el valor -1, es adir que no apunta a cap element del vector. 		 void InicialitzaPila(PilaEnters * Pila)
{
   Pila->PunterACim=-1;
} 
La funció EsBuida
Retorna CERT si la pila està buida (PunterACim és -1) i FALS si la pila conté elements (PunterACim es diferent de -1) 		 Boolean EsBuida(PilaEnters * Pila)
{
   return (Pila->PunterACim) == -1;
} 
La funció InsereixElement
Aquesta funció comprova si el vector està ple (PunterACim<MAX) i en cas que hi hagi elements buits incrementa en ú el PunterACim i posa en el nou Cim la nova dada. 

Aquesta funció podria tornar CERT en cas que hagués tingut èxit en la inserció i FALS en cas contrari.

 

 void InsereixElement(int Num, PilaEnters * Pila)
{
   if (Pila->PunterACim+1<MAX)
   {
       Pila->PunterACim++;
       Pila->Element[Pila->PunterACim]=Num;
   }
   else printf("La pila està plena\n");
} 
La funció ExtreuElement
Primer comprova si la pila està buida i en cas que no l'estigui decrementa el PunterACim i ens torna la dada del cim anterior. Si està buida ens torna NULL. 		 int ExtreuElement(PilaEnters *Pila)
{
   if (! EsBuida(Pila))
   {
       Pila->PunterACim--;
       return Pila->Element[Pila->PunterACim + 1];
   }
   else return NULL;
} 
Queda per escriure la funció main que fa ús del tipus de dades PilaEnters i de les seves funcions.  #include <stdio.h>
#include <conio.h>

#define MAX 10

#define CERT 1
#define FALS 0

typedef int Boolean;

void InicialitzaPila(PilaEnters * Pila);
Boolean EsBuida(PilaEnters * Pila);
void InsereixElement(int Num, PilaEnters * Pila);
int ExtreuElement(PilaEnters *Pila);

main()
{
   clrscr();
   int i;
   PilaEnters Numeros;
   InicialitzaPila(&Numeros);
   printf("Números est… buida: %d\n", EsBuida(&Numeros));
   for(i=0;i<11;i++)
      InsereixElement(10*i,&Numeros);
   for(i=0;i<11;i++)
      printf("Element %d: %d\n",i,ExtreuElement(&Numeros));
   return 0;
} 

12.1.2. Resolució de la pila amb estructures dinàmiques de dades.

Aquest mètode per a la resolució del problema Pila és molt més natural que l'anterior del vector.

Ara són dos el tipus de dades que es defineixen: Un és l'element de la pila i l'altre és la pila mateixa.

Element de pila és una estructura que es composa de dos camps, el camp de dades i el camp de punter a element de la pila per poder enllaçar aquest element amb el següent element de la pila. Fem notar que el camp de dades pot ser tan simple com un nombre enter o tan complex com una estructura de dades.

El tipus de dades Pila és un punter a un element de la pila que és l'element que està en el cim de la pila.
Tipus de dades
Es defineixen els dos tipus mencionats abans, ElementPilaEnters i PilaEnters.		 typedef struct ElementPilaEnters
{
    int Dada;
    ElementPilaEnters * PunterASeguent;
};

typedef struct PilaEnters
{
     ElementPilaEnters * PunterACim;
};
La funció InicialitzaPila
En aquesta pila iniciar la pila és fer que el cim de la pila sigui NULL. Es a dir que farem que el punter a cim apunti a NULL.		 void InicialitzaPila(PilaEnters * Pila)
{
     Pila->PunterACim=NULL;
} 
La funció EsBuida
La pila estarà buida si el punter a cim apunta a NULL. Per tant la funció retorna CERT o FALS segons el cas.		 int EsBuida(PilaEnters * Pila)
{
     return !(Pila->PunterACim);
}
La funció InsereixElement
Aquesta funció fa reserva d'una zona de memòria (un nou element) per tal de hi posar les dades amb les instruccions:
  • ElementPilaEnters * Element;
  • Element = new ElementPilaEnters;
En cas d'èxit fa l'assignació de dades i fa els moviments de punters següents:
  • El punter a següent del nou element apunta al mateix lloc que el punter a cim.
  • El punter a cim apunta al nou element.
Fem notar que en el moment d'inserir un nou element és el moment on fem la reserva de memòria per tal d'allotjar les dades. D'aquesta manera es fa reserva dinàmica de memòria, en temps d'execució i no en temps de compilació. La pila pot créixer tant com quantitat de memòria disposem.		 Boolean InsereixElement(int Num, PilaEnters * Pila)
{
    ElementPilaEnters * Element;
    Element = new ElementPilaEnters;
    if (Element)
    {
           Element->Dada = Num;
           Element->PunterASeguent=Pila->PunterACim;
           Pila->PunterACim = Element;
           return CERT;
    }
    else return FALS;
}
La funció TornaElement
Aquesta funció ens torna les dades del cim de la pila si la pila no està buida. 		 int TornaElement(PilaEnters *Pila)
{
     if (! EsBuida(Pila))
          return Pila->PunterACim->Dada;
     else
          return NULL;
} 
La funció ExtreuElement
Aquesta funció esborra l'element que està al cim de la pila si no està buida.
  • Primer fa que un punter, anomenat provisional apunti a l'element que està al cim de la pila. 
  • Després fa que el punter al cim apunti a l'element següent.
  • En darrer lloc es allibera la memòria del que era l'element que estava al cim i que ara està apuntat pel punter provisional.
 void ExtreuElement(PilaEnters *Pila)
{
     ElementPilaEnters * Provisional;
     if (! EsBuida(Pila))
     {
          Provisional = Pila->PunterACim;
          Pila->PunterACim = Provisional->PunterASeguent;
          delete Provisional;
     }
}
Queda fer la funció principal en la que es declara una pila anomenada Numeros i en la que inserim els elements 5,7,9 i 11.

Després es fa ús d'aquestes dades i s'eliminen de la pila.

 #include <stdio.h>
#include <conio.h> 

void InicialitzaPila(PilaEnters * Pila);
int EsBuida(PilaEnters * Pila);
void InsereixElement(int Num, PilaEnters * Pila);
int  TornaElement(PilaEnters *Pila);
void ExtreuElement(PilaEnters *Pila);

main()
{
     clrscr();
     int i;

     PilaEnters Numeros;
     InicialitzaPila(&Numeros);
     printf("Números està buida: %d\n", EsBuida(&Numeros));

     InsereixElement(5,&Numeros);
     InsereixElement(7,&Numeros);
     InsereixElement(9,&Numeros);
     InsereixElement(11,&Numeros);

     printf("Element %d\n",TornaElement(&Numeros));
     ExtreuElement(&Numeros);
     printf("Element %d\n",TornaElement(&Numeros));
     ExtreuElement(&Numeros);
     printf("Element %d\n",TornaElement(&Numeros));
     ExtreuElement(&Numeros);
     printf("Element %d\n",TornaElement(&Numeros));
     ExtreuElement(&Numeros);

     printf("Numeros est'a buida: %d\n", EsBuida(&Numeros));

     return 0;
}

12.2. Les cues.

Són altres estructures de dades semblants a les piles, que també simulen una situació real com son les cues de persones. En aquestes cues les dades s'insereixen al final de la cua i surten pel principi.

Una  cua és una estructura de dades (Objecte en la terminologia de OOP) que es composa d'elements del mateix tipus i podem dir que funciona  de la següent manera:

    1. Tenen una funció que inicialitza la cua.
    2. Tenen una funció que ens indica si la cua està buida.
    3. Tenen una funció que permet afegir elements a la cua. En una cua només es pot afegir un element al final de la cua.
    4. Tenen una funció que ens retorna l'element que està al principi de la cua.
    5. Tenen una funció que extreu l'element que està al principi de la cua.

12.2.1 Solució del problema cua amb un vector

Farem una cua de nombres enters com la de la figura.
Com veiem en la figura aquesta cua ja ha tingut vuit inserccions d'elements i també han sortit tres elements.


Tipus de dades
En primer lloc definim un nou tipus de dades que anomenarem CuaEnters.
Farem que el punter a principi apunti al primer element de la cua i que el punter a final apunti a l'element següent a l'últim.		 typedef struct CuaEnters
{
     int PunterAPrincipi;
     int PunterAFinal;
     int Element[MAX];
};
La funció InicialitzaCua.
La cua estarà inicialitzada quan el punter a principi i el punter a final apuntin tots dos a la posició 0 del vector d'elements. 		 void InicialitzaCua(CuaEnters * Cua)
{
     Cua->PunterAPrincipi=0;
     Cua->PunterAFinal=0;
}
La funció EsBuida
Segons el conveni utilitzat per als punters la cua estarà buida quan els dos punters apuntin al mateix lloc.		 Boolean EsBuida(CuaEnters * Cua)
{
     return Cua->PunterAPrincipi == Cua->PunterAFinal;
}
La funció InsereixElement
Aquesta funció comprova si el vector està ple (Cua->PunterAFinal+1<MAX) i en cas que hi hagi elements buits i fa la inserció del valor al final de la cua i incrementa el PunterAFinal. 

Aquesta funció podria tornar CERT en cas que hagués tingut èxit en la inserció i FALS en cas contrari.

 void InsereixElement(int Num, CuaEnters * Cua)
{
     if (Cua->PunterAFinal+1<MAX)
     {
          Cua->Element[Cua->PunterAFinal]=Num;
          Cua->PunterAFinal++;
     }
     else printf("La pila està plena\n");
}
La funció PrimerElement
Primer comprova si la cua està buida i en cas que no l'estigui torna les dades corresponents al primer element de la cua, si no torna un  NULL. 		 int PrimerElement(CuaEnters *Cua)
{
     if (! EsBuida(Cua))
         return Cua->Element[Cua->PunterAPrincipi];
     else
     {
          printf("La cua està buida\n");
          return NULL;
     }
}
La funció TreuPrimer
Per a treure un element aquesta funció incrementa en 1 el punter a principi cas que la cua no estigui buida.		 void TreuPrimer(CuaEnters *Cua)
{
     if (! EsBuida(Cua)) Cua->PunterAPrincipi++;
     else printf("No hi ha més elements\n");
}
Queda per escriure la funció main que fa ús del tipus de dades VuaEnters i de les seves funcions.   #include <stdio.h>
#include <conio.h>

#define MAX 100

#define CIERTO 0
#define FALSO 1

typedef int Boolean;

void InicialitzaCua(CuaEnters * Cua);
Boolean EsBuida(CuaEnters * Cua);
void InsereixElement(int Num, CuaEnters * Cua);
int PrimerElement(CuaEnters *Cua);
void TreuPrimer(CuaEnters *Cua);

main()
{
     clrscr();
     int i;

     CuaEnters Numeros;
     InicialitzaCua(&Numeros);
     printf("Números està buida: %d\n", EsBuida(&Numeros));
     for(i=0;i<11;i++) InsereixElement(10*i,&Numeros);
     for(i=0;i<11;i++)
     {
          printf("Element %d: %d\n",i,PrimerElement(&Numeros));
          TreuPrimer(&Numeros);
     }

     return 0;
}

12.2.2 Solució del problema cua amb estructures dinàmiques de dades

També, i com en el cas de les piles, aquesta solució és molt més natural que la solució amb un vector.

En aquest cas també veurem que la reserva de memòria per a les dades es fa en el moment d'execució i per tant la cua pot créixer tant com la mida de memòria disponible.

Tal i com veiem a la figura es necessiten dos nous tipus de dades que són el tipus element de cua i la cua mateixa. En la figura veiem que en el cas d'una pila de nombres enters les dades dels elements són nombres enters. Però aquí podem posar qualsevol tipus de dades.

Tipus de dades
En primer lloc definim dos nous tipus de dades: 
 
  1. Definim el tipus ElementCuaEnters que té dos camps, el camp de dades i el punter al següent element.
  2. L'altre tipus és el de CuaEnters que en realitat té nomès dos camps, els punters al primer element de la cua i el punter a l'últim element.
 typedef struct ElementCuaEnters
{
     int Dada;
     ElementCuaEnters * PunterASeguent;
};

typedef struct CuaEnters
{
     ElementCuaEnters * PunterAPrincipi;
     ElementCuaEnters * PunterAFinal;
};
La funció InicialitzaCua.
La cua estarà inicialitzada quan el punter a principi i el punter a final apuntin tots dos a NULL. 		 void InicialitzaCua(CuaEnters * Cua)
{
     Cua->PunterAPrincipi=NULL;
     Cua->PunterAFinal=NULL;
}
La funció EsBuida
La cua estarà buida quan el punter a principi apunti a NULL.		 Boolean EsBuida(CuaEnters * Cua)
{
     return  !(Cua->PunterAPrincipi);
}
La funció InsereixElement
Aquesta funció fa una reserva de memòria per a la nova dada creant un nou element.

Si té èxit posa les dades en el nou element i fa que el punter a següent sigui NULL ja que no hi haurà element següent.

Després actua segons l'estat de la cua:

  • Si la cola està buida fa que el punter a principi apunti al nou element.
  • Si no fa que el punter del darrer element de la cua apunti al nou element.
En qualsevol cas el punter a final ha de apuntar al nou element.		 void InsereixElement(int Num, CuaEnters * Cua)
{

     ElementCuaEnters * Element;
     Element = new ElementCuaEnters;
     if (Element)
     {
          Element->Dada = Num;
          Element->PunterASeguent=NULL;

          if (EsBuida(Cua)) Cua->PunterAPrincipi=Element;
          else Cua->PunterAFinal->PunterASeguent=Element;
          Cua->PunterAFinal=Element;
     }
}
La funció PrimerElement
Torna les dades corresponents al primer element de la cua. Si no hi ha elements torna un  NULL. 		 int PrimerElement(CuaEnters *Cua)
{
     return Cua->PunterAPrincipi->Dada;
}
La funció TreuPrimer
Aquesta funció comprova si la cua està buida. En cas que no estigui fa les següents operacions:
  • Fa que un punter provisional apunti al primer element.
  • Fa que els punters a principi apunti a l'element següent al primer element o a NULL si no existeix.
  • Allibera la memòria del punter provisional
  • Si el punter a principi apunta a NULL fa que el punter a final també ho faci.
 void TreuPrimer(CuaEnters *Cua)
{
     if (!(EsBuida(Cua)))
     {
          ElementCuaEnters * PunterProvisional;
          PunterProvisional = Cua->PunterAPrincipi;
          Cua->PunterAPrincipi = Cua->PunterAPrincipi->PunterASeguent;
          delete PunterProvisional;
          if (! Cua->PunterAPrincipi) Cua->PunterAFinal=NULL;
     }
}
Queda per escriure la funció main que fa ús dels nous tipus de dades de les seves funcions.   #include <stdio.h>
#include <conio.h>

#define CIERTO 0
#define FALSO 1

typedef int Boolean;

void InicialitzaCua(CuaEnters * Cua);
Boolean EsBuida(CuaEnters * Cua);
void InsereixElement(int Num, CuaEnters * Cua);
int PrimerElement(CuaEnters *Cua);
void TreuPrimer(CuaEnters *Cua);

main()
{
 clrscr();
 int i;

 CuaEnters Numeros;
 InicialitzaCua(&Numeros);
 printf("Numeros est… buida: %d\n", EsBuida(&Numeros));

 InsereixElement(15,&Numeros);
 InsereixElement(25,&Numeros);
 InsereixElement(35,&Numeros);
 InsereixElement(45,&Numeros);

 printf("Primer element: %d\n",PrimerElement(&Numeros));
 TreuPrimer(&Numeros);
 printf("Primer element: %d\n",PrimerElement(&Numeros));
 TreuPrimer(&Numeros);
 printf("Primer element: %d\n",PrimerElement(&Numeros));
 TreuPrimer(&Numeros);
 printf("Primer element: %d\n",PrimerElement(&Numeros));
 TreuPrimer(&Numeros);

  return 0;
}

12.3. Llistes unidireccionals

Són piles a les que afegim algunes funcions noves. Entre altres afegirem les funcions següents:

Recorregut, Busca, InsereixDespres, InsereixAbans, EsborraElement, EsborraSeguent, EsborraLlista

Totes aquestes funcions ens permetran també fer llistes ordenades.

A la figura veiem una llista que es diu Classe i que té quatre registres. El programa que crea aquesta llista és el següent:
Les estructures per a aquesta llista són:
  1. RegistreAgenda que té els quatre camps de dades i el camp de tipus punter al registre següent.
  2. L'estructura LlistaAgenda que només té un camp de tipus punter al primer element de la llista que a l'exercici de piles hem anomenat Cim.
 typedef struct RegistreAgenda
{
    char nom[45];
    char direccio[36];
    char telefon[15];
    char email[40];
    RegistreAgenda * PunterASeguent;
};

typedef struct LlistaAgenda
{
     RegistreAgenda * PunterAPrimer;
};
La funció InicialitzaLlista
Aquesta funció inicialitza la llista. Només ha de fer-se ús després de declarar una llista nova. Heu de pensar que, si una llista ja té registres aquesta funció no allibera la memòria que ocupen aquest elements i serà memòria perduda.		 void InicialitzaLlista(LlistaAgenda * Llista)
{
      Llista->PunterAPrimer=NULL;
}
La funció EsBuida
Aquest funció torna Cert si el punter al primer element apunta a NULL i fals en cas contrari.		 int EsBuida(LlistaAgenda * Llista)
{
      return !(Llista->PunterAPrimer);
}
La funció InsereixElement
Aquesta funció insereix un element (registre) com a primer element de la llista. Aquesta funció rep un punter a un element i el punter a la llista. Torna Cert cas que tingui èxit i pugui inserir l'element i fals en cas contrari.		 Boolean InsereixElement(RegistreAgenda * Reg, LlistaAgenda * Llista)
{
     RegistreAgenda * Element;
     Element = new RegistreAgenda;
     if (Element)
     {
           memcpy(Element,Reg,sizeof(RegistreAgenda));
           Element->PunterASeguent=Llista->PunterAPrimer;
           Llista->PunterAPrimer = Element;
           return CERT;
     }
     else return FALS;
}
La funció TornaElement
Aquesta funció torna el primer element de la llista. No fa cap validació i  cas que la llista estigui buida es produirà un error del programa.		  RegistreAgenda TornaElement(LlistaAgenda *Llista)
{
     RegistreAgenda Provisional;
     strcpy(Provisional.nom,"");
     strcpy(Provisional.direccio,"");
     strcpy(Provisional.telefon,"");
     strcpy(Provisional.email,"");

     if (! EsBuida(Llista))
     memcpy(&Provisional,Llista->PunterAPrimer, 
                    sizeof(RegistreAgenda));
     return Provisional;
}
La funció ExtreuElement
Aquesta funció saca el primer element de la llista. Si valida el cas de tenir la llista buida i no es produirà error.		 void ExtreuElement(LlistaAgenda *Llista)
{
     RegistreAgenda * Provisional;
     if (! EsBuida(Llista))
     {
          Provisional = Llista->PunterAPrimer;
          Llista->PunterAPrimer = 
                                         Provisional->PunterASeguent;
          delete Provisional;
     }
}
La funció principal i les declaracions prèvies só les del quadre de la dreta. #include <stdio.h>
#include <conio.h>
#include <string.h>

typedef int Boolean;
#define CERT 1
#define FALS 0
 

void InicialitzaLlista(LlistaAgenda * Llista);
Boolean EsBuida(LlistaAgenda * Llista);
Boolean InsereixElement(RegistreAgenda * Reg, LlistaAgenda * Llista);
RegistreAgenda TornaElement(LlistaAgenda *Llista);
void ExtreuElement(LlistaAgenda *Llista);

main()
{
    RegistreAgenda regActual;
    LlistaAgenda Classe;

    clrscr();

    InicialitzaLlista(&Classe);

     strcpy(regActual.nom,"Josep");
     InsereixElement(&regActual,&Classe);
     strcpy(regActual.nom,"Maria");
     InsereixElement(&regActual,&Classe);
     strcpy(regActual.nom,"Ramón");
     InsereixElement(&regActual,&Classe);
     strcpy(regActual.nom,"Pep");
     InsereixElement(&regActual,&Classe);

     return 0;
}


La funció Recorregut
Aquesta funció rep una llista i imprimeix per pantalla tots els noms de la llista. 
Per a fer el recorregut fa ús d'un punter auxiliar anomenat PunterAReg. En principi fem apuntar aquest punter al primer registre. Després fem que apunti al següent i a així successivament.		 void Recorregut(LlistaAgenda * Llista)
{
     //Recorregut de la llista
     RegistreAgenda * PunterAReg;
     PunterAReg = Llista->PunterAPrimer;
     while (PunterAReg)
     {
          printf("%s\n",PunterAReg->nom);
          PunterAReg=PunterAReg->PunterASeguent;
     }
}
La funció Busca
Aquesta funció rep un string amb una cadena a buscar i una llista on buscar aquest string. Fa un recorregut pels registres buscant la cadena al camp Nom. Cas que trobi la informació torna un punter a aquest registre. Si no la troba llavors torna NULL.
Podem cridar aquesta funció amb les instruccions:

    RegistreAgenda * RegistreBuscat;
    RegistreBuscat=Busca("Ramón",&Classe);

 RegistreAgenda * Busca(char * InfoABuscar,  LlistaAgenda * Llista)
{
     //Recorregut de la llist
     RegistreAgenda * PunterAReg;
     Boolean Trobat=FALS;
     PunterAReg = Llista->PunterAPrimer;
     while (PunterAReg && (!Trobat))
     {
          if (! strcmp(InfoABuscar,PunterAReg->nom)) Trobat = CERT;
          else PunterAReg=PunterAReg->PunterASeguent;
     }
        return PunterAReg;
}


La funció InsereixDespres
Aquesta funció rep el punter a un registre d'una llista i un punter a un registre a inserir després.
La funció insereix el registre. Si té èxit torna CERT i sinó torna FALS.

Poden cridar aquesta funció amb les instruccions:

    RegistreAgenda regActual;
    RegistreAgenda * RegistreBuscat;
    RegistreBuscat=Busca("Ramón",&Classe);
    strcpy(regActual.nom,"Lola");
    if (RegistreBuscat) 
            InsereixDespres(RegistreBuscat, 
                                        &RegActual);

Si té èxit la recerca de Ramón a la llista llavors inserim Lola després de Ramón.

 Boolean InsereixDespres(RegistreAgenda * PunterAReg, 
                                          RegistreAgenda * RegAInserir)
{
     RegistreAgenda * Element;
     Element = new RegistreAgenda;
     if (Element)
     {
          memcpy(Element,RegAInserir,sizeof(RegistreAgenda));
          Element->PunterASeguent=PunterAReg->PunterASeguent;
          PunterAReg->PunterASeguent = Element;
          return CERT;
     }
     else return FALS;
}


La funció InsereixAbans
El procedimient es una mica més complicat car no podem moure el PunterAReg en sentit esquerra. Peró es pot fer por mitjà d'un artifici que consisteix en inserir el nou registre després i intercanviar les dades dels  dos registres.		 Boolean InsereixAbans(RegistreAgenda * PunterAReg, 
                                       RegistreAgenda * RegAInserir)
{
     RegistreAgenda * Element;
     Element = new RegistreAgenda;
     if (Element)
     {
          memcpy(Element,PunterAReg,sizeof(RegistreAgenda));
          memcpy(PunterAReg,RegAInserir,sizeof(RegistreAgenda));
          PunterAReg->PunterASeguent = Element;
      return CERT;
     }
     else return FALS;
}


La funció EsborraElement.
Es poden presentar tres situacions diferents segons el registre a esborrar:
  1. El punter apunta al primer registre i aquest és l'únic registre de la llista. En aquest cas es fa que el punter arrel (Llista->PunterAPrimer) apunti a NULL.
  1. El punter apunta a un registre que té següent. En aquests cas es copien les dades del registre següent al apuntat pel  punter.
  2. El punter apunta a l'últim registre quan hi ha més d'un registre. En aquest cas es fa que el punter del registre anterior apunti a NULL.
En tots aquests casos s'ha de disposar d'un punter auxiliar que alliberi la memòria que es queda sense usar mitjançant la instrucció delete punter.

RegistreBuscat=Busca("Pep",&Classe);
if (RegistreBuscat) 
    EsborraSeguent(RegistreBuscat, &Classe);

 void EsborraElement(RegistreAgenda * PunterAReg, 
                                    LlistaAgenda * Llista)
{
     RegistreAgenda * Provisional, * RegAnterior;

     if(!Llista->PunterAPrimer->PunterASeguent) //Nomes existeix un registre
     {
          delete PunterAReg;
          Llista->PunterAPrimer=NULL;
     } else if (PunterAReg->PunterASeguent) //El registre a esborrar no és l'últim
       {
           Provisional = PunterAReg->PunterASeguent;
           memcpy(PunterAReg,PunterAReg->PunterASeguent, 
                          sizeof(RegistreAgenda));
           delete Provisional;
        } else //El registre a esborrar és l'últim
           {
                 RegAnterior=Llista->PunterAPrimer;
                 while (RegAnterior->PunterASeguent->PunterASeguent)
                 RegAnterior=RegAnterior->PunterASeguent;
                 RegAnterior->PunterASeguent=NULL;
                delete PunterAReg;
            }
}

 
La funció EsborraSeguent
Aquesta funció crida a la funció anterior amb el punter adien.
RegistreBuscat=Busca("Ramon",&Classe);
if (RegistreBuscat) 
    EsborraSeguent(RegistreBuscat, &Classe);		 void EsborraSeguent(RegistreAgenda * PunterAReg,
                                   LlistaAgenda * Llista)
{
       if (PunterAReg->PunterASeguent)
               EsborraElement(PunterAReg->PunterASeguent, Llista);
}

 
La funció EsborraLlista.
Consisteeix en esborrar successívamente el primer registre. Per a fer-hoo es cópia el segon registre al primer mentre hi ha segon registre. També és necesari matenir un punter provisional que apunti al segon registre per a, després de copiades les seves dades al primer, alliberar la memoria que ocupa.

Quedará alliberar la memòria del primer registre i inicialitzar la llista.
 

 void EsborraLlista(LlistaAgenda * Llista)
{
     RegistreAgenda * PunterProvisional;
     while(Llista->PunterAPrimer->PunterASeguent)
     {
          PunterProvisional=Llista->PunterAPrimer->PunterASeguent;
          memcpy(Llista->PunterAPrimer,PunterProvisional,
                          sizeof(RegistreAgenda));
          delete PunterProvisional;
     }
     delete Llista->PunterAPrimer;
     Llista->PunterAPrimer=NULL;
}

12.4. Exercicis

  1. Afegeix a la llista unidireccional de la pregunta 3 una funció que canvïi l'ordre de dels elemements de les llistes.

    2.  
  2. Afegeix una altra funció que rebi una llista i ens la ordeni pel camp nom.

    3.  
  3. Una nova funció rep dues llistes i ens torna una nova llista formada amb els elements de les dues llistes.

    4.  
  4. Una llista circular és una llista unidireccional en la que l'últim element de la llista apunta al primer element en lloc d'apuntar a NULL. Si observes la imatge veuràs que en realitat no existeix primer element.




    5. Per a recórrer una llista circular hem de mantenir un punter PunterAReg que apunti a un element de la llista. Com que no té ni principi ni fi haurem de convenir que acabarem el recorregut quan el PunterAReg torni a estar en el lloc on va començar a moure's. Així si el punter està apuntant a l'element Lola i el movem (Josep, Pep, Ramon, ...) haurem d'aurar el moviment quan arribem una altra vegada a Lola.

    En aquest tipus de llista necessitaràs les estructures següents:
     

    typedef struct RegistreAgenda
    {
        char nom[45];
        char direccio[36];
        char telefon[15];
        char email[40];
        RegistreAgenda * PunterASeguent;
    };

    typedef struct LlistaCircular
    {
         RegistreAgenda * PunterAReg;
    };

    Hauràs de fer les funcions següents: InicialitzaLlista, InsereixALaDreta, Busca, EsborraElement i ImprimeixNoms.
     

  5. Llistes doblement enllaçades són les que en cada element tenen dos punters, un apunta al registre següent i l'altre al registre anterior. Aixó permet fer el recorregut de la llista en els dos sentits posibles.


    6. En aquest tipus de llista necessitaràs les estructures següents:
     
    typedef struct ElementLlista
    {
        RegistreAgenda * PunterAAnterior;
        char nom[45];
        char direccio[36];
        char telefon[15];
        char email[40];
        RegistreAgenda * PunterASeguent;
    };

    typedef struct LlistaBidireccional
    {
         RegistreAgenda * PunterAPrimer;
         RegistreAgenda * PunterAUltim;
    };

    Hauràs de fer les funcions següents: InicialitzaLlista, InsereixALaDreta, InsereixALaEsquerra, Busca, EsborraElement i ImprimeixNomsDreta i ImprimeixNomsEsquerra.

  6. Joc del solitari del ximple.

    7. Aquest solitari és un joc que farem amb el joc de cartes de 40 cartes.
    Necessitarem una estructura d'elements de tipus carta com la següent:
     
    typedef struct Carta 
    {
         int Numero;
         int Palo;
         struct Carta * pCartaSeguent;
    };

    typedef struct LlistaCartes
    {
         Carta * pPrimeraCarta;
    };

    Estat inicial: Disposem de sis llistes on posar cartes: Maç, CartesSortides, Oros, Copes, Espases i Bastons.
    El joc consisteix en treure les cartes de la llista Maç de dues en dues i apilalar-les a la llista CartesSortides. D'aquesta llista anirem passant cartes a les llistes d'oros, copes espases o bastos de manera ordenada, és a dir que les llistes dels pals estan ordenades de menor a major i totes les cartes d'una llista de pal són del mateix pal.
    Per a fer el programa de manera que pugui jugar un usuari farem un menú amb les següents opcions:
     

    0 Acabar

    1 Iniciar el joc
    2 Treure dues cartes
    3 Passar carta de cartes sortides a Oros
    4 Passar carta de cartes sortides a Copes
    5 Passar carta de cartes sortides a Espases
    6 Passar carta de cartes sortides a Bastons
    7 Torna les cartes sortides al Maç


    Funcions auxiliars que et seran útils:

  7. Fes una programa que ha de llegir el fitxer AgendaClasse.TXT que està compost de registres amb la següent estructura:
    8. typedef struct ElementLlista
    {
        char nom[45];
        char direccio[36];
        char telefon[15];
        char email[40];
    };
    Has de emmagatzemar aquests registres en una llista unidireccional ordenada pel camp nom i fer un llistat per pantalla posant pàgines de 10 en 10 registres.
  8. Un dibuix de pantalla de text el codificarem en base a punts amb una estructura com la següent:

    9.  
    typedef struct Punt 
    {
         int x;
         int y;
         char Caracter;
         int Color;
         int Fons;
         struct Punt * Seguent;
    };

    a) Un programa demana per pantalla els punts d'un dibuix i a mesura que es reben per pantalla els inclou en una llista unidireccional. Després escriu el dibuix en pantalla i ho repeteix quatre vegades en diferents posicions.

    b) Fes un programa igual que l'anterior, preo ara la font d'entrada de dades serà un fitxer de disc.
     Primer has de fer un fitxer ASCII que contingui les dades.