Forum Programmation.c Affichage listes chainées en C

Posté par roger91 le 21 décembre 2015 à 17:58. Licence CC By‑SA.

Étiquettes : aucune

déc.

2015

Bonjour,
J'ai ce code C qui affiche la liste de quatre éléments a b c d par exemple:

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define nil NULL // pour faire plus Lisp


    typedef struct Doublet {
        int elt ;
        struct Doublet * cdr ;
    } * list ;

    int main(int x) {          // peu importe la valeur de x
        list L, top = nil ;      // top : une liste vide
        for (x = 'a' ; x < 'e' ; x++) { 
            L = malloc(sizeof(struct Doublet)) ;  //
allocation dynamique 
            L -> elt = x ;            
            L -> cdr = top ;           
            top = L ;  // redéfinition du début
        }                
        while (L) {                // repartant du début
          printf("%c\n", L -> elt) ; // affiche le premier élément
            L = L -> cdr ;            // passe au reste 
        }           
        return 0 ;
    }

J'aimerais l'adapter avec une fonction cons comme en Lisp qui m'afficherait cette liste et lorsque j'aurai car (L) elle m'enverrai le premier élément de la liste et cdr (L) le reste des éléments de la liste avec les éléments suivants que je n'arrive pas à compléter pour y parvenir.
```

#define car(doublet) ((doublet)->car)

#define cdr(doublet) ((doublet)->cdr)

list cons(void *, const list); //prototype de la fonction
// Définition de la fonction cons
list cons(void * elt, const list L)
{ list Cons = malloc(sizeof(struct Doublet));

  car(Cons) = elt ;
  cdr(Cons) = L ;
  return Cons ; }

```Merci d'avance.

# Retour papier

Posté par lolop (site web personnel) le 22 décembre 2015 à 08:59. Évalué à 2.

Il faut revoir ta structure du doublet, dans elt tu stockes un entier ou un pointeur ?

Dans ta définition de car(doublet), tu accèdes un champs car qui n'existe pas. car(doublet), ça semblerait plutôt être simplement (doublet) [¹]. À ce moment, tu peux écrire car(Cons)->elt = elt;.

M'enfin, pour moi car et cdr c'est pour extraire, pas pour aller modifier. Pour faire le Cons en C j’accéderais directement aux champs.

[¹] Sauf que là tu conserves dans ton doublet un lien vers la liste, et tu retournes "l'original" - s'il fait partie d'une liste référencée par ailleurs et qu'ensuite tu le modifies… il faudrait allouer un doublet à retourner, et gérer les allocations / libérations mémoire (il me semble que le lisp utilise un ramasse miettes pour gérer la perte de référence sur ses structures dynamiques…).

Votez les 30 juin et 7 juillet, en connaissance de cause. http://www.pointal.net/VotesDeputesRN
- [^] # Re: Retour papier
  
  Posté par roger91 le 22 décembre 2015 à 10:56. Évalué à 1. Dernière modification le 23 décembre 2015 à 21:20.
  Dans elt de ma structure Doublet,je stocke un pointeur.
  J'aurai plutot:
  typedef struct Doublet {void *elt;struct Doublet *cdr;} * list;
  Pour car(doublet) si j'ai bien compris ta remarque, j'aurais donc:
```
        #define doublet ((doublet)->car)
        #define doublet ((doublet)->cdr)
```
  Puis:
```
        list cons(void * elt, const list L)
        {list doublet=malloc(sizeof(struct Doublet));
                car(Cons)->elt = elt;            
                cdr(Cons)->L = L;          
                return Cons ;}
```
  car et cdr c'est justement pour extraire respectivement le premier élément de ma liste et le reste de la liste comme en Lisp.
  
  Et en parlant de libération de la mémoire tu fais allusion à free() je suppose.
  
  Il y a t-il quelque chose qui m'aurait encore echappé ?
  Et en ce qui concerne le main qui ferait appel à ma fonction pour l'affichage comment tu le verrais ?
  
  Merci d'avance.
  - [^] # Re: Retour papier
    
    Posté par lolop (site web personnel) le 22 décembre 2015 à 14:19. Évalué à 2.
    Le hiatus pour moi: est-ce que car() retourne le Doublet (le nœud de stockage, qui est un élément de la liste), ou bien la valeur elt stockée dans le Doublet.
    
    Il me semble qu'il devrait retourner la valeur. Donc à ce moment en C tu ne peux plus écrire car(Cons)->elt car tu as déjà directement elt.
    
    https://www.google.fr/search?q=lisp+car+lang:fr
    
    Ce qui donnerais
```
list cdr(list lst)
{
return lst->cdr;
}

// int ou autre type stocké comme valeur pour elt - tu peux même en faire
// un typedef int Atom; et utiliser Atom pour le type des valeurs de elt.
int car(list lst)
{
return lst->elt;
}
```
    Tu peux faire ça avec des #define si tu veux.
    
    En tout cas, tu peux après faire des car(cdr(cdr(lst))). Par contre, à moins que tu n'autorises le stockage de Doublet dans ton elt, tu ne peux pas faire de car(cdr(car(lst))) (ce qui correspondrait à stocker non pas des listes simples d'éléments atomiques, mais des listes de listes… pour créer par exemple des structures en arbres).
    
    Après, pour ton cons, c'est juste de la création de structure en mémoire, et l'insertion en début de liste (le Doulet créé devient la tête de liste).
```
list cons(int elt, const list L)
{
Double dbl = malloc(sizeof(struct Doublet));
dbl->elt = elt; // Stockage de l'élement
dbl->cdr = L; // Mise en place de la liaison pour la liste
return (list)dbl;
}
```
    Bon, à l'usage tel quel ça promet de jolies fuites mémoires.
    
    Votez les 30 juin et 7 juillet, en connaissance de cause. http://www.pointal.net/VotesDeputesRN
    - [^] # Re: Retour papier
      
      Posté par roger91 le 22 décembre 2015 à 15:03. Évalué à 1.
      Merci lolop, ça correspond parfaitement aux spécifications.
      
      Mais il y a une ligne que je n'ai pas comprise dans ton code:
      Double dbl = malloc(sizeof(struct Doublet)); //le Double est ce une erreur de ta part ? ou il correspond à quoi ? ce ne serai pas list à la place ?
      
      Aussi si je voudrais plutot utiliser des #define à la place des fonctions pour le car et le cdr comment traduirais je cela ?
      
      En gros ma fonction serait:
```
#define
#define

typedef struct Doublet {int elt ; struct Doublet * cdr ;} * list ; list cons(int elt, const list L) { Double dbl = malloc(sizeof(struct Doublet)); dbl->elt = elt; dbl->cdr = L; return (list)dbl; }

```Il manquerait un main pour finir afin de faire appel à cette fonction cons je pense …
      
      Pour les sous listes justement l'exo d'après demande de definir à l'aide de #define, caar et cadr et construire une liste pour les tester et afficher leur résultat. Mais avant je dois parvenir à faire pour une liste simple.
      - [^] # Re: Retour papier
        
        Posté par lolop (site web personnel) le 22 décembre 2015 à 16:25. Évalué à 2. Dernière modification le 22 décembre 2015 à 16:26.
        
        Il faut bien regarder la définition des types. list est un pointeur sur struct Doublet, si tu alloues le sizeof d'un list, tu alloues juste un pointeur… si tu l'utilises comme un Doublet, tu bug.
        
        Pour la définition en macros #define, comme les fonctions ne font que retourner des attributs de structure, il suffit de les mettre dans le développement des macros:
        
        #define car(x) ((x)->elt) #define cdr(x) ((x)->cdr)
        
        (j'ai peut-être sur-parenthésé… mais avec les macros vaut mieux être prudent, tu ne sais pas dans quel contexte elles vont être utilisées)
        
        Pour les sous listes justement l'exo d'après demande de definir à l'aide de #define, caar et cadr et construire une liste pour les tester et afficher leur résultat. Mais avant je dois parvenir à faire pour une liste simple.
        
        …ce que je craignais. Il va falloir que tu transformes ton elt en potentielle liste, pour pouvoir aller piocher le premier élément qui pourra lui-même être une liste. Éventuellement jette un coup d'œil à uintptr_t comme type pour elt. Au niveau des contrôles de type, ça va être moche.
        
        Votez les 30 juin et 7 juillet, en connaissance de cause. http://www.pointal.net/VotesDeputesRN
        
        [^] # Re: Retour papier
        
        Posté par roger91 le 22 décembre 2015 à 17:59. Évalué à 1.
        
        Merci lolop pour le retour.
        
        La compilation passe plutot lorsque j'ai:
        list dbl = malloc(sizeof(struct Doublet));
        
        et je pense que c'est cela.
        Tu pourras jeter un coup d'oeil là:
        http://dept-info.labri.fr/~strandh/Teaching/MTP/Common/Strandh-Tutorial/list.html
        
        Par contre comment pourrais je implémenter mon main pour réussir à compiler mon programme afin d'afficher une liste quelconque, son car ou son cdr ? C'est un peu un casse tete cet exercice en fin de compte.
        
        Merci d'avance.
        
        [^] # Re: Retour papier
        
        Posté par lolop (site web personnel) le 23 décembre 2015 à 09:01. Évalué à 2.
        
        Tu pourras jeter un coup d'oeil là:
        
        Ça arrive au même résultat… bon, y'a pas cinquante façons de faire.
        
        C'est un peu un casse tete cet exercice en fin de compte.
        
        Non. Si tu as écrit la fonction cons() qui chaîne des éléments, utilises la en plusieurs appels pour créer une liste, et ensuite appelles car() et cdr() sur celle-ci. Au boulot.
        
        Votez les 30 juin et 7 juillet, en connaissance de cause. http://www.pointal.net/VotesDeputesRN
        
        [^] # car et cdr avec # define
        
        Posté par roger91 le 23 décembre 2015 à 20:54. Évalué à 1.
        
        Salut lolop,
        J'ai réussi à créer ma fonction cons(), car() et cdr() avec ce que tu m'a proposé et un main pour appelé ces fonctions afin d'afficher leur résultat.
        Par ailleurs, comment procéder si je voudrais faire mon car et mon cdr à l'aide de # define et non des fonctions ?
        
        Merci
        
        [^] # Re: car et cdr avec # define
        
        Posté par roger91 le 23 décembre 2015 à 21:25. Évalué à 1.
        
        Erreur de ma part. Ce n'est pas car et cdr mais…
        
        C'était plutot comment faire caar en fonction ou avec # define.
        Comment tu l'écrirais la fonction caar (l'extraction du premier élément de la sous liste) ?
        
        Merci
        
        [^] # Re: car et cdr avec # define
        
        Posté par lolop (site web personnel) le 24 décembre 2015 à 09:37. Évalué à 2.
        
        Tu poses le clavier, et prends un papier et un crayon, tu dessines des structures, des flèches pour les pointeurs, etc.
        
        Qu'est-ce que doit faire caar (de quoi il part, qu'est-ce qu'il doit retourner) ?
        
        Quelles sont les étapes pour arriver au résultat ?
        
        Dans ces étapes, y-en-a-t-il qui ont déjà été codées et qui peuvent être réutilisées ?
        
        Là, tu devrais arriver à coder caar au moins sous forme de fonction, et le tester (important).
        Ensuite, tu élimines les résultats intermédiaires en mettant leurs expressions de calcul là où ils sont utilisés, et tu devrais réussir à arriver à une seule expression… que tu peux mettre dans un #define (on peut faire des macros multilignes, mais là il ne devrait pas y en avoir besoin.
        
        Y plus qu'a. Bon exercice.
        
        Votez les 30 juin et 7 juillet, en connaissance de cause. http://www.pointal.net/VotesDeputesRN

# liste chainé bon exo

Posté par jmax17 le 22 décembre 2015 à 11:15. Évalué à 1.

Les listes chainé sont des bons exo pour manipuler les pointeurs
Il parait que le C est un langage de bas niveaux, mais on peut quand même avoir une approche objet ou au moins structuré

dans ta fonction main évite de manipuler directement les éléments de ta liste utilise des fonction comme addTail,AddHeader, getNext, delete …
considère tout les champs de la structure comme priver au moins en ecriture

j'aime bien utiliser deux structures pour ma liste
* la liste
* un élément de la liste

typedef struct _item{
 void * data;
 struct *_item next;
}item

typedef struct{
 int nbItems;
 items *First; 
}List;

List * CreateList(){
  List *l = malloc(sizeof(List));
  l->nbItems = 0;
  l-> First = NULL;
  return l;
}

Item * CreateItem(void *MyData ){
  Item *p = malloc(sizeof(Item));
  p->next = null;
  p->data = myData;  
}

void addTail(List *MyList , void *MyData){
  if (! MyList->First){ //premier ajout 
    MyList->First = CretateItem(MyData);
  }
  else{
   item *end=MyList->First;
   while(end->Next) end = end->Next;

   end->Next = CreateItem(MyData);
  } 

  MyList->nbItem++;
}

Item *GetNext(Item *p){
 if(p) return p->next;

 return null
}


void main (){
 List *l = CreateList();
//ajout des donnés 
addTail(l,data); 

  for(item *i=getNext(L->First);i;i=getNext(i))
   Show(i);
}

[^] # Re: liste chainé bon exo

Posté par roger91 le 22 décembre 2015 à 11:58. Évalué à 0.
Tu m'as l'air de très bien maitriser les listes chainées en C. Ton code me donne une idée mais l'exercice demande:
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.
Donc je dois suivre les spécifications et adapter par rapport à l'énoncé.
car(L) extrait le premier élément de notre liste L
car(cdr(L) extrait le deuxième
car(cdr(cdr L)) extrait le troisième
car(cdr(cdr(cdr L))) extrait le quatrième
Comme en Langage Lisp.
Voilà pourquoi je dois adapter ces spécifications et compléter ce qui m'a été donné comme indice et exemple pour pouvoir réussir à le faire.
```
typedef struct Doublet {void * car ; struct Doublet * cdr ;} * list ;  // la structure de base ; list est un pointeur sur un doublet

#define car(doublet)((doublet)->car) 
 //macro plutôt que fonction, pour écrire car(x) = ...
#define cdr(doublet) ((doublet)->cdr)

list cons(void *, const list);  
                                                              // prototype de la fonction cons
...

// Définition de la fonction cons ; elle renvoie un pointeur sur un doublet
list cons(void * elt, const list L)
{ list Cons = malloc(sizeof(struct Doublet));
                             // alloc mémoire d'un doublet
  car(Cons) = elt ;
  cdr(Cons) = L ;
  return Cons ; }
```
Et ma difficulté se repose justement au niveau de cette adaptation avec ces indices données pour répondre au besoin de l'exercice.
- [^] # Re: liste chainé bon exo
  
  Posté par jmax17 le 22 décembre 2015 à 13:07. Évalué à 1.
  Je ne connaissais pas les fonctions LISP.
```
void cons(item *p , List *l){
  item *prev = l->first; //sauvegarde de l'ancienne tête
  l->first = p; //ajout de la nouvelle tête
  p->next = prev; //création de la chaine
}

/// car est la fonction get first
item *car(list *l){
  return l->first;
}

//cdr est la fonction GetNext
item *cdr(item *i){
  if(i) return i->next;
   return null;
}
```
  donc pour extraire le 4eme
  cdr(cdr(cdr(car(MyList))))

# Exo résolu

Posté par roger91 le 26 décembre 2015 à 11:44. Évalué à 1.

Résolu !!
Merci pour l'aide ;)

# fonction caar

Posté par méqueline le 29 décembre 2015 à 16:23. Évalué à 1. Dernière modification le 04 janvier 2016 à 21:21.

Bonjour,

Ça m'interresse de savoir comment tu as rédsolu ton problème avec caar? j'ai le même problème et je bloque dessous plusieurs jours.

merci

j'ai tenté ce code qui construit une liste simple.

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

vous pouvez me dire comment faire pour caar ?

Merciii

Je

Suivre le flux des commentaires

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