liste chainée

**l1informatique** · 26/12/2015, 18h35

Bonjour,

Je ne comprends pas comment résoudre ce problème.

Construire en C une liste L à quatre éléments dans le code du programme à l'aide de cons. Testez car(L), car(cdr(L), car(cdr(cdr L)), car(cdr(cdr(cdr L))), en affichant leur résultat.

La première question : le code marche bien mais dès que j'ajoute caar rien ne marche plus :s

Définir en C, à l'aide de #define, caar et cadr. Construisez une liste pour les tester et afficher leur résultat.

Code :

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

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
# include <stdio.h>
# include <stdlib.h>
#define nil NULL
 
typedef struct node { int car ; struct node * cdr ; } node, * list ;
 
void usage(char *) ;
list cons(int car, list L);
void putlist(list L);
int car(list L);
list cdr(list L);
 
 
int main() 
 
{	list L = nil ;
	int k;
		for (k = 0 ; k < 4 ; k++)
			L = cons(k, L) ;
			putlist(L) ;
			printf("\n");
			printf("car : %d\n", car(L));
			putlist(cdr(L));
			printf("\n");
			printf("car(cdr(L) : %d\n", car(cdr(L)));
			printf("car(cdr(cdr L)) : %d\n",car(cdr(cdr (L))));
			printf("car(cdr(cdr(cdr L))) : %d\n",car(cdr(cdr(cdr (L)))));
 
	return 0 ; }
 
list cons(int car, list L)
{	list new = malloc(sizeof(node)) ;
	if (! new) usage("cons : manque de RAM") ; 
		new -> car = car ;
		new -> cdr = L ;
	return new ; }
 
void putlist(list L)
{	if (! L) return ; 
	printf("%d ", L -> car) ;
	putlist(L -> cdr) ; }
 
 
int car(list L)
{
return L -> car ;
}
 
list cdr(list L)
{
	return L -> cdr;
 
}
 
 
 
void usage(char * P) { printf("Usage : %s erreur", P), exit(1) ; }

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
 
langgg.c: In function ‘main’:
langgg.c:31:4: warning: passing argument 1 of ‘car’ makes pointer from integer without a cast [enabled by default]
    putlist(caar(L));
    ^
langgg.c:10:5: note: expected ‘list’ but argument is of type ‘int’
 int car(list L);
     ^
langgg.c:31:4: warning: passing argument 1 of ‘putlist’ makes pointer from integer without a cast [enabled by default]
    putlist(caar(L));
    ^
langgg.c:9:6: note: expected ‘list’ but argument is of type ‘int’
 void putlist(list L);

Merci de m'aider

**LittleWhite** · 27/12/2015, 14h02

Bonjour,

Le compilateur vous indique que la fonction putlist() n'accepte en argument qu'une liste.
Vous, vous avez déclaré la fonction car() retournant un int. Du coup, lorsque vous faites :

Code :

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

putlist(caar(L));

(D'ailleurs pourquoi caar avec deux 'a' ?)
Le compilateur n'aime pas, car car() retourne un int et putlist() accepte uniquement une liste.

C'est exactement ce qui est dit ici :

langgg.c: In function ‘main’:
langgg.c:31:4: warning: passing argument 1 of ‘car’ makes pointer from integer without a cast [enabled by default]
putlist(caar(L));
^
langgg.c:10:5: note: expected ‘list’ but argument is of type ‘int’
int car(list L);
^
langgg.c:31:4: warning: passing argument 1 of ‘putlist’ makes pointer from integer without a cast [enabled by default]
putlist(caar(L));
^
langgg.c:9:6: note: expected ‘list’ but argument is of type ‘int’
void putlist(list L);

**Obsidian** · 27/12/2015, 15h11

J'ajoute qu'à la base, la gestion de listes avec « cons », « car », « cdr », « caar » et « cadr », ce n'est pas du C mais du LISP.

Envoyé par LittleWhite

(D'ailleurs pourquoi caar avec deux 'a' ?)

Parce qu'en LISP, « (caar) » est équivalent à « (car (car liste)) » (soit « car(car(liste)) » en syntaxe C). C'est d'ailleurs pour cela que son professeur lui demande de faire cela avec des #define : on écrit d'abord les fonctions fondamentales, et on implémente les autres avec des macros.

**l1informatique** · 27/12/2015, 15h43

J'ai déclaré define caar. mais j'ai toujours le meme probleme de cast

Code :

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

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
# include <stdio.h>
# include <stdlib.h>
#define nil NULL
 
typedef struct node { int car ; struct node * cdr ; } node, * list ;
 
void usage(char *) ;
list cons(int car, list L);
void putlist(list L);
int car(list L);
list cdr(list L);
 
#define caar(x) car(car(x)) 
#define cadr(x) car(cdr(x))
 
int main() 
 
{	list L = nil ;
	int k;
		for (k = 0 ; k < 4 ; k++)
			L = cons(k, L) ;
			putlist(L) ;
			printf("\n");
			printf("car(L) : %d\n", car(L));
			putlist(cdr(L));
			printf("\n");
			printf("car(cdr(L) : %d\n", car(cdr(L)));
			printf("car(cdr(cdr L)) : %d\n",car(cdr(cdr (L))));
			printf("car(cdr(cdr(cdr L))) : %d\n",car(cdr(cdr(cdr (L)))));
			printf("cadr(L) : %d\n", cadr(L));
			putlist(caar(L));
			//printf("caar(L) : %d\n", caar(L));
	return 0 ; }
 
list cons(int* car, list L)
{	list new = malloc(sizeof(node)) ;
	if (! new) usage("cons : manque de RAM") ; 
		new -> car = car ;
		new -> cdr = L ;
	return new ; }
 
void putlist(list L)
{	if (! L) return ; 
	printf("%d ", L -> car) ;
	putlist(L -> cdr) ; }
 
 
int car(list L)
{
return L -> car ;
}
 
list cdr(list L)
{
	return L -> cdr;
 
}
 
 
 
void usage(char * P) { printf("Usage : %s erreur", P), exit(1) ; }

**Obsidian** · 27/12/2015, 16h23

C'est tout-à-fait normal, et le problème est d'ailleurs le même en LISP quand on n'a pas l'habitude :

Code LISP :

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

1
2
3
4
5
(car '(1 2 3 4 5))
1
Break 3 [4]> (caar '(1 2 3 4 5))
 
*** - CAAR: 1 is not a list

… seulement, sa résolution va être un tout petit plus subtile que prévu si tu n'as pas mis le doigt sur la cause exacte.
Question préliminaire : as-tu déjà fait un peu de LISP ou t'a-t-on donné ce projet brut de décoffrage sans un minimum d'explications au préalable ?

**CodeurPlusPlus** · 27/12/2015, 16h35

Il y a un problème dans l'exercice à faire lui-même... caar (l) n'a aucun sens si l est une liste d'entiers.

**Obsidian** · 27/12/2015, 17h38

Envoyé par CodeurPlusPlus

Il y a un problème dans l'exercice à faire lui-même... caar (l) n'a aucun sens si l est une liste d'entiers.

C'est précisément là qu'est la subtilité : il n'a jamais été précisé explicitement « liste d'entiers » mais bien « liste d'éléments ».

Construire en C une liste L à quatre éléments dans le code du programme à l'aide de cons

Et « car » n'est pas forcément le nom d'un élément, et encore moins celui d'un type. Et surtout, cela n'a absolument rien à voir avec « char ». Ce sont des fonctions fondamentales du LISP, qui elles-mêmes portent ce nom pour raisons historiques. Bref, à moins que cette approche soit volontaire pour pousser le candidat à se poser les bonnes questions et à le confronter aux difficultés qui pourraient déboucher sur les raisons fondamentales qui ont conduit à concevoir le LISP, ce serait quand même une bonne chose de commencer par le début, de voir comment cela fonctionne dans les grandes lignes (ce qui peut se résumer en un seul commentaire) et — ensuite — implémenter un LISP minimal en langage C.

**l1informatique** · 29/12/2015, 15h15

Bonjour,

Merci pour les réponses. j'ai passé plusieurs jours sur cette exerices sans vain, mais le souci c'est que déja je dois créer une liste de liste donc changer la fonction cons je pense.

Quelqu'un peut m'aider merci

**Obsidian** · 29/12/2015, 18h03

Bonjour,

Il faut que tu fasses un peu de LISP. C'est bon pour la santé !

Plus concrètement, il faut savoir que :

LISP fonctionne de manière symbolique, un peu comme le shell ;
CAR et CDR sont des instructions qui font historiquement référence aux registres de l'IBM 7094, un ordinateur de 1962 ;
Chaque élément LISP peut être soit un « atome » (dans le sens « d'indivisible »), soit une « construction » de deux éléments, associés avec CONS ;
Il existe l'élément NIL, qui est atomique en soi, et qui signifie « néant ». C'est un peu l'équivalent du NULL des bases de données, et il est aussi, en LISP, équivalent à « false » ;
Il existe un élément « true », noté « t » ;
On peut préfixer tout élément par « ' » pour dire qu'il s'agit d'un atome et pas d'une expression à évaluer.

Une construction est représentée par la paire d'éléments qu'elle contient, entre parenthèses et séparés par un point :

Code LISP :

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

1
2
> (cons 1 2)
(1 . 2)

Les listes sont en fait des constructions de sous-constructions. Plus précisément, il s'agit d'un arbre binaire avec :

Un élément à gauche ;
Une sous-construction à droite ;
La dernière sous-construction en profondeur étant caractérisée par un élément à gauche et NIL à droite.

Code LISP :

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

1
2
> (cons '1 (cons '2 (cons '3 (cons '4 NIL))))
(1 2 3 4)

C'est donc la définition d'une liste en LISP mais les constructions ne servent pas forcément à faire des listes, ou à tout le moins, on peut en construire de manière non normalisée. Par exemple, la même liste construite à gauche plutôt qu'à droite donnerait :

Code LISP :

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

1
2
> (cons (cons (cons (cons 4 NIL) 3) 2) 1)
((((4) . 3) . 2) . 1)

Du coup, la clé du mystère est dans ta structure « node » : il ne faut pas la considérer comme une liste chaînée d'entiers, comme tu le fais. Il faut à la place définir une structure « élément » qui, elle, contient un champ « type » et une union des types possibles en LISP : http://www.gnu.org/software/emacs/ma...ata-Types.html (tu n'es pas obligé de tous les implémenter, cela dit). Et parmi ces types, un type « CONS » qui consiste en fait en un tableau d'exactement deux pointeurs vers d'autres éléments (tu es d'ailleurs obligé de passer par des pointeurs parce que les structures ne peuvent pas s'autocontenir).

Et de là :

car et cdr n'attendent qu'un seul argument (une construction) ;
car et cdr s'assurent que cet élément est bien un CONS, sinon déclenchent une erreur.
car renvoie l'élément gauche et cdr l'élément droit.

À ce stade, tu as un LISP fonctionnel. Et les fonctions supplémentaires définies avec tes macros (caar, cddr,…) fonctionneront automatiquement.

**l1informatique** · 01/01/2016, 18h14

J'ai bien compris le cours de lisp

J'ai essayé d'iplémenter deux structures et de doubler chaque fonction mais je bloque au niveau de main.

POurriez voue m'aider pour le main

Code :

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

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
# include <stdio.h>
# include <stdlib.h>
#define nil NULL
 
typedef struct node { int car ; struct node * cdr ; } node, * list ;
typedef struct node2 { struct node *Liste ; struct node2 * cdr2 ; } node2, * liste ;
 
void usage(char *) ;
list cons(int car, list L);
void putlist(list L);
list car(liste L);
int car2(list L); 
list cdr(list L);
liste cons2(struct node * Liste, liste L);
void putlist2(liste L);
liste cdr2(struct node2 * Liste);
 
#define caar(x) car2(car(x)) 
#define cadr(x) car(cdr(x))
 
int main() 
 
{	list L1 ;
	liste j ;
	int k,h;
		for (k = 0 ; k < 4 ; k++)
		    L = cons(k, L) ;
			putlist2(j) ;
			putlist2(caar(L));
			putlist2(cadr(L));
	return 0 ; }
 
list cons(int car, list L)
{	list new = malloc(sizeof(node)) ;
	if (! new) usage("cons : manque de RAM") ; 
		new -> car = car ;
		new -> cdr = L ;
	return (list)new ; }
 
 
liste cons2(struct node * Liste, liste L)	
{	liste nouveau = malloc(sizeof(node2)) ;
	if (! nouveau) usage("cons : manque de RAM") ; 
		nouveau -> Liste = Liste ;
		nouveau -> cdr2 = L ;
	return nouveau ; }
 
void putlist(list L)
{	if (! L) return ; 
	printf("%d ", L -> car) ;
	putlist(L -> cdr) ; }
 
void putlist2(liste L)
{	if (! L) return ; 
	printf("(");
	printf("(");
	putlist(L -> Liste) ;
	putlist2(L -> cdr2) ; 
	printf(")");
	printf(")");
	}
 
list car(liste L)
{
return L -> Liste ;
}
 
int car2(list L)
{
return L -> car ;
}
 
list cdr(list L)
{
	return L -> cdr;
 
}
liste cdr2(struct node2 * Liste)
{
	return Liste -> cdr2;	
}
 
void usage(char * P) { printf("Usage : %s erreur", P), exit(1) ; }

**Obsidian** · 01/01/2016, 22h20

Bonsoir et bonne année 2016,

Envoyé par l1informatique

J'ai bien compris le cours de lisp

J'ai essayé d'iplémenter deux structures et de doubler chaque fonction mais je bloque au niveau de main.
POurriez voue m'aider pour le main

On peut t'aider pour le main mais à mon avis, ça ne va pas t'aider du tout. Ton code gagne en complexité sans résoudre le problème de conception initial et cela ne va le rendre que plus compliqué à dépanner. La faille est ici :

Code :

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

1
2
typedef struct node { int car ; struct node * cdr ; } node, * list ;
typedef struct node2 { struct node *Liste ; struct node2 * cdr2 ; } node2, * liste ;

Tu persistes à envisager les constructions comme des « nœuds » qui, eux-mêmes, seraient construits comme des listes chaînées simples. Et en réalité, ce n'est pas le cas. Bien que les listes LISP consistent en un développement récursif « à droite » et que les principales fonctions (car, cdr, etc.) sont faites pour traiter des données organisées de cette façon, les constructions LISP en elles-mêmes sont en réalité complètement symétriques. Il faut donc abandonner l'approche « struct { } node, *list », surtout que cacher un pointeur dans un typedef est une très mauvaise pratique (malheureusement assez répandue dans les écoles).

Écris le bon type comme expliqué au-dessus, consistant en une structure contenant un champ « type » utilisant une énumération enum, et une union de tous les types de données possibles, dont CONS, laquelle construction consiste elle-même en un tableau de de pointeurs vers le type que tu es en train de définir. Ensuite, tu implémentes car et cdr en vérifiant que le type passé en argument est bien une construction (en examinant « type » ) et en renvoyant l'élement pointé par le premier ou le second pointeur, respectivement.

Une fois accomplie la tâche décrite dans ce dernier paragraphe, ton programme fonctionnera automatiquement, et tu n'auras rien à ajouter de plus quand tu implémenteras les macros caar, cadr et autres.

Tu pourras alors écrire la totalité de ton programme, macros comprises, en une quinzaine de lignes.

liste chainée

C

Discussions similaires

Partager

Partager