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

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

请注意，我以前没有这样做过，所以这段代码很可能充满了与链接列表算法相关的基本错误：< a href="http://codepad.org/Sl0WVeos" rel="nofollow">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()< /code> 不使用宏：

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;
    }
}

Answer 2

这里我给你一个我自己做的链表，也许可以帮助你理解这个数据结构（我放了插入和删除节点的函数）

void insert(LISTNODEPTR* sPtr, char item)
{
    LISTNODEPTR previousPtr,currentPtr,newPtr;

    newPtr = malloc(sizeof(LISTNODE));

    if(newPtr != NULL)
        {
        newPtr->value = item;
        newPtr->nextPtr = NULL;

        currentPtr = *sPtr;
        previousPtr = NULL;

        while(currentPtr != NULL && currentPtr->value < item)
        {
            previousPtr = currentPtr;
            currentPtr = currentPtr->nextPtr;
        }

        if(previousPtr == NULL)
        {
            newPtr->nextPtr = *sPtr;
            *sPtr = newPtr;
        }
        else
        {
            previousPtr->nextPtr = newPtr;
            newPtr->nextPtr = currentPtr;
        }
    }
    else
    {
        printf("No memory available\n");
    }
}

void delete(LISTNODEPTR* sPtr,char item)
{
    LISTNODEPTR currentPtr,previousPtr,tempPtr;

    if((*sPtr)->value == item)
    {
        tempPtr = *sPtr;
        *sPtr = (*sPtr)->nextPtr;
        free(tempPtr);
    }
    else
    {
        previousPtr = NULL;
        currentPtr = *sPtr;

        while(currentPtr != NULL && currentPtr->value != item)
        {
            previousPtr = currentPtr;
            currentPtr = currentPtr->nextPtr;
        }
        tempPtr = currentPtr;
        previousPtr->nextPtr = currentPtr->nextPtr;
        free(tempPtr);
    }
}

Answer 3

newnode = slist_createl(str, len);
newnode->next = (struct stringlist_t*)list->next;//1)
list->next = (struct stringlist_t*)newnode;//2)
return list;

列出以下情况下的状态：
green->red->NULL

1)newnode->red->NULL

2)green ->newnode->red->NULL

newnode 总是插入在 green（绿色之后）和 red 之间。

并且，

slist_destroy

slist_destroy 释放字符串缓冲区，而不是释放节点！