Linked List

[michellcrh]

Hola.
No puedo generar el algoritmo para la función insertAfter, la cual inserta un elemento después de otro, según la llave tecleada.
Espero me puedan ayudar por favor.

Código (c) [Seleccionar] Expandir

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <locale.h>
// Definición de variables globales
struct node {
   int data;
   struct node *next;
};
struct node *start = NULL; // start es el pointer al primer nodo
struct node *found = NULL; // found es el pointer al nodo encontrado
int count = 0; // Número de nodos
// Definición de funciones
void insertFirst(int); // Inserta un nodo al principio de la lista
void insertLast(int); // Inserta un nodo al final de la lista
void insertAfter(int, int); // Inserta un nodo después de otro
int find(int); // Buscar un nodo
void traverse(); // Realiza el recorrido de la lista
void deleteFirst(); // Remueve el primer nodo de la lista
void deleteLast(); // Remueve el último elemento de la lista
void create(); // Función auxiliar, crea una lista

int main () {
    int dato, opcion;
    setlocale(LC_ALL, ""); // para caracteres del Español
    printf(" 1 - Insertar al inicio de la linked list.\n");
    printf(" 2 - Insertar al final de la linked list.\n");
    printf(" 3 - Insertar después de otro.\n");
    printf(" 4 - Buscar un nodo en la lista.\n");
    printf(" 5 - Desplegar la linked list (traverse).\n");
    printf(" 6 - Borrar elemento al inicio\n");
    printf(" 7 - Borrar elemento al final.\n");
    printf(" 8 - Terminar\n");
    create(); // crea una lista de prueba
    while (true) {
        printf("Teclee la opción: ");
        scanf("%d", &opcion);
        switch (opcion) {
        case 1: // insertar al inicio
            printf("Teclee valor del elemento a insertar al inicio\n");
          scanf("%d", &dato);
          insertFirst(dato);
            break;
        case 2: // insertar al final
            printf("Teclee valor del elemento a insertar al final\n");
          scanf("%d", &dato);
          insertLast(dato);
            break;
        case 3: // insertar después
            printf("Teclee valor de la llave.\n");
          scanf("%d", &dato);
          int llave = find(dato);
          if (llave == -2) { // find regresa -2 si la lista está vacía
          break;
}
          if(llave == -1) { // find regresa -1 si no se encuentra
          printf("No se encontró %d en la lista.\n", dato);
          break;
}
          printf("Teclee valor de nodo a insertar después de llave.\n");
          scanf("%d", &dato);
          int nuevo = find(dato);
insertAfter(llave, dato);
            break;
        case 4: // buscar
            printf("Teclee valor del elemento a buscar.\n");
          scanf("%d", &dato);
          int encontrado = find(dato);
          if (encontrado == -2) { // find regresa -2 si la lista está vacía
          break;
}
          if(encontrado == -1) { // find regresa -1 si no se encuentra
          printf("No se encontró %d en la lista.\n", dato);
} else {
printf("Se encontró %d en la lista.\n", dato);
}
            break;
        case 5: // recorrer
        traverse();
            break;
        case 6: // borrar el primero
            deleteFirst();
            break;
        case 7: // borrar el último
            deleteLast();
            break;
        case 8:
            printf("Gracias por participar");
            exit(0);
        default:
            printf("Opción inválida, intente de nuevo\n");
  }
    }
   return 0;
}

void insertFirst(int dato) {
   struct node *t;
   t = malloc(sizeof(struct node));  // ubica memoria para el nodo
   count++;
   if (start == NULL) { // primera vez
      start = t;
      start->data = dato;
      start->next = NULL;
      return;
   }
   t->data = dato;
   t->next = start;
   start = t;
}

void insertLast(int dato) {
   struct node *t, *temp;
   t = malloc(sizeof(struct node));
   count++;
   if (start == NULL) { // Primera vez
      start = t;
      start->data = dato;
      start->next = NULL;
      return;
   }
   temp = start;
   while (temp->next != NULL) {  // busca el último nodo
      temp = temp->next;
   }
   temp->next = t;
   t->data = dato;
   t->next = NULL;
}

void insertAfter(int llave, int dato) {

   


}

int find(int datoBuscado) {
struct node *temp;
    temp = start;
    if (temp == NULL) {
      printf("Linked list vacía.\n");
      return -2;
   }
    while (temp->next != NULL) {  // busca
      if(temp->data == datoBuscado) {
      found = temp;
  return temp->data;
  } else {
  temp = temp->next;
  }
    }
    if(temp->data == datoBuscado) { // en caso de que sea el último
    found = temp;
      return temp->data;
}
return -1;
}

void traverse() {
   struct node *t;
   t = start;
   if (t == NULL) {
      printf("Linked list vacía.\n");
      return;
   }
   printf("Hay %d elemento(s) en la linked list.\n", count);
   while (t->next != NULL) {
      printf("%d -> ", t->data);
      t = t->next;
   }
   printf("%d\n", t->data);
}

void deleteFirst() {
   struct node *t;
   int n;
   if (start == NULL) {
      printf("Linked list vacía.\n");
      return;
   }
   n = start->data;
   t = start->next;
   free(start);
   start = t;
   count--;
   printf("%d eliminado del inicio de la linked list.\n", n);
}

void deleteLast() {
   struct node *t, *u;
   int n;
   if (start == NULL) {
      printf("Linked list vacía.\n");
      return;
   }

   count--;

   if (start->next == NULL) { // un solo nodo en la lista
      n = start->data;
      free(start);
      start = NULL;
      printf("%d eliminado del final de la linked list.\n", n);
      return;
   }

   t = start;

   while (t->next != NULL) {
      u = t;
      t = t->next;
   }

   n = t->data;
   u->next = NULL;
   free(t);

   printf("%d eliminado del final de la linked list.\n", n);
}

void create() {
insertFirst(444);
insertFirst(333);
insertFirst(222);
insertFirst(111);
}


[AlbertoBSD]

Pues claro que no lo puedes generar por que esta vacía esa función.

Código (c) [Seleccionar] Expandir

void insertAfter(int llave, int dato) {

}

Llevas algo de ese parte ?

[michellcrh]

Si, ya llevo una parte, la adjunto a continuación, pero mi problema es que si inserta el número después del número que le pido, pero los elementos que estaban después ya no los imprime.

Código (c) [Seleccionar] Expandir

void insertAfter(int llave, int dato) {
    struct node *l,*t;
    l = malloc(sizeof(struct node));
    count++;
     if (start == NULL) { // Primera vez
      start = t;
      start->data = dato;
      start->next = NULL;
      return;
   }
    found->data = llave;
    l->data = dato;
    found->next = l;

}


[AlbertoBSD]

pero los elementos que estaban después ya no los imprime.

Código (c) [Seleccionar] Expandir

void insertAfter(int llave, int dato) {
    struct node *l,*t;


Código (c) [Seleccionar] Expandir


     if (start == NULL) { // Primera vez
      start = t;//t en este punto no esta inicializado a nada.


[michellcrh]

Si, lo modifiqué, pero sigo con el mismo problema

Código (c) [Seleccionar] Expandir

void insertAfter(int llave, int dato) {
    struct node *l;
    l = malloc(sizeof(struct node));
    count++;
     if (start == NULL) { // Primera vez
      start = l;
      start->data = dato;
      start->next = NULL;
      return;
   }
    found->data = llave;
    l->data = dato;
    found->next = l;
   
}

[AlbertoBSD]

El problema que tienes es el siguiente, imagina que tienes una lista como la que sigue

[1]->[2]->[3]->[4]

Y quieres insertar uno nuevo después de [1] efectivamente después de [1] estas insertando un [5] pero a [5] nunca le dices que el Next es [2] y por lo tanto se pierde el "Link" que tenían y deja de ser linked list...

Espero que con eso veas como solucionarlo.

Los pasos son, guardar el next después de [1] y agregarlo al elemento que acabas de agregar en este caso seria [5]->next = [2]


Saludos!

[michellcrh]

Muchas Gracias, ya lo resolví. Excelente explicación.

[AlbertoBSD]

De que, siempre que tengas problemas con este tipo de estructuras utiliza algun diagrama para validar lo que estás haciendo, ayuda muchísimo.

Saludos!