Loop in lista unidirezionale in spazio costante

[rand]

Ciao, questo è un classico: descrivere un algoritmo che usi spazio costante e tempo lineare per decidere se in una lista concatenata unidirezionale è presente un ciclo o no.
A scanso di equivoci una lista concatenata è un insieme di oggetti ciascuno avente un puntatore al successivo. Un ciclo in una lista concatenata è un sottoinsieme degli elementi ciascuno dei quali punta a quello che lo segue nel ciclo e l'ultimo di essi punta al primo. Il vostro algoritmo può usare solo un numero di variabili finito e indipendente dalla dimensione della lista.

[MindFlyer]

Carino, ci provo:

Codice: Seleziona tutto

L1 := testa_lista;
L2 := L1;
N := 1;
repeat forever,
   for I :=1 to N,
      if L2 = null,
         return "La lista non contiene cicli"
      end if;
      L2 := L2->next;
      if L1 = L2,
         return "La lista contiene un ciclo"
      end if;
   end for;
   L1 := L2;
   N := N+N;
end repeat;

Uso 4 variabili, e il corpo del ciclo for viene eseguito al più 2*lunghezza_lista volte.

[ipparco]

Due domande, una per rand e una per MindFlyer.
Per rand: la lunghezza della lista è un parametro noto, che si può usare all'interno della routine, oppure no ?
Per MindFlyer: sei sicuro che funzioni ? A me sembra che controlli solo se ci sono cicli che cominciano dal primo elemento, dal secondo, dal quarto, dall'ottavo, ecc..., e che non controlli tutti i cicli possibili.

[rand]

La dimensione della lista intesa come numero dei suoi oggetti non è nota, se lo fosse il problema ammetterebbe la soluzione banale di visitare la lista e dire che il loop esiste se visitiamo un numero di elementi maggiore della dimensione della lista stessa.

[MindFlyer]

Per MindFlyer: sei sicuro che funzioni ?

Sì.

[MindFlyer]

ipparco, ti ho tradotto il mio pseudocodice in C, spero che tu lo possa compilare e testare.

Codice: Seleziona tutto

#include <stdio>

typedef struct lista{
	struct lista *next;
} lista;

int ciclo(lista *L) {
	lista *L1=L;
	lista *L2=L1;
	int N=1, I;

	for(;;) {
		for(I=1; I<=N; I++) {
			if(L2==NULL) return 0;
			L2=L2->next;
			if(L1==L2) return 1;
		}
		L1=L2;
		N=N+N;
	}
}

int Lunghezza=30;
int Raccordo=10; /* -1 --> nessun ciclo */

void main(void){
	lista L[Lunghezza];
	int I;
	for(I=0; I<Lunghezza>=0)
		L[Lunghezza-1].next=&L[Raccordo];
	else L[Lunghezza-1].next=NULL;
	if(ciclo(L))
		printf("La lista ha un ciclo.");
	else printf("La lista non ha cicli.");
}

La variabile Lunghezza è la lunghezza della lista, mentre Raccordo è il punto della lista a cui vuoi far puntare la sua coda (0 <= Raccordo < Lunghezza). Se Raccordo<0, la coda punta a NULL e quindi non ci sono cicli.

[ipparco]

Ok, mi rassegno, ho implementato il codice, ho fatto dei test automatici e, purtroppo per me e per i venditori di memoria RAM, funziona sempre (o per lo meno con le liste di al più 300 elementi, ma penso di potermi sbilanciare). Quello che non riesco a capire è il perchè. A me sembra che quando l1 viene valorizzato con l2, l2 è l'ultimo elemento controllato, cioè l'elemento in posizione n, con n che assume solo i valori 1,2,4,8,ecc..., e quindi che il test di uguaglianza si fa solo su questi elementi. Dove sbaglio ?

[MindFlyer]

Siccome non avevo disabilitato l'HTML, il mio messaggio precedente non si visualizzava correttamente. Adesso sì.

Dove sbaglio ?

Non sbagli, ogni test coinvolge sempre un elemento in posizione potenza di 2. Però ora sono io a non capire che problema ci sia in tutto questo...

[rand]

Un' altra soluzione consiste nel simulare due agenti che ispezionano la lista in parallelo ma uno dei due con velocità doppia dell'altro, in pratica ad ogni iterazione il più lento avanza di un solo oggetto mentre l'altro ne attraversa due. Se la lista ha un loop allora l'agente veloce raggiungerà quello lento in tempo lineare, altrimenti entrambi si incontreranno alla fine della lista. Quest'algoritmo ha spazio costante perchè tutto ciò di cui deve ricordarsi è una coppia di puntatori agli oggetti nei quali si trovano correntemente i due agenti.