C 通用链表 - 比较 void 指针

Question

我正在写一个 LinkedList 作为练习，我会更进一步，因为我喜欢它。然而，我被困在这个：
我会按值从列表中删除一个元素，例如 C#。
我有这个代码：

int M_List_RemoveItemFromList(List list, void* value)
{
    NodeList lastNode = NULL;
    NodeList currentNode = *(list->nodes);
    while (currentNode)
    {
        // 1. if (memcmp(value, currentNode->data, list->elementSize) == 0)
        // 2. if (value == currentNode->data)
        {
            if (lastNode)
            {
                lastNode->next = currentNode->next;
            }
            else {
                *(list->nodes) = currentNode->next;
            }
            currentNode->next = NULL;
            --list->length;
            return 0;
        }
        lastNode = currentNode;
        currentNode = currentNode->next;
    }
    return 1;
}

我评论了两行，因为它们适用于不同的上下文。

适用于像 int 这样的值，它会删除具有正确 int 值的元素。它不适用于“字符串”，在那种情况下它会删除第一个元素，这无关紧要。
适用于字符串，不适用于 int 值。

哪种方法正确？ C# 是怎么做到的？
如果您需要更多信息，请告诉我。

示例：

List list = NewList(char);
char* stringa = "Test 001";
AppendList(list, stringa);
AppendList(list, "Test 002");
AppendList(list, "Test 003");
AppendList(list, "Test 004");
AppendList(list, "Test 005");
AppendList(list, "Test 006");

PrintStringList(list);
PrintNewSection();

M_List_RemoveItemFromList(list, "Test 004"); // It removes the first element with (1. commented row) and the right one with (2. commented row)
M_List_RemoveItemFromList(list, "Test 001"); // It removes the first element with (1. commented row) and the right one with (2. commented row)
M_List_RemoveItemFromList(list, "Test 006"); // It removes the first element with (1. commented row) and the right one with (2. commented row)
PrintStringList(list);
PrintNewSection();

List list2 = NewList(int);

int a = 101;
int b = 2;
int c = 2;
    
AppendList(list2, &a);
AppendList(list2, &b);
M_List_RemoveItemFromList(list2, &c); // it doesn't remove anything with 2. and the right one with 1.
PrintIntList(list2);

我向列表添加元素的方式：

NodeList M_List_Append(List list, void* value)
{
    NodeList element = malloc(sizeof(T_NodeList) * list->elementSize);
    if (!element) return NULL;
    element->data = value;
    NodeList tail = M_List_GetTail(list);
    if (!tail)
    {
        *(list->nodes) = element;
    }
    else
    {
        tail->next = element;
    }
    element->next = NULL;
    ++list->length;
    if (list->length > list->capacity - 2)
        M_List_IncreaseSize(list);
    return element;
}

这是列表结构：

typedef struct S_NodeList
{
    void* data;
    struct S_NodeList* next;
} T_NodeList;

#define NodeList T_NodeList*
#define HeadList NodeList*

typedef struct S_List
{
    HeadList nodes;
    size_t elementSize;
    size_t capacity;
    size_t length;
} T_List;

#define List T_List*

Answer 1

好吧，这很棘手，但我会在@akatz 评论后回答这个问题。

我定义了一个宏：

#define List_RemoveValueFromList(list, value) \
    _Generic((value), \
    int: M_List_RemoveIntFromList, \
    char*: M_List_RemoveStringFromList) \
    (list, value);

然后我创建了两个具有不同比较的函数和一个删除函数（为了避免重复代码）：

void M_List_Remove(List list, NodeList lastNode, NodeList currentNode)
{
    if (lastNode)
    {
        lastNode->next = currentNode->next;
    }
    else {
        *(list->nodes) = currentNode->next;
    }
    currentNode->next = NULL;
    --list->length;
}

int M_List_RemoveIntFromList(List list, int value)
{
    NodeList lastNode = NULL;
    NodeList currentNode = *(list->nodes);
    while (currentNode)
    {
        if (value == *((int*)currentNode->data))
            //if (value == currentNode->data)
        {
            M_List_Remove(list, lastNode, currentNode);
            return 0;
        }
        lastNode = currentNode;
        currentNode = currentNode->next;
    }
    return 1;
}

int M_List_RemoveStringFromList(List list, char* value)
{
    NodeList lastNode = NULL;
    NodeList currentNode = *(list->nodes);
    while (currentNode)
    {
        if (strcmp(value, (char*)(currentNode->data)) == 0)
        {
            M_List_Remove(list, lastNode, currentNode);
            return 0;
        }
        lastNode = currentNode;
        currentNode = currentNode->next;
    }
    return 1;
}

绝对接受任何改进！

Answer 2

这个示例代码...

List list = NewList(char);

... 建议将 NewList 作为宏实现。鉴于 List 显然是一个结构类型，其成员名为 elementSize，并且宏仅使用类型名称，宏必须根据类型名称计算 elementSize（否则保持未初始化状态).

但是那个宏应该如何从类型 char 中知道作为成员呈现的实际字符串的长度？你是否真的打算当成员是字符串时，它们的长度必须相同？因为这就是通过

比较元素是否相等的含义

    memcmp(value, currentNode->data, list->elementSize)

我想 NewList 只是用 sizeof(type) 来设置 elementSize，但是 sizeof(char) 是 1，所以 elementSize，memcmp 将只比较每个字符串的第一个字符。（因此尝试测试字符串 "a"、"b" 和 "c"。）也就是说，字符串的方法 (1) 的问题是您指定了错误的类型。对于您提供的特定测试字符串，您可以使用

List list = NewList(char[9]);

，因为所有列表元素都是 char.

的 9 元素数组

另一方面，您的方法 (2) 比较存储在列表中的指针的值。这在语义上是完全不同的，但不一定是错误的。它评估指定的指针是否指向与存储在列表中的对象相同的对象。您有点（不）幸运它对您的字符串测试有效——您的编译器显然正在合并相同的字符串文字，这不是必需的。

Which is the right way? How C# does it?

C# 的实现方式也不是，至少如果“C#”是指它的 List<T> class。根据 that class's documentation:

The List<T> class uses both an equality comparer and an ordering comparer.

Methods such as Contains, IndexOf, LastIndexOf, and Remove use an equality comparer for the list elements. The default equality comparer for type T is determined as follows. If type T implements the IEquatable<T> generic interface, then the equality comparer is the Equals(T) method of that interface; otherwise, the default equality comparer is Object.Equals(Object).

Methods such as BinarySearch and Sort use an ordering comparer for the list elements. [...]

IList<T> 的其他实现方式可能有所不同。事实上，它的文档（继承自 ICollection<T>）明确指出“实现在确定对象相等性方面可能会有所不同”。

C 中最接近的等效项是为您的 List 结构提供一个成员，该成员指向一个用于比较元素和测试值是否相等的函数。例如，

/*
 * returns less than zero, zero, or greater than zero, corresponding to
 * whether o1 is to be considered less than, equal to, or greater than o2
 */
typedef int compare_func(const void *o1, const void *o2);

typedef struct S_List {
    HeadList nodes;
    // size_t elementSize; // probably not needed
    size_t capacity;
    size_t length;
    compare_func *compare;
} T_List;

用户需要指定适合元素类型的函数。此类函数的示例可能包括：

int compare_strings(const void *o1, const void *o2) {
    return strcmp((const char *) o1, (const char *) o2);
}

int compare_ints(const void *o1, const void *o2) {
    int i1 = *(int *)o1;
    int i2 = *(int *)o1;

    if (i1 < i2) return -1;
    else if (i1 > i2) return 1;
    else return 0;
}

像您的 M_List_RemoveItemFromList() 这样需要在适合列表的意义上比较对象是否相等的函数将使用指定的函数来执行此操作。相等比较将如下所示：

if (list->compare(value, currentNode->data) == 0) // ...

C 通用链表 - 比较 void 指针

C Generic Linked List - Compare void pointer

c

compare

linked-list

void-pointers

示例：

我向列表添加元素的方式：