I have an algorithm which compares two linked lists, L1 and L2, and the elements that are equal, it puts them in a third list L3 while deleting them from L2. I am not sure though if this is all what the algorithm is supposed to do, and I don't understand some concepts such as "p1prec" for example. I want to know the design of algorithm rationally, the bigger picture. When I try to get the sense of it by examining the instructions one by one I feel like Im trying to memorize it. Also some advices on methods to design alike algorithms would be quite welcome.The algorithm is as follows :
我有一个算法比较两个链接列表,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
2 个解决方案
#1
1
Since I guess your goal is to understand how to do this problem I will just try to explain the basic algorithm to you instead of telling you what each line does.
因为我猜你的目标是了解如何解决这个问题,我将尝试向您解释基本算法,而不是告诉您每行的作用。
You have 2 lists: L1 and L2.
您有2个列表:L1和L2。
You basically wanna check each element from L1 with each element from L2. Let L1current and L2current be the values you are checking.
你基本上想要检查L1中的每个元素与L2中的每个元素。让L1current和L2current成为您正在检查的值。
You also need a L2Prec because when you delete a L2 element you need to link the prec with the next.
您还需要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.
}
#2
1
A couple of things:
有几件事:
1) it seems it's removing stuff from both L1 and L2 but that's a minor detail
1)它似乎正在从L1和L2中删除东西,但这是一个小细节
2) how much do you know about algorithms and data structures? Do you know how a linked list works? How to implement one? What types are there and what are the differences between them?
2)您对算法和数据结构了解多少?你知道链表是如何工作的吗?如何实施一个?有什么类型,它们之间有什么区别?
I'm asking this because with basic understanding of a singly linked list it is pretty obvious what p1(2)prec is, what next[p1(2)prec] is and how deleting from a singly linked list works.
我问这个是因为基本理解了单链表,很明显p1(2)prec是什么,下一个[p1(2)prec]是什么以及如何从单链表中删除有效。
Maybe reading about lists first should be the way to go?
也许首先阅读列表应该是要走的路?
3) basically as you said this algorithm iterates over both lists and if it find a common element it deletes it from both of the lists and puts it in a resulting list (the elements can be at the sam positions in the list but don't have to - if that's what you want, that's a different question :-).
3)基本上你说这个算法迭代两个列表,如果它找到一个公共元素,它会从两个列表中删除它并将它放在结果列表中(元素可以在列表中的sam位置但不是必须 - 如果这是你想要的,这是一个不同的问题:-)。
A singly (this is important here) linked list looks more or less like this:
单独(这在这里很重要)链表看起来或多或少像这样:
prec p1 next[p1]
el1 -> el2 -> el3 -> nil
You can go only from left to right. Now let's delete "el2". But wait we are at "el2", then how do we change the pointers so "el1" points to "el3" now?
你只能从左到右去。现在让我们删除“el2”。但是等我们在“el2”,然后我们如何更改指针,以便“el1”现在指向“el3”?
Well that's what "prec" is for in this algorithm. In a SLL you will change to where the previous pointer will point and that's it! You deleted your element:
那就是这个算法中“prec”的含义。在SLL中,您将更改为前一个指针指向的位置,就是这样!你删除了你的元素:
el1 -> el3 -> nil
el1 - > el3 - >无
Why is this so? Remember when I said you can go here only from left to right? Well you changed the pointer from next[el1] to el3 so the next element to the right it el3 and there's no way to visit el2 even if we wouldn't do free on it.
为什么会这样?还记得当我说你只能从左到右去这里吗?那么你把指针从下一个[el1]更改为el3,所以右边的下一个元素就是el3,即使我们不对它进行*,也无法访问el2。
Here free(p2) also deallocates the memory used by the element from the second list. Notice that it only does that for p2 because p1 was inserted into L3 so we still need it.
这里free(p2)还从第二个列表中释放元素使用的内存。请注意,它只对p2执行此操作,因为p1已插入L3,因此我们仍然需要它。
Depending on the language/implementation this line:
取决于此行的语言/实现:
next[p1prec]
Might be problematic. What if the first elements are equal? Then p1prec and p2prec are still nil yet you are trying to do some operation on them. But as I said that's an implementation detail.
可能有问题。如果第一个元素相等怎么办?那么p1prec和p2prec仍然是零但你正试图对它们进行一些操作。但正如我所说,这是一个实施细节。
4) This has O(n^2) complexity (if I didn't miss anything) because for each element in L1 you do (in the worst case) a full traversal of L2 (notice that after while p1 =/= nil p2 points again at the head element).
4)这有O(n ^ 2)的复杂度(如果我没有错过任何东西),因为对于L1中的每个元素,你做(在最坏的情况下)完全遍历L2(注意在p1 = / = nil p2之后)再次指向头部元素)。
That's basically it...
那基本上就是......
#1
1
Since I guess your goal is to understand how to do this problem I will just try to explain the basic algorithm to you instead of telling you what each line does.
因为我猜你的目标是了解如何解决这个问题,我将尝试向您解释基本算法,而不是告诉您每行的作用。
You have 2 lists: L1 and L2.
您有2个列表:L1和L2。
You basically wanna check each element from L1 with each element from L2. Let L1current and L2current be the values you are checking.
你基本上想要检查L1中的每个元素与L2中的每个元素。让L1current和L2current成为您正在检查的值。
You also need a L2Prec because when you delete a L2 element you need to link the prec with the next.
您还需要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.
}
#2
1
A couple of things:
有几件事:
1) it seems it's removing stuff from both L1 and L2 but that's a minor detail
1)它似乎正在从L1和L2中删除东西,但这是一个小细节
2) how much do you know about algorithms and data structures? Do you know how a linked list works? How to implement one? What types are there and what are the differences between them?
2)您对算法和数据结构了解多少?你知道链表是如何工作的吗?如何实施一个?有什么类型,它们之间有什么区别?
I'm asking this because with basic understanding of a singly linked list it is pretty obvious what p1(2)prec is, what next[p1(2)prec] is and how deleting from a singly linked list works.
我问这个是因为基本理解了单链表,很明显p1(2)prec是什么,下一个[p1(2)prec]是什么以及如何从单链表中删除有效。
Maybe reading about lists first should be the way to go?
也许首先阅读列表应该是要走的路?
3) basically as you said this algorithm iterates over both lists and if it find a common element it deletes it from both of the lists and puts it in a resulting list (the elements can be at the sam positions in the list but don't have to - if that's what you want, that's a different question :-).
3)基本上你说这个算法迭代两个列表,如果它找到一个公共元素,它会从两个列表中删除它并将它放在结果列表中(元素可以在列表中的sam位置但不是必须 - 如果这是你想要的,这是一个不同的问题:-)。
A singly (this is important here) linked list looks more or less like this:
单独(这在这里很重要)链表看起来或多或少像这样:
prec p1 next[p1]
el1 -> el2 -> el3 -> nil
You can go only from left to right. Now let's delete "el2". But wait we are at "el2", then how do we change the pointers so "el1" points to "el3" now?
你只能从左到右去。现在让我们删除“el2”。但是等我们在“el2”,然后我们如何更改指针,以便“el1”现在指向“el3”?
Well that's what "prec" is for in this algorithm. In a SLL you will change to where the previous pointer will point and that's it! You deleted your element:
那就是这个算法中“prec”的含义。在SLL中,您将更改为前一个指针指向的位置,就是这样!你删除了你的元素:
el1 -> el3 -> nil
el1 - > el3 - >无
Why is this so? Remember when I said you can go here only from left to right? Well you changed the pointer from next[el1] to el3 so the next element to the right it el3 and there's no way to visit el2 even if we wouldn't do free on it.
为什么会这样?还记得当我说你只能从左到右去这里吗?那么你把指针从下一个[el1]更改为el3,所以右边的下一个元素就是el3,即使我们不对它进行*,也无法访问el2。
Here free(p2) also deallocates the memory used by the element from the second list. Notice that it only does that for p2 because p1 was inserted into L3 so we still need it.
这里free(p2)还从第二个列表中释放元素使用的内存。请注意,它只对p2执行此操作,因为p1已插入L3,因此我们仍然需要它。
Depending on the language/implementation this line:
取决于此行的语言/实现:
next[p1prec]
Might be problematic. What if the first elements are equal? Then p1prec and p2prec are still nil yet you are trying to do some operation on them. But as I said that's an implementation detail.
可能有问题。如果第一个元素相等怎么办?那么p1prec和p2prec仍然是零但你正试图对它们进行一些操作。但正如我所说,这是一个实施细节。
4) This has O(n^2) complexity (if I didn't miss anything) because for each element in L1 you do (in the worst case) a full traversal of L2 (notice that after while p1 =/= nil p2 points again at the head element).
4)这有O(n ^ 2)的复杂度(如果我没有错过任何东西),因为对于L1中的每个元素,你做(在最坏的情况下)完全遍历L2(注意在p1 = / = nil p2之后)再次指向头部元素)。
That's basically it...
那基本上就是......