鏈接列表的兩個節點中的合併值

Question

我有一個squeue（棧和隊列的組合）。我有一個叫做mergeFront的函數，它的作用是將前兩個節點合併爲一個。例如，如果前端節點是「alpha」，第二個節點是「beta」，則應將它們合併爲「alphabeta」。

void mergeFront(struct Squeue* squeue){ 
    struct Node* temp; 
    char *string; 
    char *tempstring=malloc(sizeof(char)*100); 
    temp = squeue->first; 
    temp = temp->next; 
    string = squeue->first->val; 
    strcpy(tempstring, string); 
    string = temp->val; 
    strcat(tempstring, string); 
    squeue->first->next->val=tempstring; 
    temp = squeue->first; 
    squeue->first = temp->next; 
    free(temp); 
    free(tempstring); 
} 

當我free(tempstring)在最後一行，即第一個節點現在變成空（假設是因爲我已經free'd什麼值指向）。如果我擺脫了free(tempstring)它運作良好，但有內存泄漏。我怎樣才能在正確釋放內存的情況下執行此操作？

節點的結構如下：

struct Node{ 
    char* val; 
    struct Node* next; 
    struct Node* prev; 
}; 

採取由@ikegami給出的代碼我的代碼如下之後：

void mergeFront(struct Squeue* squeue){ 

    struct Node* node1 = squeue->first; if (node1 == NULL) return; 
    struct Node* node2 = node1->next; if (node2 == NULL) return; 

    char* str1 = node1->val; size_t str1len = strlen(str1); 
    char* str2 = node2->val; size_t str2len = strlen(str2); 
    char* merged = malloc(str1len + str2len + 1); 
    memcpy(merged, str1,str1len + 1); 
    strcpy(merged+str1len, str2); 

    node1->val = NULL; 
    free(node1->val); 
    node1->val = merged; 

    node1->next = node2->next; 

    node2->val = NULL; 
    free(node2->val); 
    free(node2); 

}

它完全只是我運作我仍然在1塊中獲得10bytes的泄漏內存。任何線索，我可以在哪裏找到這個？

Answer 1

void mergeFront(struct Squeue* squeue) { 
    /* Make sure we have at least two nodes. */ 
    struct Node* node1 = squeue->first; if (node1 == NULL) return; 
    struct Node* node2 = node1->next; if (node2 == NULL) return; 

    /* Create the combined string. */ 
    char* str1 = node1->val; size_t str1len = strlen(str1); 
    char* str2 = node2->val; size_t str2len = strlen(str2); 
    char* merged = malloc(str1len + str2len + 1); 
    memcpy(merged, str1, str1len); 
    strcpy(merged+str1len, str2); 

    /* Replace the first node's string with the combined string. */ 
    free(node1->val); 
    node1->val = merged; 

    deleteNode(squeue, node2); 
} 

助手：

void deleteNode(struct Squeue* squeue, struct Node* node) { 
    if (node->prev == NULL) 
     squeue->first = node->next; 
    else 
     node->prev->next = node->next; 

    if (node->next == NULL) 
     squeue->last = node->prev; 
    else 
     node->next->prev = node->prev; 

    free(node->val); 
    free(node);  
} 

注：

• ，因爲它仍然在使用沒釋放被tempstring（現在稱爲merged）指向的內存（由squeue->first->val）！
• 不要猜測你需要多少內存！如有必要計算它。
• * sizeof(char)沒用，因爲sizeof(char)總是1。
• 上面的代碼需要C99支持，因爲它混合了聲明和代碼。它可以很容易地轉換成更多的向後兼容的代碼（以可讀性爲代價）。
• 爲了讓代碼變得清晰，我使用了比我需要更多的變量。
• 經過測試。

---

既然你叫這是一個「堆棧隊列」，這將使使用棧和隊列操作更有意義。

void mergeFront(struct Squeue* squeue) { 
    struct Node* node1 = shift(squeue); 
    if (node1 == NULL) { 
     return; 
    } 

    struct Node* node2 = shift(squeue); 
    if (node2 == NULL) { 
     unshift(squeue, node1); 
     return; 
    } 

    char* str1 = node1->val; size_t str1len = strlen(str1); 
    char* str2 = node2->val; size_t str2len = strlen(str2); 
    node1->val = realloc(node1->val, str1len + str2len + 1); 
    strcpy(node1->val + str1len, node2->val); 

    freeNode(node2); 
    unshift(squeue, node1); 
} 

助手：

void freeNode(struct Node* node) { 
    free(node->val); 
    free(node); 
} 

struct Node* shift(struct Squeue* squeue) { 
    struct Node* node = squeue->first; 
    if (node == NULL) 
     return NULL; 

    squeue->first = node->next; 
    if (node->next == NULL) 
     squeue->last = NULL; 
    else { 
     node->next->prev = NULL; 
     node->next = NULL; 
    } 

    return node; 
} 

struct Node* pop(struct Squeue* squeue) { 
    struct Node* node = squeue->last; 
    if (node == NULL) 
     return NULL; 

    squeue->last = node->prev; 

    if (node->prev == NULL) 
     squeue->first = NULL; 
    else { 
     node->prev->next = NULL; 
     node->prev = NULL; 
    } 

    return node; 
} 

void unshift(struct Squeue* squeue, struct Node* node) { 
    if (squeue->first == NULL) { 
     squeue->first = node; 
     squeue->last = node; 
    } else { 
     node->next = squeue->first; 
     squeue->first = node; 
    } 
} 

void push(struct Squeue* squeue, struct Node* node) { 
    if (squeue->last == NULL) { 
     squeue->first = node; 
     squeue->last = node; 
    } else { 
     node->prev = squeue->last; 
     squeue->last = node; 
    } 
} 

測試。

Answer 2

你想要做什麼：

1. 分配空間給新的字符串
2. 合併的2個串入新的字符串
3. 刪除2個老串
4. 刪除第一個節點，並更新第一個節點
5. 將新字符串分配給新的第一個節點

名

-

void mergeFront(struct Squeue* squeue){ 
    // Make sure there are at least 2 nodes 
    if (NULL == squeue->first || NULL == squeue->first->next) { 
     return; 
    } 

    // 1. Allocate space for the new string 
    char *tempstring = malloc(strlen(squeue->first->val) + 
           strlen(squeue->first->next->val) + 1); 
    if (NULL == tempstring) { 
     // Out of memory 
     return; 
    } 

    // 2. Merge the 2 old strings into the new string 
    sprintf(tempstring, "%s%s", squeue->first->val, squeue->first->next->val); 

    // 3. Delete the 2 old strings 
    free(squeue->first->val); 
    free(squeue->first->next->val); 

    // 4. Delete the first node, and update first node 
    struct Node* temp = squeue->first; 
    squeue->first = squeue->first->next; 
    squeue->first->prev = NULL; 
    free(temp); 

    // 5. Assign the new string to the new first node 
    squeue->first->val = tempstring; 
} 

Answer 3

這似乎很奇怪

squeue->first->next->val=tempstring; 
temp = squeue->first; 
squeue->first = temp->next; 
free(temp); 
free(tempstring); 

首先你分配tempstring並分配一個指針VAL指向它，但後來你釋放它做什麼VAL點無效。

看來你應該以合併這兩個節點跳過free(tempstring)

。首先檢查兩個字符串的長度以分配足夠的空間，而不是假設100就足夠了。分配可以包含在兩個串兩個串加上結束\ 0即使用strlen（）和1.

其後的strcpy/strcat的兩個值添加到緩衝器的緩衝器。

然後釋放第一和第二節點指向

的字符串，然後將第一個節點指向這個新節點

，然後設置的第一個節點的指針，以消除第二，做不要忘記釋放第二個節點。即每個節點是兩個分配，一個用於節點本身，另一個用於它保存的字符串。