如何在C中实现链表? [英] How to implement a linked list in C?
问题描述
我正在创建一个链接列表，就像我之前问的上一个问题一样.我发现开发链表的最佳方法是使头部和尾部处于另一种结构中.我的产品结构将嵌套在此结构中.我应该将列表传递给要添加和删除的功能.我觉得这个概念令人困惑.
I am creating a linked list as in the previous question I asked. I have found that the best way to develop the linked list is to have the head and tail in another structure. My products struct will be nested inside this structure. And I should be passing the list to the function for adding and deleting. I find this concept confusing.
我已经实现了初始化，添加和清理.但是，我不确定我是否正确地做到了.
I have implemented the initialize, add, and clean_up. However, I am not sure that I have done that correctly.
当我将产品添加到列表中时，我使用calloc声明了一些内存.但是我想我不应该声明该产品的内存.我对此增加感到非常困惑.
When I add a product to the list I declare some memory using calloc. But I am thinking shouldn't I be declaring the memory for the product instead. I am really confused about this adding.
非常感谢您的任何建议，
Many thanks for any suggestions,
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#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;
}
==============================编辑================ ===========
============================== Edited ============================
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#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;
}
推荐答案
在您的情况下，标题和结尾可能只是指向链表的开头和结尾.有了一个单独的链表，真正需要的只是头.最基本的说，可以仅使用以下结构来创建链接列表:
In your case the head and tail could simply point to the beginning and end of a linked-list. With a singly linked-list, only the head is really needed. At it's most basic, a linked-list can be made by using just a struct like:
typedef struct listnode
{
//some data
struct listnode *next;
}listnodeT;
listnodeT *list;
listnodeT *current_node;
list = (listnodeT*)malloc(sizeof(listnodeT));
current_node = list;
，并且只要列表始终指向列表的开头并且最后一项设置为NULL，就可以了，可以使用current_node遍历列表.但是有时为了使遍历列表更容易并存储有关列表的任何其他数据，会使用头标记和尾标记并将其包装到它们自己的结构中，就像您所做的那样.因此，您的添加和初始化函数将类似于(减去错误检测)
and as long as list is always pointing to the beginning of the list and the last item has next set to NULL, you're fine and can use current_node to traverse the list. But sometimes to make traversing the list easier and to store any other data about the list, a head and tail token are used, and wrapped into their own structure, like you have done. So then your add and initialize functions would be something like (minus error detection)
// 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
}
}
在这种情况下，由于它是一个单链表，所以尾部仅对将项目追加到列表中真正有用.要插入项目，您必须从头开始遍历列表.真正方便的地方是带有双向链接的列表，它使您可以从任一端开始遍历该列表.您可以像遍历该列表一样
In this case, since it's a singly linked-list, the tail is only really useful for appending items to the list. To insert an item, you'll have to traverse the list starting at the head. Where the tail really comes in handy is with a doubly-linked list, it allows you to traverse the list starting at either end. You can traverse this list like
// 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
}
通常，头和尾是完全构造的节点，它们本身用作标记以表示列表的开头和结尾.他们自己不存储数据(相反，他们的数据代表一个定点令牌)，它们只是正面和背面的占位符.这样可以简化一些处理链表的算法的编码，但必须要有两个额外的元素.总体而言，链表是具有多种实现方式的灵活数据结构.
Often times, the head and tail are fully constructed nodes themselves used as a sentinel to denote the beginning and end of a list. They don't store data themselves (well rather, their data represent a sentinel token), they are just place holders for the front and back. This can make it easier to code some algorithms dealing with linked lists at the expense of having to have two extra elements. Overall, linked lists are flexible data structures with several ways to implement them.
哦，是的，nik是对的，使用链接列表是一种很好的使用指针和间接寻址的方法.而且它们也是练习递归的好方法！熟悉链表后，请尝试接下来构建一棵树，然后使用递归遍历该树.
oh yeah, and nik is right, playing with linked-lists are a great way to get good with pointers and indirection. And they are also a great way to practice recursion too! After you have gotten good with linked-list, try building a tree next and use recursion to walk the tree.
这篇关于如何在C中实现链表?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
