0

我有一个算法，它比较两个链表 L1 和 L2，以及相等的元素，它将它们放在第三个列表 L3 中，同时从 L2 中删除它们。我不确定这是否是算法应该做的全部，而且我不理解一些概念，例如“p1prec”。我想理性地了解算法的设计，大局观。当我试图通过一一检查说明来理解它时，我觉得我在努力记住它。此外，一些关于设计类似算法的方法的建议也非常受欢迎。算法如下：

    Equal(L1,L2)

    head[L3] = NIL            //L3 is empty
    if head[L2] = NIL         //if there are no elements in L2 return NIL
       return L3
    p1 = head[L1]             //p1 points the head of L1
    p1prec = nil              //p1prec is supposed to be precedent I guess.
    while p1 =/= nil
          p2 = head[L2]       //p2 points head of L2
          p2prec = nil        //p2prec is precedent of p2; first cycle is nil
          while p2 =/= nil and key[p1] =/= key[p2]
                p2prec = p2          // pass p2 and p2prec through L2 until
                p2 = next[p2]        // key[p1] = key[p2]
          if p2 =/= nil        // if two elements are found equal
                next[p1prec] = next[p1]          // im not sure what this does
                insert(L3,p1)                    // insert the element in L3
                p1 = next[p1prec]                //neither this,
                next[p2prec] = next[p2]  //connects the p2prec with nextp2 because p2
                free(p2)                         //is going to be deleted
          p1prec = p1      //moves through L1, if no element of p2 is found          
          p1 = next[p1]                         //equal with first element of p1
4

2 回答 2

1

有几件事：

1) 似乎它正在从 L1 和 L2 中删除东西，但这是一个小细节

2）你对算法和数据结构了解多少？你知道链表是​​如何工作的吗？如何实施？有哪些类型，它们之间有什么区别？

我问这个是因为对单链表有基本的了解，很明显什么p1(2)prec是，什么next[p1(2)prec]是以及如何从单链表中删除。

也许首先阅读列表应该是要走的路？

3）基本上正如你所说，这个算法迭代两个列表，如果它找到一个公共元素，它会从两个列表中删除它并将其放入结果列表中（元素可以位于列表中的 sam 位置，但不要必须 - 如果这是你想要的，那是一个不同的问题:-)。

一个单独的（这在这里很重要）链表看起来或多或少像这样：

prec    p1   next[p1]
el1 -> el2 -> el3 -> nil

你只能从左到右。现在让我们删除“el2”。但是等等我们在“el2”，那么我们如何改变指针，让“el1”现在指向“el3”呢？

好吧，这就是该算法中“prec”的用途。在 SLL 中，您将更改为前一个指针指向的位置，仅此而已！您删除了元素：

el1 -> el3 -> 无

为什么会这样？还记得我说过你只能从左到右去吗？好吧，您将指针从 更改为next[el1]，el3因此右侧的下一个元素为 el3 ，即使我们不对其进行访问，也无法访问 el2 free。

这里free(p2)还释放第二个列表中元素使用的内存。请注意，它只对 p2 执行此操作，因为 p1 已插入 L3，所以我们仍然需要它。

根据此行的语言/实现：

next[p1prec]

可能有问题。如果第一个元素相等怎么办？然后 p1prec 和 p2prec 仍然为零，但您正试图对它们进行一些操作。但正如我所说，这是一个实现细节。

4) 这具有 O(n^2) 复杂性（如果我没有遗漏任何东西），因为对于 L1 中的每个元素，您都（在最坏的情况下）完全遍历 L2（请注意，在while p1 =/= nilp2 之后再次指向头元素）。

基本上就是这样...

于 2013-10-22T16:32:55.210 回答
1

因为我猜你的目标是理解如何解决这个问题，所以我只会尝试向你解释基本算法，而不是告诉你每一行的作用。

您有 2 个列表：L1 和 L2。

您基本上想检查 L1 中的每个元素与 L2 中的每个元素。让 L1current 和 L2current 成为您要检查的值。

您还需要 L2Prec，因为当您删除 L2 元素时，您需要将 prec 与下一个链接。

You start with L1current = L1 and L2current = L2;
While ( L1current is not NULL)
{
    L2current = L2; // you set the L2Current to the begging of L2 list.
    While ( L2current is not NULL) // you run untill the end.
    {
        You check if L1current == L2current;
        {
            // If they are equal
            You add the L2 element to L3;
            You connect L2prec with L2next;
            You delete L2current;
        }
        Else
        {
                L2current = L2next;
        }
    }
       L1current = L1next; // after you are done with the first element of L1 you
                          // move to the next one.
}
于 2013-10-22T16:39:09.133 回答