尝试在C中创建一个链表:我可以导入一个c++头文件

现在我正在研究malloc()的实现，并希望使用链表跟踪空闲块。除了，我不知道标准C库是否为程序员提供了一个"链表"，但显然c++提供了。

否则，谁能提供一些关于如何实现链表的指导?

没有标准的C语言链表;如果你决定自己动手，可以去维基百科看看，但我不建议你这么做。

bsd和Linux会给你sys/queue.h;见男士3排队。但这不是标准的。

就我个人而言，如果我用C语言工作并且需要标准的数据结构，我通常使用Glib。(http://developer.gnome.org/glib)

不，你真的不能。

c++带有映射到一些C的头(如XYZ.h和cXYZ)，它可以使用和链接到正确标记的C代码(参见extern "C")。

但是你不能走相反的路。c++头文件将包含各种美妙的c++内容，这些内容是你的C编译器无法理解的(如果它们被理解，那么它们就是真正的C头文件)。

如果你想实现一个链表，网上有成千上万的纯c示例。

或者这里有一个非常简单的开始(没有错误检查malloc，简单的FIFO队列):

#include <stdio.h>
#include <stdlib.h>
typedef struct sNode {
    int payload;
    struct sNode *next;
} tNode;

void listAppend (tNode **pFirst, tNode **pLast, int val) {
    tNode *node;
    node = malloc (sizeof (tNode));
    node->payload = val;
    node->next = NULL;
    printf ("Append %d: ", val);
    if (*pFirst == NULL) {
        *pFirst = node;
        *pLast = node;
        return;
    }
    (*pLast)->next = node;
    *pLast = node;
}

int listRemove (tNode **pFirst, tNode **pLast) {
    int val;
    tNode *node;
    if (*pFirst == NULL)
        return -999;
    node = *pFirst;
    *pFirst = (*pFirst)->next;
    if (*pFirst == NULL)
        *pLast = NULL;
    val = node->payload;
    printf ("Remove %d: ", val);
    free (node);
    return val;
}

void dump (tNode* n) {
    printf ("list = [");
    while (n != NULL) {
        printf (" %d", n->payload);
        n = n->next;
    }
    printf (" ]n");
}

int main (int argc, char *argv[]) {
    int val;
    tNode *first = NULL;
    tNode *last = NULL;
    while (argv[1] != NULL) {
        if (*argv[1] == '-')
            val = listRemove (&first, &last);
        else
            listAppend (&first, &last, atoi (argv[1]));
        dump (first);
        argv++;
    }
    return 0;
}

pax$ ./testprog 10 20 30 15 25 - - - - - -

输出为:

Append 10: list = [ 10 ]
Append 20: list = [ 10 20 ]
Append 30: list = [ 10 20 30 ]
Append 15: list = [ 10 20 30 15 ]
Append 25: list = [ 10 20 30 15 25 ]
Remove 10: list = [ 20 30 15 25 ]
Remove 20: list = [ 30 15 25 ]
Remove 30: list = [ 15 25 ]
Remove 15: list = [ 25 ]
Remove 25: list = [ ]
list = [ ]

可以包含一个c++头文件，只要这个文件的内容是在C和c++支持的子集中编写的(这是大部分但不是全部的C)，它就会工作。如果你考虑的是c++ std::list，那么你就不走运了，它不会在C中工作。

你必须自己创建一个链表。对于您的用例来说，一个转发列表就足够了(与双链表相反)。您可以将next指针嵌入到您正在分配的同一块中，使其成为侵入性列表。

更新:

下面是伪代码如何处理malloc( N )

struct bookkeeping {
    std::size_t size;
    void* next;
};
void* malloc( std::size_t N )
{
    unsigned char* ptr = ...get ahold of a memory block of size N + sizeof( bookkeeping )...
    bookkeeping* info = ptr;
    info->size = N;
    ...fill the bookkeeping information...
    return ptr + sizeof(bookkeeping);
}
void free( void* ptr )
{
    bookkeeping* info = (unsigned char*)ptr - sizeof( bookkeeping );
    ...free the block pointed to by `info`...
}

还记得考虑对齐

不能在C文件中包含c++头文件。但是你可以在C中使用c++代码。

mymodule.c想包含c++ utility.h，但是它不能。

写C_utility.h和C_utility.cpp。h只使用C语言特性。它声明了一些函数，通常是一些不透明的类型，它们基本上作为void指针呈现给C语言。(有一些更好的技术可以让C编译器至少检查类型是否匹配，但不给它任何关于类型的信息。)不透明类型实际上是指向c++对象的指针，但C并不知道这一点。你从头文件中声明的函数中取出指针，然后把它们发回头文件。

C_utility.cpp包含utility.h。cpp包含c++代码。您可以定义类。只有来自C_utility,h的函数签名被限制为C语法。函数体可以构造c++类之类的东西。

mymodule.c包含C_utility.h.

用c++编译器编译C_utility.cpp，用C编译器编译mymodule.c。两个编译器都会生成。o文件，并且链接器能够将这两种。o文件组合在一起。

出于您的目的，您可以创建C_linkedlist.h和C_linkedlist.cpp，它们为链表公开一个C接口。然后可以创建包含C_linkedlist.h的malloc.c。或者您可以创建C_malloc.h和C_malloc.cpp，其中C_malloc.h只包含C语法，而C_malloc.cpp可以自由地使用c++。

顺便说一下，我不认为使用c++链表的malloc是一个好主意。Malloc会影响性能。它真的应该调到非常快的速度。c++非常快，但增加了一些开销，因为它做了一些在特定情况下可能不需要的"漂亮"的事情。

C语言中没有提供链表实现的标准头文件。

实现链表的标准方法(至少我学到的方法)是1. 声明一个结构体

struct node{
    <datatype> data;
    struct node *next;
    struct node *prev; //if you want a doubly linked list
}

有一个start/head指针指向节点的第一个元素
根据需要动态分配内存。对于创建的第一个节点，开始/头部指针应该指向它。之后，最后一个块(节点)的下一个指针指向新创建的节点。

您可以查看这个或这个以获取更多信息

相关内容

最新更新

热门标签：