List: Unterschied zwischen den Versionen

Aus SibiWiki
Zur Navigation springen Zur Suche springen
 
(9 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)
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>
=Erklärvideo=
Wie durchläuft man standardmäßig Listen?


== Schnittstellenbeschreibung (Zentralabitur) ==
Das wird hier anhand der Methode <code>public int gesamtVermoegen()</code> erklärt.
 
[https://youtu.be/W3-JBKnl7xk Erklärvideo: Liste durchlaufen am Beispiel "public int gesamtVermoegen()"]
 
=Fachbegriffe=
 
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 27:
## 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>
# <code>while(pList.hasAccess()){</code>
* <code>while(pList.hasAccess()){</code>
## <code>Person p = pList.getContent();</code>
** <code>Person p = pList.getContent();</code>
## <code>//TODO: mit der Person p etwas machen!</code>
** <code>//TODO: mit der Person p etwas machen!</code>
## <code>pList.next();</code>
** <code>pList.next();</code>
* <code>}</code>


==Beispielmethoden für Listen==
==Mit for-Schleife==
'''Mit einer for-Schleife lässt sich dieses Standard-Verfahren viel einfacher implementieren!'''
* <code>for(pList.toFirst(); pList.hasAccess(); pList.next()){</code>
** <code>Person p = pList.getContent();</code>
** <code>//TODO: mit der Person p etwas machen!</code>
* <code>}</code>
 
=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) {
   boolean ergebnis = false;
   boolean ergebnis = false;
Zeile 42: Zeile 60:
   return ergebnis;
   return ergebnis;
  }
  }
</code>
</code>


Die Methode zeigt das Standard-Vorgehen zum Durchlaufen von Listen:
Die Methode zeigt das Standard-Vorgehen zum Durchlaufen von Listen:
Zeile 52: Zeile 70:
* Zum Schluss wird <code>ergebnis</code> zurückgegeben.
* Zum Schluss wird <code>ergebnis</code> zurückgegeben.


===jüngste Person===
==Anzahl aus Geburtsjahr==
Hier wird folgendes algorithmische Verfahren umgesetzt:
* <code>ergebnis</code> wird auf 0 gesetzt.
* die Liste <code>pList</code> komplett durchlaufen.
** Für die jeweils aktuelle Person wird geprüft, ob ihr Geburtsjahr dem Parameter <code>pJahr</code> entspricht.<br/>Wenn ja, wird <code>ergebnis</code> um 1 erhöht.
* Nach dem Ende der Schleife wird <code>ergebnis</code> zurückgegeben.
 
''Hinweis: Hier wird die Liste mit einer for-Schleife durchlaufen. Das ist für die Programmierung viel angenehmer, weil man nicht Gefahr läuft, das <code>next()</code> zu vergessen!
 
<code>
  public Person anzahlPersonenAusGeburtsjahr(List<Person> pList, int pJahr){
    int ergebnis = 0;
    for(pList.toFirst(); pList.hasAccess(); pList.next()){
        Person p = pList.getContent();
        if(p.getGeburtsjahr() == pJahr){
          ergebnis += 1;
        }
    }
    return ergebnis;
  }
</code>
 
 
 
==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.
# Dann wird die Liste komplett durchlaufen.
* Dann wird die Liste komplett durchlaufen.
## Dabei wird die jeweils aktuelle Person mit <code>ergebnis</code> verglichen: Wenn sie jünger ist, dann wird <code>aktuell</code> in <code>ergebnis</code> gespeichert.
** Dabei wird die jeweils die Person, auf die der Zeiger zeigt, mit <code>ergebnis</code> verglichen: Wenn sie jünger ist, dann wird <code>aktuell</code> in <code>ergebnis</code> gespeichert.
# Am Ende wird <code>ergebnis</code> zurückgegeben.  
* Am Ende wird <code>ergebnis</code> zurückgegeben.  


<code>
<code>
   public Person juengstePerson(List<Person> pList){
   public Person juengstePerson(List<Person> pList){
     Person ergebnis = null;
     Person ergebnis = null;
Zeile 68: Zeile 110:
     Person ergebnis = pList.getContent();
     Person ergebnis = pList.getContent();
     while(pList.hasAccess()){
     while(pList.hasAccess()){
         Person aktuell = pList.getContent();
         Person p = pList.getContent();
         if(aktuell.getGeburtsjahr() < ergebnis.getGeburtsjahr()){
         if(p.getGeburtsjahr() < ergebnis.getGeburtsjahr()){
           ergebnis = aktuell;
           ergebnis = p;
         }
         }
         pList.next();
         pList.next();
Zeile 76: Zeile 118:
     return ergebnis;
     return ergebnis;
   }
   }
</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 134:
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>
  public boolean istSortiert(List<Person> pList)
  public boolean istSortiert(List<String> pList)
  {
  {
     boolean ergebnis = true;
     boolean ergebnis = true;
Zeile 128: Zeile 170:
     return ergebnis;
     return ergebnis;
  }
  }
</code>
</code>

Aktuelle Version vom 23. Februar 2024, 15:58 Uhr

Diese Seite entspricht dem Abi 17 (und folgenden)

Erklärvideo

Wie durchläuft man standardmäßig Listen?

Das wird hier anhand der Methode public int gesamtVermoegen() erklärt.

Erklärvideo: Liste durchlaufen am Beispiel "public int gesamtVermoegen()"

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):

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

Mit for-Schleife

Mit einer for-Schleife lässt sich dieses Standard-Verfahren viel einfacher implementieren!

  • for(pList.toFirst(); pList.hasAccess(); pList.next()){
    • Person p = pList.getContent();
    • //TODO: mit der Person p etwas machen!
  • }

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.

Anzahl aus Geburtsjahr

Hier wird folgendes algorithmische Verfahren umgesetzt:

  • ergebnis wird auf 0 gesetzt.
  • die Liste pList komplett durchlaufen.
    • Für die jeweils aktuelle Person wird geprüft, ob ihr Geburtsjahr dem Parameter pJahr entspricht.
      Wenn ja, wird ergebnis um 1 erhöht.
  • Nach dem Ende der Schleife wird ergebnis zurückgegeben.

Hinweis: Hier wird die Liste mit einer for-Schleife durchlaufen. Das ist für die Programmierung viel angenehmer, weil man nicht Gefahr läuft, das next() zu vergessen!


 public Person anzahlPersonenAusGeburtsjahr(List<Person> pList, int pJahr){
    int ergebnis = 0;
    for(pList.toFirst(); pList.hasAccess(); pList.next()){
       Person p = pList.getContent();
       if(p.getGeburtsjahr() == pJahr){
          ergebnis += 1;
       }
    }
    return ergebnis;
  }


jüngste Person

Hier wird folgende Strategie verfolgt:

  • in ergebnis wird zuerst die erste Person der Liste gespeichert.
  • Dann wird die Liste komplett durchlaufen.
    • 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.
  • 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;
}