Merge pull request onlyliuxin#19 from xiongyilun/master

Greastate · web-flow · commit bca76d79ae2a · 2017-02-25T23:18:44.000+08:00
2-26作业
diff --git a/group08/529757467/.classpath b/group08/529757467/.classpath
diff --git a/group08/529757467/.gitignore b/group08/529757467/.gitignore
diff --git a/group08/529757467/.project b/group08/529757467/.project
diff --git a/group08/529757467/2017-02-26作业/com/coding/basic/ArrayList.java b/group08/529757467/2017-02-26作业/com/coding/basic/ArrayList.java
@@ -0,0 +1,92 @@
+package com.coding.basic;
+
+public class ArrayList implements List {
+	// size不仅是ArrayList中实际存值得体现，直接add时，也是在elementData[size]处进行
+	private int size = 0;
+	// 数组是连续且有序的
+	private Object[] elementData;
+
+	private void resize(int newSize) {
+		Object[] newArray = new Object[newSize];
+		System.arraycopy(elementData, 0, newArray, 0, size);
+		elementData = newArray;
+	}
+
+	public ArrayList() {
+		elementData = new Object[10];
+	}
+
+	// 添加指定元素至列表尾
+	public void add(Object o) {
+		if (size == elementData.length) {
+			resize(size * 2);
+		}
+		elementData[size++] = o;
+	}
+
+	// 将指定元素插入列表中的指定位置。移动当前位置的元素（如果有的话）和右边的后续元素（向索引添加一个元素）
+	public void add(int index, Object o) {
+		rangeCheck(index);
+		if (size == elementData.length / 4) {
+			resize(elementData.length / 2);
+		}
+		System.arraycopy(elementData, index, elementData, index + 1, size - index);
+		elementData[index] = o;
+		size++;
+	}
+	
+	/*
+	 * 获取指定位置元素
+	 * (non-Javadoc)
+	 * @see com.coding.basic.List#get(int)
+	 */
+	public Object get(int index) {
+		rangeCheck(index);
+		return elementData[index];
+	}
+	
+	/*
+	 * 删除指定位置元素
+	 * (non-Javadoc)
+	 * @see com.coding.basic.List#remove(int)
+	 */
+	public Object remove(int index) {
+		rangeCheck(index);
+		Object oldValue = elementData[index];
+		System.arraycopy(elementData, index + 1, elementData, index, size - index - 1);
+		size--;
+		return oldValue;
+	}
+
+	public int size() {
+		return this.size;
+	}
+
+	public Iterator iterator() {
+		return new ArrayListIterator();
+	}
+
+	// 检测索引值，当前有size个元素，占了elementData[0]至elementData[size-1],add时，只能在已有[0,size-1]处插入，或者在列表尾size处add
+	// 所以index在[0,size之间]
+	private void rangeCheck(int index) {
+		if (index < 0 || index > size) {
+			throw new IndexOutOfBoundsException();
+		}
+	}
+
+	class ArrayListIterator implements Iterator {
+		int i = 0;
+
+		@Override
+		public boolean hasNext() {
+			return i < size;
+		}
+
+		@Override
+		public Object next() {
+			return elementData[i++];
+		}
+
+	}
+
+}
diff --git a/group08/529757467/2017-02-26作业/com/coding/basic/BinaryTreeNode.java b/group08/529757467/2017-02-26作业/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/group08/529757467/2017-02-26作业/com/coding/basic/Iterator.java b/group08/529757467/2017-02-26作业/com/coding/basic/Iterator.java
@@ -0,0 +1,7 @@
+package com.coding.basic;
+
+public interface Iterator {
+	public boolean hasNext();
+	public Object next();
+
+}
diff --git a/group08/529757467/2017-02-26作业/com/coding/basic/LinkedList.java b/group08/529757467/2017-02-26作业/com/coding/basic/LinkedList.java
@@ -0,0 +1,143 @@
+package com.coding.basic;
+
+public class LinkedList implements List {
+
+	private int size = 0;
+	// 头结点
+	private Node head;
+	// 尾结点
+	private Node tail;
+
+	private void rangeCheck(int index) {
+		if (index < 0 || index > size) {
+			throw new IndexOutOfBoundsException();
+		}
+	}
+
+	public void add(Object o) {
+		Node node = new Node(o, null);
+		if (head == null) {
+			head = tail = node;
+		}
+		Node oldTail = tail;
+		tail = node;
+		oldTail.next = tail;
+		size++;
+	}
+
+	public void add(int index, Object o) {
+		rangeCheck(index);
+		if (index == size) {
+			this.add(o);
+		} else {
+			// 保存index处节点
+			Node x = head;
+			// 保存index-1处的节点
+			Node y = null;
+			for (int i = 0; i < index; i++) {
+				y = x;
+				x = x.next;
+			}
+			Node node = new Node(o, x);
+			y.next = node;
+			size++;
+		}
+	}
+
+	public Object get(int index) {
+		rangeCheck(index);
+		Node x = head;
+		for (int i = 0; i < index; i++) {
+			x = x.next;
+		}
+		return x.data;
+	}
+
+	public Object remove(int index) {
+		rangeCheck(index);
+		Object removeData;
+		if (index == 0) {
+			removeData = removeFirst();
+		} else if (index == size - 1) {
+			removeData = removeLast();
+		} else {
+			Node x = head;
+			Node y = head;
+			for (int i = 0; i < index; i++) {
+				y = x;
+				x = x.next;
+			}
+			y.next = x.next;
+			size--;
+			removeData = x.data;
+		}
+		return removeData;
+	}
+
+	public int size() {
+		return this.size;
+	}
+
+	public void addFirst(Object o) {
+		Node oldHead = head;
+		head = new Node(o, oldHead);
+		size++;
+	}
+
+	public void addLast(Object o) {
+		Node oldTail = tail;
+		tail = new Node(o, null);
+		oldTail.next = tail;
+		size++;
+	}
+
+	public Object removeFirst() {
+		Node oldHead = head;
+		head = oldHead.next;
+		size--;
+		return oldHead.data;
+	}
+
+	public Object removeLast() {
+		Node oldTail = tail;
+		Node temp = head;
+		for (int i = 0; i < size - 2; i++) {
+			temp = temp.next;
+		}
+		tail = temp;
+		size--;
+		return oldTail.data;
+	}
+
+	public Iterator iterator() {
+		return new LinkedListIterator();
+	}
+
+	private static class Node {
+		Object data;
+		Node next;
+
+		Node(Object data, Node next) {
+			this.data = data;
+			this.next = next;
+		}
+
+	}
+
+	private class LinkedListIterator implements Iterator {
+		Node x = head;
+
+		@Override
+		public boolean hasNext() {
+			return x != null;
+		}
+
+		@Override
+		public Object next() {
+			Object data = x.data;
+			x = x.next;
+			return data;
+		}
+
+	}
+}
diff --git a/group08/529757467/2017-02-26作业/com/coding/basic/List.java b/group08/529757467/2017-02-26作业/com/coding/basic/List.java
@@ -0,0 +1,9 @@
+package com.coding.basic;
+
+public interface List {
+	public void add(Object o);
+	public void add(int index, Object o);
+	public Object get(int index);
+	public Object remove(int index);
+	public int size();
+}
diff --git a/group08/529757467/2017-02-26作业/com/coding/basic/Queue.java b/group08/529757467/2017-02-26作业/com/coding/basic/Queue.java
@@ -0,0 +1,25 @@
+package com.coding.basic;
+
+public class Queue {
+	private LinkedList linkedList;
+
+	public Queue() {
+		linkedList = new LinkedList();
+	}
+
+	public void enQueue(Object o) {
+		linkedList.add(o);
+	}
+
+	public Object deQueue() {
+		return linkedList.removeFirst();
+	}
+
+	public boolean isEmpty() {
+		return linkedList.size() == 0;
+	}
+
+	public int size() {
+		return linkedList.size();
+	}
+}
diff --git a/group08/529757467/2017-02-26作业/com/coding/basic/Stack.java b/group08/529757467/2017-02-26作业/com/coding/basic/Stack.java
@@ -0,0 +1,30 @@
+package com.coding.basic;
+
+public class Stack {
+
+	private LinkedList linkedList;
+
+	public Stack() {
+		linkedList = new LinkedList();
+	}
+
+	public void push(Object o) {
+		linkedList.add(o);
+	}
+
+	public Object pop() {
+		return linkedList.removeLast();
+	}
+
+	public Object peek() {
+		return linkedList.get(linkedList.size()-1);
+	}
+
+	public boolean isEmpty() {
+		return linkedList.size() == 0;
+	}
+
+	public int size() {
+		return linkedList.size();
+	}
+}
diff --git a/group08/529757467/2017-02-26作业/com/coding/basic/Test.java b/group08/529757467/2017-02-26作业/com/coding/basic/Test.java
@@ -0,0 +1,15 @@
+package com.coding.basic;
+
+public class Test {
+	public static void main(String[] args) {
+		LinkedList linkedList = new LinkedList();
+		for (int i = 0; i < 10; i++) {
+			linkedList.add(i);
+		}
+		for (int i = 0; i < 10; i++) {
+			linkedList.removeLast();
+		}
+		linkedList.removeLast();
+	}
+
+}
diff --git a/group08/529757467/2017-02-26作业/计算机组成原理.doc b/group08/529757467/2017-02-26作业/计算机组成原理.doc
