Das Array

Beispiel Bubblesort

Anschaulich

Schauen und tauschen

Sie sehen, dass sich die Zahlen bereits im ersten Durchlauf dahingehend geändert haben, dass nun die höchste Zahl nach rechts gewandert ist. Alle anderen Zahlen sind noch unsortiert, so dass der Vorgang wiederholt werden muss. Im nächsten Schritt müssen allerdings nur noch die ersten drei Karten bearbeitet werden, weil die höchste Karte ja bereits an der richtigen Position liegt. Auch im zweiten Durchgang wandert die höchste der verbleibenden Karten nach rechts. Zu guter Letzt müssen nur noch die ersten beiden Karten getauscht werden.

Umsetzung

for (i=MAX-1; i>0; i--)
{
    for (j=0; j<i; j++)
    {
        ...
    }
}

Die im Buch erscheinende Grafik Struktogramm Bubblesort (bubblediagramm) fehlt hier.

Nun muss das Struktogramm nur noch in C++-Code umgesetzt werden. Das folgende Listing zeigt das Programm inklusive der Erzeugung von zufälligen Testdaten und der Bildschirmausgaben.

#include <iostream>
using namespace std;
#include <stdlib.h>

const int MAX=5;

int main()
{
    int feld[MAX], hilf;
    int i, j, k;

    srand(56); // Zufallsgenerator vorbereiten
    for (i=0; i<MAX; i++)
    { // Array besetzen und anzeigen
        feld[i] = rand() % 100 + 1;
        cout << feld[i] << " ";
    }
    cout << endl;

    for(i=MAX-1; i>0; i--)
    {
        for (j=0; j<i; j++)
        {
            cout << "(" << j << "-" << j+1 << "): " ;
            if (feld[j]>feld[j+1])
            { // Tauschen erforderlich
                hilf = feld[j];
                feld[j] = feld[j+1];
                feld[j+1] = hilf;
            }
            cout << feld[j] << " - " << feld[j+1] << "  ";
        }
        // Zeige das Array in diesem Durchlauf
        cout << endl << MAX-i << ". Durchlauf beendet: ";
        for (k=0; k<MAX; k++)
        {
            cout << feld[k] << " ";
        }
        cout << endl;
    }

}

Bildschirmausgabe

80 91 14 78 17
(0-1): 80 - 91  (1-2): 14 - 91  (2-3): 78 - 91  (3-4): 17 - 91
1. Durchlauf beendet: 80 14 78 17 91
(0-1): 14 - 80  (1-2): 78 - 80  (2-3): 17 - 80
2. Durchlauf beendet: 14 78 17 80 91
(0-1): 14 - 78  (1-2): 17 - 78
3. Durchlauf beendet: 14 17 78 80 91
(0-1): 14 - 17
4. Durchlauf beendet: 14 17 78 80 91

Übung

• Ergänzen Sie das Lottoprogramm um den Bubblesort in der Weise, dass die Lottozahlen immer aufsteigend angezeigt werden.
• Das Bubblesort-Programm kann noch optimiert werden. Wurde nämlich in einem Durchlauf von links nach rechts nicht getauscht, dann waren die Zahlen offensichtlich in der richtigen Reihenfolge und es ist nicht nötig, weitere Sortierläufe durchzuführen.

Zuweisung von Arrays

Kein L-Value

#include <iostream>
using namespace std;
const int MAX=256;
int main()
{
    char input[MAX];
    int i=0;
    double Wert = 0;

    cin.getline(input, MAX);
    while (input[i]>='0' && input[i]<='9')
    {
        Wert *= 10;
        Wert += input[i] - '0';
        i++;
    }
    if (input[i]==',')
    {
        double NK = 1;
        i++;
        while (input[i]>='0' && input[i]<='9')
        {
            NK *= 10;
            Wert += (input[i]-'0')/NK;
            i++;
        }
    }
    cout << input << Wert << endl;
}

Übung

• Schreiben Sie ein Programm, das Brüche als Eingaben zulässt und sie in double-Variablen umrechnet. Der Nenner und der Zähler sollen durch einen Schrägstrich getrennt werden. Bei der Eingabe 3/4 sollte die Variable dann 0.75 enthalten.

Mehrere Dimensionen

Definition

double matrix[MAXSPALTEN][MAXZEILEN];

Zugriff

Beispiel: Bermuda

Spielanleitung

Spielfeld anzeigen

#include <iostream>
using namespace std;

const int X=9;
const int Y=7;

int main()
{
char Spielfeld[X][Y];
int x, y;
char cx, cy;


    for (x=0; x<X; x++)
    {
        for (y=0; y<Y; y++)
        {
            Spielfeld[x][y] = '.';
        }
    }
    // Anzeige und Eingabe
    bool SchleifenEnde=false;
    int xin, yin;
    do
    {
        cout << "      1  2  3  4  5  6  7  8  9" << endl;
        for (y=0; y<Y; y++)
        {
            cout << (char)('A'+y) << "   ";
            for (x=0; x<X; x++)
            {
                cout << "  " << Spielfeld[x][y];
            }
            cout << endl;
        }
        cin >> cx >> cy;
        xin = cx - '1';
        yin = cy - 'A';
        if (xin>=0 && xin<9 && yin>=0 && yin<7)
        {
            Spielfeld[xin][yin] = 'x';
        }
        else
        {
             SchleifenEnde = true;
        }
    }
    while (!SchleifenEnde);
}

     1  2  3  4  5  6  7  8  9
A    .  .  .  .  .  .  .  .  .
B    .  .  .  .  .  .  .  .  .
C    .  .  .  .  .  .  .  .  .
D    .  .  .  .  .  .  .  .  .
E    .  .  .  .  .  .  .  .  .
F    .  .  .  .  .  .  .  .  .
G    .  .  .  .  .  .  .  .  .
2C
     1  2  3  4  5  6  7  8  9
A    .  .  .  .  .  .  .  .  .
B    .  .  .  .  .  .  .  .  .
C    .  x  .  .  .  .  .  .  .
D    .  .  .  .  .  .  .  .  .
E    .  .  .  .  .  .  .  .  .
F    .  .  .  .  .  .  .  .  .
G    .  .  .  .  .  .  .  .  .
6F
     1  2  3  4  5  6  7  8  9
A    .  .  .  .  .  .  .  .  .
B    .  .  .  .  .  .  .  .  .
C    .  x  .  .  .  .  .  .  .
D    .  .  .  .  .  .  .  .  .
E    .  .  .  .  .  .  .  .  .
F    .  .  .  .  .  x  .  .  .
G    .  .  .  .  .  .  .  .  .
xx