一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 318|回复: 1
收起左侧

[算法题] 双链表遍历问题

[复制链接] |试试Instant~ |关注本帖
大成若缺 发表于 2015-7-13 11:16:30 | 显示全部楼层 |阅读模式
35小米
普林斯顿算法week2的deque实现 check iterator() 这个test搞了我一整天 没解决 想问问大家问题出在哪里?
题目是这样的:
Dequeue. A double-ended queue or deque (pronounced "deck") is a generalization of a stack and a queue that supports adding and removing items from either the front or the back of the data structure. Create a generic data type Deque that implements the following API:
public class Deque<Item> implements Iterable<Item> {   public Deque()                           // construct an empty deque   public boolean isEmpty()                 // is the deque empty?   public int size()                        // return the number of items on the deque   public void addFirst(Item item)          // add the item to the front   public void addLast(Item item)           // add the item to the end   public Item removeFirst()                // remove and return the item from the front   public Item removeLast()                 // remove and return the item from the end   public Iterator<Item> iterator()         // return an iterator over items in order from front to end   public static void main(String[] args)   // unit testing}我打算用双链表做,coursera上其他函数检测都正常,唯独Iterator函数通不过 我的代码是这样的:
  1. import java.util.Iterator;

  2. public class Deque<Item> implements Iterable<Item> {
  3.        
  4.         public Deque() {
  5.                
  6.                 first = null;
  7.                 last = null;
  8.         }
  9.        
  10.         public boolean isEmpty() {
  11.                
  12.                 return (first == null);
  13.         }
  14.        
  15.         public int size() {
  16.                
  17.                 if (this.isEmpty()) {
  18.                        
  19.                         return 0;
  20.                 }
  21.                
  22.                 Node current = first;
  23.                 int i = 1;
  24.                
  25.                 while (true) {
  26.                        
  27.                         if (current == last) {
  28.                                
  29.                                 return i;
  30.                         }
  31.                        
  32.                         current = current.next;
  33.                         i++;
  34.                 }
  35.         }
  36.        
  37.         public void addFirst(Item item) {
  38.                
  39.                 if (item == null) {
  40.                        
  41.                         throw new java.lang.NullPointerException();
  42.                 }
  43.                
  44.                 Node toAdd = new Node();
  45.                 toAdd.item = item;
  46.                
  47.                 if (this.isEmpty()) {
  48.                        
  49.                         toAdd.next = null;
  50.                         toAdd.previous = null;
  51.                         first = toAdd;
  52.                         last = toAdd;
  53.                 }
  54.                
  55.                 Node oldFirst = first;
  56.                 oldFirst.previous = toAdd;
  57.                 toAdd.next = oldFirst;
  58.                 toAdd.previous = null;
  59.                 first = toAdd;
  60.         }
  61.        
  62.         public void addLast(Item item) {
  63.                
  64.                 if (item == null) {
  65.                        
  66.                         throw new java.lang.NullPointerException();
  67.                 }
  68.                
  69.                 Node toAdd = new Node();
  70.                 toAdd.item = item;
  71.                
  72.                 if (this.isEmpty()) {
  73.                        
  74.                         toAdd.next = null;
  75.                         toAdd.previous = null;
  76.                         first = toAdd;
  77.                         last = toAdd;
  78.                 }
  79.                
  80.                 Node oldLast = last;
  81.                 oldLast.next = toAdd;
  82.                 toAdd.next = null;
  83.                 toAdd.previous = oldLast;
  84.                 last = toAdd;
  85.         }
  86.        
  87.         public Item removeFirst() {
  88.                
  89.                 Item item;
  90.                
  91.                 if (this.isEmpty()) {
  92.                        
  93.                         throw new java.util.NoSuchElementException();
  94.                 }
  95.                
  96.                 else {
  97.                
  98.                         if (first.equals(last)) {
  99.                                
  100.                                 item = first.item;
  101.                                
  102.                                 first = null;
  103.                                 last = null;
  104.                         }
  105.                        
  106.                         else {
  107.                        
  108.                                 Node oldFirst = first;
  109.                                
  110.                                 item = oldFirst.item;
  111.                                 first = oldFirst.next;
  112.                                 first.previous = null;
  113.                                 oldFirst = null;
  114.                         }
  115.                        
  116.                         return item;
  117.                 }
  118.         }
  119.        
  120.         public Item removeLast() {
  121.                
  122.                 Item item;
  123.                
  124.                 if (this.isEmpty()) {
  125.                        
  126.                         throw new java.util.NoSuchElementException();
  127.                 }
  128.                
  129.                 else {

  130.                         if (first.equals(last)) {
  131.                                
  132.                                 item = last.item;
  133.                                
  134.                                 first = null;
  135.                                 last = null;
  136.                         }
  137.                        
  138.                         else {
  139.                                
  140.                                 Node oldLast = last;
  141.                                 item = oldLast.item;
  142.                                 last = oldLast.previous;
  143.                                 last.next = null;
  144.                                 oldLast = null;
  145.                         }
  146.                        
  147.                         return item;
  148.                 }
  149.         }
  150.        
  151.         @Override
  152.         public Iterator<Item> iterator() {
  153.                
  154.                 return new ListIterator();
  155.         }
  156.        
  157.         public static void main(String[] args) {
  158.                
  159.                 Deque<String> deq = new Deque<String>();
  160.                 deq.addFirst("world!");
  161.                 deq.addFirst("Hello");
  162.                 deq.iterator();
  163.                 deq.removeFirst();
  164.                 deq.iterator();
  165.         }
  166.        
  167.         private Node first;
  168.         private Node last;
  169.        
  170.         private class Node {
  171.                
  172.                 Item item;
  173.                 Node next;
  174.                 Node previous;
  175.         }
  176.        
  177.         private class ListIterator implements Iterator<Item> {
  178.                
  179.                 private Node ptr;
  180.                 private Item i;
  181.                
  182.                 public ListIterator() {
  183.                        
  184.                         ptr = first;
  185.                 }
  186.                
  187.                 @Override
  188.                 public boolean hasNext() {
  189.                        
  190.                         return (ptr != null);
  191.                 }
  192.                
  193.                 @Override
  194.                 public Item next() {
  195.                        
  196.                         if (!this.hasNext()) {
  197.                                
  198.                                 throw new java.util.NoSuchElementException();
  199.                         }
  200.                         else {
  201.                        
  202.                                 i = ptr.item;
  203.                                 ptr = ptr.next;
  204.                                
  205.                                 return i;
  206.                         }
  207.                 }
  208.                
  209.                 public void remove() {
  210.                        
  211.                         throw new java.lang.UnsupportedOperationException();
  212.                 }
  213.         }
  214. }
复制代码
我觉得问题是出在Iterator几个重写的函数上了。但是我看了一个通过的代码,和我的几乎是一模一样的。我百思不得其解,有会的同学请给我一些指教。

 楼主| 大成若缺 发表于 2015-7-13 20:43:09 | 显示全部楼层
已经解决了 addFirst addLast函数少了else谢谢太阳神同志
回复

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-8 16:16

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表