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

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 */
}

因此,您的插入过程并不总是将新节点插入到同一位置.它有时会在开头插入,有时会插入第二个位置.这解释了为什么这些物品的顺序错误.

一个简单的解决方法是始终在列表的开头插入新节点,然后以相反的顺序产生项目.或者您可以遍历列表直到到达end(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),则插入过程将修改列表以使其成为第一个项目.宏负责重新分配修改后的列表.如果您不想使用宏,则必须将list参数作为指针传递,以便可以在插入过程中直接修改它.

(首先编写代码的人使得他可以在列表中间的任何位置插入一个项目而无需编写特定的程序来执行此操作)

这是一个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;
    }
}