C 通用链表 [英] C generic linked-list

问题描述

我有一个包含 void* 类型数据的通用链表我试图用类型 struct employee 填充我的列表，最终我也想销毁对象 struct employee.

I have a generic linked-list that holds data of type void* I am trying to populate my list with type struct employee, eventually I would like to destruct the object struct employee as well.

考虑这个通用链表头文件(我已经用 char* 类型对其进行了测试):

Consider this generic linked-list header file (i have tested it with type 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; 
} 

现在考虑这个将从 main() 调用的示例测试用例:

Now consider this sample testcase that will be called from main():

    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
", ((struct employee*)secondList.head->data)->name);   //cast to type struct employee
      printf("Employee2: %s
", ((struct employee*)secondList.tail->data)->name);  
    }

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

Why does the answer that I posted below solve my problem? I believe it has something to do with pointers and memory allocation. The function Malloc() that i use is a custom malloc that checks for NULL being returned.

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

Here is a link to my entire generic linked list implementation: https://codereview.stackexchange.com/questions/13007/c-linked-list-implementation

推荐答案

问题在于这个 accList_allocate() 和你对它的使用.

The problem is this accList_allocate() and your use of it.

struct accList secondList;
accList_allocate(&secondList);

在原来的 test2() 中，secondList 是栈上的内存.&secondList 是指向该内存的指针.当您调用 accList_allocate() 时，将传入指向堆栈内存的指针副本.Malloc() 然后返回一块内存并将其分配给指针的副本，而不是原始的 secondList.

In the original test2() secondList is memory on the stack. &secondList is a pointer to that memory. When you call accList_allocate() a copy of the pointer is passed in pointing at the stack memory. Malloc() then returns a chunk of memory and assigns it to the copy of the pointer, not the original secondList.

回来后，secondList 仍然指向堆栈上未初始化的内存，因此对 appendToEnd() 的调用失败.

Coming back out, secondList is still pointing at uninitialised memory on the stack so the call to appendToEnd() fails.

除了 secondList 恰好没有垃圾之外，答案也是如此.可能是偶然的，也可能是编译器的设计.无论哪种方式，它都不是您应该依赖的东西.

The same happens with the answer except secondList just happens to be free of junk. Possibly by chance, possibly by design of the compiler. Either way it is not something you should rely on.

要么:

struct accList *secondList = NULL;

accList_allocate(&secondList);

并更改 accList_allocate()

And change 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() 因为它不分配

With accList_allocate() changed to accList_initialise() because it does not allocate

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

这篇关于C 通用链表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！