Foro de elhacker.net

He desarrollado el código de mi lista doblemente ligada pero ahora quisiera implementarla de forma circular. No comprendo exactamente que diferencias tienen con la circular ya que yo lo veo de la misma manera. PD: No me lo he robado >:(

Esta algo largo pero necesito implementarlo de varias maneras para que sea completo se que le falta pero no quiero complicarme la vida.

#include <stdio.h>
#include <stdlib.h>
 
enum opcion {EXIT,INSERT,FIND,DELETE,SHOW,CURR,NEXT,PREV,FINDPREV,FINDNEXT};
 
struct nodo {
    char nombre[40];
    struct nodo *next;
    struct nodo *prev;
};
 
struct nodo *crearNodo () {
    struct nodo *x;
    x= (struct nodo *) malloc (sizeof (struct nodo));
    printf ("Nombre: ");
    gets (x->nombre);
    x->next=NULL;
    x->prev=NULL;
    return x;
}
 
struct nodo *buscar (struct nodo *lista, char *k) {
    if (lista == NULL) return NULL; 
    while (lista) {
        if (strcmp (lista->nombre,k) == 0)
            break;
        lista= lista->next;
    }
    return lista;
}
 
struct nodo *buscar_sig (struct nodo *act) {
	char *k = act->nombre;
    if (act == NULL) return NULL;
 
     act= act->next;
     while (act) {
        if (strcmp (act->nombre,k) == 0)
        	 break;    
        	 act= act->prev;
        }
        return act;
     }
 
 
struct nodo *buscar_ant (struct nodo *act) {
	char *k = act->nombre;
    if (act == NULL) return NULL;
 
     act= act->prev;
     while (act) {
        if (strcmp (act->nombre,k) == 0)
        	 break;    
        	 act= act->prev;
        }
        return act;
     }
// operacion eliminar: elimina el primer nodo que coincida con la llave k
// recibe referencia del apuntador al inicio de la lista y llave a eliminar
// devuelve el nodo eliminado o null si no se encuentra el nodo 
 
struct nodo *borrar (struct nodo **lista, char *k) {
    struct nodo *ant, *act;
 
    if (*lista == NULL) return NULL;
 
    act= *lista;
    ant= *lista;
    while (act != NULL) {
        if (strcmp (act->nombre,k) == 0) // nodo encontrado
            break;
        ant= act;
        act= act->next;                      // avance al sig. nodo
    }
    if (act == NULL) return NULL;
 
    // Si se encontro el nodo
    if (act == *lista)  {               // Si es el primer nodo
        *lista= act->next;               // Se mueve el aptdor. al inicio de la lista al siguiente nodo 
        if (act->next)
            act->next->prev= NULL;
    }
    else {
        ant->next= act->next;         // Se liga el nodo antecesor con el nodo sucesor del nodo a eliminar
        act->prev= ant;
    }
    return act;
}
 
 
void listar (struct nodo *lista) {
    if (lista == NULL) {
        printf ("Lista vacia\n");
        return;
    }
    do {
        if (lista->prev && lista->next)
            printf ("<-%s->",lista->nombre);
        else if (lista->prev == NULL && lista->next == NULL)
            printf ("%s",lista->nombre);
        else if (!lista->next)
            printf ("<-%s",lista->nombre);
        else if (!lista->prev)
            printf ("%s->",lista->nombre);
        lista= lista->next;
    }
    while (lista != NULL);
    printf ("\n");
}
struct nodo *insertar (struct nodo *head, struct nodo *x) {
    if (head != NULL) {     //Tiene elementos
        head->prev= x;       // El antecesor al primer nodo de la lista apunta al nuevo nodo
        x->next= head;       // El sucesor del nuevo nodo apunta al primer nodo de la lista
        //x->prev=
 
    }
 
    head= x;                // El inicio de la lista apunta al nuevo nodo
 
    return head;
}
 
struct nodo *curr (struct nodo *actual) {
    if (actual) {
        printf ("%s\n",actual->nombre);
        return actual;
    }
    printf ("No hay nodo actual\n");
 
    return actual;
}
 
struct nodo *prev (struct nodo *actual) {
    if (actual && actual->prev) {
        printf ("%s\n",actual->prev->nombre);
        return actual->prev;
    }
    printf ("No hay nodo anterior\n");
 
    return actual;
}
struct nodo *next (struct nodo *actual) {
    if (actual && actual->next) {
        printf ("%s\n",actual->next->nombre);
        return actual->next;
    }
    printf ("No hay nodo siguiente\n");
 
    return actual;
}
int main ()
{
    char nombre[40];
    enum opcion op= EXIT;
    struct nodo *x,*act=NULL;
    struct nodo *head= NULL;
    struct nodo *tail= NULL;
 
    while (1) {
        system ("cls");
        printf ("1. Insertar\n");
        printf ("2. Buscar\n");
        printf ("3. Borrar\n");
        printf ("4. Listar\n");
        printf ("5. Actual\n");
        printf ("6. Siguiente\n");
        printf ("7. Anterior\n");
        printf ("8. Buscar Anterior \n");
        printf ("9. Buscar Siguiente\n");
        printf ("0. Salir\n");
        printf ("\nOpcion: ");
        scanf ("%d", &op);
        fflush (stdin);
 
        switch (op) {
            case INSERT:
                x= insertar (head,crearNodo ());
                if (head == NULL)
                tail=x;
                tail->next=x;
                head=x;
                head->prev =tail;
                act= head;
                break;
            case FIND:
                printf ("Buscar: ");
                gets (nombre);
                act= buscar (head,nombre);
                if (act == NULL)
                    printf ("No se encuentra: %s\n", nombre);
                else
                    printf ("Se encuentra: %s\n", nombre);
                system ("pause");
                break;
            case DELETE:
                printf ("Buscar: ");
                gets (nombre);
                x= borrar (&head,nombre);
                if (x != NULL) {
                    printf ("Se elimino: %s\n", x->nombre);
                    if (x == act) act= NULL;
                }
                else
                    printf ("No se encuentra: %s\n", nombre);
                system ("pause");
                break;              
            case SHOW:
                listar (head);
                system ("pause");
                break;
            case CURR:
                curr (act);
                system ("pause");
                break;
            case NEXT:
                act= next (act);
                system ("pause");
                break;
            case PREV:
                act= prev (act);
                system ("pause");
                break;
            case FINDNEXT:    
                x= buscar_sig (act);
                if (x != NULL) {
                    printf ("Se encontro: %s\n", x->nombre);
                    act=x;
                }
                else
                    printf ("No se encuentra: %s\n", nombre);
                system ("pause");
                break; 
            case FINDPREV:
        		 x= buscar_ant (act);
                if (x != NULL) {
                    printf ("Se encontro: %s\n", x->nombre);
                    act=x;
                }
                else
                    printf ("No se encuentra: %s\n", nombre);
                system ("pause");
                break; 
            case EXIT:
                return;
            default:
                printf ("Opcion invalida\n");
        }
    }       
}
 

La única diferencia, es que el nodo "siguiente" del nodo final, es el primero. Y el nodo "anterior" del primer nodo, es el último. Está conectada la cola con la cabeza.

Eso sí, hay q hacer ligeros cambios. por ejemplo, no puedes hacer un:

while(ptr->next != NULL){
    // ...
    ptr = ptr->next;
}

Porque si la lsita tiene elementos, qerá un bucle infinito.
Quitando esos cambios, el resto es parecido.

Gracias por la notacion.