Comment créer un tableau vide en C (sans structure)

Bonjour,

Si code_char.code était un int * une manière de s'en sortir serait de représenter le tableau vide par NULL. Puis, lorsque tu as besoin d'accéder à code_char.code, tu commences par vérifier si cette adresse n'est pas NULL. Si c'est le cas et que tu veux corriger la valeur de code_char.code il faut juste faire une allocation dynamique.

Dans ton cas, le fait que code_char soit un int[256] fait que quoi qu'il arrive, ce tableau est un bloc mémoire et sa taille réelle est 256*sizeof(int). Si tu veux une notion de taille effective, il faut donc la stocker à part. Dans ton code, c'est le rôle code_char.lg : comme cette valeur stocke la taille effective de code_char.code, pourquoi ne pas simplement la mettre à 0 dans le cas où le code correspond à la chaîne vide ? Car dans les faits, quelle que soit la longueur effective de code_char.code, vu qu'il s'agit un int[256], en mémoire cela engendrera toujours un tableau de 256 ints.

Par rapport à la question initiale, comme le dit Pierrot, dans ses messages #18, il n'y a pas de notion de tableau vide en C contrairement au C++ ou au python. Je vais même aller plus loin, en vrai de vrai il n'y a réellement de notion de tableau native au langage C (à moins de définir sa propre structure). Il y a uniquement une notion de bloc mémoire. L'algèbre des pointeur fait qu'on peut indexer un bloc conformément à la taille du type pointé, et c'est ce qui définit l'opérateur [ ]. Car en réalité :

tab[i] == *(tab + i)

... où tab correspond à l'adresse du bloc. Le décalage de i "cases" dépend du type pointé. Par exemple, si tab est de type int *, alors le type pointé est int, et donc la i-ème "case" est i * sizeof(int) octets après l'adresse tab, comme le met en évidence le programme suivant :

#include <stdio.h>
#include <stdlib.h>

int main() {
    int * tab = malloc(10 * sizeof(int));
    size_t i = 1;
    printf("tab                           = %p i = %zu\n", tab, i);
    printf("tab[i]                        = %p\n", &tab[i]);
    printf("tab + i                       = %p\n", tab + i);
    printf("((int) tab) + i * sizeof(int) = %p\n", ((long) tab) + i * sizeof(int));
    free(tab);
    return 0;
}

(mando@silk) (~) $ gcc toto.c && ./a.out 
tab                           = 0x55de759dc2a0 i = 1
tab[i]                        = 0x55de759dc2a4
tab + i                       = 0x55de759dc2a4
((int) tab) + i * sizeof(int) = 0x55de759dc2a4

On comprend donc que l'opérateur [ ] n'est qu'un jeu d'écriture qui jongle avec les pointeurs en arrière-boutique, et qu'il n'y a pas de notion de tableau à proprement parler.

Bonne chance

Pourrais-tu expliquer ce que tu veux en faire? Parce que je ne vois pas l'utilité à priori.
Et "vide", ça veut dire que sa longueur est 0, ou que tu ne veux rien y mettre en partant ?

C'est possible de faire  int tab[0];  mais ça n'est pas ISO.

Oui je veux que sa taille soit égale à 0 

Rien en partant, exact.

Comment vas-tu y ajouter des éléments?
Ce n'est pas comme Python où on peut faire des append, ou bien c++ où on peut faire des push_back

Je viens de tester, on peut faire des malloc de longueur 0, quitte à faire des realloc.

Mais c'est plus que douteux comme façon de faire ...

Je vais vous expliquer le contexte sinon vous n'allez pas comprendre. Je dois faire un exercice sur les arbres de Huffman (je ne sais pas si vous connaissez)

On m'a demandé d'écrire une fonction qui me permet d'avoir le code de chaque caractère et sa longueur

Exemple:

Le codage sera :

• C: 000
• B: 001
• D: 1100
• ...

J'ai une fonction ConstruireCode dont le prototype est :

void ConstruireCode(Arbre huff) {
  
}
typedef unsigned char Element;

struct cellule {
    Element etiq;
    struct cellule *fd;
    struct cellule *fg;
};

typedef struct cellule *Arbre;
struct code_char {
    int lg;
    int code[256]; /* ne contient que des 0 ou des 1 */
};

struct code_char tab;

• tab[i] contient le code du caractere de code ASCII i
• tab[i].lg contient la longueur du code (exemple pour B: code de longueur 3)
• tab[i].code contient le code du caractère (comme dans mon exemple B=001)

Pourquoi j'ai posé la question tableau vide?

Pour calculer le code d'une lettre, on a besoin de parcourir de la racine à la feuille. Le côté gauche de l'arbre n'a que des 0 et le côté droit que des 1.

Je veux écrire la fonction récursivement, il me faut donc un cas de base, ce qui donne à peu près ceci :

void ConstruireCode(Arbre huff) {
  if Estfeuille(huff)
     tab[i].code=creer_un_tableau_vide
   else
      //ConstruireCode(Filgauche(huff))
       //ConstruireCode(Fildroit(huff))


}

Dans ma solution, je n'ai pas encore trouvé le moyen de mettre que des 0 à gauche et que des 1 à droite.

J'ai donc besoin de créer un tableau vide pour traiter mon cas de base.

Si un arbre est réduit à une feuille (1 nœud), il ne doit pas avoir de code, donc il faut que j'ai un tableau vide pour dire juste qu'il y a rien.

Exemple en Python:

from __future__ import annotations
from typing import Dict
from heapq import heappush, heappop


class Noeud():
    """
    Noeud de l'arbre de Huffman. 
    """

    def __init__(self: Noeud,
                 valeur: int,
                 lettre: str = "",
                 filsG: Noeud = None,
                 filsD: Noeud = None) -> None:
        self.valeur = valeur
        self.lettre = lettre
        self.filsG = filsG
        self.filsD = filsD

    def __lt__(self, n: Noeud):
        """
        Comparaison de deux noeuds = comparaison des valeurs
        """
        return self.valeur < n.valeur

def creation_codes_huffman(a: Noeud) -> Dict[str, str]:
    """
    Étant donné un arbre de Huffman retourne un dictionnaire dans lequel 
    les clés sont les chaînes binaires et les valeurs les caractères
    correspondants.

    Fonction enveloppe de la fonction codes_huffman_parcours.
    """
    dic = {}
    codes_huffman_parcours(a, dic, "")
    return dic


def codes_huffman_parcours(a: Noeud, dic: Dict[str, str], code: str) -> None:
    
    if est_feuille(a):
        dic[code] = a.lettre
    else:
        codes_huffman_parcours(a.filsG, dic, code + "0")
        codes_huffman_parcours(a.filsD, dic, code + "1")

Dans cette version Python, rien est symbolisé par "". Dans la version C, la structure qu'on m'a donnée, la structure code_char contient un tableau code avec le code du carctere. Donc par analogie, je pense avoir besoin à la place d'un tableau vide.

Dans la version Python rien est symbolisé par" " et moi vu la structure qu'on m'a donné code-char il ci=ontient un tableau code avec le code du carctere donc par analogie ici je dois avoir je pense un tableau vide

J'ai déjà fait un Huffman. J'avais fait un tableau des fréquences de 256 de long.
Chaque élément était un noeud et j'y accumulais la fréquence.

Je ne gardais que les éléments avec une fréquence non nulle et je triais en ordre descendant.
Je pense que je construisais l'arbre de façon itérative, mais ça se fait sans doute de façon récursive.
Il me semble que je construisais une table des codes avec la longueur de chacun, cette fois de façon récursive.

Oui c'est ça, mon exercice me demande de faire la table des codes

Exemple :

Huffman[97] = a
​​​​​​​Huffman[97].code = [0011]
Huffman[97].lg = 4

Du coup, est-ce que mon idée de créer un tableau vide est bonne ou pas ?

Si c'est le cas,comment en créer en C ?

Si vous lisez la version python (voir #6) vous comprendrez ce que je veux faire.

Comme je t'ai dit, j'ai créé ma table des codes à partir du tableau des fréquences. Ce tableau était formé de noeuds.
Donc, à la fin, je me retrouvais avec un arbre binaire avec une racine.
C'est à partir de ce point selon moi que tu vas créer ta table de codes de façon récursive.
Je peux toujours poster mon code.
Mais il ne sera pas coloré car je suis aveugle et j'utilise mon ordi avec une synthèse vocale.
Elle ne me donne pas accès à la barre des options.

Pour répondre à ta question, ce n'est pas une bonne idée que de partir avec un tableau vide.

Je ne sais pas si ça va marcher pour la mienne, mais en tout cas, moi aussi j'ai une table de fréquences.

Par exemple, si j'ai : bal alh

tab[97] = 2 // a
tab[98] = 1 // b
...

J'ai aussi une fonction init_huffman  qui me renvoie une file à priorite dont les elements sont des nœuds avec pour priorité leur fréquence. Pensez-vous que ça ressemble à votre tableau fréquence ?

Mais je suis curieux quand même, je voudrais bien voir votre code.

Voici mon code:

// Arbre de Huffman.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Node Node;
struct Node {
    Node *left;
    Node *right;
    int occur;
    char code;
};
typedef struct Bits Bits;
struct Bits {
    unsigned char number;
    unsigned char bits;
};
void *getArea(char *name, int size) {
    void *area = malloc(size);
    if(area) return area;
    perror(name);
    printf("Required: %d\n", size);
    exit(EXIT_FAILURE);
}
Node *getNode(char symbol) {
    Node *node = getArea("getNode", sizeof(Node));
    node->left = NULL;
    node->right = NULL;
    node->occur = 0;
    node->code = symbol;
    return node;
}
void setTree(Node *node, Bits convert[], Bits bits, int level) {
    if(node->left) {   // pas une feuille
    bits.number++;
    setTree(node->right, convert, bits, level+1);
    bits.bits |= 1<<level;
    setTree(node->left, convert, bits, level+1);
} else {
    convert[node->code] = bits;
}
}
int compare(const void *freq1, const void *freq2) {
    int cmp =(*((Node **)freq2))->occur - (*((Node **)freq1))->occur;
    if(cmp != 0) return cmp;
    return ( *((Node **)freq1))->code - (*((Node **)freq2))->code;
}
void freeTree(Node *node) {
    if(node->left) freeTree(node->left);
    if(node->right) freeTree(node->right);
    free(node);
}
int main(void) {
    Node **frequency = getArea("frequency", sizeof(Node *) * 256);
    unsigned char texte[] = "this is an example of a huffman tree";
    for(int i=0; i < 256; i++) frequency[i] = NULL;
    // Augmenter les occurences.
    for(int i=0; texte[i]; i++) {
        char code = texte[i];
        if(frequency[code] == NULL) frequency[code] = getNode(code);
        frequency[code]->occur++;
    }
    // Ne garder que s'il y a au moins une occurence.
    int count = 0;
    for(int i=0; i < 256; i++)
        if(frequency[i])
            frequency[count++] = frequency[i];
    // Tri des fréquences en ordre descendant.
    qsort(frequency, count, sizeof(Node **), compare);
    // Construire l'arbre à partir des noeuds.
    Node *newNode;
    int rest = count;
    while(rest > 1) {
        newNode = getNode('\0');
        newNode->left = frequency[rest-2];
        newNode->right = frequency[rest-1];
        newNode->occur = frequency[rest-2]->occur + frequency[rest-1]->occur;
        rest -= 2;
        // Remonter le noeud dans le tableau
        int i;
        for(i=rest; i>0 && newNode->occur > frequency[i-1]->occur; i--) frequency[i] = frequency[i-1];
        frequency[i] = newNode;
        rest++;
    }
    free(frequency);
    Bits *convert = getArea("convert", sizeof(Bits) * 256);
    Bits bits;
    bits.number=0;
    bits.bits=0;
    for(int i=0; i<256; i++) convert[i] = bits;
    setTree(newNode, convert, bits, 0);
    unsigned char *memory = getArea("memory", strlen(texte)*8);   // === revoir
    int in =  0;
    // parcourir le texte et le convertir
    for(int i=0; texte[i]; i++) {
        char code =texte[i];
        for(int s=0; s < convert[code].number; s++) {
            memory[in++] = (convert[code].bits >> s) & 1;
        }
    }
    free(convert);
    // décoder le fichier
    printf("%d bits\n", in);
    int out = 0;
    int acc = 0;
    Node *node = newNode;
    while(out < in) {
        if(node->left == NULL) {
            memory[acc++] = node->code;
            node = newNode;
        }
        if(memory[out++])
        node = node->left;
        else
        node = node->right;
    }
    memory[acc++]=node->code;
    memory[acc]='\0';
    // afficher le résultat
    printf("\n%s\n", memory);
    free(memory);
    freeTree(newNode);
    return 0;
}

J'ai tout lu, mais je ne vois pas à partir de quel moment vous calculez le code des caractères.

Je le fais dans la fonction setTree avec le tableau convert. La fonction setTree est récursive.

D'accord merci. J'ai regardé, je pense que c'est très different de la signature de mes fonctions et de mes structures, mais merci.

Revenons à mon problème initial. Je veux juste savoir comment créer un tableau vide.

Exemple:

struct tableau{
   int *tab;
   int taille;
}

void creer_tableau_vide(){
   tableau t;
    t.taille = 0;
}

Comment faire sans utiliser struct tableau ??

Ce que tu veux faire sans structure est impossible en C. En C++, j'utiliserais les std::vector
et tu sais comment faire en Python.
Dans ton exemple, tu ne retournes pas la structure à la fonction appelante.

d'accord je comprends mieux merci