List: Unterschied zwischen den Versionen

Aus SibiWiki
Zur Navigation springen Zur Suche springen
Zeile 4: Zeile 4:
[[Kategorie:Informatik-Abitur]]
[[Kategorie:Informatik-Abitur]]
<font color='red'>'''Diese Seite entspricht dem Abi 17 (und folgenden)'''</font>
<font color='red'>'''Diese Seite entspricht dem Abi 17 (und folgenden)'''</font>
=Fachbegriffe=


== Schnittstellenbeschreibung (Zentralabitur) ==
Liste, Zeiger, an den Anfang, aktuelles Element, hasAccess(), ist leer (=isEmpty()), einfügen, (hinten) anhängen, (das aktuelle Element) löschen
 
= Schnittstellenbeschreibung (Zentralabitur) =
* [[Medium:Dokumentation_List_Abi2017.pdf|Schnittstelle der Klasse List (PDF)]]
* [[Medium:Dokumentation_List_Abi2017.pdf|Schnittstelle der Klasse List (PDF)]]




==Standardvorgehen im Umgang mit Listen==
=Standardvorgehen im Umgang mit Listen=
Meistens werden Listen von vorne nach hinten durchlaufen und dabei wird mit jedem einzelnen Eintrag der Liste etwas gemacht. Das funktioniert folgendermaßen:
Meistens werden Listen von vorne nach hinten durchlaufen und dabei wird mit jedem einzelnen Eintrag der Liste etwas gemacht. Das funktioniert folgendermaßen:
# Zeiger auf den Anfang der Liste setzen
# Zeiger auf den Anfang der Liste setzen
Zeile 17: Zeile 20:
## den Zeiger eins weiterrücken.
## den Zeiger eins weiterrücken.


===Java===
=Java=
In '''Java''' sieht das so aus (die Liste ist in diesem Beispiel mit Objekten vom Typ <code>Person</code> gefüllt):
In '''Java''' sieht das so aus (die Liste ist in diesem Beispiel mit Objekten vom Typ <code>Person</code> gefüllt):
# <code>pList.toFirst();</code>
# <code>pList.toFirst();</code>
Zeile 25: Zeile 28:
## <code>pList.next();</code>
## <code>pList.next();</code>


==Beispielmethoden für Listen==
=Beispielmethoden für Listen=
Hier werden beispielhaft einige Methoden für Listen aufgeführt:
Hier werden beispielhaft einige Methoden für Listen aufgeführt:


===enthaelt===
==enthaelt==
<code>
<code>
  private boolean enthaelt(List<Person> pList, String pName) {
  private boolean enthaelt(List<Person> pList, String pName) {
Zeile 52: Zeile 55:
* Zum Schluss wird <code>ergebnis</code> zurückgegeben.
* Zum Schluss wird <code>ergebnis</code> zurückgegeben.


===jüngste Person===
==jüngste Person==
Hier wird folgende Strategie verfolgt:
Hier wird folgende Strategie verfolgt:
# in <code>ergebnis</code> wird zuerst die erste Person der Liste gespeichert.
# in <code>ergebnis</code> wird zuerst die erste Person der Liste gespeichert.
Zeile 78: Zeile 81:
</code>
</code>


== Sortierverfahren ==
= Sortierverfahren =


=== Sortieren durch Einfügen ===
== Sortieren durch Einfügen ==
siehe [[Insertionsort|Insertionsort]]
siehe [[Insertionsort|Insertionsort]]


=== Sortieren durch Auswählen ===
== Sortieren durch Auswählen ==
siehe [[Selectionsort|Selectionsort]]
siehe [[Selectionsort|Selectionsort]]


=== Bubblesort ===
== Bubblesort ==
[[Bubblesort|Bubblesort]] ist mit der neuen List-Implementierung nicht mehr sinnvoll, da es keine Möglichkeit gibt die Methode '''Flip''' sinnvoll zu programieren. <br>
[[Bubblesort|Bubblesort]] ist mit der neuen List-Implementierung nicht mehr sinnvoll, da es keine Möglichkeit gibt die Methode '''Flip''' sinnvoll zu programieren. <br>
'''Flip''' soll immer dann zwei Werte vertauschen, wenn der im Alphabet vordere Buchstabe hinten steht bzw. die hintere Zahl größer ist.<br>
'''Flip''' soll immer dann zwei Werte vertauschen, wenn der im Alphabet vordere Buchstabe hinten steht bzw. die hintere Zahl größer ist.<br>
Zeile 92: Zeile 95:
Desweiteren wäre am Ende das Sortierverfahren zu '''Rechenintensiv'''.
Desweiteren wäre am Ende das Sortierverfahren zu '''Rechenintensiv'''.


=== Mergesort ===
== Mergesort ==
'''<font color='red'>nicht relevant fürs Zentralabitur!</font>'''
'''<font color='red'>nicht relevant fürs Zentralabitur!</font>'''


siehe [[Mergesort|Mergesort]]
siehe [[Mergesort|Mergesort]]


===Quicksort===
==Quicksort==
'''<font color='red'>im Zentralabitur nur relevant für den LK!</font>'''
'''<font color='red'>im Zentralabitur nur relevant für den LK!</font>'''


siehe [[Quicksort|Quicksort]]
siehe [[Quicksort|Quicksort]]


=== istSortiert ===
== istSortiert ==
für eine Liste, die mit Objekten vom Typ String gefüllt ist.
für eine Liste, die mit Objekten vom Typ String gefüllt ist.
<code>
<code>

Version vom 23. Juni 2019, 13:46 Uhr

Diese Seite entspricht dem Abi 17 (und folgenden)

Fachbegriffe

Liste, Zeiger, an den Anfang, aktuelles Element, hasAccess(), ist leer (=isEmpty()), einfügen, (hinten) anhängen, (das aktuelle Element) löschen

Schnittstellenbeschreibung (Zentralabitur)


Standardvorgehen im Umgang mit Listen

Meistens werden Listen von vorne nach hinten durchlaufen und dabei wird mit jedem einzelnen Eintrag der Liste etwas gemacht. Das funktioniert folgendermaßen:

  1. Zeiger auf den Anfang der Liste setzen
  2. while-Schleife, die so lange läuft, wie der Zeiger in der Liste ist. Innerhalb der Schleife...
    1. das Element, auf das der Zeiger zeigt, in einer lokalen Variable speichern.
    2. mit diesem Element etwas machen (das hängt von der Aufgabe der Methode ab)
    3. den Zeiger eins weiterrücken.

Java

In Java sieht das so aus (die Liste ist in diesem Beispiel mit Objekten vom Typ Person gefüllt):

  1. pList.toFirst();
  2. while(pList.hasAccess()){
    1. Person p = pList.getContent();
    2. //TODO: mit der Person p etwas machen!
    3. pList.next();

Beispielmethoden für Listen

Hier werden beispielhaft einige Methoden für Listen aufgeführt:

enthaelt

private boolean enthaelt(List<Person> pList, String pName) {
  boolean ergebnis = false;
  pList.toFirst();
  while(pList.hasAccess()){
     Person p = pList.getContent();
     if(p.gibName().equals(pName)){
        ergebnis = true;
     }
     pList.next();
  }
  return ergebnis;
}

Die Methode zeigt das Standard-Vorgehen zum Durchlaufen von Listen:

  • Es wird ein ergebnis deklariert. ergebnis ist vom selben Typ wie der Rückgabetyp der Methode (hier: boolean). ergebnis wird mit einem Standardwert versehen: Bevor man die Liste durchsucht, hat man noch nichts gefunden, d.h. ergebnis ist false
  • Der Zeiger wird auf den Anfang der Liste gesetzt.
  • Mit while(pList.hasAccess()) und pList.next() wird die Liste dann komplett durchlaufen.
  • Dabei wird mit Person p = pList.getContent(); jeweils die Person ausgelesen, auf die der Zeiger zeigt.
  • Mit der Person p wird dann etwas gemacht; in diesem Fall wird ihr Name mit dem Parameter pName verglichen und wenn das übereinstimmt, dann wird ergebnis auf true gesetzt.
  • Zum Schluss wird ergebnis zurückgegeben.

jüngste Person

Hier wird folgende Strategie verfolgt:

  1. in ergebnis wird zuerst die erste Person der Liste gespeichert.
  2. Dann wird die Liste komplett durchlaufen.
    1. Dabei wird die jeweils die Person, auf die der Zeiger zeigt, mit ergebnis verglichen: Wenn sie jünger ist, dann wird aktuell in ergebnis gespeichert.
  3. Am Ende wird ergebnis zurückgegeben.

 public Person juengstePerson(List<Person> pList){
    Person ergebnis = null;
    if(pList.isEmpty()){
        return ergebnis;
    }
    pList.toFirst();
    Person ergebnis = pList.getContent();
    while(pList.hasAccess()){
       Person p = pList.getContent();
       if(p.getGeburtsjahr() < ergebnis.getGeburtsjahr()){
          ergebnis = p;
       }
       pList.next();
    }
    return ergebnis;
  }

Sortierverfahren

Sortieren durch Einfügen

siehe Insertionsort

Sortieren durch Auswählen

siehe Selectionsort

Bubblesort

Bubblesort ist mit der neuen List-Implementierung nicht mehr sinnvoll, da es keine Möglichkeit gibt die Methode Flip sinnvoll zu programieren.
Flip soll immer dann zwei Werte vertauschen, wenn der im Alphabet vordere Buchstabe hinten steht bzw. die hintere Zahl größer ist.
Um die Methode jedoch sinnvoll programieren zu können, wären komplizierte & umständliche Programierungen notwendig.
Desweiteren wäre am Ende das Sortierverfahren zu Rechenintensiv.

Mergesort

nicht relevant fürs Zentralabitur!

siehe Mergesort

Quicksort

im Zentralabitur nur relevant für den LK!

siehe Quicksort

istSortiert

für eine Liste, die mit Objekten vom Typ String gefüllt ist.

public boolean istSortiert(List<String> pList)
{
   boolean ergebnis = true;
   pList.toFirst();
   while(pList.hasAccess())
      {
      String aktuell = pList.getContent();
      pList.next();
      if(pList.hasAccess() == false)
      {
         ergebnis = true;
         return ergebnis;
      }
      String naechster = pList.getContent();
      if(aktuell.compareTo(naechster)>0)
      {
         ergebnis = false;
         return ergebnis;
      }
   }
   ergebnis = true;
   return ergebnis;
}