c - 链接列表以错误的顺序返回值

Question

我已经(尝试)编写了一个 LinkedList，但是，当我遍历列表中的所有元素时，项目的生成顺序与插入顺序不同。

比如说，我这样插入它们:

slist_insert(list, "red");
slist_insert(list, "green");
slist_insert(list, "blue");
slist_insert(list, "yellow");
slist_insert(list, "pink");
slist_insert(list, "purple");
slist_insert(list, "beige");
slist_insert(list, "white");
slist_insert(list, "black");
slist_insert(list, "brown");
slist_insert(list, "fuchsia");
slist_insert(list, "aqua");
slist_insert(list, "magenta");

但是在循环中，这会被产生:

green
magenta
aqua
fuchsia
brown
black
white
beige
purple
pink
yellow
blue
red

请注意，我以前没有这样做过，所以这段代码很有可能充满了与链表算法相关的基本错误:http://codepad.org/Sl0WVeos

这样的代码工作正常，但有几件事让我烦恼:

• 产生了错误的订单(如上所述)
• 必须使用宏(有更好的方法吗？)
• 即使在调用 slist_destroy 之后，仍然存在内存泄漏，我不知道它是从哪里来的

非常感谢您的帮助!

Answer 1

关于错误的商品顺序

slist_impl_insertl() 的逻辑是错误的。

让我们跟随您的代码:

stringlist_t* slist_impl_insertl(stringlist_t* list, const char* str, unsigned int len)
{
    stringlist_t* newnode;
    if(list == NULL) // if the list is empty
    {
        newnode = slist_createl(str, len); // create a new item
        list = newnode;                    // insert the new item at the start of the list
        return list;
    }
    else // if the list is not empty
    {
        if(list->next == NULL) // if it contains only one item
        {
            list = slist_insertb(list, str, len); // insert a new item at the front of the list
            return list;
        }
        else // if it contains more than one item
        {
            newnode = slist_createl(str, len);                // create a new node
            newnode->next = (struct stringlist_t*)list->next; // insert the new node just after the first item !?!.
            list->next = (struct stringlist_t*)newnode;
            return list;
        }
    }
    return list; /* not reached */
}

因此，您的插入过程并不总是在同一位置插入新节点。它有时在开头插入，有时在第二个位置插入。这解释了为什么这些项目以错误的顺序产生。

一个简单的修复是总是在列表的开头插入新节点，然后项目将以相反的顺序产生。或者您可以遍历列表直到到达末尾 (list->next == NULL)，然后在最后一项之后插入新项:

stringlist_t* slist_impl_insertl(stringlist_t* list, const char* str, unsigned int len)
{
    stringlist_t *iter;
    if(list == NULL)
    {
        list = slist_createl(str, len);
    }
    else
    {
        // find the last ist item
        iter = list; 
        while(iter->next!=NULL)
            iter = iter->next;
        // insert the new item at the end of the list
        iter->next = slist_createl(str,len);
    }
    return list;
}

关于使用宏

如果列表为空 (list == NULL)，您的插入过程将修改列表以使其成为第一项。宏负责重新分配修改后的列表。如果您不想使用宏，则必须将列表参数作为指针传递，以便您可以直接在插入过程中修改它。

(一开始写代码的人做到了，这样他就可以在列表中间的任何地方插入一个项目，而不必为此编写特定的程序)

这里是不使用宏的 slist_insert() 的候选实现:

void slist_insert(stringlist_t** list, const char* str)
{
    *list = slist_impl_insertl(*list, str);
}

使用此实现，您必须更改在列表中插入项目的方式:

slist_insert(&list, "red"); // note the use of '&'

关于内存泄漏

销毁过程正在释放存储在每个项目中的字符串，这很好。但是每个项目也是动态分配的，因此它们也需要被释放!你必须临时存储列表指针，前进到下一项，然后释放存储的指针，直到到达列表末尾。

void slist_destroy(stringlist_t* list)
{
    stringlist_t *temp;
    while(list != NULL)
    {
        // free the data contained in the current list item
        free(list->data);
        // save the pointer to the next item
        temp = slist_next(list);
        // free the current item
        free(list);
        // continue with the next item
        list = temp;
    }
}