Skip to content

Commit db24fec

Browse files
GreastateGreastate
authored
Merge pull request onlyliuxin#17 from chhsalex/master
upload homework for 2-26
2 parents 9251e42 + c38a630 commit db24fec

File tree

9 files changed

+428
-0
lines changed

9 files changed

+428
-0
lines changed

‎group08/619057560/2-26/article/CPU，内存，硬盘，指令之间的关系.pdf

61.8 KB
Binary file not shown.

‎group08/619057560/2-26/code/com/coding/basic/ArrayList.java

Lines changed: 80 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,80 @@
1+
package com.coding.basic;
2+
3+
import java.util.Arrays;
4+
import java.util.NoSuchElementException;
5+
6+
public class ArrayList implements List {
7+
8+
private int size = 0;
9+
10+
private Object[] elementData = new Object[100];
11+
12+
public void add(Object o){
13+
if (size + 1 > elementData.length) {
14+
elementData = Arrays.copyOf(elementData, elementData.length * 3 / 2 + 1);
15+
}
16+
elementData[size++] = o;
17+
}
18+
public void add(int index, Object o){
19+
if (index < 0 || index > size) {
20+
throw new IndexOutOfBoundsException();
21+
}
22+
23+
if (size + 1 > elementData.length) {
24+
elementData = Arrays.copyOf(elementData, elementData.length * 3 / 2 + 1);
25+
}
26+
27+
System.arraycopy(elementData, index, elementData, index+1, size-index);
28+
elementData[index] = o;
29+
size++;
30+
}
31+
32+
public Object get(int index){
33+
if (index < 0 || index >= size) {
34+
throw new IndexOutOfBoundsException();
35+
}
36+
37+
return elementData[index];
38+
}
39+
40+
public Object remove(int index){
41+
if (index < 0 || index >= size) {
42+
throw new IndexOutOfBoundsException();
43+
}
44+
45+
Object old = elementData[index];
46+
size--;
47+
System.arraycopy(elementData, index+1, elementData, index, size-index);
48+
elementData[size] = null;
49+
50+
return old;
51+
}
52+
53+
public int size(){
54+
return size;
55+
}
56+
57+
public Iterator iterator(){
58+
return new Itr();
59+
}
60+
61+
private class Itr implements Iterator {
62+
63+
int cursor = 0;
64+
65+
@Override
66+
public boolean hasNext() {
67+
return (cursor < size);
68+
}
69+
70+
@Override
71+
public Object next() {
72+
if (cursor < 0 || cursor >= size) {
73+
throw new NoSuchElementException();
74+
}
75+
return elementData[cursor++];
76+
}
77+
78+
}
79+
80+
}

‎group08/619057560/2-26/code/com/coding/basic/BinaryTreeNode.java

Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
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+
if (data == null || ((Integer)data).intValue() == ((Integer)o).intValue()) {
30+
data = o;
31+
return this;
32+
}
33+
else if (((Integer)o).intValue() < ((Integer)data).intValue()) {
34+
if (left == null) {
35+
left = new BinaryTreeNode();
36+
}
37+
return left.insert(o);
38+
}
39+
else {
40+
if (right == null) {
41+
right = new BinaryTreeNode();
42+
}
43+
return right.insert(o);
44+
}
45+
}
46+
47+
}

‎group08/619057560/2-26/code/com/coding/basic/Iterator.java

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

‎group08/619057560/2-26/code/com/coding/basic/LinkedList.java

Lines changed: 137 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,137 @@
1+
package com.coding.basic;
2+
3+
import java.util.NoSuchElementException;
4+
5+
public class LinkedList implements List {
6+
7+
private Node head;
8+
9+
public void add(Object o){
10+
Node pNewNode = new Node();
11+
pNewNode.data = o;
12+
13+
Node pNode = head;
14+
15+
if (head == null) {
16+
head = pNewNode;
17+
return;
18+
}
19+
20+
while (pNode.next != null) {
21+
pNode = pNode.next;
22+
}
23+
24+
pNode.next = pNewNode;
25+
}
26+
27+
public void add(int index , Object o){
28+
if (index < 0 && index > size()) {
29+
throw new IndexOutOfBoundsException();
30+
}
31+
32+
Node pNewNode = new Node();
33+
pNewNode.data = o;
34+
35+
if (index == 0) {
36+
pNewNode.next = head;
37+
head = pNewNode;
38+
return;
39+
}
40+
41+
Node pNode = head;
42+
while (--index > 0) {
43+
pNode = pNode.next;
44+
}
45+
pNewNode.next = pNode.next;
46+
pNode.next = pNewNode;
47+
}
48+
49+
public Object get(int index){
50+
if (index < 0 && index >= size()) {
51+
throw new IndexOutOfBoundsException();
52+
}
53+
54+
Node pNode = head;
55+
while (index-- > 0) {
56+
pNode = pNode.next;
57+
}
58+
59+
return pNode.data;
60+
}
61+
62+
public Object remove(int index){
63+
if (index < 0 && index >= size()) {
64+
throw new IndexOutOfBoundsException();
65+
}
66+
67+
Node pNode = head;
68+
if (index == 0) {
69+
head = head.next;
70+
return pNode.data;
71+
}
72+
73+
while (--index > 0) {
74+
pNode = pNode.next;
75+
}
76+
Node pTargetNode = pNode.next;
77+
pNode.next = pTargetNode.next;
78+
79+
return pTargetNode.data;
80+
}
81+
82+
public int size(){
83+
Node pNode = head;
84+
int num = 0;
85+
while (pNode != null) {
86+
pNode = pNode.next;
87+
num++;
88+
}
89+
return num;
90+
}
91+
92+
public void addFirst(Object o){
93+
add(0, o);
94+
}
95+
96+
public void addLast(Object o){
97+
add(o);
98+
}
99+
100+
public Object removeFirst(){
101+
if (head == null) {
102+
throw new NoSuchElementException();
103+
}
104+
return remove(0);
105+
}
106+
107+
public Object removeLast(){
108+
if (head == null) {
109+
throw new NoSuchElementException();
110+
}
111+
112+
Node pNode = head;
113+
Node pPrevNode = null;
114+
while (pNode.next != null) {
115+
pPrevNode = pNode;
116+
pNode = pNode.next;
117+
}
118+
if (pPrevNode != null) {
119+
pPrevNode.next = pNode.next;
120+
}
121+
else {
122+
head = null;
123+
}
124+
return pNode.data;
125+
}
126+
127+
public Iterator iterator(){
128+
return null;
129+
}
130+
131+
132+
private static class Node{
133+
Object data;
134+
Node next;
135+
136+
}
137+
}

‎group08/619057560/2-26/code/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+
}

‎group08/619057560/2-26/code/com/coding/basic/Queue.java

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
package com.coding.basic;
2+
3+
public class Queue {
4+
5+
private LinkedList queueList = new LinkedList();
6+
7+
public void enQueue(Object o){
8+
queueList.addFirst(o);
9+
}
10+
11+
public Object deQueue(){
12+
return queueList.removeLast();
13+
}
14+
15+
public boolean isEmpty(){
16+
return queueList.size() == 0;
17+
}
18+
19+
public int size(){
20+
return queueList.size();
21+
}
22+
}

‎group08/619057560/2-26/code/com/coding/basic/Stack.java

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
package com.coding.basic;
2+
3+
public class Stack {
4+
private ArrayList elementData = new ArrayList();
5+
6+
public void push(Object o){
7+
elementData.add(o);
8+
}
9+
10+
public Object pop(){
11+
return elementData.remove(elementData.size()-1);
12+
}
13+
14+
public Object peek(){
15+
return elementData.get(elementData.size()-1);
16+
}
17+
public boolean isEmpty(){
18+
return elementData.size() == 0;
19+
}
20+
public int size(){
21+
return elementData.size();
22+
}
23+
}

0 commit comments

Comments
 (0)