Skip to content

Commit 07c1290

Browse files
author
赵睿
committed
基本功能完成
1 parent 2a69b5e commit 07c1290

File tree

15 files changed

+916
-0
lines changed

15 files changed

+916
-0
lines changed

‎group03/1360464792/.gitignore

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
# Created by .ignore support plugin (hsz.mobi)
2+
### Java template
3+
# Compiled class file
4+
*.class
5+
6+
# Log file
7+
*.log
8+
9+
# BlueJ files
10+
*.ctxt
11+
12+
# Mobile Tools for Java (J2ME)
13+
.mtj.tmp/
14+
15+
# Package Files #
16+
*.jar
17+
*.war
18+
*.ear
19+
*.zip
20+
*.tar.gz
21+
*.rar
22+
23+
# virtual machine crash logs, see http://www.java.com/en/download/help/error_hotspot.xml
24+
hs_err_pid*
25+
26+
27+
### IntelliJ IDEA ###
28+
.idea
29+
*.iws
30+
*.iml
31+
*.ipr
32+
33+
### maven
34+
target

‎group03/1360464792/pom.xml

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
<?xml version="1.0" encoding="UTF-8"?>
2+
<project xmlns="http://maven.apache.org/POM/4.0.0"
3+
xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
4+
xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
5+
<modelVersion>4.0.0</modelVersion>
6+
7+
<groupId>rui.study</groupId>
8+
<artifactId>coding2017</artifactId>
9+
<version>0.0.1-SNAPSHOT</version>
10+
11+
<name>学习数据结构</name>
12+
13+
<properties>
14+
<java.version>1.6</java.version>
15+
<encoding>UTF-8</encoding>
16+
</properties>
17+
18+
<dependencies>
19+
<dependency>
20+
<groupId>junit</groupId>
21+
<artifactId>junit</artifactId>
22+
<version>4.12</version>
23+
</dependency>
24+
25+
</dependencies>
26+
27+
<build>
28+
<finalName>coding2017</finalName>
29+
<plugins>
30+
<plugin>
31+
<groupId>org.apache.maven.plugins</groupId>
32+
<artifactId>maven-compiler-plugin</artifactId>
33+
<version>3.5.1</version>
34+
<configuration>
35+
<source>${java.version}</source>
36+
<target>${java.version}</target>
37+
<encoding>${encoding}</encoding>
38+
</configuration>
39+
</plugin>
40+
</plugins>
41+
</build>
42+
</project>

‎group03/1360464792/src/main/java/rui/study/coding2017/ArrayList.java

Lines changed: 142 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,142 @@
1+
package rui.study.coding2017;
2+
3+
4+
import java.util.Arrays;
5+
import java.util.NoSuchElementException;
6+
7+
public class ArrayList implements List {
8+
9+
private int size;
10+
11+
private Object[] elementData;
12+
13+
private static Object[] emptyObjects={};
14+
15+
private static int defaultCapacity=10;
16+
17+
public void add(Object o){
18+
ensureCapacity(this.size+1);
19+
elementData[size++]=o;
20+
}
21+
22+
public void add(int index, Object o){
23+
rangeCheckForAdd(index);
24+
if(elementData[index]!=null){
25+
ensureCapacity(this.size+1);
26+
//执行数组拷贝
27+
System.arraycopy(elementData,index,elementData,index+1,size-index);
28+
size++;
29+
}
30+
elementData[index]=o;
31+
}
32+
33+
public Object get(int index){
34+
rangeCheck(index);
35+
return elementData[index];
36+
}
37+
38+
public Object remove(int index){
39+
rangeCheck(index);
40+
Object object=elementData[index];
41+
42+
int numMoved=size-index-1;
43+
//如果是最后一位remove ，无需进行数组拷贝
44+
if(numMoved>0){
45+
System.arraycopy(elementData, index+1, elementData, index,numMoved);
46+
}
47+
elementData[--size]=null;
48+
return object;
49+
}
50+
51+
public int size(){
52+
return this.size;
53+
}
54+
55+
public Iterator iterator(){
56+
return new ArrayListIterator();
57+
}
58+
59+
public ArrayList(){
60+
this.size=0;
61+
this.elementData=emptyObjects;
62+
}
63+
64+
public ArrayList(int size){
65+
this.size=size;
66+
if(size>0){
67+
this.elementData=new Object[size];
68+
}else if(size==0){
69+
this.elementData=emptyObjects;
70+
}else{
71+
throw new IllegalArgumentException("非法容器大小 "+size);
72+
}
73+
74+
}
75+
76+
/**
77+
* 判断索引是否合法
78+
* @param index 索引
79+
*/
80+
private void rangeCheckForAdd(int index) {
81+
if(index>size||index<0)throw new IndexOutOfBoundsException("索引为"+index+",但是当前数组长度为："+size);
82+
}
83+
84+
/**
85+
* 判断索引是否合法 ,
86+
* @param index 索引
87+
*/
88+
private void rangeCheck(int index) {
89+
if(index>=size||index<0)throw new IndexOutOfBoundsException("索引为"+index+",但是当前数组长度为："+size);
90+
}
91+
92+
93+
/**
94+
* 确保当前数组能够长度能够容纳新的对象，如果不够，就自行增长
95+
* @param needLength 需要的数组长度
96+
*/
97+
private void ensureCapacity(int needLength) {
98+
if(elementData==emptyObjects){
99+
needLength = Math.max(defaultCapacity, needLength);
100+
}
101+
102+
if(needLength-elementData.length>0){
103+
this.grow(needLength);
104+
}
105+
}
106+
107+
/**
108+
* 数组扩容
109+
* @param needLength 需要的长度
110+
*/
111+
private void grow(int needLength) {
112+
int elementLength=elementData.length;
113+
//扩容1.5倍
114+
int newLength=elementLength+(elementLength>>1);
115+
116+
if(needLength-newLength>0){
117+
newLength=needLength;
118+
}
119+
this.elementData= Arrays.copyOf(this.elementData,newLength);
120+
}
121+
122+
private class ArrayListIterator implements Iterator{
123+
//游标，当前迭代器执行到何处了
124+
private int cursor=0;
125+
126+
@Override
127+
public boolean hasNext() {
128+
return cursor!=size;
129+
}
130+
131+
@Override
132+
public Object next() {
133+
if (cursor >= size)throw new NoSuchElementException();
134+
Object[] elementData = ArrayList.this.elementData;
135+
return elementData[cursor++];
136+
}
137+
}
138+
139+
140+
141+
142+
}

‎group03/1360464792/src/main/java/rui/study/coding2017/BinaryTree.java

Lines changed: 93 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,93 @@
1+
package rui.study.coding2017;
2+
3+
/**
4+
* 二叉树
5+
* Created by 赵睿 on 2017/2/25.
6+
*/
7+
public class BinaryTree {
8+
private BinaryTreeNode root;
9+
10+
private int size;
11+
12+
public void insert(Comparable comparable){
13+
BinaryTreeNode binaryTreeNode=new BinaryTreeNode(comparable);
14+
15+
if(this.root==null){
16+
this.root=binaryTreeNode;
17+
}else {
18+
boolean flag=false;
19+
BinaryTreeNode cursorNode=root;
20+
while(!flag){
21+
if(comparable.compareTo(cursorNode.getData())<0){
22+
if(cursorNode.getLeft()==null){
23+
cursorNode.setLeft(binaryTreeNode);
24+
flag=true;
25+
}else{
26+
cursorNode=cursorNode.getLeft();
27+
}
28+
}else {
29+
if(cursorNode.getRight()==null){
30+
cursorNode.setRight(binaryTreeNode);
31+
flag=true;
32+
}else{
33+
cursorNode=cursorNode.getRight();
34+
}
35+
}
36+
37+
}
38+
}
39+
size++;
40+
}
41+
42+
public LinkedList inorder(){
43+
LinkedList linkedList=new LinkedList();
44+
sortLeft(linkedList,root);
45+
sortRight(linkedList,root);
46+
return linkedList;
47+
}
48+
49+
private void sortRight(LinkedList linkedList,BinaryTreeNode binaryTreeNode){
50+
Queue queue=getRightList(binaryTreeNode);
51+
while(!queue.isEmpty()){
52+
BinaryTreeNode queueNode = (BinaryTreeNode) queue.deQueue();
53+
sortLeft(linkedList,queueNode);
54+
}
55+
56+
}
57+
58+
private void sortLeft(LinkedList linkedList,BinaryTreeNode binaryTreeNode){
59+
Stack stack=getLeftList(binaryTreeNode);
60+
while(!stack.isEmpty()) {
61+
BinaryTreeNode stackNode = (BinaryTreeNode) stack.pop();
62+
linkedList.add(stackNode.getData());
63+
Queue queue = getRightList(stackNode);
64+
while (!queue.isEmpty()) {
65+
BinaryTreeNode queueNode = (BinaryTreeNode) queue.deQueue();
66+
sortLeft(linkedList,queueNode);
67+
}
68+
}
69+
linkedList.add(binaryTreeNode.getData());
70+
}
71+
72+
73+
private Stack getLeftList(BinaryTreeNode binaryTreeNode){
74+
Stack stack=new Stack();
75+
while(binaryTreeNode.getLeft()!=null){
76+
binaryTreeNode=binaryTreeNode.getLeft();
77+
stack.push(binaryTreeNode);
78+
}
79+
return stack;
80+
}
81+
82+
private Queue getRightList(BinaryTreeNode binaryTreeNode){
83+
Queue queue=new Queue();
84+
while(binaryTreeNode.getRight()!=null){
85+
binaryTreeNode=binaryTreeNode.getRight();
86+
queue.enQueue(binaryTreeNode);
87+
}
88+
return queue;
89+
}
90+
91+
92+
93+
}

‎group03/1360464792/src/main/java/rui/study/coding2017/BinaryTreeNode.java

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
package rui.study.coding2017;
2+
3+
public class BinaryTreeNode {
4+
5+
private Comparable data;
6+
private BinaryTreeNode left;
7+
private BinaryTreeNode right;
8+
9+
public Comparable getData() {
10+
return data;
11+
}
12+
public void setData(Comparable 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() {
29+
}
30+
31+
public BinaryTreeNode(Comparable data) {
32+
this.data = data;
33+
}
34+
35+
public BinaryTreeNode(Comparable data, BinaryTreeNode left, BinaryTreeNode right) {
36+
this.data = data;
37+
this.left = left;
38+
this.right = right;
39+
}
40+
}

‎group03/1360464792/src/main/java/rui/study/coding2017/Iterator.java

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

0 commit comments

Comments
 (0)