Merge pull request onlyliuxin#8 from XeCtvi/master

gqipan · web-flow · commit 7adcbb6e7589 · 2017-02-26T23:14:04.000+08:00
DataStructure
diff --git a/group11/635189253/dataStructure/.classpath b/group11/635189253/dataStructure/.classpath
@@ -0,0 +1,6 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<classpath>
+	<classpathentry kind="src" path="src"/>
+	<classpathentry kind="con" path="org.eclipse.jdt.launching.JRE_CONTAINER"/>
+	<classpathentry kind="output" path="bin"/>
+</classpath>
diff --git a/group11/635189253/dataStructure/.gitignore b/group11/635189253/dataStructure/.gitignore
@@ -0,0 +1 @@
+/bin/
diff --git a/group11/635189253/dataStructure/.project b/group11/635189253/dataStructure/.project
@@ -0,0 +1,17 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<projectDescription>
+	<name>dataStructure</name>
+	<comment></comment>
+	<projects>
+	</projects>
+	<buildSpec>
+		<buildCommand>
+			<name>org.eclipse.jdt.core.javabuilder</name>
+			<arguments>
+			</arguments>
+		</buildCommand>
+	</buildSpec>
+	<natures>
+		<nature>org.eclipse.jdt.core.javanature</nature>
+	</natures>
+</projectDescription>
diff --git a/group11/635189253/dataStructure/src/com/coding/basic/ArrayList.java b/group11/635189253/dataStructure/src/com/coding/basic/ArrayList.java
@@ -0,0 +1,74 @@
+package com.coding.basic;
+
+public class ArrayList implements List {
+	
+	private int size = 0;
+	
+	private Object[] elementData = new Object[100];
+	
+	public boolean add(Object o){
+		add(size(), o);
+		size++;
+		return true;
+	}
+	public boolean add(int index, Object o){
+		if (index >= 0 && index < elementData.length) {
+			for (int i = size(); i > index; i--) {
+				elementData[i] = elementData[i-1];
+			}
+			elementData[index] = o;
+		}
+		size++;
+		return true;
+	}
+	
+	public Object get(int index){
+		if (index >= 0 && index < size()) {
+			return elementData[index];
+		}
+//		return null;
+		throw  new ArrayIndexOutOfBoundsException();
+	}
+	
+	public Object remove(int index){
+		Object removedItem = elementData[index];
+		if (index > size()) {
+			throw  new ArrayIndexOutOfBoundsException();
+		}
+		for (int i = index; i < size() - 1; i++) {
+			elementData[i] = elementData[i+1];
+		}
+		size--;
+		return removedItem;
+	}
+	
+	public int size(){
+		return size;
+	}
+	
+	public Iterator iterator(){
+		return new ArrayListIterator();
+	}
+
+	private class ArrayListIterator implements Iterator {
+
+		private int current = 0;
+
+		public boolean hasNext() {
+			return current < size();
+		}
+		
+		public Object next() {
+/*			if (elementData[current+1] != null) {
+				return elementData[current+1];
+			} else {
+				return null;
+			}*/
+			if (!hasNext()) {
+				throw new java.util.NoSuchElementException();
+			}
+			return elementData[current++];
+		}
+	}
+	
+}
diff --git a/group11/635189253/dataStructure/src/com/coding/basic/BinaryTreeNode.java b/group11/635189253/dataStructure/src/com/coding/basic/BinaryTreeNode.java
@@ -0,0 +1,32 @@
+package com.coding.basic;
+
+public class BinaryTreeNode {
+	
+	private Object data;
+	private BinaryTreeNode left;
+	private BinaryTreeNode right;
+	
+	public Object getData() {
+		return data;
+	}
+	public void setData(Object data) {
+		this.data = data;
+	}
+	public BinaryTreeNode getLeft() {
+		return left;
+	}
+	public void setLeft(BinaryTreeNode left) {
+		this.left = left;
+	}
+	public BinaryTreeNode getRight() {
+		return right;
+	}
+	public void setRight(BinaryTreeNode right) {
+		this.right = right;
+	}
+	
+	public BinaryTreeNode insert(Object o){
+		return  null;
+	}
+	
+}
diff --git a/group11/635189253/dataStructure/src/com/coding/basic/Iterator.java b/group11/635189253/dataStructure/src/com/coding/basic/Iterator.java
@@ -0,0 +1,6 @@
+package com.coding.basic;
+
+public interface Iterator {
+	public boolean hasNext();
+	public Object next();
+}
diff --git a/group11/635189253/dataStructure/src/com/coding/basic/LinkedList.java b/group11/635189253/dataStructure/src/com/coding/basic/LinkedList.java
@@ -0,0 +1,191 @@
+package com.coding.basic;
+
+public class LinkedList implements List {
+	
+	private int size;
+	private int modCount = 0;
+	private Node beginMarker;
+	private Node endMarker;
+	
+	private static class Node{
+		public Node( Object d, Node p, Node n) {
+			data = d;
+			prev = p;
+			next = n;
+		}
+		public Object data;
+		public Node prev;
+		public Node next;
+	}
+	
+	public LinkedList () {
+		doClear();
+	}
+	
+	public void clear() {
+		doClear();
+	}
+	
+	private void doClear() {
+		beginMarker = new Node(null, null, null);
+		endMarker = new Node(null, beginMarker, null);
+		beginMarker.next = endMarker;
+		
+		size = 0;
+		modCount++;
+	}
+	
+	public boolean add(Object o){
+		add(size(), o);
+		return true;
+	}
+	public boolean add(int index , Object o){
+		/*if (index < 0 && index > size()) {
+			throw new IndexOutOfBoundsException();
+		}*/
+		addBefore( getNode( index, 0, size()), o);
+		return true;
+	}
+	
+	public void addFirst(Object o){
+		add(0, o);
+	}
+	
+	public void addLast(Object o){
+		add(size(), o);
+	}
+	
+	public Object removeFirst(){
+		return remove(0);
+	}
+	
+	public Object removeLast(){
+		return remove(size());
+	}
+	
+	public Object get(int index){
+		return getNode(index).data;
+	}
+	public Object remove(int index){
+		return remove(getNode(index));
+	}
+	
+	public int size(){
+		return size;
+	}
+	
+	public boolean isEmpty() {
+		return size() == 0;
+	}
+	
+	private void addBefore( Node p, Object o ) {
+		Node newNode = new Node(o, p.prev, p );
+		newNode.prev.next = newNode;
+		p.prev = newNode;
+//		p.prev = p.prev.next = new Node(o, p.prev, p);
+		size++;
+		modCount++;
+	}
+	
+	private Node getNode(int idx) {
+		return getNode(idx, 0, size() - 1);
+	}
+	
+	private Node getNode(int idx, int lower, int upper) {
+		Node p;
+		if (idx < lower || idx > upper) {
+			throw new IndexOutOfBoundsException();
+		}
+		
+		if (idx < size() / 2) {
+			p = beginMarker.next;
+			for (int i = 0; i < idx; i++) {
+				p = p.next;
+			}
+		} else {
+			p = endMarker.prev;
+			for (int i = size(); i > idx; i--) {
+				p = p.prev;
+			}
+		}
+		return p;
+	}
+	
+	private Object remove( Node p ) {
+		p.prev.next = p.next;
+		p.next.prev = p.prev;
+		modCount++;
+		size--;
+		
+		return p.data;
+	}
+	
+	
+	public java.util.Iterator iterator() {
+		return new LinkListIterator();
+	}
+	
+	private class LinkListIterator implements java.util.Iterator {
+		
+		private Node current = beginMarker.next;
+		private int expectedModCount = modCount;
+		private boolean okToRemove = false;
+
+		@Override
+		public boolean hasNext() {
+			return current != endMarker;
+		}
+
+		@Override
+		public Object next() {
+			if ( modCount != expectedModCount ) {
+				throw new java.util.ConcurrentModificationException();
+			}
+			if (!hasNext()) {
+				throw new java.util.NoSuchElementException();
+			}
+			Object nextItem = current.next;
+			current = current.next;
+			okToRemove = true;
+			return nextItem;
+		}
+		
+		public void remove() {
+			if ( modCount != expectedModCount ) {
+				throw new java.util.ConcurrentModificationException();
+			}
+			if ( !okToRemove ) {
+				throw new IllegalStateException();
+			}
+			LinkedList.this.remove(current.prev);
+			expectedModCount++;
+			okToRemove = false;
+			
+		}
+	}
+}
+
+class TestLinkLedList {
+	
+	public static void main(String[] args) {
+		LinkedList lst = new LinkedList();
+		for (int i = 0; i < 10; i++) {
+			lst.add(i);
+		}
+		for (int i = 20; i < 30; i++) {
+			lst.add(0, i);
+		}
+		
+		lst.remove(0);
+		lst.remove(lst.size()-1);
+		
+		System.out.println(lst);
+		
+		java.util.Iterator itr = lst.iterator();
+		while (itr.hasNext()) {
+			itr.next();
+			itr.remove();
+			System.out.println(lst);
+		}
+	}
+}
diff --git a/group11/635189253/dataStructure/src/com/coding/basic/List.java b/group11/635189253/dataStructure/src/com/coding/basic/List.java
@@ -0,0 +1,9 @@
+package com.coding.basic;
+
+public interface List {
+	public boolean add(Object o);
+	public boolean add(int index, Object o);
+	public Object get(int index);
+	public Object remove(int index);
+	public int size();
+}
diff --git a/group11/635189253/dataStructure/src/com/coding/basic/Queue.java b/group11/635189253/dataStructure/src/com/coding/basic/Queue.java
@@ -0,0 +1,22 @@
+package com.coding.basic;
+
+public class Queue {
+	
+	private LinkedList elementData;
+	
+	public void enQueue(Object o){
+		elementData.add(o);
+	}
+	
+	public Object deQueue(){
+		return null;
+	}
+	
+	public boolean isEmpty(){
+		return false;
+	}
+	
+	public int size(){
+		return -1;
+	}
+}
diff --git a/group11/635189253/dataStructure/src/com/coding/basic/Stack.java b/group11/635189253/dataStructure/src/com/coding/basic/Stack.java
@@ -0,0 +1,22 @@
+package com.coding.basic;
+
+public class Stack {
+	private ArrayList elementData = new ArrayList();
+	
+	public void push(Object o){		
+	}
+	
+	public Object pop(){
+		return null;
+	}
+	
+	public Object peek(){
+		return null;
+	}
+	public boolean isEmpty(){
+		return false;
+	}
+	public int size(){
+		return -1;
+	}
+}
