在C中创建和理解结构的链接列表

Question

我无法一起掌握struct链接列表数据结构的概念.例如,假设我们有这样的代码:a struct具有worker的内容和这些结构的链表,其中包含每个worker的节点和指向下一个节点的指针(？).

    typedef struct Schedule {
        char name[10];
        char description[10];
        int hours;
        int workordernum;
    } Work;

    typedef struct linkedlist {
        struct Schedule work;
        struct linkedlist *next;
    } Node;

问题是如何创建一个始终在列表开头添加节点的方法,一种使用用户定义将其添加到列表中任何位置(中间)workordernum的方法,以及始终将其添加到最后的方法.

我不是很了解->和*正确使用.我确实在网上阅读了有关创建头尾节点的信息,但我没有正确使用它,因为它们有struct一个列表和struct一个节点.

我没有得到的另一件事是,假设在列表的开头添加一个节点,你如何改变workordernum以前所有节点的每一个值呢？

我理解每次添加,删除或移动节点时都必须跟踪,这意味着每次调用这些方法时,我们必须有一个跟踪数字的变量.所以,如果我们在列表中的所有准备的一个节点,其顺序将是一个,我们再加入一个又一个开始,我们将如何改变顺序编号为1至2和一个被添加到1？

或者如果我们只有一个指针,node-> next-> next-> next怎么工作？然后我们将如何打印所有这些？因为我们不能使用for循环.

所以这些是我无法理解代码的概念.如果你花时间解释它,而不是仅仅给出代码,如果可能的话,我会非常感激.因为我必须应用我学到的东西来移动并删除节点.我想自己学习.如果必须作为代码示例提供某些内容,那就没问题,但请不要为我发布所有答案代码.

-谢谢

*请原谅任何格式错误,因为我是这个网站的新手.

编辑:我确实理解指针是一个地址,并且->属于"指向"成员.我的意思是我理解所有基础知识,但我的理解不够坚定,否则我可以做我需要帮助的事情.

编辑2:我将尝试使用我目前学到的链接列表创建一个头节点.我将使用上面的结构,它将是松散的代码,而不是完美的.这只是为了确保我到目前为止在正确的轨道上.

int main() {

   // creates a work struct to hold user content
   Work *workstruct = (Work*)malloc((sizeof(struct Schedule));

   // creates first node to hold a work struct for linkedlist
   Node *initialNode = (Node*)malloc((sizeof(struct linkedlist));

   // Method call to add work nodes to list in main
   addWork(initialNode, workstruct);

}

void addWork(Node *initialNode, Work *workstruct) {

   // Suppose user already initialized workstruct

   // create double-pointer to make initialNode as head
   Node **head = (Node **)malloc(sizeof(struct linkedlist));

   // assigns user's workstruct to the workstruct of initialNode
   initialNode->work = *workstruct;

   // If im understanding what you have taught me so far,
   // this is how you always add a node on the head

   initialNode->next = *head;
   *head = initialNode;
}

到目前为止,我似乎唯一的问题是,每次我尝试向列表中添加一个新节点时,它都会使新节点成为头部,但会丢失列表中的上一个节点.

Answer 1

链接列表 - 101 - 单链表

这是一个很长的答案.我之所以如此详细的原因是,我希望在适当的背景下有大量的链接列表问题.

当我学习C时,我很难用指针.但是,在实现链表后,我终于开始掌握指针的概念.主链表在C语言中是一件好事,它可以帮助您熟悉指针.当事情看起来令人困惑时,抓住一支铅笔和一张纸,勾勒出一个列表图和相关的节点链接.当我使用复杂的列表实现时,偶尔会这样做.

链表是一种存储数据记录的方法.与所有元素占据一个连续内存块的数组不同,链表元素占用内存的随机片段.

链表有两种基本类型; 一个单链表和一个双向链表.区别在于单链表只能在一个方向上遍历; 而双向链表可以在两个方向上遍历.

通过其"头"指针或指向头列表节点的指针访问单链表.双链表也可以通过其"head"指针或通过其"tail"指针来访问.

与数组的每个元素可以通过其数组索引直接寻址的数组不同,链接列表元素是按顺序访问的.

这是一个单链表的布局:

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

列表中的每个节点及其数据有效负载都是单独分配的.节点结构(在C中)可能如下所示:

    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;

要初始化上述结构的单链表:

LIST_NODE_T *listHead = NULL;

'listHead'现在是指向链表(没有节点)的指针.

以下是如何在此列表的开头添加新节点:

int LIST_InsertHeadNode(
      LIST_NODE_T **IO_head,

问:为什么这里需要"双指针"(即:LIST_NODE_T**...)？为什么不使用"单级"指针(即:LIST_NODE_T*...)？

答:指向列表头的"单个"指针不足以进行此操作.具体地,该操作指定新的"头节点".这意味着此函数需要修改指向头节点的指针.

之前:

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

后:

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

注意,之前,HEADPTR指向'Node #Y'; 之后,HEADPTR指向'新节点'.调用此函数时,将传入listHead指针的地址,允许此函数更改listHead指针指向的位置.换句话说,listHead指针的地址被传递给这个函数,该函数表示(在此函数内部)作为指向listHead指针(指向指针的指针)的指针.这就是为什么它是一个"双指针".

      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;

问:这是什么'goto CLEANUP;' 商业？

答:与C++和JAVA不同,C语言没有"例外"的概念.在C中检查错误至关重要.malloc()函数可能会失败的原因有很多,如果确实如此,代码必须尽可能优雅地处理它.'goto CLEANUP'语句使正常的程序流跳过跳转到'CLEANUP:'标签的代码(在此函数中,如下).

显然,如果malloc()失败了,那么尝试使用紧随其后的行初始化NULL指针(由失败的malloc返回)是不明智的.因此,重要的是转移程序流程以跳过此初始化(以及稍后出现的链接).

"CLEANUP:"标签没有什么特别之处.我可以称之为'错误:','退出:','结束:','LIAHONA:','MY_BAD'或任何其他适合我的乐趣.(标签不必是大写的,也不必放在左边缘.但是,我的风格是做到这一点,以便它们脱颖而出.)

标签,例如'CLEANUP:',其范围仅限于放置它们的功能的边界; 它允许每个函数都有一个唯一的'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 head node. */
   newNode->next = *IO_head;
   *IO_head = newNode;

CLEANUP:

   return(rCode);
   }

可以按如下方式调用上述函数:

#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);
   }

可以多次调用LIST_InsertHeadNode()函数.每次调用都会向列表中添加一个新节点.新节点将放置在列表的"头部",这样可以将其余节点推到列表的下方.

将多个节点添加到列表后,访问列表可能会很好; 也许打印每个节点的有效载荷:

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);
   }

可以从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);
   }

在列表头部添加节点[即:LIST_InsertHeadNode()]是添加节点的一种方法.但是,有时候将节点添加到列表的另一端(即:列表'tail')是可取的.下面的代码显示了这是如何完成的.

首先,一个函数将返回列表的当前"尾节点".

   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);
      }

接下来,将一个节点插入列表尾部的函数.

   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;
      }

重要提示:LIST_GetTailNode()函数将tailNode指针设置为链表中的最后一个节点; -unless-列表中没有节点.当列表为空时,LIST_GetTailNode()会将tailNode指针设置为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

这个'else'情况表示当tailNode为NULL时发生,这意味着(当前)链表没有节点.在这种情况下,该节点将是列表中的第一个(头部)节点(以及最后一个节点).因此,调用者的"列表头"指针会更新,以指示此新节点现在是头节点.

      *IO_head = newNode;

CLEANUP:

   return(rCode);
   }

LIST_InsertTailNode()函数的调用方式与调用LIST_InsertHeadNode()的方式相同.唯一的区别是使用LIST_InsertTailNode(),新节点将插入列表的尾部,而不是列表的头部.

好的,现在您可以在列表的头部或尾部插入新节点.如何在列表中间的某处插入新节点？

例如,假设您希望有一个列表,其中所有节点按有效负载中的某些字段排序,如"名称".虽然可以添加所有节点,然后对列表进行排序; 将每个新节点插入到适当位置的列表中要容易得多.这样,列表将始终按排序顺序自动维护.

完成此任务分两步完成.首先,分配并初始化新节点.然后找出它在列表中的适当位置,然后将新节点链接到该位置的列表中.

首先,一个函数将返回到新节点的"父节点".(此节点假定列表按名称按排序顺序维护):

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);
   }

现在,这个函数将插入新节点,保持列表按名称排序.

   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;
      }

重要说明:LIST_FetchParentNodeByName()函数将父指针设置为列表中的节点,该节点立即小于指定的I__name; -unless-头节点大于指定的I__name.对于这种特殊情况,LIST_FetchParentNodeByName()将父指针设置为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);
   }

调用LIST_InsertNodeByName()函数的方式与调用LIST_InsertHeadNode()或LIST_InsertTailNode()的方式相同.唯一的区别是,使用LIST_InsertNodeByName(),新节点将插入到列表中的排序(按名称)位置; 而不是在列表的头部或尾部.

有时候必须从列表中删除节点.这是通过定位要删除的节点,从列表中取消链接节点,然后删除节点及其有效负载来完成的.

首先,通过有效负载名称字段定位特定节点的功能.

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);
   }

这是一个函数,它将从列表中删除与特定有效负载名称匹配的节点.

   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;
      }

重要说明:LIST_FetchNodeByName()函数将设置delNode的父指针; -unless- delNode是头节点.对于这种特殊情况,LIST_FetchNodeByName()将父指针设置为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);
   }       

注意:上面的所有代码都经过测试,应该可以使用,可以下载到:23279119_List_101.c

(继续 - 按要求......)