Pb tableau de listes chainées

Version imprimable

24/11/2005, 12h05
Beush

Pb tableau de listes chainées
En fait tout se passe comme si le dernier élément de tab_pointeur[i] au lieu de pointer vers NULL il pointait vers le premier élément de tab[i-1]. Du coup dans la dernière case du tableau on a tous les éléments que j'ai inséré et seul la première contient juste ce qu'il faut. Après la deuxième contient les éléments de la première puis de la deuxième.

Je vous fournit aussi le code de ma fonctions ajoutTete :
Code:

1 2 3 4 5 6 Cellule * ajoutTete(Cellule *c, Cellule * l){ if(c!=NULL){ c->suivant=l; } return c; }
Merci d'avance de vos réponses et n'hésitez pas à me demander plus d'infos si besoin est.

En fait ce message doit être situé avant le premier désolé je me suis un peu planté.

Bonjour j'ai un petit problème (mais qui fait bien ch..!) concernant un tableau de listes chainées. Les listes contiennent des structures Cellule défini comme ceci :
Code:

1 2 3 4 typedef struct Cellule{ Codage code; struct Cellule* suivant; }Cellule;
Le tableau de listes est défini comme ceci :

Code:

Cellule** tab_pointeur;

puis alloué et mis a NULL :
Code:

1 2 tab_pointeur=(Cellule**)malloc(sizeof(Cellule*)*NB_AA);//NB_AA=20 init_null(tab_pointeur,NB_AA);
J'appelle ensuite cette fonction pour construire mon tableau de liste :
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 Cellule* remplissage_liste(Codage tabCodage[NB_COD], Cellule* l, Cellule** tab_pointeur,Cellule* tab_rech[NB_COD]){ int i,j=0,ind_occ; Cellule *c; //on cree une cellule temporaire for(i=NB_COD-1;i>=0;i--){//NB_COD=64 c=creer_cellule(c,tabCodage[i].codon,tabCodage[i].AA3,tabCodage[i].AA1); ind_occ=recherche_occurence(tab_pointeur,tabCodage[i].AA3); if(ind_occ==-1){ tab_pointeur[j]=c; j++; } else{ tab_pointeur[ind_occ]=ajoutTete(c,tab_pointeur[ind_occ]); //si le codon est //déjà inséré //on insert en queue } tab_rech[fct_hachage(c->code.codon)]=c; l=ajoutTete(c,l); } return l; }

24/11/2005, 13h42
Emmanuel Delahaye

Citation:

Envoyé par Beush

Bonjour j'ai un petit problème (mais qui fait bien ch..!) concernant un tableau de listes chainées. Les listes contiennent des structures Cellule défini comme ceci :

Ne compile pas.

Poste une version complète et compilable, mais réduite au minimum qui montre le défaut. On ne va pas passer 2 heures à deviner tes intentions...

Voici le fichier codage_prot.c :

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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include "liste.h"
 
#define NB_AA 20
#define NB_COD 64
 
Cellule* creer_cellule(Cellule *c,char codon[4],char AA3[4],char AA1);
 
void afficher_cellule(Cellule* c);
 
Cellule* remplissage_liste(Codage tab_codage[NB_COD], Cellule* l,Cellule** tab_pointeur,Cellule* tab_rech[NB_COD]);
 
void afficher_liste(Cellule *l);
 
void init_null(Cellule** tab, int n);
 
int recherche_occurence(Cellule** tab_pointeur,char AA3[4]);
 
void tri_alpha(Cellule** tab_pointeur);
 
void afficher_tab_pointeur(Cellule** tab_pointeur);
 
int valeur_base(char lettre);
 
int fct_hachage(char codon[4]);
 
void libere_cellule(Cellule* l,Cellule *c);
 
int main(){
	Codage tabCodage[64] = {
	{"AAA","Lys",'K'},{"AAU","Asn",'N'},{"AAC","Asn",'N'},{"AAG","Lys",'K'},
	{"AUA","Ile",'I'},{"AUU","Ile",'I'},{"AUC","Ile",'I'},{"AUG","Ile",'I'},
	{"ACA","Thr",'T'},{"ACU","Thr",'T'},{"ACC","Thr",'T'},{"ACG","Thr",'T'},
	{"AGA","Arg",'R'},{"AGU","Ser",'S'},{"AGC","Ser",'S'},{"AGG","Arg",'R'},
	{"UAA","Sto",'*'},{"UAU","Tyr",'Y'},{"UAC","Tyr",'Y'},{"UAG","Sto",'*'},
	{"UUA","Leu",'L'},{"UUU","Phe",'F'},{"UUC","Phe",'F'},{"UUG","Leu",'L'},
	{"UCA","Ser",'S'},{"UCU","Ser",'S'},{"UCC","Ser",'S'},{"UCG","Ser",'S'},
	{"UGA","Sto",'*'},{"UGU","Cys",'C'},{"UGC","Cys",'C'},{"UGG","Trp",'W'},
	{"CAA","Gln",'Q'},{"CAU","His",'H'},{"CAC","His",'H'},{"CAG","Gln",'Q'},
	{"CUA","Leu",'L'},{"CUU","Leu",'L'},{"CUC","Leu",'L'},{"CUG","Leu",'L'},
	{"CCA","Pro",'P'},{"CCU","Pro",'P'},{"CCC","Pro",'P'},{"CCG","Pro",'P'},
	{"CGA","Arg",'R'},{"CGU","Arg",'R'},{"CGC","Arg",'R'},{"CGG","Arg",'R'},
	{"GAA","Glu",'E'},{"GAU","Asp",'D'},{"GAC","Asp",'D'},{"GAG","Glu",'E'},
	{"GUA","Val",'V'},{"GUU","Val",'V'},{"GUC","Val",'V'},{"GUG","Val",'V'},
	{"GCA","Ala",'A'},{"GCU","Ala",'A'},{"GCC","Ala",'A'},{"GCG","Ala",'A'},
	{"GGA","Gly",'G'},{"GGU","Gly",'G'},{"GGC","Gly",'G'},{"GGG","Gly",'G'}};
 
	Cellule* l;
	Cellule** tab_pointeur;
	Cellule* tab_rech[NB_COD];
	int i,indice;
	char codon[4];
 
	l=initListeVide();
	tab_pointeur=(Cellule**)malloc(sizeof(Cellule*)*NB_AA);
	init_null(tab_pointeur,NB_AA);	
 
 
	l=remplissage_liste(tabCodage,l,tab_pointeur,tab_rech);
 
	printf("Remplissage de la liste : OK\n");
	printf("tab[0]=%d\n",tab_pointeur[0]);
	printf("tab[1]->=%d\n",tab_pointeur[1]->suivant->suivant->suivant->suivant);
	//afficher_liste(tab_pointeur[1]);
 
	tri_alpha(tab_pointeur);
	printf("Tri du tableau de pointeur : OK\n");
	//afficher_tab_pointeur(tab_pointeur);
 
	scanf("%s",codon);
	afficher_cellule(tab_rech[fct_hachage(codon)]); //affiche le codon demandé
 
	//désallocation de la mémoire
	return 0;
}
 
Cellule* creer_cellule(Cellule *c,char codon[4],char AA3[4],char AA1){
	int i;
	c=(Cellule*)malloc(sizeof(Cellule));
	for(i=0;i<4;i++){
		c->code.codon[i]=codon[i]; //on copie la chaine 
		//codon de tabcodage[i] dans dans codon de la cellule courante
	}
	for(i=0;i<4;i++){
		c->code.AA3[i]=AA3[i];
	}
	c->code.AA1=AA1;
	c->suivant=NULL;
	return c;
}
 
void afficher_cellule(Cellule* c){
	printf("Codon : %s\n",c->code.codon);
	printf("AA3 : %s\n",c->code.AA3);
	printf("AA1 : %c\n",c->code.AA1);
}
 
Cellule* remplissage_liste(Codage tabCodage[NB_COD], Cellule* l, Cellule** tab_pointeur,Cellule* tab_rech[NB_COD]){
	int i,j=0,ind_occ;
	Cellule *c; //on cree une cellule temporaire
	for(i=NB_COD-1;i>=0;i--){
 
		c=creer_cellule(c,tabCodage[i].codon,tabCodage[i].AA3,tabCodage[i].AA1);
		ind_occ=recherche_occurence(tab_pointeur,tabCodage[i].AA3);
 
		/*printf("i=%d\n",i);
		printf("j=%d\n",j);
		printf("tabCodage[i].AA3=%s\n",tabCodage[i].AA3);
		printf("ind_occ=%d\n\n",ind_occ);*/
 
		if(ind_occ==-1){
			tab_pointeur[j]=c;
			j++;
		}
		else{
			tab_pointeur[ind_occ]=ajoutTete(c,tab_pointeur[ind_occ]); //si le codon est 
										//déjà inséré 
									   //on insert en queue
		}
 
		tab_rech[fct_hachage(c->code.codon)]=c;
		l=ajoutTete(c,l);
	}
	return l;
}
 
void afficher_liste(Cellule *l){
	Cellule *cellule_cour=l;
	if(!listeVide(cellule_cour)){
		afficher_cellule(cellule_cour);
		printf("\n");
		afficher_liste(cellule_cour->suivant);
	}
	else{
		printf("Liste vide\n");
	}
}
 
void init_null(Cellule** tab, int n){
	int i;
	for(i=0;i<n;i++){
		tab[i]=NULL;
	}
}
 
int recherche_occurence(Cellule** tab_pointeur,char AA3[4]){
	int i=0,indice=-1;
	while(tab_pointeur[i]!=NULL && indice==-1){
		if(strcmp(tab_pointeur[i]->code.AA3,AA3)==0){
			indice=i;
		}
		i++;
	}
	return indice;
}
 
void tri_alpha(Cellule** tab_pointeur){
     int i,j,res;
     Cellule* tmp;
     for(i=NB_AA;i>=0;i--){
          for(j=0;j<i-1;j++){
              if(strcmp(tab_pointeur[j]->code.AA3,tab_pointeur[j+1]->code.AA3)>0)
	      {
                   tmp=tab_pointeur[j];	//on permute
                   tab_pointeur[j]=tab_pointeur[j+1];
                   tab_pointeur[j+1]=tmp;
              }
          }
     }
 
}
 
void afficher_tab_pointeur(Cellule** tab_pointeur){
	int i;
 
	for(i=0;i<NB_AA;i++){
		printf("Liste n°%d\n",i);
		afficher_liste(tab_pointeur[i]);
	}
}
 
int valeur_base(char lettre){
	int val;
	switch(lettre){
		case 'A':val=0;
			break;
		case 'C':val=1;
			break;
		case 'G':val=2;
			break;
		case 'U':val=3;
			break;
		default:printf("La lettre ne fait pas partie  de {ACGT}.\n");
	}
	return val;
 
}
 
int fct_hachage(char codon[4]){
	int indice;
	indice=16*valeur_base(codon[0])+4*valeur_base(codon[1])+1*valeur_base(codon[2]);
	return indice;
}
 
void libere_cellule(Cellule* l,Cellule *c){
 
 
}

Puis liste.h :

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
typedef struct {
	char codon[4] ;
	char AA3[4] ;
	char AA1 ;
} Codage;
 
typedef struct Cellule{
	Codage code;
	struct Cellule* suivant;
}Cellule;
 
extern Cellule* initListeVide();
 
//test la vacuité de la liste
extern int listeVide(Cellule *l);
 
//retourne un pointeur sur la premiere cellule de la liste
extern Cellule * tete(Cellule *l);
 
//retourne l'adresse de la queue de la liste
extern Cellule * queue(Cellule *l);
 
extern Cellule * ajoutTete(Cellule *c, Cellule *l);
 
//supprime la premiere cellule de la liste
extern Cellule * supprimeTete(Cellule * l, void(*lc)(Cellule *));
 
extern Cellule* ajoutQueue(Cellule* c, Cellule *l);

puis liste.c :

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
#include "liste.h"
#include <stdlib.h>
#include <stdio.h>
 
Cellule* initListeVide(){
	return NULL;
}
 
//test la vacuité de la liste
int listeVide(Cellule* l){
	return (l==NULL);
}
 
//retourne un pointeur sur la premiere cellule de la liste
Cellule* tete(Cellule* l){
	if(listeVide(l)){
		printf("Erreur:La liste est vide!\n");
		return NULL;
	}
	else{
		return l;
	}
}
 
//retourne l'adresse de la queue de la liste
Cellule* queue(Cellule* l){
	if(listeVide(l)){
		printf("Erreur:La liste est vide!\n");
		return NULL;
	}
	else{
		return l->suivant;
	}
}
 
Cellule * ajoutTete(Cellule *c, Cellule * l){
	if(c!=NULL){
		c->suivant=l;
	}
	return c;
}
 
//supprime la premiere cellule de la liste
Cellule* supprimeTete(Cellule * l, void(*lc)(Cellule *)){
	Cellule *t;
 
	if(!listeVide(l)){
		t=l;	//on stocke l'adresse du premier element de la liste dans t
		l=l->suivant;	//on met dans l'adressse de l'élément suivant de la liste
		lc(t);	//on detruit la cellule situe a l'adresse t(ancienne tete de liste)
	}
	return l;
}
 
Cellule* ajoutQueue(Cellule* c, Cellule *l){
	Cellule *l2;
	if(listeVide(l)){
		l2=ajoutTete(c,l);
	}
	else{
		//l2=ajoutTete(tete(l),ajoutQueue(c,queue(l)));
		l2=ajoutQueue(c,l->suivant);
	}
	return l2;
}

et enfin le Makefile :

Code:

1
2
3
4
5
6
codage_prot:codage_prot.o liste.o
	gcc -o codage_prot codage_prot.o liste.o
codage_prot.o:codage_prot.c liste.h
	gcc -c -g codage_prot.c
liste.o:liste.c liste.h
	gcc -c liste.c