Algorithmen und Datenstrukturen - Kapitel 1

Medientechnik und Design Algorithmen und Datenstrukturen

Medientechnik und Design

Algorithmen und Datenstrukturen

Mag. Volker Christian

FH Oberösterreich – Campus HagenbergFakultät für Informatik, Kommunikation und Medien

Softwarepark 11, 4232 Hagenberg/Austria

Sommersemester 2013

Volker Christian FH-OÖ – Hagenberg – MTD – ADS Sommersemester 2013 1 Pages

Algorithmen und Datenstrukturen Kapitel 1: Einführung

Algorithmen und DatenstrukturenKapitel 1

Einführung

Allgemeines

Überblick über Algorithmen und Datenstrukturen

Volker Christian FH-OÖ – Hagenberg – MTD – ADS 22. Oktober 2013 1-1 | 1/461


AllgemeinesInhalt

1 Form der Lehrveranstaltung

2 Literatur


Algorithmen und Datenstrukturen – Kapitel 1 Einführung

Allgemeines


2 Literatur


Algorithmen und Datenstrukturen – Kapitel 1 Form der Lehrveranstaltung

Lehrveranstaltungen

VorlesungVolker [email protected]

Die Homepage der Vorlesung finden Sie unterhttp://elearning.fh-hagenberg.at/course/view.php?id=2236

Die Vorlesung findet wöchentlich jeweils am Montag von 940 bis 1115 statt.

ÜbungenVolker [email protected]

Die Homepage der Übungen finden Sie unterhttp://elearning.fh-hagenberg.at/course/view.php?id=2237

Es finden neun Übungseinheiten statt.Die Termine werden gesondert bekannt gegeben.


mailto:Volker Christian <[email protected]>

http://elearning.fh-hagenberg.at/course/view.php?id=2236

mailto:Volker Christian <[email protected]>

http://elearning.fh-hagenberg.at/course/view.php?id=2237

Algorithmen und Datenstrukturen – Kapitel 1 Form der Lehrveranstaltung

Beurteilung

VorlesungEs findet eine abschließende Klausur statt.

ÜbungenIn jeder Übungseinheit werden Übungsaufgaben ausgegeben.Diese Übungsaufgaben werden von Tutoren korrigiert und bewertet.Bei jeder Übung können maximal 24 Punkte erreicht werden.Von den neu Übungen werden die besten Acht gewertet.Jede dieser acht Übungen muss für sich selbst positiv (≥ 12 Punkte)sein.Für einen positiven Abschluss müssen insgesamt mehr als 96 Punkteerreicht werden.



Allgemeines


2 Literatur


Algorithmen und Datenstrukturen – Kapitel 1 Literatur

Basisliteratur

Algorithmen in Java(http://www.pearsonhighered.com/educator/product/Algorithms-in-Java-Parts-14/9780201361209.page)

Author: Robert SedgewickVerlag: Pearson StudiumSeiten: 768Preis: e 54.08ISBN: 9780201361209


http://www.pearsonhighered.com/educator/product/Algorithms-in-Java-Parts-14/9780201361209.page


http://www.cs.princeton.edu/~rs/

http://www.pearson-studium.de



Überblick über Algorithmen und DatenstrukturenInhalt

1 Datensätze

2 Datenstrukturen

3 Algorithmen

4 Leitfaden für die Lösung von Problemstellungen

5 Einführendes Beispiel

6 Zusammenfassung


Algorithmen und Datenstrukturen – Kapitel 1 Überblick über Algorithmen und Datenstrukturen

Das große Bild

Beim Studium von Datenstrukturen . . .beschäftigt man sich mit verschiedenen, strukturierten Möglichkeitenzum Verwalten (d.h. Speichern) von Datensätzen.beschäftigt man sich mit der Art, wie man auf Datensätze wiederzugreifen kann.beschäftigt man sich mit der Effizienz verschiedenerDatenverwaltungstrategien.lernt man, selbst problemgerechte Datenstrukturen zu entwickeln.

Beim Studium von Algorithmen . . .beschäftigt man sich mit grundsätzlichen, schematischenLösungsverfahren für elementare Problemstellungen.beschäftigt man sich mit der Effizienz von Lösungsverfahren.lernt man, selbst in strukturierter Weise Lösungsverfahren fürspezifische Problemstellungen zu entwickeln.




1 Datensätze

2 Datenstrukturen

3 Algorithmen



6 Zusammenfassung


Algorithmen und Datenstrukturen – Kapitel 1 Datensätze

Datensätze

Ein Datensatz ist eine Gruppe von inhaltlich zusammenhängendenDatenfeldern.Datensätze sind dem jeweiligen Problem angepasst.Datensätze sind wiederum aus Datensätzen und elementaren Datenaufgebaut.

TelefonbucheintragNameVornameTelefonnummernStraßeOrt. . .

VertexKoordinatenFarbeNormaleNachbarvertizesTexturkoordinaten. . .

Zeichen eines TextesZeichencodeSchriftartSchnitt (Fett,Kursiv, . . . )FarbenUnterstrich. . .



Datensätze beinhalten selbst wieder Datenstrukturen

Telefonbucheintrag (Auszug)Vorname: z.B. Liste oder Array von Zeichen. (Man kann nicht davon

ausgehen, dass es in jeder Programmiersprache eine KlasseString gibt.)

Nummern: z.B. Liste von Telefonnummern. Möglicherweise existierenmehrere Telefonnummern für die betreffende Person.

Vertex (Auszug)Koordinaten: z.B. Array für die Koordinaten x , y und z .

Nachbarn: z.B. Liste von Vertizes.Farbe: z.B. Array für die Komponenten Rot, Grün und Blau.



Implementierung von Datensätzen in Java

Elementare Datensätze besitzen elementare Datentypen, d.h. Wertevon elementaren Datentypen sind elementare Datensätze – bestehenaus einzelnen Bits und Bytes.boolean, byte, char, short, int, long, float, double

Komplexe Datensätze sind Objekte von Klassen.class TelBookEntry, class Vertex, class Symbol, . . .Die öffentlichen Methoden der Klassen bilden die Schnittstelle desDatensatzes.Die Schnittstelle abstrahiert den Datensatz von dessen eigentlicherImplementierung.



Beispiel: Telefonbucheintrag

1 public class TelephoneBookEntry {2 protected String name;3 protected String surName;4 protected String city;5 protected String street;6 protected String[] phoneNumbers;78 public TelephoneBookEntry(String name, String surName, String city, String street, ←↩

String[] phoneNumbers) {9 this.name = name;

10 this.surName = surName;11 this.city = city;12 this.street = street;13 this.phoneNumbers = phoneNumbers.clone();14 }1516 public String getName() { return name; }1718 public void setName(String name) { this.name = name; }

35 }

Listing 1 : TelephoneBookEntry.java




1 Datensätze

2 Datenstrukturen

3 Algorithmen



6 Zusammenfassung


Algorithmen und Datenstrukturen – Kapitel 1 Datenstrukturen

Datenstrukturen verwalten Datensätze

Datenstrukturen werden verwendet, um Daten bzw. Datensätzegeeignet zu verwalten.Eine spezielle Datenstruktur ist definiert durch . . .

die Art der Anordnung und Verknüpfung der Datensätze.mögliche Zugriffsarten auf die Datensätze.

(a) Liste

(b) Baum (c) Hashmap

Abbildung 1 : Beispiele von Datenstrukturen



Elementare Datenstrukturen

Es existieren viele elementare Datenstrukturen. Jede Datenstruktur hatihre Vor- und Nachteile.

Felder (Arrays)Stapelspeicher (Stack)Warteschlangen (Queue)Listen (List)Bäume (Tree)Hashtabellen (Hashtable/Hashmap)Halden (Heaps)Graphen (Graphs)



Charakteristika von Datenstrukturen

Datenstrukturen werden nach folgenden Eigenschaften charakterisiert:Schnittstelle: Zugriffsarten (Operationen) auf die Datenstruktur.

Operationen zum Einfügen von DatensätzenOperationen zum Löschen von DatensätzenOperationen, um auf Datensätze zuzugreifen. . .

Komplexität: Dynamische und statische KomplexitätDynamische Komplexität ist ein Maß für dasLaufzeitverhalten der Schnittstelle und dessenAbhängigkeit von der Zahl gespeicherter Datensätze.Statische Komplexität ist ein Maß für die Komplexitätdes Quelltextes der Implementierung.



Implementierung von Datenstrukturen in Java

Datenstrukturen werden als Klassen implementiert.class List, class Tree, class Array, . . .Die öffentlichen Methoden dieser Klassen bilden die Schnittstelle derDatenstruktur.Die Schnittstelle abstrahiert die Datenstruktur von ihrer eigentlichenImplementierung.Sind Hilfsmethoden und Hilfsklassen notwendig, so werden diese alsnicht öffentlich vereinbart.



Beispiel: Array als Datenstruktur

Eine Datenstruktur ist ein Array, wenn man über einen Index aufDatensätze zugreifen kann.

1 public class Array {2 protected int size = 0;3 protected Object[] array = null;45 public Array(int size) {6 this.size = size; array = new Object[size];7 }89 public void add(int index, Object o) {10 array[index] = o;11 }1213 public Object get(int index) {14 return array[index];15 }1617 public int size() {18 return size;19 }20 }

Listing 2 : Array.java

array0..size

<<array>>

Array

#size:int

+Array(size:int)+add(index:int, o:Object):void+get(index:int):Object+size():int

Object

Abbildung 2 : UML-Class-Diagrammder Klasse Array




1 Datensätze

2 Datenstrukturen

3 Algorithmen



6 Zusammenfassung


Algorithmen und Datenstrukturen – Kapitel 1 Algorithmen

Strukturierte Problemlösungsverfahren

Wortstamm: Verballhornung des Namens Muhammed ibn Musaal-Chwarizmi (b ca. 783, d ca. 850), dessen arabischesLehrbuch „Über das Rechnen mit indischen Ziffern“ (um825) in der mittelalterlichen lateinischen Übersetzung mitden Worten Dixit Algorismi (Algorismi hat gesagt) beginnt.

Bedeutung: Eine Vorschrift zur Lösung einer Problemstellung.Elementare Algorithmen sind Problemlösungsstrategien für verschiedene, inAbwandlungen immer wiederkehrende Problemstellungen.

SortierenSuchenZeichenkettenverarbeitungGeometrie und GrafikNumerik



Charakteristika von Algorithmen

Ein Algorithmus ist eine Vorschrift zur Lösung eines elementaren,unabhängigen Problems und muss . . .

aus einzelnen Schritten zusammengesetzt sein.In jedem Schritt wird eine „Berechnung“ durchgeführt.Bei jedem Schritt ist angegeben, welcher Schritt als nächsterauszuführen ist.

eindeutig ausführbar sein.Es darf kein Interpretationsspielraum, was zu geschehen hat, bestehen.

endlich sein.Statische Endlichkeit: Ein Algorithmus muss sich mit endlich vielenZeichen formulieren lassen.Dynamische Endlichkeit: Ein Algorithmus muss das Problem in endlichvielen Schritten lösen.

Daten verarbeiten.Manipulation – z.B. Sortieren – von bestehenden Daten.Berechnung eines Ergebnisses – z.B. Berechnung der Wurzel aus 9.



Eingangsgrößen und Ausgangsgrößen

Ein Algorithmus muss Zugriff auf die zu verarbeitenden Datensätzeoder die für eine Berechnung heranzuziehenden Werte haben.Ein Algorithmus muss die verarbeiteten Datensätze oder dieErgebnisse einer Rechnung wieder zur Verfügung stellen.

Eingangsgrößen: Die Datenbasis wird einem Algorithmus meist in Formvon Datensätzen in einer Datenstruktur zur Verfügunggestellt.

Ausgangsgrößen: Die Ergebnisse werden von einem Algorithmus meist inForm eine Datenstruktur, eines Datensatzes oder einesWertes zur Verfügung gestellt.



Fehlerfreiheit

Ein Algorithmus muss in allen erdenklichen Situationen wohldefiniertund geeignet reagieren.⇒ Prüfen der Eingangsgrößen auf Plausibilität.⇒ Ist die Ermittlung des Ergebnisses nicht möglich, muss dies vom

Algorithmus geeignet signalisiert werden.



Definition des Algorithmusbegriffs

Versuch einer Definition:Ein Algorithmus ist ein endliches, schrittweises Verfahren zur Berechnunggesuchter aus gegebenen Größen, in dem jeder Schritt aus einer Anzahleindeutig ausführbarer Operationen und einer Angabe über den nächstenSchritt besteht.



Beschreibung von Algorithmen

Spezifikation = Sicht von außenBeschreibung der Problemstellung.Definition des „Was“.Beschreibung der Schnittstelle und deren Verhalten.Der Algorithmus an sich wird als „Black Box“ betrachtet.

Darstellung = Sicht von innenBeschreibung der Lösungsidee.Beschreibung des „Wie“.Beschreibung des eigentlichen Lögungsverfahrens.Muss die spezifizierte Schnittstelle und deren Verhalten zur Verfügungstellen.



Darstellung von Algorithmen

Die Darstellung eines Algorithmus ist eine Meta-Beschreibung – dieBeschreibung einer Beschreibung.

Darstellungsarten:Prosa: Umgangssprachlich in Form eines kurzen „Aufsatzes“.

Stilisiert: Umgangssprachlich, aber schon etwas formalisiert –schrittweise, eindeutig, endlich.

Grafisch: Ablaufdiagramm (Flussdiagramm) oder Struktogramm.Abstrakt: Algorithmenbeschreibungssprache wie Adele oder Jana

(Pseudocode).Konkret: Implementierung in einer Programmiersprache wie Java, C#,

C, C++, Pascal, . . .



Implementierung von Algorithmen als Objekt-MethodenIst ein Algorithmus Teil einer Datenstruktur, so wird der Algorithmus alsObjektmethode implementiert.

Beispiel: Sort-Algorithmus der Klasse List

1 public class List {2 ...34 public void sort() {5 ...6 }78 ...9 }

Die Eingangsgrößen kann der Algorithmus direkt von derDatenstruktur beziehen.Die Ausgangsgrößen kann der Algorithmus direkt in der Datenstrukturablegen oder als Rückgabewert liefern.



Implementierung von Algorithmen als Klassen-MethodenWird ein Algorithmus nicht als Teil einer Datenstruktur formuliert, so wirder als Klassenmethode einer Klasse implementiert.Beispiel: Externer Sort-Algorithmus

1 public class Sort {2 ...34 public static void sort(List list) {5 ...6 }78 ...9 }

Die Eingangsgrößen werden dem Algorithmus über dieAktualparameter übergeben.Die Ausgangsgrößen liefert der Algorithmus über den Rückgabewertoder wenn möglich über Referenz-Aktualparameter (für komplexeoder mehrere Ergebniswerte).




1 Datensätze

2 Datenstrukturen

3 Algorithmen



6 Zusammenfassung


Algorithmen und Datenstrukturen – Kapitel 1 Lösungsleitfaden

Schrittweise Herangehensweise

1 Beschäftigung mit der Thematik.Wenn die Thematik nicht bekannt ist, muss man sich in dieseeinarbeiten!

2 Mit welchen Datensätzen hat man zu tun? Wie können dieDatensätze dargestellt werden?

3 Auswahl einer geeigneten Datenstruktur.Kann eine elementare, bekannte Datenstruktur verwendet werden?Muss eine problemgerechte Datenstruktur entwickelt werden?

4 Spezifizieren der Schnittstelle des Algorithmus und was er zu tun hat.5 Entwicklung und Implementierung des Algorithmus unter

Bedachtnahme auf die ausgewählte Datenstruktur und diespezifizierte Schnittstelle.




1 Datensätze

2 Datenstrukturen

3 Algorithmen



6 Zusammenfassung


Algorithmen und Datenstrukturen – Kapitel 1 Einführendes Beispiel

Ermittlung des Index eines Folgegliedes

Problemstellung:Gegeben: Eine endliche Folge von paarweise disjunkten, ganzen Zahlen.

z = (6, 3, 4, 8, 5, 7, 2, 9, . . . , zn)

Gesucht: Der Index einer gegebenen Zahl der Folge.

Fragestellungen bei der Analyse für die Implementierung:1 Beschäftigen mit der Problemstellung: Was ist eine Folge und was ist

der Index eines Folgegliedes?2 Wie können die ganzen Zahlen in Java dargestellt werden?3 Welche Datenstruktur passt auf das Problem?4 Wie soll der Algorithmus das Problem mit Bedacht auf die

ausgewählte Datenstruktur lösen?Volker Christian FH-OÖ – Hagenberg – MTD – ADS 22. Oktober 2013 1-34 | 34/461


Beschäftigung mit der Problemstellung

Was ist eine Folge und was ist der Index eines Folgegliedes?

Aus Wikipedia:Als Folge wird eine Auflistung endlich oder unendlich vieler, durchOrdinalzahlen fortlaufend nummerierter Objekte bezeichnet.Das Objekt mit der Nummer i , man sagt hier auch: mit dem Index i ,wird i-tes Glied der Folge genannt.Schreibweise:

Endliche Folge: x = (x1, x2, x3, . . . , xn)Unendliche Folge: x = (x1, x2, x3, . . .)

Formale Definition: Eine Folge x ist als Abbildung aus einerIndexmenge I in die Zielmenge X definiert:

x : I → X , wobei I = {1, 2, 3, . . . , n} und X = {xi}x : i 7→ xi



Eine ganze Zahl als Datensatz

In Java können ganze Zahlen durch die elementaren Datentypenbyte, short, int oder long dargestellt werden.

Nach der Regel, dass Datensätze als Objekte von Klassen dargestelltwerden müssen, können die in Java existierenden Wrapperklassen derelementaren Datentypen verwendet werden.

Datentyp Wrapperklassebyte Byteshort Shortint Integerlong Long

Welche dieser Wrapperklasse verwendet werden soll, hängt von demWertebereich der darzustellenden ganzen Zahlen ab.



Eine ganze Zahl als Datensatz

Ein Objekt der Wrapperklasse Long repräsentiert einen long-Wert

1 package java.lang;23 public class Long {4 public Long(long l); // Constructor56 public int compareTo(Long anotherLong);7 // < 0, if longValue() < anotherLong.longValue()8 // = 0, if longValue() == anotherLong.longValue()9 // > 0, if longValue() > anotherLong.longValue()

1011 public long longValue(); // The represented value1213 public String toString(); // The value as a String1415 public static Long valueOf(long l); // Create an Object from a value16 }

Listing 3 : Auszug aus der Klasse Long



Welche Datenstruktur passt auf das Problem?

Welche Funktionalitäten muss die Datenstruktur zur Verfügung stellen?Die Reihenfolge der Folgeglieder muss in der Datenstruktur erhaltenbleiben.Es soll möglich sein, auf einzelne Objekte der Folge direkt über ihrenIndex zugreifen zu können.

Eine mögliche und in diesem Fall gute Wahl ist die Verwendung einesArrays.

In Arrays bleibt die Reihenfolge der Elemente erhalten.In Arrays kann über den Array-Index auf die einzelnen Elementezugegriffen werden.Achtung:

Das erste Element einer Folge trägt typischerweise den Index 1.Das erste Element eines Arrays trägt den Index 0.



Die Datenstruktur Array

Array als Klasse

1 public class Array {2 protected int size = 0;3 protected Object[] array = null;45 public Array(int size) {6 this.size = size; array = new Object[size];7 }89 public void add(int index, Object o) {

10 array[index] = o;11 }1213 public Object get(int index) {14 return array[index];15 }1617 public int size() {18 return size;19 }20 }

Listing 4 : Array.java



Spezifikation des Algorithmus: Version 1

1 Name: Der Algorithmus heißt indexSearch und wird alsKlassenmethode der Klasse IndexSearch implementiert.

2 Eingangsgrößen: Dem Algorithmus wird ein mit Long-Objektengefülltes Objekt der Klasse Array und ein long-Wert als Schlüssel, inForm eines Objektes der Klasse Long, übergeben.

3 Ausgangsgrößen: Der Algorithmus ermittelt den (mathematischen)Index des Schlüssels und gibt diesen als Ergebnis zurück.

4 Schnittstelle:int indexSearch(Array array, Long key);

5 Fehlerfälle:Ist der Schlüssel nicht im Array gespeichert, so soll dies durch denRückgabewert -1 angezeigt werden.



Darstellung des Algorithmus

DatenrepräsentationJedes Glied der Folge wird in ein Element des Array gespeichert.Die Reihenfolge der Folgeglieder und deren Repräsentation alsElemente im Array soll identisch sein.⇒ Die Indizes index der Elemente des Arrays korrespondieren mit den

Indizes i der Folgeglieder, wobei ein Offset von 1 besteht:

index = i − 1.

ArbeitsweiseSchleife über alle Elemente des Arrays.Jedes Element des Arrays mit der gegebenen Zahl vergleichen.Sind beide gleich, ist der Index i der gegebenen Zahl gleich dem Indexdes Elements im Array plus eins: index + 1.



Ermittlung des Index eines FolgegliedesProsa

Man nehme die gegebene Folge und wähle die erste Position der Folge alsaktuelle Position.Ist die aktuelle Position außerhalb der gegebenen Folge, ist dievorgegebene Zahl nicht Element der Folge und die Suche kann somit nichterfolgreich beendet werden. Ist die Zahl an der aktuellen Position gleichder gesuchten Zahl, so ist die aktuelle Position in der gegebenen Folge dieOrdinalzahl, d.h. der Index der vorgegebenen Zahl und die Suche könnensomit erfolgreich beendet werden. Ist die Zahl an der aktuellen Positionnicht die gesuchte Zahl, so gehe zur nächsten Position in der Folge undwiederhole den in diesem Absatz beschriebenen Vorgang!



Ermittlung des Index eines FolgegliedesStilisierte Prosa

1 Wähle die erste Position der Folge als aktuelle Position.2 Liegt die aktuelle Position außerhalb der Folge (aktuelle Position

> |F |), gehe zu Schritt 6!3 Ist die Zahl an der aktuellen Position der Folge gleich der

vorgegebenen Zahl, dann gehe zu Schritt 5!4 „Erhöhe“ die aktuelle Position um 1 und gehe zu Schritt 2!5 Die gesuchte Ordinalzahl, also der Index der vorgegebenen Zahl, ist

die aktuelle Position.6 Ende des Algorithmus.



Ermittlung des Index eines FolgegliedesFlussdiagramm

indexsearch(F , vZahl)

i = 1

? i > |F |

? Fi == vZahl

i = i + 1

index = i

End

Y

Y

N

N



Der fertig implementierte Algorithmus

Der Algorithmus indexSearch

1 public class IndexSearch {2 public static int indexSearch(Array array, Long key) {3 for (int i = 0; i < array.size(); i++) { // Iterate over every index4 Long currentLong = (Long) array.get(i);56 if (key.compareTo(currentLong) == 0) { // Found?7 return i + 1; // Found: Return the8 // adjusted index9 }

10 }11 return -1; // Not found: Return -112 }13 }

Listing 5 : IndexSearch.java



Testen des Algorithmus

Ein Test-Treiber für indexSearch1 public class IndexSearchTreiber {2 public static void main(String[] args) {3 Array array = new Array(10);45 for (int i = 0; i < 10; i++) {6 array.add(i, new Long(100 + i));7 }89 Long key = new Long(102);

10 int index = IndexSearch.indexSearch(array, key);1112 System.out.println("Index␣of␣" + key + ":␣" + index);13 }14 }

Listing 6 : IndexSearchTreiber.java



Spezifikation des Algorithmus: Version 2

1 Name: Der Algorithmus heißt indexSearch und wird alsObjektmethode der Klasse ArrayWithIndexSearch implementiert.

2 Eingangsgrößen: Der Algorithmus kann direkt auf die Elemente derKlasse ArrayWithIndexSearch zugreifen. Zusätzlich wird ihm einlong-Wert als Schlüssel, in Form eines Objektes der Klasse Long,übergeben.

3 Ausgangsgrößen: Der Algorithmus ermittelt den (mathematischen)Index des Schlüssels und gibt diesen als Ergebnis zurück.

4 Schnittstelle:int indexSearch(Long key);

5 Fehlerfälle:Ist der Schlüssel nicht im Array gespeichert, so soll dies durch denRückgabewert -1 angezeigt werden.



indexSearch als Objektmethode

Algorithmen können, auch als Objektmethoden implementiert werden.

Der Algorithmus indexSearch also Objektmethode

1 public class ArrayWithIndexSearch extends Array { // Inherit Array as base2 public ArrayWithIndexSearch(int size) {3 super(size);4 }56 public int indexSearch(Long key) {7 for (int i = 0; i < this.size(); i++) { // Iterate over every index8 Long currentLong = (Long) this.get(i);9

10 if (key.compareTo(currentLong) == 0) { // Found?11 return i + 1; // Found: Return the12 // adjusted index13 }14 }15 return -1; // Not found: Return -116 }17 }

Listing 7 : ArrayWithIndexSearch.java



Wieder ein Test-Treiber

Ein Test-Treiber für indexSearch als Objektmethode

1 public class ArrayWithIndexSearchTreiber {2 public static void main(String[] args) {3 ArrayWithIndexSearch array = new ArrayWithIndexSearch(10);45 for (int i = 0; i < 10; i++) {6 array.add(i, new Long(100 + i));7 }89 Long key = new Long(102);

10 int index = array.indexSearch(key);1112 System.out.println("Index␣of␣" + key + ":␣" + index);13 }14 }

Listing 8 : ArrayWithIndexSearchTreiber.java




1 Datensätze

2 Datenstrukturen

3 Algorithmen



6 Zusammenfassung


Algorithmen und Datenstrukturen – Kapitel 1 Zusammenfassung

Algorithmen und Datenstrukturen

Algorithmen verarbeiten meist eine Menge von Datensätzen.Diese Datensätze müssen in geeigneter Weise in Datenstrukturenverwaltet werden.Algorithmen greifen über die Schnittstellen der Datenstrukturen aufdie Daten zu.Die Schnittstellen der Datenstrukturen sind selbst wieder Algorithmen.

Fazit:Algorithmen und Datenstrukturen bilden eine Einheit. Datenstrukturenverwalten Datensätze und Algorithmen verarbeiten diese. Dabei bedienensich die Algorithmen der Schnittstellen der Datenstrukturen, um auf dieDatensätze zugreifen zu können und der Schnittstellen der Datensätze, umdiese zu verarbeiten.


Education

Algorithmen und Datenstrukturen - Kapitel 1