Skip to content

Commit b1e9d0b

Browse files
zhijiaxinyuzhijiaxinyu
authored
Merge pull request onlyliuxin#3 from AllenLink/master
FirstHomework
2 parents cd9bfa2 + 4baf9c1 commit b1e9d0b

File tree

10 files changed

+536
-0
lines changed

10 files changed

+536
-0
lines changed

‎group10/3314793852/.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>

‎group10/3314793852/.gitignore

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1 @@
1+
/bin/

‎group10/3314793852/.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>FirstWeek</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>

‎group10/3314793852/src/myList/MyArrayList.java

Lines changed: 103 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,103 @@
1+
package myList;
2+
3+
/*
4+
* ArrayList的底层是一个数组，通过重新创建新数组的方法，动态扩大数组的容量。
5+
* 该ArrayList不允许隔空插入数据。
6+
*/
7+
8+
public class MyArrayList {
9+
private int theSize; //当前大小
10+
private static final int DEFAULT_CAPACITY=10; //默认容量
11+
private Object[] theArr=new Object[10]; //底层数组
12+
13+
//初始化
14+
public MyArrayList(){
15+
clear();
16+
}
17+
18+
//清空
19+
public void clear(){
20+
theSize=0;
21+
capacityBigger(DEFAULT_CAPACITY);
22+
}
23+
24+
//获取大小
25+
public int size(){
26+
return theSize;
27+
}
28+
29+
//获取底层数组
30+
public Object[] getArr(){
31+
return theArr;
32+
33+
}
34+
//插入，直接插入到数组尾部。
35+
public void add(Object a){
36+
add(theSize, a);
37+
}
38+
39+
//根据下标获取数据
40+
public Object get(int i){
41+
if(i<0||i>=theSize){
42+
throw new ArrayIndexOutOfBoundsException();
43+
}
44+
return theArr[i];
45+
}
46+
47+
//插入，根据指定下标插入。
48+
public void add(int i,Object a){
49+
50+
if(theSize==theArr.length){ //开始容量为10，每当成功添加了一个数据时，则size+1,当size和数组的大小相同时，则调用数组扩大方法，动态扩大数组的大小。
51+
capacityBigger(size());
52+
}
53+
for(int j=theSize-1;j>=i;j--){
54+
theArr[j+1]=theArr[j];
55+
}
56+
theArr[i]=a;
57+
58+
theSize++;
59+
}
60+
61+
//删除,根据下标删除数据。
62+
public void remove(int i){
63+
64+
for(int j=i;j<theSize;j++){
65+
theArr[j]=theArr[j+1];
66+
}
67+
68+
theSize--;
69+
}
70+
71+
//数组扩大容量
72+
public void capacityBigger(int Size){
73+
Object[] newTheArr=new Object[Size*2];
74+
for(int i=0;i<theArr.length;i++){
75+
newTheArr[i]=theArr[i];
76+
}
77+
theArr=newTheArr;
78+
}
79+
80+
//获取MyIterator接口对象
81+
public MyIterator myIterator(){
82+
83+
return myIterator(this);
84+
}
85+
86+
public MyIterator myIterator(Object arr){
87+
MyIterator i=new MyIterator(arr);
88+
return i;
89+
}
90+
91+
92+
//打印数组
93+
public void print(){
94+
for(int i=0;i<theSize;i++){
95+
System.out.println(theArr[i]);
96+
}
97+
}
98+
}
99+
100+
101+
102+
103+

‎group10/3314793852/src/myList/MyBinarySearchTree.java

Lines changed: 113 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,113 @@
1+
2+
package myList;
3+
4+
public class MyBinarySearchTree {
5+
6+
private BinaryNode root; //根节点
7+
8+
//节点BinaryNode
9+
private static class BinaryNode{
10+
11+
Object element; //节点数据
12+
BinaryNode left; //该节点的左节点
13+
BinaryNode right; //该节点的右节点
14+
15+
BinaryNode(Object theElement){
16+
this(theElement, null, null);
17+
}
18+
19+
BinaryNode(Object element,BinaryNode left,BinaryNode right){
20+
this.element=element;
21+
this.left=left;
22+
this.right=right;
23+
}
24+
}
25+
26+
public MyBinarySearchTree(){
27+
this.root=null;
28+
}
29+
30+
//清空二叉树。
31+
public void makeEmpty(){
32+
root=null;
33+
}
34+
35+
//判断是否为空。
36+
public boolean isEmpty(){
37+
return this.root==null;
38+
}
39+
40+
//判断是否存在一个数。
41+
public boolean contains(Object x,BinaryNode aNode){
42+
43+
//首先判断该二叉树是否为空，就是没有找到符合的子节点。
44+
if(aNode==null){
45+
return false;
46+
}
47+
48+
//和当前的节点进行比较。
49+
Integer comparaResult=(Integer)aNode.element-(Integer)x;
50+
51+
//当数据小于当前节点的数据时，则该数据应该在当前节点的左孩子节点中。
52+
if(comparaResult>0){
53+
return contains(x,aNode.left);
54+
}
55+
else if(comparaResult<0){//当数据大于当前节点的数据时，则该数据应该在当前节点的右孩子节点中。
56+
return contains(x,aNode.right);
57+
}
58+
else{ //当数据等于当前节点的数据时，则该数据应该在当前节点中。
59+
return true;
60+
}
61+
}
62+
63+
//插入数据。
64+
public void insert(Object x){
65+
root=insert(x,root);
66+
}
67+
68+
public BinaryNode insert(Object x,BinaryNode aNode){
69+
70+
if(aNode==null){//当前为新的数据节点，因为是叶子节点，所以左右节点为null.
71+
return new BinaryNode(x,null,null);
72+
}
73+
74+
//和当前的节点进行比较。
75+
Integer comparaResult=(Integer)aNode.element-(Integer)x;
76+
77+
//当数据小于当前节点的数据时，则该数据应该在当前节点的左孩子节点中。
78+
if(comparaResult>0){
79+
aNode.left= insert(x,aNode.left);
80+
}
81+
else if(comparaResult<0){//当数据大于当前节点的数据时，则该数据应该在当前节点的右孩子节点中。
82+
aNode.right=insert(x,aNode.right);
83+
}
84+
else{ //当数据等于当前节点的数据时，则该数据应该在当前节点中,则不做任何操作。
85+
;
86+
}
87+
return aNode;
88+
}
89+
90+
//打印出二叉树。
91+
public void getData(){
92+
getData(root);
93+
}
94+
public void getData(BinaryNode root){
95+
if (root != null) {
96+
//左孩子
97+
this.getData(root.left);
98+
99+
//右孩子
100+
this.getData(root.right);
101+
//父节点
102+
this.print(root);
103+
}
104+
105+
}
106+
107+
//打印节点。
108+
public void print(BinaryNode root){
109+
System.out.println(
110+
(Integer)(root.element)
111+
);
112+
}
113+
}

‎group10/3314793852/src/myList/MyIterator.java

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
2+
package myList;
3+
4+
public class MyIterator {
5+
6+
private Object aData;
7+
private int i=0;
8+
private int l=0;
9+
MyLinkedList.Node node;
10+
public MyIterator(Object aDate){
11+
this.aData=aDate;
12+
}
13+
14+
public boolean hasNext(){
15+
if(aData instanceof MyArrayList){//MyArrayListµÄIterator
16+
17+
Object[] arr=((MyArrayList) aData).getArr();
18+
int a=((MyArrayList)aData).size();
19+
return a>i;
20+
}
21+
else{//MyLinkedListµÄIterator
22+
node=((MyLinkedList)aData).getHeadNode();//»ñµÃÍ·½Úµã
23+
int a=((MyLinkedList)aData).size();
24+
return a>l;
25+
}
26+
27+
28+
}
29+
public Object next(){
30+
if(aData instanceof MyArrayList){//MyArrayListµÄIterator
31+
32+
Object[] arr=((MyArrayList) aData).getArr();
33+
return arr[++i];
34+
}
35+
else{//MyLinkedListµÄIterator
36+
l++;
37+
return node.getDate();
38+
}
39+
}
40+
}

0 commit comments

Comments
 (0)