Lista Simple

Estructura de archivos:

📁 09_Lista
└── 📁 Lista-NN
    ├── 📄 main.c
    └── 📄 Makefile

Ejercicios:

Lista Simple 01

Makefile

CC = gcc
CFLAGS = -std=c11 -Wall -Wextra -pedantic

PROG = main
OBJ = main.o

$(PROG): $(OBJ)
	$(CC) $(OBJ) -o $(PROG)

$(OBJ): main.c
	$(CC) $(CFLAGS) -c main.c

.PHONY: clean
clean:
	del $(OBJ) $(PROG).exe

Código:

// gcc -std=c11 -Wall -Wextra -pedantic main.c -o main

#include <stdio.h>
#include <stdlib.h> // Se usa system(), exit(), malloc(), free()
#include <conio.h> // Se usa getch() y getche()

/* Nodo de lista simplemente enlazada.
 * - Dato => valor almacenado.
 * - Sig  => puntero al siguiente nodo.
 */
struct Lis
{
    int Dato;
    struct Lis *Sig;
};

/* Prototipos de funciones */
void Ingresa(struct Lis **);
void Lee(struct Lis **);
void Borra(struct Lis **);
void Elimina(struct Lis **);

int main(void)
{
    int Opcion;

    /* Inicio apunta al primer nodo de la lista.
     * Si es NULL => lista vacia.
     */
    struct Lis *Inicio = NULL;

    /* Bucle infinito tipo menu */
    for (;;)
    {
        system("cls"); // Limpia la pantalla.

        printf("\n1 - Ingresa datos\n");
        printf("2 - Lee datos\n");
        printf("3 - Borra datos\n");
        printf("4 - Salir\n\n");
        printf("Ingrese una opcion (1 - 4): ");
        
        Opcion = getche(); // Lee el caracter y lo muestra, sin esperar Enter

        switch(Opcion)
        {
            case '1':
                Ingresa(&Inicio);
                break;

            case '2':
                Lee(&Inicio);
                break;

            case '3':
                Borra(&Inicio);
                break;

            case '4':
                /* Antes de salir, libera toda la memoria. */
                Elimina(&Inicio);
                exit(0);
        }
    }

    return 0;
}

/* Inserta nodo al final de la lista. 
 * **Principio es un puntero a puntero porque:
 * Necesitamos poder modificar el puntero original cuando la lista esta vacia.
 */
void Ingresa(struct Lis **Principio)
{
    /* *Actual:
     * - Se usa para recorrer la lista, comienza apuntando al primer nodo.
     *
     * *Nuevo:
     * - Sera el nodo recien creado con malloc().
     */
    struct Lis *Actual = *Principio, *Nuevo;

    system("cls"); // Limpia la pantalla.

    /* Se reserva memoria dinamica para un nodo.
     * sizeof() reserva spacio para Dato y *Sig
     * Si malloc devuelve NULL => no hay memoria disponible.
     */
    if (! (Nuevo = (struct Lis *)malloc(sizeof(struct Lis))))
    {
        system("cls"); // Limpia la pantalla.

        printf("\n\nNo hay memoria disponible\n");
        
        printf("\n\nPresiones una tecla para continuar\n");
        getch(); // Espera que se presione una tecla.

        return;
    }

    printf("\n\nIngrese el dato: ");
    /* Se carga el valor en el nuevo nodo.
     * Nuevo->Dato accede al campo Dato del nodo recien creado.
     */
    scanf("%d", &Nuevo->Dato);

    Nuevo->Sig = NULL; // Siempre apunta a NULL al crearse.

    /* Si la lista esta vacia, el nuevo nodo pasa a ser el primero. */
    if (!*Principio)
    {
        *Principio = Nuevo;

        return;
    }

    /* Recorre hasta el ultimo nodo el que tiene Sig == NULL */
    while(Actual->Sig)
        Actual = Actual->Sig;

    /* Enlaza el nuevo al final. */
    Actual->Sig = Nuevo;
}

/* Recorre e imprime la lista completa, desde el inicio hasta NULL. */
void Lee(struct Lis **Principio)
{
    /* *Actual empieza apuntando al primer nodo */
    struct Lis *Actual = *Principio;
    
    system("cls"); // Limpia la pantalla.

    /* Mientras Actual NO sea NULL, significa que aun hay nodos por recorrer. */
    while (Actual)
    {
        printf("\nEl dato es: %d", Actual->Dato);
        Actual = Actual->Sig; // Avanza al siguiente nodo.
    }

    printf("\n\nPresione una tecla para continuar\n");
    getch(); // Espera que se presione una tecla. 
}

/* Borra un nodo por valor */
void Borra(struct Lis **Principio)
{
    /* *Actual comienza apuntando al primer nodo, se usa para recorrer la lista.
     * *Anterior comienza apuntando al primer nodo, guarda el nodo previo, necesario para reconectar enlaces.
     */ 
    struct Lis *Actual = *Principio, *Anterior = *Principio;
    int b;
    
    system("cls"); // Limpia la pantalla.

    printf("\nIngrese el dato a borrar: ");
    scanf("%d", &b);

    /* Busca el nodo que contenga el valor */
    while ((Actual) && (b != Actual->Dato))
    {
        Anterior = Actual;
        Actual = Actual->Sig;
    }

    /* Caso 1: es el primer nodo */
    if ( (Actual) && (*Principio == Actual))
    {
        /* Se mueve el inicio al segundo nodo. */
        *Principio = Actual->Sig;
        free(Actual); // Se libera la memoria del nodo eliminado.

        return;
    }

    /* Caso 2: esta en medio o final */
    if (Actual)
    {
        /* El nodo Anterior ahora apunta al siguiente del nodo eliminado. */
        Anterior->Sig = Actual->Sig;
        free(Actual);

        return;
    }

    /* Caso 3: no encontrado */
    system("cls"); // Limpia la pantalla

    printf("\nEl dato no ha sido encontrado");
    printf("\n\nPresiones una tecla para continuar\n");

    getch(); // Espera  que se presione una tecla
}

/* Libera completamente la memoria de todos los nodos de la lista */
void Elimina(struct Lis **Principio)
{
    struct Lis *Actual;

    /* Mientras la lista no este vacia */
    while (*Principio)
    {
        Actual = *Principio;            // Guarda el nodo actual.
        *Principio = (*Principio)->Sig; // Avanza el inicio al siguiente nodo.
        free(Actual);                   // Libera el nodo que estaba primero (Actual).
    }
    /* Al terminar el bucle:
     * *Principio == NULL
     * La lista quedo completamente vacia.
     */
}

Lista Simple 02

Makefile

CC = gcc
CFLAGS = -std=c11 -Wall -Wextra -pedantic

PROG = main
OBJ = main.o

$(PROG): $(OBJ)
	$(CC) $(OBJ) -o $(PROG)

$(OBJ): main.c
	$(CC) $(CFLAGS) -c main.c

.PHONY: clean
clean:
	del $(OBJ) $(PROG).exe

Código:

// gcc -std=c11 -Wall -Wextra -pedantic main.c -o main

#include <stdio.h>
#include <stdlib.h> // Se usa system(), exit(), malloc(), free()
#include <conio.h> // Se usa getch() y getche()
#include <ctype.h> // Se usa toupper()

/* Definicion del nodo de la lista */
struct Lis
{
    int Dato;
    struct Lis *Sig; // Puntero al siguiente nodo
};

/* Prototipos de funciones */
void Ingresa(struct Lis **);
void Lee(struct Lis **);
void Borra(struct Lis **);
void Busca(struct Lis **);

int main(void)
{
    int Opcion;

    /* Inicio apunta al primer nodo de la lista.
     * Si es NULL => lista vacia.
     */
    struct Lis *Inicio = NULL;

    /* Bucle infinito tipo menu */
    for (;;)
    {
        system("cls"); // Limpia la pantalla.

        printf("\n1 - Ingresa datos\n");
        printf("2 - Lee datos\n");
        printf("3 - Borra datos\n");
        printf("4 - Busca datos\n");
        printf("5 - Salir\n\n");
        printf("Ingrese una opcion (1 - 5): ");
        
        Opcion = getche(); // Lee el caracter y lo muestra, sin esperar Enter

        switch(Opcion)
        {
            case '1':
                Ingresa(&Inicio);
                break;

            case '2':
                Lee(&Inicio);
                break;

            case '3':
                Borra(&Inicio);
                break;

            case '4':
                Busca(&Inicio);
                break;

            case '5':
                exit(0); // Finaliza inmediatamente el programa
        }
    }
    return 0;
}

/* Inserta un nodo en forma ordenada de mayor a menor */
void Ingresa(struct Lis **Principio)
{
    /* *Actual   => Se usa para recorrer la lista.
     * *Nuevo    => Nodo recien creado.
     * *Anterior => Mantiene el nodo previo para poder enlazar.
     */
    struct Lis *Actual, *Nuevo, *Anterior;
    
    /* Reserva dinamica de memoria para el nuevo nodo.
     * Si malloc devuelve NULL => No hay memoria disponible
     */
    if (! (Nuevo = (struct Lis *)malloc(sizeof(struct Lis))))
    {
        printf("\n\nNo hay memoria disponible\n");
        printf("\n\nPresiones una tecla para continuar\n");
        getch(); // Espera que se presione una tecla.

        return;
    }

    /* Carga del dato en el nodo nuevo */
    printf("\n\nIngrrese el dato: ");
    scanf("%d", &Nuevo->Dato);

    /* Caso 1: Si la lista esta vacia.
     * El Nuevo nodo pasa a ser el primero.
     */
    if (!*Principio)
    {
        *Principio = Nuevo;
        Nuevo->Sig = NULL;

        return;
    }

    /* Inicializacion de punteros para recorrer */
    Anterior = *Principio;
    Actual = *Principio;

    /* Busca la posicion correcta para mantener la lista ordenada de mayor a menor.
     * Busca mientras:
     * - No llegue al final.
     * - Y el valor Actual sea mayor que el Nuevo.
     */
    while((Actual->Dato > Nuevo->Dato) && Actual) // Deberia ser while(Actual && (Actual->Dato > Nuevo->Dato)) Dato no existiria si no existe Actual!
    {
        Anterior = Actual;
        Actual = Actual->Sig;
    }

    /* Caso 2: Si se llego al final (Actual == NULL). Insertamos al final. */
    if (!Actual)
    {
        Anterior->Sig = Nuevo;
        Nuevo->Sig = NULL;

        return;
    }

    /* Caso 3: Si se inserta al principio.
     * Ocurre cuando el nuevo valor debe ir antes del primero.
     */
    if (Anterior == Actual)
    {
        *Principio = Nuevo;
        Nuevo->Sig = Anterior;

        return;
    }

    /* Caso4: Insercion intermedia
     * Se reconectan los enlaces:
     * Anterior => Nuevo => Actual
     */
    Anterior->Sig = Nuevo;
    Nuevo->Sig = Actual;
}

/* Recorre e imprime la lista */
void Lee(struct Lis **Principio)
{
    /* *Actual apunta a el primer nodo */
    struct Lis *Actual = *Principio;

    /* Recorre hasta que Actual sea NULL, desde inicio a NULL */
    while (Actual)
    {
        printf("\nEl dato es: %d\n", Actual->Dato);
        Actual = Actual->Sig;
    }

    printf("\n\nPresione una tecla para continuar\n");
    getch(); // Espera que se presione una tecla.
}

/* Elimina un nodo si existe, con pedido de confirmacion de la eliminacion */
void Borra(struct Lis **Principio)
{
    struct Lis *Actual, *Anterior;
    int Valor;
    char Opcion;

    /* Carga del dato a eliminar */
    printf("\nIngrese el dato a borrar: ");
    scanf("%d", &Valor);
    
    Actual = *Principio;
    Anterior = *Principio;

    /* Busca el nodo */
    while ((Valor != Actual->Dato) && Actual) // Lo mismo la condicion && esta invertida, Si Actual no existe, Dato no existira!
    {
        Anterior = Actual;
        Actual = Actual->Sig;
    }

    /* Si fue encontrado */
    if (Actual)
    {
        printf("\nEl dato es: %d\n\n", Actual->Dato);
        printf("\n\nDesea eliminar este dato (S / N)");

        Opcion = toupper(getche()); // Cambia a mayuscula lo ingresado y lo muestra y almacena en la variable

        if (Opcion == 'S')
        {
            /* Caso 1: Si es el primer nodo */
            if (Anterior == Actual)
            {
                *Principio = Actual->Sig; // El segundo nodo pasa a ser el primero
                free(Actual); // Libera la memoria del nodo eliminado.

                return;
            }
            
            /* Caso 2: Nodo intermedio o final */
            Anterior->Sig = Actual->Sig; // Se saltea el nodo a eliminar
            free(Actual); // Libera la memoria del nodo eliminado

            return;
        }

        return;
    }

    /* Si no se encontro */
    printf("\nEl dato no ha sido encontrado");
    printf("\n\nPresione una tecla para continuar\n");

    getch(); // Espera que se presione una tecla.

}

/* Busca un nodo por valor */
void Busca(struct Lis **Principio)
{
    struct Lis *Actual;
    int Valor;

    printf("\nIngrese el dato a buscar: ");
    scanf("%d", &Valor);

    Actual = *Principio;

    /* Recorre la lista buscando coincidencia */
    while ((Valor != Actual->Dato) && Actual) // Nuevamente && con condiiones invertidas
    {
        Actual = Actual->Sig;
    }

    /* Si fue encontrado */
    if (Actual)
    {
        printf("\nEl dato es: %d\n\n", Actual->Dato);
        printf("\n\nPresione una tecla para continuar\n");

        getch(); // Espera que se presione una tecla.

        return;
    }

    /* Si no fue encontrado */
    printf("\nEl dato no ha sido encontrado");
    printf("\n\nPresione una tecla para continuar\n");

    getch(); // Espera que se presione una tecla.
    
}

Lista Simple 03

Makefile

CC = gcc
CFLAGS = -std=c11 -Wall -Wextra -pedantic

PROG = main
OBJ = main.o

$(PROG): $(OBJ)
	$(CC) $(OBJ) -o $(PROG)

$(OBJ): main.c
	$(CC) $(CFLAGS) -c main.c

.PHONY: clean
clean:
	del $(OBJ) $(PROG).exe

Código:

// gcc -std=c11 -Wall -Wextra -pedantic main.c -o main

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h> // Se usa toupper()

/* Definicion de nodo de lista simplemente enlazada */
struct Lis
{
  int Dato; /* Valor almacenado en el nodo */
  struct Lis *Sig; /* Puntero al siguiente nodo */
};

/* Prototipos de funciones */
void Ingresa(struct Lis **);
void Lee(struct Lis **);
void Borra(struct Lis **);
void Busca(struct Lis **);
void Contar(struct Lis **);

int main(void)
{
  int Opcion;

  /* Inicializa la lista vacia */
  struct Lis *Inicio = NULL;

  /* Bucle infinito (menu) */
  for(;;)
  {
    system("cls"); /* Limpia la pantalla en Windows, en Linux "clear" */

    /* Menu de opciones */
    printf("1 - Ingresa datos\n");
    printf("2 - Lee datos\n");
    printf("3 - Borrar datos\n");
    printf("4 - Buscar datos\n");
    printf("5 - Contar nodos\n");
    printf("6 - Salir\n\n");
    printf("Ingrese una opcion ( 1 - 5 ) : ");

    /* Lee opcion como caracter */
    Opcion = getchar();

    /* Limpia buffer no estandar */
    fflush(stdin);

    switch(Opcion)
    {
    case '1':
      Ingresa(&Inicio);
      break;
    case '2':
      Lee(&Inicio);
      break;
    case '3':
      Borra(&Inicio);
      break;
    case '4':
      Busca(&Inicio);
      break;
    case '5':
      Contar(&Inicio);
      break;
    case '6':
      exit(0); // Finaliza programa
    }
  }
  return 0;
}

/* Inserta un nodo en la lista de forma ordenada */
void Ingresa(struct Lis **Principio)
{
  struct Lis *Actual, *Nuevo, *Anterior;

  /* Reserva memoria para un nuevo nodo */
  if (!(Nuevo = (struct Lis *)malloc(sizeof(struct Lis))))
  {
    printf("\n\nNo hay memoria disponible\n");
    system("pause");
    return;
  }

  /* Carga el dato en el nuevo nodo */
  printf("\n\nIngrese el dato : ");
  scanf("%d", &Nuevo->Dato);
  fflush(stdin);

  /* Caso lista vacia */
  if (!*Principio)
  {
    *Principio = Nuevo;
    Nuevo->Sig = NULL;
    return;
  }

  /* Recorre la lista para ubicar posicion ordenada */
  Anterior = *Principio;
  Actual = *Principio;

  while (Actual && (Actual->Dato < Nuevo->Dato))
  {
    Anterior = Actual;
    Actual = Actual->Sig;
  }

  /* Insertar al final */
  if (!Actual)
  {
    Anterior->Sig = Nuevo;
    Nuevo->Sig = NULL;
    return;
  }

  /* Insertar al inicio */
  if (Anterior == Actual)
  {
    *Principio = Nuevo;
    Nuevo->Sig = Anterior;
    return;
  }

  /* Insertar en el medio */
  Anterior->Sig = Nuevo;
  Nuevo->Sig = Actual;
}

/* Recorre y muestra todos los nodos */
void Lee(struct Lis **Principio)
{
  struct Lis *Actual = *Principio;
  while (Actual)
  {
    printf("\nEl dato es : %d\n", Actual->Dato);
    Actual = Actual->Sig;
  }
  system("pause");
}

/* Busca y elimina un nodo por valor */
void Borra(struct Lis **Principio)
{
  struct Lis *Actual, *Anterior;
  int Valor;
  char Opcion;

  printf("\nIngrese el dato a borrar : ");
  scanf("%d", &Valor);
  fflush(stdin);

  Actual = *Principio;
  Anterior = *Principio;

  /* Busca el nodo */
  while (Actual && (Valor != Actual->Dato))
  {
    Anterior = Actual;
    Actual = Actual->Sig;
  }
  /* Si lo encontro */
  if (Actual)
  {
    printf("\nEl dato es : %d\n\n", Actual->Dato);
    printf("\n\nDesea eliminar este dato (S / N) ");

    Opcion = toupper(getchar());
    fflush(stdin);
    
    if (Opcion == 'S')
    {
      /* Si es el primer nodo */
      if (Anterior == Actual)
      {
        *Principio = Actual->Sig;
        free(Actual);
        return;
      }

      /* Nodo intermedio o final */
      Anterior->Sig = Actual->Sig;
      free(Actual);
      return;
    }
    return;
  }

  printf("\nEl dato no ha sido encontrado\n\n");
  system("pause");
}

/* Busca un nodo y muestra su direccion */
void Busca(struct Lis **Principio)
{
  struct Lis *Actual;
  int Valor;

  printf("\nIngrese el dato a buscar : ");
  scanf("%d", &Valor);
  
  Actual = *Principio;
  
  /* Recorre hasta encontrar */
  while (Actual && (Valor != Actual->Dato))
    Actual = Actual->Sig;
  
  if (Actual)
  {
    printf("\nEl dato es : %d\tSu ubicacion es : %p\n\n", Actual->Dato, Actual); // Castear a (void *)Actual
    
    system("pause");
    return;
  }

  printf("\nEl dato no ha sido encontrado\n\n");
  system("pause");
}

/* Cuenta la cantidad de nodos de la lista */
void Contar(struct Lis **Principio)
{
  int Contador = 0;
  struct Lis *Actual;
  Actual = *Principio;

  /* Recorre toda la lista */
  while (Actual)
  {
    Contador++;
    Actual = Actual->Sig;
  }
  
  printf("\n\nLa cantidad de nodos de la lista es : %d\n\n", Contador);
  system("pause");
}