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

我已经（试过）写一个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一个电话，还有内存（有没有更好的方式来做到这一点？）泄漏，我不知道它来自哪里

帮助是真正的赞赏！

来源

2011-10-05 hiobs

这是太多的代码。尝试进一步调试它，但首先运行你的代码只添加_one_元素，然后只有两个，然后只有三个。确保您的删除在上述所有三种情况下均有效。你应该能够用笔和纸跟踪你的分配。 – Mat

@Mat噢，我* *已经*用valgrind（分别用'--leak-check = full'）和gdb调试代码，无济于事。即使在循环内部的“slist_destroy”中有一个额外的'free（list）'（在分配给下一个列表之前）也不会关闭内存泄漏。因此，这个问题。 – hiobs

有关错误的项目顺序

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

来源

2011-10-05 08:20:41

我很抱歉地看到，你仍然相信它是功课，真的。 – hiobs

@hiobs：让我们重写代码，以纠正你的问题......我 –

也相应使用您的建议，这是结果：http://codepad.org/E44XRoLZ。非常感谢您的亲切帮助，我们深表谢意。 – hiobs

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

列表状态时：绿光>红色 - > NULL

1）newnode->红色 - > NULL

2）绿 - > newnode->红色 - > NULL

newnode总是插绿之间（后绿色）和红色。

，并

slist_destroy

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

来源

2011-10-05 12:49:10 BLUEPIXY

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

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

来源

2011-10-08 16:05:19 Daniel

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

回答

相关问题