Die Datenstruktur Feld

Aus ProgrammingWiki

Inhaltsverzeichnis 1 Begriff 2 Deklaration eines eindimensionalen Feldes 3 Methoden 4 Felder mit Zufallszahlen 5 Sequenzielle Suche 6 Aufgaben 6.1 Effiziente Suchfunktion 6.2 Positionssuche eines Elements 6.3 Anzahl eines Elements 6.4 Größtes Feldelement 6.5 Gerade und ungerade Feldelemente

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.

Mathematik	$a_0, a_1, ... , a_n$
JavaScript	$a[0], a[1], ... , a[n]$

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

Deklaration eines eindimensionalen Feldes

var Feld = new Array(); Feld[0] = "Montag"; Feld[1] = "Dienstag"; Feld[2] = "Mittwoch"; Feld[3] = "Donnerstag"; Feld[4] = "Freitag";

Feld;

ausführen

Methoden

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

var n = Feld.length; var newFeld = Feld.slice(2, 3); Feld.reverse(); var zk = Feld.join();

n;

ausführen

Felder mit Zufallszahlen

Wir haben in der Wiederholung von Datentypen und Programmstrukturen eine Zufallsfunktion für natürliche Zahlen kennen gelernt, die wir um eine linke Intervallgrenze erweitern wollen:

function zufallszahl(von, bis) { return Math.floor(Math.random() * (bis - von + 1) + von); }

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

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

newFeld;

ausführen

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

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

ausgabe(newFeld);

ausführen

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.
Prinzipiell stehen uns zwei syntaktische Programmstrukturen zur Verfügung:

for (var i = 0; i < feld.length; i++) { //-- Anweisungsteil -- }

for (var i in feld) { //-- Anweisungsteil -- }

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

function elementSuche(element, feld) { var exist = false; for (var i in feld) if (element == feld[i]) exist = true; return exist; }

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.");

ausführen

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

Aufgaben

1. Effiziente Suchfunktion

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

   function newElementSuche(element, feld) { var exist = false; var i = 0; while ((! exist) && (i < feld.length)) { exist = (element == feld[i]); i++; } return exist; }

   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.");

   ausführen

2. Positionssuche eines Elements

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

   function elementPosition(element, feld) { var pos = -1; //-- weitere Anweisungen -- return pos; }

    

   Quelltext überprüfen:

   jetzt prüfen

   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.");

   ausführen

3. Anzahl eines Elements

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

   function elementAnzahl(element, feld) { var anz = 0; //-- weitere Anweisungen -- return anz; }

    

   Quelltext überprüfen:

   jetzt prüfen

   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.");

   ausführen

4. Größtes Feldelement

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

   function maxElement(feld) { var max = feld[0]; //-- weitere Anweisungen -- return max; }

    

   Quelltext überprüfen:

   jetzt prüfen

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

   ausführen

5. Gerade und ungerade Feldelemente

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

   Hinweise:

   • Zur Erinnerung: Die Anweisung

     rest = zahl % n;

     gibt den Rest der ganzzahligen Division der Variablen zahl und n an.

   • Beachte, dass hier beide Werte in einem zweielementigen Feld zurückgegeben werden.

   function geradeUngerade(feld) { var gerade = 0; var ungerade = 0; var newFeld = new Array(); //-- weitere Anweisungen -- return newFeld; }

    

   Quelltext überprüfen:

   jetzt prüfen

   var newFeld = erzeugen(1, 100, 50); var anzFeld = geradeUngerade(newFeld); ausgabe(newFeld); console.log("...");

   ausführen