Transcript
Informatik in Q1:
Sortierte Listen
Gierhardt
Einführung Die Elemente einer sortierten Liste sind ähnlich angeordnet wie in einem Array. Allerdings ergeben sich bei Strukturierung mit einem Array verschiedene Probleme: • Beim Einfügen eines Elementes müssen alle nachfolgenden Elemente um eine Stelle verschoben werden. • Beim Löschen eines Elementes muss die Datenstruktur umgekehrt entsprechend angepasst werden. • Die Liste kann in einem Array nicht dynamisch wachsen und schrumpfen. Die einfachste Form einer sortierten dynamischen Liste besteht aus Knoten mit Inhalt und einem Verweis auf den nachfolgenden Knoten. Diese Strukturierung ist durch Verweise auf den jeweiligen Vorgänger erweiterbar. Dann erhält man eine doppelt verkettete Liste.
Einfügen Beim Einfügen in eine sortierte Liste ergeben sich verschiedene Fälle, die beachtet werden müssen: 1. Es wird in eine leere Liste eingefügt. 2. Es wird vor dem ersten Element der Liste eingefügt. 3. Es wird zwischen zwei Elementen eingefügt. 4. Es wird am Ende der Liste eingefügt. Zeichne für jeden der vier Fälle eine Graphik mit Zeigern, die die Operationen der im Anhang angegebenen Methode insert darstellt. Zeige damit die Korrektheit der Methode für alle Fälle.
Löschen Beim Löschen in einer sortierten Liste ergeben sich verschiedene Fälle, die beachtet werden müssen: 1. Es wird versucht, in einer leeren Liste zu löschen. 2. Es wird das erste Element der Liste gelöscht. 3. Es wird zwischen zwei Elementen gelöscht.
1
4. Es wird am Ende der Liste gelöscht. 5. Es wird versucht, ein nicht vorhandenes Element zu löschen. Zeichne für jeden der fünf Fälle eine Graphik mit Zeigern, die die Operationen der im Anhang angegebenen Methode delete darstellt. Zeige damit die Korrektheit der Methode für alle Fälle.
Suchen Schreibe eine Methode, die feststellt, ob ein bestimmtes Element in der Liste vorhanden ist.
Aufgabe Schreibe geeignete Klassen für eine Telephonnummernliste (mit Namen). Informiere dich dazu über geeignete Vergleichsoperationen für Strings und schreibe eine Methode, die als booleschen Funktionswert angibt, ob ein String kleiner als ein anderer ist oder nicht. Schreibe ein Hauptprogramm zum Testen der Klassen mit einer Menüstruktur zum Einfügen, Löschen und Ansehen der Einträge.
Anhang 1 2
class ZahlenListenTest { ZahlenListe l i s t e ;
3 4 5 6 7
public Z a h l e n L i s t e n T e s t ( ) { l i s t e = new Z a h l e n L i s t e ( ) ; action ( ) ; }
8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
public void a c t i o n ( ) { l i s t e . gibAllesAus ( ) ; liste . insert (3); liste liste . insert (7); liste liste . insert (12); liste liste . insert (2); liste liste . insert (8); liste liste . insert (13); liste l i s t e . delete (7); liste l i s t e . delete (2); liste l i s t e . delete (3); liste l i s t e . delete (12); liste l i s t e . delete (12); liste l i s t e . delete (13); liste l i s t e . delete (8); liste } } // c l a s s Z a h l e n L i s t e n T e s t
. gibAllesAus . gibAllesAus . gibAllesAus . gibAllesAus . gibAllesAus . gibAllesAus . gibAllesAus . gibAllesAus . gibAllesAus . gibAllesAus . gibAllesAus . gibAllesAus . gibAllesAus
2
(); (); (); (); (); ( ) ; // j e t z t l o e s c h e n (); (); (); (); (); (); ();
1 2 3 4 5
public c l a s s Knoten { private int wert ; // S t a r k v e r e i n f a c h t e r r Knoten ! // h i e r werden s p a e t e r s t a t t Zahlen // b e l i e b i g e O b j e k t e v e r w a l t e t
6 7
private Knoten n a c h f o l g e r ;
8 9 10 11 12
public Knoten ( int z a h l , Knoten next ) { wert = z a h l ; n a c h f o l g e r = next ; }
13 14 15
public void s e t N a c h f o l g e r ( Knoten next ) { n a c h f o l g e r = next ; }
16 17 18
public Knoten g e t N a c h f o l g e r ( ) { return n a c h f o l g e r ; }
19 20 21
public void setWert ( int z a h l ) { wert = z a h l ; }
22 23 24
public int getWert ( ) { return wert ; }
25 26
} // c l a s s Knoten
3
1 2
public c l a s s Z a h l e n L i s t e { private Knoten e r s t e r ;
3 4 5
public Z a h l e n L i s t e ( ) { e r s t e r = null ; }
6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
public void i n s e r t ( int z a h l ) { Knoten l a u f = erster ; Knoten v o r h e r = null ; while ( l a u f != null && z a h l >l a u f . getWert ( ) ) { vorher = l a u f ; lauf = lauf . getNachfolger ( ) ; } // E i n f u e g e s t e l l e od er L i s t e n e n d e g e f u n d e n Knoten neu = new Knoten ( z a h l , null ) ; neu . s e t N a c h f o l g e r ( l a u f ) ; // nach vorne " v e r k n o t e n " i f ( l a u f==e r s t e r ) e r s t e r = neu ; e l s e v o r h e r . s e t N a c h f o l g e r ( neu ) ; // von h i n t e n " v e r k n o t e n " } // i n s e r t
21 22 23 24 25 26 27 28 29 30 31 32 33 34
public void d e l e t e ( int z a h l ) { Knoten l a u f = erster ; Knoten v o r h e r = null ; while ( l a u f != null && z a h l != l a u f . getWert ( ) ) // k u r z e Auswertung { vorher = l a u f ; lauf = lauf . getNachfolger ( ) ; } // Ende d e r S c h l e i f e , wenn z a h l=l a u f . getWert ( ) ode r l a u f==n u l l i f ( l a u f != null ) i f ( l a u f==e r s t e r ) erster = lauf . getNachfolger ( ) ; else vorher . setNachfolger ( l a u f . getNachfolger ( ) ) ; } // d e l e t e
35 36 37 38 39 40 41 42 43 44 45 46 47
public void g i b A l l e s A u s ( ) { Knoten l a u f = e r s t e r ; i f ( l a u f==null ) { System . out . p r i n t l n ( " L i s t e ␣ i s t ␣ l e e r . " ) ; return ; } while ( l a u f != null ) { System . out . p r i n t ( l a u f . getWert ( ) + " ␣ ␣ " ) ; lauf = lauf . getNachfolger ( ) ; } System . out . p r i n t l n ( ) ; } // g i b A l l e s A u s
48 49
} // c l a s s Z a h l e n L i s t e
4
