Tableaux à deux dimensions

Tableaux à deux dimensions#

Motivation : Le jeu de morpion#

On voudrait modéliser le plateau d’un jeu de morpion :

XO
XXX
OO

C’est comme un tableau, mais à deux dimensions: numéro de ligne, numéro de colonne

012
0XO
1XXX
2 OO

Comment modéliser un plateau de morpion en C++?#

  • modéliser une case : un entier : int

    • 0 : pas de pion

    • 1 : pion joueur 1 : X

    • 2 : pion joueur 2 : O

int c = 2;

  • modéliser une ligne : un tableau d’entiers : vector<int>

#include <vector> 
using namespace std;
012
0XO
vector<int> ligne0 = { 1, 2, 0 };
012
1XXX
vector<int> ligne1 = { 1, 1, 1 };
012
2 OO
vector<int> ligne2 = { 0, 2, 2 };

  • modéliser le plateau : un tableau de tableaux : vector<vector<int>>

vector<vector<int>>  plateau = { ligne0, ligne1, ligne2 };

plateau

En version courte :

vector<vector<int>> plateau = {
    { 1, 2, 0 },
    { 1, 1, 1 },
    { 0, 2, 2 },
};

Utilisation du tableau de Morpion#

#include <iostream>

Accès par indices de ligne et de colonne :

for ( int i = 0; i < plateau.size(); i++ ) {
    for ( int j = 0; j < plateau[i].size(); j++ ) {
        if      ( plateau[i][j] == 1 ) cout << "X ";
        else if ( plateau[i][j] == 2 ) cout << "O ";
        else                           cout << "  ";
    }
    cout << endl;
}

Avec une boucle «pour tout» :

for ( auto ligne: plateau ) {
    for ( auto c: ligne ) {
        if      ( c == 1 ) cout << "X ";
        else if ( c == 2 ) cout << "O ";
        else               cout << "  ";
    }
    cout << endl;
}

Construction d’un tableau à deux dimensions#

#include <vector>
using namespace std;

En une seule étape :

vector<vector<int>> plateau = {
    { 1, 2, 0 },
    { 1, 1, 1 },
    { 0, 2, 2 },
};

Construction d’un tableau étape par étape :

  • Déclaration :

vector<vector<int>> plateau;

  • Allocation :

plateau = vector<vector<int>>(3);

  • Allocation des sous-tableaux :

for ( int i = 0; i < plateau.size(); i++ )
    plateau[i] = vector<int>(3);

  • Initialisation :

plateau[0][0] = 1; plateau[0][1] = 2; plateau[0][2] = 0;
plateau[1][0] = 1; plateau[1][1] = 1; plateau[1][2] = 1;
plateau[2][0] = 0; plateau[2][1] = 2; plateau[2][2] = 2;

Que se passe-t’il en mémoire?#

  1. État initial

    état initial de la pile et du tas

  1. Déclaration du tableau

    pile et tas après la déclaration

  1. Allocation du tableau

    pile et tas après l'allocation

  1. Allocation des sous-tableaux

    pile et tas après l'allocation des sous tableaux

  1. Initialisation

    pile et tas après l'initialisation

Tableaux à deux dimensions : résumé#

  • On modélise un tableau à deux dimensions par un tableau de tableaux : vector<vector<...>>

  • t[i][j]: la case \(t_{i,j}\) du tableau d’indice de ligne \(i\) et d’indice de colonne \(j\).
    (on aurait pu prendre l’autre convention)

  • Un tableau à deux dimension se construit en quatre étapes :

    1. Déclaration du tableau

    2. Allocation du tableau

    3. Allocation des sous-tableaux

    4. Initialisation

Contenu