在C中创建和理解结构的链接列表
我无法一起掌握struct和链表数据结构的概念。 例如，假设我们有这样的代码：一个具有worker的内容的struct ，这些struct的链表包含每个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，那么我们在开头添加另一个节点，如何将订单号1更改为2，将1添加到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; }
到目前为止，我似乎唯一的问题是，每次我尝试向列表中添加一个新节点时，它都会使新节点成为头部，但会丢失列表中的上一个节点。
链接列表 – 101 – 单链表
这是一个很长的答案。 我之所以如此详细的原因是，我希望在适当的背景下，有大量的链接列表问题。
当我学习C时，我很难用指针。 但是，在实现链表后，我终于开始掌握指针的概念。 在C中，主链表是一件好事，它可以帮助您熟悉指针。 当事情看起来令人困惑时，抓住一支铅笔和一张纸，勾勒出一个列表图和相关的节点链接。 当我使用复杂的列表实现时，偶尔会这样做。
链表是一种存储数据记录的方法。 与所有元素占据一个连续内存块的数组不同，链表元素占用内存的随机片段。
链表有两种基本类型; 一个单链表和一个双向链表。 区别在于单链表只能在一个方向上遍历; 而双向链表可以在两个方向上遍历。
通过其“头”指针或指向头列表节点的指针访问单链表。 双链表也可以通过其“头”指针或通过其“尾”指针来访问。
与数组的每个元素可以通过其数组索引直接寻址的数组不同，链接的列表元素是按顺序访问的。
这是一个单链表的布局：
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 #include 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 #include 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（），新节点将插入到列表中的排序（按名称）位置; 而不是在列表的头部或尾部。
有时候必须从列表中删除节点。 这是通过定位要删除的节点，从列表中取消链接节点，然后删除节点及其有效负载来完成的。
首先，通过有效负载名称字段定位特定节点的function。
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
（继续 – 按要求……）