Dudas con Listas Enlazadas

[traviatØ]

Hola, sucede que estaba analizando este codigo y lo entiendo casi en su totalidad sin embargo existen unas lineas donde tengo dudas (no entiendo claramente), las cuales estan señaladas con comentarios:

Código (c) [Seleccionar] Expandir

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

struct listNode {
      char data;
      struct listNode *nextPtr;
};

typedef struct listNode LISTNODE;
typedef LISTNODE *LISTNODEPTR;

void insert(LISTNODEPTR *, char);
char delete(LISTNODEPTR *, char);
int isEmpty(LISTNODEPTR);
void printList(LISTNODEPTR);
void instructions(void);

main()
{
     LISTNODEPTR startPtr = NULL;
     int choice;
     char item;
     instructions();
     printf("? ");
     scanf("%d", &choice);
   
     while (choice != 3) {
         
           switch (choice) {
                  case 1:
                       printf("Enter a character: ");
                       scanf("\n%c", &item);
                       insert(&startPtr, item);
                       printList(startPtr);
                       break;
                  case 2:
                       if (!isEmpty(startPtr)) {
                           printf("Enter character to be deleted: ");
                           scanf("\n%c", &item);
                         
                           if (delete(&startPtr, item)) {
                               printf("%c deleted.\n", item);
                               printList(startPtr);
                           }
                           else
                               printf("%c not found.\n\n", item);
                       }
                       else
                           printf("List is empty.\n\n");
                         
                       break;
                  default:
                      printf("Invalid choice.\n\n");
                      instructions();
                      break;
           }
         
           printf("? ");
           scanf("%d", &choice);
     }
   
     printf("End of run.\n");
     system("pause");
     return 0;
}

void instructions(void)
{
    printf("Enter your chice:\n"
    "   1 to insert an element into the list.\n"
    "   2 to delete an element from the list.\n"
    "   3 to end.\n");
}

void insert(LISTNODEPTR *sPtr, char value)
{
    LISTNODEPTR newPtr, previewPtr, currentPtr;
   
    newPtr = malloc(sizeof(LISTNODE));
   
    if (newPtr != NULL) {
               newPtr->data = value;
               newPtr->nextPtr = NULL;
             
               previousPtr = NULL;
               currentPtr = *sPtr;
             
               while (currentPtr != NULL && value > currentPtr->data) {
                     previousPtr = currentPtr;
                     currentPtr = currentPtr->nextPtr;
               }
             
               if (previousPtr == NULL) {
                              newPtr->nextPtr = *sPtr; //¿Para que es esta linea?, si sPtr se usa por primera ves con NULL, entonces aqui newPTr.nextPtr valdra NULL?
                              *sPtr = newPtr; // Como es esta linea no entiendo
               }
               else {
                    previousPtr->nextPtr = newPtr; // Para que es esto?
                    newPtr->nextPtr = currentPtr; // y Esto para que se hace? una explicacion detallada por favor
               }
    }
    else
        printf("%c not inserted. No memory available.\n", value);
}

char delete(LISTNODEPTR *sPtr, char value)
{
    LISTNODEPTR previousPtr, currentPtr, tempPtr;
   
    if(value == (*sPtr)->data) { // Porque se usan parentesis en *aPtr ? , no es valido sPtr.data? o sPtr->data?
             tempPtr = *sPtr
             *sPtr = (*sPtr)->nextPtr; //Parentesis para que?
             free(tempPtr);
             return value;
    }
    else {
         previousPtr = *sPtr;
         currentPtr : (*sPtr)->nextPtr; //Parentesis para que?
       
         while (currentPtr != NULL && currentPtr->data != value) {
               previousPtr = currentPtr;
               currentPtr = currentPtr->nextPtr;
         }
       
         if (currentPtr != NULL) {
                        tempPtr = currentPtr;
                        previousPtr->nextPtr = currentPtr->nextPtr;
                        free(tempPtr);
                        return value;
         }
    }
   
    return '\0';
}

int isEmpty(LISTNODEPTR sPtr)
{
   return sPtr == NULL;
}

void printList(LISTNODEPTR sPtr)
{
    if (currentPtr == NULL)
        printf("List is empty.\n\n");
    else {
         printf(The list is:\n");
       
         while (currentPtr != NULL) {
               printf("%c --> ", currentPtr->data);
               currentPtr = currentPtr->nextPtr;
         }
       
         printf("NULL\n\n");
    }
}

Agradecido por su valiosa explicacion

Un saludo  

[BatchianoISpyxolo]

Código (c) [Seleccionar] Expandir

void insert(LISTNODEPTR *sPtr, char value)
{
    LISTNODEPTR newPtr, previewPtr, currentPtr;

    newPtr = malloc(sizeof(LISTNODE));

    if (newPtr != NULL) {
               newPtr->data = value;
               newPtr->nextPtr = NULL;

               previousPtr = NULL;
               currentPtr = *sPtr;

               while (currentPtr != NULL && value > currentPtr->data) {
                     previousPtr = currentPtr;
                     currentPtr = currentPtr->nextPtr;
               }

               if (previousPtr == NULL) {
                              newPtr->nextPtr = *sPtr; //¿Para que es esta linea?, si sPtr se usa por primera ves con NULL, entonces aqui newPTr.nextPtr valdra NULL?
                              *sPtr = newPtr; // Como es esta linea no entiendo
               }
               else {
                    previousPtr->nextPtr = newPtr; // Para que es esto?
                    newPtr->nextPtr = currentPtr; // y Esto para que se hace? una explicacion detallada por favor
               }
    }
    else
        printf("%c not inserted. No memory available.\n", value);
}

La idea es tener una lista simplemente ordenada y esa función inserta ordenadamente.

*sPtr no es NULO. *sPtr es un puntero a un nodo que se pasa a la función. En general sería el puntero al primer nodo de la lista, es decir el puntero cabecera. Si fuera NULO, la lista estaría vacía. Hay listas que se implementan de manera que al crear la lista ya añadas un Nodo. Todo depende de la implementación que se siga.

Luego verificas si hay memoria, creas el nodo y lo inicializas tatatata...

Con el while recorres la lista enlazada y este ciclo terminará cuando el puntero siguiente de un nodo actual apunte a NULO o también cuando el valor que quieras insertar sea mayor que el valor del nodo actual.

Si previousPtr está a NULL al salir del bucle es que la lista está vacía o hay que insertar en la primera posición.

Código (c) [Seleccionar] Expandir

newPtr->nextPtr = *sPtr;
*sPtr = newPtr;

Verás que sencillo es de enteder.

Si la lista está vacía, *sPtr será NULO y el siguiente del nodo creado apuntará a NULO. Luego hacemos que el puntero cabecera de la lista *sPtr apunte al nuevo nodo creado de tal manera que habrás insertado un nodo en una lista vacía.

*sPtr----->[newPtr]----->NULO

En el caso de que haya uno o más elementos. Imagina que haces *sPtr = newPtr;. En este caso PERDERÁS LA REFERENCIA A LA LISTA y habrás estropeado tu estructura. Entonces al hacer primero newPtr->nextPtr = *sPtr; te aseguras de que el nuevo nodo creado apunte a la cabeza de la lista y luego tú puedas apuntar con *sPtr a newPtr de tal manera que no perderás la referencia a la lista e insertarás en la primera posición:

Inicialmente: *sPtr----->[newPtr]----->[newPtr2]----->[newPtr3]----->[newPtr4]----->[newPtrN]----->NULO

Hacemos: newPtr->nextPtr = *sPtr;

Entonces: newPtr->nextPtr----->[newPtr]----->[newPtr2]----->[newPtr3]----->[newPtr4]----->[newPtrN]----->NULO

Y finalmente hacemos *sPtr = newPtr;

Entonces: *sPtr----->newPtr->nextPtr----->[newPtr]----->[newPtr2]----->[newPtr3]----->[newPtr4]----->[newPtrN]----->NULO



Por último como previousPtr no es nulo pues haces una inserción en el medio de la lista o al final.

Código (c) [Seleccionar] Expandir

previousPtr->nextPtr = newPtr;
newPtr->nextPtr = currentPtr;

Entonces ahora piensa que tienes que insertar por el medio, tendrás un nodo "anterior" y un nodo "posterior"

Entonces la idea es: [NodoAnterior]------>[NuevoNodoAInsertar]------>[NodoPosterior]

Entonces: previousPtr->nextPtr = newPtr; <= Es la unión NodoAnterior ------> NuevoNodoAInsertar

y newPtr->nextPtr = currentPtr; <= Es la unión NuevoNodoAInsertar ------> NodoPosterior


Por último si insertas al final.

La idea es: [UltimoNodo]------>[NuevoNodoAInsertar]------>NULO <= En este caso currentPtr sería NULO en vez de tener una referencia a un nodo interno distinta del primer nodo.

En la función del delete es necesario usar:

Código (c) [Seleccionar] Expandir

(*sPtr)->data

La función recibe un LISTNODEPTR *sPtr, por tanto deberás usar *sPtr dentro de la función

Por otra parte, el operador de indirección -> tiene prioridad sobre el operador *, por lo que si no pones paréntesis, esa línea será tomada como:

Código (c) [Seleccionar] Expandir

*(sPtr->data)

Y eso no tienen ningún sentido. En cambio:

Código (c) [Seleccionar] Expandir

(*sPtr)->data

Sí que tiene porque con (*sPtr) haces referencia a ese puntero y luego con -> data accedes al campo data de la struct Nodo apuntada por el puntero *sPtr.

Perdón si te lío pero esa es la explicación.

¡Saludos!

[traviatØ]

muy amable hermano, estoy agradecido, ya leere lo que has escrito  gracias  saludos