La création et la Compréhension des listes liées à des structures en C

Listes chaînées - 101 - liée Individuellement des Listes de

C'est une longue réponse. La raison j'ai fait tellement de détail est qu'il y a un grand nombre de liens de la liste de questions qui, je l'espère, de répondre sur place, avec le bon contexte.

Lorsque j'ai appris le C, j'ai eu du mal avec les pointeurs. Cependant, après la mise en œuvre d'une liste liée, j'ai enfin commencé à saisir la notion de pointeurs. Maître des listes liées est une bonne chose en C, et il va vous aider à être à l'aise avec les pointeurs. Quand les choses semblent confus, prenez un crayon et du papier et de l'esquisse d'un schéma d'une liste et les liens associés aux nœuds. Il m'arrive de le faire lorsque je travaille avec des complexes liste des implémentations.

Une liste chaînée est une façon de stocker des enregistrements de données. Contrairement à un tableau où tous les éléments sont logés dans un bloc de mémoire contiguë de mémoire, lié à des éléments de la liste occuper aléatoire des fragments de mémoire.

Il y a deux types de base de la liste liée; une liste liée individuellement, et une liste à double liaison. La différence est que une liste liée individuellement ne peut être parcouru dans un sens; alors qu'une liste à double liaison peut être parcouru dans les deux sens.

Une liste liée individuellement est accessible par l'intermédiaire de son "chef" pointeur, ou un pointeur à la tête d'une liste de noeuds. Une liste à double liaison peut également être consulté par l'intermédiaire de son "chef" pointeur, ou par l'intermédiaire de sa "queue" pointeur.

Contrairement à un tableau où chaque élément de la matrice peuvent être directement adressée par son index de tableau, la liste des éléments à accès séquentiel.

Voici une présentation d'une liste liée individuellement:

            Node #1      Node #2      Node #3      EndOfList
            ----------   ----------   --------     ---------
HEADPTR-->  NEXTPTR-->   NEXTPTR-->   NEXTPTR-->   NULL
            DataPayload  DataPayload  DataPayload

Chaque nœud dans la liste, avec sa charge utile de données, est allouée séparément. Un nœud de la structure (C) pourrait ressembler à quelque chose comme ceci:

    typedef struct NODE_PAYLOAD_S
       {
       /* Data Payload (defined by coder) */
       char name[10];
       char desc[10];
       int hours;
       int workordernum;
       } NODE_PAYLOAD_T;

    typedef struct LIST_NODE_S
       {
       /* Next-node pointer */
       struct LIST_NODE_S *next;     /* pointer to the next node in the list. */
       NODE_PAYLOAD_T      payload;  /* Data Payload (defined by coder) */
       } LIST_NODE_T;

Pour initialiser une liste liée individuellement de la structure ci-dessus:

LIST_NODE_T *listHead = NULL;

'"' est maintenant un pointeur vers une liste liée (sans nœuds).

Ici est de savoir comment ajouter un nouveau nœud à la tête de cette liste:

int LIST_InsertHeadNode(
      LIST_NODE_T **IO_head,

---

Q: Pourquoi est un "double-pointeur" nécessaire (c'est à dire: LIST_NODE_T **...)? Pourquoi ne pas utiliser un "simple" de niveau pointeur (c'est à dire: LIST_NODE_T *...)?

Un: Un "simple" pointeur sur la liste de la tête ne serait pas suffisant pour cette opération. Plus précisément, cette opération désigne une nouvelle "tête de nœud". Cela signifie que cette fonction doit modifier le pointeur qui pointe vers le nœud de tête.

AVANT:

                         Node #Y      Node #Z      EndOfList
                         ----------   ----------   ---------
             HEADPTR-->  NEXTPTR-->   NEXTPTR-->   NULL
                         DataPayload  DataPayload  

APRÈS:

            New Node      Node #Y      Node #Z      EndOfList
            ----------   ----------   --------     ---------
HEADPTR-->  NEXTPTR-->   NEXTPTR-->   NEXTPTR-->   NULL
            DataPayload  DataPayload  DataPayload

Note qu'avant, HEADPTR a été pointant vers "Node #Y'; puis après, HEADPTR est pointant vers 'nœud'. Lorsque cette fonction est appelée, l'adresse de la "pointeur est passé, permettant à cette fonction pour modifier l'emplacement où le" pointeur pointe. Dans otherwords, l'adresse de la "pointeur est passé dans cette fonction, qui est représenté (en interne pour cette fonction) comme un pointeur vers le" pointeur (pointeur vers un pointeur). C'est pourquoi il est un "double-pointeur".

---

      char         *I__name,
      char         *I__desc,
      int           I__hours,
      int           I__workordernum
      )
   {
   int rCode=0;
   LIST_NODE_T *newNode = NULL;

   /* Allocate memory for new node (with its payload). */
   newNode=malloc(sizeof(*newNode));
   if(NULL == newNode)
      {
      rCode=ENOMEM;   /* ENOMEM is defined in errno.h */
      fprintf(stderr, "malloc() failed.\n");
      goto CLEANUP;

---

Q: Qu'est-ce " goto NETTOYAGE;' entreprise?

Un: Le langage C, à la différence de C++ et de JAVA, n'a pas de notion d '"exception". La vérification des erreurs en C est critique. Il y a un certain nombre de raisons que le malloc() la fonction peut échouer, et si c'est le cas, le code est à manipuler avec autant de tact que possible. Le "goto NETTOYAGE' instruction provoque le flux de programme normal d'ignorer le code de saut à la 'NETTOYAGE:' étiquette à l'intérieur de cette fonction, ci-dessous).

Évidemment, si la fonction malloc() a échoué, il serait imprudent d'essayer d'initialiser le pointeur NULL (retourné par l'échec de malloc) avec les lignes qui suivent immédiatement. Donc, il est important de détourner le flux du programme d'ignorer cette initialisation (et sur le lien qui vient plus tard).

Il n'y a rien de spécial à propos de la 'NETTOYAGE:' étiquette. J'ai pu l'ont appelé 'ERREUR:', 'SORTIE', 'TERMINER:', 'LIAHONA:', 'MY_BAD" ou toute autre chose qui convenait à mon plaisir. (Les étiquettes n'ont pas à être en majuscules, ni ont-ils être mis à la marge de gauche. Cependant, mon style est de faire de sorte qu'ils se démarquent.)

Étiquettes, tels que le 'NETTOYAGE' a un champ d'application limité aux frontières de la fonction où elles sont placées, et qui permet à chaque fonction pour un NETTOYAGE de: "l'étiquette (si nécessaire).

---

      }

   /* Initialize the new node's payload. */       
   snprintf(newNode->payload.name, sizeof(newNode->payload.name), "%s", I__name);
   snprintf(newNode->payload.desc, sizeof(newNode->payload.desc), "%s", I__desc);
   newNode->payload.hours = I__hours;
   newNode->payload.workordernum = I__workordernum;

   /* Link this node into the list as the new head node. */
   newNode->next = *IO_head;
   *IO_head = newNode;

CLEANUP:

   return(rCode);
   }

La fonction ci-dessus pourrait être appelé comme suit:

#include <stdio.h>
#include <errno.h>

int LIST_InsertHeadNode(LIST_NODE_T **, char *, char *, int, int);

int main(void)
   {
   int rCode=0;
   LIST_NODE_T *listHead = NULL;

   rCode=LIST_InsertHeadNode(&listHead, "Mahonri", "Jareds Bro", 4, 2421);
   if(rCode)
      {
      fprintf(stderr, "LIST_InsertHeadNode() reports: %d\n", rCode);
      goto CLEANUP;
      }

CLEANUP:

   return(rCode);
   }

La LIST_InsertHeadNode() la fonction peut être appelée plusieurs fois. Chaque appel d'ajouter un nouveau nœud à la liste. Le nouveau nœud est placé à la "tête" de la liste, ce qui a pour effet de pousser le reste des nœuds plus bas dans la liste.

Après l'ajout de plusieurs nœuds de la liste, il peut être bon pour accéder à la liste; peut-être d'imprimer la charge utile de chaque nœud:

int PrintListPayloads(
      LIST_NODE_T *head;
      )
   {
   int rCode=0;
   LIST_NODE_T *cur = head
   int nodeCnt=0;

   while(cur)
      {
      ++nodeCnt;
      printf("%s, %s, %d, %d\n",
            cur->payload.name,
            cur->payload.desc,
            cur->payload.hours,
            cur->payload.workordernum
            );
       cur=cur->next;
       }

    printf("%d nodes printed.\n", nodeCnt);

   return(rCode);
   }

La fonction ci-dessus peut être appelée main():

#include <stdio.h>
#include <errno.h>

int LIST_InsertHeadNode(LIST_NODE_T **, char *, char *, int, int);
int PrintListPayloads(LIST_NODE_T *);

int main(void)
   {
   int rCode=0;
   LIST_NODE_T *listHead = NULL;

   /* Insert a linked-list node. */
   rCode=LIST_InsertHeadNode(&listHead, "Mahonri", "Jareds Bro", 4, 2421);
   if(rCode)
      {
      fprintf(stderr, "LIST_InsertHeadNode() reports: %d\n", rCode);
      goto CLEANUP;
      }

   /* Insert a linked-list node. */
   rCode=LIST_InsertHeadNode(&listHead, "Joe", "CEO", 5, 2419);
   if(rCode)
      {
      fprintf(stderr, "LIST_InsertHeadNode() reports: %d\n", rCode);
      goto CLEANUP;
      }

   /* Insert a linked-list node. */
   rCode=LIST_InsertHeadNode(&listHead, "Eve", "Mother", 24, 2);
   if(rCode)
      {
      fprintf(stderr, "LIST_InsertHeadNode() reports: %d\n", rCode);
      goto CLEANUP;
      }

   rCode=PrintListPayloads(listHerad);
   if(rCode)
      {
      fprintf(stderr, "PrintListPayloads() reports: %d\n", rCode);
      goto CLEANUP;
      }

CLEANUP:

   return(rCode);
   }

D'ajouter des nœuds à la tête d'une liste [ie: LIST_InsertHeadNode()] est un moyen pour ajouter des nœuds. Cependant, il y a des moments où l'ajout de nœuds à l'autre extrémité de la liste (c'est à dire: la liste "queue") est préférable. Le code ci-dessous montre comment c'est fait.

Tout d'abord, une fonction qui sera de retour l'actuel "queue nœud" de la liste.

   int LIST_GetTailNode(
         LIST_NODE_T  *I__listHead,   /* The caller supplied list head pointer. */
         LIST_NODE_T **_O_listTail    /* The function sets the callers pointer to the
                                         last node. */
         )
      {
      int rCode=0;
      LIST_NODE_T *curNode = I__listHead;

      /* Iterate through all list nodes until the last node is found. */
      /* The last node's 'next' field, which is always NULL. */
      if(curNode)
         {
         while(curNode->next)
            curNode=curNode->next;
         }

      /* Set the caller's pointer to point to the last (ie: tail) node. */
      if(_O_listTail)
         *_O_listTail = curNode;

      return(rCode);
      }

Ensuite, une fonction qui permet d'insérer un nœud à la queue de la liste.

   int LIST_InsertTailNode(
      LIST_NODE_T **IO_head,
      char         *I__name,
      char         *I__desc,
      int           I__hours,
      int           I__workordernum
      )
   {
   int rCode=0;
   LIST_NODE_T *tailNode;
   LIST_NODE_T *newNode = NULL;

   /* Get a pointer to the last node in the list. */
   rCode=LIST_GetTailNode(*IO_head, &tailNode);
   if(rCode)
      {
      fprintf(stderr, "LIST_GetTailNode() reports: %d\n", rCode);
      goto CLEANUP;
      }

---

Remarque importante: La LIST_GetTailNode() va définir le tailNode pointeur vers le dernier nœud de la liste liée; -moins - il n'y a pas de nœuds dans la liste. Lorsque la liste est vide, LIST_GetTailNode() permet de définir la tailNode pointeur à NULL.

---

   /* Allocate memory for new node (with its payload). */
   newNode=malloc(sizeof(*newNode));
   if(NULL == newNode)
      {
      rCode=ENOMEM;   /* ENOMEM is defined in errno.h */
      fprintf(stderr, "malloc() failed.\n");
      goto CLEANUP;
      }

   /* Initialize the new node's payload. */       
   snprintf(newNode->payload.name, sizeof(newNode->payload.name), "%s", I__name);
   snprintf(newNode->payload.desc, sizeof(newNode->payload.desc), "%s", I__desc);
   newNode->payload.hours = I__hours;
   newNode->payload.workordernum = I__workordernum;

   /* Link this node into the list as the new tail node. */
   newNode->next = NULL;
   if(tailNode)
      tailNode->next = newNode;
   else

Cette "autre chose" cas indique se produit lorsque tailNode est NULL, ce qui signifie que (pour l'instant) de la liste liée a pas de nœuds. Dans ce cas, ce nœud sera la première (la tête) nœud dans la liste (ou la dernière). Ainsi, l'appelant "la Liste Tête de" pointeur est mis à jour pour indiquer que ce nouveau nœud est maintenant à la tête de nœud.

      *IO_head = newNode;

CLEANUP:

   return(rCode);
   }

La LIST_InsertTailNode() la fonction est appelée de la même façon LIST_InsertHeadNode() est appelée. La seule différence est que, avec LIST_InsertTailNode(), le nouveau nœud est inséré à la liste de la queue, plutôt qu'à la liste du tête de.

OK, alors maintenant, vous pouvez insérer un nouveau nœud à la tête ou à la queue de la liste. Ce sujet de l'insertion d'un nouveau nœud quelque part dans le milieu de la liste?

Par exemple, supposons que vous voulez avoir une liste où tous les nœuds sont triés par certains de terrain dans la charge utile, comme 'nom'. Alors qu'il est possible d'ajouter tous les nœuds, puis trier la liste par la suite; il est beaucoup plus facile à insérer chaque nouveau nœud dans la liste dans sa place. Ce faisant, la liste sera toujours maintenu dans l'ordre automatiquement.

L'accomplissement de ce qui est fait en deux étapes. Tout d'abord, allouer et initialiser le nouveau nœud. Alors, où sa place est dans la liste, puis lier le nouveau nœud dans la liste à cet endroit.

Tout d'abord, une fonction qui sera de retour ce sera le nœud parent " pour le nouveau nœud. (Ce nœud suppose que la liste est maintenue dans l'ordre de tri par nom):

int LIST_FetchParentNodeByName( 
      LIST_NODE_T *I__head,
      const char  *I__name,
      LIST_NODE_T **_O_parent
      )
   {
   int rCode=0;
   LIST_NODE_T *parent = NULL;
   LIST_NODE_T *curNode = I__head;

   /* Inform the caller of an 'empty list' condition. */
   if(NULL == I__head)
      {
      rCode=ENOENT;
      goto CLEANUP;
      }

   /* Find a node with a payload->name string greater than the I__name string */
   while(curNode)
      {
      if(strcmp(curNode->payload.name, I__name) > 0)
         break;

      parent = curNode; /* Remember this node. It is the parent of the next node. */
      curNode=curNode->next;  /* On to the next node. */
      }

   /* Set the caller's 'parent' pointer. */
   if(_O_parent)
      *_O_parent = parent;

CLEANUP:

   return(rCode);
   }

Et maintenant, une fonction qui permet d'insérer de nouveaux nœuds, en gardant la liste triée par nom.

   int LIST_InsertNodeByName(
      LIST_NODE_T **IO_head,
      char         *I__name,
      char         *I__desc,
      int           I__hours,
      int           I__workordernum
      )
   {
   int rCode=0;
   LIST_NODE_T *parent;
   LIST_NODE_T *newNode = NULL;

   /* Allocate memory for new node (with its payload). */
   newNode=malloc(sizeof(*newNode));
   if(NULL == newNode)
      {
      rCode=ENOMEM;   /* ENOMEM is defined in errno.h */
      fprintf(stderr, "malloc() failed.\n");
      goto CLEANUP;
      }

   /* Initialize the new node's payload. */       
   snprintf(newNode->payload.name, sizeof(newNode->payload.name), "%s", I__name);
   snprintf(newNode->payload.desc, sizeof(newNode->payload.desc), "%s", I__desc);
   newNode->payload.hours = I__hours;
   newNode->payload.workordernum = I__workordernum;

   /* Find the proper place to link this node */
   rCode=LIST_FetchParentNodeByName(*IO_head, I__name, &parent);
   switch(rCode)
      {
      case 0:
         break;

      case ENOENT:
         /* Handle empty list condition */ 
         newNode->next = NULL;
         *IO_head = newNode;
         rCode=0;
         goto CLEANUP;

      default:
         fprintf(stderr, "LIST_FetchParentNodeByName() reports: %d\n", rCode);
         goto CLEANUP;
      }

---

Remarque importante: La LIST_FetchParentNodeByName() va définir le parent pointeur vers le nœud de la liste qui est immédiatement inférieur au spécifiée j'__nom; -sauf - le nœud de tête est plus grande que la valeur spécifiée j'__nom. Pour ce cas particulier, LIST_FetchParentNodeByName() permet de définir le parent pointeur à NULL.

---

   /* Handle the case where all current list nodes are greater than the new node. */
   /* (Where the new node will become the new list head.) */
   if(NULL == parent)
      {
      newNode->next = *IO_head;
      *IO_head = newNode;
      goto CLEANUP;
      }

   /* Final case, insert the new node just after the parent node. */
   newNode->next = parent->next;
   parent->next = newNode;

CLEANUP:

   return(rCode);
   }

La LIST_InsertNodeByName() la fonction est appelée de la même façon LIST_InsertHeadNode() ou LIST_InsertTailNode() est appelée. La seule différence est que, avec LIST_InsertNodeByName(), le nouveau nœud est inséré dans son triée (par nom) emplacement dans la liste, plutôt qu'à la liste de tête ou de queue.

Il y aura des occasions où un nœud devra être supprimé de la liste. Ceci est fait par la localisation du nœud à supprimer, supprimer le lien avec le nœud de la liste, puis de supprimer le nœud et c'est la charge utile.

Tout d'abord, une fonction pour localiser un nœud spécifique par la charge utile de nom de domaine.

int LIST_FetchNodeByName( 
      LIST_NODE_T  *I__head,
      const char   *I__name,
      LIST_NODE_T **_O_node,
      LIST_NODE_T **_O_parent
      )
   {
   int rCode=0;
   LIST_NODE_T *parent = NULL;
   LIST_NODE_T *curNode = I__head;

   /* Search the list for a matching payload name. */
   while(curNode)
      {
      if(0 == strcmp(curNode->payload.name, I__name))
         break;

      parent = curNode;   /* Remember this node; it will be the parent of the next. */
      curNode=curNode->next;
      }

   /* If no match is found, inform the caller. */
   if(NULL == curNode)
     {
     rCode=ENOENT;
     goto CLEANUP;
     }

   /* Return the matching node to the caller. */
   if(_O_node)
      *_O_node = curNode;

   /* Return parent node to the caller. */
   if(_O_parent)
      *_O_parent = parent;

CLEANUP:

   return(rCode);
   }

Ici est une fonction qui supprime un nœud de la liste qui correspond à une charge spécifique de nom.

   int LIST_DeleteNodeByName(
      LIST_NODE_T **IO_head,
      char         *I__name
      )
   {
   int rCode=0;
   LIST_NODE_T *parent;
   LIST_NODE_T *delNode = NULL;

   /* Find the node to delete. */
   rCode=LIST_FetchNodeByName(*IO_head, I__name, &delNode, &parent); 
   switch(rCode)
      {
      case 0:
         break;

      case ENOENT:
         fprintf(stderr, "Matching node not found.\n");
         goto CLEANUP;

      default:
         fprintf(stderr, "LIST_FetchNodeByName() reports: %d\n", rCode);
         goto CLEANUP;
      }

---

Remarque importante: La LIST_FetchNodeByName() va définir le parent pointeur de la delNode; -sauf - le delNode est le nœud de tête. Pour ce cas particulier, LIST_FetchNodeByName() permet de définir le parent pointeur à NULL.

---

   /* Unlink the delNode from the list. */
   if(NULL == parent)
      *IO_head = delNode->next;
   else
      parent->next = delNode->next;

   /* Free the delNode and its payload. */
   free(delNode);

CLEANUP:

   return(rCode);
   }       

REMARQUE: Tout le code ci-dessus a été testé et doit être fonctionnel, et peut être téléchargé sous: 23279119_List_101.c

(La suite - selon la demande...)

OriginalL'auteur Mahonri Moriancumer