如何在C语言中实现链表？

Question

如何在C语言中实现链表？

clinked-list

11

我正在创建一个链表，就像我之前提出的问题一样。我发现开发链表的最佳方法是在另一个结构中拥有头和尾。我的产品结构将嵌套在这个结构中。我应该将列表传递给添加和删除函数。我发现这个概念很困惑。

我已经实现了初始化、添加和清除。然而，我不确定我是否做得正确。

当我向列表中添加一个产品时，我使用calloc声明一些内存。但是我在想，难道我不应该为产品声明内存吗？我真的很困惑这个添加过程。

非常感谢您的任何建议，

#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;
}

============================== 编辑 ============================

#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;
}

- ant2009

initialize() 函数中的代码一定有问题（你只需要写其中一个赋值语句，但这没有任何好处）；你可能想要写 list->head = NULL; list->tail = NULL; 而在 clean_up() 中也存在类似的问题。 - Jonathan Leffler

相关：https://codereview.stackexchange.com/questions/139482/generic-doubly-linked-list-in-c - Ciro Santilli OurBigBook.com

14个回答

7

可以说你希望你的列表数据结构是独立于它所存储的数据之外的。

比如说你有：

struct Whatever
{
   int x_;
}

然后你的列表结构应该像这样：

struct Whatever_Node
{
   Whatever_Node* next_
   Whatever* data_
}

Ryan Oberoi发表了类似的评论，但没有例子。

- Craig Wright

5

在您的情况下，头和尾可以简单地指向链表的开头和结尾。对于单向链表，只需要头部即可。最基本的链表可以使用如下结构体创建：

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遍历列表。但有时为了使列表遍历更容易并存储任何其他关于列表的数据，会使用head和tail token，并将它们包装成自己的结构，就像你所做的那样。因此，您的添加和初始化函数将是以下内容（减去错误检测）。

    // 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是正确的，使用链表玩耍是熟练掌握指针和间接引用的好方法。它们也是练习递归的好方法！当你熟练掌握链表后，尝试构建一棵树并使用递归来遍历树。

- jhufford

1

你好，感谢你的帮助。然而，看了其他评论后，我正在尽可能地将我的链表泛化。就像kung提到的那样，将列表数据与外部数据分离开来。因此，我已经更改了我的结构，使其中一个仅包含数据，另一个仅包含列表数据。但是，我不确定我应该如何处理我在产品地址中分配的list->data。我认为我仍然缺乏一些理解。谢谢。 - ant2009

2

我这里不写代码，但你需要按照以下步骤操作：

创建一个列表对象，它将在程序的整个生命周期内保持全局。
分配 product_data_t 的大小。
对于第一个元素（头部为空），将头指向分配的地址。
要添加下一个元素，请移动到列表的末尾，然后将分配地址的指针添加到最后一个元素的下一个位置。（最后一个元素的下一个位置始终为NULL，这样就可以遍历到结尾了。）
暂时忘记尾巴。

- Naunidh

2

如果你正在学习C指针理论，这是一个很好的练习。否则，对于不是通用的代码（如库），感觉有太多的间接引用。

与其分配一个静态的128字节字符串，你可能想要进行更多的指针练习，并使用分配的确切长度字符串，在退出时清理它。

从学术上讲，kungfucraig的结构看起来比你定义的更加通用。

- nik

1

在内存中，您的项目通过列表结构中的指针链接在一起

项目1 -> 项目2

为什么不将列表结构作为项目的一部分？

然后，您可以分配一个产品项目，并且列表结构就在其中。

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;

- justinhj

1

你正在为list_t结构分配空间，只是指向列表头和尾的指针，这不是你想要做的。

当你添加到链表时，应该为实际节点（即product_data_t结构）分配空间。

- user447688

1

你正在分配错误的内存块。不是为每个列表元素分配内存，而是为列表头和尾分配内存。

为了简单起见，去掉头和尾的单独结构。将它们变成全局变量（与现在相同的作用域），并将它们更改为listhead和listtail。这将使代码更易读（您不必通过单独的结构进行无谓的操作），您也不会错误地分配不正确的结构。

除非要创建双向链表，否则不需要尾指针。一旦创建了链接列表，添加它不是主要因素，但也不是必需的。

- Andrew Scagnelli

1

我认为您首先需要想象后端。代码并不是非常重要。请访问此处并可视化所有插入的基本C代码。 1）在开头插入{{link1：访问并滚动以获取后端的每个指令执行}} 您需要前端和想象，请转到此处 后端想象

其他所有可能的插入都在这里。

而且重要的事情是您可以使用以下方式。

struct Node{
int data;//数据字段
struct Node* next; //指针字段
};

结构体Node * head，* tail; //尝试这种方式

或者快捷方式

struct Node{
int data;//数据字段
struct Node* next; //指针字段
}*head，*tail; //全局根指针

并且

<< {{link3：点击}} >> 可视化其他链表问题。

谢谢。

- nandu deshmukh

1

一个展示单向链表的演示。如果您想要的话，可以尝试查看循环链表和双向链表。

#include <stdio.h>
#include <stdlib.h>


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/

- debug

在您的pop_head()函数中，这里释放head会导致未定义的行为吗？您释放了head，然后又使用了*head。 - scrollout

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Brandon E Taylor · Accepted Answer

如果您想更好地了解链表的基础知识，请查看以下文档：

http://cslibrary.stanford.edu/103/LinkedListBasics.pdf