C语言实现具有单个值字段的公共链表

最近，当用c编写一些linux程序时，似乎很多地方需要一个可以支持不同类型的值的通用链表，因此我尝试实现一个，但仍然存在一些问题。

方法：

用指针定义一个结构，然后以 char[] 类型的值字段结尾，使用它作为公共结构，
在链表上定义和 impl 方法，使用通用结构，
定义具有不同类型的值字段的新结构类型，
调用函数时，只需将事物转换为通用类型，

代码：（草稿版）

linked_list.h

#ifndef _LINKED_LIST
#define _LINKED_LIST
// common list for any type,
struct llist_item {
    struct llist_item *next;
    char value[1];
};
// int list
struct llist_int {
    struct llist_int *next;
    int value;
};
/**
 * append item to end of list,
 * 
 * @param headp
 *  pointer to head pointer,
 * @param valuep
 *  pointer set value of deleted item into,
 * @param value_size
 *  size of value,
 * @param struct_size
 *  size of actual struct,
 * 
 * @return
 *  pointer to head,
 */
extern struct llist_item *llist_append(struct llist_item **headp, void *valuep, ssize_t value_size, ssize_t struct_size);
/**
 * delete head,
 * 
 * @param headp
 *  pointer to head pointer,
 * @param valuep
 *  pointer set value of deleted item into,
 * 
 * @return
 *  pointer to new head,
 */
extern struct llist_item *llist_del_head(struct llist_item **headp, char *valuep);
#endif

linked_list.c

// linked_list utility
#include <stdio.h>
#include <string.h>
#include <errno.h>
#include <stdlib.h>
#include "linked_list.h"
/*
   printf("error while linked_list: %sn", strerror(errno));
   printf("linked_list succeedn");
 */
struct llist_item *llist_append(struct llist_item **headp, void *valuep, ssize_t value_size, ssize_t struct_size) {
    struct llist_item *head = *headp;
    // create new item
    struct llist_item *new_item = (struct llist_item*) malloc(struct_size);
    new_item->next = NULL;
    memcpy(&(new_item->value), valuep, value_size);
    // append new item
    if(head == NULL) { // empty queue,
        head = new_item;
        *headp = head;
    } else {
        // find last item
        struct llist_item *tail = head;
        while(tail->next != NULL) {
            tail = tail->next;
        }   
        tail->next = new_item;
    }
    return head;
}
struct llist_item *llist_del_head(struct llist_item **headp, char *valuep) {
    struct llist_item *head = *headp;
    if(head == NULL) {
        return NULL;
    } else {
        memcpy(valuep, &(head->value), sizeof(*valuep));
        *headp = head->next;
        free(head);
        return *headp;
    }
}

llist_test.c

// linked_list test
#include <stdio.h>
#include <string.h>
#include <errno.h>
#include <stdlib.h>
#include "linked_list.h"
int linked_list_test() {
    struct llist_int *int_list = NULL; // it's important to initialize this pointer as NULL explicitly,
    int i;
    for(i=1; i<=5; i++) {
        llist_append((struct llist_item **) &int_list, (void *) &i, sizeof(int), sizeof(struct llist_int));
    }
    struct llist_int *int_item;
    int value;
    if(int_list != NULL) {
        do {
            (struct llist_int *)llist_del_head((struct llist_item **) &int_list, (char *) &value);
            printf("%dn", value);
        } while (int_list!= NULL);
    }
    return 0;
}
int main(int argc, char * argv[]) {
    return linked_list_test();
}

编译和运行

代码列表：

linked_list.h，标题，
linked_list.c，实施，
llist_test.c，做测试，

编译 - 用于测试：

gcc -Wall linked_list.c llist_test.c -o a.out

执行：

.
/a.out

问题：

铸造很复杂，有没有简化的方法？

在测试方法linked_list_test()：

如果更改：

    do {
        int_item = (struct llist_int *)llist_del_head((struct llist_item **) &int_list, (char *) &value);
        printf("%dn", value);
    } while (int_item != NULL);

自

    do {
        (struct llist_int *)llist_del_head((struct llist_item **) &int_list, (char *) &value);
        printf("%dn", value);
    } while (int_list!= NULL);

然后结果是挥舞，而不是输出：

1 2 3 4 5

它输出：

32513 32514 32515 32516
32517

区别在于指针投射，为什么会使结果不同？

@Update - 关于第二个问题

正如评论中所描述@BLUEPIXY，确实sizeof(*valuep)导致了问题，现在我修改了llist_del_head()，并在参数列表中明确提供了大小，并修复了问题。

该函数现在如下所示：

extern struct llist_item *llist_del_head(struct llist_item **headp, char *valuep, ssize_t value_size);

这种方法有几个问题：

您在结构中留出的空间只有 1 个字节，您不能在其中存储大于 1 字节的类型。
如果要在那里为较大的类型腾出空间，则仍然会遇到对齐问题：较大的类型可能需要与编译器在struct llist_item *后为char数组假定的对齐方式不同的对齐方式。因此，即使在结构中使用可变大小的尾随数组也不能提供可行的解决方案。

您可以使用void *并单独分配值，但这是浪费，或者使用宏来实现不同类型的源代码模板，但这很麻烦且容易出错。

C 语言没有适合这种概念的结构，C++以更大的复杂性为代价。

我不确定你想做什么，但我建议：

不要导出.h文件中列表的定义。用户不需要知道实现。
请注意，您的struct llist_item只能容纳一个字符。将其更改为void *以便它可以保存指向任何类型的值的指针。
必须在llist_append中传递结构大小似乎很奇怪，因为这是列表结构的大小加上要存储的值的大小。但这与您希望如何存储"任何价值"有关

通常，用户希望您维护指向列表必须存储的数据的指针。您的 .h 文件可能看起来像：

/* append pointer valuep to the list */
void *llist_append(void **list, void *valuep, ssize_t value_size);
/* delete the list element that contains pointer valuep */
void *llist_del_head(void **list, void *valuep);

和您的实施：

// common list for any type,
struct llist_item {
    struct llist_item *next;
    void *value;
};

并附加：

// create new item
struct llist_item *new_item = malloc(sizeof(struct llist_item));
new_item->next = NULL;
new_item->value= valuep;

方法：

代码：（草稿版）

编译和运行

相关内容

最新更新

热门标签：

C语言 实现具有单个值字段的公共链表

方法：

代码：（草稿版）

编译和运行

相关内容

最新更新

热门标签：

C语言实现具有单个值字段的公共链表