Problème déclaration liste chainée

Version imprimable

bonjour,

Bon je ne suis pas assez fort en liste chainée.
J'ai une petit soucis sur ça.
voici une petit code.
je veux juste ici créer une structure et dans cette structure une variable de type liste chainée.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 typedef struct liste liste; struct liste { char* id; int pos; struct liste *nxt; }; typedef liste* llist; typedef struct { char* Kmer; uint32_t hashvalue; liste posID; }Thash;
est-ce que c'est exacte?
Merci

14/04/2016, 13h56
ternel

non. dans la seconde, tu veux une probablement une lliste.

De plus, il est très déconseillé de faire un typedef sur un pointeur, si ce n'est pas un type completement opaque.
14/04/2016, 13h57
Médinoc

Au passage, liste comme nom est mensonger; tu devrais plutôt appeler ta structure chainon.

Dans une meme situation, j'écrirai:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
typedef struct pos_id_chained
{
    char* id;
    int pos;
    struct pos_id_chained * next;
} pos_id_chained_t;
 
 
typedef struct {
    char* Kmer;
    uint32_t hashvalue;
    struct pos_id_chained * positions;
}Thash;

14/04/2016, 14h48
mido1951
pour:
Code:

1 2 struct pos_id_chained * next; struct pos_id_chained * positions;
l'étoile est de qulle coté pour le pointeur??
14/04/2016, 15h03
ternel
l'étoile est un modificateur de type agissant à droite. C'est un token indépendant, qui peut être précédé ou suivi d'espaces (ou non)

je conseille de lire l'étoile comme "ce qui est désigné par".
Ici, struct pos_id_chained * positions; signifie:

Citation:

soit struct pos_id_chained le type de ce qui est désigné par next;

Citation:

soit un struct pos_id_chained, ce qui est désigné par next;

L'intérêt d'une telle lecture est que tu ne peux pas te tromper:
int * a, b; signifie "soit int le type de ce qui est désigné par a et celui de b".
Conformément au langage, avec une telle lecture, on a bien un pointeur de int (a) et un int (b)

Du coup, pour répondre à ta question pratique:
on peut placer l'étoile de plusieurs façon:
- la notation int *a est pratique pour déclarer une variable (locale ou globale) sans risquer la confusion int* a, b;
- je me sers de int * a pour les paramètres de fonctions, ou pour les membres d'une structure (que je sépare toujours), pour que l'étoile soit toujours bien visible.
- j'utilise parfois int* a dans un prototype de fonction, si le type est un typedef et que le paramètre n'est pas nommé.
je pense que int*a est possible, mais je ne vois aucun cas utile, puisque c'est toujours moins lisible.
14/04/2016, 15h14
mido1951

merci pour le code leternel.
mais ici, où est la déclaration de la liste chainée?
tu as juste définie la structure de la liste chainée. n'est ce pas?
14/04/2016, 15h19
Médinoc

Il y a une déclaration de liste chaînée dans la structure Thash.
14/04/2016, 15h20
ternel

Dans ton code aussi.

J'ai fais en sorte qu'il y ait une liste dans la seconde structure.
à toi d'écrire les fonctions qui font correctement les insertions, suppressions, parcours et recherches.

Citation:
Envoyé par leternel
Dans une meme situation, j'écrirai:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 typedef struct pos_id_chained { char* id; int pos; struct pos_id_chained * next; } pos_id_chained_t; typedef struct { char* Kmer; uint32_t hashvalue; struct pos_id_chained * positions; }Thash;
ici il y a une liste chainée dans la deuxième structure et oui c'est ce que je veux.
Mais ici quand je déclare un tableau de structure et dans sa troisième colonne est la liste chainée. Comment faire pour cette liste?
est-ce que je dois déclarer une liste ou lorsque le tableau de structure est déclaré la liste va etre aussi déclaré?
voici une déclaration:
Code:

1 2 3 Thash* TThash; TThash=malloc(20000*sizeof(Thash));
pour la liste est-ce que je dois faire la même chose ou non??
Merci

Tout ce que tu as à faire, c'est initialiser tous les pointeurs de ton tableau à NULL.

Code:

1
2
3
4
5
6
7
8
9
Thash* TThash;
TThash=malloc(20000*sizeof(Thash));
if(TThash == NULL) {
    /*gestion d'erreurs ici*/
}
Thash def = {NULL, 0, NULL};
size_t i;
for(i=0 ; i<20000 ; i++)
    TThash[i] = def;

15/04/2016, 08h23
ternel

En complément d'explication, il faut bien comprendre le role de malloc.
Cette fonction ne crée pas un tableau, elle alloue un bloc mémoire de la taille demandée, donc compatible avec un tableau.
Pour que ce bloc mémoire soit utilisable comme un tableau, il faut initialiser la mémoire obtenue (après avoir vérifié qu'on en a obtenu)
15/04/2016, 09h25
mido1951

ok pour la mémoire mais ici j'ai une petit problème que j'ai pas pu le comprendre.
Je sais que je suis entrain de faire une structure complexe mais dans elle est facile dans sa compréhension.
Comme vous voyez je fais un tableau de TThash et sa troisième colonne est une liste chainée.
donc OK pour la déclaration du tableau de la structure et l'initialisation.
Mais mon problème Comment faire pour la liste chainée?
je ne suis pas assez puissant dans les listes chainées c'est pour ça que je veux un peux d'aide ici.
est-ce que je dois initialiser la liste ou... ?? :(
Merci
15/04/2016, 09h51
Médinoc

Normalement, une liste simplement chaînée vide, c'est juste un pointeur nul.
15/04/2016, 09h59
mido1951
Citation:

Envoyé par Médinoc

Normalement, une liste simplement chaînée vide, c'est juste un pointeur nul.

est-ce que c'est exacte?
Code:

1 2 3 4 5 6 7 8 9 Thash* TThash; TThash=malloc(20000*sizeof(Thash)); if(TThash == NULL) { /*gestion d'erreurs ici*/ } Thash def = {NULL, 0, NULL}; size_t i; for(i=0 ; i<20000 ; i++) TThash[i] = def;
la liste est initialisé de cette façon? je ne dois faire une fonction initialiser()?

Citation:
Envoyé par leternel
Dans une meme situation, j'écrirai:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 typedef struct pos_id_chained { char* id; int pos; struct pos_id_chained * next; } pos_id_chained_t; typedef struct { char* Kmer; uint32_t hashvalue; struct pos_id_chained * positions; }Thash;
je pense ici pos_id_chained_t est inutile n'est ce pas? on a déclaré le typedef pos_id_chained

15/04/2016, 10h27
ternel

En fait, non, on a combiné la définition de struct pos_id_chained et le typedef.
L'alias est bien pos_id_chained_t.

C'est suffisant pour initialiser la liste, mais rien n'empêche de mettre tout ça dans une fonction:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
Thash* CreerTableHash(size_t nbEntrees)
{
	Thash def = {NULL, 0, NULL};
	size_t i;
	Thash* TThash = malloc(nbEntrees * sizeof(Thash));
	if(TThash == NULL)
		return NULL;
 
	for(i=0 ; i<nbEntrees ; i++)
		TThash[i] = def;
	return TThash;
}

Citation:
Envoyé par Médinoc
C'est suffisant pour initialiser la liste, mais rien n'empêche de mettre tout ça dans une fonction:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 Thash* CreerTableHash(size_t nbEntrees) { Thash def = {NULL, 0, NULL}; size_t i; Thash* TThash = malloc(nbEntrees * sizeof(Thash)); if(TThash == NULL) return NULL; for(i=0 ; i<nbEntrees ; i++) TThash[i] = def; return TThash; }
D'accord merci pour ta réponse.
donc pour l'instant ce que je veux faire c'est de remplir les lignes du tableau et biensur remplir la dernière colonne par une liste chainée.
donc je crée une fonction ajouter(liste, pos, id) pour remplir la liste? c'est suffisant?
est-ce que c'est exacte?
parce que moi je veux juste remplir la liste puis faire une recherche dans la liste(aprés).
comment faire dans ce cas?
désolé pour mes msgs parce que je ne suis pas assez fort en liste chainée.
merci

15/04/2016, 14h05
Médinoc
Pour moi, le meilleur moyen de faire une fonction qui ajoute à une liste simplement chaînée est de lui passer le pointeur par pointeur:
Code:

1 2 3 4 5 void ajoute(pos_id_chained_t **ppListe, char const *id, int pos); ... ajoute(&TThash[index].positions, "blabla", 42);
15/04/2016, 14h12
picodev

Citation:

Envoyé par mido1951

[...]
désolé pour mes msgs parce que je ne suis pas assez fort en liste chainée.
merci

Bonjour,
tout dépend aussi pourquoi tu fais ce que tu fais. Si c'est un exercice pour apprendre les listes chaînées ou si c'est autre chose. Si c'est autre chose, il n'y a pas de honte,bien au contraire, à ne pas réinventer la roue carrée et utiliser des bibliothèques externes.
Par exemple, mais c'en est une parmi d'autres : la GLib2. C'est une bibliothèque qui propose des structures de données classiques avec tout ce qu'il faut pour les manipuler. Elle sert entre autre de fondation à la bibliothèque Gtk+ et d'autres.
En ce qui te concerne, elle propose des sdd comme les listes chaînées simple et double, des tableaux croissant dynamiquement, des tables de hachage, … → Glib Data Type.

Il y a aussi la bibliothèque APR (Apache Portable Runtime), les modules GNULIB qui ne forment pas à proprement parler une bibliothèque mais qui mettent des sources à disposition, …
15/04/2016, 15h04
mido1951

merci. :)
je suis entrain de créer un gros projet ce n'est pas un exercice.
j'ai juste besoin d'introduire la liste chainée dans une place et voila. c'est ce que je cherche.
MERCI
15/04/2016, 15h06
mido1951
Citation:
Envoyé par Médinoc

Pour moi, le meilleur moyen de faire une fonction qui ajoute à une liste simplement chaînée est de lui passer le pointeur par pointeur:

Code:

1 2 3 4 5 void ajoute(pos_id_chained_t **ppListe, char const *id, int pos); ... ajoute(&TThash[index].positions, "blabla", 42);
pourquoi ne pas utiliser un seul pointeur?
de cette façon:
Code:

1 2 3 4 5 6 void ajoute(pos_id_chained_t *ppListe, char const *id, int pos); ... ajoute(TThash[index].positions, "blabla", 42);
[/QUOTE]
[/CODE]
15/04/2016, 16h55
Médinoc

Parce si tu ne peux pas modifier le premier pointeur, comment ajoutes-tu le premier élément à une liste vide?

j'ai crée une fonction ajoute dans la liste de cette façon:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
pos_id_chained_t * ajoute(pos_id_chained_t *ppListe, char const *id, int pos)
{
            pos_id_chained_t * newelem= malloc(sizeof(pos_id_chained_t));
            strcpy(newelem->id,id);
            newelem->pos=pos;
            newelem->next = NULL;
 
        if(ppListe == NULL)
        {
            return newelem;
        }
        else
        {
            pos_id_chained_t * temp=ppListe;
            while(temp->next != NULL)
            {
              temp= temp->next;
            }
            temp->next=newelem;
            return ppListe;
        }
}

maintenant dans le main je dois faire quoi?
j'ai fait un main de cette façon:

Code:

1
2
3
4
5
6
7
8
9
10
 
 Thash* TThash;
     TThash=CreerTableHash(20000);
 
 
             TThash[j].Kmer=Kmer;
             TThash[j].hashvalue=Value;
             TThash[j].positions= ajoute(TThash[j].positions,sequence1,1000); // comment j'ajoute ici? je dois creer une variable de type liste chainée?                
             printf("TThash[%d].Kmer= %s \n",j,TThash[j].Kmer);
             printf("TThash[%d].hashvalue= %d \n",j,TThash[j].hashvalue);

Merci

18/04/2016, 10h08
Médinoc

Attention, n'appelle pas la variable "ppListe" s'il n'y a qu'un seul niveau de pointeur!

Citation:

Envoyé par Médinoc

Attention, n'appelle pas la variable "ppListe" s'il n'y a qu'un seul niveau de pointeur!

j'ai changé ma variable en "pListe".
mais le programme ne marche pas voici mon prog.

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
 
 
typedef struct pos_id_chained
{
    char* id;
    int pos;
    struct pos_id_chained * next;
} pos_id_chained_t;
 
typedef struct {
    char* Kmer;
    uint32_t hashvalue;
    struct pos_id_chained * positions;
}Thash;
 
 
Thash* CreerTableHash(size_t nbEntrees)
{
	Thash def = {NULL, 0, NULL};
	size_t i;
	Thash* TThash = malloc(nbEntrees * sizeof(Thash));
	if(TThash == NULL)
		return NULL;
 
	for(i=0 ; i<nbEntrees ; i++)
		TThash[i] = def;
	return TThash;
}
 
pos_id_chained_t * ajoute(pos_id_chained_t *pListe, char const *id, int pos)
{
            pos_id_chained_t * newelem= malloc(sizeof(pos_id_chained_t));
            strcpy(newelem->id,id);
            newelem->pos=pos;
            newelem->next = NULL;
 
        if(pListe == NULL)
        {
            return newelem;
        }
        else
        {
            pos_id_chained_t * temp=pListe;
            while(temp->next != NULL)
            {
              temp= temp->next;
            }
            temp->next=newelem;
            return pListe;
        }
}
 
void display ( pos_id_chained_t *p_head)
{
   pos_id_chained_t *p = p_head;
 
   while (p != NULL)
   {
      /* afficher les données courantes */
      printf ("sequence:  %s \n", p->id);
        printf("position:  %d \n", p->pos);
      /* pointer sur le suivant */
      p = p->next;
   }
   /* afficher la fin */
   printf ("NIL\n");
}
int main()
{
             int k=3;int i=0;int j=0;
char *sequence = NULL;
     sequence = malloc(sizeof(char) * 200000);int TAILLE_MAX=200001;
     char *Kmer = NULL;
     Kmer = malloc(sizeof(char) * k);
 int longseq=0; int nbKmer=0;
 
 
     Thash* TThash;
     TThash=CreerTableHash(20000);
 
         while(fgets(sequence,TAILLE_MAX, fichier1)!= NULL)
        {
            nbKmer=0;
        longseq=strlen(sequence)-1; printf("\nlongeur= %d\n", longseq);
 
         if(sequence[0]!='>' && strlen(sequence)>50)
        {
 
           for(i=0;i<=longseq-k;i++)
           {
                nbKmer++;
            strncpy(Kmer,sequence+i,k);
 
                Value= hash(Kmer);
             TThash[j].Kmer=Kmer;
             TThash[j].hashvalue=Value;
             TThash[j].positions= ajoute(TThash[j].positions,sequence1,1000);
 
             printf("TThash[%d].Kmer= %s \n",j,TThash[j].Kmer);
             printf("TThash[%d].hashvalue= %d \n",j,TThash[j].hashvalue);
             display(TThash[j].positions);
 
              j++;
            }
             printf("\n%d",nbKmer);
         }
         }
	if (fichier == NULL)
	 {		
		printf("File not found"); //      perror(msg);
	 }
 
    return 0;
}

bon les autres variables sont des variables déclarées deja.
Mais lorsque je stocke la première valeur dans le TThash[0] avec j=0 il ne veut pas avancer. et il sort de la boucle for(i=0;i<=longseq-k;i++) alors qu'il y a encore du travail a faire dans la boucle i.
est-ce que vous avec des suggestions?
MERci

18/04/2016, 11h21
Médinoc
Citation:
Code:

1 2 pos_id_chained_t * newelem= malloc(sizeof(pos_id_chained_t)); strcpy(newelem->id,id);
Boum!
newelem->id n'est pas alloué, ni même initialisé. Tu dois l'initialiser avec la valeur malloc(strlen(id)+1)...

bonjour,
j'ai changé mon idée de départ.
je veux créer une structure dans une structure et ajouter une liste chainée et dans cette sous-structure.
La première colonne de la matrice est hashvalue et les autres colonnes sont Id_Pos.
voici ma liste et les structures:
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 typedef struct { char* id; struct pos_id_chained * positions; }IdThash; typedef struct pos_id_chained { int pos; struct pos_id_chained * next; } pos_id_chained_t; typedef struct { uint32_t hashvalue; IdThash Id_Pos; }Thash; Thash** CreerTableHash(size_t nbEntrees,size_t nbLLR) { size_t i=0; //Thash def = {NULL, 0, NULL}; Thash **TThash = (Thash**)malloc(nbEntrees * sizeof(Thash*)); Thash *TThash2 = (Thash*)malloc(nbLLR*nbEntrees * sizeof(Thash)); /*if(TThash == NULL) return NULL;*/ for(i=0 ; i<nbEntrees ; i++) { TThash[i]= &TThash2[i*nbLLR]; } return TThash; }
pour la declaration comment je dois faire?
je ne sais pas si ma declaration est exacte pour pas!?

MErci

22/04/2016, 09h47
mido1951

salut,
je voulais savoir pour la liste chainée si on a une liste qu'on a déja explorer et on l'explore une nouvelle fois pourquoi çq ne donne rien?
j'ai une structure {char* ID, pos (de type liste chainée)}.
j'ai lu les pos de l'ID mais j'ai accédé une nouvelle fois mais ça me donne rien?
Est-ce que vous avez une solution??
Merci
22/04/2016, 10h00
Médinoc

Repars-tu bien du début de la liste?
22/04/2016, 10h06
mido1951

Citation:

Envoyé par Médinoc

Repars-tu bien du début de la liste?

non je n'ai pas pu retourner le pointeur au debut de la liste. comment faire?
je pense une fois la liste est lu donc on ne peut pas la relire sans pointer son pointeur au début.
22/04/2016, 10h18
Matt_Houston

Tu as dû modifier ta liste en la parcourant. Utilises des variables locales à ta fonction, ta liste doit rester inchangée.
22/04/2016, 13h49
mido1951
Citation:

Envoyé par Matt_Houston

Tu as dû modifier ta liste en la parcourant. Utilises des variables locales à ta fonction, ta liste doit rester inchangée.

je lis ma liste de cette façon:
Code:

1 2 3 4 5 while(maliste != NULL) { printf("%d",p->pos); p=p->next; }
et quand j'accede une nouvelle fois à la meme valeur pour enuméré une nouvelle fois les valeur de la liste ça ne donne rien!?
Est-ce que vous avez une idée??
Merci

Ça va faire une boucle infinie, ça.
Ce qu'il te faut, c'est un truc comme ceci:
Code:

1 2 3 4 5 6 7 8 9 { pos_id_chained_t * p = maListe; while(p != NULL) { printf("%d",p->pos); p = p->next; } }

22/04/2016, 13h59
mido1951

oui c'est ce que j'ai fait j'ai juste minimiser. meme comme ça. ça foctionne pas. j'ai pas mis dans une fonction je l'ai mis dans mon programme principal.
je ne comprends pas le truc.
je pense ici quand je sors de la boucle je dois remettre le pointeur à la première position. est-ce que vous avez une idée comment faire?
MERci
22/04/2016, 14h23
Médinoc

Citation:

Envoyé par mido1951

quand je sors de la boucle je dois remettre le pointeur à la première position. est-ce que vous avez une idée comment faire?

En en gardant une copie, tout simplement. Ou comme dans mon exemple, en travaillant sur une copie plutôt que l'original.