les listes chainees - Page 1

est ce que quelqu'un aurait de bonnes adresses a propos des structures autoréferrentielles, parce que je m'embrouille un peu les pates !
Du genre avec quelques exemples etc.

merci d'avance !

un exemple :

typedef struct element {
  struct element * previous;
  struct element * next;
}element;

void _main(void) {
  element el1,el2;
  el1.next = &el2;
  el1.previous = NULL;
  el1.el2->previous = &el1;
// etc... etc... n'importe quoi etc...
}

Merci Lionel !
Et sans vouloir abuser tu pourrais me donner un petit exemple de declaration avec un pointeur et malloc s'il te plait?

un exemple avec malloc et pointeur :

typedef struct element {
  struct element * previous;
  struct element * next;
}element;

void _main(void) {
  element *el1;
  el1 = (element*)malloc(sizeof(element));
  el1->previous = NULL;
  el1->next = NULL;
// etc... etc... n'importe quoi etc...
  free(el1);
}

Et par la suite si je veux creer un nouveau maillon, il faut que j'utilise un pointeur temporaire et que je renseigne les elements next et previous bien comme il faut c'est ça ?
Comme ça c'est bon ?

struct _LISTE_UNITE *Nouveau;
	
	Nouveau = (struct _LISTE_UNITE*)malloc(sizeof(struct _LISTE_UNITE));

et ensuite j'ai plus besoin de Nouveau c'est ça?

./2 :
- el1.el2->previous = &el1; + el1.next->previous=&el1; ?

erf bien vu
Thepro va donc continuer l'explication, je suis trop naze là

./6:
the pro, comment ça se fait qu'on utilise el1.el2->previous ?
ça existe pas ça pourtant ?

Ha non !
désolé j'avais pas calculé le - et le + !
Et sinon dans le ./5 est ce que le code est bon ?
Au fait c'est quoi la difference entre structure.next et structure->next ?

non il disait que je m'etais planté lamentablement bien sur qu'on ne peut pas

structure.next c'est quand structure est un élément structure, structure->next c'est quand structure est un pointeur vers une structure

Merci limmt !(et lionel et the pro en passant !)
Et quand je cree en pointeur de type structure pour creer un nouveau maillon, je peux le liberer apres ?

si tu libere quelque chose, tu ne peut plus t'en servir, donc dans le cas d'une liste chainée tu dois garder toutes les allocations de chaque maillon intactes et liberer seulement a la fin quand tu detruit la liste (avec une fonction recursive) ou bien lorsque que tu detruit un maillon.
Mais au fait les listes chainées c'est moisi sur TI avec cette methode d'allouer chaque maillon car tu vas pouvoir en allouer maximum 2000 (nombre de handles max il me semble)

./13
Bah j'ai pas trop le choix je vois pas d'autres methodes pour ce que je veux faire, car un tableau ne conviendrait pas. Et puis 2000, c'est suffisant !
Mais dans mon cas

struct _LISTE_UNITE *Nouveau; 
	 
	Nouveau = (struct _LISTE_UNITE*)malloc(sizeof(struct _LISTE_UNITE));

Si j'ai renseigner les elements previous et next de la structure, ainsi que dans le maillon precedent, est ce que je peux me debarasser de Nouveau ?(pour moi c'est ok, mais je prefere demander !)
Merci !

Nouveau est une variable de type pointeur, tu n'es pas obligé de l'utilisé mais il ne faut pas le freeé temps que tu utilise l'espace qu'il pointe (avec un autre pointeur ...).

Tu peux donc réutiliser Nouveau pour un autre malloc mais attention aux free à la fin.

C'est peut-être un peu bourrin de commencer directement par une liste doublement chainée (même si c'est ce que j'avais fait en cours de système).
Enfin, l'avantage, c'est qu'on peut faire n'importe quelle manipulation à peu près n'importe où, une fois que lss fonctions sont définies.

Voici un petit exemple, avec des typedef en prime parce que je trouve que ça simpifie: typedef struct elementDbl ST_ELEMENTDBL, *PT_ELEMENTDBL; struct elementDbl {      PT_ELEMENTDBL pt_prev;      PT_ELEMENTDBL pt_next;      float fMyData; //Histoire de mettre quelque chose dans la liste }; //Pour créer un nouvel élément PT_ELEMENTDBL NewElement(float fData) {      PT_ELEMENTDBL pt_returnVal;            //Attention, on alloue bien la taille de la structure et non du pointeur      pt_returnVal = (PT_ELEMENTDBL)malloc(sizeof(ST_ELEMENTDBL));      if(pt_returnVal) {           pt_returnVal->pt_prev = NULL;           pt_returnVal->pt_next = NULL;           pt_returnVal->fMyData = fData;      }      return pt_returnVal; } //Pour insérer un élément à gauche d'un élément existant //(Retourne pt_newElement si OK, NULL si erreur (par exemple, pt_newElement non-orphelin) PT_ELEMENTDBL InsertLeft(PT_ELEMENTDBL pt_list, PT_ELEMENTDBL pt_newElement) {      //Erreur si pt_newElement n'est pas orphelin      if(pt_newElement==NULL || pt_newElement->pt_prev!=NULL || pt_newElement->pt_next!=NULL) {           return NULL;      }      pt_newElement->pt_prev = pt_list;      pt_newElement->pt_next = pt_list->pt_next;      pt_list->pt_next = pt_newElement;      if(pt_newElement->pt_next) {           pt_newElement->pt_next->pt_prev = pt_newElement;      }      return pt_newElement; } //Pour insérer un élément à droite d'un élément existant PT_ELEMENTDBL InsertRight(PT_ELEMENTDBL pt_list, PT_ELEMENTDBL pt_newElement) {      //Erreur si pt_newElement n'est pas orphelin      if(pt_newElement==NULL || pt_newElement->pt_prev!=NULL || pt_newElement->pt_next!=NULL) {           return NULL;      }      pt_newElement->pt_prev = pt_list->pt_prev;      pt_newElement->pt_next = pt_list;      pt_list->pt_prev = pt_newElement;      if(pt_newElement->pt_prev) {           pt_newElement->pt_prev->pt_next = pt_newElement;      }      return pt_newElement; } //Petites fonctions pour obtenir la tête et la queue d'une liste PT_ELEMENTDBL GetFirstElement(PT_ELEMENTDBL pt_list) {      if(pt_list==NULL) {           return NULL;      }      while(pt_list->pt_prev != NULL) {           pt_list = pt_list->pt_prev;      }      return pt_list; } PT_ELEMENTDBL GetLastElement(PT_ELEMENTDBL pt_list) {      if(pt_list==NULL) {           return NULL;      }      while(pt_list->pt_next != NULL) {           pt_list = pt_list->pt_next;      }      return pt_list; }
A ce moment-là, tu n'as même pas besoin de retenir le pointeur Nouveau, car tu peux directement ajouter à la liste avec

InsertRight(pt_dernierElement, NewElement(fMesDonnees));
pt_dernierElement = GetLastElement(pt_dernierElement);

Tu vois, en gérant bien les listes chaînées, tu n'as besoin que d'un seul pointeur.
En fait, avec ces fonctions de base, tu peux à peu près tout faire au niveau élément. Pour concaténer deux listes, c'est pas bien compliqué non plus (il faut toucher aux pointeurs de la tête d'une liste et la queue de l'autre).

PS: mettre un nom spécial aux variables pointeurs, ça aide.

valentin > le 2000 vient du fait qu'il ne peut y avoir que (à peu pres) 2000 éléments alloués en même temps avec un malloc sur une ti
donc ca veut dire qu'il faut enlever tout ce qui a été alloué par le systeme d'exploitation, enlever chaque fichier présent dans la calculatrice
ca veut dire qu'au final tu auras bien moins de 2000 éléments disponibles
donc pour des grosses listes chainées c'est une tres mauvaise idée (je pense pas qu'il faille depasser quelques centaines d'elements)

par contre si tu veux faire des grosses listes chainées, tu peux aussi reserver en une seul fois un grand tableau qui va contenir chacun de tes maillons (que tu devra chainer entre eux)
ca va te faire une liste ou tu as tous tes maillons dedans, et ensuite il te suffit de les faire passer à ta liste en changeant les pointeurs, et pour les liberer tu les remet dans la grosse liste du debut
mais avec cette methode tu perds le principe ou tu n'alloues que la méméoire que tu utilises. mais les listes chainées ont plein d'autres avantages

pas besoin de récursion pour tout libérer:

void free_list(element *head) {
  element *nxt;
  while(nxt=head->next) {
    free(head);
    head=nxt;
  }
  free(head);
}

moi je fais ça (de mémoire)

edit: rah merde up