Skip to content

Commit d0eaeb2

Browse files
JayzyyzyyJayzyyzyy
committed
xuweijay
1 parent 0b12c50 commit d0eaeb2

File tree

13 files changed

+626
-165
lines changed

13 files changed

+626
-165
lines changed

‎group15/1511_714512544/.idea/workspace.xml

Lines changed: 265 additions & 99 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎group15/1511_714512544/src/com/coding/basic/ArrayList.java

Lines changed: 11 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -4,37 +4,37 @@
44
import java.util.NoSuchElementException;
55

66
public class ArrayList implements List {
7-
private int size = 0; //表内元素个数
8-
private Object[] elementData = new Object[10]; //数据结构--数组
7+
private int size = 0; //表内现有元素个数
8+
private Object[] elementData = new Object[2]; //数据结构--数组
99

1010
public void add(Object o){ //在后面追加
11-
if(size == elementData.length) elementData = grow(elementData, 2*elementData.length); //先扩容
11+
if(size == elementData.length) elementData = grow(elementData, 2* elementData.length); //先扩容
1212
elementData[size++] = o;
1313
}
1414

1515
public void add(int index, Object o){ //在指定位置插入
16-
if(size == elementData.length) elementData = grow(elementData, 2*elementData.length); //先扩容
17-
if(index > size || index < 0) throw new RuntimeException("索引越界"); //保证最后一个元素后面也可以插
18-
System.arraycopy(elementData,index,elementData,index+1,size-index);
16+
if(size == elementData.length) elementData = grow(elementData, 2* elementData.length); //先扩容
17+
if(index > size || index < 0) throw new ArrayIndexOutOfBoundsException(); //保证最后一个元素后面也可以插
18+
System.arraycopy(elementData,index, elementData,index+1,size-index);
1919
elementData[index] = o;
2020
size ++;
2121
}
2222

2323
public Object get(int index){ //返回指定索引的元素
24-
if(index > size - 1 || index < 0) throw new RuntimeException("索引越界");
24+
if(index > size - 1 || index < 0) throw new ArrayIndexOutOfBoundsException();
2525
return elementData[index];
2626
}
2727

2828
public Object remove(int index){ //删除指定索引处的元素
29-
if(index > size - 1 || index < 0) throw new RuntimeException("索引越界");
29+
if(index > size - 1 || index < 0) throw new ArrayIndexOutOfBoundsException();
3030
Object o = elementData[index];
31-
System.arraycopy(elementData,index+1,elementData,index,size-index-1);
31+
System.arraycopy(elementData,index+1, elementData,index,size-index-1);
3232
elementData[size-1] = null;
3333
size --;
3434
return o;
3535
}
3636

37-
public int size(){ //元素多少
37+
public int size(){ //number of elements
3838
return size;
3939
}
4040

@@ -52,7 +52,7 @@ public boolean hasNext() {
5252

5353
@Override
5454
public Object next() {
55-
if(size() == 0) throw new NoSuchElementException("堆栈下溢");
55+
if(size() == 0) throw new NoSuchElementException("Stack Underflow");
5656
return elementData[i++];
5757
}
5858
}

‎group15/1511_714512544/src/com/coding/basic/BinarySearchTree.java

Lines changed: 12 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -1,9 +1,9 @@
11
package com.coding.basic;
22

3-
import edu.princeton.cs.algs4.Stack;
3+
import java.util.Stack;
44

55
/**
6-
* 二叉树
6+
二叉树
77
5
88
/ \
99
2 7
@@ -15,7 +15,7 @@
1515
3.后序遍历: 1 4 2 6 8 7 5
1616
*/
1717
public class BinarySearchTree<T extends Comparable<? super T>> {
18-
private BinarySearchTreeNode<T> root; //根节点
18+
private BinarySearchTreeNode<T> root; //root node
1919

2020
public BinarySearchTreeNode<T> getRoot() {
2121
return root;
@@ -87,7 +87,7 @@ public boolean contains(T data){
8787
}
8888

8989
/**
90-
* 前序遍历递归实现
90+
* 前序遍历递归实现 根节点 左子树 右子树
9191
* @param n 根节点
9292
*/
9393
public void preOrder(BinarySearchTreeNode<T> n){
@@ -101,7 +101,7 @@ public void preOrder(BinarySearchTreeNode<T> n){
101101
}
102102

103103
/**
104-
* 中序遍历递归实现
104+
* 中序遍历递归实现 左子树 根节点 右子树
105105
* @param n 根节点
106106
*/
107107
public void midOrder(BinarySearchTreeNode<T> n){
@@ -115,8 +115,8 @@ public void midOrder(BinarySearchTreeNode<T> n){
115115
}
116116

117117
/**
118-
* 后序遍历递归实现
119-
* @param n
118+
* 后序遍历递归实现 左子树 右子树 根节点
119+
* @param n 根节点
120120
*/
121121
public void postOrder(BinarySearchTreeNode<T> n){
122122
if(n.getLeft() != null){
@@ -156,7 +156,7 @@ public void preOrderWithoutRecursion(){
156156
}
157157
current.setState(3); //确认是否有右子树
158158
}else if(current.getState() == 3){
159-
stack.pop(); //删除栈顶节点
159+
stack.pop(); //删除栈顶节点(该节点已经执行完所有程序)
160160
current.setState(0);
161161
}
162162
}
@@ -178,12 +178,12 @@ public void midOrderWithoutRecursion(){
178178
current = stack.peek(); //得到栈顶节点
179179
if(current.getState() == 0){
180180
if(current.getLeft() != null){
181-
stack.push(current.getLeft());
181+
stack.push(current.getLeft()); //确认是否有左子树
182182
}
183183
current.setState(1);
184184
}else if(current.getState() == 1){
185185
System.out.print(current.getData() + " "); //打印数据
186-
current.setState(2); //确认是否有左子树
186+
current.setState(2);
187187
}else if(current.getState() == 2){
188188
if(current.getRight() != null){
189189
stack.push(current.getRight());
@@ -221,7 +221,6 @@ public void postOrderWithoutRecursion(){
221221
}
222222
current.setState(2); //确认是否有左子树
223223
}else if(current.getState() == 2){
224-
225224
System.out.print(current.getData() + " "); //打印数据
226225
current.setState(3); //确认是否有右子树
227226
}else if(current.getState() == 3){
@@ -232,8 +231,8 @@ public void postOrderWithoutRecursion(){
232231
}
233232

234233
//按层遍历，每层从左到右输出
235-
public void printNodeAtLevel(){
234+
/*public void TraversalByLayer(){
236235
237-
}
236+
}*/
238237

239238
}

‎group15/1511_714512544/src/com/coding/basic/BinarySearchTreeNode.java

Lines changed: 9 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,13 +1,13 @@
11
package com.coding.basic;
22

33
/**
4-
* 二叉树结点
4+
* 二叉树BST结点
55
*/
66
public class BinarySearchTreeNode<T>{
77
private T data;
88
private BinarySearchTreeNode<T> left;
99
private BinarySearchTreeNode<T> right;
10-
private int state; //递归状态
10+
private int state; //递归状态(非递归遍历表示一个节点运行到的状态)
1111

1212
public BinarySearchTreeNode(T data) {
1313
this.data = data;
@@ -18,24 +18,31 @@ public BinarySearchTreeNode(T data) {
1818
public T getData() {
1919
return data;
2020
}
21+
2122
public void setData(T data) {
2223
this.data = data;
2324
}
25+
2426
public BinarySearchTreeNode<T> getLeft() {
2527
return left;
2628
}
29+
2730
public void setLeft(BinarySearchTreeNode<T> left) {
2831
this.left = left;
2932
}
33+
3034
public BinarySearchTreeNode<T> getRight() {
3135
return right;
3236
}
37+
3338
public void setRight(BinarySearchTreeNode<T> right) {
3439
this.right = right;
3540
}
41+
3642
public int getState() {
3743
return state;
3844
}
45+
3946
public void setState(int state) {
4047
this.state = state;
4148
}

‎group15/1511_714512544/src/com/coding/basic/LinkedList.java

Lines changed: 28 additions & 21 deletions
Original file line numberDiff line numberDiff line change
@@ -3,7 +3,7 @@
33
import java.util.NoSuchElementException;
44

55
public class LinkedList implements List {
6-
private Node head; //数据结构,首节点
6+
private Node head; //首节点
77
private int size; //节点个数
88

99
public void add(Object o){ //在链表尾部添加node
@@ -20,18 +20,18 @@ public void add(Object o){ //在链表尾部添加node
2020
}
2121

2222
public void add(int index , Object o){ //在指定索引处插入node
23-
if(index > size || index < 0) throw new RuntimeException("索引越界");
23+
if(index > size || index < 0) throw new RuntimeException("IndexOutOfBounds");
2424
if(head == null){
2525
head = new Node(o, null);
2626
}else {
2727
if(index == 0){ //插入位置在头部
2828
head = new Node(o, head);
29-
}else { //后面位置
30-
int i = 0;
29+
}else { //后面位置插入
3130
Node temp = head;
31+
int i = 0;
3232
while(i != index - 1){
33-
i ++;
3433
temp = temp.next;
34+
i ++;
3535
}
3636
Node tempNext = temp.next;
3737
temp.next = new Node(o, tempNext);
@@ -40,8 +40,8 @@ public void add(int index , Object o){ //在指定索引处插入node
4040
size ++;
4141
}
4242

43-
public Object get(int index){ //取出指定节点处的元素
44-
if(index > size -1 || index < 0) throw new RuntimeException("索引越界");
43+
public Object get(int index){ //取出指定节点处的元素,从0开始
44+
if(index > size -1 || index < 0) throw new RuntimeException("IndexOutOfBounds");
4545
int i = 0;
4646
Node temp = head;
4747
while(i != index){
@@ -52,23 +52,22 @@ public Object get(int index){ //取出指定节点处的元素
5252
}
5353

5454
public Object remove(int index){ //删除指定索引处的节点
55-
if(index > size -1 || index < 0) throw new RuntimeException("索引越界");
55+
if(index > size -1 || index < 0) throw new RuntimeException("IndexOutOfBounds");
5656
if(index == 0) { //第一个元素或只有一个元素
5757
Object o = head.data;
5858
head = head.next;
5959
size --;
6060
return o;
6161
}else { //其他元素
6262
int i = 0;
63-
Node temp = head;
63+
Node temp = head; //被删除节点之前的节点
6464
while(i != index - 1){
6565
i ++;
6666
temp = temp.next;
6767
}
68-
Node delete = temp.next;
68+
Node delete = temp.next; //被删除的节点
6969
Object o = delete.data;
70-
temp.next = delete.next;
71-
delete = null;
70+
temp.next = delete.next; //删除
7271
size --;
7372
return o;
7473
}
@@ -98,22 +97,30 @@ public void addLast(Object o){ //在链表尾部添加节点
9897
}
9998

10099
public Object removeFirst(){ //在链表头部删除节点
101-
if(size() == 0) throw new RuntimeException("堆栈下溢");
100+
if(size() == 0) throw new RuntimeException("Underflow");
102101
Object o = head.data;
103102
head = head.next;
104103
size --;
105104
return o;
106105
}
107106

108107
public Object removeLast(){ //在链表尾部删除节点
109-
if(size() == 0) throw new RuntimeException("堆栈下溢");
110-
Node last = head;
111-
while(last.next != null){
112-
last = last.next;
108+
if(size() == 0) throw new RuntimeException("Underflow");
109+
if(size() == 1){
110+
Object o = head.data;
111+
head = null;
112+
size --;
113+
return o;
114+
}
115+
Node temp = head;
116+
int i = 0;
117+
while(i != size-2){
118+
temp = temp.next;
119+
i ++;
113120
}
114-
Object o = last.data;
121+
Object o = temp.next.data;
122+
temp.next = null;
115123
size --;
116-
last = null;
117124
return o;
118125
}
119126

@@ -131,14 +138,14 @@ public boolean hasNext() {
131138

132139
@Override
133140
public Object next() {
134-
if(size() == 0) throw new NoSuchElementException("堆栈下溢");
141+
if(size() == 0) throw new NoSuchElementException("Underflow");
135142
Object o = current.data;
136143
current = current.next;
137144
return o;
138145
}
139146
}
140147

141-
//这里内部类必须为static,这里的每个LinkedList对象都对应唯一的class Node,在类级别上一一对应，非实例级别
148+
//这里内部类须为static,在类级别上一一对应，非实例级别
142149
private static class Node{
143150
Object data;
144151
Node next;

‎group15/1511_714512544/src/com/coding/basic/List.java

Lines changed: 5 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,12 +1,16 @@
11
package com.coding.basic;
22

33
/**
4-
* 随机访问
4+
* List可以随机访问,不需要遍历
55
*/
66
public interface List {
77
void add(Object o);
8+
89
void add(int index, Object o);
10+
911
Object get(int index);
12+
1013
Object remove(int index);
14+
1115
int size();
1216
}

‎group15/1511_714512544/src/com/coding/basic/Queue.java

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -6,7 +6,7 @@
66
* 队列,先进先出
77
*/
88
public class Queue {
9-
private LinkedList list = new LinkedList(); //自己选取数据结构
9+
private LinkedList list = new LinkedList(); //链表数据结构
1010

1111
//入队
1212
public void enQueue(Object o){
@@ -28,6 +28,7 @@ public boolean isEmpty(){
2828
public int size(){
2929
return list.size();
3030
}
31+
3132
//迭代器
3233
public Iterator iterator(){
3334
return list.iterator();

‎group15/1511_714512544/src/com/coding/basic/Stack.java

Lines changed: 3 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,7 @@
11
package com.coding.basic;
22

33
import java.util.NoSuchElementException;
4-
//后进先出
4+
//LIFO
55
public class Stack {
66
private ArrayList elementData = new ArrayList(); //使用刚实现的ArrayList
77

@@ -12,13 +12,13 @@ public void push(Object o){
1212

1313
//出栈
1414
public Object pop(){
15-
if(elementData.size() == 0) throw new NoSuchElementException("堆栈下溢");
15+
if(elementData.size() == 0) throw new NoSuchElementException("Stack Underflow");
1616
return elementData.remove(elementData.size()-1);
1717
}
1818

1919
//栈顶元素
2020
public Object peek(){
21-
if(elementData.size() == 0) throw new NoSuchElementException("堆栈下溢");
21+
if(elementData.size() == 0) throw new NoSuchElementException("Stack Underflow");
2222
return elementData.get(elementData.size()-1);
2323
}
2424

@@ -32,7 +32,4 @@ public int size(){
3232
return elementData.size();
3333
}
3434

35-
36-
37-
3835
}

0 commit comments

Comments
 (0)