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.
#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 premiers 10 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.
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.
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.
#include <stdio.h> #include <stdlib.h> #include <stdbool.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) { // 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; 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); 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 + N; 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; }