comment utiliser un pointeur vers un pointeur à insérer dans une liste chaînée

Question

Think est une fonction permettant d'insérer un nouvel élément dans l'ordre de son nom. Je savais comment le faire si j'utilise une condition d'insertion si au départ et autres. Mais on m'a demandé de fusionner le si et le while en une seule boucle while. Comment est-ce que j'ai pu intégrer la fonction d'insertion dans une boucle while avec le pointeur au pointeur?

person* insert_sorted(person *people, char *name, int age) 
{ 
    person *p=NULL;//,*t=NULL,*q=NULL; 
    person *ptr= people; 
    person **ptr2ptr=&ptr; 

    p=malloc(sizeof(person)); 

    if (p == NULL){ 
     printf("malloc() failed\n"); 
     return NULL; 
    } 
    else { 
     p->name = name; 
     p->age = age; 

     if (people == NULL){ // empty list 
      people = p; 
      people->next =NULL; 
     } 
     else{ 
      *ptr2ptr = ptr; 
      while((*ptr2ptr) !=NULL) 
      { 
       if (compare_people(p, people)<=0) // insert at the start 
        break; 
       else if ((*ptr2ptr)->next == NULL) //insert at the end 
        break; 
       else if (compare_people(*ptr2ptr, p) <=0 && compare_people(p, (*ptr2ptr)->next)<=0)//insert at the middle 
        break; 
       *ptr2ptr = (*ptr2ptr)->next; 
      } 
      //insert at the end 
      p->next = (*ptr2ptr)->next; 
      (*ptr2ptr)->next = p; 

     } 
    } 

Answer 1

ici j'ai trouvé la réponse la plus utile à cette question: http://www.mvps.org/user32/linkedlist.html

 ptr2ptr = &people; 
     while (*ptr2ptr!=NULL && compare_people(*ptr2ptr,p)) { 
      ptr2ptr = &(*ptr2ptr)->next; 
     } 
     p->next = *ptr2ptr; 
     *ptr2ptr = p; 

Answer 2

eInstead d'essayer de trouver l'élément person dans la liste qui n'a pas de successeur, essayez de trouver le premier pointeur NULL. Quelque chose comme ça (non testé):

void insert_sorted(person **p, char *name, int age) 
{ 
    while (*p) { 
    p = &(*p)->next; 
    } 
    *p = malloc(...); 
    /* ... */ 
} 

Ce genre de problème est généralement mieux résolu avec un stylo un papier, puis dessiner quelques boîtes et des flèches. L'idée est que votre pointeur 'p' ne pointe plus sur un person spécifique mais plutôt sur un pointeur qui pointe vers un person.

Answer 3

Il peut y avoir quelques options.

Je déplacerais le si à l'intérieur de la fonction compare_people à condition que vous puissiez le changer. Après tout, ajouter le tout premier élément dans une liste revient à ajouter un nouvel élément "haut de la liste" (du moins de la liste). Je sais que cela peut être vu comme "tricher". Et c'est, en effet!

Vous pouvez créer un élément de liste "faux" qui sera toujours testé pour être le premier (ou le dernier) de la liste triée (comme avec un nom vide). Ainsi, la liste ne sera jamais vide et il n'y aura jamais de test de "vérification d'une liste vide". Bien sûr, le contenu de ce faux objet doit être conforme à la sémantique de la fonction compare_people.

À un coût légèrement supérieur à O (n), O (n * log (n)), vous pouvez utiliser une structure de support temporaire (comme un tableau de pointeurs) et qsort() de stdlib. h afin de garder la liste triée.

Enfin, implémentez insertion sort qui exploiterait le fait que l'ensemble d'origine est déjà trié avant d'insérer le nouvel élément.

Answer 4

La fonction peut être écrit de la manière suivante (sans test parce que je ne sais pas quelques définitions de la liste)

person * insert_sorted(person **people, char *name, int age) 
{ 
    person *p = malloc(sizeof(person)); 

    if (p == NULL) 
    { 
     printf("malloc() failed\n"); 
    } 
    else 
    { 
     p->name = name; 
     p->age = age; 

     person *prev = NULL; 
     person *current = *people; 

     while (current && !(compare_people(p, current) < 0)) 
     { 
      prev = current; 
      current = current->next; 
     } 

     p->next = current; 
     if (prev == NULL) *people = p; 
     else prev->next = p; 
    } 

    return p; 
}  

Et la fonction devrait être appelée comme

insert_sorted(&people, name, age); 
       ^^^^^^^ 

Answer 5

Sans test: La façon dont vous utilisez le pointeur vers le pointeur ne fait pas usage de l'indirection

person* insert_sorted(person** people, char *name, int age) { 
    person* added = malloc(sizeof(person)); 
    added->name = name; 
    added->age = age; 
    added->next = NULL; 

    person* previous = NULL; 
    person* current = *people; 
    while (current && compare_people(current, added) <= 0) { 
     previous = current; 
     current = current->next; 
    } 

    if (!people) { 
     *people = added; 
    } else { 
     previous->next = added; 
     added->next = current; 
    } 

    return added; 
} 

Answer 6

. Vous écrivez seulement (*ptr2ptr) où vous auriez normalement écrit'ptr`. L'idée d'utiliser un pointeur vers un pointeur de nœud est qu'en ajoutant un niveau d'indirection, vous pouvez accéder et modifier le pointeur de tête à partir de la fonction appelante. Si vous passez simplement un pointeur de noeud, toutes les modifications apportées à ce pointeur sont locales à la fonction insert et ne mettront pas à jour le pointeur de tête de votre liste dans la fonction d'appel si nécessaire.

Votre signature de fonction doit déjà passer un pointeur vers un pointeur de nœud:

void insert(person **p, const char *name, int age); 

et l'appeler comme ceci:

person *head = NULL; 

insert(&head, "Betty", 26); 
insert(&head, "Ralph", 23); 
insert(&head, "Chuck", 19); 
insert(&head, "Alice", 42); 
insert(&head, "Simon", 34); 

Lorsque vous entrez dans le auj, p est l'adresse de head en la fonction d'appel. Comme vous itérer la liste avec

p = &(*p)->next; 

*p tenir l'adresse du pointeur next du noeud précédent. p est un pointeur «d'où»: Il contient l'adresse du pointeur qui pointe vers l'ode que vous traitez. Cela signifie qu'une liste vide n'est plus un cas particulier.

Votre fonction nécessite de renvoyer le nouveau pointeur de tête. Il est facile d'oublier de l'assigner et cela ajoute également de la redondance à l'appel. L'approche pointeur vers point fixe également cela.

Voilà comment votre code d'insertion pourrait ressembler à une fonction qui prend un pointeur vers pointeur comme argument:

struct person { 
    const char *name; 
    int age; 
    person *next; 
}; 

int compare(const person *p1, const person *p2) 
{ 
    return strcmp(p1->name, p2->name); 
} 

person *person_new(const char *name, int age) 
{ 
    person *p = malloc(sizeof(*p)); 

    p->name = name; 
    p->age = age; 
    p->next = NULL; 

    return p; 
} 

void insert(person **p, const char *name, int age) 
{ 
    person *pnew = person_new(name, age); 

    while (*p && compare(*p, pnew) < 0) { 
     p = &(*p)->next; 
    } 

    pnew->next = *p; 
    *p = pnew; 
}