Discussion :

[Stillbogus]

J'aurais besoin d'un coup de main à déboguer cette liste doublement chainée, en particulier les fonctions append(), appbeg() voici le code:

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
 
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
 
struct dlist {
    int i;
    struct dlist *prev;
    struct dlist *next;
}; 
 
struct dlist *init(int j) {
    struct dlist *p = (struct dlist *) malloc(sizeof(struct dlist));
    p->i = j;
    p->prev = p->next = NULL;
    return p;
}
 
void print(struct dlist *p) {
    printf("%d %p %p\n", p->i, p->prev, p->next); 
}
 
struct dlist *append(struct dlist *new) {
 
	struct dlist *first = init(0), *head = init(0);
 
	if(new->next == NULL) {
		first->i = new->i;
		first->prev = new->prev;
		first->next = new->next; // jusqu'ici ca va
		first->prev->prev = NULL; // ici et ensuite je ne maîtrise plus
		first->next->next = new;
		return first;
	}
 
	if(new->next != NULL) { /* une address */
		struct dlist *head = init(0);
/* Avance jusqu'au dernier noeud... volontairement enlevé, sinon à partir du dernier noeud, pointe le nouveau */
		new->i = head->i; // jusqu'ici ca va
		new->prev = head->prev;
		new->next = head->next;
/* Puis la je ne maitrise plus */
		return new;
	}
	return new; 
}
 
struct dlist *appbeg(struct dlist *old) { /* celle la plante aussi */
	struct dlist *new = init(0); 
	new->i = old->i;
	new->prev = old->prev;
	new->next = old->next;
	new->prev->next= old;
	new->next->prev = old;
	return new;
}
 
int main(int argc, char **argv) {
    int i = 0;
    while(i++ < 10000) print(append(init(0)));
    return 0;
}

J'ai déjà trouvé plusieurs exemples de code sur l'Internet, mais je préférerais travailler sur ce bout de code.

[moins1]

J'ai déjà trouvé plusieurs exemples de code sur l'Internet, mais je préférerais travailler sur ce bout de code.

Pour ça, du travail y'en a à faire.

Quelle est la différence entre head et first?

Si on utilise seulement first. Tu va devoir l'initialiser c'est sûr mais seulement une fois. Là ce que je vois dans ton code: tu recréer first à chaque append() en appelant init().

Quand tu vas faire append(), la fonction devrait vérifier si first est NULL. Si c'est le cas: c'est une liste vide donc first va égaler le nouveau noeud. Si first est différent de NULL, là tu vas devoir parcourir la liste jusqu'au dernier noeud et ajouter le nouveau à la fin.

Pour parcourir la liste. Genre

Code :

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

1
2
3
4
5
6
 
p = first;
while(p->next != NULL)
{
    p = p->next;
}

Enfin ça devrait ressembler à ça.



EDIT: N'oublie pas de vider la liste.

[diogene]

Code :

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

		first->prev->prev = NULL; // ici et ensuite je ne maîtrise plus

first vient d'être créé par init() donc first->prev est obligatoirement à NULL et on ne peut déréférencer NULL -> plantage.
Même remarque pour le plantage de appbeg()

Globalement, le code est difficile à suivre. La première raison est qu'il se base sur la même structure de données pour représenter la liste (struct dlist *) et pour représenter les maillons de la liste (struct dlist). Pourtant, conceptuellement, ce sont deux choses différentes et dans le code il n'apparait pas à l'évidence si un struct dlist * est la liste ou un pointeur sur un maillon.
Il faut les différentier ce qui permettra aussi de faire apparaitre dans la représentation de la liste les particularités de celle-ci (par exemple un pointeur sur le dernier maillon facilitera grandement la fonction append().

Faire ceci demande de revisiter le code actuel, Autant le faire maintenant alors que le code n'est pas trop volumineux, tu y gagneras beaucoup ensuite en simplicité et clarté. C'est un bon investissement !

Pour t'aider dans cette voie, une trame possible peut être :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
typedef struct maillon
{
    int i;
    struct maillon *prev;
    struct maillon *next;
} Maillon;
typedef struct
{
    Maillon * first;
    Maillon * last;
} Liste;

La fonction init(), qui crée la liste, devrait créer une liste vide. C'est logique. Par sa fonction, son nom devrait être changé.

Code :

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

1
2
3
4
5
6
7
8
9
10
Liste * creerListe(void)
{ 
   Liste * p= malloc(sizeof *p); // ou si on préfère malloc(sizeof(Liste))
   if(p!= NULL)
   {
      p->first = NULL;
      p->last = NULL;
   }
   return p;
}

A noter que dans cette configuration, il n'est pas obligatoire d'allouer la liste dynamiquement. On peut avoir pour la créer Liste liste = {NULL, NULL};.

Il sera peut être préférable de faire aussi une fonction Maillon * creerMaillon(int val).

Ta fonction print() affiche en fait un maillon, elle devient :

Code :

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

1
2
3
4
void printMaillon( Maillon * p)
{
   printf("%d %p %p\n", p->i, p->prev, p->next);
}

à différentier d'une fonction qui afficherait la liste :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
void printListe(Liste * liste)
{
   if(liste != NULL)
   {
     Maillon * p = liste->first;
     while(p != NULL)
     {
         printMaillon(p);
         p = p->next;
     }
   }
}

La fonction append() prend pour prototype Maillon * append( Liste * liste, int val). Elle sera beaucoup plus simple à écrire (et à relire) du fait du champ last dans Liste. Sa trame sera :

- Créer un maillon en utilisant la fonction creerMaillon(). La fonction retourne p.
- Si la création a échoué (p==NULL), sortir en retournant p (qui est NULL, c'est
      ce NULL qui indiquera l'échec de l'append()) 
- Sinon
   - Si la liste est vide (liste->last==NULL), mettre dans liste->first et 
         liste->last l'adresse du maillon (p) et sortir en retournant l'adresse p 
         du maillon (p!= NULL ce qui indiquera le succès de l'append())
   - Sinon, ajouter le maillon en queue :
          - placer dans l'actuel dernier maillon de la liste (d'adresse liste->last) le champ
                next sur p 
          - placer dans p->prev l'adresse de l'actuel dernier maillon
          - changer l'adresse du dernier maillon de la liste (liste->last) par celle
                du nouveau maillon de queue (p)
          - sortir en retournant l'adresse p du maillon (pour indiquer le succès de 
                l'append())

[codes non testés]

[Médinoc]

+1, séparer les structures Maillon et Liste est pratiquement indispensable.

Aussi, quelques const ne seraient pas de refus sur les fonctions d'affichage, puisqu'elles ne sont pas censées modifier la liste ou les maillons.