我很难同时掌握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,然后在开头添加另一个,如何将顺序号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 * ...)?
答:指向列表头的“单个”指针不足以完成此操作。具体地说,此操作指定一个新的“头节点”。这意味着此函数需要修改指向头节点的指针。
前:
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;
问:这是什么“去清洁”;商业?
答:与C++和JAVA不同,C语言没有“异常(exception)”的概念。 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
这种“其他”情况表明当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);
}
注意:上面的所有代码都已经过测试,应该可以运行,可以下载为:23279119_List_101.c
(待续-根据要求...)
关于c - 在C中创建和理解结构的链接列表,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/23279119/