Tableau de structures, structure de structures

Version imprimable

Bonsoir à tous,

J'ai besoin de créer un tableau de structures; jusque là tout va bien. Cette structure contient un char et un pointeur vers une structure du même type (c'est une pile)

Ce dont j'ai besoin c'est, après avoir généré ma pile, la parcourir.
L'idée est de lire le caractère contenu dans ma pile (elle même contenu dans un tableau), et de passer a l'élément suivant (ou précédent, vu que c'est une pile); et en faire de même tant que ce caractère n'est pas égal à -1.

Ci-joint le bout de code.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 typedef struct pile_s{ struct pile_s *prec; char bit; }pile; void ecrireCode(uchar *buffer, short *posBuffer, pile code[], uchar c, FILE *g) { pile a; a=code[(int)c]; while (a.bit!=-1) { *buffer=(*buffer>>1); // Décaler les bits vers la droite *buffer+= a.bit; // Écrire le nouveau bit *posBuffer+=1; a=*(a.prec); // Erreur de segmentation... if (*posBuffer==8) { fprintf(g,"%c",*buffer); *posBuffer=0; } } }
Des heures que je tourne en rond... J'espère que l'on me trouvera une erreur bête :]

Merci de vos réponses.

10/12/2012, 06h40
Neckara
Bonjour,
Citation:
Code:

1 2 3 4 void ecrireCode(uchar *buffer, short *posBuffer, pile code[], uchar c, FILE *g) { pile a; a=code[(int)c];
Pourquoi utiliser deux paramètres quand un seul suffit ?

Code:

void ecrireCode(uchar *buffer, short *posBuffer, pile * code, FILE *g)

De plus la variable a ne te sert à rien, autant utiliser un pointeur pour éviter la copie ( ici on a déjà un pointeur avec code) code = code->prec;.

Si tu veux stocker qu'un seul bit, pourquoi ne pas faire :
Code:

1 2 3 4 typedef struct pile_s{ struct pile_s *prec; unsigned bit:1; }pile;
Pour la condition de fin de ta pile, il suffira de mettre prec à NULL.

Il faut aussi faire attention avec char, suivant les compilateurs, il peut être équivalent à un unsigned char ou à un signed char.

Salut,

Pourquoi ne pas utiliser des noms simples à comprendre?

Code:

1
2
3
4
5
6
7
typedef struct PILE_S{
	struct PILE_S *prev;
	char value;
}PILE;
 
void push(char value, PILE* stack);
char* pop(PILE* stack);

A+

Pfeuh

P.S. Tu n'es pas obligé d'utiliser une liste chainée pour une pile. Si la taille max est raisonnable , tu peux très bien utiliser un tableau et un pointeur pour la balayer. Les piles des processeurs marchent comme cela. Je trouve, et ce n'est que mon avis, qu'une liste chainée pour une pile c'est dommage.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
 
#include <stdlib.h>
#include <assert.h>
 
typedef char STACK_DATA_TYPE;
 
typedef struct STACK_S
{
	int size;
	STACK_DATA_TYPE* data;
	int pointer;
}STACK;
 
STACK* createStack(int size);
int destroyStack(STACK* stack);
void push(char value, STACK* stack);
STACK_DATA_TYPE pop(STACK* stack);
 
STACK* createStack(int size)
{
    STACK* stack = malloc(sizeof(STACK));
    STACK_DATA_TYPE* data;
 
    if(stack != NULL)
    {
        data = malloc(sizeof(STACK_DATA_TYPE) * size);
        if(data == NULL)
        {
            free(stack);
            stack = NULL;
        }
        else
        {
            stack->size = size;
            stack->data = data;
            stack->pointer = 0;
        }
    }
    return stack;
}
 
int destroyStack(STACK* stack)
{
    free(stack->data);
    free(stack);
    return 0;
}
 
void push(STACK_DATA_TYPE value, STACK* stack)
{
    if(stack->pointer + 1 == stack->size)
        exit(1); /* stack overflow */
    stack->data[stack->pointer++] = value;
}
 
STACK_DATA_TYPE pop(STACK* stack)
{
    if(stack->pointer == 0)
        exit(2); /* empty stack */
    return stack->data[--stack->pointer];
}
 
int main(void)
{
    STACK* stack = createStack(256);
    if(stack == NULL)
        return -1;
 
    push(123, stack);
    push(-1, stack);
    push(-10, stack);
    push(7, stack);
    assert(pop(stack) == 7);
    assert(pop(stack) == -10);
    assert(pop(stack) == -1);
    assert(pop(stack) == 123);
    destroyStack(stack);
    return 0;
}

10/12/2012, 14h20
nuwanda03

Bonjour à tous,

Je viens de lire vos réponses. Instructives !

Pour le cas de la pile, j'essaie de minimiser la taille de chacune. Je suis en fait en train de faire un compresseur et décompresseur utilisant l'algorithme d'Huffman. Ce qui ferait que chaque pile, vue comme un tableau, m'allouerait 256 octets (taille maximale du code d'un caractère), et ce 256 fois (256 caractères différents) : soit 65536 octets. Donc légèrement trop à mon goût.

La formule magique de Neckara :

Code:

unsigned bit:1;

Je pensais que la plus petite structure de données que l'on pouvait utiliser était le char. Ça devrait me faire économiser un max de RAM, je dirai même jusqu'à 7 fois moins. (Y'a possibilité de créer un tableau de bits ??? Et dans le cas de la structure, il suffit d'écrire nomstruc.bit=0 pour mettre mon bit à zéro ?)

Pour revenir sur le code que je vous ai posté, il semble juste. Le compilateur ne me crie pas dessus du moins. C'est certainement à l'initialisation de ma pile que j'ai un problème. J'y reviendrai plus tard si je n'arrive toujours pas à trouver de solution; en attendant gardons le sujet propre.

Je vous tient au courant de mes résultats. Merci à vous.
10/12/2012, 14h34
diogene

Citation:

Je pensais que la plus petite structure de données que l'on pouvait utiliser était le char. Ça devrait me faire économiser un max de RAM, je dirai même jusqu'à 7 fois moins. (Y'a possibilité de créer un tableau de bits ??? Et dans le cas de la structure, il suffit d'écrire nomstruc.bit=0 pour mettre mon bit à zéro ?)

Tu pensais juste. Le compilateur allouera au minimum un char pour stocker les champ de bits, même si il n'y a qu'un bit.
Donc, tu ne gagneras rien en utilisant ici un champ de bits.

De plus, le compilateur, dans les deux cas, peut ajouter des bytes supplémentaires en queue de structure ou derrière une variable de ce type, pour des questions d'alignement des variables.
10/12/2012, 14h35
nuwanda03

Citation:

Envoyé par diogene

Tu pensais juste. Le compilateur allouera au minimum un char pour stocker les champ de bits, même si il n'y a qu'un bit.
Donc, tu ne gagneras rien en utilisant ici un champ de bits.

De plus, le compilateur, dans les deux cas, peut ajouter des bytes supplémentaires en queue de structure ou derrière une variable de ce type, pour des questions d'alignement des variables.

Donc la notation précédente n'est qu'une vue de l'esprit ? Un char qui ne prendra que les valeurs 1 ou 0 ?

Citation:

Envoyé par nuwanda03

Donc la notation précédente n'est qu'une vue de l'esprit ? Un char qui ne prendra que les valeurs 1 ou 0 ?

Un peu plus qu'une vue de l'esprit. Je connaissais pas et j'ai donc testé.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 #include <stdio.h> typedef struct pile_s{ unsigned bit:1; }pile; int main(){ struct pile_s p; p.bit = 0; printf("%d\n", p.bit); p.bit = 1; printf("%d\n", p.bit); p.bit = 2; printf("%d\n", p.bit); return 0; }
Curieusement il ne m'a pas autorisé la notation en dehors de la structure. Faudrait que je regarde plus en détail.

A la compilation de ce code on obtient un warning nous mettant sur la voie de la limitation qu'on a ajouté :

Citation:

warning: large integer implicitly truncated to unsigned type [-Woverflow]

Et à l'exécution :

Citation:

0
1
0

J'ai pas pu vérifié la taille effectivement prise, sizeof envoie bouler à la compilation :

Citation:

error: ‘sizeof’ applied to a bit-field

Et je n'ai pas la possibilité d'installer valgrind.

10/12/2012, 16h47
diogene

Les champs de bits ne sont pas des "objets" autonomes : ils ne peuvent exister qu'à l'intérieur d'une structure/union.
De plus :
- on ne peut prendre leur adresse
- on ne peut leur appliquer l'opérateur sizeof. La seule possibilité est de prendre la taille de la structure, sizeof p, qui est d'ailleurs la chose qui nous interesse (= 4 avec mon compilateur).
10/12/2012, 19h59
nuwanda03

Citation:

Les champs de bits ne sont pas des "objets" autonomes : ils ne peuvent exister qu'à l'intérieur d'une structure/union.
De plus :
- on ne peut prendre leur adresse
- on ne peut leur appliquer l'opérateur sizeof. La seule possibilité est de prendre la taille de la structure, sizeof p, qui est d'ailleurs la chose qui nous interesse (= 4 avec mon compilateur).

Si l'on a une taille de 4, alors quitte à stocker un bit il vaut mieux le faire de cette façon !

Avec ces explications je peux continuer de coder, avec cette fois une file, et non pas une pile. Je vais mettre le sujet comme résolu, et ouvrirai un autre poste dans le cas où j'ai besoin de nouvelles réponses sur un autre point.

Merci à tous pour votre aide, et vos conseils précieux :ccool:
11/12/2012, 09h35
ternel

euh, sizeof p == 4, c'est plus que sizeof (char), qui vaut toujours 1.
11/12/2012, 11h23
diogene

Oui, et c'est la raison de ma remarque dans ce message :

Citation:

De plus, le compilateur, dans les deux cas, peut ajouter des bytes supplémentaires en queue de structure ou derrière une variable de ce type, pour des questions d'alignement des variables.
11/12/2012, 21h16
nuwanda03

Au temps pour moi, effectivement j'ai dit nawak !