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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
/** * 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 ); } } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
/** * Ich bilde hier eine Klasse nach, die bei uns im Unternehmen genutzt wird. Die * Bezeichnungen und Typisierungen sind natürlich durchweg andere. Aber das * Prinzip ist dasselbe. Insbesondere wird viel mit "static" gearbeitet :-( * Und es gibt eineFunktion(x), die sich selbst aufruft, als Parameter eine * einfach verkettete Datenstruktur. <br> * <br> * Wesentliche Aufgabestellung war, Zirkel in der Kette von Documents erkennen * zu können. Die Signatur der Methode sollte erhalten bleiben.<br> * <br> * Dazu wurden die Elemente hase, igel und ersterAufruf hinzugefügt. Die * Konsolen-Ausdrucke wurden zwecks Nachvollziehbarkeit für dieses Beispiel * hinzugefügt. * <br> <br> * Der Übersichtlichkeit halber verzichte ich auf alle normalen Kodierungsgewohnheiten. * Es ist der minimal notwendige Code, um das Beispiel zu illustrieren. * */ public class HaseIgel { public static int cnt = 0; public static Document hase = null; public static Document igel = null; public static boolean ersterAufruf = true; public static int eineFunktion ( Document o ) { cnt++; System.out.println ( "HaseIgel.eineFunktion() verarbeitet ID " + o.id ); /* -------------------- <Zirkel erkennen> --------------------------- */ igel = o; // Der Igel geht von Element zu Element if ( ersterAufruf ) { ersterAufruf = false; hase = o; } if ( null != hase ) { if ( null != hase.next ) { hase = hase.next.next; // Der Hase geht zum übernächsten Element, } else { hase = null; // oder er ist am Ende angelangt. } } /* Wenn hase und igel sich treffen, dann ist ein Zirkel vorhanden */ if ( null != hase && hase.id.equals ( igel.id ) ) { System.out.println ( "HaseIgel.eineFunktion() hat " + "einen Zirkel gefunden. Abbruch." ); return cnt; } /* -------------------- </Zirkel erkennen> -------------------------- */ if ( null != o.next ) { /* Rekursion */ eineFunktion ( o.next ); } return cnt; } } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
/** * Ein einfaches Beispiel für eine verkettete Datenstruktur. <br> * Ein Document hat einen Zeiger auf seinen Nachfolger. Und es ist durch * die ID universumsweit eindeutig identifizierbar. * <br> * In der "wirklichen Welt" wird diese Datenstruktur nicht benutzt, aber sie * steht in diesem Beispiel für andere, beispielweise ein lotus.domino.Document. * <br> <br> * Der Übersichtlichkeit halber verzichte ich auf alle normalen Kodierungsgewohnheiten. * Es ist der minimal notwendige Code, um das Beispiel zu illustrieren. * */ public class Document { public String id; public Document next; } |