Skip to content

Commit 95d9fa6

Browse files
Ren650119726Ren650119726
committed
1 parent d4a25d6 commit 95d9fa6

17 files changed

+454
-0
lines changed

‎group17/102228177/.classpath

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,6 @@
1+
<?xml version="1.0" encoding="UTF-8"?>
2+
<classpath>
3+
<classpathentry kind="src" path="src"/>
4+
<classpathentry kind="con" path="org.eclipse.jdt.launching.JRE_CONTAINER"/>
5+
<classpathentry kind="output" path="bin"/>
6+
</classpath>

‎group17/102228177/.project

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
<?xml version="1.0" encoding="UTF-8"?>
2+
<projectDescription>
3+
<name>102228177</name>
4+
<comment></comment>
5+
<projects>
6+
</projects>
7+
<buildSpec>
8+
<buildCommand>
9+
<name>org.eclipse.jdt.core.javabuilder</name>
10+
<arguments>
11+
</arguments>
12+
</buildCommand>
13+
</buildSpec>
14+
<natures>
15+
<nature>org.eclipse.jdt.core.javanature</nature>
16+
</natures>
17+
</projectDescription>

‎group17/102228177/bin/data2_19/ArrayList.class

2.42 KB
Binary file not shown.

‎group17/102228177/bin/data2_19/BinaryTreeNode.class

2.23 KB
Binary file not shown.

‎group17/102228177/bin/data2_19/Iterator.class

168 Bytes
Binary file not shown.

‎group17/102228177/bin/data2_19/LinkedList$Node.class

589 Bytes
Binary file not shown.

‎group17/102228177/bin/data2_19/LinkedList.class

2.51 KB
Binary file not shown.

‎group17/102228177/bin/data2_19/List.class

245 Bytes
Binary file not shown.

‎group17/102228177/bin/data2_19/Queue.class

1.36 KB
Binary file not shown.

‎group17/102228177/bin/data2_19/Stack.class

1.48 KB
Binary file not shown.

‎group17/102228177/src/data2_19/ArrayList.java

Lines changed: 116 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,116 @@
1+
package data2_19;
2+
3+
public class ArrayList implements List{
4+
public static final int defLen = 10;
5+
private Object[] elements;
6+
private int size;
7+
private int maxLen;
8+
9+
public ArrayList(){
10+
size = 0;
11+
maxLen = defLen;
12+
elements = new Object[defLen];
13+
}
14+
15+
/**
16+
* 在ArrayList末尾处追加元素
17+
* @param o 添加的元素
18+
*/
19+
public void add(Object o){
20+
if(size >= maxLen){
21+
grow();
22+
}
23+
elements[size] = o;
24+
size++;
25+
}
26+
27+
/**
28+
* 数组扩容
29+
*/
30+
private void grow(){
31+
maxLen = maxLen + (maxLen >> 1);
32+
Object[] newArr = new Object[maxLen];
33+
System.arraycopy(elements, 0, newArr, 0, size);
34+
elements = newArr;
35+
}
36+
37+
/**
38+
* 在指定索引处添加元素
39+
* @param i 指定索引
40+
* @param o 添加元素
41+
*/
42+
public void add(int i,Object o){
43+
//判断插入位置大于数组实际长度
44+
if(i > size){
45+
size = i;
46+
if(size >= maxLen){//数组大小大于数组最大容量则需要扩容
47+
grow();
48+
}
49+
}
50+
//插入位置不大于数组实际长度时，将插入位置的元素向后移。
51+
for (int j = size; j > i ; j++) {
52+
elements[j] = elements[j-1];
53+
}
54+
elements[i] = o;
55+
size++;
56+
}
57+
58+
/**
59+
* 获取传入索引的元素
60+
* @param index 索引
61+
* @return 返回传入索引的元素
62+
*/
63+
public Object get(int index){
64+
//索引不在实际范围内
65+
if(index < 0||index >= size){
66+
throw new ArrayIndexOutOfBoundsException();
67+
}
68+
for (int i = 0; i < size; i++) {
69+
return elements[index];
70+
}
71+
return null;
72+
}
73+
74+
/**
75+
* 删除指定索引元素并返回
76+
* @param index
77+
* @return 该索引处元素
78+
*/
79+
public Object remove(int index){
80+
//索引不在实际范围内
81+
if(index < 0||index >= size){
82+
throw new ArrayIndexOutOfBoundsException();
83+
}else{
84+
for (int j = index; j < size-1; j++) {
85+
elements[j]=elements[j+1];
86+
}
87+
size--;
88+
return elements[index];
89+
}
90+
}
91+
92+
/**
93+
* 获取大小
94+
* @return
95+
*/
96+
public int size(){
97+
return size;
98+
}
99+
100+
// public Iterator iterator(){
101+
// return null;
102+
// }
103+
public static void main(String[] args) {
104+
ArrayList list = new ArrayList();
105+
list.add(0);
106+
list.add(1);
107+
list.add(2);
108+
list.add(3);
109+
list.add(4);
110+
list.add(6, 6);
111+
list.remove(3);
112+
for (int i = 0; i < list.size(); i++) {
113+
System.out.println(i+":"+list.get(i));
114+
}
115+
}
116+
}

‎group17/102228177/src/data2_19/BinaryTreeNode.java

Lines changed: 74 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,74 @@
1+
package data2_19;
2+
3+
public class BinaryTreeNode implements Comparable<BinaryTreeNode>{
4+
5+
private Object data;
6+
private BinaryTreeNode left;
7+
private BinaryTreeNode right;
8+
9+
public BinaryTreeNode(Object o) {
10+
this.data = o;
11+
}
12+
13+
public Object getData() {
14+
return data;
15+
}
16+
public void setData(Object data) {
17+
this.data = data;
18+
}
19+
public BinaryTreeNode getLeft() {
20+
return left;
21+
}
22+
public void setLeft(BinaryTreeNode left) {
23+
this.left = left;
24+
}
25+
public BinaryTreeNode getRight() {
26+
return right;
27+
}
28+
public void setRight(BinaryTreeNode right) {
29+
this.right = right;
30+
}
31+
32+
@Override
33+
public int compareTo(BinaryTreeNode o) {
34+
return (this.data.hashCode() < o.data.hashCode()) ? -1 :
35+
((this.data.hashCode() == o.data.hashCode()) ? 0 : 1);
36+
}
37+
38+
public BinaryTreeNode insert(Object o){
39+
BinaryTreeNode node = new BinaryTreeNode(o);
40+
insertNode(this,node);
41+
return node;
42+
}
43+
44+
private void insertNode(BinaryTreeNode parentNode, BinaryTreeNode node) {
45+
//父节点大于添加元素
46+
if(parentNode.compareTo(node) == 1){
47+
if(parentNode.left == null){
48+
parentNode.left = node;
49+
return;
50+
}
51+
insertNode(parentNode.left, node);
52+
}
53+
//父节点小于添加元素
54+
else
55+
if(parentNode.compareTo(node) == -1){
56+
if(parentNode.right == null){
57+
parentNode.right = node;
58+
return;
59+
}
60+
insertNode(parentNode.right, node);
61+
}else{
62+
throw new RuntimeException("No duplicate vertex allowed!");
63+
}
64+
}
65+
66+
public static void main(String[] args) {
67+
BinaryTreeNode tree = new BinaryTreeNode(5);
68+
tree.insert(2);
69+
tree.insert(23);
70+
tree.insert(7);
71+
tree.insert(1);
72+
}
73+
74+
}

‎group17/102228177/src/data2_19/Iterator.java

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

‎group17/102228177/src/data2_19/LinkedList.java

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

‎group17/102228177/src/data2_19/List.java

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
package data2_19;
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+
}

0 commit comments

Comments
 (0)