Skip to content

Commit 27f1753

Browse files
jodie-zssjodie-zss
authored
Merge pull request onlyliuxin#12 from hiei17/master
....
2 parents 4ea6342 + 7816dd2 commit 27f1753

File tree

8 files changed

+481
-0
lines changed

8 files changed

+481
-0
lines changed

‎group15/1503_1311822904/myCollection/src/ArrayList.java

Lines changed: 99 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,99 @@
1+
import java.util.Arrays;
2+
3+
public class ArrayList implements List {
4+
5+
private int size = 0;
6+
private int length=3;
7+
private Object[] elementData = new Object[length];
8+
9+
public void add(Object o){
10+
if(size>=length){
11+
grow(100);
12+
}
13+
elementData[size]=o;
14+
size++;
15+
}
16+
public void add(int index, Object o){
17+
size++;
18+
if(size>=length){
19+
grow(100);
20+
}
21+
System.arraycopy(elementData,index,elementData,index+1,size-index-1);
22+
elementData[index]=o;
23+
}
24+
25+
public Object get(int index){
26+
if(index<size)
27+
return elementData[index];
28+
throw new IndexOutOfBoundsException();
29+
}
30+
31+
public Object remove(int index){
32+
//越界
33+
if(index>=size)
34+
throw new IndexOutOfBoundsException();
35+
size--;
36+
Object a=elementData[index];
37+
//刚好最后一个
38+
if (index+1==size){
39+
return a;
40+
}
41+
System.arraycopy(elementData,index+1,elementData,index,size);
42+
return a;
43+
}
44+
45+
public int size(){
46+
return size;
47+
}
48+
49+
public Iterator iterator(){
50+
return new ArrayListIterator();
51+
}
52+
private class ArrayListIterator implements Iterator{
53+
private int index=0;
54+
@Override
55+
public boolean hasNext() {
56+
if(index+1<size){
57+
index++;
58+
return true;
59+
}
60+
return false;
61+
}
62+
63+
@Override
64+
public Object next() {
65+
return elementData[index];
66+
}
67+
}
68+
private void grow(int increase){
69+
//return Arrays.copyOf(src,src.length+size);
70+
Object[] target=new Object[length+increase];
71+
System.arraycopy(elementData,0,target,0,length);
72+
elementData= target;
73+
length=length+increase;
74+
}
75+
public String toString(){
76+
return Arrays.toString(Arrays.copyOf(elementData,size));
77+
}
78+
public static void main(String[] arg){
79+
ArrayList a=new ArrayList();
80+
a.add(0);
81+
a.add(1);
82+
a.add("2");
83+
a.add("3");
84+
a.add("4");
85+
a.add("5");
86+
a.add("six");
87+
a.add("七");
88+
a.add(8);
89+
Iterator iterator=a.iterator();
90+
while (iterator.hasNext())
91+
System.out.println(iterator.next());
92+
/*System.out.println(a.remove(3));
93+
System.out.println(a.size());
94+
System.out.println(a);*/
95+
96+
//System.out.println(a.get(3));
97+
//System.out.println(a.get(99));
98+
}
99+
}

‎group15/1503_1311822904/myCollection/src/BinaryTreeNode.java

Lines changed: 70 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,70 @@
1+
import java.util.Objects;
2+
3+
public class BinaryTreeNode {
4+
5+
private Integer data;
6+
private BinaryTreeNode left;
7+
private BinaryTreeNode right;
8+
9+
public Integer getData() {
10+
return data;
11+
}
12+
public void setData(Integer 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+
//TODO
28+
public BinaryTreeNode insert(Integer o){
29+
if(data==null){
30+
data=o;
31+
return this;
32+
}
33+
34+
BinaryTreeNode b=new BinaryTreeNode();
35+
b.setData(o);
36+
37+
if(Objects.equals(data, o)){
38+
return this;
39+
}
40+
if(data<o){
41+
if(left==null){
42+
left=b;
43+
return b;
44+
}
45+
left.insert(o);
46+
}
47+
if(data>o){
48+
if(right==null){
49+
right=b;
50+
return b;
51+
}
52+
right.insert(o);
53+
}
54+
return b;
55+
}
56+
57+
public void showAll(){
58+
if(right!=null){
59+
right.showAll();
60+
}
61+
System.out.print(data+" ");
62+
if(left!=null){
63+
left.showAll();
64+
}
65+
66+
}
67+
68+
69+
70+
}

‎group15/1503_1311822904/myCollection/src/Iterator.java

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

‎group15/1503_1311822904/myCollection/src/LinkedList.java

Lines changed: 182 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,182 @@
1+
public class LinkedList implements List {
2+
private int size = 0;
3+
private Node head=new Node(null);
4+
5+
public void add(Object o){
6+
if(head.data==null){
7+
head.data=o;
8+
return;
9+
}
10+
Node n=head;
11+
while (n.next!=null){
12+
n=n.next;
13+
}
14+
n.next=new Node(o);
15+
size++;
16+
}
17+
public void add(int index , Object o){
18+
Node n=getNode(index);
19+
Node newN=new Node(o);
20+
newN.next=n.next;
21+
n.next=newN;
22+
size++;
23+
}
24+
public Object get(int index){
25+
return getNode(index).data;
26+
}
27+
private Node getNode(int index){
28+
Node n=head;
29+
for (int i=0;i<index;i++){
30+
if(n==null)
31+
throw new IndexOutOfBoundsException();
32+
n= n.next;
33+
}
34+
return n;
35+
}
36+
public Object remove(int index){
37+
Object o;
38+
if (index==0){
39+
o=head.data;
40+
head.data=null;
41+
size--;
42+
return o;
43+
}
44+
Node n=getNode(index-1);
45+
o=n.next.data;
46+
n.next=n.next.next;
47+
size--;
48+
return o;
49+
}
50+
51+
public int size(){
52+
53+
return size;
54+
}
55+
56+
public void addFirst(Object o){
57+
size++;
58+
if(head.data==null){
59+
head.data=o;
60+
return;
61+
}
62+
Node n=new Node(o);
63+
n.next=head;
64+
head=n;
65+
66+
}
67+
public void addLast(Object o){
68+
size++;
69+
//要是还没有值 就是头
70+
if (head.data==null){
71+
head.data=o;
72+
}
73+
Node n=head;
74+
//找到最后一个
75+
while (n.next!=null){
76+
n=n.next;
77+
}
78+
//接上去
79+
n.next=new Node(o);
80+
81+
}
82+
public Object removeFirst(){
83+
//没有头
84+
if(head.data==null)
85+
throw new IndexOutOfBoundsException();
86+
Object o=head.data;
87+
head=head.next;
88+
size--;
89+
return o;
90+
}
91+
public Object removeLast(){
92+
//还没有值 异常
93+
if (head.data==null){
94+
throw new IndexOutOfBoundsException();
95+
}
96+
size--;
97+
Object o;
98+
//只有头有值
99+
if(head.next==null){
100+
o=head.data;
101+
head.data=o;
102+
return o;
103+
}
104+
Node n=head;
105+
//找到最后第二个
106+
while (n.next.next!=null)
107+
n=n.next;
108+
//拿到最后一个值
109+
o=n.next.data;
110+
//去掉最后一个节点
111+
n.next=null;
112+
return o;
113+
}
114+
public Iterator iterator(){
115+
return new LinkedIterator();
116+
}
117+
private class LinkedIterator implements Iterator{
118+
private Node n=head;
119+
@Override
120+
public boolean hasNext() {
121+
if(n!=null&&n.next!=null){
122+
n=n.next;
123+
return true;
124+
}
125+
return false;
126+
}
127+
128+
@Override
129+
public Object next() {
130+
return n.data;
131+
}
132+
}
133+
134+
private static class Node{
135+
Object data;
136+
Node next;
137+
Node(Object o){
138+
data=o;
139+
}
140+
141+
142+
}
143+
144+
public String toString(){
145+
String s="[";
146+
for (int i=0;i<size;i++)
147+
s+=get(i)+", ";
148+
s+="]";
149+
return s;
150+
}
151+
152+
public static void main(String[] arg){
153+
LinkedList a=new LinkedList();
154+
// a.removeFirst();
155+
a.addFirst("first");
156+
a.addLast("ll");
157+
a.add(0);
158+
a.add(1);
159+
a.add("2");
160+
a.add("3");
161+
a.add("4");
162+
a.add("5");
163+
a.add("six");
164+
a.add("七");
165+
a.add(8);
166+
System.out.println(a);
167+
Iterator iterator=a.iterator();
168+
while (iterator.hasNext())
169+
System.out.println(iterator.next());
170+
/*System.out.println(a.size);
171+
System.out.println(a);
172+
System.out.println(a.remove(3));
173+
System.out.println(a.remove(3));
174+
a.removeFirst();
175+
a.removeLast();
176+
System.out.println(a);*/
177+
178+
179+
//System.out.println(a.get(3));
180+
//System.out.println(a.get(99));
181+
}
182+
}

‎group15/1503_1311822904/myCollection/src/List.java

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

0 commit comments

Comments
 (0)