鏈接列表以錯誤的順序返回值

我已經（試過）寫一個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

鏈接列表以錯誤的順序返回值

回答

相關問題