C通用链表-比较无效指针

我正在写一个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*

此示例代码。。。

List list = NewList(char);

。。。表明CCD_ 1被实现为宏。假设List显然是一个成员名为elementSize的结构类型，并且宏只使用类型名称，则宏必须根据类型名称计算elementSize(否则不初始化(。

但是，该宏应该如何从类型char中知道作为成员呈现的实际字符串的长度呢？你真的打算当成员是字符串时，它们必须都是相同的长度吗？因为这就是通过比较相等元素的含义

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

我假设NewList只是使用sizeof(type)来设置elementSize，但sizeof(char)是1，与NewList0相比，memcmp将只比较每个字符串的第一个字符。(因此，请尝试测试字符串"a"、"b"和"c"。(也就是说，方法(1(对字符串的问题在于您指定了错误的类型。对于您正在呈现的特定测试字符串，您可能会使用

List list = NewList(char[9]);

，因为所有列表元素都是char的9元素数组。

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

哪种方式是正确的？C#是如何做到的？

C#也不是这样做的，至少如果通过"；C#"；你指的是它的List<T>类。根据该类的文档：

List<T>类同时使用相等比较器和排序比较器。
Contains、IndexOf、LastIndexOf和Remove等方法对列表元素使用相等比较器。默认相等比较器对于类型CCD_ 22如下确定。如果类型T实现IEquatable<T>通用接口，则等式comparer是该接口的Equals(T)方法；否则，默认相等比较器为CCD_ 27。
诸如BinarySearch和Sort之类的方法对列表元素使用排序比较器。[…]

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) // ...

好吧，这很棘手，但我将在@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;
}

任何改进都是绝对可以接受的！

示例：

我将元素添加到列表的方式：

相关内容

最新更新

热门标签：