Discussion :

[mido1951]

bonsoir,
j'ai une question s'il vous plait: est-ce que je peux créer un tableau dynamique en C.c'est à dire créer un tableau avec une taille varie au cours du programme??
merci pour votre aide.

[Invité]

Bonsoir,


tableau dynamique en C

[gangsoleil]

bonsoir,
j'ai une question s'il vous plait: est-ce que je peux créer un tableau dynamique en C.c'est à dire créer un tableau avec une taille varie au cours du programme??
merci pour votre aide.

Oui, bien sur, c'est possible.

Par contre, ce n'est pas "trivial", et un minimum de connaissances du langage sont necessaires. Je te conseille donc la lecture de tutoriels sur le C

[ternel]

En bref résumé.
il n'y a pas de comportement réellement automatique en C.

Pour le besoin d'un ensemble cohérent de valeurs (un tableau), tu as plusieurs situations, chacune avec sa solution.

1. Tu connais une taille maximale de l'ensemble, et elle sera atteinte au moins une fois.
2. L'ensemble ne change pas souvent de taille, mais cette taille est arbitraire.
3. La taille de l'ensemble change fréquemment, et la taille connait de grande variation

1) Taille bornée, mais variable.
Un tableau fixe, une constante de taille maximale, et une taille actuelle suffisent.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
const int TailleMax = 17;
int taille = 0;
int tableau[TailleMax];

2) Une taille arbitraire, mais constante (par morceaux, comme dirait les matheux…).
Ici, un pointeur et une taille devrait correspondre:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
int* tableau = NULL;//ou 0 selon ta manière de traiter ce sujet polémique
int taille = 0;

il faudra alors utiliser malloc, free et realloc pour respectivement créer le tableau, le supprimer et le retailler.

3) L'ajout ou la suppression du tableau sont une opération fréquente.
La, il te faut tout autre chose, un tableau ne convient pas vraiment.
Il te faut une liste chainée (doublement ou pas)
le modèle général est le suivant:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
typedef struct intChainon {
    int valeur;
    struct intChainon * suivant;
    struct intChainon * précédent;//si le doublement chainé.
} intChainon_t;
 
//si doublement chainé, tu peux avoir aussi:
struct intChaine{
struct intChainon * premier;
struct intChainon * dernier;
}

Il convient alors de créer des fonctions pour:

• savoir si la liste est vide
• vider une liste (généralement, vider(intChainon**liste) { while(!estVide(*liste)) supprimerPremier(*liste); *liste=null;})
• ajouter un élément au début (malloc)
• ajouter un élément en fin (malloc)
• supprimer le premier élément (free)
• supprimer le dernier élément (free)

Il y a d'autres possibilités, mais celles-ci sont les plus courantes.
En général, les autres solutions font appels à ces concepts.

[I_believe_in_code]

Dans une série de vidéos de cours, j'ai montré une manière de créer un type de donnée "tableau redimensionnable". Ce type de tableau a une taille allouée (qui peut être augmentée en cas de besoin) et une taille utilisée (inférieure ou égale à la taille allouée, selon la quantité de données effectivement stockées).

Dès qu'on souhaite écrire une donnée dans une case située au-delà de la taille allouée, celle-ci est agrandie suffisamment pour que l'opération soit possible (et même deux fois plus).

Les deux vidéos suivantes parlent exactement de cela :





Trois remarques :

1- il s'agit d'une implémentation naïve, c'est à dire ni la plus performante ni la plus joliment codée. La raison est que c'est un cours réservé à des débutants et que je n'ai utilisé que des choses que nous avions déjà vues dans les cours précédents.

2- les vidéos montrent comment faire cela sur des tableaux d'int. Bien sûr la méthode est généralisable, et, idéalement, il vaudrait mieux des tableaux de void* plus réutilisables (mais c'est un cours pour les débutants, je le répète)

3- si ton bagage sur le langage C, voire sur la programmation en général est faible, tu risques aussi d'avoir besoin de suivre certains des cours précédents.

En particulier :

- sur les pointeurs :


- sur l'allocation dynamique :


- sur les struct :

[AceSir]

Il reste encore une dernière solution par rapport à ce qu'a dis leternel : un arbre binaire de recherche. Mais ça demande bien plus de travail, et cela dépend de ce que tu veux faire de ton tableau

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
typedef struct _abin {
  [type] value; // Où type désigne... le type !
  struct _abin* sag; // Le sous arbre gauche.
  struct _abin* sad // Le sous arbre droit.
} *abin;

[Médinoc]

Wow, c'est un cours très intéressant.

Ce qui est regrettable, c'est qu'il y a des informations voisines qui ne peuvent pas vraiment être abordées dans un tel cours (elles n'apporteraient que confusion), notamment le problème du nombre d'or qui empêche de réutiliser la mémoire libérée quand on double la longueur du tableau à chaque fois.

vPersonnellement, j'utilise racine de 2, mais en trichant un peu pour être sur que deux agrandissements multiplient bien par 2 et non pas 1.999...

[ternel]

Merci!
Je connaissais le fait que 1,5 soit un bon ratio, mais pas la raison.

[diogene]

En fait, on a intérêt à avoir un facteur de croissance inférieur au nombre d'or si on veut que le mécanisme de récupération évoqué dans le post signalé par Médinoc puisse fonctionner :

On cherche à allouer successivement 1, puis k puis k^2, k^3,...k^n (k>1)
Si on veut que le critère fonctionne pour l'allocation k^n, (n>=3) il faut avoir

       k^n <= Sn = 1+k+k^2+..k^(n-2)
soit   k^n <= (k^(n-1)-1)/(k-1)
       k^(n+1) - k^n - k^(n-1)+ 1 <=0
ou     k^2 - k -1 + 1/(k^(n-1))<=0

Soit n0, la plus petite valeur de n (si elle existe), qui, pour un k donné, satisfait ce critère. Alors, il sera également satisfait pour n>n0
Si on admet vouloir cette condition pour n0 très grand, k^(n0-1)>>1 , k tend vers le nombre d'or, racine de k^2-k-1 =0. Mais si on veut que ce critère soit satisfait pour des valeurs petites de n0, il faut diminuer k.
Ainsi,

n0     3        4       5       6      10    ... 
k<=  1.3247   1.465   1.534   1.57    1.61         1.618

Par exemple,

k = 1.5
n =    0     1        2       3        4        5
k^n    1    1.5      2.25   3.375    5.0625   7.5938
Sn     -     -        -      2.5      4.75     8.125
k = 1.414
n =    0     1        2       3         4        5
k^n    1   1.414      2     2.818       4      5.6569                                   
Sn     -     -        -     2.414     4.414    7.2426
k = 1.3247
n =    0     1        2       3        4     
k^n    1   1.3247  1.7548   2.3246   3.0794
Sn     -     -        -     2.3247   4.0795