Aide sur une liste doublement chainée

[vivel...@orange.fr]

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\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: 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

[Marc Espie]

In article <m2hakcj...@orange.fr>, <vivel...@orange.fr> wrote:
>
>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;
>}

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

>void print(struct dlist *p) {
> printf("%d %p %p\n", 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 15/03/2013 12:42, vivel...@orange.fr 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("=> %d\n", 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>