C通用链表

Question

我是一名有用的助手，可以为您进行翻译。以下是您需要翻译的内容：

我有一个通用的链表，保存void*类型的数据。我想使用struct employee类型的数据填充我的链表，最终我也想析构struct employee对象。

考虑这个通用的链表头文件（我已经测试过它可以使用char*类型）:

struct accListNode                 //the nodes of a linked-list for any data type
{
  void *data;                     //generic pointer to any data type
  struct accListNode *next;       //the next node in the list
};

struct accList                    //a linked-list consisting of accListNodes
{
  struct accListNode *head;
  struct accListNode *tail;
  int size;
};

void accList_allocate(struct accList *theList);           //allocate the accList and set to NULL
void appendToEnd(void *data, struct accList *theList);    //append data to the end of the accList
void removeData(void *data, struct accList *theList);         //removes data from accList
  --------------------------------------------------------------------------------------

考虑员工结构。

struct employee 
{ 
   char name[20]; 
   float wageRate; 
} 

现在考虑这个将从主函数调用的样本测试用例：

    void test2()
    {
      struct accList secondList;
      struct employee *emp = Malloc(sizeof(struct employee));
      emp->name = "Dan";
      emp->wageRate =.5;

      struct employee *emp2 = Malloc(sizeof(struct employee));
      emp2->name = "Stan";
      emp2->wageRate = .3;

      accList_allocate(&secondList);
      appendToEnd(emp, &secondList);
      appendToEnd(emp2, &secondList);

      printf("Employee: %s\n", ((struct employee*)secondList.head->data)->name);   //cast to type struct employee
      printf("Employee2: %s\n", ((struct employee*)secondList.tail->data)->name);  
    }

为什么我下面发布的答案解决了我的问题？我相信这与指针和内存分配有关。我使用的函数Malloc()是一个自定义的malloc，它检查是否返回NULL。

这是我整个通用链表实现的链接：https://codereview.stackexchange.com/questions/13007/c-linked-list-implementation

- CodeKingPlusPlus

---

如果你在调试器中运行此代码，你会知道哪一行引起了错误。 - Oliver Charlesworth

@Oli Charlesworth: Ted? 一部保证令人讨厌的"恶味练习" ;) - paulsm4

"如果你想要往未分配的内存中写入内容，那么应该使用strcpy(emp->name, "Dan")吗？" - Jim Balter

请阅读赏金下面的文本。那是我感兴趣的内容。 - CodeKingPlusPlus

让人困惑的是问题中有相关的代码，而回答中也有。@CodeKingPlusPlus，你所询问的代码应该在问题中。 - ggorlen

Answer 1

问题在于accList_allocate()以及您对其使用的方式。

struct accList secondList;
accList_allocate(&secondList);

在原始的test2()函数中，secondList是存储在堆栈上的内存。&secondList是指向该内存的指针。当调用accList_allocate()函数时，传递了指向堆栈内存的指针副本。然后，malloc()函数返回一块内存并将其分配给指针副本，而不是原始的secondList。

回到外部时，secondList仍然指向未初始化的堆栈内存，因此调用appendToEnd()函数失败。

答案中发生的情况与此相同，只是secondList恰好没有垃圾。这可能是偶然的，也可能是编译器设计的。无论哪种方式，都不应该依赖它。

要么：

struct accList *secondList = NULL;

accList_allocate(&secondList);

需要修改accList_allocate()函数。

accList_allocate(struct accList **theList) {
    *theList = Malloc(sizeof(struct accList));
    (*theList)->head = NULL;
    (*theList)->tail = NULL;
    (*theList)->size = 0;
}

或者

struct accList secondList;

accList_initialise(secondList);

由于accList_allocate()不分配内存，因此已更改为accList_initialise()。

accList_initialise(struct accList *theList) {
    theList->head = NULL;
    theList->tail = NULL;
    theList->size = 0;
}

- SpacedMonkey

Answer 2

我认为你的问题在于：

1. 在你原来的test2函数中，你在堆栈上分配了secondList。
2. 堆栈内存可能是脏的，所以secondList需要初始化。
3. 你的accList_allocate函数接受一个指向列表的指针，但随后用Malloc调用覆盖它。这意味着你传入的指针从未被初始化。
4. 当test2尝试运行时，它会遇到坏指针（因为内存没有被初始化）。

当你在main中分配它时，它能够工作的原因是你的C编译器可能会在程序启动时将堆栈清零。当main在堆栈上分配变量时，该分配是持久的（直到程序结束），因此当你在main中分配secondList时，它实际上是正确初始化的，而且是偶然的。

你当前的accList_allocate实际上没有初始化传入的指针，而且你的其余代码永远不会看到它使用Malloc分配的指针。为了解决这个问题，我建议创建一个新函数：accList_initialize，它的唯一任务是初始化列表：

void accList_initialize(struct accList* theList)
{
    // NO malloc
   theList->head = NULL;
   theList->tail = NULL;
   theList->size = 0;
}

在您原来的test2函数中，使用这个代替accList_allocate。如果您真的想在堆上分配列表，那么您应该这样做（不要将其与在堆栈上分配的结构混合使用）。让accList_allocate 返回指向已分配结构的指针：

struct accList* accList_allocate(void)
{
   struct accList* theList = Malloc( sizeof(struct accList) );
   accList_initialize(theList);
   return theList;
}

- sfstewman

---

验证正确性的一种方法是在堆栈上分配数据结构之后，但在调用accList_allocate之前将其打印出来。使用类似于printf（“size =％lu head =％p tail =％p \ n”，secondList-> size，secondList-> head，secondList-> tail）;的东西。 - sfstewman

Answer 3

这可能取决于您的员工结构是如何设计的，但您应该注意

strcpy(emp->name, "Dan");

并且

emp->name = "Dan";

函数的行为不同。特别是后者很可能是总线错误的来源，因为通常不能以这种方式写入字符串字面值。尤其是如果您的代码有类似于

name = "NONE"

或类似的内容。

编辑：好吧，那么对于员工结构的设计，问题在于：

您无法分配给数组。 C标准包括可修改的lvalue列表，而数组不是其中之一。

char name[20];
name = "JAMES" //illegal

strcpy很好 - 它只是转到由name [0]解引用的内存地址，并一次一个字节地将“JAMES \ 0”复制到那里的内存中。

- argentage

---

我的答案使用了strcpy。我正在寻找为什么我的答案解决了我的问题。我相信这与指针和分配有关。"我的答案"是作为一个字面的堆栈溢出答案发布的。 - CodeKingPlusPlus

我正在尝试回答那个问题，但你遗漏了关键部分（员工结构的设计）。你的回答还意味着修复来自重新安排内存分配范围（“当我将secondList的声明和分配放在main()中，并将其余部分放在函数中时，它就可以工作”）。 - argentage

好的，你所拥有的结构格式让问题更加清晰。 - argentage

Answer 4

根据上述问题，我看到两件事情出了问题。

你所见到的是未定义的行为，并且由此引起了总线错误消息，因为你正在将字符串文字分配给变量，而实际上你应该使用 strcpy 函数，你已经相应地编辑了原始代码，所以在将来要记住这一点 :)

使用单词 Malloc 会导致混淆，特别是在同行评审中，评审员会脑抽并说“哇，这是什么，难道不应该是 malloc 吗？” 并很可能提出。 （基本上，不要调用与 C 标准库函数具有类似名称的自定义函数）

你没有检查 NULL，如果你升级版的 Malloc 失败了，那么 emp 就会是 NULL！无论多么琐碎，都要检查它，即使你认为“啊，平台上有大量内存，4GB RAM 没问题，不必检查 NULL”

看一下其他地方发布的这个问题，以解释什么是总线错误。

编辑：使用链表结构，在函数中调用参数对于理解它非常重要。注意使用&，意思是取指向链表结构的变量的地址，并且通过引用传递，而不是按值传递，后者是变量的副本。这个规则同样适用于指针的使用 :)

在你的问题的第一个代码中，你的参数有点错了，如果你在参数列表中使用双指针，那么使用&secondList就可以了。

- t0mm13b

---

我刚刚发布了Malloc的作用，它只是检查NULL。请阅读赏金下面的文本并回答该文本... - CodeKingPlusPlus

不，这是为了让我拥有通用的链表并进行练习。下一步将是在释放列表中的节点时释放“对象类型”。我打算使用函数指针来调用对象的释放函数。 - CodeKingPlusPlus