[C] Liste circolari

[lucas87]

Salve ho un problema con le liste circolari.
Praticamente per la ricerca ho implementato la seguente funzione:

struct list *cerca(struct list *L, int x)
{
	struct list *L2 = L;

	/* se la lista è vuota, restituisce NULL  */
	if (L == NULL) return NULL;

	/* per ogni elemento della lista */
	do
	{
		if (L2->el == x) return L2;

		/* elemento successivo */
		L2 = L2->next;
	} while(L2 != L);

	return NULL;
}

Quindi la lista passata alla funzione è L, poi faccio un nuovo puntatore alla lista L che si chiama L2 e effettuo la ricerca finche L!=L2, dove però L2 dovrebbe partire a puntare al primo elemento e L dovrebbe rimanere fisso a puntare all'ultimo elemento.

COme faccio a farlo puntare all'ultimo elemento?

Grazie in anticipo. se non vi è chiaro qualcosa contattatemi, sono sempre connesso.

[lucas87]

Help please!!!

[cionci]

Mi sembra che vada benissimo così come è scritto..
L punta al primo elemento da controllare, ma è anche il primo elemento già controllato nella ricerca
Infatti L2 parte da L e quando ritorna (la lista è circolare) ad L significa che hai controllato tutti gli elementi ed il ciclo finisce correttamente.

[lucas87]

giusto, non ci avevo pensato che comuqnue sarebbe arrivato a L lo stesso, il problema è che nella fase di esecuzione crasha tutto.

[cionci]

Ad occhio non è quello il codice che ti fa crashare... Chiaramente se a quel codice gli passi una lista non circolare ti crasha...

[lucas87]

Io gli ho passato una lista concatenata, perchè pensavo che si dichiarassero =.

posto tutto il prog, vedi se la lista che gli passo è giusta o no:

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

struct list {
       int el;
       struct list *next;
};


typedef struct list ELEMENT;
typedef ELEMENT *LINK;

LINK carica(LINK,int);
LINK cerca(LINK,int);

int main (void) {
    LINK L;
    int n_el,x;
    printf("Inserisci numero elementi da inserire");
    scanf("%d",&n_el);
    carica(L,n_el);
    printf("Inserisci l'elemento da cercare");
    scanf("%d",&x);
    if(x == cerca(L,x)) printf("Elemento %d presente nella lista",x);

    system ("PAUSE");
    return 0;
}


/*INSERISCE N ELEMENTI IN UNA LISTA CONCATENATA CIRCOLARE*/
LINK carica(LINK L, int n){
     if (n==0) return NULL;
     else {
          L=malloc(sizeof(ELEMENT));
          printf("inserisci l' elemento nella lista\n");
          scanf("%d",&L->el);
          L->next=carica(L,n-1);
          return L;
     }
}

/*CERCA UN ELEMENTO IN UNA LISTA CONCATENATA CIRCOLARE*/
LINK cerca(LINK L, int x)
{
	LINK L2 = L;

	/* se la lista è vuota, restituisce NULL  */
	if (L == NULL) return NULL;

	/* per ogni elemento della lista */
	do
	{
		if (L2->el == x) return L2;

		/* elemento successivo */
		L2 = L2->next;
	} while(L2 != L);

	return NULL;
}

grazie

[cionci]

La differenza fra una lista concatenata ed una lista circolare è che in quella circolare l'ultimo elemento della lista deve puntare alla testa invece che a NULL.
Anche se il concetto di testa piano piano sparisce

[lucas87]

Questo lo so, ma io chiedo se nella dichiarazione di una lista tra una lista concatenata e una circolare cambia qual cosa e se si cosa?

grazie

[cionci]

No, non cambia assolutamente niente, l'unica differenza è nell'inizializzazione, in cui il campo next dell'ultimo elemento deve puntare alla testa e non a null (come fai nel codice).

[lucas87]

Potresti indicarmi dove lo faccio puntare a NULL nel codice? NOn lo trovo

grazier

[cionci]

LINK carica(LINK L, int n){
     if (n==0) return NULL;
     else {
          L=malloc(sizeof(ELEMENT));
          printf("inserisci l' elemento nella lista\n");
          scanf("%d",&L->el);
          L->next=carica(L,n-1);
          return L;
     }
}

Quando arrivi all'ultimo elemento ritorni NULL, invece avresti dovuto ritornare l'elemento in testa.
Comunque io per un lista circolare inizializzerei la lista tramite un inserimento in testa.
In questo modo sei sicuro di mantenere sempre la lista consistente...

Inoltre mi sembra di vedere un altro problema, devi fare così nel main:

L = carica(L,n_el);

altrimenti il valore di L non viene modificato e rimane sempre pari a NULL

[lucas87]

Niente non riesco a farlo andare.
Non è che mi fai creazione inserimento caricamento di una lista circolare tipo quello che ho fatto io ma funzionante?
Se puoi.

Gazrie

[cionci]

Primo suggerimento: non mescolare mai l'input con gli algoritmi, un input ricorsivo non è bellissimo

LINK carica_elemento_in_testa(LINK old, int valore)
{
   LINK head = (LINK)malloc(sizeof(ELEMENT));
   head->el = valore;
   
   if(old == NULL)
      old = head;
   
   head->next = old;

   return head;      
}

Poi ovviamente nel main dovrai inserire un for in cui chiederai in input l'intero e poi lo passerai alla funzione sopra.

Nel main definisci:

LINK head = NULL;

Quindi nel for dopo l'input con scanf richiama la funzione sopra così:

head = carica_elemento_in_testa(head, valore_letto);

Ovviamente tutto non compilato e passibile di sviste

[lucas87]

In teoria ora va il caricamneto, ma non va la stampa se come consizione metto che il puntatore che si muove L2 deve tornare alla posizione iniziale ed essere = al puntatore che rimane fermo L.
Se uso un for per stampare va,anche se con l'inserimento che mi stai facendo fare tu sembra di caricare uno stak e infatti la stampa la fa diciamo al contrario.

[cionci]

Sì, è chiaro, facendo l'inserimento in testa si carica al contrario, ma non mi sembra che tu abbia vincoli da questo punto di vista, no ? Per la stampa comunque se vuoi mantenere l'ordine di inserimento puoi fare una visita posticipata...

Che ti succede con la ricerca che avevi fatto sopra ? Ti si pianta ?

[lucas87]

Si ora la ricerca va che è una mervaiglia. grazie.
ti linko anche questo post, magari sai darmi un consiglio

http://www.hwupgrade.it/forum/showth...6#post16578656

grazie