Programacion C++ y Java: septiembre 2009

Publicado por rogikato / en 23:39 / / 0 comentarios

En una lista simplemente encadenada, cada elemento posee apenas información de quien es su sucesor.
Es necesario también almacenar la información del primer elemento de la lista.
Principales problemas:
_Imposibilidad de regresar al elemento anterior.
_Necesidad de guardar información del elemento anterior a fin de realizar algunas operaciones.

Implementación (Estática)

Para simplificar se considerará que los elementos almacenados serán números enteros. Los elementos serán insertados de forma ordenada.
El esquema gráfico abajo muestra el proceso de inserción de un nuevo elemento en una lista encadenada estática. El nuevo elemento será insertado entre el elemento actual y el elemento anterior.

Especificación:
1. LE *Inicia_Lista(int N) // Crea una nueva lista con N elementos
2. void Inserta_Elemento(LE *L, int A) //Inserta un nuevo elemento A en la posicion correcta de la lista L
3. int Elimina_Elemento(LE *L, int A) //Elimina el elemento A de la lista L. Si el elemento no existe o la lista está vacía, retorna -1.
4. void Imprime_Lista (LE *L)
5. LE *Vacia_Lista(LE *L)

Código:

#include<iostream.h>
#include<stdlib.h>
#include<stdio.h>
typedef struct lista    LE;
typedef struct nodo_lista NO;
typedef struct vacio    VC;

struct vacio
{
  int  ultimo; /* guarda a última posición ocupada del vector pos_vac */
  int *pos_vac;
};

struct nodo_lista
{
  int elem;
  int prox; /* guarda la posición del próximo elemento en la lista */
};

struct lista
{
  int  head ; /* marca la posición del primer elemento de la lista */
  VC  *vac  ; /* guarda posiciones vacías */
  NO  *nodo   ;
};

LE *Inicia_Lista(int N)
{
  LE *temp;
  int i   ;

if ((temp = (LE *) malloc(sizeof(LE))) != NULL)
  {
    if ((temp->nodo = (NO *) malloc(N*sizeof(NO))) != NULL)
    {
      if ((temp->vac = (VC *) malloc(N*sizeof(VC))) != NULL)
      {
        if ((temp->vac->pos_vac = (int *) malloc(N*sizeof(int))) != NULL)
        {
          temp->vac->ultimo = N-1;

for (i = 1; i <= N; i++)
            temp->vac->pos_vac[i-1] = N-i;

temp->head = -1; /* lista vacia */
          return(temp);
        }
        else
          exit(0);
      }
      else
        exit(0);
    }
    else
      exit(0);
  }
  else
    exit(0);
}

void Inserta_Elemento(LE *L, int A) 
{
  int i,ant;

/* Ejercicio: realizar prueba para ver si todavía existe espacio */

if (L->head == -1) /* Lista esta vacía */ 
  {
    L->head = 0; 
    L->nodo[0].elem = A;
    L->nodo[0].prox = -1; 
    (L->vac->ultimo)--;
  } 
  else
  { 
    i = L->head;
    ant = -1; 
    while ((i != -1) && (L->nodo[i].elem <= A))
    { 
      ant = i; /* guarda la posicion del anterior */
      i = L->nodo[i].prox; 
    }
  
    L->nodo[L->vac->pos_vac[L->vac->ultimo]].elem = A;
  
    if (ant == -1) /* incluir al inicio de la lista */
    { 
      L->nodo[L->vac->pos_vac[L->vac->ultimo]].prox = L->head;
      L->head = L->vac->pos_vac[L->vac->ultimo]; 
    }
    else 
    {
      L->nodo[L->vac->pos_vac[L->vac->ultimo]].prox =  L->nodo[ant].prox; 
      L->nodo[ant].prox = L->vac->pos_vac[L->vac->ultimo];
    } 
    (L->vac->ultimo)--;
  } 
  return;
}

void Imprime_Lista(LE *l) 
{
  int i; 
  
  i = l->head;
  cout<<"\n Elementos "; 
  while (i != -1) 
  {
    cout<<l->nodo[i].elem<<" "; 
    i = l->nodo[i].prox; 
  }
} 
/* Ejercicios: Implementar las funciones que faltan */

int Elimina_Elemento(LE *L, int A){
   int i,ant;

if (L->head == -1){    
       return -1;
   }
   else 
   { 
       i = L->head;
      
       if (L->nodo[i].elem == A) 
       {
          L->head = L->nodo[i].prox; 
          (L->vac->ultimo)++;
          return 1;
       } 
       while(i != -1){
          if(L->nodo[i].elem==A){
                L->nodo[ant].prox=L->nodo[i].prox; 
                L->nodo[i].prox=NULL;
                (L->vac->ultimo)++;
                return 1;
          }     
          else{
                ant=i; 
                i=L->nodo[i].prox;
          }
       }
       return -1;
   }
}
  
main()
{ 
  LE *l; 
  int N,aux_l,x=0;
  char opc; 
  
  cout<<"Ingrese el num. max. elem. en la lista\n";
  cin>>N; 
  
  l = (LE *) Inicia_Lista(N);
  
  while (1) 
  {
    cout<<"\n Insertar(i) Eliminar(e) Imprimir(p) Salir(s) "; 
    cin>>opc;

if (opc == 'i') 
    { 
      cout<<"\n Ingrese el nuevo número entero ";
      cin>>x; 
      Inserta_Elemento(l,x);
    }
  
    if (opc == 'e') 
    {
      printf("\n Ingrese el núm. entero a buscar ");
      scanf("%d",&x); 
      aux_l = Elimina_Elemento(l,x);
      if (aux_l == -1) 
        printf("Numero no encontrado\n"); 
    }
  
    if (opc == 'p') 
      Imprime_Lista(l);
  
    if (opc == 's') 
    {
     /* l = (LE *) Vacia_Lista(l); */
      exit(0); 
    }
  } 
}

Implementación (Dinámica)

Por simplicidad los elementos almacenados serán números enteros. Los elementos serán insertados de forma ordenada.
El esquema gráfico abajo muestra el proceso de inserción de un nuevo elemento en una lista encadenada dinámica. el nuevo elemento será insertado entre el elemento actual y el elemento anterior.

Las operaciones ilustradas pueden ser descritas como:
nuevo->prox = actual;
anterior->prox = nuevo;

Especificación:

LE *Inicia_Lista() //Crea una nueva lista
void Inserta_Elemento(LE *L, int A) //Inserta un nuevo elemento A en la posición correcta de la lista L
int Elimina_Elemento(LE *L, int A) //Elimina el elemento A de la lista L. Si el elemento no existe o la lista está vacía retorna -1.
void Imprime_Lista (LE *L)
LE *Vacia_Lista(LE *L)

Código:

#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
typedef struct lista    LE;
typedef struct nodo_lista NO;

struct nodo_lista
{ 
  int elem; 
  NO *prox; /* guarda la posicion del proximo elemento en la lista */ 
};
  
struct lista 
{ 
  NO *head,*pa,*imp; /* guarda la direccion del primer elemento de la lista */
};

LE *Inicia_Lista(void)
{ 
  LE *temp;

if ((temp = (LE *) malloc(sizeof(LE))) != NULL) 
  { 
    temp->head = NULL; 
    return(temp);
  } 
  else 
    exit(0); 
}

void Inserta_Elemento(LE *L, int A)
{ 
  NO *aux,*ant,*atu;

if ((aux = (NO *) malloc(sizeof(NO))) != NULL) 
  { 
    aux->elem = A; 
    if (L->head == NULL) 
    {
      aux->prox = NULL; 
      L->head = aux; 
    } 
    else 
    { 
      atu = L->head;
      ant = NULL;
      while ((atu != NULL) && (atu->elem <= A))
      {
        ant = atu;
        atu = atu->prox;
      } 
      if (ant == NULL) /* insertar en la primera posición de la lista */ 
      { 
        aux->prox = L->head; 
        L->head = aux; 
      } 
      else 
      {
        aux->prox = ant->prox; 
        ant->prox = aux;
      }
    }
  }
  else
    exit(0);
  return;
}

int Eliminar_Elemento(LE *L,int A){

NO *aux,*ant,*atu;

if ((aux = (NO *) malloc(sizeof(NO))) != NULL)
  {
      if(L->head == NULL){
         return -1;
      }
      else{
           atu=L->head;

if(atu->elem==A){
              L->head = atu-> prox;
              return 1;
           }

while (atu != NULL)
           {
             if(atu->elem==A){
                ant->prox=atu->prox;
                atu->prox=NULL;
                return 1;
             }
             else{
                ant=atu;
                atu=atu->prox;
             }
           }
           return -1;
      }

}
}

void Invertir_Lista(LE *L){

NO *aux,*ant,*atu;

if ((aux = (NO *) malloc(sizeof(NO))) != NULL)

{   atu = L->head;
      ant = NULL;

while (atu!= NULL)
      {
       L->head=atu->prox;
       atu->prox=ant;
       ant=atu;
       atu=L->head;
      }
      while (ant != NULL)
      { cout<<ant->elem<<" ";
        ant = ant->prox;
      }
  }
}

void InPar_Lista(LE *L){
  NO *atu,*par,*impar;
  if ((par = (NO *) malloc(sizeof(NO))) != NULL)
  {  atu = L->head;
     par = NULL;
     impar = NULL;
      while (atu != NULL)
      { if(atu->elem%2==0)
        { if(par==NULL)
            {L->pa=atu;
             par=atu;
            }
        else{
         par->prox=atu;
         par=atu;
        }}
        else
        {
        if(impar==NULL)
            {L->imp=atu;
             impar=atu;
            }
        else{
        impar -> prox = atu;
         impar=atu;
        }}
        atu = atu->prox;
      if(atu==NULL)
      {if(par!=NULL)par->prox=NULL;
       if(impar!=NULL)impar->prox=NULL;
      }
    }
    par=L->pa;
    impar=L->imp;
    while(par!=NULL)
   { cout<<par->elem<<" ";
    par = par->prox;
   }
   cout<<endl;
  while(impar!=NULL)
   { cout<<impar->elem<<" ";
    impar = impar->prox;
   }
  }
}

void Imprime_Lista(LE *L){

NO *aux,*atu;
  int tam=0;

if ((aux = (NO *) malloc(sizeof(NO))) != NULL)
  {
      atu = L->head;

while (atu != NULL)
      {
        tam++;
        cout<<atu->elem<<" ";
        atu = atu->prox;

}
      
      cout<<" de tama\xa4o "<<tam;
   }
}

/* Ejercicios: Implementar las funciones que faltan */

main()
{
  int aux_l;
  LE *l;
  int x=0;
  char opc;

l = (LE *) Inicia_Lista();

while (1) 
  { 
    cout<<"\nInsertar (i) Eliminar (e) Imprimir (p)  Invertir (v) Inpar Par (d) Sair s)   ";
    cin>>opc;

if (opc == 'i')
    { 
      cout<<"\n Ingrese el nuevo elemento entero "; 
      cin>>x;
      Inserta_Elemento(l,x);      
    }

if (opc == 'e')
    { 
      cout<<"\n Ingrese el número entero a buscar ";
      cin>>x; 
      aux_l = Eliminar_Elemento(l,x);
      if (aux_l == -1)
        cout<<"Numero no encontrado\n"; 
    }
    if(opc=='v')
     Invertir_Lista(l);
    if(opc=='d')
     InPar_Lista(l);

if (opc == 'p')
      Imprime_Lista(l);

if (opc == 's') 
    { 
      //l = (LE *) Vacia_Lista(l);
      exit(0);
    }
  }
}

Árbol Patricia en c++

Listas simplemente encadenada

Temas...

Archivo del blog

Seguidores

Subscribete Via Email A Sta Web....