Gymnasium Löbau/Vertiefungsklasse 2013/Die Datenstruktur Feld

Wiki-Quelltext dieser Seite.

<language>Javascript</language>
== Begriff ==

Ein Datenfeld (kurz: Feld oder Array) ist eine komplexe Datenstruktur, bei der mehrere Daten ''eines Datentyps'' in einer definierten Reihenfolge an einen Variablennamen gebunden werden.

<blockquote>
<table border="1" cellspacing ="0" cellpadding="4">
<tr>
<td>Mathematik</td><td>$a_0, a_1, ... , a_n$</td>
</tr>
<tr>
<td>JavaScript</td><td>$a[0], a[1], ... , a[n]$</td>
</tr>
</table>
</blockquote>

Jedem Feldelement kann über seinen ''Feldindex'' ein Wert zugewiesen werden, der natürlich auch geändert oder ausgegeben werden kann.

== Deklaration eines eindimensionalen Feldes ==

<code id="5bdff3f5cb048">
var Feld = new Array();
Feld[0] = "Montag";
Feld[1] = "Dienstag";
Feld[2] = "Mittwoch";
Feld[3] = "Donnerstag";
Feld[4] = "Freitag";
</code>

<run id="5bdff3f5cb131">
Feld;
</run>

== Methoden ==

An die Datenstruktur Feld sind sehr nützliche Methoden gebunden. Teste sie in der mit den nachfolgenden Definitionen:

<code id="5bdff3f5cb0c4">
var n = Feld.length;
var newFeld = Feld.slice(2, 3);
Feld.reverse(); 
var zk = Feld.join(); 
</code>

<run id="5bdff3f5cb1a2">
n;
</run>

== Felder mit Zufallszahlen ==

Wir haben in der [[Gymnasium Löbau/Vertiefungsklasse 2013/Wiederholung: Datentypen und Programmstrukturen|Wiederholung von Datentypen und Programmstrukturen]] eine Zufallsfunktion für natürliche Zahlen kennen gelernt, die wir um eine linke Intervallgrenze erweitern wollen:

<code id="5bdff8b72412f">
function zufallszahl(von, bis) {
 return Math.floor(Math.random() * (bis - von + 1) + von);
}
</code>

Damit können wir nun Felder mit ganzen Zufallszahlen generieren:

<code id="5be018508eb8a">
function erzeugen(von, bis, anz) {
 var feld = new Array();
 for (var i = 0; i < anz; i++)
  feld[i] = zufallszahl(von, bis);
 return feld;
}

var newFeld = erzeugen(-50, 100, 20);
</code>

<run id="5bdff8b724224">
newFeld;
</run>

Felder mit Zufallszahlen können i.A. sehr umfangreich werden. Wir wollen deshalb eine geeignete Ausgabe-Prozedur entwickeln.<br />
''Prozeduren'' sind in JavaScript spezielle Funktionen, die ''keine Werte'' zurückgeben.

<code id="5be869094fc5e">
function ausgabe(feld) {
 var maxAnzahl = 25;
 var teilFeld = new Array();
 var i = 0, j = 0;
 while (i < feld.length) {
  j = i + maxAnzahl;
  if (j < feld.length)
   teilFeld = feld.slice(i, j);
  else
   teilFeld = feld.slice(i, feld.length);
  console.log(teilFeld);
  i = j;
 }
} 

var newFeld = erzeugen(1, 1000, 1000);
</code>

<run id="5be00ed718cc8">
ausgabe(newFeld);
</run>

== Sequenzielle Suche ==

Wir wollen umfangreiche numerische Datenfelder näher untersuchen, z.B. ausgewählte Feldelemente suchen, zählen oder ersetzen. Dazu müssen alle Feldelemente nacheinander durchmustert werden. <br />
Prinzipiell stehen uns zwei syntaktische Programmstrukturen zur Verfügung:

<blockquote>
<table border="0" cellspacing ="0" cellpadding="4">
<tr>
<td width="400">
 for (var i = 0; i < feld.length; i++) {
  //-- Anweisungsteil --
 }
</td>
<td width="400">
 for (var i in feld) {
  //-- Anweisungsteil --
 }
</td>
</tr>
</table>
</blockquote>

In der sogenannten <tt>for-in</tt>-Schleife werden allerdings nur Feldelemente berücksichtigt, die auch mit einem Wert belegt sind. 

<code id="5be869094fce9">
function elementSuche(element, feld) {
 var exist = false;
 for (var i in feld)
  if (element == feld[i])
   exist = true;
 return exist;
} 
</code>

<run id="5be869094fd78">
var newFeld = erzeugen(1, 100, 50);
var newElement = 47;
ausgabe(newFeld);
if (elementSuche(newElement, newFeld))
 console.log("Das Element " + newElement + " ist im Datenfeld vorhanden.");
else
 console.log("Das Element " + newElement + " ist im Datenfeld nicht vorhanden.");
</run>

Ein Suchverfahren, in dem ''alle Feldelemente'' nacheinander durchmustert werden, nennt man ''lineare'' oder ''sequenzielle Suche''.

== Aufgaben ==

<ol>
<li>

=== Effiziente Suchfunktion ===

Begründe, warum die nachfolgende Funktion zur Elementsuche noch effizienter ist.<br />
Zeichne dazu das entsprechende Struktogamm.

<code id="5be8928f16607">
function newElementSuche(element, feld) {
 var exist = false;
 var i = 0;
 while ((! exist) && (i < feld.length)) {
  exist = (element == feld[i]);
  i++;
 }
 return exist;
}
</code>

<run id="5be8928f16723">
var newFeld = erzeugen(1, 100, 50);
var newElement = 47;
ausgabe(newFeld);
if (newElementSuche(newElement, newFeld))
 console.log("Das Element " + newElement + " ist im Datenfeld vorhanden.");
else
 console.log("Das Element " + newElement + " ist im Datenfeld nicht vorhanden.");
</run>

</li>
<li>

=== Positionssuche eines Elements ===

In einem numerischen Feld ist die Position eines zu suchenden Elements zu bestimmen, an der es erstmalig auftritt.<br />
Ist das Element im Feld nicht vorhanden, soll $-1$ zurückgegeben werden.

<code id="5be8928f16682">
function elementPosition(element, feld) {
 var pos = -1;
 //-- weitere Anweisungen --
 return pos;
}
</code>

<check execute="(elementPosition(17, [23, 5, 67, 17, 88, 17]) == 3) && (elementPosition(13, [23, 5, 67, 17, 88, 17]) == -1) && (elementPosition(0, []) == -1)">
true
</check>

<run id="5be8928f1678f">
var newFeld = erzeugen(1, 100, 50);
var newElement = 47;
var pos = elementPosition(newElement, newFeld);
ausgabe(newFeld);
if (pos >= 0)
 console.log("Das Element " + newElement + " ist im Datenfeld an " + pos + ". Position vorhanden.");
else
 console.log("Das Element " + newElement + " ist im Datenfeld nicht vorhanden.");
</run>

</li>
<li>

=== Anzahl eines Elements ===

Mit der nachfolgenden Funktion soll ermittelt werden, wie oft ein bestimmtes Element in einem Feld vorkommt.

<code id="5be92567e5c8d">
function elementAnzahl(element, feld) {
 var anz = 0;
 //-- weitere Anweisungen --
 return anz;
}
</code>

<check execute="(elementAnzahl(17, [23, 5, 67, 17, 88, 17]) == 2) && (elementAnzahl(13, [23, 5, 67, 17, 88, 17]) == 0) && (elementAnzahl(0, []) == 0)">
true
</check>

<run id="5be92567e5d4e">
var newFeld = erzeugen(1, 100, 50);
var newElement = 47;
var anz = elementAnzahl(newElement, newFeld);
ausgabe(newFeld);
console.log("Das Element " + newElement + " ist im Datenfeld " + anz + " mal vorhanden.");
</run>

</li>
<li>

=== Größtes Feldelement ===

Aus einem numerische Datenfeld soll nun das größte Element ermittelt werden.

<code id="5be9ace330dcb">
function maxElement(feld) {
 var max = feld[0];
 //-- weitere Anweisungen --
 return max;
}
</code>

<check execute="(maxElement([23, 5, 67, 17, 88, 17]) == 88) && (maxElement([-23, -5, -67, -17, -88, -17]) == -5) && (maxElement([0]) == 0);">
true
</check>

<run id="5be9ace330ea9">
var newFeld = erzeugen(1, 100, 50);
var max = maxElement(newFeld);
ausgabe(newFeld);
console.log("Das größte Element im Datenfeld ist " + max + ".");
</run>

</li> 
<li>

=== Gerade und ungerade Feldelemente ===

In einem numerischen Datenfeld sollen gerade und ungerade Feldelemente gezählt werden.

'''Hinweise:'''
<ul>
<li>
Zur Erinnerung: Die Anweisung
<pre>rest = zahl % n;</pre>
gibt den Rest der ganzzahligen Division der Variablen <tt>zahl</tt> und <tt>n</tt> an.
</li>
<li> 
Beachte, dass hier beide Werte in einem ''zweielementigen Feld'' zurückgegeben werden.
</li>
</ul>

<code id="5bfbf1ca90dd3">
function geradeUngerade(feld) {
 var gerade = 0;
 var ungerade = 0;
 var newFeld = new Array();
 //-- weitere Anweisungen --
 return newFeld;
}
</code>

<check execute="(geradeUngerade([23, 5, 67, 17, 88, 17]).join() == '1,5') 
&& (geradeUngerade([-24, -6, -68, -18, -88, 0]).join() == '6,0') 
&& (geradeUngerade([]).join() == '0,0');">
true
</check>

<run id="5bfc246686ed6">
var newFeld = erzeugen(1, 100, 50);
var anzFeld = geradeUngerade(newFeld);
ausgabe(newFeld);
console.log("...");
</run>

</li>
</ol>