Skip to content

Commit f63a0b3

Browse files
author
龚启盼
committed
init
1 parent d4a25d6 commit f63a0b3

File tree

11 files changed

+376
-0
lines changed

11 files changed

+376
-0
lines changed

‎group11/252308879/dataStructure/.classpath

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
<?xml version="1.0" encoding="UTF-8"?>
2+
<classpath>
3+
<classpathentry kind="src" output="target/classes" path="src/main/java">
4+
<attributes>
5+
<attribute name="optional" value="true"/>
6+
<attribute name="maven.pomderived" value="true"/>
7+
</attributes>
8+
</classpathentry>
9+
<classpathentry kind="src" output="target/test-classes" path="src/test/java">
10+
<attributes>
11+
<attribute name="optional" value="true"/>
12+
<attribute name="maven.pomderived" value="true"/>
13+
</attributes>
14+
</classpathentry>
15+
<classpathentry kind="con" path="org.eclipse.jdt.launching.JRE_CONTAINER"/>
16+
<classpathentry kind="con" path="org.eclipse.m2e.MAVEN2_CLASSPATH_CONTAINER">
17+
<attributes>
18+
<attribute name="maven.pomderived" value="true"/>
19+
</attributes>
20+
</classpathentry>
21+
<classpathentry kind="output" path="target/classes"/>
22+
</classpath>

‎group11/252308879/dataStructure/.gitignore

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
dataStructure/.classpath
2+
dataStructure/.project
3+
dataStructure/.settings/
4+
dataStructure/.classpath
5+
6+
.project
7+
.settings/
8+
target/
9+
# 忽略IntelliJ IDEA配置文件
10+
*.iml
11+
*.idea/

‎group11/252308879/dataStructure/pom.xml

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
2+
xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
3+
<modelVersion>4.0.0</modelVersion>
4+
5+
<groupId>org.apn.coding2017</groupId>
6+
<artifactId>dataStructure</artifactId>
7+
<version>1.0.0-SNAPSHOT</version>
8+
<packaging>jar</packaging>
9+
10+
<name>dataStructure</name>
11+
<url>http://maven.apache.org</url>
12+
13+
<properties>
14+
<project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
15+
</properties>
16+
17+
<dependencies>
18+
<dependency>
19+
<groupId>junit</groupId>
20+
<artifactId>junit</artifactId>
21+
<version>4.12</version>
22+
<scope>test</scope>
23+
</dependency>
24+
</dependencies>
25+
</project>

‎group11/252308879/dataStructure/src/main/java/org/apn/coding2017/basic/ArrayList.java

Lines changed: 120 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,120 @@
1+
package org.apn.coding2017.basic;
2+
3+
import java.util.Arrays;
4+
5+
/**
6+
* Created by QiPan on 2017/2/23.
7+
*/
8+
public class ArrayList implements List {
9+
10+
private int size;
11+
12+
// 设置默认容量 不可变
13+
private static final int DEFAULT_CAPACITY = 10;
14+
15+
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
16+
17+
private Object[] elementData;
18+
19+
private int modCount = 0;
20+
21+
// 定义一个默认的空的数组,引用不可变
22+
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
23+
24+
public ArrayList(int initialCapacity) {
25+
if (initialCapacity > 0) {
26+
this.elementData = new Object[initialCapacity];
27+
} else if (initialCapacity == 0) {
28+
this.elementData = new Object[]{};
29+
} else {
30+
throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
31+
}
32+
}
33+
34+
public ArrayList() { // 如果调用默认构造函数，设置容器为空的默认数组
35+
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
36+
}
37+
38+
39+
public boolean add(Object o) {
40+
ensureCapacityInternal(size + 1);
41+
elementData[size++] = o;
42+
return true;
43+
}
44+
45+
public Object set(int index, Object element) {
46+
return null;
47+
}
48+
49+
public Object get(int index) {
50+
return null;
51+
}
52+
53+
public Object remove(int index) {
54+
return null;
55+
}
56+
57+
public int size() {
58+
return 0;
59+
}
60+
61+
public boolean isEmpty() {
62+
return false;
63+
}
64+
65+
public Iterator iterator() {
66+
return null;
67+
}
68+
69+
private void ensureCapacityInternal(int minCapacity) {
70+
// 如果是容器是默认的空的数组
71+
if (this.elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
72+
// 取得为与默认容量相比的较大值
73+
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
74+
}
75+
ensureExplicitCapacity(minCapacity);
76+
// 调用确保有能力放下那么多元素
77+
}
78+
79+
private void ensureExplicitCapacity(int minCapacity) {
80+
modCount++;
81+
82+
// 防止容量溢出。所需的最小容器大于数组长度
83+
if (minCapacity - elementData.length > 0) {
84+
grow(minCapacity);
85+
}
86+
}
87+
88+
/**
89+
* 扩充容量
90+
* @param minCapacity
91+
*/
92+
private void grow(int minCapacity){
93+
int oldCapacity = elementData.length;
94+
// 得到一个新的容量大小，为 oldCapacity 的1.5倍
95+
int newCapacity = oldCapacity + (oldCapacity >> 1);
96+
// 如果扩容后的大小比，最小容量（DEFAULT_CAPACITY： 10）小
97+
if (newCapacity - minCapacity < 0){
98+
newCapacity = minCapacity;
99+
}else if (newCapacity - MAX_ARRAY_SIZE > 0){ // 扩容后比最大的还大，考虑溢出
100+
//
101+
newCapacity = hugeCapacity(minCapacity);
102+
}
103+
104+
elementData = Arrays.copyOf(elementData, newCapacity);
105+
}
106+
107+
/**
108+
* 这个很少用到这个判断，毕竟基本不会使用那么大容量存储
109+
* @param minCapacity
110+
* @return
111+
*/
112+
private static int hugeCapacity(int minCapacity){
113+
if (minCapacity < 0){
114+
throw new OutOfMemoryError();
115+
}
116+
return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
117+
}
118+
119+
120+
}

‎group11/252308879/dataStructure/src/main/java/org/apn/coding2017/basic/BinaryTreeNode.java

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

‎group11/252308879/dataStructure/src/main/java/org/apn/coding2017/basic/Iterator.java

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
package org.apn.coding2017.basic;
2+
3+
/**
4+
* Created by QiPan on 2017/2/23.
5+
*/
6+
public interface Iterator {
7+
boolean hasNext();
8+
9+
Object next();
10+
11+
void remove();
12+
}

‎group11/252308879/dataStructure/src/main/java/org/apn/coding2017/basic/LinkedList.java

Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
package org.apn.coding2017.basic;
2+
3+
/**
4+
* Created by QiPan on 2017/2/23.
5+
*/
6+
public class LinkedList implements List {
7+
8+
Node last;
9+
10+
private static class Node {
11+
Object item;
12+
Node next;
13+
}
14+
15+
public boolean add(Object o) {
16+
17+
return true;
18+
}
19+
20+
public Object set(int index, Object element) {
21+
return null;
22+
}
23+
24+
public void add(int index, Object o) {
25+
26+
}
27+
28+
public Object get(int index) {
29+
return null;
30+
}
31+
32+
public Object remove(int index) {
33+
return null;
34+
}
35+
36+
public int size() {
37+
return 0;
38+
}
39+
40+
public boolean isEmpty() {
41+
return false;
42+
}
43+
44+
public Iterator iterator() {
45+
return null;
46+
}
47+
48+
49+
50+
}

‎group11/252308879/dataStructure/src/main/java/org/apn/coding2017/basic/List.java

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
package org.apn.coding2017.basic;
2+
3+
4+
/**
5+
* Created by QiPan on 2017/2/23.
6+
*/
7+
public interface List {
8+
9+
boolean add(Object o);
10+
11+
Object set(int index, Object element);
12+
13+
Object get(int index);
14+
15+
Object remove(int index);
16+
17+
int size();
18+
19+
boolean isEmpty();
20+
21+
Iterator iterator();
22+
}

‎group11/252308879/dataStructure/src/main/java/org/apn/coding2017/basic/Queue.java

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
package org.apn.coding2017.basic;
2+
3+
/**
4+
* Created by QiPan on 2017/2/23.
5+
*/
6+
public class Queue {
7+
8+
public void enQueue(Object o){
9+
}
10+
11+
public Object deQueue(){
12+
return null;
13+
}
14+
15+
public boolean isEmpty(){
16+
return false;
17+
}
18+
19+
public int size(){
20+
return -1;
21+
}
22+
}

‎group11/252308879/dataStructure/src/main/java/org/apn/coding2017/basic/Stack.java

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
package org.apn.coding2017.basic;
2+
3+
/**
4+
* Created by QiPan on 2017/2/23.
5+
*/
6+
public class Stack {
7+
private ArrayList elementData = new ArrayList();
8+
9+
public void push(Object o){
10+
}
11+
12+
public Object pop(){
13+
return null;
14+
}
15+
16+
public Object peek(){
17+
return null;
18+
}
19+
public boolean isEmpty(){
20+
return false;
21+
}
22+
public int size(){
23+
return -1;
24+
}
25+
}

‎group11/252308879/dataStructure/src/test/java/org/apn/coding2017/TestJavaUtilArrayList.java

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
package org.apn.coding2017;
2+
3+
import org.junit.Assert;
4+
import org.junit.Test;
5+
6+
import java.util.ArrayList;
7+
import java.util.List;
8+
9+
/**
10+
* Created by QiPan on 2017/2/23.
11+
*/
12+
public class TestJavaUtilArrayList {
13+
14+
15+
@Test
16+
public void testAdd() {
17+
List arrayList = new ArrayList(5);
18+
arrayList.add(new Object());
19+
System.out.println("sssssssssssss");
20+
}
21+
22+
@Test
23+
public void testRightShift() {
24+
int x = 5;
25+
26+
x = x << 1;
27+
x = x >> 1;
28+
29+
System.out.println(x);
30+
}
31+
32+
}

0 commit comments

Comments
 (0)