arrays und vectors, Suchen und Sortieren - fbi.h-da.de · PDF file2006 Pearson Education, Inc. All rights reserved. 1 7 arrays und vectors, Suchen und Sortieren

2006 Pearson Education, Inc. All rights reserved.

1

77arrays und vectors,

Suchen undSortieren


2

7.1 Einführung7.2 Arrays 7.3 Deklaration von arrays 7.4 Beispiele zum Gebrauch von arrays 7.5 Übergabe von arrays an Funktionen7.6 Fallstudie: Die Klasse GradeBook mit einem array

7.7 Einführung in die C++ STL Klasse vector

7.8 Suchen und Sortieren7.8.1 Lineare Suche7.8.2 Binäre Suche7.8.3 Sortieren durch direktes Einfügen (Insertion-Sort)7.8.4 Merge-Sort (rekursive Implementierung)

7.9 Mehrdimensionale arrays 7.10 Fallstudie: Die Klasse GradeBook mit einem zweidimensionalen

array


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)


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.


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 einspezifisches 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.


6

Fig.7.1 | Array mit 12 Elementen


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.


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)’.


9

Fig.7.2 | Operatorvorrang und Assoziativiät.

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


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 selbst-

definierte Klassen) enthalten, jedoch keine Referenzen.– Mehrere arrays des gleichen Elementtyps und der

gleichen Elementanzahl können in einer einzigenDeklaration deklariert werden.

• Mit einer kommaseparierten Liste der Namen


11

7.4 Beispiele zum Gebrauch von arrays

• Einsatz einer Schleife zur Initialisierung der arrayelemente

– Deklaration des arrays mit Angabe von Typ und Anzahlder Elemente

– Wiederholungsanweisung, um jedes Arrayelementanzusprechen

• Im Körper der Wiederholungsanweisung wird jedeseinzelne Arrayelement initialisiert.


12Outline

fig07_03.cpp

(1 von 1)

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;

7 8 int main()

9 {

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 cout << setw( 7 ) << j << setw( 13 ) << n[ j ] << endl; 19 }

20 } // end main Element Value

0 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 0

n[ j ] gibt den int zurück, der dem Index j im Array n zugeordnet ist.

Jeder int wurde mit 0 initialisiert.

Der Header <array> muss eingeschlossen werden.


13


• 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.


14


• Initialisierung eines arrays bei der Deklarationmit Hilfe einer Initialisierungsliste

– Initialisierungsliste• Werte werden in geschweifte Klammern ({}) eingeschlossen.• Einzelne Werte in der Liste werden durch Kommas getrennt.• Beispielarray< 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.


15


• 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 ).

• Beispielarray< 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.


16


Falls mehr Initialisierungswerte angegeben werden als Elemente im Array vorhanden sind, führt dies zu einer Fehlermeldung des Compilers.


17 1 // Fig. 7.4: fig07_04.cpp

2 // Initializing an array in a declaration.




7 8 int main()

9 {

10 // use initializer list to initialize array n 11 array< int, 10 > n = { 32, 27, 64, 18, 95, 14, 90, 70, 60, 37 }; 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 cout << setw( 7 ) << i << setw( 13 ) << n[ i ] << endl; 18 } 19 } // end main Element Value

0 32 1 27 2 64 3 18 4 95 5 14 6 90 7 70 8 60 9 37

Outline

fig07_04.cpp

(1 von 1)


18


• Beispiel: Festlegen der arraygröße mit einerkonstanten 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 alsconst 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.


19 1 // Fig. 7.5: fig07_05.cpp

2 // Set array s to the even integers from 2 to 20.




7 8 int main()

9 {

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 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 cout << setw( 7 ) << j << setw( 13 ) << s[ j ] << endl; 21 }

22 } // end main Element Value

0 2 1 4 2 6 3 8 4 10 5 12 6 14 7 16 8 18 9 20

Outline

fig07_05.cpp

(1 von 1)

Soll die Arraygröße mit einer Variablen festgelegt werden, muss diese als const erklärt werden.

Die Schleifenvariable wird als Arrayindex und als Rechengröße verwendet.


20


• 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


21


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.


22 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

7 8 x = 7; // Error: cannot modify a const variable

9 } // end main

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'

Outline

fig07_07.cpp

(1 von 1)


23


Nur Konstanten können zur Deklaration der Größe von arrays verwendet werden. Wird hierfür keine Konstante verwendet, führtdies zu einer Fehlermeldung des Compilers.

Soll die Arraygröße veränderbar sein, muss einvector verwendet werden (s. Abschnitt 7.7) .


24

Betrachtung zum Software Engineering

Die Festlegung von arraygrößen mit konstantenVariablen anstelle von Literalkonstanten machtProgramme skalierbarer.Soll das array bzw. mehrere gleich große arrays eine andere Größe bekommen, muss nur an einereinzigen Stelle im Programm die Definition der konstanten Variablen geändert werden.


25


• 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.


26


• Bereichsbasierte for-Schleife– Um über alle Elemente in einem Array (bzw. allgemeiner:

Container) zu iterieren, gibt es eine kürzere Form der for-Schleife, die bereichsbasierte for-Schleife:

• for( int n : numbers ) {cout << n << ' ';

}

• Alle Elemente des int arrays numbers werden der Reihenach ü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, dassdieser Zähler den erlaubten Bereich für die Indices verlässt, wird vermieden.


27 1 // Fig. 7.8: fig07_08.cpp

2 // Compute the sum of the elements of an array.



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; 12 13 // sum contents of array numbers 14 for( int n : numbers ) { 15 total += n; 16 } 17 18 cout << "Total of array elements: " << total << endl; 19 } // end main Total of array elements: 458

Outline

fig07_08.cpp

(1 von 1)


28


• Graphische Darstellung von arraydaten durchHistogramme

– Eine einfache Darstellung der Werte in einem array kanndurch ein um 90 Grad gedrehtes Histogramm, das z.B. ausSternchen (*) aufgebaut wird, realisiert werden.

– Im folgenden Beispiel wird dies für die Darstellung von Prozentpunkten durch Sternchensäulen demonstriert.

– Geschachtelte for Anweisungen steuern die Ausgabe des Histogramms.


29 1 // Fig. 7.9: fig07_09.cpp

2 // Bar chart printing program.



5 #include <array>

6 using namespace std;

7 8 int main()

9 {

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 << "Element" << setw( 13 ) << "Value" << setw( 17 ) << "Histogram\n"; 14 // for each element of array numbers, output a bar of the chart 15 for( size_t i = 0; i < size; ++i ) { 16 cout << setw( 7 ) << i << setw( 13 ) << numbers [ i ] << setw( 8 ); 17 // print bar of asterisks 18 for( unsigned stars = 0; stars < numbers[ i ]; ++stars ) { 19 cout << '*'; 20 } 21 cout << endl; // start a new line of output 22 } // end outer for 23 } // end main

Outline

fig07_09.cpp

(1 von 2)

Für jedes Arrayelement wird die entsprechende Anzahl von

Sternchen ausgegeben


30 Element Value Histogram

0 0

1 0

2 0

3 0

4 4 ****

5 15 ***************

6 23 ***********************

7 42 ******************************************

8 16 ****************

9 8 ********

10 0

Outline

fig07_09.cpp

(2 von 2)


31


• Die Elemente eines arrays als Zähler verwenden– Ein array soll zur Zählung von ganzzahligen Größen

verwendet werden (Beispiel: Häufigkeit der Augenzahleneines 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ählendenGrößen in dem array.

– Im folgenden Beispiel wird dies für die Häufigkeitsverteilungbeim Würfeln mit einem Würfel demonstriert.


32 1 // Fig. 7.10: fig07_10.cpp

2 // Frequency of rolling a six-sided die 6,000,000 times using an array.



5 #include <array>

6 #include <cstdlib> 7 #include <ctime>


9 10 int main() 11 { 12 srand( static_cast< unsigned >( time( nullptr ) ) ); 13 const size_t arraySize = 7; // ignore element zero 14 array< unsigned, arraySize > frequency = { 0 }; // initialize to 0s 15 16 // roll die 6,000,000 times; use die value as frequency index 17 for( unsigned roll = 1; roll <= 6000000; ++roll ) { 18 ++frequency[ 1 + rand() % 6 ]; 19 } 20 21 cout << "Face" << setw( 13 ) << "Frequency" << endl; 22 // output each array element's value 23 for( size_t face = 1; face < arraySize; ++face ) { 24 cout << setw( 4 ) << face << setw( 13 ) << frequency[ face ] 25 << endl; 26 } 27 } // end main

Outline

fig07_10.cpp

(1 von 2)

Inkrementierung des frequency Wertesan der Indexposition, die durch die

Zufallszahl ausgewählt wird


33 Face Frequency

1 1000167

2 1000149

3 1000152

4 998748

5 999626

6 1001158

Outline

fig07_10.cpp

(2 von 2)


34


• 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.


35 1 // Fig. 7.11: fig07_11.cpp

2 // Student poll program.




7 8 int main()

9 {

10 const size_t responseSize = 40; // size of array responses 11 const size_t frequencySize = 11; // size of array frequency 12 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 }; 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 cout << setw( 6 ) << rating << setw( 17 ) << frequency[ rating ] 30 << endl; 31 } 32 } // end main

Outline

fig07_11.cpp

(1 von 2)

Für jede Antwort wird der frequency Wert an der zugehörigen

Indexposition inkrementiert


36 Rating Frequency

1 2

2 2

3 2

4 2

5 5

6 11

7 5

8 7

9 1

10 3

Outline

fig07_11.cpp

(2 von 2)


37

7.5 Übergabe von arrays an Funktionen

• Funktionsprototypen von Funktionen, die arrays als Argumente übernehmen

– Die Parameterliste der Funktion muss einen arrayparameterfestlegen.

• Beispiel:void modifyArray( array< int, arraySize > );

– Der arrayparameter muss Typ und Anzahl der Elementeeinschließen.

• Nur dann ist das Klassentemplate array ein vollständigerTyp.


38


• Übergabe eines Arrays als Argument an eine Funktion

– Angabe des Arraynamens (ohne weitere Informationen)• Array a ist deklariert als

array< int, arraySize > a;

• Der FunktionsaufrufmodifyArray( 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.


39


•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 Programmteilbleibt unverändert.

– Das gilt genauso für vector und alle anderen STL-Container.

– Im Gegensatz dazu werden C-Arrays wegen ihres simplerenAufbaus referenzmäßig an Funktionen übergeben (Details hierzu s. Kapitel 8).


40


• 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 array-elements als Argument verwendet werden.


41 1 // Fig. 7.14: fig07_14.cpp

2 // Passing arrays and individual array elements to functions.




7 8 const int arraySize = 5; // size of array a; global CONSTANT is okay 9 10 void modifyArray( array< int, arraySize > ); // receive array 11 void modifyElement( int ); // receive array element value 12 13 int main() 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 cout << setw( 3 ) << elem;

22 }

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 // array elements are unaffected 30 for( const int& elem : a ) { 31 cout << setw( 3 ) << elem;

32 }

Outline

fig07_14.cpp

(1 von 3)

Funktion übernimmt ein array als Argument


4233 34 cout << "\n\n\nEffects of passing array element by value:" 35 << "\n\na[3] before modifyElement: " << a[ 3 ] << endl; 36 37 modifyElement( a[ 3 ] ); // pass array element a[ 3 ] by value 38 cout << "a[3] after modifyElement: " << a[ 3 ] << endl; 39 } // end main 40 41 // in function modifyArray, "b" is a local copy of 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 cout << setw( 3 ) << elem; 51 } 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

Outline

fig07_14.cpp

(2 von 3)


43 Effects of passing entire array by value:

The values of the original array are: 0 1 2 3 4 The values of the array in modifyArray are: 0 2 4 6 8 The values of the array after modifyArray are: 0 1 2 3 4

Effects of passing array element by value:

a[3] before modifyElement: 3 Value of element in modifyElement: 6 a[3] after modifyElement: 3

Outline

fig07_14.cpp

(3 von 3)


44

7.6 Fallstudie: Die Klasse GradeBook miteinem array

• 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ößeeines gewöhnlichen Arrays in der Klassendefinition verwendet werden.


45 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

4 5 #include <string>

6 #include <array>

7 8 // GradeBook class definition

9 class GradeBook

10 { 11 public: 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 int getMinimum() const; // find the minimum grade for the test 22 int getMaximum() const; // find the maximum grade for the test 23 double getAverage() const; // determine the average grade for the test 24 std::string gradesContents() const; // contents of grades array as a string 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< int, students > grades; // array of student grades 29 }; // end class GradeBook

Outline

GradeBook.h

(1 von 1)

Anzahl der betrachteten Studenten


46 1 // Fig. 7.17: GradeBook.cpp

2 // Member-function definitions for class GradeBook that

3 // uses an array to store test grades.

4

5 #include <sstream>



8 9 #include "GradeBook.h" // GradeBook definition

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 29

Outline

GradeBook.cpp

(1 von 4)


4730 // return a welcome message to the GradeBook user 31 string GradeBook::message() const 32 { 33 return "Welcome to the grade book for\n" + getCourseName() + "!\n\n"; 34 } // end function message 35 36 int GradeBook::getMinimum() const // find minimum grade 37 { 38 int lowGrade = 100; // assume lowest grade is 100 39 for( int grade : grades ) { 40 // if current grade lower than lowGrade, assign it to lowGrade 41 if( grade < lowGrade ) 42 lowGrade = grade; // new lowest grade 43 } // end for 44 return lowGrade; // return lowest grade 45 } // end function getMinimum 46 47 int GradeBook::getMaximum() const // find maximum grade 48 {

49 int highGrade = 0; // assume highest grade is 0 50 for( int grade : grades ) { 51 // if current grade higher than highGrade, assign it to highGrade 52 if( grade > highGrade ) 53 highGrade = grade; // new highest grade 54 } // end for 55 return highGrade; // return highest grade 56 } // end function getMaximum

Outline

GradeBook.cpp

(2 von 4)Schleife durch grades, um schlechteste Note zu finden

Schleife durch grades, um beste Note zu finden


4857 58 // determine average grade for test 59 double GradeBook::getAverage() const 60 { 61 int total = 0; // initialize total 62 63 // sum grades in array 64 for( int grade : grades ) { 65 total += grade; 66 } 67 // return average of grades 68 return static_cast< double >( total ) / students; 69 } // end function getAverage 70 71 // return the contents of the grades array as a string 72 string GradeBook::gradesContents() const 73 { 74 stringstream gradesStream; // write grades as text in here 75 76 gradesStream << "The grades are:\n\n"; 77 // write each student's grade 78 for( size_t student = 0; student < students; ++student ) { 79 gradesStream << "Student " << setw( 2 ) << student + 1 << ": " 80 << setw( 3 ) << grades[ student ] << endl; 81 } 82 return gradesStream.str(); // return grades as a string 83 } // end function gradesContent 84

Outline

GradeBook.cpp

(3 von 4)

Schleife durch grades, um Noten aller Studenten zu summieren

Durchschnittsnote: Teilen der Summe durch die Anzahl der Studenten


4985 // output bar chart displaying grade distribution 86 string GradeBook::barChart() const 87 { 88 stringstream chartStream; // write bar chart as text in here 89 90 chartStream << "\nGrade distribution:" << endl; 91 // stores frequency of grades in each range of 10 grades 92 const size_t frequencySize = 11; 93 array< unsigned int, frequencySize > frequency = { 0 }; 94 // for each grade, increment the appropriate frequency 95 for( int grade : grades ) { 96 ++frequency[ grade / 10 ]; 97 } 98 // for each grade frequency, write bar in chart 99 for( size_t count = 0; count < frequencySize; ++count ) { 100 // write bar labels ("0-9:", ..., "90-99:", "100:" ) 101 if( 0 == count ) 102 chartStream << " 0-9: "; 103 else if( 10 == count ) 104 chartStream << " 100: "; 105 else 106 chartStream << count * 10 << "-" << ( count * 10 ) + 9 << ": "; 107 // write bar of asterisks 108 for( unsigned int stars = 0; stars < frequency[ count ]; ++stars ) { 109 chartStream << '*'; 110 } 111 chartStream << endl; // start a new line of text 112 } // end outer for 113 return chartStream.str(); // return bar chart as a string 114 } // end function barChart

Outline

GradeBook.cpp

(4 von 4)

Schleife durch grades, um Häufigkeit zu berechnen

Histogramm aus Sternchen ausgeben


50 1 // Fig. 7.18: fig07_18.cpp

2 // Creates GradeBook object using an array of grades.

3 #include <iostream> 4 #include <iomanip> 5 #include <array>


7 8 #include "GradeBook.h" // GradeBook definition

9 10 int main() 11 { 12 // array of student grades 13 const array< int, GradeBook::students > grades = 14 { 87, 68, 94, 100, 83, 78, 85, 91, 76, 87 }; 15 16 GradeBook myGradeBook( 17 "CS101 Introduction to C++ Programming", grades ); 18 cout << myGradeBook.message(); 19 cout << myGradeBook.gradesContents(); 20 cout << "\nClass average is " << setprecision( 2 ) << fixed 21 << myGradeBook.getAverage() << endl; 22 cout << "Lowest grade is " << myGradeBook.getMinimum() 23 << "\nHighest grade is "<< myGradeBook.getMaximum() << endl; 24 cout << myGradeBook.barChart(); 25 } // end main

Outline

fig07_18.cpp

(1 von 2)

Übergabe von grades an GradeBook Konstruktor

Verwendung des static Datenelements students der Klasse GradeBook


51Outline

fig07_18.cpp

(2 von 2)

Welcome to the grade book for CS101 Introduction to C++ Programming!

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

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


527.7 Einführung in die C++ STL Klassevector

• 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 weiteresElement 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.


53

7.7 Einführung in die C++ STL Klassevector

• 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!


54 1 // Fig. 7.19: fig07_19.cpp

2 // Demonstrating C++ Standard Library class template vector.



5 #include <vector>


8 9 void outputVector( const vector< int > & ); // display the vector

10 11 int main() 12 { 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 << "\nvector after initialization:" << endl; 19 outputVector( v1 ); 20 21 // print v2 size and contents 22 cout << "\nSize of vector v2 is " << v2.size() 23 << "\nvector after initialization:" << endl; 24 outputVector( v2 ); 25 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;

Outline

fig07_19.cpp

(1 von 4)

Verwendung von const, damit outputVector einen übergebenen vector nicht modifizieren kann

Diese vector-Objekte speichern ints.

Funktion size gibt Anzahl der Elemente im vector zurück.

Funktion push_back fügt ein Element am Ende des vectors ein.


5529 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 ); 39 40 // use inequality (!=) operator with vector objects 41 cout << "\nEvaluating: v1 != v2" << endl; 42 if( v1 != v2 ) { 43 cout << "v1 and v2 are not equal" << endl; 44 } 45 46 // use square brackets to create rvalue 47 cout << "\nv1[5] is " << v1[ 5 ]; 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 );

Outline

fig07_19.cpp

(2 von 4)

back gibt das letzte Element eines vectors zurück und pop_back entfernt es.

Einen Wert des vectors ausgeben

Einen Wert des vectors ändern


5654 55 // attempt to use out-of-range subscript 56 try { 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 cerr << "An exception occurred: " << ex.what() << endl; 62 } 63 64 cout << "\nAfter exception-handling program can continue:" << endl; 65 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 cerr << "An exception occurred: " << ex.what() << endl; 73 } 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 }

Outline

fig07_19.cpp

(3 von 4)

Funktion at führt Bereichsüberprüfung durch

try und catch-Block für eine geregelte Ausnahmebehandlung

Behandlung der Ausnahme: hier einfach Aufruf der Elementfunktion what


57Outline

fig07_19.cpp

(4 von 4)

Size of vector v1 is 7 vector after initialization: 1 2 3 4 5 6 7 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 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


58

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


59

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)


60


• Ü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


61


• 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


62

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


63Outline

fig07_20.cpp

(1 von 2)

1 // Fig. 7.20: fig07_20.cpp

2 // Linear search of an array.


4 #include <array>

5 using namespace std; 6

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

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


6419 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 25 26 for( size_t i = 0; i < arraySize; ++i ) 27 a[ i ] = 2 * i; // create some data 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 cout << "Found value in element " << element << endl; 38 else 39 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

Outline

fig07_20.cpp

(2 von 2)

Funktion gibt den Index des Suchschlüssels zurück; -1 falls er nicht gefunden wird


65

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


66

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.


67

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


68

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


69

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.


70

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.


71

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 Suchenur noch in der ersten Hälfte des vectors fortgesetzt.

– Falls es kleiner als der Suchschlüssel ist, wird die Suchenur noch in der zweiten Hälfte des vectors fortgesetzt.


72

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.


73 1 // Fig 7.23: Fig07_23.cpp

2 // Binary search in a vector of random integers.

3


5 #include <vector> 6 #include <algorithm> // prototype for std::sort function 6 #include <cstdlib> 7 #include <ctime> 8 using namespace std; 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 for( size_t i = 0; i < low; ++i ) // display spaces for alignment 15 cout << " "; 16 for( size_t i = low; i <= high; ++i ) // display elements left in vector 17 cout << data[ i ] << " "; 18 cout << endl; 19 } // end function displayElements 20

Outline

fig07_23.cpp

(1 von 4)


7421 // perform a binary search on the data 22 template < typename T > 23 int binarySearch( const vector< T >& data, const T& key ) 24 { 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 { 32 // 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 ) 36 cout << " "; 37 cout << " * " << endl; // indicate current middle 38 39 if( key < data[ middle ] ) 40 high = middle - 1; // eliminate the higher half 41 else if( data[ middle ] < key ) 42 low = middle + 1; // eliminate the lower half 43 else 44 location = middle; // location is the current middle 45 46 middle = ( low + high + 1 ) / 2; // recalculate the middle 47 } while( ( low <= high ) && ( location == -1 ) ); 48 49 return location; // return location of key 50 } // end function binarySearch 51

Outline

fig07_23.cpp

(2 von 4)

Initialisierung der Indices low, highund middle des vectors

Initialisierung von location mit -1, um anzuzeigen, dass der Suchschlüssel (noch) nicht gefunden wurde

Schleife läuft, bis der Teilvector die Größe Null hat oder der Suchschlüssel gefunden ist

Test, ob das Element an der Position middle gleich key ist

Fortsetzung der Suche in der passenden Hälfte des vectors


7552 int main() 53 { 54 srand( static_cast< unsigned >( time( nullptr ) ) ); 55 const size_t size = 15; // vector size 56 vector< int > data; // empty vector of ints 57 58 for( size_t i = 0; i < size; ++i ) // random ints from 10 to 99 59 data.push_back( 10 + rand() % 90 ); // 10-99 60 std::sort( data.begin(), data.end() ); // sort the data 61 displayElements( data, 0, size - 1 ); // output the data 62 63 cout << "\n\nPlease enter an integer value (-1 to quit): "; 64 int searchKey; // value to locate 65 cin >> searchKey; // read an int from user 66 cout << endl; 67 68 while( searchKey != -1 ) { // repeatedly input; -1 ends program 69 int position = binarySearch( data, searchKey ); 70 if( position == -1 ) 71 cout << "The integer " << searchKey << " was not found.\n"; 72 else 73 cout << "The integer " << searchKey 74 << " was found in position " << position << ".\n"; 75 cout << "\n\nPlease enter an integer value (-1 to quit): "; 76 cin >> searchKey; // read an int from user 77 cout << endl; 78 } // end while 79 } // end main

Outline

fig07_23.cpp

(3 von 4)

Durchführung der binären Suche


76Outline

fig07_23.cpp

(4 von 4)

26 31 33 38 47 49 51 67 73 74 82 89 90 91 95

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. 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


77

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.


78

7.8.3 Sortieren durch direktes Einfügen(Insertion-Sort)

• 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 eingesetztenAlgorithmus.

• Die Wahl des Algorithmus beeinflusst allerdings die zumSortieren benötigte Laufzeit sowie den Speicherverbrauch.


79

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.


80

7.8.3 Insertion-Sort• Beispiel

• Unsortiertes Array34 56 04 10 77 51 93 30 05 52

• Erster Schritt (Vertauschen, falls erforderlich)34 56

• Einsetzen des dritten Elements an der passenden Stelle34 56 0434 56 04

34 56 0404 34 56

• Einsetzen des vierten Elements an der passenden Stelle 04 34 56 1004 34 56 1004 34 56 1004 10 34 56 und so weiter...


81 1 // Fig. 7.24: fig07_24.cpp

2 // Sorting a container into ascending order with insertion sort.



5 #include <array>

6 #include <vector> 7 #include <string> 8 using namespace std; 9

10 template < typename T > void insertionSort( T & container ); 11 template < typename T > void print( const T & container ); 12 13 int main() 14 { 15 const size_t SIZE = 10; // size of array a 16 array< int, SIZE > a = { 34, 56, 4, 10, 77, 51, 93, 30, 5, 52 }; 17 cout << "Unsorted array:\n"; 18 print( a ); 19 insertionSort( a ); // sort the array of ints 20 cout << "\nSorted array:\n"; 21 print( a ); 22 23 vector< string > v = { "Kilo", "Papa", "Delta", "Mike", "Lima" }; 24 cout << "\n\nUnsorted vector:\n"; 25 print( v ); 26 insertionSort( v ); // sort the vector of strings 27 cout << "\nSorted vector:\n"; 28 print( v ); 29 cout << endl << endl; 30 } // end main

Outline

fig07_24.cpp

(1 von 2)


8231 32 template < typename T > // sort a container into ascending order

33 void insertionSort( T & container ) 34 { 35 for( size_t next = 1; next < container.size(); ++next ) { 36 auto insert = container[ next ]; // save value of next item to insert 37 size_t moveIndex = next; // initialize location to place element 38 // search for the location in which to put the current element 39 while( ( moveIndex > 0 ) && ( container[ moveIndex - 1 ] > insert ) ) { 40 // shift element one slot to the right 41 container[ moveIndex ] = container[ moveIndex - 1 ]; 42 --moveIndex; 43 } // end while 44 container[ moveIndex ] = insert; // place insert item back into array 45 } // end for 46 } // end function insertionSort 47 48 template < typename T > // print a container 49 void print( const T & container ) 50 { 51 cout << left; 52 for( const auto & element : container ) 53 cout << setw( 7 ) << element; 54 } // end function print Unsorted array: 34 56 4 10 77 51 93 30 5 52 Sorted array: 4 5 10 30 34 51 52 56 77 93 Unsorted vector: Kilo Papa Delta Mike Lima Sorted vector: Delta Kilo Lima Mike Papa

Outline

fig07_24.cpp

(2 von 2)

Die Position finden, wohin das gerade betrachtete

Element gehört

Das Element an die richtigePosition setzen


83


• Typinferenz mit auto– Wird eine Variable bei ihrer Definition bereits initialisiert,

kann aus dem Typ des Initialisierungswertes automatischder 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 beispielsweisebei der Zuweisung eines Arrayelements an eine neu zudefinierende Variable oder beim bereichsbasierten for

möglich.


84


• 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.


85

7.8.4 Merge-Sort (rekursive Implementierung)

• 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 beidenTeilvectoren verglichen.

– Das kleinere Element wird entfernt und in den großen, kombinierten vector geschrieben.


86

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.


87

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.


88 1 // Fig 7.27: Fig07_27.cpp

2 // Sorting a vector into ascending order with merge sort.


4 #include <vector> 5 #include <cstdlib> 6 #include <ctime> 7 using namespace std; 8 9 // 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

Outline

fig07_27.cpp

(1 von 7)

Formatierte Ausgabe der (Teil-)vectorenzur Veranschaulichung des Algorithmus


8930 31 // recursive function to sort (sub)vectors 32 template < typename T > 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 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

Outline

fig07_27.cpp

(2 von 7)

Sortierung der (Teil-)vectoren

Verschmelzen der beiden sortierten (Teil-)vectoren in einen größeren, sortierten (Teil-)vector


9057 58 // merge two sorted subvectors into one sorted subvector 59 template < typename T > 60 void merge( vector< T >& data, size_t left, size_t middle1, 61 size_t middle2, size_t right, vector< T >& combined ) 62 { 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 66 67 // output two subvectors before merging 68 cout << "merge: "; 69 displayElements( data, left, middle1 ); 70 cout << " "; 71 displayElements( data, middle2, right ); 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 combined[ combinedIndex++ ] = data[ leftIndex++ ]; 79 else 80 combined[ combinedIndex++ ] = data[ rightIndex++ ]; 81 } // end while 82

Outline

fig07_27.cpp

(3 von 7)

Schleife, bis das Ende einer der Teilvectoren erreicht ist

Test, welches Element am Anfang der vectoren kleiner ist

Schreiben des kleineren Elements in den kombinierten vector


9183 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 while( leftIndex <= middle1 ) // copy in rest of left vector 90 combined[ combinedIndex++ ] = data[ leftIndex++ ]; 91 } // end else 92 93 // copy values back into original vector 94 for( size_t i = left; i <= right; ++i ) { 95 data[ i ] = combined[ i ]; 96 } 97 98 // output merged vector 99 cout << " "; 100 displayElements( data, left, right ); 101 cout << endl; 102} // end function merge

Outline

fig07_27.cpp

(4 von 7)

Füllen des kombinierten vectors mit den restlichen Elementen des rechten vectors oder…

… mit den restlichen Elementen des linken vectors

Kopieren des kombinierten vectors in den Originalvector


92 103 int main() 104 { 105 srand( static_cast< unsigned >( time( nullptr ) ) ); 106 const size_t SIZE = 10; // vector size 107 108 vector< int > data; // empty vector of ints 109 for( int i = 0; i < SIZE; ++i ) { 110 data.push_back( 10 + rand() % 90 ); // 10-99 111 } 112 cout << "Unsorted vector:" << endl; 113 displayElements( data, 0, SIZE - 1 ); // print unsorted vector 114 cout << endl; 115 116 mergeSort( data, 0, SIZE - 1 ); // sort vector 117 118 cout << "Sorted vector:" << endl; 119 displayElements( data, 0, SIZE - 1 ); // print sorted vector 120 } // end main

Outline

fig07_27.cpp

(5 von 7)


93Outline

fig07_27.cpp

(6 von 7)

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


94Outline

fig07_27.cpp

(7 von 7)

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


95

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)


96

Fig. 7.28 | Such- und Sortieralgorithmen mit Komplexitätswerten.

Algorithmus Komplexität

Lineare Suche O(n) Binäre Suche O(log n) Rekursive lineare Suche O(n) Rekursive binäre Suche O(log n) Bubble-Sort O(n2) Selection-Sort O(n2) Insertion-Sort O(n2) Merge-Sort O(n log n)

Quick-Sort Ungünstigster Fall: O(n2) Durchschnittlich: O(n log n)


97

Fig. 7.29 | Zahlenwerte zu typischen Groß-O-Ausdrücken.

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


98

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.


99

Fig.7.30 | Zweidimensionales Array mit drei Zeilen (rows) und vier Spalten (columns).


100


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


101


• Deklaration und Initialisierung von zweidimensionalen arrays

– Deklaration des zweidimensionalen Arrays b• array< array< int, 2 >, 2 > b =

{ 1, 2, 3, 4 };

1 und 2 initialisieren b[ 0 ][ 0 ] und b[ 0 ][ 1 ]3 und 4 initialisieren b[ 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).


102 1 // Fig. 7.31: fig07_31.cpp

2 // Initializing multidimensional arrays.


4 #include <array>


6 7 const size_t rows = 2; 8 const size_t columns = 3; 9 void printArray( const array< array < int, columns >, rows > & );

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

Outline

fig07_31.cpp

(1 von 2)


10326 27 // output array with two rows and three columns 28 void printArray( const array< array < int, columns >, rows > & a ) 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 cout << element << ' '; 35 } 36 cout << endl; // start new line of output 37 } // end outer for 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

Outline

fig07_31.cpp

(2 von 2)

Geschachtelte for-Schleifenzur Ausgabe des arrays

Typinferenz: Der Typ eines Elements wirdautomatisch aus dem Typ des arrays abgeleitet.


104


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

}

}


105

7.10 Fallstudie: Die Klasse GradeBookmit einem zweidimensionalen array

• Klasse GradeBook– Zweidimensionales Array

• Es werden die erreichten Punktzahlen aller Studenten einesZuges 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.


106 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>

6 7 class GradeBook // GradeBook class definition

8 {

9 public:

10 // constants 11 static const size_t students = 10; // number of students 12 static const size_t tests = 3; // number of tests 13 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 int getMinimum() const; // find the minimum grade in the grade book 21 int getMaximum() const; // find the maximum grade in the grade book 22 double getAverage( const std::array< int, tests > & ) const; // average 23 std::string gradesContents() const; // return contents of grades array 24 std::string barChart() const; // return bar chart of grade distribution 25 private: 26 std::string courseName; // course name for this grade book 27 std::array< std::array< int, tests >, students > grades; // 2D array 28 }; // end class GradeBook

Outline

GradeBook.h

(1 von 1)

GradeBook Konstruktor akzeptiert einen string und ein zweidimensionales Array


107 1 // Fig. 7.33: GradeBook.cpp

2 // Member-function definitions for class GradeBook that

3 // uses a two-dimensional array to store grades.

4 #include <sstream>



7

8 #include "GradeBook.h" // GradeBook definition

9 10 // two-parameter constructor initializes courseName and grades array 11 GradeBook::GradeBook( const string& name, 12 const array< array< int, tests >, students > & gradesArray ) 13 : courseName( name ), grades( gradesArray ) { } // end constructor 14 15 // function to set the course name 16 void GradeBook::setCourseName( const string& name ) 17 { 18 courseName = name; // store the course name 19 } // end function setCourseName 20 21 // function to retrieve the course name 22 string GradeBook::getCourseName() const 23 { 24 return courseName; 25 } // end function getCourseName 26 27 // return a welcome message to the GradeBook user 28 string GradeBook::message() const 29 { 30 return "Welcome to the grade book for\n" + getCourseName() + "!\n\n"; 31 } // end function message

Outline

GradeBook.cpp

(1 von 4)


10832 // find minimum grade 33 int GradeBook::getMinimum() const 34 { 35 int lowGrade = 100; // assume lowest grade is 100 36 // loop through rows of grades array 37 for( const auto& student : grades ) { 38 // loop through columns of current row 39 for( const auto& grade : student ) { 40 // if current grade less than lowGrade, assign it to lowGrade 41 if( grade < lowGrade ) 42 lowGrade = grade; // new lowest grade 43 } // end inner for 44 } // end outer for 45 return lowGrade; // return lowest grade 46 } // end function getMinimum 47 48 // find maximum grade

49 int GradeBook::getMaximum() const 50 { 51 int highGrade = 0; // assume highest grade is 0 52 // loop through rows of grades array 53 for( const auto& student : grades ) { 54 // loop through columns of current row 55 for( const auto& grade : student ) { 56 // if current grade greater than lowGrade, assign it to highGrade 57 if( grade > highGrade ) 58 highGrade = grade; // new highest grade 59 } // end inner for 60 } // end outer for 61 return highGrade; // return highest grade 62 } // end function getMaximum

Outline

GradeBook.cpp

(2 von 4)

Schleifen über Zeilen und Spalten von grades, um schlechteste Note aller Studenten zu finden

Schleifen über Zeilen und Spalten von grades, um beste Note aller Studenten zu finden


109Outline

GradeBook.cpp

(3 von 4)

63 64 // determine average grade for particular set of grades 65 double GradeBook::getAverage( const array< int, tests > & setOfGrades ) const 66 { 67 int total = 0; // initialize total 68 // sum grades in array 69 for( const auto& grade : setOfGrades ) 70 total += grade; 71 // return average of grades 72 return static_cast< double >( total ) / tests; 73 } // end function getAverage 74 75 // return the contents of the grades array as a string 76 string GradeBook::gradesContents() const 77 { 78 stringstream gradesStream; // write grades as text in here 79 gradesStream << "The grades are:\n\n"; 80 gradesStream << " "; // align column heads 81 for( size_t test = 0; test < tests; ++test ) 82 gradesStream << "Test " << test + 1 << " "; 83 gradesStream << "Average" << endl; // student average column heading 84 for( size_t student = 0; student < students; ++student ) { 85 gradesStream << "Student " << setw( 2 ) << student + 1; 86 for( size_t test = 0; test < tests; ++test )

87 gradesStream << setw( 8 ) << grades[ student ][ test ];

88 double average = getAverage( grades[ student ] );

89 gradesStream << setw( 9 ) << setprecision( 2 ) << fixed << average<< endl;

90 } // end outer for 91 return gradesStream.str(); // return grades as a string

92 } // end function gradesContents

Für einen Studenten wird der Mittelwert über alle seine Tests berechnet, indem eine Zeile aus

dem zweidimensionalen Array als eindimensionales Array an die

Funktion getAverageübergeben wird.


110Outline

GradeBook.cpp

(4 von 4)

93 94 // return bar chart displaying grade distribution as a string 95 string GradeBook::barChart() const 96 { 97 stringstream chartStream; // write bar chart as text in here 98 chartStream << "\nOverall grade distribution:" << endl; 99 // stores frequency of grades in each range of 10 grades 100 const size_t frequencySize = 11; 101 array< unsigned int, frequencySize > frequency = { 0 }; // init to all 0s 102 // for each grade, increment the appropriate frequency 103 for( const auto& student : grades ) 104 for( const auto& test : student ) 105 ++frequency[ test / 10 ]; 106 // for each grade frequency, write bar in chart 107 for( size_t count = 0; count < frequencySize; ++count ) { 108 // write bar label ("0-9:", ..., "90-99:", "100:" ) 109 if( 0 == count) 110 chartStream << " 0-9: "; 111 else if( 10 == count) 112 chartStream << " 100: "; 113 else 114 chartStream << count * 10 << "-" << ( count * 10 ) + 9 << ": "; 115 // write bar of asterisks 116 for( unsigned int stars = 0; stars < frequency[ count ]; ++stars ) 117 chartStream << '*'; 118 chartStream << endl; // start a new line of output 119 } // end outer for 120 return chartStream.str(); // return bar chart as a string 121 } // end function barChart

Berechnung der Verteilung aller Studentennoten


111 1 // Fig. 7.34: fig07_34.cpp

2 // Creates GradeBook object using a two-dimensional array of grades.

3 #include <array> 4 #include <iostream>


6

7 #include "GradeBook.h" // GradeBook definition

8 9 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 }; 23 24 GradeBook myGradeBook( 25 "CS101 Introduction to C++ Programming", grades ); 26 cout << myGradeBook.message(); 27 cout << myGradeBook.gradesContents(); 28 cout << "\nLowest grade is " << myGradeBook.getMinimum() 29 << "\nHighest grade is " << myGradeBook.getMaximum() << endl; 30 cout << myGradeBook.barChart(); 31 } // end main

Outline

fig07_34.cpp

(1 von 2)

Deklaration von gradesals 3-mal-10 Array

Jede Zeile entspricht einem Studenten; jede Spalte entspricht einer Prüfung


112Outline

fig07_34.cpp

(2 von 2)

Welcome to the grade book for CS101 Introduction to C++ Programming! The grades are: Test 1 Test 2 Test 3 Average

Student 1 87 96 70 84.33 Student 2 68 87 90 81.67 Student 3 94 100 90 94.67 Student 4 100 81 82 87.67 Student 5 83 65 85 77.67 Student 6 78 87 65 76.67 Student 7 85 75 83 81.00 Student 8 91 94 100 95.00 Student 9 76 72 84 77.33 Student 10 87 93 73 84.33 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: ***

Documents

arrays und vectors, Suchen und Sortieren - fbi.h-da.de · PDF file2006 Pearson Education, Inc. All rights reserved. 1 7 arrays und vectors, Suchen und Sortieren