arrays und vectors,
Transcrição
arrays und vectors,
1 7 arrays und vectors, Suchen und Sortieren 2006 Pearson Education, Inc. All rights reserved. 2 7.1 7.2 7.3 7.4 7.5 7.6 7.7 7.8 7.9 7.10 Einführung Arrays Deklaration von arrays Beispiele zum Gebrauch von arrays Übergabe von arrays an Funktionen Fallstudie: Die Klasse GradeBook mit einem array Einführung in die C++ STL Klasse vector Suchen und Sortieren 7.8.1 Lineare Suche 7.8.2 Binäre Suche 7.8.3 Sortieren durch direktes Einfügen (Insertion-Sort) 7.8.4 Merge-Sort (rekursive Implementierung) Mehrdimensionale arrays Fallstudie: Die Klasse GradeBook mit einem zweidimensionalen array 2006 Pearson Education, Inc. All rights reserved. 3 7.1 Einführung • Array – Datenstruktur, die zusammengehörige Datenelemente desselben Typs enthält – Datenstruktur der Sprache C++ (‘STL-Klasse') in zwei Varianten: • array: Behält immer die Größe, in der es vom Compiler während des Übersetzungsvorgangs erzeugt wurde – Weniger komfortabel zu nutzen, aber schneller und weniger Speicherverbrauch (normalerweise auf Stack) • vector: Größe kann während der Programmausführung verändert werden – Bei Bedarf automatisches Wachsen und Schrumpfen, aber langsamer und mehr Speicherverbrauch (auf Heap) 2006 Pearson Education, Inc. All rights reserved. 4 7.1 Einführung • Arrays in C++ und C – Statt der in diesem Kapitel behandelten C++-Arrays (array und vector) kann in C++ auch das ‘eingebaute (built-in)’ Array aus C verwendet werden. • Diese ‘C-Arrays’ sind unsicherer und weniger komfortabel zu nutzen. • Wegen ihrer Bedeutung für einige Anwendungsgebiete (s. z.B. Veranstaltung ‘Betriebssysteme’) werden sie im Kapitel 8 im Zusammenhang mit Zeigern noch ausführlich besprochen. 2006 Pearson Education, Inc. All rights reserved. 5 7.2 Arrays • Array (array, vector und C-Array) – Gruppe aufeinanderfolgender Speicherplätze • Alle haben denselben Typ. – Index • Ganzzahliger Positionszähler, der einen spezifischen Platz, d.h ein spezifisches Element im Array anspricht • Wird in eckige Klammern [ ] gesetzt – Muss positive ganze Zahl oder ganzzahliger Ausdruck sein • Das erste Element des Arrays hat den Index 0. 2006 Pearson Education, Inc. All rights reserved. 6 Fig.7.1 | Array mit 12 Elementen 2006 Pearson Education, Inc. All rights reserved. 7 7.2 Arrays • Für das Array c in Fig. 7.1 gilt – c ist der Arrayname – c hat 12 Elemente ( c[0], c[1], … c[11] ) • Der Wert von c[0] ist –45 • Die eckigen Klammern, die einen Arrayindex umschließen, sind in C++ ein Operator. 2006 Pearson Education, Inc. All rights reserved. 8 Häufiger Programmierfehler Es ist wichtig, sich den Unterschied zwischen dem “siebten Element des Arrays” und dem “Array Element mit Index 7” klar zu machen: Array Indices beginnen mit 0, so dass das “siebte Element des Arrays” den Index 6 hat, während das “Array Element mit Index 7” das achte Element des Arrays ist. Dieser Unterschied führt häufig zu einem ‘Eins-daneben-Fehler (off-by-one error)’. 2006 Pearson Education, Inc. All rights reserved. 9 Operatoren Assoziativität Typ () [] links nach rechts Klammern, Index ++ -- static_cast< Typ >( Operand ) links nach rechts unär (postfix) ++ -- + rechts nach links unär (prefix) * / % links nach rechts multiplikativ + - links nach rechts additiv << >> links nach rechts Ausgabe / Eingabe < <= links nach rechts Vergleich == != links nach rechts Gleichheit && links nach rechts logisches UND || links nach rechts logisches ODER ?: rechts nach links Bedingung rechts nach links Zuweisung links nach rechts Komma = , += > -= - ! >= *= /= %= Fig.7.2 | Operatorvorrang und Assoziativiät. 2006 Pearson Education, Inc. All rights reserved. 10 7.3 Deklaration von arrays – arrays belegen Platz im Speicher. – Vom Programmierer werden Typ und Anzahl der Elemente als Typparameter bzw. Nichttypparameter des Klassentemplates array angegeben: array< int, 12 > c; • c ist ein Array von 12 ints – Die arraygröße muss eine ganzzahlige Konstante größer als Null sein. – arrays können Werte jedes Datentyps (auch selbstdefinierte Klassen) enthalten, jedoch keine Referenzen. – Mehrere arrays des gleichen Elementtyps und der gleichen Elementanzahl können in einer einzigen Deklaration deklariert werden. • Mit einer kommaseparierten Liste der Namen 2006 Pearson Education, Inc. All rights reserved. 11 7.4 Beispiele zum Gebrauch von arrays • Einsatz einer Schleife zur Initialisierung der arrayelemente – Deklaration des arrays mit Angabe von Typ und Anzahl der Elemente – Wiederholungsanweisung, um jedes Arrayelement anzusprechen • Im Körper der Wiederholungsanweisung wird jedes einzelne Arrayelement initialisiert. 2006 Pearson Education, Inc. All rights reserved. 1 // Fig. 7.3: fig07_03.cpp 2 // Initializing an array's elements to zeros and printing the array. 3 #include <iostream> 4 #include <iomanip> 5 #include <array> 6 using namespace std; fig07_03.cpp 8 int main() (1 von 1) 9 { Der Header <array> muss eingeschlossen werden. 7 10 array< int, 10 > n; // n is an array of 10 integers 11 // initialize elements of array n to 0 12 for( size_t i = 0; i < n.size(); ++i ) { 13 n[ i ] = 0; // set element at location i to 0 14 } 15 cout << "Element" << setw( 13 ) << "Value" << endl; 16 // output each array element's value 17 for( size_t j = 0; j < n.size(); ++j ) { 18 19 Outline 12 cout << setw( 7 ) << j << setw( 13 ) << n[ j ] << endl; } 20 } // end main Element 0 1 2 3 4 5 6 7 8 9 Value 0 0 0 0 0 0 0 0 0 0 n[ j ] gibt den int zurück, der dem Index j im Array n zugeordnet ist. Jeder int wurde mit 0 initialisiert. 2006 Pearson Education, Inc. All rights reserved. 13 7.4 Beispiele zum Gebrauch von arrays • Die Kontrollvariablen i und j, die die Indices der arrayelemente bezeichnen, werden mit dem Typ size_t deklariert. – size_t stellt laut C++ Standard einen ganzzahligen Typ ohne Vorzeichen dar. – Dieser Typ soll für jede Variable, die die Größe oder die Indices von Arrays repäsentiert, verwendet werden. – size_t ist definiert im Namensbereich std und im Header <cstddef>, der von verschiedenen anderen Headern eingeschlossen wird. 2006 Pearson Education, Inc. All rights reserved. 14 7.4 Beispiele zum Gebrauch von arrays • Initialisierung eines arrays bei der Deklaration mit Hilfe einer Initialisierungsliste – Initialisierungsliste • Werte werden in geschweifte Klammern ({}) eingeschlossen. • Einzelne Werte in der Liste werden durch Kommas getrennt. • Beispiel array< int, 5 > n = { 10, 20, 30, 40, 50 }; • Es wird ein Array mit 5 Elementen erzeugt. • Die Indexwerte sind 0, 1, 2, 3, 4. • Die Werte werden mit 10, 20, 30, 40, 50 initialisiert. 2006 Pearson Education, Inc. All rights reserved. 15 7.4 Beispiele zum Gebrauch von arrays • Initialisierung eines Arrays bei der Deklaration mit Hilfe einer Initialisierungsliste – Falls weniger Initialisierungswerte angegeben werden als Elemente im Array vorhanden sind, werden die restlichen Elemente entsprechend ihres Typs wertinitialisiert ( int z.B. mit 0 ). • Beispiel array< int, 10 > n = { 0 }; • Initialisiert das erste Element explizit mit 0. • Initialisiert die restlichen neun Elemente implizit mit 0. • Bei einer leeren Initialisierungsliste {} werden alle Elemente implizit wertinitialisiert. 2006 Pearson Education, Inc. All rights reserved. 16 Häufiger Programmierfehler Falls mehr Initialisierungswerte angegeben werden als Elemente im Array vorhanden sind, führt dies zu einer Fehlermeldung des Compilers. 2006 Pearson Education, Inc. All rights reserved. 1 // Fig. 7.4: fig07_04.cpp 2 // Initializing an array in a declaration. 3 #include <iostream> 4 #include <iomanip> 5 #include <array> 6 using namespace std; fig07_04.cpp 8 int main() (1 von 1) 9 { 7 10 // use initializer list to initialize array n 11 array< int, 10 > n = { 32, 27, 64, 18, 95, 14, 90, 70, 60, 37 }; Outline 17 12 13 cout << "Element" << setw( 13 ) << "Value" << endl; 14 15 // output each array element's value 16 for( size_t i = 0; i < n.size(); ++i ) { 17 18 cout << setw( 7 ) << i << setw( 13 ) << n[ i ] << endl; } 19 } // end main Element 0 1 2 3 4 5 6 7 8 9 Value 32 27 64 18 95 14 90 70 60 37 2006 Pearson Education, Inc. All rights reserved. 18 7.4 Beispiele zum Gebrauch von arrays • Beispiel: Festlegen der arraygröße mit einer konstanten Variablen und Setzen der arrayelemente aufgrund von Berechnungen – Ein 10-elementiges array soll mit geraden Zahlen (beginnend mit 2) gefüllt werden. – Für die Festlegung der Größe des arrays kann eine als const deklarierte Variable verwendet werden. – Dann wird eine Wiederholungsstruktur benutzt, die den Wert für das aktuelle Element berechnet und das arrayelement mit dem berechneten Wert initialisiert. 2006 Pearson Education, Inc. All rights reserved. 1 // Fig. 7.5: fig07_05.cpp 2 // Set array s to the even integers from 2 to 20. 3 #include <iostream> 4 #include <iomanip> 5 #include <array> 6 using namespace std; fig07_05.cpp 8 int main() 9 { (1 von 1) Outline 7 10 // constant variable can be used to specify array size 11 const size_t arraySize = 10; 12 array< int, arraySize > s; // array s has 10 elements 13 14 Soll die Arraygröße mit einer Variablen festgelegt werden, muss diese als const erklärt werden. for( size_t i = 0; i < arraySize; ++i ) { // set the values 15 s[ i ] = 2 + 2 * i; 16 } 17 cout << "Element" << setw( 13 ) << "Value" << endl; 18 // output contents of array s in tabular format 19 for( size_t j = 0; j < arraySize; ++j ) { 20 21 19 Die Schleifenvariable wird als Arrayindex und als Rechengröße verwendet. cout << setw( 7 ) << j << setw( 13 ) << s[ j ] << endl; } 22 } // end main Element 0 1 2 3 4 5 6 7 8 9 Value 2 4 6 8 10 12 14 16 18 20 2006 Pearson Education, Inc. All rights reserved. 20 7.4 Beispiele zum Gebrauch von arrays • Konstante Variablen – Deklaration unter Verwendung des const Qualifizierers – Auch als Namenskonstanten oder Read-Only-Variablen bezeichnet – Müssen zum Zeitpunkt ihrer Deklaration mit einem konstanten Ausdruck initialisiert werden und können danach nicht mehr modifiziert werden – Können überall dort stehen, wo ein konstanter Ausdruck erwartet wird 2006 Pearson Education, Inc. All rights reserved. 21 Häufiger Programmierfehler Wird einer konstanten Variablen bei ihrer Deklaration kein Wert zugewiesen, führt dies zu einer Fehlermeldung des Compilers. Wird einer konstanten Variablen in einer ausführbaren Anweisung ein Wert zugewiesen, führt dies zu einer Fehlermeldung des Compilers. 2006 Pearson Education, Inc. All rights reserved. 1 // Fig. 7.7: fig07_07.cpp 2 // A const variable must be initialized. 3 4 int main() 5 { 6 const int x; // Error: x must be initialized fig07_07.cpp x = 7; // Error: cannot modify a const variable (1 von 1) 7 8 9 Outline } // end main 22 Fehlermeldung des Microsoft Visual C++ Compilers: C:\fig07_07.cpp(6) : error C2734: 'x' : const object must be initialized if not extern C:\fig07_07.cpp(8) : error C2166: l-value specifies const object Fehlermeldung des GNU C++ Compilers: fig07_07.cpp:6: error: uninitialized const `x' fig07_07.cpp:8: error: assignment of read-only variable `x' 2006 Pearson Education, Inc. All rights reserved. 23 Häufiger Programmierfehler Nur Konstanten können zur Deklaration der Größe von arrays verwendet werden. Wird hierfür keine Konstante verwendet, führt dies zu einer Fehlermeldung des Compilers. Soll die Arraygröße veränderbar sein, muss ein vector verwendet werden (s. Abschnitt 7.7) . 2006 Pearson Education, Inc. All rights reserved. 24 Betrachtung zum Software Engineering Die Festlegung von arraygrößen mit konstanten Variablen anstelle von Literalkonstanten macht Programme skalierbarer. Soll das array bzw. mehrere gleich große arrays eine andere Größe bekommen, muss nur an einer einzigen Stelle im Programm die Definition der konstanten Variablen geändert werden. 2006 Pearson Education, Inc. All rights reserved. 25 7.4 Beispiele zum Gebrauch von arrays • Aufsummieren der Elemente eines arrays – arrayelemente können eine Folge von Werten darstellen. • Diese Werte können wie folgt aufsummiert werden: • Innerhalb einer Schleife wird jedes arrayelement angesprochen. – Der Wert jedes Elementes wird zu einer laufenden Summe aufaddiert. 2006 Pearson Education, Inc. All rights reserved. 26 7.4 Beispiele zum Gebrauch von arrays • Bereichsbasierte for-Schleife – Um über alle Elemente in einem Array (bzw. allgemeiner: Container) zu iterieren, gibt es eine kürzere Form der forSchleife, die bereichsbasierte for-Schleife: • for( int n : numbers ) { cout << n << ' '; } • Alle Elemente des int arrays numbers werden der Reihe nach über den Bezeichner n angesprochen. • Hierdurch ist die Definition eines Zählers zum Durchlaufen des Arrays nicht mehr nötig und die häufige Fehlerquelle, dass dieser Zähler den erlaubten Bereich für die Indices verlässt, wird vermieden. 2006 Pearson Education, Inc. All rights reserved. 1 // Fig. 7.8: fig07_08.cpp 2 // Compute the sum of the elements of an array. 3 #include <iostream> 4 #include <array> 5 using namespace std; Outline 27 fig07_08.cpp 6 7 int main() 8 { 9 const size_t arraySize = 10; // specifies size of array 10 array< int, arraySize > numbers = { 42, 15, 94, 8, 23, 78, 4, 91, 16, 87 }; 11 int total = 0; (1 von 1) 12 13 // sum contents of array numbers 14 for( int n : numbers ) { 15 16 total += n; } 17 18 cout << "Total of array elements: " << total << endl; 19 } // end main Total of array elements: 458 2006 Pearson Education, Inc. All rights reserved. 28 7.4 Beispiele zum Gebrauch von arrays • Graphische Darstellung von arraydaten durch Histogramme – Eine einfache Darstellung der Werte in einem array kann durch ein um 90 Grad gedrehtes Histogramm, das z.B. aus Sternchen (*) aufgebaut wird, realisiert werden. – Im folgenden Beispiel wird dies für eine Verteilung von Prozentpunkten auf elf Bereiche demonstriert. – Geschachtelte for Anweisungen steuern die Ausgabe des Histogramms. 2006 Pearson Education, Inc. All rights reserved. 1 // Fig. 7.9: fig07_09.cpp 2 // Bar chart printing program. 3 #include <iostream> 4 #include <iomanip> 5 #include <array> 6 using namespace std; fig07_09.cpp 8 int main() (1 von 2) 9 { Outline 29 7 10 const size_t size = 11; 11 array< unsigned, size > numbers = { 0, 0, 0, 0, 4, 15, 23, 42, 16, 8, 0 }; 12 13 cout << "Grade distribution:" << endl; 14 // for each element of array numbers, output a bar of the chart 15 for( size_t i = 0; i < size; ++i ) { 16 // output bar labels ("0-9:", ..., "90-99:", "100:" ) 17 if( 0 == i ) 18 cout << " 19 else if( 10 == i ) 20 21 0-9: "; cout << " 100: "; else 22 cout << i * 10 << "-" << ( i * 10 ) + 9 << ": "; 23 // print bar of asterisks 24 for( unsigned stars = 0; stars < numbers[ i ]; ++stars ) { 25 cout << '*'; 26 } 27 cout << endl; // start a new line of output 28 Für jedes Arrayelement wird die entsprechende Anzahl von Sternchen ausgegeben } // end outer for 29 } // end main 2006 Pearson Education, Inc. All rights reserved. Grade distribution: 0-9: 10-19: 20-29: 30-39: 40-49: **** 50-59: *************** 60-69: *********************** 70-79: ****************************************** 80-89: **************** 90-99: ******** 100: Outline 30 fig07_09.cpp (2 von 2) 2006 Pearson Education, Inc. All rights reserved. 31 7.4 Beispiele zum Gebrauch von arrays • Die Elemente eines arrays als Zähler verwenden – Ein array soll zur Zählung von ganzzahligen Größen verwendet werden (Beispiel: Häufigkeit der Augenzahlen eines Würfels). – Die Größen, die gezählt werden sollen, spielen die Rolle der Indices des arrays. – Immer wenn eine Größe als Index benutzt wird, wird der zugehörige arraywert um Eins erhöht. – Dadurch entsteht die Häufigkeitsverteilung der zu zählenden Größen in dem array. – Im folgenden Beispiel wird dies für die Häufigkeitsverteilung beim Würfeln mit einem Würfel demonstriert. 2006 Pearson Education, Inc. All rights reserved. 1 // Fig. 7.10: fig07_10.cpp 2 // Frequency of rolling a six-sided die 6,000,000 times using an array. 3 #include <iostream> 4 #include <iomanip> 5 #include <array> 6 #include <random> 7 #include <ctime> 8 using namespace std; Outline 32 fig07_10.cpp (1 von 2) 9 10 int main() 11 { 12 default_random_engine engine( static_cast< unsigned >( time( nullptr ) ) ); 13 uniform_int_distribution< unsigned > randomInt( 1, 6 ); 14 15 const size_t arraySize = 7; // ignore element zero 16 array< unsigned, arraySize > frequency = { 0 }; // initialize to 0s 17 18 // roll die 6,000,000 times; use die value as frequency index 19 for( unsigned roll = 1; roll <= 6000000; ++roll ) { 20 ++frequency[ randomInt( engine ) ]; 21 } 22 cout << "Face" << setw( 13 ) << "Frequency" << endl; 23 // output each array element's value 24 for( size_t face = 1; face < arraySize; ++face ) { 25 cout << setw( 4 ) << face << setw( 13 ) << frequency[ face ] 26 27 Inkrementierung des frequency Wertes an der Indexposition, die durch die Zufallszahl ausgewählt wird << endl; } 28 } // end main 2006 Pearson Education, Inc. All rights reserved. Face 1 2 3 4 5 6 Frequency 1000167 1000149 1000152 998748 999626 1001158 Outline 33 fig07_10.cpp (2 von 2) 2006 Pearson Education, Inc. All rights reserved. 34 7.4 Beispiele zum Gebrauch von arrays • Aufsummieren von Umfrageresultaten mit arrays – 40 Studenten bewerten das Mensaessen • Skala von 1-10 : 1 bedeutet furchtbar, 10 bedeutet exzellent – Die 40 Antworten werden in einem array gespeichert. – Zur Erstellung einer Zusammenfassung der Ergebnisse, d.h. einer Häufigkeitsverteilung, wird jedes Element des arrays als Zähler für eines der möglichen Umfrageresultate verwendet. 2006 Pearson Education, Inc. All rights reserved. 1 // Fig. 7.11: fig07_11.cpp 2 // Student poll program. 3 #include <iostream> 4 #include <iomanip> 5 #include <array> 6 using namespace std; fig07_11.cpp 8 int main() 9 { (1 von 2) Outline 7 10 const size_t responseSize = 40; // size of array responses 11 12 const size_t frequencySize = 11; // size of array frequency 13 // place survey responses in array responses 14 const array< unsigned int, responseSize > responses = { 1, 2, 6, 4, 15 8, 5, 9, 7, 8, 10, 1, 6, 3, 8, 6, 10, 3, 8, 2, 7, 6, 5, 7, 6, 8, 16 6, 7, 5, 6, 6, 5, 6, 7, 5, 6, 4, 8, 6, 8, 10 }; 35 17 18 // initialize frequency counters to 0 19 array< unsigned int, frequencySize > frequency = { 0 }; 20 21 // for each answer, select responses element and use that value 22 // as frequency subscript to determine element to increment 23 for( size_t answer = 0; answer < responseSize; ++answer ) { 24 ++frequency[ responses[ answer ] ]; 25 } 26 cout << "Rating" << setw( 17 ) << "Frequency" << endl; 27 // output each array element's value 28 for( size_t rating = 1; rating < frequencySize; ++rating ) { 29 30 31 Für jede Antwort wird der frequency Wert an der zugehörigen Indexposition inkrementiert cout << setw( 6 ) << rating << setw( 17 ) << frequency[ rating ] << endl; } 32 } // end main 2006 Pearson Education, Inc. All rights reserved. Rating 1 2 3 4 5 6 7 8 9 10 Frequency 2 2 2 2 5 11 5 7 1 3 Outline 36 fig07_11.cpp (2 von 2) 2006 Pearson Education, Inc. All rights reserved. 37 7.5 Übergabe von arrays an Funktionen • Funktionsprototypen von Funktionen, die arrays als Argumente übernehmen – Die Parameterliste der Funktion muss einen arrayparameter festlegen. • Beispiel: void modifyArray( array< int, arraySize > ); – Der arrayparameter muss Typ und Anzahl der Elemente einschließen. • Nur dann ist das Klassentemplate array ein vollständiger Typ. 2006 Pearson Education, Inc. All rights reserved. 38 7.5 Übergabe von arrays an Funktionen • Übergabe eines Arrays als Argument an eine Funktion – Angabe des Arraynamens (ohne weitere Informationen) • Array a ist deklariert als array< int, arraySize > a; • Der Funktionsaufruf modifyArray( a ); übergibt das array a einschließlich der Information über seine Größe an die Funktion modifyArray. – Die Arraygröße ist in der Funktion – z.B. über a.size() verfügbar. 2006 Pearson Education, Inc. All rights reserved. 39 7.5 Übergabe von arrays an Funktionen •arrays werden wertmäßig übergeben. – Der Funktionsaufruf übergibt eine Kopie des arrays an die aufgerufene Funktion. • Änderungen innerhalb der Funktion wirken sich nur auf die Kopie aus, das Original im aufrufenden Programmteil bleibt unverändert. – Das gilt genauso für vector und alle anderen STLContainer. – Im Gegensatz dazu werden C-Arrays wegen ihres simpleren Aufbaus referenzmäßig an Funktionen übergeben (Details hierzu s. Kapitel 8). 2006 Pearson Education, Inc. All rights reserved. 40 7.5 Übergabe von arrays an Funktionen • Einzelne Arrayelemente werden auch wertmäßig übergeben. – Sie werden als Skalare oder skalare Größen bezeichnet. – Um ein einzelnes Element an eine Funktion zu übergeben, muss der indizierte Name des arrayelements als Argument verwendet werden. 2006 Pearson Education, Inc. All rights reserved. 1 // Fig. 7.14: fig07_14.cpp 2 // Passing arrays and individual array elements to functions. 3 #include <iostream> 4 #include <iomanip> 5 #include <array> 6 using namespace std; fig07_14.cpp const int arraySize = 5; // size of array a; global CONSTANT is okay (1 von 3) 7 8 9 Outline 41 10 void modifyArray( array< int, arraySize > ); // receive array 11 void modifyElement( int ); // receive array element value 12 13 int main() Funktion übernimmt ein array als Argument 14 { 15 array< int, arraySize > a = { 0, 1, 2, 3, 4 }; // initialize array a 16 17 cout << "Effects of passing entire array by value:" 18 << "\n\nThe values of the original array are:\n"; 19 // output original array elements 20 for( const int& elem : a ) { 21 22 cout << setw( 3 ) << elem; } 23 24 cout << endl; 25 26 // pass array a to modifyArray by value 27 modifyArray( a ); 28 cout << "The values of the array after modifyArray are:\n"; 29 30 // array elements are unaffected for( const int& elem : a ) { 31 32 cout << setw( 3 ) << elem; } 2006 Pearson Education, Inc. All rights reserved. 33 34 cout << "\n\n\nEffects of passing array element by value:" 35 36 37 modifyElement( a[ 3 ] ); // pass array element a[ 3 ] by value 38 cout << "a[3] after modifyElement: " << a[ 3 ] << endl; << "\n\na[3] before modifyElement: " << a[ 3 ] << endl; Outline 39 } // end main fig07_14.cpp 40 41 // in function modifyArray, "b" is a local copy of (2 von 3) 42 42 // the original array "a" passed from main 43 void modifyArray( array< int, arraySize > b ) 44 { 45 for( int& elem : b ) { 46 elem *= 2; // multiply each array element by 2 47 } 48 cout << "The values of the array in modifyArray are:\n"; 49 for( const int& elem : b ) { 50 51 cout << setw( 3 ) << elem; } 52 cout << endl; 53 } // end function modifyArray 54 55 // in function modifyElement, "e" is a local copy of 56 // array element a[ 3 ] passed from main 57 void modifyElement( int e ) 58 { 59 e *= 2; // multiply parameter by 2 60 cout << "Value of element in modifyElement: " << e << endl; 61 } // end function modifyElement 2006 Pearson Education, Inc. All rights reserved. Effects of passing entire array by value: The values of 0 1 2 3 The values of 0 2 4 6 The values of 0 1 2 3 the original array are: 4 the array in modifyArray are: 8 the array after modifyArray are: 4 Outline 43 fig07_14.cpp (3 von 3) Effects of passing array element by value: a[3] before modifyElement: 3 Value of element in modifyElement: 6 a[3] after modifyElement: 3 2006 Pearson Education, Inc. All rights reserved. 7.6 Fallstudie: Die Klasse GradeBook mit einem array 44 • Klasse GradeBook – Stellt eine Notenliste dar, die Punktzahlen speichert und analysiert – Soll jetzt die Punktzahlen in einem array speichern • Statische (static) Datenelemente – Werden auch Klassenvariablen genannt – Variablen, für die die Objekte einer Klasse keine eigenen Kopien enthalten • Eine einzige Instanz einer Klassenvariablen wird von allen Objekten der Klasse gemeinsam benutzt. – Auf diese Variablen kann auch zugegriffen werden, wenn keine Objekte der Klasse existieren. • Dazu wird der Klassenname gefolgt vom Scopeoperator :: und dem Namen des static Datenelements benutzt. – Ganzzahlige const static Datenelemente dürfen innerhalb einer Klassendefinition initialisiert und damit für die Festlegung der Größe eines gewöhnlichen Arrays in der Klassendefinition verwendet werden. 2006 Pearson Education, Inc. All rights reserved. 1 // Fig. 7.16: GradeBook.h 2 // Definition of class GradeBook that uses an array to store test grades. 3 // Member functions are defined in GradeBook.cpp Outline 45 4 5 #include <string> 6 #include <array> GradeBook.h 8 // GradeBook class definition 9 class GradeBook (1 von 1) 7 10 { 11 public: Anzahl der betrachteten Studenten 12 // constant -- number of students who took the test 13 static const size_t students = 10; // note public data 14 15 // constructor initializes course name and array of grades 16 GradeBook( const std::string &, const std::array< int, students > & ); 17 18 void setCourseName( const std::string & ); // set the course name 19 std::string getCourseName() const; // retrieve the course name 20 std::string message() const; // return a welcome message 21 std::string processGradesResults() const; // perform operations on grade data 22 int getMinimum() const; // find the minimum grade for the test 23 int getMaximum() const; // find the maximum grade for the test 24 double getAverage() const; // determine the average grade for the test 25 std::string gradesContents() const; // contents of grades array as a string 26 std::string barChart() const; // return bar chart of grade distribution 27 private: 28 std::string courseName; // course name for this grade book 29 std::array< int, students > grades; // array of student grades 30 }; // end class GradeBook 2006 Pearson Education, Inc. All rights reserved. 1 // Fig. 7.17: GradeBook.cpp 2 // Member-function definitions for class GradeBook that 3 // uses an array to store test grades. Outline 46 4 5 #include <sstream> 6 #include <iomanip> 7 using namespace std; 8 9 #include "GradeBook.h" // GradeBook definition GradeBook.cpp (1 von 5) 10 11 // constructor initializes courseName and grades array 12 GradeBook::GradeBook( const string& name, 13 const array< int, students >& gradesArray ) 14 : courseName( name ), grades( gradesArray ) 15 { 16 } // end GradeBook constructor 17 18 // function to set the course name 19 void GradeBook::setCourseName( const string& name ) 20 { 21 courseName = name; // store the course name 22 } // end function setCourseName 23 24 // function to retrieve the course name 25 string GradeBook::getCourseName() const 26 { 27 return courseName; 28 } // end function getCourseName 2006 Pearson Education, Inc. All rights reserved. 32 33 // return a welcome message to the GradeBook user 34 string GradeBook::message() const Outline 47 35 { 36 return "Welcome to the grade book for\n" + getCourseName() + "!\n\n"; 37 } // end function message 38 39 // perform various operations on the data 40 string GradeBook::processGradesResults() const GradeBook.cpp (2 von 5) 41 { 42 stringstream resultStream; // write result as text in here 43 44 resultStream << gradesContents(); // write grades array as text 45 46 // call function getAverage to calculate the average grade 47 resultStream << "\nClass average is " << setprecision( 2 ) << fixed 48 49 << getAverage() << endl; 50 // call functions getMinimum and getMaximum 51 resultStream << "Lowest grade is " << getMinimum() 52 << "\nHighest grade is "<< getMaximum() << endl; 53 54 // call function barChart to write grade distribution chart as text 55 resultStream << barChart(); 56 57 return resultStream.str(); // return result as a string 58 } // end function processGradesresults 59 2006 Pearson Education, Inc. All rights reserved. 60 // find minimum grade Outline 61 int GradeBook::getMinimum() const 62 { 63 int lowGrade = 100; // assume lowest grade is 100 64 // loop through grades array 65 for( int grade : grades ) { Schleife durch grades, um schlechteste Note zu finden GradeBook.cpp 66 // if current grade lower than lowGrade, assign it to lowGrade 67 if( grade < lowGrade ) 68 48 (3 von 5) lowGrade = grade; // new lowest grade 69 } // end for 70 return lowGrade; // return lowest grade 71 } // end function getMinimum 72 73 // find maximum grade 74 int GradeBook::getMaximum() const 75 { 76 int highGrade = 0; // assume highest grade is 0 77 // loop through grades array 78 for( int grade : grades ) { Schleife durch grades, um beste Note zu finden 79 // if current grade higher than highGrade, assign it to highGrade 80 if( grade > highGrade ) 81 highGrade = grade; // new highest grade 82 } // end for 83 return highGrade; // return highest grade 84 } // end function getMaximum 2006 Pearson Education, Inc. All rights reserved. 85 Outline 86 // determine average grade for test 87 double GradeBook::getAverage() const 49 88 { 89 int total = 0; // initialize total 90 91 // sum grades in array 92 for( int grade : grades ) { 93 Schleife durch grades, um Noten aller Studenten zu summieren (4 von 5) total += grade; 94 } 95 // return average of grades 96 return static_cast< double >( total ) / students; 97 } // end function getAverage GradeBook.cpp Durchschnittsnote: Teilen der Summe durch die Anzahl der Studenten 98 99 // return the contents of the grades array as a string 100 string GradeBook::gradesContents() const 101 { 102 stringstream gradesStream; // write grades as text in here 103 104 gradesStream << "The grades are:\n\n"; 105 // write each student's grade 106 for( size_t student = 0; student < students; ++student ) { 107 gradesStream << "Student " << setw( 2 ) << student + 1 << ": " 108 << setw( 3 ) << grades[ student ] << endl; 109 } 110 return gradesStream.str(); // return grades as a string 111 } // end function gradesContent 112 2006 Pearson Education, Inc. All rights reserved. 113 // output bar chart displaying grade distribution Outline 114 string GradeBook::barChart() const 115 { 116 50 stringstream chartStream; // write bar chart as text in here 117 118 chartStream << "\nGrade distribution:" << endl; 119 // stores frequency of grades in each range of 10 grades 120 const size_t frequencySize = 11; 121 array< unsigned int, frequencySize > frequency = { 0 }; 122 // for each grade, increment the appropriate frequency 123 124 for( int grade : grades ) { ++frequency[ grade / 10 ]; 125 } 126 // for each grade frequency, write bar in chart 127 for( size_t count = 0; count < frequencySize; ++count ) { 128 // write bar labels ("0-9:", ..., "90-99:", "100:" ) 129 if( 0 == count ) 130 chartStream << " 131 else if( 10 == count ) 132 chartStream << " 133 GradeBook.cpp (5 von 5) Schleife durch grades, um Häufigkeit zu berechnen 0-9: "; 100: "; else 134 chartStream << count * 10 << "-" << ( count * 10 ) + 9 << ": "; 135 // write bar of asterisks 136 for( unsigned int stars = 0; stars < frequency[ count ]; ++stars ) { 137 chartStream << '*'; 138 } 139 chartStream << endl; // start a new line of text 140 } // end outer for 141 return chartStream.str(); // return bar chart as a string Histogramm aus Sternchen ausgeben 142 } // end function barChart 2006 Pearson Education, Inc. All rights reserved. 1 // Fig. 7.18: fig07_18.cpp 2 // Creates GradeBook object using an array of grades. 3 #include <iostream> 4 #include <array> 5 using namespace std; fig07_18.cpp 6 7 #include "GradeBook.h" // GradeBook definition 8 9 int main() 10 { (1 von 2) Verwendung des static Datenelements students der Klasse GradeBook 11 // array of student grades 12 const array< int, GradeBook::students > grades = 13 Outline 51 { 87, 68, 94, 100, 83, 78, 85, 91, 76, 87 }; 14 15 16 GradeBook myGradeBook( "CS101 Introduction to C++ Programming", grades ); 17 cout << myGradeBook.message(); 18 cout << myGradeBook.processGradesResults(); 19 } // end main Übergabe von grades an GradeBook Konstruktor 2006 Pearson Education, Inc. All rights reserved. Welcome to the grade book for CS101 Introduction to C++ Programming! Outline 52 The grades are: Student 1: 87 Student 2: 68 Student 3: 94 Student 4: 100 Student 5: 83 Student 6: 78 Student 7: 85 Student 8: 91 Student 9: 76 Student 10: 87 fig07_18.cpp (2 von 2) Class average is 84.90 Lowest grade is 68 Highest grade is 100 Grade distribution: 0-9: 10-19: 20-29: 30-39: 40-49: 50-59: 60-69: * 70-79: ** 80-89: **** 90-99: ** 100: * 2006 Pearson Education, Inc. All rights reserved. 7.7 Einführung in die C++ STL Klasse vector 53 • Das Klassentemplate vector – Im Gegensatz zum array kann die Größe während der Programmausführung verändert werden. – Bei Bedarf automatisches Wachsen und Schrumpfen: • push_back: Ein Element wird am Ende eines vectors eingefügt. Falls die Kapazität des vectors für ein weiteres Element nicht ausreicht, wird er automatisch vergrößert. • pop_back: Ein Element wird am Ende eines vectors entfernt. • back: Das letzte Element eines vectors wird zurückgegeben (ohne es zu entfernen): • Durch den größeren Verwaltungsaufwand ist ein vector langsamer und hat mehr Speicherverbrauch als ein array. 2006 Pearson Education, Inc. All rights reserved. 7.7 Einführung in die C++ STL Klasse vector 54 • vector (und array) Elementfunktion at – Gestattet den Zugriff auf einzelne Elemente – Führt Bereichsüberprüfung durch • Wirft eine Ausnahme (‘throws an exception’) in Form eines Objekts einer passenden Fehlerklasse (out_of_range), wenn der angegebene Index ungültig ist. • Wird der Aufruf von at in einen try-Block eingeschlossen, kann diese Ausnahme in einem direkt folgenden catch-Block aufgefangen und behandelt werden. – Der (auch mögliche) Zugriff mit eckigen Klammern [ ] führt aus Gründen der Performanz keine Bereichsüberprüfung durch! 2006 Pearson Education, Inc. All rights reserved. 1 // Fig. 7.19: fig07_19.cpp 2 // Demonstrating C++ Standard Library class template vector. 3 #include <iostream> 4 #include <iomanip> 5 #include <vector> 6 #include <array> 7 using namespace std; Verwendung von const, damit outputVector einen übergebenen vector nicht modifizieren kann 8 9 void outputVector( const vector< int > & ); // display the vector Outline 55 fig07_19.cpp (1 von 4) 10 11 int main() 12 { Diese vector-Objekte speichern ints. 13 vector< int > v1 = { 1, 2, 3, 4, 5, 6, 7 }; 14 vector< int > v2 = { 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 }; 15 16 // print v1 size and contents 17 cout << "Size of vector v1 is " << v1.size() 18 19 << "\nvector after initialization:" << endl; outputVector( v1 ); Funktion size gibt Anzahl der Elemente im vector zurück. 20 21 // print v2 size and contents 22 cout << "\nSize of vector v2 is " << v2.size() 23 24 << "\nvector after initialization:" << endl; outputVector( v2 ); 25 Funktion push_back fügt ein Element am Ende des vectors ein. 26 // add two elements at back of v1 27 v1.push_back( 8 ); 28 v1.push_back( 9 ); 29 cout << "\n8 and 9 added at back of v1." << endl; 2006 Pearson Education, Inc. All rights reserved. 29 30 // show and remove last element of v2 31 cout << "Last element of v2 will be removed: " << v2.back() << endl; 32 v2.pop_back(); 33 34 cout << "\nAfter modification, the vectors contain:\n" 35 << "v1 ( size = " << v1.size() << " ):" << endl; 36 outputVector( v1 ); 37 cout << "v2 ( size = " << v2.size() << " ):" << endl; 38 outputVector( v2 ); Outline 56 back gibt das letzte Element eines vectors zurück und fig07_19.cpp pop_back entfernt es. (2 von 4) 39 40 // use inequality (!=) operator with vector objects 41 cout << "\nEvaluating: v1 != v2" << endl; 42 if( v1 != v2 ) { 43 44 cout << "v1 and v2 are not equal" << endl; } 45 46 // use square brackets to create rvalue 47 cout << "\nv1[5] is " << v1[ 5 ]; Einen Wert des vectors ausgeben 48 49 // use square brackets to create lvalue 50 cout << "\n\nAssigning 1000 to v1[5]" << endl; 51 v1[ 5 ] = 1000; 52 cout << "v1:" << endl; 53 outputVector( v1 ); Einen Wert des vectors ändern 2006 Pearson Education, Inc. All rights reserved. 54 55 // attempttry to use subscript und out-of-range catch-Block für eine 56 try { geregelte Ausnahmebehandlung 57 cout << "\nAttempt to display v1.at( 9 )" << endl; 58 cout << v1.at( 9 ) << endl; // ERROR: out of range 59 } 60 catch( out_of_range& ex ) { 61 62 Funktion at führt Bereichsüberprüfung durch fig07_19.cpp cerr << "An exception occurred: " << ex.what() << endl; } 63 (3 von 4)hier einfach Behandlung der Ausnahme: Aufruf der Elementfunktion what 64 65 cout << "\nAfter exception-handling program can continue:" << endl; 66 array< int, 7 > intArray = { 1, 2, 3, 4, 5, 6, 7 }; 67 try { 68 cout << "\nAttempt to display intArray.at( 15 )" << endl; 69 cout << intArray.at( 15 ) << endl; // ERROR: out of range 70 } 71 catch( out_of_range& ex ) { 72 73 Outline 57 cerr << "An exception occurred: " << ex.what() << endl; } 74 } // end main 75 76 // output vector contents 77 void outputVector( const vector< int > & items ) 78 { 79 for( int item : items ) { 80 cout << item << " "; 81 } 82 cout << endl; 83 } 2006 Pearson Education, Inc. All rights reserved. Size of vector v1 is 7 vector after initialization: 1 2 3 4 5 6 7 Outline 58 Size of vector v2 is 10 vector after initialization: 10 11 12 13 14 15 16 17 18 19 8 and 9 added at back of v1. Last element of v2 will be removed: 19 After modification, the vectors contain: v1 ( size = 9 ): 1 2 3 4 5 6 7 8 9 v2 ( size = 9 ): 10 11 12 13 14 15 16 17 18 fig07_19.cpp (4 von 4) Evaluating: v1 != v2 v1 and v2 are not equal v1[5] is 6 Assigning 1000 to v1[5] v1: 1 2 3 4 5 1000 7 8 9 Attempt to display v1.at( 9 ) An exception occurred: invalid vector<T> subscript After exception-handling program can continue: Attempt to display intArray.at( 15 ) An exception occurred: invalid array<T, N> subscript 2006 Pearson Education, Inc. All rights reserved. 59 7.8 Suchen und Sortieren • Übersicht: Suchen von Daten – Es soll bestimmt werden, ob ein bestimmter Wert, der ‘Suchschlüssel’ (search key), in den Daten vorkommt. • Wenn ja: an welcher Stelle? – Algorithmen • Lineare Suche – Einfach, relativ langsam • Binäre Suche – Schneller, aber komplizierter 2006 Pearson Education, Inc. All rights reserved. 60 7.8 Suchen und Sortieren • Übersicht: Sortieren von Daten – Die Daten sollen in eine bestimmte Reihenfolge gebracht werden • Oft aufsteigend oder absteigend • Grundlage ist eine ‘Ordnungsrelation’ für die Daten – Einfache Algorithmen • Direktes Einfügen (Insertion-Sort) • Direktes Vertauschen (Bubble-Sort) • Direkte Auswahl (Selection-Sort) – Effizientere, aber aufwändigere Algorithmen: • Merge-Sort (Einfügen) • Quick-Sort (Vertauschen) • Heapsort (Auswahl) 2006 Pearson Education, Inc. All rights reserved. 61 7.8 Suchen und Sortieren • Übersicht: Groß-O-Schreibweise (Big O notation) – Kurzschreibweise für eine Abschätzung der Laufzeit (im ungünstigsten Fall) für einen Algorithmus • Ist Bestandteil der Komplexitätstheorie • Ergebnisse für wichtigste Algorithmen werden hier angegeben 2006 Pearson Education, Inc. All rights reserved. 62 7.8 Suchen und Sortieren • Suchalgorithmen – Finden des Elements, das zu einem gegebenen Suchschlüssel passt, in einer gegebenen Datenmenge • Falls ein solches Element existiert – Wesentliche Differenz zwischen unterschiedlichen Suchalgorithmen • Aufwand, der für die Durchführung der Suche benötigt wird – Ist insbesondere von der Anzahl der Datenelemente abhängig – Kann in der Groß-O-Schreibweise angegeben werden 2006 Pearson Education, Inc. All rights reserved. 63 7.8.1 Lineare Suche • Lineare Suche – Vergleicht jedes Element eines Arrays mit dem Suchschlüssel – Bei zufällig angeordneten Daten ist es genauso wahrscheinlich, dass der Wert gleich beim ersten Element gefunden wird, wie beim letzten. • Das Programm muss den Suchschlüssel durchschnittlich mit der Hälfte der Elemente des Arrays vergleichen. – Um festzustellen, dass ein Wert nicht in dem Array vorkommt, muss das Programm den Suchschlüssel mit jedem Element des Arrays vergleichen. – Ist sinnvoll für kleine oder unsortierte Arrays 2006 Pearson Education, Inc. All rights reserved. 1 // Fig. 7.20: fig07_20.cpp 2 // Linear search of an array. 3 #include <iostream> 4 #include <array> 5 using namespace std; 6 Outline 64 fig07_20.cpp 7 // compare key to every element of array until location is 8 // found or until end of array is reached; return location of 9 // element if key is found or -1 if key is not found (1 von 2) 10 template < typename T, size_t size > 11 int linearSearch( const array< T, size >& items, const T& key ) 12 { 13 for( size_t i = 0; i < items.size(); ++i ) 14 if( items[ i ] == key ) // if found, 15 return i; // return location of key 16 17 return -1; // key not found 18 } // end function linearSearch 2006 Pearson Education, Inc. All rights reserved. 19 Outline 20 int main() 21 { 22 const size_t arraySize = 100; // size of array 23 array< int, arraySize > a; // create array 24 int searchKey; // value to locate in array fig07_20.cpp for( size_t i = 0; i < arraySize; ++i ) (2 von 2) 25 26 27 a[ i ] = 2 * i; // create some data 65 28 29 cout << "Enter integer search key: "; 30 cin >> searchKey; 31 32 // attempt to locate searchKey in array a 33 int element = linearSearch( a, searchKey ); 34 35 // display results 36 if( element != -1 ) 37 38 39 Funktion gibt den Index des Suchschlüssels zurück; -1 falls er nicht gefunden wird cout << "Found value in element " << element << endl; else cout << "Value not found" << endl; 40 } // end main Enter integer search key: 36 Found value in element 18 Enter integer search key: 37 Value not found 2006 Pearson Education, Inc. All rights reserved. 66 7.8.1 Lineare Suche • Groß-O-Schreibweise – Misst das Anwachsen der Laufzeit eines Algorithmus im Verhältnis zur Anzahl der verarbeiteten Werte • Betont die dominanten Anteile • Vernachlässigt die Anteile, die unwichtig werden, wenn n stark anwächst • Vernachlässigt konstante Anteile 2006 Pearson Education, Inc. All rights reserved. 67 7.8.1 Lineare Suche • Groß-O-Schreibweise – Konstante Laufzeit • Die Anzahl der Operationen, die ein Algorithmus durchführt, ist konstant. – Erhöht sich nicht, wenn die Anzahl der Werte anwächst • Wird in Groß-O-Schreibweise als O(1) dargestellt – Gesprochen “von der Ordnung 1” oder “Ordnung 1” • Beispiel – Überprüfen, ob das erste Element eines n-Arrays gleich dem zweiten Element ist • Es wird immer genau ein Vergleich benötigt, egal wie groß das Array ist. 2006 Pearson Education, Inc. All rights reserved. 68 7.8.1 Lineare Suche • Groß-O-Schreibweise – Lineare Laufzeit • Die Anzahl der Operationen, die ein Algorithmus durchführt, wächst linear mit der Anzahl der Werte. • Wird in Groß-O-Schreibweise als O(n) dargestellt – Gesprochen “von der Ordnung n” oder “Ordnung n” • Beispiel – Überprüfen, ob das erste Element eines n-Arrays mit irgendeinem der anderen Elemente gleich ist. • Benötigt n - 1 Vergleiche • n Anteil dominiert, -1 wird ignoriert 2006 Pearson Education, Inc. All rights reserved. 69 7.8.1 Lineare Suche • Groß-O-Schreibweise – Quadratische Laufzeit • Die Anzahl der Operationen, die ein Algorithmus durchführt, wächst quadratisch mit der Anzahl der Werte. • Wird in Groß-O-Schreibweise als O(n2) dargestellt – Gesprochen “von der Ordnung n2” oder “Ordnung n2” • Beispiel – Überprüfen, ob irgendein Element eines n-Arrays mit irgendeinem der anderen Elemente gleich ist. • Benötigt n2/2 – n/2 Vergleiche • n2 Anteil dominiert, die Konstante 1/2 wird ignoriert, -n/2 wird ignoriert 2006 Pearson Education, Inc. All rights reserved. 70 7.8.1 Lineare Suche • Effizienz der linearen Suche – Die lineare Suche läuft in O(n) Zeit • Ungünstigster Fall: Jedes Element muss überprüft werden. • Falls die Größe des Arrays verdoppelt wird, verdoppelt sich auch die Anzahl der Vergleiche. 2006 Pearson Education, Inc. All rights reserved. 71 Tipp zur Performanz Oft ist die Performanz von einfachen Algorithmen schlecht. Ihr Wert besteht darin, dass sie leicht zu schreiben, zu testen und zu debuggen sind. Oft werden komplexere Algorithmen benötigt, um die optimale Performanz zu erreichen. 2006 Pearson Education, Inc. All rights reserved. 72 7.8.2 Binäre Suche • Algorithmus für die binäre Suche – Erfordert, dass der vector / das array zuerst sortiert wird • Dies kann z.B. durch die Funktion sort der Standardbibliothek erledigt werden. – Sortiert Elemente in aufsteigender Ordnung – Erste Iteration (setzt aufsteigend sortierte Ordnung voraus) • Das mittlere Element des vectors wird überprüft. – Falls es mit dem Suchschlüssel übereinstimmt, endet der Algorithmus. – Falls es größer als der Suchschlüssel ist, wird die Suche nur noch in der ersten Hälfte des vectors fortgesetzt. – Falls es kleiner als der Suchschlüssel ist, wird die Suche nur noch in der zweiten Hälfte des vectors fortgesetzt. 2006 Pearson Education, Inc. All rights reserved. 73 7.8.2 Binäre Suche • Algorithmus für die binäre Suche – Darauf folgende Iterationen • Das mittlere Element des übrig gebliebenen Teilvectors wird überprüft. – Falls es mit dem Suchschlüssel übereinstimmt, endet der Algorithmus. – Falls nicht, wird die Suche in der passenden Hälfte des Teilvectors fortgesetzt. – Der Algorithmus endet, wenn • ein Element, das mit dem Suchschlüssel übereinstimmt, gefunden wird oder • der aktuelle Teilvector die Größe 0 hat. – Daraus folgt, dass der Suchschlüssel nicht im vector enthalten ist. 2006 Pearson Education, Inc. All rights reserved. 1 // Fig 7.23: Fig07_23.cpp 2 // Binary search in a vector of random integers. Outline 3 4 #include <iostream> 5 #include <vector> 6 #include <algorithm> // prototype for std::sort function 6 #include <random> 7 #include <ctime> 8 using namespace std; 74 fig07_23.cpp (1 von 5) 9 10 // display vector elements from index low through index high 11 template < typename T > 12 void displayElements( const vector< T >& data, size_t low, size_t high ) 13 { 14 15 16 17 18 for( size_t i = 0; i < low; ++i ) // display spaces for alignment cout << " "; for( size_t i = low; i <= high; ++i ) // display elements left in vector cout << data[ i ] << " "; cout << endl; 19 } // end function displayElements 20 2006 Pearson Education, Inc. All rights reserved. 21 // perform a binary search on the data 22 template < typename T > 23 int binarySearch( const vector< T >& data, const T& key ) 24 { Outline Initialisierung der Indices low, high und middle des vectors 25 int low = 0; // low index of elements to search 26 int high = data.size() - 1; // high index of elements to search 27 int middle = ( low + high + 1 ) / 2; // middle element 28 int location = -1; // key's index; -1 if not found 29 30 do // loop to search for element 31 { (2 von 5) // display remaining elements of vector to be searched 33 displayElements( data, low, high ); 34 // output spaces for alignment 35 for( size_t i = 0; i < middle; ++i ) 37 cout << " "; cout << " * " << endl; // indicate current middle Fortsetzung der Suche in der passenden Hälfte des vectors 38 39 40 41 42 43 44 fig07_23.cpp Initialisierung von location mit -1, um anzuzeigen, dass der Suchschlüssel (noch) nicht gefunden wurde 32 36 75 if( key < data[ middle ] ) high = middle - 1; // eliminate the higher half else if( data[ middle ] < key ) low = middle + 1; // eliminate the lower half else Test, ob das Element an der Position middle gleich key ist location = middle; // location is the current middle 45 46 47 middle = ( low + high + 1 ) / 2; // recalculate the middle } while( ( low <= high ) && ( location == -1 ) ); 48 49 return location; // return location of key 50 } // end function binarySearch Schleife läuft, bis der Teilvector die Größe Null hat oder der Suchschlüssel gefunden ist 2006 Pearson Education, Inc. All rights reserved. 51 Outline 52 int main() 53 { 54 // use the default random-number generation engine to produce 55 // uniformly distributed pseudorandom int values from 10 to 99 56 default_random_engine engine( static_cast< unsigned >( time( nullptr ) ) ); 57 uniform_int_distribution< unsigned int > randomInt( 10, 99 ); 58 59 const size_t size = 15; // vector size 60 vector< int > data; // empty vector of ints 61 62 // fill vector with random ints in range 10-99 for( size_t i = 0; i < size; ++i ) 63 76 fig07_23.cpp (3 von 5) data.push_back( randomInt( engine ) ); // 10-99 64 std::sort( data.begin(), data.end() ); // sort the data 65 displayElements( data, 0, size - 1 ); // output the data 66 67 // get input from user 68 cout << "\n\nPlease enter an integer value (-1 to quit): "; 69 int searchKey; // value to locate 70 cin >> searchKey; // read an int from user 71 cout << endl; 2006 Pearson Education, Inc. All rights reserved. 72 73 // repeatedly input an integer; -1 terminates the program 74 while( searchKey != -1 ) { 75 // use binary search to try to find integer 76 int position = binarySearch( data, searchKey ); Outline Durchführung der binären Suche 77 78 // return value of -1 indicates integer was not found 79 if( position == -1 ) 80 81 82 77 fig07_23.cpp (4 von 5) cout << "The integer " << searchKey << " was not found.\n"; else cout << "The integer " << searchKey 83 << " was found in position " << position << ".\n"; 84 85 // get input from user 86 cout << "\n\nPlease enter an integer value (-1 to quit): "; 87 cin >> searchKey; // read an int from user 88 cout << endl; 89 } // end while 90 } // end main 2006 Pearson Education, Inc. All rights reserved. 26 31 33 38 47 49 51 67 73 74 82 89 90 91 95 Outline 78 Please enter an integer value (-1 to quit): 38 26 31 33 38 47 49 51 67 73 74 82 89 90 91 95 * 26 31 33 38 47 49 51 * The integer 38 was found in position 3. fig07_23.cpp (5 von 5) Please enter an integer value (-1 to quit): 91 26 31 33 38 47 49 51 67 73 74 82 89 90 91 95 * 73 74 82 89 90 91 95 * 90 91 95 * The integer 91 was found in position 13. Please enter an integer value (-1 to quit): 25 26 31 33 38 47 49 51 67 73 74 82 89 90 91 95 * 26 31 33 38 47 49 51 * 26 31 33 * 26 * The integer 25 was not found. Please enter an integer value (-1 to quit): -1 2006 Pearson Education, Inc. All rights reserved. 79 7.8.2 Binäre Suche • Effizienz der binären Suche – Logarithmische Laufzeit • Die Anzahl der Operationen, die der Algorithmus durchführt, wächst logarithmisch mit der Anzahl der Werte. • Wird in Groß-O-Schreibweise als O(log n) dargestellt – Gesprochen “von der Ordnung log n” oder “Ordnung log n” • Beispiel – Einen sortierten vector mit 1000 Elementen binär zu durchsuchen benötigt höchstens 10 Vergleiche (10 ist die kleinste ganze Zahl größer als 9.97 = log2 1000). • Wiederholtes ganzzahliges Teilen von 1000 durch 2 ergibt 0 nach 10 Iterationen. 2006 Pearson Education, Inc. All rights reserved. 7.8.3 Sortieren durch direktes Einfügen (Insertion-Sort) 80 • Sortieralgorithmen – Bringen Daten in eine bestimmte Ordnung • Beispielsweise ansteigend oder abfallend – Eine der wichtigsten Anwendungen in der Informatik – Das Endresultat, ein sortiertes array / vector, ist unabhängig von dem zum Sortieren eingesetzten Algorithmus. • Die Wahl des Algorithmus beeinflusst allerdings die zum Sortieren benötigte Laufzeit sowie den Speicherverbrauch. 2006 Pearson Education, Inc. All rights reserved. 81 7.8.3 Insertion-Sort • Insertion-Sort – Einfach, für große Arrays nicht sehr effizient – Die erste Iteration nimmt das zweite Element. • Falls es kleiner als das erste Element ist, wird es mit dem ersten Element vertauscht. – Die zweite Iteration betrachtet das dritte Element. • Es wird an die richtige Stelle des bereits sortierten Teilarrays aus den ersten beiden Elementen gesetzt. Dadurch ist der sortierte Bereich um ein Element größer. – … – In der i-ten Iteration dieses Algorithmus, sind die ersten i Elemente des ursprünglichen Arrays sortiert. 2006 Pearson Education, Inc. All rights reserved. 82 7.8.3 Insertion-Sort • Beispiel • Unsortiertes Array 34 56 04 10 77 51 93 30 05 52 • Erster Schritt (Vertauschen, falls erforderlich) 34 56 • Einsetzen des dritten Elements an der passenden Stelle 34 56 04 34 56 04 34 56 04 04 34 56 • Einsetzen des vierten Elements an der passenden Stelle 04 34 56 10 04 34 56 10 04 34 56 10 04 10 34 56 und so weiter... 2006 Pearson Education, Inc. All rights reserved. 1 // Fig. 7.24: fig07_24.cpp 2 // Sorting an array into ascending order with insertion sort. 3 #include <iostream> 4 #include <iomanip> 5 #include <array> 6 using namespace std; fig07_24.cpp 8 // sort an array into ascending order 9 template < typename T > (1 von 2) Outline 7 83 10 void insertionSort( T & items ) 11 { 12 // loop over the elements of the array 13 for( size_t next = 1; next < items.size(); ++next ) { 14 auto insert = items[ next ]; // save value of next item to insert 15 size_t moveIndex = next; // initialize location to place element 16 17 // search for the location in which to put the current element 18 while( ( moveIndex > 0 ) && ( items[ moveIndex - 1 ] > insert ) ) { 19 // shift element one slot to the right 20 items[ moveIndex ] = items[ moveIndex - 1 ]; 21 --moveIndex; 22 } // end while Die Position finden, wohin das gerade betrachtete Element gehört 23 24 25 items[ moveIndex ] = insert; // place insert item back into array } // end for 26 } // end function insertionSort Das Element an die richtige Position setzen 2006 Pearson Education, Inc. All rights reserved. 27 Outline 28 int main() 29 { 30 const size_t arraySize = 10; // size of array a 31 array< int, arraySize > a = { 34, 56, 4, 10, 77, 51, 93, 30, 5, 52 }; 32 fig07_24.cpp 33 cout << "Unsorted array:\n"; 34 // output original array 35 for( const auto& element : a ) { 36 cout << setw( 4 ) << element; 37 84 (2 von 2) } 38 39 insertionSort( a ); // sort the array 40 41 cout << "\nSorted array:\n"; 42 // output sorted array 43 for( const auto& element : a ) { 44 cout << setw( 4 ) << element; 45 } 46 cout << endl; 47 } // end main Unsorted array: 34 56 4 10 Sorted array: 4 5 10 30 77 51 93 30 5 52 34 51 52 56 77 93 2006 Pearson Education, Inc. All rights reserved. 85 7.8.3 Insertion-Sort • Typinferenz mit auto – Wird eine Variable bei ihrer Definition bereits initialisiert, kann aus dem Typ des Initialisierungswertes automatisch der Typ der Variablen abgeleitet werden: auto x = 0; // same as: int x = 0; auto x = 0.0; // same as: double x = 0.0; – Entsprechend ist die Verwendung von auto beispielsweise bei der Zuweisung eines Arrayelements an eine neu zu definierende Variable oder beim bereichsbasierten for möglich. 2006 Pearson Education, Inc. All rights reserved. 86 7.8.3 Insertion-Sort • Effizienz von Insertion-Sort – In der i-ten Iteration • wird das (i + 1)te Element in die korrekte Position in bezug auf die ersten i Elemente gesetzt. – Nach der i-ten Iteration • sind die ersten i Elemente sortiert. – Die äußere Schleife wird (n – 1) mal durchlaufen. • Im ungünstigsten Fall wird die innere Schleife n mal durchlaufen. – Damit ergibt sich O(n2). – Für die Bestimmung des Groß-O-Wertes bedeuten verschachtelte Wiederholungsanweisungen eine Multiplikation der jeweiligen Anzahl der Iterationen. 2006 Pearson Education, Inc. All rights reserved. 7.8.4 Merge-Sort (rekursive Implementierung) 87 • Merge-Sort – Ein vector wird sortiert, indem • er in zwei gleich große Teilvectoren zerlegt wird. – Falls die vectorgröße ungerade ist, wird ein Teilvector ein Element größer als der andere. • Jeder Teilvector wird sortiert. • Beim Verschmelzen (merge) der Teilvectoren in einen großen, sortierten vector – werden wiederholt die kleinsten Elemente in den beiden Teilvectoren verglichen. – Das kleinere Element wird entfernt und in den großen, kombinierten vector geschrieben. 2006 Pearson Education, Inc. All rights reserved. 88 7.8.4 Merge-Sort • Merge-Sort – Rekursive Implementierung • Basisfall – Ein vector mit einem Element ist schon sortiert. • Rekursionsschritt – Der vector (mit ≥ 2 Elementen) wird in zwei gleich große Hälften aufgeteilt. • Falls die vectorgröße ungerade ist, wird ein Teilvector ein Element größer als der andere. – Rekursives Sortieren jedes Teilvectors – Verschmelzen der Teilvectoren in einen großen, sortierten vector. 2006 Pearson Education, Inc. All rights reserved. 89 7.8.4 Merge-Sort • Merge-Sort – Verschmelzung an einem Beispiel • Kleinere, sortierte Teilvectoren – A: 4 10 34 56 77 – B: 5 30 51 52 93 • Vergleich des kleinsten Elements in A mit dem kleinsten Element in B – 4 (A) ist kleiner als 5 (B) • 4 wird das erste Element im verschmolzenen vector – 5 (B) ist kleiner als 10 (A) • 5 wird das zweite Element im verschmolzenen vector – 10 (A) ist kleiner als 30 (B) • 10 wird das dritte Element im verschmolzenen vector – usw. 2006 Pearson Education, Inc. All rights reserved. 1 // Fig 7.27: Fig07_27.cpp 2 // Sorting a vector into ascending order with merge sort. 3 #include <iostream> 4 #include <vector> 5 #include <random> 6 #include <ctime> 7 using namespace std; 8 9 Outline Formatierte Ausgabe der (Teil-)vectoren zur Veranschaulichung des Algorithmus 90 fig07_27.cpp (1 von 7) // display vector elements from index low through index high 10 template < typename T > 11 void displayElements( const vector< T >& data, size_t low, size_t high ) 12 { 13 for( size_t i = 0; i < low; ++i ) { // display spaces for alignment 14 cout << " "; 15 } 16 for( size_t i = low; i <= high; ++i ) { // display elements left in vector 17 cout << " " << data[ i ]; 18 } 19 cout << endl; 20 } // end function displayElements 21 22 // function that starts a merge sort 23 template < typename T > 24 void mergeSort( vector< T >& data, size_t low, size_t high ) 25 { 26 vector< T > combined( data.size() ); // not-in-place working vector 27 mergeSortHelper( data, low, high, combined ); 28 } // end function mergeSort 29 2006 Pearson Education, Inc. All rights reserved. 30 Outline 31 // recursive function to sort (sub)vectors 32 template < typename T > 91 33 void mergeSortHelper( vector< T >& data, size_t low, size_t high, 34 vector< T >& combined ) 35 { 36 if( ( high - low ) >= 1 ) { // if not base case (vector with size 1) 37 size_t middle1 = ( low + high ) / 2; // calculate middle of vector 38 size_t middle2 = middle1 + 1; // calculate next element over fig07_27.cpp (2 von 7) 39 40 // output split step 41 cout << "split: 42 displayElements( data, low, high ); 43 cout << " 44 displayElements( data, low, middle1 ); 45 cout << " 46 displayElements( data, middle2, high ); 47 cout << endl; "; "; "; 48 49 // split vector in half; sort each half (recursive calls) 50 mergeSortHelper( data, low, middle1, combined ); // first half of vector 51 mergeSortHelper( data, middle2, high, combined ); // second half of vector 52 53 // merge two sorted vectors after split calls return 54 merge( data, low, middle1, middle2, high, combined ); 55 } // end if 56 } // end function mergeSortHelper Sortierung der (Teil-)vectoren Verschmelzen der beiden sortierten (Teil-)vectoren in einen größeren, sortierten (Teil-)vector 2006 Pearson Education, Inc. All rights reserved. 57 Outline 58 // merge two sorted subvectors into one sorted subvector 59 template < typename T > 92 60 void merge( vector< T >& data, size_t left, size_t middle1, 61 size_t middle2, size_t right, vector< T >& combined ) 62 { fig07_27.cpp 63 size_t leftIndex = left; // index into left subvector 64 size_t rightIndex = middle2; // index into right subvector 65 size_t combinedIndex = left; // index into not-in-place working vector (3 von 7) 66 67 // output two subvectors before merging 68 cout << "merge: 69 displayElements( data, left, middle1 ); 70 cout << " 71 displayElements( data, middle2, right ); "; "; Schleife, bis das Ende einer der Teilvectoren erreicht ist 72 73 // merge vectors until reaching end of either 74 while( leftIndex <= middle1 && rightIndex <= right ) { 75 // place smaller of two current elements into result 76 // and move to next space in vector 77 if( data[ leftIndex ] <= data[ rightIndex ] ) 78 79 80 81 combined[ combinedIndex++ ] = data[ leftIndex++ ]; else combined[ combinedIndex++ ] = data[ rightIndex++ ]; Test, welches Element am Anfang der vectoren kleiner ist Schreiben des kleineren Elements in den kombinierten vector } // end while 82 2006 Pearson Education, Inc. All rights reserved. 83 84 if( leftIndex == middle2 ) { // if at end of left vector 85 while( rightIndex <= right ) // copy in rest of right vector 86 combined[ combinedIndex++ ] = data[ rightIndex++ ]; 87 } // end if 88 else { // at end of right vector 89 combined[ combinedIndex++ ] = data[ leftIndex++ ]; } // end else 92 93 // copy values back into original vector 94 for( size_t i = left; i <= right; ++i ) { 95 96 data[ i ] = combined[ i ]; } 97 98 // output merged vector 99 cout << " 100 displayElements( data, left, right ); 101 cout << endl; 93 fig07_27.cpp while( leftIndex <= middle1 ) // copy in rest of left vector 90 91 Füllen des kombinierten Outline vectors mit den restlichen Elementen des rechten vectors oder… … mit den (4 restlichen von 7) Elementen des linken vectors Kopieren des kombinierten vectors in den Originalvector "; 102} // end function merge 2006 Pearson Education, Inc. All rights reserved. Outline 103 int main() 104 { 105 // use the default random-number generation engine to produce 106 // uniformly distributed pseudorandom int values from 10 to 99 107 default_random_engine engine( static_cast< unsigned >( time( nullptr ) ) ); 108 uniform_int_distribution< unsigned int > randomInt( 10, 99 ); 109 110 const size_t size = 10; // vector size 111 vector< int > data; // empty vector of ints 112 for( int i = 0; i < size; ++i ) { 113 94 fig07_27.cpp (5 von 7) data.push_back( randomInt( engine ) ); // 10-99 114 } 115 cout << "Unsorted vector:" << endl; 116 displayElements( data, 0, size - 1 ); // print unsorted vector 117 cout << endl; 118 119 mergeSort( data, 0, size - 1 ); // sort vector 120 121 122 cout << "Sorted vector:" << endl; displayElements( data, 0, size - 1 ); // print sorted vector 123 } // end main 2006 Pearson Education, Inc. All rights reserved. Unsorted vector: 77 63 69 41 39 75 58 12 16 15 split: 77 63 69 41 39 75 58 12 16 15 77 63 69 41 39 75 58 12 16 15 split: 77 63 69 41 39 77 63 69 41 39 split: 77 63 69 77 63 69 split: 77 63 77 63 merge: 77 Outline 95 fig07_27.cpp (6 von 7) 63 63 77 merge: 63 77 69 63 69 77 split: 41 39 41 39 merge: 41 39 39 41 merge: 63 69 77 39 41 39 41 63 69 77 2006 Pearson Education, Inc. All rights reserved. split: 75 58 12 16 15 75 58 12 16 15 split: 75 58 12 75 58 12 split: 75 58 75 58 merge: 75 Outline 96 fig07_27.cpp (7 von 7) 58 58 75 merge: 58 75 12 12 58 75 split: 16 15 16 15 merge: 16 15 15 16 merge: 12 58 75 15 16 12 15 16 58 75 merge: 39 41 63 69 77 12 15 16 58 75 12 15 16 39 41 58 63 69 75 77 Sorted vector: 12 15 16 39 41 58 63 69 75 77 2006 Pearson Education, Inc. All rights reserved. 97 7.8.4 Merge-Sort • Effizienz von Merge-Sort – O(n log n) Laufzeit: • Das Halbieren der vectoren bedeutet log2 n Ebenen, um den Basisfall zu erreichen. – Verdopplung der vectorgröße erfordert eine weitere Ebene, vervierfachen zwei weitere Ebenen usw. • O(n) Vergleiche sind auf jeder Ebene erforderlich: – Aufruf von sortSubVector mit einem vector der Größe n führt zu • Zweimal sortSubVector mit Teilvectoren der Größe n/2 • merge mit n – 1 (Ordnung n) Vergleichen • Damit ergibt sich insgesamt O(n log n) 2006 Pearson Education, Inc. All rights reserved. 98 Algorithmus Komplexität Lineare Suche Binäre Suche Rekursive lineare Suche Rekursive binäre Suche O(n) O(log n) O(n) O(log n) Bubble-Sort Selection-Sort Insertion-Sort Merge-Sort O(n2) O(n2) O(n2) O(n log n) Quick-Sort Ungünstigster Fall: O(n2) Durchschnittlich: O(n log n) Fig. 7.28 | Such- und Sortieralgorithmen mit Komplexitätswerten. 2006 Pearson Education, Inc. All rights reserved. 99 n Genäherter Dezimalwert O(log n) O(n) O(n log n) O(n2) 210 1000 10 210 10 ·210 220 220 1,000,000 20 220 20 ·220 240 230 1,000,000,000 30 230 30 ·230 260 Fig. 7.29 | Zahlenwerte zu typischen Groß-O-Ausdrücken. 2006 Pearson Education, Inc. All rights reserved. 100 7.9 Mehrdimensionale arrays • Zweidimensionale Arrays – Matrix oder Tabelle – Werte, die in Zeilen und Spalten angeordnet sind – Elemente werden über zwei Indices a[ i ][ j ] angesprochen – Ein Array mit m Zeilen und n Spalten wird als m-mal-n Array bezeichnet. • Mehrdimensionale Arrays können mehr als zwei Dimensionen haben – Jede weitere Dimension führt zu einem zusätzlichen Index: a[ i ][ j ][ k ] usw. 2006 Pearson Education, Inc. All rights reserved. 101 Fig.7.30 | Zweidimensionales Array mit drei Zeilen (rows) und vier Spalten (columns). 2006 Pearson Education, Inc. All rights reserved. 102 Häufiger Programmierfehler Spricht man ein Element eines zweidimensionalen Arrays - wie a[ i ][ j ] - als a[ i, j ] an, so ist dies ein logischer Fehler. a[ i, j ] wird wie a[ j ] behandelt, weil C++ den Ausdruck i, j (der einen Kommaoperator enthält) einfach als j auswertet (den am weitesten rechts stehenden der kommaseparierten Ausdrücke). 2006 Pearson Education, Inc. All rights reserved. 103 7.9 Mehrdimensionale arrays • Deklaration und Initialisierung von zweidimensionalen arrays – Deklaration des zweidimensionalen Arrays b • array< array< int, 2 >, 2 { 1, 1 und 2 initialisieren b[ 0 ][ 3 und 4 initialisieren b[ 1 ][ > b = 2, 3, 4 }; 0 ] und b[ 0 ][ 1 ] 0 ] und b[ 1 ][ 1 ] • array< array< int, 2 >, 2 > b = { 1, 2, 3 } }; – Die Zeile 0 enthält die Werte 1 und 2 – Die Zeile 1 enthält die Werte 3 und 0 (implizit mit Null initialisiert). 2006 Pearson Education, Inc. All rights reserved. 1 // Fig. 7.31: fig07_31.cpp 2 // Initializing multidimensional arrays. 3 #include <iostream> 4 #include <array> 5 using namespace std; 6 Outline 104 fig07_31.cpp 7 const size_t rows = 8 const size_t columns = 9 void printArray( const array< array < int, columns >, rows > & ); 2; 3; (1 von 2) 10 11 int main() 12 { 13 array< array < int, columns >, rows > a1 = { 1, 2, 3, 4, 5, 6 }; 14 array< array < int, columns >, rows > a2 = { 1, 2, 3, 4, 5 }; 15 array< array < int, columns >, rows > a3 = { 1, 2, 3 }; 16 17 cout << "Values in a1 by row are:" << endl; 18 printArray( a1 ); 19 20 cout << "\nValues in a2 by row are:" << endl; 21 printArray( a2 ); 22 23 cout << "\nValues in a3 by row are:" << endl; 24 printArray( a3 ); 25 } // end main 2006 Pearson Education, Inc. All rights reserved. 26 27 // output array with two rows and three columns 28 void printArray( const array< array < int, columns >, rows > & a ) Outline 105 29 { 30 // loop through array's rows 31 for( const auto& row : a ) { 32 // loop through columns of current row 33 for( const auto& element : row ) { 34 35 36 37 Geschachtelte for-Schleifen zur Ausgabe des arrays cout << element << ' '; } fig07_31.cpp (2 von 2) Typinferenz: cout << endl; // start new line of output } // end outer for Der Typ eines Elements wird automatisch aus dem Typ des arrays abgeleitet. 38 } // end function printArray Values in a1 by row are: 1 2 3 4 5 6 Values in a2 by row are: 1 2 3 4 5 0 Values in a3 by row are: 1 2 3 0 0 0 2006 Pearson Education, Inc. All rights reserved. 106 7.9 Mehrdimensionale arrays • Manipulationen von mehrdimensionalen arrays – Werden üblicherweise mit for-Anweisungen durchgeführt. • Beispiel – Alle Elemente einer Zeile auf den Wert 0 setzen for( size_t col = 0; col < 4; ++col ) { a[ 2 ][ col ] = 0; } • Beispiel – Alle Elemente eines zweidimensionalen Arrays aufsummieren total = 0; for( auto row : a ) { for( auto element : row ) { total += element; } } 2006 Pearson Education, Inc. All rights reserved. 7.10 Fallstudie: Die Klasse GradeBook mit einem zweidimensionalen array 107 • Klasse GradeBook – Zweidimensionales Array • Es werden die erreichten Punktzahlen aller Studenten eines Zuges für alle Prüfungen des Studiums gespeichert. – Jede Zeile stellt alle Punktzahlen eines Studenten dar. – Jede Spalte stellt die Punktzahlen aller Studenten für eine bestimmte Prüfung dar. • Bestimmt werden sollen: – Minimum und Maximum aller Punktzahlen, – Durchschnittspunktzahl eines Studenten für alle seine Prüfungen, – Histogramm aller erreichten Punktzahlen. 2006 Pearson Education, Inc. All rights reserved. 1 // Fig. 7.32: GradeBook.h 2 // Definition of class GradeBook that uses a 2-dim array to store test grades. 3 // Member functions are defined in GradeBook.cpp 4 #include <array> 5 #include <string> Outline 108 GradeBook.h 6 7 class GradeBook // GradeBook class definition 8 { 9 public: (1 von 1) 10 // constants 11 static const size_t students = 10; // number of students 12 static const size_t tests = 3; // number of tests 13 GradeBook Konstruktor akzeptiert einen string und ein zweidimensionales Array 14 // constructor initializes course name and array of grades 15 GradeBook( const std::string &, 16 const std::array< std::array< int, tests >, students > & ); 17 void setCourseName( const std::string & ); // set the course name 18 std::string getCourseName() const; // retrieve the course name 19 std::string message() const; // return a welcome message 20 std::string processGradesResults() const; // operations on grade data 21 int getMinimum() const; // find the minimum grade in the grade book 22 int getMaximum() const; // find the maximum grade in the grade book 23 double getAverage( const std::array< int, tests > & ) const; // average 24 std::string gradesContents() const; // return contents of grades array 25 std::string barChart() const; // return bar chart of grade distribution 26 private: 27 std::string courseName; // course name for this grade book 28 std::array< std::array< int, tests >, students > grades; // 2D array 29 }; // end class GradeBook 2006 Pearson Education, Inc. All rights reserved. 1 // Fig. 7.33: GradeBook.cpp 2 // Member-function definitions for class GradeBook that 3 // uses a two-dimensional array to store grades. Outline 109 4 5 6 #include <sstream> #include <iomanip> 7 using namespace std; 8 9 #include "GradeBook.h" // GradeBook definition GradeBook.cpp (1 von 5) 10 11 // two-parameter constructor initializes courseName and grades array 12 GradeBook::GradeBook( const string& name, 13 14 const array< array< int, tests >, students > & gradesArray ) : courseName( name ), grades( gradesArray ) 15 { 16 } // end GradeBook constructor 17 18 // function to set the course name 19 void GradeBook::setCourseName( const string& name ) 20 { 21 courseName = name; // store the course name 22 } // end function setCourseName 23 24 // function to retrieve the course name 25 string GradeBook::getCourseName() const 26 { 27 return courseName; 28 } // end function getCourseName 2006 Pearson Education, Inc. All rights reserved. 29 30 // return a welcome message to the GradeBook user 31 string GradeBook::message() const Outline 110 32 { 33 return "Welcome to the grade book for\n" + getCourseName() + "!\n\n"; 34 } // end function message 35 36 // perform various operations on the data 37 string GradeBook::processGradesResults() const GradeBook.cpp (2 von 5) 38 { 39 stringstream resultStream; // write result as text in here 40 41 // write grades array 42 resultStream << gradesContents(); 43 44 // call functions getMinimum and getMaximum 45 resultStream << "\nLowest grade is " << getMinimum() 46 << "\nHighest grade is " << getMaximum() << endl; 47 48 // call function barChart to write grade distribution chart as text 49 resultStream << barChart(); 50 51 return resultStream.str(); // return result as a string 52 } // end function processGradesResults 53 2006 Pearson Education, Inc. All rights reserved. 54 // find minimum grade Outline 55 int GradeBook::getMinimum() const 56 { 57 int lowGrade = 100; // assume lowest grade is 100 58 // loop through rows of grades array 59 for( const auto& student : grades ) { 60 // loop through columns of current row 61 for( const auto& grade : student ) { GradeBook.cpp 62 // if current grade less than lowGrade, assign it to lowGrade 63 if( grade < lowGrade ) 64 65 lowGrade = grade; // new lowest grade } // end inner for 66 } // end outer for 67 return lowGrade; // return lowest grade 111 (3 von 5) Schleifen über Zeilen und Spalten von grades, um schlechteste Note aller Studenten zu finden 68 } // end function getMinimum 69 70 // find maximum grade 71 int GradeBook::getMaximum() const 72 { 73 int highGrade = 0; // assume highest grade is 0 74 // loop through rows of grades array 75 for( const auto& student : grades ) { 76 77 Schleifen über Zeilen und Spalten von grades, um beste Note aller Studenten zu finden // loop through columns of current row for( const auto& grade : student ) { 78 // if current grade greater than lowGrade, assign it to highGrade 79 if( grade > highGrade ) 80 81 highGrade = grade; // new highest grade } // end inner for 82 } // end outer for 83 return highGrade; // return highest grade 84 } // end function getMaximum 2006 Pearson Education, Inc. All rights reserved. 85 86 // determine average grade for particular set of grades 87 double GradeBook::getAverage( const array< int, tests > & setOfGrades ) const Outline 112 88 { 89 int total = 0; // initialize total 90 // sum grades in array 91 for( const auto& grade : setOfGrades ) 92 GradeBook.cpp (4 von 5) total += grade; 93 // return average of grades 94 return static_cast< double >( total ) / tests; 95 } // end function getAverage 96 97 // return the contents of the grades array as a string 98 string GradeBook::gradesContents() const 99 { 100 stringstream gradesStream; // write grades as text in here 101 gradesStream << "The grades are:\n\n"; 102 gradesStream << " 103 for( size_t test = 0; test < tests; ++test ) 104 105 106 107 108 109 110 111 "; // align column heads Für einen Studenten wird der Mittelwert über alle seine Tests gradesStream << "Test " << test + 1 << " "; berechnet, indem eine Zeile aus gradesStream << "Average" << endl; // student average column heading dem zweidimensionalen Array als for( size_t student = 0; student < students; ++student ) { gradesStream << "Student " << setw( 2 ) << student + 1; eindimensionales Array an die for( size_t test = 0; test < tests; ++test ) Funktion getAverage gradesStream << setw( 8 ) << grades[ student ][ test ]; übergeben wird. double average = getAverage( grades[ student ] ); gradesStream << setw( 9 ) << setprecision( 2 ) << fixed << average<< endl; 112 } // end outer for 113 return gradesStream.str(); // return grades as a string 114 } // end function gradesContents 2006 Pearson Education, Inc. All rights reserved. 115 116 // return bar chart displaying grade distribution as a string 117 string GradeBook::barChart() const Outline 113 118{ 119 stringstream chartStream; // write bar chart as text in here 120 chartStream << "\nOverall grade distribution:" << endl; 121 // stores frequency of grades in each range of 10 grades 122 const size_t frequencySize = 11; 123 array< unsigned int, frequencySize > frequency = { 0 }; // init to all 0s 124 // for each grade, increment the appropriate frequency 125 for( const auto& student : grades ) 126 127 for( const auto& test : student ) ++frequency[ test / 10 ]; // for each grade frequency, write bar in chart 129 for( size_t count = 0; count < frequencySize; ++count ) { 130 // write bar label ("0-9:", ..., "90-99:", "100:" ) 131 if( 0 == count) 133 134 135 136 chartStream << " 0-9: "; else if( 10 == count) chartStream << " 100: "; else chartStream << count * 10 << "-" << ( count * 10 ) + 9 << ": "; 137 // write bar of asterisks 138 for( unsigned int stars = 0; stars < frequency[ count ]; ++stars ) 139 140 (5 von 5) Berechnung der Verteilung aller Studentennoten 128 132 GradeBook.cpp chartStream << '*'; chartStream << endl; // start a new line of output 141 } // end outer for 142 return chartStream.str(); // return bar chart as a string 143 } // end function barChart 2006 Pearson Education, Inc. All rights reserved. 1 // Fig. 7.34: fig07_34.cpp 2 // Creates GradeBook object using a two-dimensional array of grades. 3 #include <array> 4 #include <iostream> 5 using namespace std; 6 7 fig07_34.cpp #include "GradeBook.h" // GradeBook definition 8 9 Outline 114 (1 von 2) int main() 10 { 11 // two-dimensional array of student grades 12 array< array< int, GradeBook::tests >, GradeBook::students > grades = 13 { 87, 96, 70, 14 68, 87, 90, 15 94, 100, 90, 16 100, 81, 82, 17 83, 65, 85, 18 78, 87, 65, 19 85, 75, 83, 20 91, 94, 100, 21 76, 72, 84, 22 87, 93, 73 }; Deklaration von grades als 3-mal-10 Array Jede Zeile entspricht einem Studenten; jede Spalte entspricht einer Prüfung 23 24 25 GradeBook myGradeBook( "CS101 Introduction to C++ Programming", grades ); 26 cout << myGradeBook.message(); 27 cout << myGradeBook.processGradesResults(); 28 } // end main 2006 Pearson Education, Inc. All rights reserved. Welcome to the grade book for CS101 Introduction to C++ Programming! Outline 115 The grades are: Student 1 Student 2 Student 3 Student 4 Student 5 Student 6 Student 7 Student 8 Student 9 Student 10 Test 1 87 68 94 100 83 78 85 91 76 87 Test 2 96 87 100 81 65 87 75 94 72 93 Test 3 70 90 90 82 85 65 83 100 84 73 Average 84.33 81.67 94.67 87.67 77.67 76.67 81.00 95.00 77.33 84.33 fig07_34.cpp (2 von 2) Lowest grade is 65 Highest grade is 100 Overall grade distribution: 0-9: 10-19: 20-29: 30-39: 40-49: 50-59: 60-69: *** 70-79: ****** 80-89: *********** 90-99: ******* 100: *** 2006 Pearson Education, Inc. All rights reserved.