链接列表的两个节点中的合并值

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的两个值添加到缓冲器的缓冲器。

然后释放第一和第二节点指向

的字符串，然后将第一个节点指向这个新节点

，然后设置的第一个节点的指针，以消除第二，做不要忘记释放第二个节点。即每个节点是两个分配，一个用于节点本身，另一个用于它保存的字符串。