暂存作业

unknown · unknown · commit f6c77f439ae1 · 2017-02-25T23:15:21.000+08:00
diff --git a/group11/252308879/dataStructure/src/main/java/org/apn/coding2017/basic/LinkedList.java b/group11/252308879/dataStructure/src/main/java/org/apn/coding2017/basic/LinkedList.java
@@ -3,68 +3,119 @@
 /**
  * Created by QiPan on 2017/2/23.
  */
-public class LinkedList implements List {
+public class LinkedList {
 
-    Node last;
+    private Node head;
+    private int size;
+    public LinkedList() {
+        head = new Node(null, null);
+        size = 0;
+    }
 
+    public void add(Object o){
+        add(size, o);
+    }
 
-    public boolean add(Object o) {
+    public void add(int index , Object o){
+        if (index > size || index < 0) {
+            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
+        }
+        Node frontNode = getNode(index-1);
+        Node newNode = new Node(o, frontNode.next);
+        frontNode.next = newNode;
+        size++;
 
-        return true;
     }
 
-    public Object set(int index, Object element) {
-        return null;
+    private Node getNode(int index) {
+        Node node = head;
+        int i = 0;
+        while(node.next != null && i <= index) {
+            node = node.next;
+            i++;
+        }
+        return node;
     }
 
-    public boolean add(int index, Object o) {
+    public Object get(int index){
+        if (index >= size || index < 0) {
+            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
+        }
+
+        Node node = getNode(index);
+        return node.data;
+    }
 
-        return true;
+    public Object remove(int index){
+        if (index >= size || index < 0) {
+            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
+        }
+        Node frontNode = getNode(index-1);
+        Node oldNode = getNode(index);
+        frontNode.next = oldNode.next;
+        size--;
+        return oldNode.data;
     }
 
-    public Object get(int index) {
-        return null;
+    public int size(){
+        return size;
     }
 
-    public Object remove(int index) {
-        return null;
+    public void addFirst(Object o){
+        add(0, o);
     }
 
-    public int size() {
-        return 0;
+    public void addLast(Object o){
+        add(size, o);
     }
 
-    public boolean isEmpty() {
-        return false;
+    public Object removeFirst(){
+        return remove(0);
     }
 
-    public Iterator iterator() {
-        return null;
+    public Object removeLast(){
+        return remove(size-1);
     }
-    
-    private static class Node {
-        Object item;
-        Node next;
 
-        Node(Object item, Node next) {
-            this.item = item;
-            this.next = next;
+    public Iterator iterator(){
+        return new LinkedListIterator();
+    }
+
+    private class LinkedListIterator implements Iterator {
+        int index;
+        final int capacity = size;
+        LinkedListIterator() {
+            index = 0;
         }
-        public Object getItem() {
-            return item;
+        @Override
+        public boolean hasNext() {
+            return index < capacity;
         }
 
-        public void setItem(Object item) {
-            this.item = item;
+        @Override
+        public Object next() {
+            return get(index++);
         }
 
-        public Node getNext() {
-            return next;
+        @Override
+        public void remove() {
+
         }
+    }
 
-        public void setNext(Node next) {
+    private String outOfBoundsMsg(int index) {
+        return "index:" + index + ", size:" + size;
+    }
+
+    private static  class Node {
+        Object data;
+        Node next;
+
+        Node(Object data, Node next) {
+            this.data = data;
             this.next = next;
         }
     }
 
+
 }
diff --git a/group11/252308879/dataStructure/src/main/java/org/apn/coding2017/basic/Queue.java b/group11/252308879/dataStructure/src/main/java/org/apn/coding2017/basic/Queue.java
@@ -2,21 +2,49 @@
 
 /**
  * Created by QiPan on 2017/2/23.
+ * 队列，链表实现版本
  */
-public class Queue {
+public class Queue<E> {
 
-    public void enQueue(Object o){
+    private Node first;
+    private Node last;
+    private int N;
+
+    private class Node {
+        E item;
+        Node next;
+    }
+
+    public void enQueue(E e) {
+        // 向表尾添加元素
+        Node oldLast = last;
+        last = new Node();
+        last.item = e;
+        last.next = null;
+        if (isEmpty()){// 如果是往空的队列里面添加东西。那么首尾链表都是指向第一个元素
+            first = last;
+        }else {
+
+            oldLast.next = last;
+        }
+        N++;
     }
 
-    public Object deQueue(){
-        return null;
+    public E deQueue() {
+        E item = first.item;
+        first = first.next;
+        if (isEmpty()){
+            last = null;
+        }
+        N--;
+        return item;
     }
 
-    public boolean isEmpty(){
-        return false;
+    public boolean isEmpty() {
+        return first == null;
     }
 
-    public int size(){
-        return -1;
+    public int size() {
+        return N;
     }
 }
diff --git a/group11/252308879/dataStructure/src/main/java/org/apn/coding2017/basic/Stack2.java b/group11/252308879/dataStructure/src/main/java/org/apn/coding2017/basic/Stack2.java
@@ -0,0 +1,47 @@
+package org.apn.coding2017.basic;
+
+/**
+ * Created by Pan on 2017/2/25.
+ * 栈（链表实现）： 下压栈。操作栈顶元素
+ */
+public class Stack2<E> {
+
+    private Node first;
+    private int N;
+
+    private class Node {
+        E item;
+        Node next;
+    }
+
+    public boolean isEmpty(){
+        return first == null;
+    }
+
+    public int size(){
+        return  N;
+    }
+
+    /**
+     * 向栈顶添加元素
+     * @param element
+     */
+    public void push (E element){
+        Node oldFirst = first;
+        first = new Node();
+        first.item = element;
+        first.next = oldFirst;
+        N++;
+    }
+
+    /**
+     * 弹出栈顶元素
+     * @return
+     */
+    public E pop(){
+        E item = first.item;
+        first = first.next;
+        N--;
+        return item;
+    }
+}
