Aide sur une liste doublement chainée

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

#include <stdio.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", 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: plus d'un noeud */
struct dlist *head = init(0);

/* Avance jusqu'au dernier noeud volontairement enlevé, sinon à
partir du dernier noeud, pointe le nouveau qui devient head*/

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.

--
FR

--
FR
Vidéos High-Tech et Jeu Vidéo
Téléchargements
Vos réponses
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
espie
Le #25282402
In article

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

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



Pas besoin du cast en C, ca ne sert qu'en C++

void print(struct dlist *p) {
printf("%d %p %pn", p->i, p->prev, p->next);
}

struct dlist *append(struct dlist *new) {


Par contre, eviter new en nom de variable est toujours une bonne idee

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



Fais ton test de pointeur nul beaucoup plus tard. Tu t'inventes des cas
particuliers pour rien.


if(new->next != NULL) { /* une address: plus d'un noeud */
struct dlist *head = init(0);

/* Avance jusqu'au dernier noeud... volontairement enlevé, sinon à
partir du dernier noeud, pointe le nouveau qui devient head*/

new->i = head->i; // jusqu'ici ca va
new->prev = head->prev;
new->next = head->next;



Apres, l'interet des listes doublement chainees, c'est generalement
d'avoir un acces direct au dernier element.

Je te recommande de voir plutot ca comme une liste circulaire. Il suffit
d'arreter le parcours lorsque tu es revenu au premier element.

Si tu veux une vraie liste doublement chainee, traditionnellement, on
se definit un entete, qui va pointer sur le 1er et le dernier element de
la liste (donc une structure separee de liste et d'element).
Xavier Roche
Le #25283702
Le 15/03/2013 12:42, a écrit :
struct dlist {



Remarque très personnelle: je n'aime pas les listes chaînées. En
général, il faut bien se poser la question de l’intérêt de la chose (ie.
le seul amha est d'insérer un élément avant la fin en O(1)), mais bon,
ce n'est pas la question là.

int i;
struct dlist *prev;
struct dlist *next;
};



Du coup "prev" sur le premier élément c'est quoi ? NULL ou le dernier
élément ? (on va supposer le dernier pour un truc circulaire)

On pourra typedef'er la struct dlist pour éviter les "struct dlist"
partout (typedef struct dlist dlist;)

struct dlist *init(int j) {
void print(struct dlist *p) {



Moi j'aurais sorti la chaine complète: (nota: une petite macro CHECK
n'est pas inutile pour valider certains invariants, histoire d'avoir un
arrêt propre en cas de problème)

#define CHECK(P) do {
assert((P)->prev->next == (P));
assert((P)->next->prev == (P));
} while(0)

static void print(dlist *p) {
dlist *const first = p;
assert(p != NULL);
do {
CHECK(p);
printf("<%d>", p->i);
p = p->next;
} while(p != first);
printf("n");
}

struct dlist *append(struct dlist *new) {



C'est un poil compliqué. Le truc, dans les listes chaînées, c'est
d'avoir un pointeur qui est positionné sur l'élément à allouer/écrire,
c'est à dire ici un dlist**.

Donc a vue de nez je commencerai en:
void append(dlist **new);
pour écrire dans un dlist*

avec du coup dans le main:
dlist *list = NULL;
append(&list, 42);

Pour l'ajout, le mieux est toujours de dessiner ce qui se passe:

départ ici----\//
=>last<=>[first]<=>second<=...

on insère la-\//
=>last<=>item===[first]<=>second<=...

Après, pour chaîner, il faut modifier quatre pointeurs: les deux
pointeurs prev/next du nouvel élément créé, qui vont pointer
respectivement sur l'ancien dernier élément, et sur le premier ; et le
chaînage next de l'ancien dernier élément et prev du premier élément,
qui vont pointer sur notre nouvel élément.

Du coup le code est très simple:

static void append(dlist **new, int j) {
/* we have to create a new item in all cases */
dlist *const item = init(j);

/*
We have to chain 'item' ; ie.
* change current last 'next' member
* change current first 'prev' member

=>last<=>[first]<=>second<=...

\//
=>last<=>item===[first]<=>second<=...
/ /
here here
*/

/* previous last element or item */
dlist *const last = *new != NULL ? (*new)->prev : item;

/* pointer to current last element pointer or pointer to item */
dlist **const plast = *new != NULL ? &(*new)->prev : new;

/* place new item */
*plast = item;

/* chain new item */
item->prev = last;
item->next = *new;

/* previous last 'next' element and head 'previous' element to new one */
last->next = (*new)->prev = item;

CHECK(item);
CHECK(*new);
CHECK(last);
}

Et plutôt que de faire une boucle pour tester, un programme qui prend
des arguments entiers me semblerait mieux:

int main(int argc, char **argv) {
dlist *list = NULL;
int i;
for(i = 1 ; i < argc ; i++) {
int num;
if (sscanf(argv[i], "%d", &num) == 1) {
printf("=> %dn", num);
append(&list, num);
print(list);
} else {
return EXIT_FAILURE;
}
}
return EXIT_SUCCESS;
}

$ chain_list 1 2 3 4
=> 1
<1>
=> 2
<1><2>
=> 3
<1><2><3>
=> 4
<1><2><3><4>
Publicité
Poster une réponse
Anonyme