Tabla de fichas Indice del Tema 1106
1101 1102 1103 1104 1105 1106 1107 1108

ASIGNACIÓN DINÁMICA DE MEMORIA - CREACIÓN DE UNA LISTA ENLAZADA


Se muestra aquí un ejercicio cuyo propósito es doble:
  1. Mostrar una implementación sencilla de una lista simplemente enlazada.
  2. Aplicar el código reutilizable mostrado en estas páginas para ejercitar las operaciones de la lista enlazada construida.
Los conceptos y operaciones propios de las listas enlazadas ya se han descrito detalladamente, y no se insistirá sobre ellos. Con respecto al código reutilizable, la única curiosidad es que se han separado los archivos que forman parte del programa en dos directorios: adiciones y reutilizados. Como cabría suponer: Además, el directorio de adiciones contiene un módulo llamado conector, que es el que invoca a funciones de lista_enlazada desde el programa principal. En conector se concentran las llamadas a funciones de otros módulos; es el punto de acoplamiento entre el programa reutilizable y cualquier otro conjunto de módulos de los que se haga uso en nuestra aplicación.

Téngase en cuenta que las inclusiones deben respetar, necesariamente, la arquitectura de directorios.
Es cómodo, aunque no necesario, utilizar un IDE para aquellos programas que constan de múltiples archivos.

Contenido del directorio reutilizados

  1. aplicacion.h
  2. cda.h
  3. tipos.h
  4. aplicacion.c
  5. cda.c
  6. main.c
aplicacion.h
/*
 * aplicacion.h
 *
 *  Created on: 30/09/2009
 *      Author: coti
 */

#ifndef APLICACION_H_
#define APLICACION_H_

#include <coti/utiles.h>
#include "tipos.h"

void distribuidor(  GlobRef g,
                    charRef men,
                    charRef opc,
                    funRef * fun);
void salir      (   GlobRef g);
void volver     (   GlobRef g);

#endif /*APLICACION_H_*/
cda.h
/*
 * cda.h
 *
 *  Created on: 30/09/2009
 *      Author: coti
 */

#ifndef CDA_H_
#define CDA_H_

#include <coti/utiles.h>
#include "tipos.h"

void arranque(GlobRef g, int argc, char * argv[]);
void parada  (GlobRef g);
void ayuda   (GlobRef g);

#endif /*CDA_H_*/
tipos.h
/*
 * tipos.h
 *
 *  Created on: 30/09/2009
 *      Author: coti
 */

#include <coti/utiles.h>

#ifndef __TIPOS__
#define __TIPOS__
/*
 Normalmente, será preciso incluir aquí los archivos de encabezado
 que aportan tipos específicos para la funcionalidad deseada.
 */

#include "../adiciones/lista_enlazada.h"

typedef struct Globales {
  ListaRef lista;
  ListaRef duplicado;
  int salirDePrograma;
} Globales;

typedef Globales * GlobRef;

typedef void (*funRef)(GlobRef);


#endif
aplicacion.c
/*
 * aplicacion.c
 *
 *  Created on: 30/09/2009
 *      Author: coti
 */

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include "aplicacion.h"

/* Esta parte del programa es fija, no requiere modificaciones. */

void salir(GlobRef g)
{
    g->salirDePrograma = confirmar("\n\n¿Desea salir del programa?");
}

void volver(GlobRef g)
{
  printf("\n\n***\7Opción incorrecta***\n\n");
  return;
}

void distribuidor(  GlobRef  g,
                    charRef  men,
                    charRef  opc,
                    funRef * fun)
{
  char orden;
  int numOpciones = 0;
  int numFunciones = 0;
  int i;
  funRef * f;
  numOpciones = strlen(opc);
  while(fun[numFunciones]) numFunciones++;
  if (numOpciones != numFunciones)
  {
    printf("\n\nError fatal: numOpciones (%d) =! numFunciones (%d)\n\n",
         numOpciones, numFunciones);
    exit(1);
  }

  f = malloc(256*sizeof(funRef));
  for(i=0;i<256;i++) f[i] = volver;

  for(i=0;i<numOpciones;i++) f[(int)opc[i]] = fun[i];

  do
  {
    printf("%s ", men);
    orden = toupper(abs(getch()));
    f[(int)orden](g);
  } while (!g->salirDePrograma);
  free(f);
}
cda.c
/*
 * cda.c
 *
 *  Created on: 30/09/2009
 *      Author: coti
 */

#include "cda.h"
/*
 Constructor, destructor y ayuda
 -            -            -
 */
void arranque(GlobRef g, int argc, charRef argv[]) {
  g->lista = malloc(sizeof(Lista));
  g->duplicado = malloc(sizeof(Lista));
  g->lista->ppio = g->lista->fin = g->duplicado->ppio = g->duplicado->fin
      = NULL;
  g->salirDePrograma = 0;
  printf("\n\nSe ha ejecutado el procedimiento de arranque.\n\n");

}

void parada(GlobRef g) {
  printf("\n\nSe ha ejecutado el procedimiento de parada.\n\n");
}

void ayuda(GlobRef g) {
  printf("\n\nEste es el mecanismo de ayuda.\n\n");
}
main.c
/*
 ============================================================================
 Name        : main.c
 Author      : 
 Version     :
 Copyright   : Tests by (C)oti
 Description : Aplicación de distribuidor() a listas enlazadas
 ============================================================================
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "tipos.h"
#include "cda.h"
#include "aplicacion.h"
#include "../adiciones/conector.h"

int main(int argc, char * argv[]) {
  GlobRef g = malloc(sizeof(Globales));

  /* Sólo hay que modificar las variables siguientes. */
  charRef menu =
   "(1) Añadir al principio (2) Añadir al final (3) Insertar ordenado\n"
   "(4) Borrar principio (5) Borrar final (6) Borrar buscando\n"
   "(7) Ver lista completa (8) Borrar lista (9) Duplicar lista\n"
   "(H) Ayuda (S) Salir";
  charRef opciones = "123456789HS";
  funRef funciones[] = { opcion_ins_ppio, opcion_ins_final,
   opcion_ins_ordenado, opcion_borrar_principio, opcion_borrar_final,
   opcion_borrar_buscando, opcion_ver_lista, opcion_borrar_lista,
   opcion_duplicar_lista, ayuda, salir, NULL };

  /* El resto del programa no se modifica */

  arranque(g, argc, argv);
  distribuidor(g, menu, opciones, funciones);
  parada(g);
  printf("\n\nTerminación normal\n\n");
  return 0;
}

Contenido del directorio adiciones

  1. conector.h
  2. lista_enlazada.h
  3. conector.c
  4. lista_enlazada.c
conector.h
/*
 * conector.h
 *
 *  Created on: 30/09/2009
 *      Author: coti
 */
#include "../reutilizados/tipos.h"

#ifndef CONECTOR_H_
#define CONECTOR_H_

 void opcion_ins_ppio(GlobRef);
 void opcion_ins_final(GlobRef);
 void opcion_ins_ordenado(GlobRef);
 void opcion_borrar_principio(GlobRef);
 void opcion_borrar_final(GlobRef);
 void opcion_borrar_buscando(GlobRef);
 void opcion_ver_lista(GlobRef);
 void opcion_borrar_lista(GlobRef);
 void opcion_duplicar_lista(GlobRef);

#endif /* CONECTOR_H_ */
lista_enlazada.h
/*
 * lista_enlazada.h
 *
 *  Created on: Sep 30, 2009
 *      Author: bruegel
 */
#ifndef __LISTAENLAZADA__
#define __LISTAENLAZADA__

typedef struct Nodo {
  int valor;
  struct Nodo * sig;
} Nodo;

typedef Nodo * NodoRef;

typedef struct Lista {
  NodoRef ppio;
  NodoRef fin;
} Lista;

typedef Lista * ListaRef;

void leer_nodo(NodoRef);
void escribir_nodo(NodoRef);

void insertar_ppio(ListaRef);
void insertar_final(ListaRef);
void insertar_ordenado(ListaRef);
void borrar_principio(ListaRef);
void borrar_final(ListaRef);
void borrar_buscando(ListaRef);
void ver_lista(ListaRef);
void borrar_lista(ListaRef);
void duplicar_lista(ListaRef);

#endif /* __LISTAENLAZADA__ */
conector.c
/*
 * conector.c
 *
 *  Created on: 30/09/2009
 *      Author: coti
 */

#include "conector.h"

void opcion_ins_ppio(GlobRef g) {
  printf("\n\nOpción de inserción al principio\n\n");
  insertar_ppio(g->lista);
}

void opcion_ins_final(GlobRef g) {
  printf("\n\nOpción de inserción al final\n\n");
  insertar_final(g->lista);

}

void opcion_ins_ordenado(GlobRef g) {
  printf("\n\nOpción de inserción ordenada (ascendente)\n\n");
  insertar_ordenado(g->lista);
}

void opcion_borrar_principio(GlobRef g) {
  printf("\n\nOpción de borrado del primer elemento\n\n");
  borrar_principio(g->lista);
}

void opcion_borrar_final(GlobRef g) {
  printf("\n\nOpción de borrado del segundo elemento\n\n");
  borrar_final(g->lista);
}

void opcion_borrar_buscando(GlobRef g) {
  printf("\n\nOpción de borrado buscando un valor\n\n");
  borrar_buscando(g->lista);
}

void opcion_ver_lista(GlobRef g) {
  printf("\n\nOpción de visualización del lista completa\n\n");
  ver_lista(g->lista);
}

void opcion_borrar_lista(GlobRef g) {
  printf("\n\nOpción de borrado de lista completa\n\n");
  borrar_lista(g->lista);
}

void opcion_duplicar_lista(GlobRef g) {
  printf("\n\nOpción de duplicado de una lista\n\n");
  duplicar_lista(g->lista);
}
lista_enlazada.c
/*
 * lista_enlazada.c
 *
 *  Created on: 30/09/2009
 *      Author: coti
 */

#include <stdlib.h>
#include "coti/utiles.h"
#include "lista_enlazada.h"

/* Implementaciones de operaciones específicas del programa */

void leer_nodo(NodoRef pn) {
  pn->valor = pedirInt("\n\nEscriba un número entre 1 y 100:", 1, 100);
  pn->sig = NULL; /* Supone seguridad y brevedad */
  printf("\n");
}
void escribir_nodo(NodoRef pn) {
  printf("%6d", pn->valor);
}
/* 1.- Insertar nodo al principio. */
void insertar_ppio(Lista * pl) {
  NodoRef temp = (NodoRef) malloc(sizeof(Nodo));
  if (temp != NULL) /* Hay espacio para el nodo nuevo */
  {
    printf("\n\nAdición de un nodo al principio de la lista.\n\n");
    leer_nodo(temp);
    if (NULL == pl->ppio) { /* La lista está vacía */
      pl->ppio = pl->fin = temp;
    } else {
      temp->sig = pl->ppio;
      pl->ppio = temp; /* El nodo pasa a ser el nuevo ppio*/
    }
  } else
    printf("\n\ninsertar_ppio() - memoria insuficiente.\n\n");
}
/* 2.- Insertar nodo al final. */
void insertar_final(Lista * pl) {
  NodoRef temp = (NodoRef) malloc(sizeof(Nodo));
  if (temp != NULL) {
    printf("\n\nAdición de un nodo al final de la lista.\n\n");
    leer_nodo(temp);
    if (NULL == pl->ppio) { /* La lista está vacía */
      pl->ppio = pl->fin = temp;
    } else { /* La lista no está vacía */
      pl->fin->sig = temp;
      pl->fin = temp; /* El nodo pasa a ser el nuevo fin*/
    }
  } else
    printf("\n\ninsertar_final() - memoria insuficiente.");
}
/* 3.- Insertar nodo buscando su posición. */
void insertar_ordenado(ListaRef pl) {
  NodoRef t, ant, pos;
  t = (NodoRef) malloc(sizeof(Nodo));
  if (t) {
    printf("\n\nInserción de un nodo buscando su posición.\n\n");
    leer_nodo(t);
    if (NULL == pl->ppio) { /* La lista está vacía */
      pl->ppio = pl->fin = t;
    } else { /* Va a la izquierda del primer nodo? */
      if (t->valor <= pl->ppio->valor) {
        t->sig = pl->ppio;
        pl->ppio = t;
      } else if (t->valor >= pl->fin->valor) {
        /* Va a la derecha del último? */
        pl->fin->sig = t;
        pl->fin = t;
      } else { /* Entonces va en posición intermedia */
        ant = pl->ppio;
        pos = pl->ppio->sig;
        while (!(t->valor >= ant->valor && t->valor <= pos->valor)) {
          ant = pos;
          pos = pos->sig;
        }
        /* Al llegar aquí, hay que insertar t entre ant y pos */
        t->sig = pos;
        ant->sig = t;
      }
    }
  } else
    printf("\n\ninsertar_ordenado() - memoria insuficiente.");
}
/* 4.- Borrar nodo al principio. */
void borrar_principio(ListaRef pl) {
  NodoRef t;
  if (NULL == pl->ppio)
    printf("\n\nLa lista está vacía.\n\n");
  else {
    if (NULL != pl->ppio->sig) /* No es el único nodo */
    {
      t = pl->ppio;
      pl->ppio = pl->ppio->sig;
      printf("\n\nEl valor del nodo borrado es: ");
      escribir_nodo(t);
      free(t);
    } else {/* Es el último nodo */
      free(pl->ppio);
      pl->ppio = pl->fin = NULL;
    }
  }
  printf("\n\nNodo inicial borrado.\n\n");
}
/* 5.- Borrar nodo final. */
void borrar_final(ListaRef pl) {
  NodoRef t;
  if (NULL == pl->ppio)
    printf("\n\nLa lista está vacía.\n\n");
  else {
    if (NULL == pl->ppio->sig) /* Hay un solo nodo */
    {
      printf("\n\nEl valor del nodo borrado es: ");
      escribir_nodo(pl->ppio);
      free(pl->ppio);
      pl->ppio = pl->fin = NULL;
    } else {
      /* Hay que buscar penúltimo nodo */
      t = pl->ppio;
      while (t->sig != pl->fin) {
        t = t->sig;
      }
      /* Al llegar aquí, t apunta al nodo anterior a fin */
      printf("\n\nEl valor del nodo borrado es: ");
      escribir_nodo(pl->fin);
      printf("\n");
      free(pl->fin);
      pl->fin = t;
      t->sig = NULL;
    }
  }
  printf("\n\nNodo final borrado.\n\n");
}
/* 6.- Borrar un nodo tras buscarlo. */
void borrar_buscando(ListaRef pl) {
  int buscado;
  NodoRef p, ant;
  if (NULL == pl->ppio) {
    printf("\n\nPerdón, la lista está vacía.\n\n");
    return;
  }
  buscado = pedirInt("Escriba el valor que quiere borrar: ", 1, 100);
  if (pl->ppio == pl->fin) /* Hay un solo nodo */
  {
    if (buscado == pl->ppio->valor) {
      borrar_principio(pl);
    } else
      printf("No se encontró el valor.");
  } else /*Hay dos nodos o más */
  {
    if (buscado == pl->ppio->valor) {
      borrar_principio(pl);
    } else if (buscado == pl->fin->valor) {
      borrar_final(pl);
    } else /*Puede estar en posición intermedia. */
    {
      ant = pl->ppio;
      for (p = ant->sig; p != pl->fin; p = p->sig) {
        if (buscado == p->valor) {
          ant->sig = p->sig;
          free(p);
          return;
        }
        ant = ant->sig;
      }
      if (p == pl->fin)
        printf("No se encontró el valor.");
    }
  }
}
/* 7.- Ver toda la lista. */
void ver_lista(ListaRef pl) {
  NodoRef t;
  if (NULL == pl->ppio) {
    /* La lista está vacía */
    printf("\n\nPerdón, la lista está vacía.\n\n");
  } else {
    printf("\n\nContenido de la lista (izquierda primero).\n\n");
    for (t = pl->ppio; t; t = t->sig)
      escribir_nodo(t);
    printf("\n\n");
  }
}
/* 8.- Borrar toda la lista. */
void borrar_lista(ListaRef pl) {
  if (NULL == pl->ppio) {
    printf("\n\nPerdón, la lista está vacía.\n\n");
  } else {
    while (pl->ppio) {
      borrar_principio(pl);
    }
    printf("\n\nLa lista se ha borrado.\n\n");
  }
}
/*  9.- Duplicar una lista. */
void duplicar_lista(ListaRef pl) {
  ListaRef lista_local; /* Para manejar la otra ListaRef */
  NodoRef tg;
  NodoRef tl;
  if (NULL == pl->ppio) {
    printf("\n\nImposible duplicar - lista vacía.\n\n");
  } else {
    lista_local = malloc(sizeof(Lista));
    tg = pl->ppio;
    tl = (NodoRef) malloc(sizeof(Nodo));
    tl->valor = tg->valor;
    tl->sig = NULL;
    lista_local->ppio = tl;
    lista_local->fin = tl;
    tg = tg->sig;
    while (tg) {
      tl = (NodoRef) malloc(sizeof(Nodo));
      tl->valor = tg->valor;
      tl->sig = 0;
      lista_local->fin->sig = tl;
      lista_local->fin = tl;
      tg = tg->sig;
    }
    /* Comprobación */
    printf("\n\nLISTA LOCAL - ");
    ver_lista(lista_local);
    /* Y después borramos la lista */
    borrar_lista(lista_local);
    free(lista_local);
  }
}