0

新程序员在这里，我试图理解并分解下面的代码以获取删除方法，排序链表。我在下面添加了我的理解和不理解的评论。有人可以阐明不清楚的事情吗？

提前致谢。

/* 1  */ public void remove(E e) throws NotFoundException{
/* 2  */     Node<E> p; //declares node p
/* 3  */     // chunk below determines where to start traversing based on element value. should traverse from head if new element < pos value
/* 4  */     if(pos == head || pos.compareTo(e) >= 0 ){ //I do not understand 2nd equality..why?
/* 5  */         p = head; //traverse list from head
/* 6  */     }else{
/* 7  */         //traverse list from pos
/* 8  */         p = pos;
/* 9  */     }
/* 10 */     for( ;p.next!=null && p.next.compareTo(e)<0; p = p.next); //nothing to initialize?
/* 11 */     //e not found in the list
/* 12 */     if(p.next == null || p.next.compareTo(e) > 0){
/* 13 */         throw new NotFoundException();
/* 14 */     }
/* 15 */     if(p.next == pos){
/* 16 */         //if node to be deleted is pos, update pos to head
/* 17 */         pos = head;
/* 18 */     }
/* 19 */     p.next = p.next.next; //delete node
/* 20 */ }
4

2 回答 2

0

第 4 行：它是一个排序列表，因此如果您要删除的元素大于或等于 pos 所指向的元素，则可以从 pos 开始移动（而不是从列表的头部）-（如果您不知道，a.compareTo(b) < 0 如果 a < b，0 如果 a == b 和 > 0 如果 a < b)

第 10 行：当 p.next 低于您要查找的内容（且不为空）时，在列表中移动 - 一旦完成，您要么位于您要查找的节点，要么抛出 NotFoundException()

还有什么不清楚的吗？

于 2012-06-16T22:26:53.557 回答
0 
4. if(pos == head || pos.compareTo(e) >= 0 ){ //I do not understand 2nd equality..why? 
5. p = head; //traverse list from head
6. }else{
7. //traverse list from pos 
8. p = pos;  
9. }

首先，这是compareTo 的文档。第二个相等性检查 pos 是否指向“e”之后的节点。如果它是真的，那么你必须从它的头部遍历列表，因为 e 在 pos 之前。否则，e 在 pos 之后，因此您可以从 pos 遍历列表。这是真的，因为列表是排序的。

10. for( ;p.next!=null && p.next.compareTo(e)<0; p = p.next); //nothing to initialize?
11. //e not found in the list
12. if(p.next == null || p.next.compareTo(e) > 0){
13. throw new NotFoundException();
14. }

在这里，您从选择的位置开始扫描列表，如果您到达一个为空的节点（列表的末尾）或一个大于“e”的节点，那么您知道“e”在列表（因为列表已排序），因此您抛出异常

第 10 行：你不必在这里初始化任何东西，因为你已经在上面初始化了 p。

于 2012-06-16T22:32:18.850 回答