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
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 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.
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
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.
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
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.
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
• 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 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.
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 ).
• 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.
16
Falls mehr Initialisierungswerte angegeben
werden als Elemente im Array vorhanden
sind, führt dies zu einer Fehlermeldung des
Compilers.
1
// Fig. 7.4: fig07_04.cpp
2
// Initializing an array in a declaration.
3
#include <iostream>
4
#include <iomanip>
5
#include <array>
6
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
14
15
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
18
• 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.
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
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
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
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.
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'
23
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) .
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.
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 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.
1
// Fig. 7.8: fig07_08.cpp
2
// Compute the sum of the elements of an array.
3
#include <iostream>
4
#include <array>
5
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
28
• 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.
1
// Fig. 7.9: fig07_09.cpp
2
// Bar chart printing program.
3
#include <iostream>
4
#include <iomanip>
5
#include <array>
6
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
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)
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 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.
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
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
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
Face
1
2
3
4
5
6
Frequency
1000167
1000149
1000152
998748
999626
1001158
Outline
33
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.
1
// Fig. 7.11: fig07_11.cpp
2
// Student poll program.
3
#include <iostream>
4
#include <iomanip>
5
#include <array>
6
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
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
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)
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.
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 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.
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 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).
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 arrayelements als Argument verwendet werden.
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
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
}
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
}
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
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
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.
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
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
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
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
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
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
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
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
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
++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
1
// Fig. 7.18: fig07_18.cpp
2
// Creates GradeBook object using an array of grades.
3
#include <iostream>
4
#include <array>
5
fig07_18.cpp
6
7
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
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: *
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.
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!
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
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;
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
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 }
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
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
60
• Ü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)
61
• Ü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
62
• 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
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
1
// Fig. 7.20: fig07_20.cpp
2
// Linear search of an array.
3
#include <iostream>
4
#include <array>
5
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
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
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
67
7.8.1 Lineare Suche
– 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.
68
7.8.1 Lineare Suche
– Lineare Laufzeit
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
69
7.8.1 Lineare Suche
– Quadratische Laufzeit
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
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.
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.
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.
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.
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
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
21 // perform a binary search on the data
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
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
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;
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
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)
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.
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
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.
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.
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.
82
• 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...
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
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
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
85
• 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.
86
• 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.
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.
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.
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.
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
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
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
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
30
Outline
31 // recursive function to sort (sub)vectors
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
57
Outline
58 // merge two sorted subvectors into one sorted subvector
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
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
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
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
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
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
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)
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.
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.
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.
101
Fig.7.30 | Zweidimensionales Array mit drei Zeilen (rows) und vier Spalten (columns).
102
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).
103
• 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).
1
// Fig. 7.31: fig07_31.cpp
2
// Initializing multidimensional arrays.
3
#include <iostream>
4
#include <array>
5
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
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
1 2 3
4 5 0
1 2 3
0 0 0
106
• 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;
}
}
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.
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
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
8
9
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
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
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
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
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
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
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
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
6
7
fig07_34.cpp
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
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: ***

arrays und vectors,

Transcrição

Documentos relacionados

Prozedurale Programmierung (PPG)

sparen! - Lichtburg Essen

Wir suchen Dich! Azubi zum Industriemechaniker (m/w)

modified mags

Arrays: Der Standard C++ Typ (class) vector

PDF 256 KB - Johannes Anders

Urolift Praesentation

07 Funktionen (Teil I) - NKSA-Binf

Checkliste zum 2. Videokurs - Malen lernen mit Acryl

PHAsis®one – Phased Array Spotweld Inspection System