在C中创建和理解结构的链接列表 [英] Creating and Understanding linked lists of structs in C
问题描述
我很难同时理解struct和链表数据结构的概念.例如，假设我们有以下代码:struct，其中包含工作程序的内容以及这些结构的链接列表，这些结构包含每个工作程序的节点和指向下一个node(?)的指针.
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循环.
这些是我无法理解代码的概念. 如果您花时间解释它，而不是仅仅提供代码，我将不胜感激.因为我必须将我学到的知识应用于移动和删除节点.我想自己学习.如果必须提供一些示例代码，那很好，但是请不要为我发布所有答案代码.
-谢谢
*由于我是这个网站的新手，请原谅任何格式错误.
我确实知道指针是地址，并且->与指向"成员有关.我的意思是我了解所有基础知识，但是我的理解不够坚定，否则我可能会做我需要帮助的事情.
Edit2:我将尝试根据到目前为止所学的知识制作一个带有链接列表的头节点.我将使用上面的结构，它将是松散的代码，而不是完美的代码.这只是为了确保我到目前为止走在正确的轨道上.
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 * ...)?
A:指向列表头的单个"指针不足以完成此操作.具体地说，此操作指定一个新的头节点".这意味着此函数需要修改指向头节点的指针.
之前:
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指向节点#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;
问:这是什么去清洁"；业务吗?
A:与C ++和JAVA不同，C语言没有例外"的概念. C语言中的错误检查至关重要.有很多原因可能导致malloc()函数失败，如果失败，则代码必须尽可能优雅地处理它. "goto CLEANUP"语句使普通程序流跳过跳转到"CLEANUP:"标签的代码(在此功能内，如下).
很显然，如果malloc()失败了，试图用紧随其后的行来初始化NULL指针(由失败的malloc返回)是不明智的.因此，转移程序流以跳过此初始化(以及随后出现的链接)非常重要.
"CLEANUP:"标签没有什么特别之处.我可以将其称为"ERROR:"，"EXIT:"，"FINISH:"，"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指针设置为链接列表中的最后一个节点. -除非-列表中没有节点.当列表为空时，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的节点的父指针. -除非头节点大于指定的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的父指针. -除非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);
}
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: What's this 'goto CLEANUP;' business?
A: The C language, unlike C++ and JAVA, has no concept of an 'exception'. Error checking in C is critical. There are a number of reasons that the malloc() function might fail, and if it does, the code has to handle it as gracefully as possible. The 'goto CLEANUP' statement causes the normal program flow to skip code jumping to the 'CLEANUP:' label (within this function, below).
Obviously, if malloc() has failed, it would be unwise to try to initialize the NULL pointer (returned by the failed malloc) with the lines that immediately follow. So, it is important to divert the flow of the program to skip this initialization (and the linkage that comes later).
There is nothing special about the 'CLEANUP:' label. I could have called it 'ERROR:', 'EXIT:', 'FINISH:', 'LIAHONA:', 'MY_BAD' or anything else that suited my pleasure. (Labels don't have to be uppercase, nor do they have to be placed at the left margin. However, my style is to do that so that they stand out.)
Labels, such as 'CLEANUP:' has a scope that is limited to the boundaries of the function where they are placed; which allows each function to have a unique 'CLEANUP:' label (if needed).
}
/* 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);
}
The above function might be called as follows:
#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);
}
The LIST_InsertHeadNode() function may be called multiple times. Each call will add a new node to the list. The new node will be placed at the "head" of the list, which has the effect of pushing the rest of the nodes further down the list.
After adding several nodes to the list, it might be good to access the list; perhaps to print the payload of each node:
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);
}
The above function can be called from 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);
}
Adding nodes at the head of a list [ie: LIST_InsertHeadNode()] is one way to add nodes. However, there are times where adding nodes to the other end of the list (ie: the list 'tail') is preferable. The code below shows how this is done.
First, a function that will return the current 'tail node' of a list.
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);
}
Next, a function that will insert a node at the tail of the list.
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;
}
Important note: The LIST_GetTailNode() function will set the tailNode pointer to the last node in the linked list; -unless- there are no nodes in the list. When the list is empty, LIST_GetTailNode() will set the tailNode pointer to 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
This 'else' case indicates occurs when tailNode is NULL, meaning that (currently) the linked list has no nodes. In this case, this node will be the first (head) node in the list (as well as the last). So, the caller's 'List Head' pointer is updated to indicate that this new node is now the head node.
*IO_head = newNode;
CLEANUP:
return(rCode);
}
The LIST_InsertTailNode() function is called the same way LIST_InsertHeadNode() is called. The only difference is that with LIST_InsertTailNode(), the new node is inserted at the list's tail, rather than at the list's head.
OK, so now you can insert a new node at the head, or tail of the list. What about inserting a new node somewhere in the middle of the list?
For example, assume that you want to have a list where all the nodes are sorted by some field in the payload like 'name'. While it is possible to add all the nodes, and then sort the list afterwords; it is much easier to insert each new node into the list in it's proper place. Doing that, the list will always be maintained in sorted order automatically.
Accomplishing this is done in two steps. First, allocate and initialize the new node. Then figure out where its proper place is in the list, then link the new node into the list at that location.
First, a function that will return what will be the 'parent node' to the new node. (This node assumes that the list is being maintained in sorted order by name):
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);
}
And now, a function that will insert new nodes, keeping the list sorted by name.
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;
}
Important note: The LIST_FetchParentNodeByName() function will set the parent pointer to the node in the list that is immediately less than the specified I__name; -unless- the head node is greater than the specified I__name. For this special case, LIST_FetchParentNodeByName() will set the parent pointer to 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);
}
The LIST_InsertNodeByName() function is called the same way LIST_InsertHeadNode() or LIST_InsertTailNode() is called. The only difference is that with LIST_InsertNodeByName(), the new node is inserted into its sorted (by name) location in the list; rather than at the list head or tail.
There will be occasions when a node will have to be deleted from the list. This is done by locating the node to be deleted, unlinking the node from the list, and then deleting the node and it's payload.
First, a function to locate a specific node by the payload name field.
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);
}
Here is a function that will delete a node from the list that matches a specific payload name.
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;
}
Important note: The LIST_FetchNodeByName() function will set the parent pointer of the delNode; -unless- the the delNode is the head node. For this special case, LIST_FetchNodeByName() will set the parent pointer to 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);
}
NOTE: All code above has been tested and should be functional, and can be downloaded as: 23279119_List_101.c
(To be continued- as per request...)
这篇关于在C中创建和理解结构的链接列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
