Aide sur une liste doublement chainée

In article <m2hakcj3dg.fsf@orange.fr>, <vivelesexe@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 %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).

Le 15/03/2013 12:42, vivelesexe@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("=> %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>