0

正如问题的名称所暗示的那样。我需要获取 2 个链表并仅从前 2 个链表共有的元素中创建第三个列表。

这是我写的函数

void computeC(DLL<int> &a, DLL<int> &b, DLL<int> &c)
{
    Node<int> *hunterA, *hunterB;
    hunterA = a.getHead();
    hunterB = b.getHead();


  while ( hunterA != NULL )
    {
        while ( hunterB != NULL )
        {
            int aData = hunterA->data, bData = hunterB->data;

            if ( aData == bData )
            {
                    int temp = bData;
                c.progAppend2(temp);
            }
            else
            {
                hunterB = hunterB->next;
            }   
        }
        hunterA = hunterA->next;
    }
    c.output();
}

这是我的双向链表类中的 progAppend2() 函数

template <class Type>
void DLL<Type>::progAppend2(Type data)
{
    Node<Type> *newNode = new Node<Type>;
    newNode->data = data;

    if ( head == NULL )
    {
        head = newNode;
        tail = newNode;
        size++;
    }

    else
    {
         tail->next = newNode;
        newNode->prev = tail;
        tail = tail->next;
        size++;
    }
}

这是 main()

int main (void)
{   
    int a[9] = {3,7,10,15,16,9,22,17,32};
    int b[9] = {16,2,9,13,37,8,10,1,28};
    DLL<int> listA, listB, listC, listD;
    for ( int i = 0; i < 9; i++ )
    {
        listA.progAppend2(a[i]);
        listB.progAppend2(b[i]);
    }
    computeC(listA,listB,listC);
    listC.output();

    return 0;
}

我遇到的问题是，由于某种原因，当我调用 output(); 时，ListC 没有填充任何内容，只是输出和空列表；

我认为问题出在 computeC 函数上。外层while循环应该设置hunterA指向ListA中的一个元素，然后内层循环应该将listB的每个元素与hunterA指向的元素进行比较。如果找到匹配项，则将该元素复制到 ListC 中。至少我认为它应该是这样工作的。我真的很感激任何帮助。

4

2 回答 2

1

我认为@AEDrew 为您提供了正确的建议。

我只想补充一点，您的解决方案的时间复杂度为 O(length(A)*length(B))，更好的解决方案是 O(length(A)+length(B))。您可以散列所有 A 列表节点，然后迭代 B 列表以查找是否有任何 B 节点在 A 列表中。

希望这也有帮助:)

于 2013-05-07T06:16:10.307 回答
1

每次检查 A 中的新节点时，都需要再次查看 B 中的所有节点。例如，如果 A 中的第一个节点与 B 中的任何元素都不匹配（就像在您的输入中一样），您的指针将移动到 B 的末尾。因此，在您的 while 循环中通过 A 移动时，将 b 指针重置为b列表的开始。

注意：如果 a 和 b 中的节点匹配，看起来您将进入无限循环，因为您未能在 if-then 语句中移动 b 指针。

于 2013-05-06T22:52:14.837 回答