0

我有一个链接列表的合并实现。它接受两个 List 类型的参数，这是一个包含Node* head指针和Node由 atypename T data和 a组成的结构的类Node* next。我遇到的问题是我的实现没有按应有的方式链接节点，或者我只是做错了。它需要做的是，如果你这样做了，list1.merge(list2, list3);那么list1将成为list2和list3的节点的组合。我需要通过指针操作和没有新的内存分配来做到这一点，所以 list2 和 list3 将被修改。这是我现在所拥有的：

template <typename T>
void List<T>::merge(List& list1, List& list2) {

typename List<T>::Node* list1Ptr = list1.head;
typename List<T>::Node* list2Ptr = list2.head;

for(;;) {
    if (list1Ptr == NULL && list2Ptr != NULL) {
        list1Ptr = list2Ptr->next;
        head = list1.head;
        break;
    }
    else if (list2Ptr == NULL && list1Ptr != NULL) {
        list2Ptr = list1Ptr->next;
        head = list1.head;
        break;
    }
    else if (list1Ptr == NULL && list2Ptr == NULL) {
        head = list1.head;
        break;
    }
    else if (list1Ptr != NULL && list2Ptr != NULL) {

        if (list1Ptr->data > list2Ptr->data){
            typename List<T>::Node* temp;
            temp = list2Ptr->next;
            list1Ptr->next = list1Ptr;
            list2Ptr = temp;
        }
        else if (list1Ptr->data < list2Ptr->data) {
            typename List<T>::Node* temp;
            temp = list1Ptr->next;
            list1Ptr->next = list2Ptr;
            list1Ptr = temp;
        }
        else if (list1Ptr->data == list2Ptr->data) {
            list1Ptr = list1Ptr->next;
        }
    }
}
}

节点中包含的数据是为我们提供的类类型，其中包含我们需要的所有适当的重载运算符。整个代码运行得很好，直到 main 超出范围并且为剩余的内容调用析构函数，之后我得到一个Debug Assertion Failed Expression: _BLOCK_TYPE_IS_VALID(pHead->nBlockUse).

我真的不知道该怎么做，我已经画了很多次，这对我来说似乎很有意义。如果有人有任何提示可以让我朝着正确的方向前进，我将不胜感激。感谢大家观看！

4

2 回答 2

1

这不能按预期工作：

list1Ptr->data > list2Ptr->data && list1Ptr != NULL 
             && list2Ptr != NULL

您需要在取消引用之前检查指针是否为 NULL，否则您将获得未定义的行为。（这意味着任何事情都可能发生，非常糟糕。）此外，您应该使用 nullptr 而不是 NULL。

然而，这不是错误消息的原因，因为您已经检查了其他条件中的所有 NULL 情况。

您的问题可能与 asalic 建议的一样。如果您想发表评论，请向我们展示其余代码。

于 2013-10-27T18:08:39.397 回答
1

那么对于初学者来说这里有问题：

    if (list1Ptr == NULL && list2Ptr != NULL) {
        list1Ptr = list2Ptr;
        head = list1.head;
        break;
    }

如果您完成了对 list1 的遍历，那么您想要将 list1 的最后一个节点指向 list2。 list1Ptr = list2Ptr;
什么也没做。它只是改变局部变量的值。
这部分也一样：

    else if (list2Ptr == NULL && list1Ptr != NULL) {
        list2Ptr = list1Ptr;
        head = list1.head;
        break;
    }

这是一种不好的做法：
list1Ptr->data > list2Ptr->data && list1Ptr != NULL && list2Ptr != NULL
如果 list1Ptr 变为 NULL，那么如果您尝试访问 NULL->data 肯定会遇到麻烦（因为通常表达式将从左到右执行）。
还：

        else if (list1Ptr->data > list2Ptr->data && list1Ptr != NULL 
             && list2Ptr != NULL) {
        typename List<T>::Node* temp = list2Ptr;
        list2Ptr = list2Ptr->next;
        temp->next = list1Ptr;
        }

这里也确实有问题。您首先将 list2ptr 存储在临时文件中。然后将 list2ptr 移动到 list2 中的下一个节点。但为什么要制作temp->next = list1ptr？
你应该重新考虑那部分。下一个 else 块也是如此。
最好的。
编辑：
好吧，让我们看看还能做些什么：
这是我建议您使用的伪代码：

func(list1,list2):
ptr1 = list1.head
ptr2 = list2.head
declare pointer curr
if(ptr1!= NULL and ptr2!=NULL){
    if(ptr1->data < prt2->data)
    {curr = ptr1
    ptr1 = ptr1->next
    head = curr
    }
    else{
    curr = ptr2
    ptr1 = ptr2->next
    head = curr}}
else{
    head = whichever one is not NULL, or NULL if both of them are and return
    }
while(ptr1 != NULL and ptr2!=NULL){
    if(ptr1->data < ptr2->data){
    curr->next = ptr1
    curr = ptr1
    ptr1 = ptr1->next
    continue}
    else{
    curr->next = ptr2
    curr = ptr2
    ptr2 = ptr2->next
    continue}
}
if(ptr1 == NULL)
    curr->next = ptr2
else
    curr->next = ptr1
于 2013-10-27T18:22:16.557 回答