如何在C中实现链表？
我正在创建一个链接列表，就像我之前提出的问题一样。 我发现开发链表的最好方法是将头部和尾部放在另一个结构中。 我的products struct将嵌套在这个结构中。 我应该将列表传递给添加和删除function。 我发现这个概念令人困惑。
我已经实现了initialize，add和clean_up。 但是，我不确定我是否正确地做到了这一点。
当我将产品添加到列表中时，我使用calloc声明了一些内存。 但我想我不应该为产品声明内存。 我对此添加感到困惑。
非常感谢任何建议，
#include #include #include #define PRODUCT_NAME_LEN 128 typedef struct product_data { int product_code; char product_name[PRODUCT_NAME_LEN]; int product_cost; struct product_data_t *next; }product_data_t; typedef struct list { product_data_t *head; product_data_t *tail; }list_t; void add(list_t *list, int code, char name[], int cost); void initialize(list_t *list); void clean_up(list_t *list); int main(void) { list_t *list = NULL; initialize(list); add(list, 10, "Dell Inspiron", 1500); clean_up(list); getchar(); return 0; } void add(list_t *list, int code, char name[], int cost) { // Allocate memory for the new product list = calloc(1, sizeof(list_t)); if(!list) { fprintf(stderr, "Cannot allocated memory"); exit(1); } if(list) { // First item to add to the list list->head->product_code = code; list->head->product_cost = cost; strncpy(list->head->product_name, name, sizeof(list->head->product_name)); // Terminate the string list->head->product_name[127] = '/0'; } } // Initialize linked list void initialize(list_t *list) { // Set list node to null list = NULL; list = NULL; } // Release all resources void clean_up(list_t *list) { list_t *temp = NULL; while(list) { temp = list->head; list->head = list->head->next; free(temp); } list = NULL; list = NULL; temp = NULL; } ==============================编辑=================== =========
#include #include #include #define PRODUCT_NAME_LEN 64 // typedef struct product_data product_data_t; typedef struct product_data { int product_code; char product_name[PRODUCT_NAME_LEN]; int product_cost; }product_data_t; typedef struct list { struct list *head; struct list *tail; struct list *next; struct list *current_node; product_data_t *data; }list_t; void add(list_t *list, int code, char name[], int cost); int main(void) { list_t *list = NULL; list = initialize(list); add(list, 1001, "Dell Inspiron 2.66", 1299); add(list, 1002, "Macbook Pro 2.66", 1499); clean_up(list); getchar(); return 0; } void add(list_t *list, int code, char name[], int cost) { /* Allocate memory for the new product */ product_data_t *product = (product_data_t*) calloc(1, sizeof(*product)); if(!product) { fprintf(stderr, "Cannot allocate memory."); exit(1); } /* This is the first item in the list */ product->product_code = code; product->product_cost = cost; strncpy(product->product_name, name, sizeof(product->product_name)); product->product_name[PRODUCT_NAME_LEN - 1] = '\0'; if(!list->head) { /* Assign the address of the product. */ list = (list_t*) product; /* Set the head and tail to this product */ list->head = (list_t*) product; list->tail = (list_t*) product; } else { /* Append to the tail of the list. */ list->tail->next = (list_t*) product; list->tail = (list_t*) product; } /* Assign the address of the product to the data on the list. */ list->data = (list_t*) product; }
在您的情况下，头部和尾部可以简单地指向链表的开头和结尾。 使用单链表，只需要头部。 在最基本的情况下，可以通过仅使用如下结构来创建链接列表：
typedef struct listnode { //some data struct listnode *next; }listnodeT; listnodeT *list; listnodeT *current_node; list = (listnodeT*)malloc(sizeof(listnodeT)); current_node = list;
只要list总是指向列表的开头而最后一个项目下一个设置为NULL，你就可以了，并且可以使用current_node来遍历列表。 但有时为了更容易遍历列表并存储有关列表的任何其他数据，使用头尾令牌，并将其包装到自己的结构中，就像您所做的那样。 那么你的添加和初始化函数就像（减去错误检测）
// Initialize linked list void initialize(list_t *list) { list->head = NULL; list->tail = NULL; } void add(list_t *list, int code, char name[], int cost) { // set up the new node product_data_t *node = (product_data_t*)malloc(sizeof(product_data_t)); node->code = code; node->cost = cost; strncpy(node->product_name, name, sizeof(node->product_name)); node->next = NULL; if(list->head == NULL){ // if this is the first node, gotta point head to it list->head = node; list->tail = node; // for the first node, head and tail point to the same node }else{ tail->next = node; // append the node tail = node; // point the tail at the end } }
在这种情况下，由于它是一个单独的链表，尾部只对将项添加到列表中非常有用。 要插入项目，您必须从头部开始遍历列表。 尾部真正派上用场的地方是双向链表，它允许你从两端开始遍历列表。 你可以遍历这个列表
// return a pointer to element with product code product_data_t* seek(list_t *list, int code){ product_data_t* iter = list->head; while(iter != NULL) if(iter->code == code) return iter; iter = iter->next; } return NULL; // element with code doesn't exist }
通常，头部和尾部是完全构造的节点，它们本身用作哨兵以表示列表的开始和结束。 它们本身并不存储数据（更确切地说，它们的数据代表了一个标记符号），它们只是正面和背面的占位符。 这样可以更容易地编写一些处理链表的算法，但代价是必须有两个额外的元素。 总的来说，链表是灵活的数据结构，有几种实现方式。
哦是的，而且nik是对的，玩链接列表是一个很好的方法来获得指针和间接的好处。 而且它们也是练习递归的好方法！ 使用链接列表后，请尝试构建一个树，然后使用递归来遍历树。
可以说，您希望列表数据结构在其存储的数据外部。
说你有：
结构无论如何
{
int x_;
}
那么你的列表结构将如下所示：
struct Whatever_Node
{
Whatever_Node * next_
无论*数据_
}
Ryan Oberoi同样评论，但没有例子。
如果您希望更好地了解链接列表的基础知识，请查看以下文档：
如果你正在学习C指针理论，这是一个很好的练习。 否则，对于非通用的代码（如在库中），感觉就像是太多间接。
您可能希望执行更多指针练习，并使用在退出时清理的已分配的精确长度字符串，而不是分配静态128字节字符串。
在学术上， kungfucraig的结构看起来比你定义的更通用。
你是list_t结构的calloc’ing空间，只是指向列表头部和尾部的指针，这不是你想要做的。
添加到链接列表时，为列表中的实际节点分配空间，这是您的product_data_t结构。
你正在分配错误的内存块。 您不是为每个列表元素分配内存，而是为列表头部和尾部分配。
为简单起见，摆脱头部和尾部的独立结构。 使它们成为全局变量（与它们现在相同的范围）并将它们更改为listhead和listtail。 这将使代码更具可读性（您不会不必要地通过单独的结构）并且您不会错误地分配错误的结构。
你不需要尾指针，除非你打算制作一个双向链表。 创建链表后，它不是添加的主要元素，但也不是必需的。
我不是在这里编写代码，但您需要执行以下操作：
- 创建列表的对象，这将在程序的长度上保持全局。
- malloc产品_ data _ t的大小。
- 对于第一个元素（head为NULL），指向malloced’地址。
- 要添加下一个元素，请移至列表末尾，然后将malloced地址的指针添加到最后一个元素。 （最后一个元素的下一个元素将始终为NULL，因此您将如何遍历结束。）
- 忘了尾巴一会儿。
在内存中，您的项目通过列表结构中的指针链接
item1 – > item2
为什么不将列表结构作为项目的一部分？
然后分配一个产品项，列表结构就在其中。
typedef struct product_data { int product_code; char product_name[PRODUCT_NAME_LEN]; int product_cost; struct list_t list; // contains the pointers to other product data in the list }product_data_t;
我想你首先需要Imagin后端。 代码没什么重要的。 转到此处，可视化所有插入的后端基本c代码。 1）在开始时插入访问并滚动以获得后端的每个指令执行并且你需要前面和想象去这里返回结束imagin
所有其他可能插入此处。
重要的是你可以用这种方式。
struct Node {
int data; //数据字段
struct Node * next; //指针字段
};
struct Node * head，* tail; //试试这个
或捷径
struct Node {
int data; //数据字段
struct Node * next; //指针字段
} *头，尾*; //全局根指针
和
<< Click >>可视化其他链表问题。
谢谢。
单链表的演示。 如果您愿意，请尝试检查循环链接列表和双向链接列表 。
#include #include typedef struct node { int val; struct node * next; } node_t; // Iterating over a list void print_list(node_t *head) { node_t *current = head; while(current != NULL) { printf("%d\n", current->val); current = current->next; } } // Adding an item to the end of the list void push_end(node_t *head, int val) { node_t *current = head; while (current->next != NULL) { current = current->next; } current->next = malloc(sizeof(node_t)); current->next->val = val; current->next->next = NULL; } // Adding an item to the head of the list void push_head(node_t **head, int val) { node_t *new_node = NULL; new_node = malloc(sizeof(node_t)); new_node->val = val; new_node->next = *head; *head = new_node; } // Removing the head item of the list int pop_head(node_t **head) { int retval = -1; node_t *next_node = NULL; if (*head == NULL) { return -1; } next_node = (*head)->next; retval = (*head)->val; free(*head); *head = next_node; return retval; } // Removing the last item of the list int pop_last(node_t *head) { int retval = 0; node_t *current = NULL; if (head->next == NULL) { retval = head->val; free(head); return retval; } /* get to the second to last node in the list */ current = head; while (current->next->next != NULL) { current = current->next; } /* now current points to the second to last item of the list. so let's remove current->next */ retval = current->next->val; free(current->next); current->next = NULL; return retval; } // Removing a specific item int remove_by_index(node_t **head, int n) { int i = 0; int retval = -1; node_t *current = *head; node_t *temp_node = NULL; if (n == 0) { return pop_head(head); } for (i = 0; i < n - 1; i++) { if (current->next == NULL) { return -1; } current = current->next; } temp_node = current->next; retval = temp_node->val; current->next = temp_node->next; free(temp_node); return retval; } int main(int argc, const char *argv[]) { int i; node_t * testnode; for (i = 0; i < argc; i++) { push_head(&testnode, atoi(argv[i])); } print_list(testnode); return 0; } // http://www.learn-c.org/en/Linked_lists // https://www.geeksforgeeks.org/data-structures/linked-list/
受Linux内核中使用的实现启发的链表实现：
// for 'offsetof', see: https://stackoverflow.com/q/6433339/5447906. #include // See: https://stackoverflow.com/q/10269685/5447906. #define CONTAINER_OF(ptr, type, member) \ ( (type *) ((char *)(ptr) - offsetof(type, member)) ) // The macro can't be used for list head. #define LIST_DATA(ptr, type, member) \ CONTAINER_OF(ptr, type, member); // The struct is used for both: list head and list nodes. typedef struct list_node { struct list_node *prev, *next; } list_node; // List heads must be initialized by this function. // Using the function for list nodes is not required. static inline void list_head_init(list_node *node) { node->prev = node->next = node; } // The helper function, mustn't be used directly. static inline void list_add_helper(list_node *prev, list_node *next, list_node *nnew) { next->prev = nnew; nnew->next = next; nnew->prev = prev; prev->next = nnew; } // 'node' must be a list head or a part of a list. // 'nnew' must not be a list head or a part of a list. It may // be uninitialized or contain any data (even garbage). static inline void list_add_after(list_node *node, list_node *nnew) { list_add_helper(node, node->next, nnew); } // 'node' must be a list head or a part of a list. // 'nnew' must not be a list head or a part of a list. It may // be uninitialized or contain any data (even garbage). static inline void list_add_before(list_node *node, list_node *nnew) { list_add_helper(node->prev, node, nnew); } // 'node' must be part of a list. static inline list_node *list_del(list_node *node) { node->prev->next = node->next; node->next->prev = node->prev; return node->prev; }
用法示例：
#include // The struct must contain 'list_node' to be able to be inserted to a list typedef struct { int data; list_node node; } my_struct; // Convert 'list_node *' to 'my_struct*' that contains this 'list_node' static inline my_struct* get_my_struct(list_node *node_ptr) { return LIST_DATA(node_ptr, my_struct, node); } void print_my_list(list_node *head) { printf("list: {"); for (list_node *cur = head->next; cur != head; cur = cur->next) { my_struct *my = get_my_struct(cur); printf(" %d", my->data); } printf(" }\n"); } // Print 'cmd' and run it. Note: newline is not printed. #define TRACE(cmd) \ (printf("%s -> ", #cmd), (cmd)) int main() { // The head of the list and the list itself. It doesn't contain any data. list_node head; list_head_init(&head); // The list's nodes, contain 'int' data in 'data' member of 'my_struct' my_struct el1 = {1}; my_struct el2 = {2}; my_struct el3 = {3}; print_my_list(&head); // print initial state of the list (that is an empty list) // Run commands and print their result. TRACE( list_add_after (&head , &el1.node) ); print_my_list(&head); TRACE( list_add_after (&head , &el2.node) ); print_my_list(&head); TRACE( list_add_before(&el1.node, &el3.node) ); print_my_list(&head); TRACE( list_del (head.prev) ); print_my_list(&head); TRACE( list_add_before(&head , &el1.node) ); print_my_list(&head); TRACE( list_del (&el3.node) ); print_my_list(&head); return 0; }
执行上面代码的结果：
list: { } list_add_after (&head , &el1.node) -> list: { 1 } list_add_after (&head , &el2.node) -> list: { 2 1 } list_add_before(&el1.node, &el3.node) -> list: { 2 3 1 } list_del (head.prev) -> list: { 2 3 } list_add_before(&head , &el1.node) -> list: { 2 3 1 } list_del (&el3.node) -> list: { 2 1 }
http://coliru.stacked-crooked.com/a/6e852a996fb42dc2
当然，在现实生活中，您最有可能将malloc用于列表元素。
在C语言中，我们需要定义一个Node来存储一个整数数据和一个指向下一个值的指针。
struct Node{ int data; struct Node *next; };
要添加新节点，我们有一个函数add，它将数据作为int参数。 首先，我们创建一个新的Node n。 如果程序没有创建n，那么我们打印一条错误消息并返回值-1。 如果我们创建n，那么我们将n的数据设置为具有参数的数据，而下一个将包含根，因为它具有堆栈的顶部。 之后，我们将根设置为引用新节点n。
#include struct node { int data; struct node* next; }; int main() { //create pointer node for every new element struct node* head = NULL; struct node* second = NULL; struct node* third = NULL; //initialize every new pointer with same structure memory head = malloc(sizeof(struct node)); second = malloc(sizeof(struct node)); third = malloc(sizeof(struct node)); head->data = 18; head->next = second; second->data = 20; second->next = third; third->data = 31; third->next = NULL; //print the linked list just increment by address for (int i = 0; i < 3; ++i) { printf("%d\n",head->data++); return 0; } }
这是一种了解指针如何与指针一起工作的简单方法。 在这里，您需要使用新节点创建指针增量，以便我们可以将其设置为自动节点。
去STL路线。 声明链接列表应该与数据无关。 如果您真的必须自己编写，请查看它在STL或Boost中的实现方式。
您甚至不应该将* next指针与数据结构保持一致。 这允许您在各种数据结构中使用您的产品数据结构 – 树，数组和队列。
希望此信息有助于您的设计决策。
编辑：
由于post被标记为C，因此您使用遵循基本设计原则的void *指针进行等效实现。 例如，请查看：
文档 | list.c | list.h