Algorithmen und Datenstrukturen 2

Übungsblatt 3: Algorithmen für eine Datenstruktur

Diese Aufgaben bauen auf der Klasse Menge auf, die eine mathematische Menge mit Hilfe eines internen Arrays implementiert. Gehen Sie in diesem Übungsblatt davon aus, dass dieses Array sortiert ist.

Aufgabe 3-1 *

Schreiben Sie eine Objektmethode finde, die eine Zahl im internen Array sucht und den Array-Index der Fundstelle zurückgibt. Verwenden Sie den Algorithmus der binären Suche.

Aufgabe 3-2 *

Schreiben Sie eine Objektmethode enthaelt, die feststellt, ob zahl in der Menge enthalten ist – egal wie!

Zusatzaufgabe 3-3

Entwerfen Sie Algorithmen für einige der folgenden Operationen auf einer sortierten Menge. Formulieren Sie die Algorithmen möglichst sowohl in Java als auch in „natürlicher Sprache“ nach Dr. Bürg.

1. int groesse () liefert die Anzahl der Elemente der Menge
2. boolean istLeer () gibt an, ob die Menge leer ist
3. int kleinstes () liefert den Wert des kleinsten Elements der Menge
4. int groesstes () liefert den Wert des größten Elements der Menge
5. boolean enthaeltAlle (int[] zahlen) gibt an, ob die Menge alle in zahlen enthaltenen Werte enthält
6. void leere () entfernt alle Elemente aus der Menge
7. int entferne (int zahl) entfernt den Wert zahl aus der Menge
8. int[] teilmenge (int vonWert, int bisWert) liefert eine Teilmenge zurück, die alle Werte von vonWert bis bisWert enthält
9. Menge teilmenge (int vonWert, int bisWert) liefert eine Teilmenge zurück, die alle Werte von vonWert bis bisWert enthält
10. void fuegeEin (int zahl) fügt den Wert zahl zur Menge hinzu

Tipp. Die letzten fünf Teilaufgaben verlangen, dass ein neuer Array der passenden Länge erzeugt und der Objektvariable menge, welche die interne Array-Referenz hält, zugewiesen wird.

$Id: HEADER.html 2009-04-20 $

 Name                                   Last modified      Size  Description
 Parent Directory                                            -   
 HEADER.html                            2023-10-11 10:00  2.5K  
 Loesung31.java                         2023-10-11 10:00  1.6K  
 Loesung32.java                         2023-10-11 10:00  938   
 Loesung33a.java                        2023-10-11 10:00  740   
 Menge.java                             2023-10-11 10:00  1.1K  
 README.html                            2023-10-11 10:00  957