Skip to content

Commit e0ab6d0

Browse files
onlyliuxinonlyliuxin
authored
Merge pull request onlyliuxin#33 from MrGPanPan/master
Group 11 第一周作业提交
2 parents 99f53a7 + 452821d commit e0ab6d0

File tree

88 files changed

+4452
-0
lines changed

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

88 files changed

+4452
-0
lines changed

‎group11/1178243325/DataStructure/build.gradle

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,10 @@
1+
apply plugin: 'java'
2+
apply plugin: 'eclipse'
3+
4+
jar {
5+
manifest {
6+
attributes 'Main-Class' : 'com.coding.Main'
7+
}
8+
}
9+
10+

‎group11/1178243325/DataStructure/readme.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1 @@
1+
实现基本的数据结构ArrayList,LinkList,Stack,Queue,Tree,Iterator

‎group11/1178243325/DataStructure/src/main/java/com/coding/Main.java

Lines changed: 58 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,58 @@
1+
package com.coding;
2+
3+
import com.coding.basic.*;
4+
public class Main {
5+
public static void main(String[] args) {
6+
ArrayList list = new ArrayList();
7+
8+
list.add(0, "2xxx");
9+
list.add(1, "we");
10+
list.add(2, "sss");
11+
list.add("xing");
12+
list.remove(2);
13+
System.out.println(list.get(2));
14+
Iterator iterator = list.iterator();
15+
while(iterator.hasNext()) {
16+
System.out.println(iterator.next());
17+
}
18+
System.out.println(list.size());
19+
20+
LinkedList llist = new LinkedList();
21+
llist.add("hu");
22+
llist.add("zhao");
23+
llist.add(2,"xing");
24+
llist.addFirst("身骑白马");
25+
llist.addLast("德州小老虎");
26+
llist.add(5, "sf");
27+
llist.remove(5);
28+
llist.removeFirst();
29+
llist.removeLast();
30+
for (int i = 2; i >=0; i--)
31+
System.out.print(llist.get(i));
32+
System.out.println(llist.size());
33+
34+
Iterator literator = llist.iterator();
35+
while(literator.hasNext()) {
36+
System.out.println(literator.next());
37+
}
38+
39+
Stack stack = new Stack();
40+
stack.push(1);
41+
stack.push(2);
42+
stack.push(3);
43+
stack.push(4);
44+
System.out.println(stack.peek());
45+
while(!stack.isEmpty())
46+
System.out.println(stack.pop());
47+
48+
Queue queue = new Queue();
49+
queue.enQueue(1);
50+
queue.enQueue(2);
51+
queue.enQueue(3);
52+
System.out.println(queue.size());
53+
while (!queue.isEmpty()) {
54+
System.out.println(queue.deQueue());
55+
}
56+
57+
}
58+
}

‎group11/1178243325/DataStructure/src/main/java/com/coding/basic/ArrayList.java

Lines changed: 97 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,97 @@
1+
package com.coding.basic;
2+
3+
import com.coding.basic.exception.*;
4+
public class ArrayList implements List {
5+
6+
private int size;
7+
private Object[] elementData;
8+
9+
public ArrayList () {
10+
size = 0;
11+
elementData = new Object[100];
12+
}
13+
14+
public void add(Object o){
15+
add(size(), o);
16+
}
17+
18+
public void add(int index, Object o){
19+
if (size() == elementData.length)
20+
ensureCapacity( size() * 2 + 1);
21+
if (index > size() || index < 0) { //index == size时相当于在尾后插入
22+
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
23+
}
24+
for (int i = size; i > index; i--) {
25+
elementData[i] = elementData[i-1];
26+
}
27+
elementData[index] = o;
28+
size++;
29+
30+
}
31+
32+
private void ensureCapacity(int newCapacity) {
33+
if (newCapacity < size())
34+
return;
35+
Object[] old = elementData;
36+
elementData = new Object[newCapacity];
37+
for (int i = 0; i < size(); i++) {
38+
elementData[i] = old[i];
39+
}
40+
}
41+
42+
public Object get(int index){
43+
if (index >= size() || index < 0) { //获取时,index==size()越界
44+
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
45+
}
46+
return elementData[index];
47+
}
48+
49+
private String outOfBoundsMsg(int index) {
50+
return "Index:" + index + ", Size:" + size;
51+
}
52+
53+
public Object remove(int index){
54+
if (index >= size() || index < 0) {
55+
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
56+
}
57+
Object old = elementData[index];
58+
for (int i = index; i < size(); i++) {
59+
elementData[i] = elementData[i+1];
60+
}
61+
size--;
62+
return old;
63+
}
64+
65+
/*获取表内容量*/
66+
public int size(){
67+
return size;
68+
}
69+
70+
public Iterator iterator(){
71+
return new ArrayListIterator();
72+
}
73+
74+
public class ArrayListIterator implements Iterator {
75+
private final int ONLY_CAPACITY = size;
76+
private int index;
77+
public ArrayListIterator() {
78+
index = 0;
79+
}
80+
81+
@Override
82+
public boolean hasNext() {
83+
if (ONLY_CAPACITY != size)
84+
throw new ConcurrentModificationException("此对象没有进行修改同步");
85+
return index != size;
86+
}
87+
88+
@Override
89+
public Object next() {
90+
if (ONLY_CAPACITY != size)
91+
throw new ConcurrentModificationException("此对象没有进行修改同步");
92+
if (index >= ONLY_CAPACITY)
93+
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
94+
return elementData[index++];
95+
}
96+
}
97+
}

‎group11/1178243325/DataStructure/src/main/java/com/coding/basic/BinaryTreeNode.java

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
package com.coding.basic;
2+
3+
public class BinaryTreeNode {
4+
5+
private Object data;
6+
private BinaryTreeNode left;
7+
private BinaryTreeNode right;
8+
9+
public Object getData() {
10+
return data;
11+
}
12+
public void setData(Object data) {
13+
this.data = data;
14+
}
15+
public BinaryTreeNode getLeft() {
16+
return left;
17+
}
18+
public void setLeft(BinaryTreeNode left) {
19+
this.left = left;
20+
}
21+
public BinaryTreeNode getRight() {
22+
return right;
23+
}
24+
public void setRight(BinaryTreeNode right) {
25+
this.right = right;
26+
}
27+
28+
public BinaryTreeNode insert(Object o){
29+
return null;
30+
}
31+
32+
}

‎group11/1178243325/DataStructure/src/main/java/com/coding/basic/Iterator.java

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,6 @@
1+
package com.coding.basic;
2+
3+
public interface Iterator {
4+
public boolean hasNext();
5+
public Object next();
6+
}

‎group11/1178243325/DataStructure/src/main/java/com/coding/basic/LinkedList.java

Lines changed: 135 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,135 @@
1+
package com.coding.basic;
2+
3+
import com.coding.basic.exception.*;
4+
public class LinkedList implements List {
5+
6+
private Node head;
7+
private int size;
8+
public LinkedList() {
9+
head = new Node(null, null);
10+
size = 0;
11+
}
12+
13+
public void add(Object o){
14+
add(size, o);
15+
}
16+
17+
public void add(int index , Object o){
18+
if (index > size || index < 0) {
19+
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
20+
}
21+
Node frontNode = getNode(index-1);
22+
Node newNode = new Node(o, frontNode.next);
23+
frontNode.next = newNode;
24+
size++;
25+
26+
}
27+
28+
private Node getNode(int index) {
29+
Node node = head;
30+
int i = 0;
31+
while(node.next != null && i <= index) {
32+
node = node.next;
33+
i++;
34+
}
35+
return node;
36+
}
37+
38+
public Object get(int index){
39+
if (index >= size || index < 0) {
40+
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
41+
}
42+
43+
Node node = getNode(index);
44+
return node.data;
45+
}
46+
47+
public Object remove(int index){
48+
if (index >= size || index < 0) {
49+
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
50+
}
51+
Node frontNode = getNode(index-1);
52+
Node oldNode = getNode(index);
53+
frontNode.next = oldNode.next;
54+
size--;
55+
return oldNode.data;
56+
}
57+
58+
public int size(){
59+
return size;
60+
}
61+
62+
public void addFirst(Object o){
63+
//就是这么硬!
64+
add(0, o);
65+
}
66+
67+
public void addLast(Object o){
68+
add(size, o);
69+
}
70+
71+
public Object removeFirst(){
72+
return remove(0);
73+
}
74+
75+
public Object removeLast(){
76+
return remove(size-1);
77+
}
78+
79+
public Iterator iterator(){
80+
return new LinkedListIterator();
81+
}
82+
83+
private class LinkedListIterator implements Iterator {
84+
int index;
85+
final int capacity = size;
86+
LinkedListIterator() {
87+
index = 0;
88+
}
89+
@Override
90+
public boolean hasNext() {
91+
if (capacity != size)
92+
throw new ConcurrentModificationException("此对象没有修改同步");
93+
return index < capacity;
94+
}
95+
96+
@Override
97+
public Object next() {
98+
if (capacity != size)
99+
throw new ConcurrentModificationException("此对象没有修改同步");
100+
if (index >= capacity)
101+
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
102+
return get(index++);
103+
}
104+
}
105+
106+
private String outOfBoundsMsg(int index) {
107+
return "index:" + index + ", size:" + size;
108+
}
109+
110+
private static class Node {
111+
Object data;
112+
Node next;
113+
114+
Node(Object data, Node next) {
115+
this.data = data;
116+
this.next = next;
117+
}
118+
119+
void setData(Object data) {
120+
this.data = data;
121+
}
122+
123+
Object getData() {
124+
return data;
125+
}
126+
127+
void setNext(Node next) {
128+
this.next = next;
129+
}
130+
131+
Object getNext() {
132+
return next;
133+
}
134+
}
135+
}

‎group11/1178243325/DataStructure/src/main/java/com/coding/basic/List.java

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
package com.coding.basic;
2+
3+
public interface List {
4+
public void add(Object o);
5+
public void add(int index, Object o);
6+
public Object get(int index);
7+
public Object remove(int index);
8+
public int size();
9+
}

‎group11/1178243325/DataStructure/src/main/java/com/coding/basic/Queue.java

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
package com.coding.basic;
2+
import com.coding.basic.exception.*;
3+
public class Queue {
4+
5+
private LinkedList elementData;
6+
7+
public Queue() {
8+
elementData = new LinkedList();
9+
}
10+
11+
public void enQueue(Object o){
12+
elementData.addLast(o);
13+
}
14+
15+
public Object deQueue(){
16+
if (isEmpty()) {
17+
throw new EmptyQueueException("队空");
18+
}
19+
Object result = elementData.removeFirst();
20+
return result;
21+
}
22+
23+
public boolean isEmpty(){
24+
return elementData.size() == 0;
25+
}
26+
27+
public int size(){
28+
return elementData.size();
29+
}
30+
}

0 commit comments

Comments
 (0)