Licence Informatique - Université de Bordeaux

Nous supposerons que les tableaux ont déjà été vus et utilisés dans un cadre de programmation. Pré-requis : le cours d'algorithmique et programmation suivi en L1

Un tableau est un type concret (par opposition à type abstrait), puisqu'on précise comment les éléments sont physiquement stockés. Dans la plupart des langages, les éléments d'un tableau sont indexés à partir de 0. Ainsi, le premier élément d'un tableau T est T[0], le second est T[1], etc. Avec cette convention de numérotation (le premier élément a l'indice 0), l'indice le plus grand dans le tableau est donc len(T) - 1 où len désigne la longueur d'un tableau T.

L'accès aux éléments s'effectue directement par l'indice, pour accéder à l’élément d’indice i on écrit T[i]. Le temps de calcul pour accéder à un élément du tableau est constant.

La définition et l'utilisation des tableaux varient d'un langage à l'autre, selon que les langages sont typés ou non, par exemple. Ainsi, en C, un tableau contient des éléments de même type – celui que l'on déclare lorsqu'on introduit le tableau. Vous en apprendrez plus sur les tableaux en C dans le cours de programmation C.

ex_tableau.c

#include <stdio.h>
#include <stdlib.h>
 
int main() {
	int tab[10];
 
	for(int i = 0; i < 10; ++i) {
		tab[i] = (i+1)*2;
	}
 
	printf("Le tableau contient les 10 premiers nombres pairs: \n");
	for(int i = 0; i < 10; ++i) {
		printf("%d ", tab[i]);
	}
	printf("\n");
 
	return EXIT_SUCCESS;
}

Ce code utilise un tableau d'entiers de taille 10. On introduit les premiers 10 nombres pairs dans l'ordre croissante et on restitue le contenu du tableau. Vous en apprendrez plus (en cours de programmation) sur la fonction main, sur la déclaration de variables, sur la fonction printf ou sur la formulation des boucles.

On compile ce code à l'aide de la commande gcc -std=c99 -Wall ex_tableau.c -o ex_tableau. On l'exécute ensuite depuis le même répertoire avec la commande ./ex_tableau.

Soit T un tableau d'entiers de taille N.

1. Proposez un algorithme qui décale d'une case vers la droite les entrées du tableau T à partir de la position k. Par exemple si T =[b,o,n,j,o,u,r], N=7 et k=3 le décalage donnera T=[b,o,n,j,j,o,u].
   • Remarques : On ne se soucie pas ici du fait que la valeur T[k] sera égale à la valeur T[k+1].On ne se soucie pas non plus d'avoir en quelque sorte perdu l'entrée T[N-1] initiale.
2. Dans quel cas l'algorithme de décalage peut-il être utilisé ?

Soient deux tableaux d'entiers T, T' de taille N, N' respectivement, qu'on supposera triés par ordre croissant. On souhaite obtenir un nouveau tableau T“ de taille N + N' contenant les entrées des tableaux T et T', triées dans l'ordre croissant aussi.

• Considérons un algorithme (pas très rusé) qui débute par recopier le tableau T au début de T”, puis insère une à une les entrées de T'
  • A chaque fois, on recherchera à partir du début de T“ l'endroit où l'entrée T'[i] doit être insérée dans T”, puis on décale les entrées au besoin.

• Considérons maintenant un algorithme plus malin, qui ajoute dans T“ à la position courante, soit une entrée de T, soit une entrée de T'
  • On tiendra à jour des indices i et i' indiquant le prochain élément de T et T' à ajouter à T”
  • On détermine qui de T[i] ou T'[i'] doit être inséré dans T“
  • On l'insère et on incrémente la position i'' où doit être inséré le prochain élément dans T”
  • On met à jour i ou i'

Avant de commencer: http://dept-info.labri.fr/ENSEIGNEMENT/algoprog/DocumentsMemoTp/MemoTP.pdf

Le programme suivant est à compléter pour les exercices qui suivent. Il vous permet également de tester vos fonctions.

test_tableaux.c

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>
 
#define N 10
#define N1 5
#define N2 10
 
bool rechercheElem (int tab[], int elem) {
    bool trouve = false;
    // TO DO
    return trouve;
}
 
void decaleTab (int tab[], int k, int n) {
    // TO DO
}
 
void fusionNaive (int tab1[], int tab2[], int newTab[]) {
    // TO DO
}
 
void fusionMaligne (int tab1[], int tab2[], int newTab[]) {
    // TO DO
}
 
int main() {
    int tab[N];
    int elem1, elem2;
 
    srand(time(NULL));    
 
    for(int i = 0; i < N; ++i) {
	tab[i] = rand()%100;
    }
    elem1 = tab[N-1];
    elem2 = 100;
 
    printf("Le tableau tab a ete initialise avec: \n");
    for(int i = 0; i < N; ++i) {
        printf("%d ", tab[i]);
    }
    printf("\n");
 
    printf("L'element %d se trouve dans le tableau tab. Est-ce le cas?\n", elem1);
    if ( rechercheElem(tab, elem1))
        printf ("vrai\n");
    else
        printf ("faux\n");
 
    printf("L'element %d ne se trouve pas dans le tableau tab. Est-ce le cas?\n", elem2);
    if ( !rechercheElem(tab, elem2))
        printf ("vrai\n");
    else
        printf ("faux\n");
 
    decaleTab(tab, 5, N);
    printf("Le tableau tab obtenu apres le decalage à partir de la position 5 est: \n");
    for(int i = 0; i < N; ++i) {
        printf("%d ", tab[i]);
    }
    printf("\n");
 
    int newN = N1 + N2;
    int tab1[N1], tab2[N2], newTab[newN];
 
    for(int i = 0; i < N1; ++i) {
        tab1[i] = i * 3;
    }
 
    printf("Le tableau tab1 a ete initialise avec: \n");
    for(int i = 0; i < N1; ++i) {
        printf("%d ", tab1[i]);
    }
    printf("\n");
 
    for(int i = 0; i < N2; ++i) {
        tab2[i] = i;
    }
 
    printf("Le tableau tab2 a ete initialise avec: \n");
    for(int i = 0; i < N2; ++i) {
        printf("%d ", tab2[i]);
    }
    printf("\n");
 
    for(int i = 0; i < newN; ++i) {
        newTab[i] = 0;
    }
    fusionNaive(tab1, tab2, newTab);
    printf("Le tableau newTab apres la fusion de tab1 et tab2 avec l'algo naif: \n");
    for(int i = 0; i < newN; ++i) {
        printf("%d ", newTab[i]);
    }
    printf("\n");
 
    for(int i = 0; i < newN; ++i) {
        newTab[i] = 0;
    }
    fusionMaligne(tab1, tab2, newTab);
    printf("Le tableau newTab apres la fusion de tab1 et tab2 avec l'algo malin: \n");
    for(int i = 0; i < newN; ++i) {
        printf("%d ", newTab[i]);
    }
    printf("\n");
 
    return EXIT_SUCCESS;
}

• Ecrivez la fonction rechercheElem qui recherche si un élément donné elem est présent dans un tableau tab.

• Écrivez la fonction decaleTab qui implémente l'algorithme décrit dans l'exercice 1.

• Écrivez les fonctions fusionNaive et fusionMaligne qui implémentent les algorithmes décrits dans l'exercice 2.