Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Aufgabe 1 - Wissensfragen   (Übersicht)

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

Beide Seiten, vorherige ÜberarbeitungVorherige Überarbeitung
Nächste Überarbeitung		Vorherige Überarbeitung
pruefungen:bachelor:aud:loesungws13 [15.03.2018 12:35] – Evrenpruefungen:bachelor:aud:loesungws13 [05.08.2019 09:31] (aktuell) – SpeedyGonzalez
Zeile 90: Zeile 90:
     }     }
 } }
 +//Anmerkung: hier wird allerdings immer der gleiche hashcode fuer einen String s verwendet, den ich mehrfach einfuege.
 +//Heisst wenn ich String x (...equals(s)) einfuege, bleibt hs gleich, also landen gleiche Strings immer im gleichen Bucket!!! Wodurch 
 +//sollte der String in einem anderen Bucket landen? Bedeutet erstere Implementierung reicht fuer diese Anwendung voellig aus!
 +//Ausserdem wuerde der platz auch kaum reichen auf der Angabe fuer eine Implementierung mit dieser Fehlerbeachtung
 </code>   </code>  
  
Zeile 140: Zeile 144:
          
     for(char c : s.toCharArray(){     for(char c : s.toCharArray(){
-      if(curr.children[c - 'A'] == null) curr.children[c-'A'] = new Trie();+      if(curr.children[c - 'A'] == null){ 
 +            curr.children[c-'A'] = new Trie(); 
 +      }
       curr = curr.children[c - 'A'];       curr = curr.children[c - 'A'];
     }     }
Zeile 146: Zeile 152:
     curr.myString = s;     curr.myString = s;
   }   }
 +}
 +</code>
 +\\
 +oder
 +\\
 +<code java>
 +public class Trie {
 +    // bis zu 26 Kinder; null, wenn kein Kind mit zugehoerigem Buchstaben:
 +    Trie[] children = new Trie['Z' - 'A' + 1];
 +    String myString; // null, wenn keine Zeichenkette zu speichern ist
 +
 +    void insert(String s) {
 +        assert s != null;
 +
 +        for (char c : s.toCharArray()) {
 +            assert c >= 'A' && c <= 'Z';
 +        }
 +
 +        Trie curr = this;
 +
 +        for (int i = 0; i < s.length(); i++) {
 +            int charIndex = s.charAt(i) - 'A';
 +
 +            if (curr.children[charIndex] == null) {
 +                curr.children[charIndex] = new Trie();
 +            }
 +            curr = curr.children[charIndex];
 +        }
 +        curr.myString = s;
 +    }
 } }
 </code> </code>
Zeile 154: Zeile 190:
  
 <code java> <code java>
-void printSorted(){ +void printSorted() { 
-   if(myString != null) { +    Trie curr = this; 
-      System.out.println(myString); +     
-   } +    if (curr.myString != null) { 
-   for(int i=0; i < 26; i++){ +        System.out.println(curr.myString); 
-      if(children[i] != null) { +    } 
-         children[i].printSorted(); + 
-      } +    for (int i = 0; i < curr.children.length; i++) { 
-   }+        if (curr.children[i] != null) { 
 +            curr.children[i].printSorted(); 
 +        } 
 +    }
 } }
 </code> </code>