Monatsarchive: November 2015

Hase-Igel-Algorithmus

Publiziert am 19. November 2015 von matthias

Mein Chef bat mich, Endlosschleifen zu vermeiden, die in einem alten Programm gelegentlich auftauchen, wenn die Daten “unsauber” eingegeben wurden. Die zugrundeliegende Datenstruktur ist eine einfach verkettete Liste. Im folgenden skizziere ich einen Weg, das zu ermöglichen.

/**
*         Hase und Igel
*
* siehe https://de.wikipedia.org/wiki/Hase-Igel-Algorithmus
*
* Dies ist der Startpunkt, um die Hase-Igel-Thematik an drei Beispielen
* zu zeigen. Eine Liste enthält einen Zirkel, eine andere nicht und 
* schließlich wird ein Grenzfall ausprobiert: Eine Liste mit nur einem 
* Element.<br>
* <br>
* Diese Implementierung ist anders als die im Artikel bei Wikipedia. Aber 
* die zugrundeliegende Idee ist diesselbe.
*/
public class Main
{
	public static void main ( String[] args )
	{
		
		/* ------------------ Vorbereitung ---------------------------------- */
		/* Dokumenten-Kette aufbauen ... */
		Document[] d = new Document[6];
		
		for (int i = 0; i<6; i++) {
			d[i] = new Document ();
			d[i].id = Integer.toString ( i );
		}
		for (int i = 0; i<5; i++) {
			d[i].next = d[i+1];
		}
		d[5].next = d[1]; // ... mit Zirkel!!
		/* Rekursive Funktion aufrufen; Zirkel vorhanden; ------------------- */
		printAnzahlDerRekursionen ( d[0] );
		
		/* ------------------ anderes Szenario ------------------------------ */
		resetHaseIgelStatics ();
		d[5].next = null; // Zirkel entfernen;
		printAnzahlDerRekursionen ( d[0] );
		
		/* ------------------ anderes Szenario ------------------------------ */
		resetHaseIgelStatics ();
		d[0].next = null; // Liste endet nach dem ersten Element;
		printAnzahlDerRekursionen ( d[0] );
	}
	
	private static void resetHaseIgelStatics () {
		HaseIgel.cnt = 0;
		HaseIgel.hase = null;
		HaseIgel.igel = null;
		HaseIgel.ersterAufruf = true;
	}
	
	private static void printAnzahlDerRekursionen ( Document d )
	{
		int anzahlDerRekursionen = 0;
		anzahlDerRekursionen = HaseIgel.eineFunktion ( d );
		System.out.println ( "Main.main() anzahlDerRekursionen ist " 
				+ anzahlDerRekursionen );
	}
}

/**

* Hase und Igel

* siehe https://de.wikipedia.org/wiki/Hase-Igel-Algorithmus

* Dies ist der Startpunkt, um die Hase-Igel-Thematik an drei Beispielen

* zu zeigen. Eine Liste enthält einen Zirkel, eine andere nicht und

* schließlich wird ein Grenzfall ausprobiert: Eine Liste mit nur einem

* Element.<br>

* <br>

* Diese Implementierung ist anders als die im Artikel bei Wikipedia. Aber

* die zugrundeliegende Idee ist diesselbe.

public class Main

{

public static void main ( String[] args )

{

/* ------------------ Vorbereitung ---------------------------------- */

/* Dokumenten-Kette aufbauen ... */

Document[] d = new Document[6];

for (int i = 0; i<6; i++) {

d[i] = new Document ();

d[i].id = Integer.toString ( i );

}

for (int i = 0; i<5; i++) {

d[i].next = d[i+1];

}

d[5].next = d[1]; // ... mit Zirkel!!

/* Rekursive Funktion aufrufen; Zirkel vorhanden; ------------------- */

printAnzahlDerRekursionen ( d[0] );

/* ------------------ anderes Szenario ------------------------------ */

resetHaseIgelStatics ();

d[5].next = null; // Zirkel entfernen;

printAnzahlDerRekursionen ( d[0] );

/* ------------------ anderes Szenario ------------------------------ */

resetHaseIgelStatics ();

d[0].next = null; // Liste endet nach dem ersten Element;

printAnzahlDerRekursionen ( d[0] );

}

private static void resetHaseIgelStatics () {

HaseIgel.cnt = 0;

HaseIgel.hase = null;

HaseIgel.igel = null;

HaseIgel.ersterAufruf = true;

}

private static void printAnzahlDerRekursionen ( Document d )

{

int anzahlDerRekursionen = 0;

anzahlDerRekursionen = HaseIgel.eineFunktion ( d );

System.out.println ( "Main.main() anzahlDerRekursionen ist "

+ anzahlDerRekursionen );

}

… Weiterlesen →

Veröffentlicht unter Allgemein | Kommentare deaktiviert

Monatsarchive: November 2015

Hase-Igel-Algorithmus

Neueste Beiträge

Archive

Kategorien

Meta