Forum Programmation.c liste de liste

Posté par méqueline le 04 janvier 2016 à 15:00. Licence CC By‑SA.

Étiquettes : aucune

jan.

2016

Bonjour,

quelqu'un peut m'aider a résoudre ce problème

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

#define caar(x) car(car(x)) 
#define cadr(x) car(cdr(x))

ESt ce qu'on doit construire une liste avec deux structures ?

typedef struct node { int car ; struct node * cdr ; } node, * list ;

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 ; }


int main() 

{   list L;
    int k;
        for (k = 0 ; k < 4 ; k++)
            L = cons(k, L);
            putlist(L) ;
            putlist(caar(L));
            printf("\n");
            putlist(cadr(L));
    return 0 ; }

ESt ce que c'est possible de construire une liste de liste

L = cons(cons(k, L), nil); exemple ((1 2 3 4)) ??

la fonction putlist est la suivant :

void putlist(list L)
{   if (! L) return ; 
    printf("%d ", L -> car) ;
    putlist(L -> cdr) ; }

Merci de m'aider

# ooohhhh ... déïja vou !

Posté par Anonyme le 04 janvier 2016 à 15:17. Évalué à 5.

https://linuxfr.org/forums/programmation-c--2/posts/affichage-listes-chainees-en-c

vous devriez vous mettre en binôme pour faire vos devoirs
- [^] # Re: ooohhhh ... déïja vou !
  
  Posté par totof2000 le 04 janvier 2016 à 19:25. Évalué à 3.
  
  Vu comment ils se sont pris le bec sur un autre fil, je pense que ça ne risque pas … ;)
  
  Au fait c'est bien du C ou du shell ?
# merci

Posté par NeoX le 04 janvier 2016 à 15:19. Évalué à 7.

Merci de m'aider

merci de lire le cours (et les consignes de mises en forme au bas de la page)
# liste de liste

Posté par méqueline le 04 janvier 2016 à 20:30. Évalué à 1.

Il s'agit du C.

J'ai posté dans le forum pour avoir de l'aide c'est tout, je bloque un bon moment sur cette exercice.
- [^] # Re: liste de liste
  
  Posté par Dr BG le 05 janvier 2016 à 06:53. Évalué à 3.
  
  Les profs servent aussi à répondre aux questions.
- [^] # Re: liste de liste
  
  Posté par benja le 05 janvier 2016 à 07:18. Évalué à 2.
  J'imagine qu'il s'agit que vous avez maintenant à devoir traiter des listes de listes.
  Dans votre exemple, le membre "car" est un entier, mais vous avez maintenant besoin qu'il puisse être un entier ou (un pointeur vers) une liste. Donc si j'ai bien compris/inféré votre énoncé:
  - Je vous conseillerais, dans un premier temps, de remplacer votre entier par une nouvelle structure --appellons là par exemple "value_t"—qui contiendrait une union des types "int" et "node" et un tag pour discriminer l'union.
  - Ensuite j'écrirais des fonctions "inline" ayant les signatures: value_t* car(node*) et node*cdr(node*).
  - Enfin je me rendrais compte que pour utiliser vos définitions de caar/cadr j'ai besoin d'unifier mes types node et value_t pour ne plus n'avoir qu'un seul type de donnée. Je changerais la définitions de mes fonctions d'accès comme suit: value_t* car(value_t*); value_t* cdr(value_t*). Et je modifierais leur implémentation pour gérer les différents cas de l'union, idem pour putlist. Elles seront maintenant imbricables…
  PS: c'est un peu dommage que vous n'ayez pas fait cette réflexion vous même… Votre "je bloque c'est tout", je l''interprète par "j'ai envie qu'on me donne la solution tout cuit", il aurait été plus intéressant pour vous de nous montrer spécifiquement sur quoi vous bloquer (i.e. une erreure de compilation, un code complet et pas juste des extraits dont on ne comprend pas s'ils viennent de votre énoncé ou d'un de vos camarade…). Sur ce je vous souhaite bon courage et n'hésitez pas à poser une question au cas où vous trouveriez mes explications peu claires!
  - [^] # Re: liste de liste
    
    Posté par benja le 06 janvier 2016 à 14:26. Évalué à 1. Dernière modification le 06 janvier 2016 à 14:28.
    
    Est-ce que cela a pu vous mettre sur la voie ? Sinon, qu'est-ce qui ne va pas ? Avez-vous compris maintenant pourquoi votre #define caadr ne pouvait pas fonctionner ?
    
    Avez vous déja des notions de lisp ? Cela pourrait vous aider à comprendre la finalité de vos exercices qui consistent à première vue à créer un mini interpréteur lisp. Ce lien pourrait, peut-être, vous éclairer: http://stackoverflow.com/questions/23966768/cadr-of-a-list-involving-assoc-function/23967225#23967225

# liste de liste

Posté par méqueline le 06 janvier 2016 à 14:55. Évalué à 1. Dernière modification le 06 janvier 2016 à 17:56.

Oui j'ai compris toute les notions de lisp et pour ma fonction j'ai essayé ça

#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 L;
    //liste j;
    int k;
        for (k = 0 ; k < 4 ; k++)
            L = cons(k, L);
            putlist(L) ;
            //putlist(caar(j));
            /*printf("\n");
            putlist(car(j));
            //printf("car(L) : %d\n", car(L));
            printf("\ncdr(j) :");
            putlist2(cdr2(j));
            printf("\ncaar(L) : %d\n", caar(j));
            //putlist(caar(j));
            printf("\n");
            printf("cadr(L) : %d\n", cadr(L));
            putlist2(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 (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 ; 
    putlist(L -> Liste) ;
    putlist2(L -> cdr2) ; 
    }

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) ; }

mais mon problème c'est dans main je ne vois pas comment crée une liste de liste.

[^] # Re: liste de liste

Posté par Space_e_man (site web personnel) le 06 janvier 2016 à 15:45. Évalué à 2.

Le but de cet exercice ne serait-il pas d'utiliser les macros (#define) en C pour une programmation générique de listes, à l'instar de l'usage des templates en C++ ? (cf. std::list)

Le cours n'aurait-il pas porté là-dessus ?
[^] # Re: liste de liste

Posté par benja le 06 janvier 2016 à 16:47. Évalué à 1. Dernière modification le 06 janvier 2016 à 16:49.
Ok. Comme je vous l'ai dit, le problème se situe au niveau du type de vos données et des signatures de vos fonctions qui doivent toutes retourner le même type "liste" (que j'ai appellé value dans ma solution). En effet, la beauté de LISP, c'est que tout est une liste ! Ainsi, car,cdr,… prennent une liste et retournent une liste… Ça je pense que vous avez compris.

Donc l'astuce c'est que votre node doit pouvoir contenir soit un entier, soit une autre liste. Et par conséquent, doit posséder un moyen de "typer" la node pour savoir si elle représente une liste ou une valeur immédiate/un entier, ici grâce au champs "tag".
```
struct node3;

struct value {
  enum {LISTE, ENTIER} tag;
  union { struct node3 * lst; int ival; } val;
};
```
J'ai utilisé une "union" mais rien ne vous empêche d'utiliser une "struct", sauf que vous gaspillez ce faisant un peu de mémoire car une valeur ne peut pas être à la fois un entier et une liste.

Votre type node devient:
```
struct node3 {
  struct value car;
  struct node3 * cdr ;
};
typedef struct node3 *value;
```
Remarquez bien au passage que ma définition de struct node3 contient (embed en anglais) la structure value, et non un pointeur. Cela permet de ne faire qu'une seule allocation pour créer une liste d'un élément (cf. plus bàs).

Le typedef rend les choses un peu confuses: "struct value" et "value" représente des choses différentes. Il pourrait avantagement être renommé en "liste" pour rendre les choses plus claires. Il rend déja les déclarations de fonctions plus lisibles. Néanmoins, dans les appels à sizeof je garde j'utilise toujours le type de base, question de goût.

Bref avec cette représentation la construction de cons devient triviale.
```
value cons(value head, value tail) {
  if (nil == head)
    return nil;                 /* FIXME: ERROR */

  value nouveau = calloc(sizeof(struct node3),1);
  if (! nouveau)
    return nil;                  /* IDEM */

  nouveau->car.tag = LISTE;
  nouveau->car.val.lst = head;
  nouveau->cdr = tail;

  return nouveau;
}
```
Il vous manque plus qu'un constructeur pour créer un entier. Remarquez qu'un entier est une liste d'un élément de type entier… Remarquez aussi l'utilisation de calloc qui initialise la mémoire à zéro en même temps que de l'allouer.
```
value entier(int i)
{
  value nouveau = calloc(sizeof(struct node3),1);
  if (! nouveau)
    return nil;

  nouveau->car.tag = ENTIER;
  nouveau->car.val.ival = i;
  nouveau->cdr = nil;

  return nouveau;
}
```
Chez moi ça compile, je n'ai pas implémenté le reste de votre exercice mais cela devrait être trivial maintenant.
```
int main()
{
  value l1,l2,l3;

  l1 = cons(entier(42),nil);    /* (list 42) */
  l2 = cons(l1,nil);            /* (list (list 42)) */
  l3 = cons(entier(22),entier(23)); /* (list 22 23) */

  return 0;
}
```
- [^] # Re: liste de liste
  
  Posté par benja le 06 janvier 2016 à 18:36. Évalué à 1.
  ps: avec cette représentation, pour implémenter car, vous devez en réalité créer une nouvelle liste d'un élément. Il serait peut-être plus judicieux de déplacer cdr dans l'union, à vous de voir.
  
  Autre possibilité (économise un pointeur, mais risque de rendre le code plus compliqué).
```
struct node
{
  enum {LISTE, ENTIER} tag;
  union {
   int ival;
   struct {
     struct node *car;
     struct node *cdr;
   };
  };
}
```
[^] # Re: liste de liste

Posté par NeoX le 06 janvier 2016 à 17:57. Évalué à 2.

Oui j'ai compris toute les notions de lisp et pour ma fonction j'ai essayé ça

sauf que là ton programme est en C donc les notions de LISP ne te servent à rien,
il faut aller lire de le cours sur la programmation en C
- [^] # Re: liste de liste
  
  Posté par benja le 06 janvier 2016 à 18:04. Évalué à 1.
  
  Je crois que la personne répondait à mon message juste plus haut qui lui demandait si elle avait des notions de lisp. Il me semble que lorsqu'on écrit un simili de lisp, ça peut-être utile de savoir ce que ça fait ;-)

# liste en liste

Posté par méqueline le 06 janvier 2016 à 22:18. Évalué à 1.

Oui je vous remerci benja pour les explications je vais essayer de comprendre et de relire le cours en C.

et de poser des questions si je bloque merci

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.