Skip to content

Commit 475ec74

Browse files
844028312844028312
authored
Merge pull request onlyliuxin#21 from wubingyang/master
作业
2 parents e62c2fc + cf8ff38 commit 475ec74

File tree

11 files changed

+447
-0
lines changed

11 files changed

+447
-0
lines changed

‎group04/120549547/base/buil.bat

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,5 @@
1+
javac -sourcepath src -d classes -encoding utf-8 src\com\coding\basic\*.java
2+
3+
java -cp classes com.coding.basic.Main
4+
5+
pause

‎group04/120549547/base/src/com/coding/basic/ArrayList.java

Lines changed: 93 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,93 @@
1+
package com.coding.basic;
2+
import java.util.Arrays;
3+
4+
public class ArrayList implements List {
5+
/*默认数组容量*/
6+
public static final int DEFAULT_CAPCATITY = 10;
7+
8+
/*数组元素个数*/
9+
private int size;
10+
11+
private Object[] elementData;
12+
13+
public ArrayList(){
14+
this(DEFAULT_CAPCATITY);
15+
}
16+
17+
public ArrayList(int capacity){
18+
if (capacity<0 || capacity>Integer.MAX_VALUE)
19+
throw new IllegalArgumentException("非法容量： " + capacity);
20+
elementData = new Object[capacity];
21+
}
22+
23+
24+
public void add(Object o){
25+
/*判断是否需要扩容*/
26+
ensureCapacity(size + 1);
27+
elementData[size++] = o;
28+
}
29+
30+
public void add(int index, Object o){
31+
checkIndex(index);
32+
/*判断是否需要扩容*/
33+
ensureCapacity(size + 1);
34+
/*将index->size的元素依次向右移一个位置*/
35+
System.arraycopy(elementData, index, elementData, index+1, size-index);
36+
/*插入o的值*/
37+
elementData[index] = o;
38+
size++;
39+
}
40+
41+
42+
public Object get(int index){
43+
44+
checkIndex(index);
45+
return elementData[index];
46+
}
47+
48+
public Object remove(int index){
49+
50+
checkIndex(index);
51+
Object value = elementData[index];
52+
/*将index+1 -> size的元素依次向左移一个位置*/
53+
System.arraycopy(elementData,index+1, elementData, index, size-index-1);
54+
elementData[--size]=null; //释放最后一个元素,同时size减一；
55+
return value;
56+
}
57+
58+
public int size(){
59+
return this.size;
60+
}
61+
62+
public Iterator iterator(){
63+
return null;
64+
}
65+
/* 确认容量是否足够，也可以直接调用手动扩容*/
66+
public void ensureCapacity(int minCapacity){
67+
int oldCapacity = elementData.length;
68+
/*容量不足需要扩容*/
69+
if(oldCapacity < minCapacity){
70+
int newCapacity = oldCapacity * 2; //扩大2倍
71+
if (newCapacity < minCapacity){
72+
newCapacity = minCapacity; //扩容后仍不足,取最大值
73+
}
74+
System.out.println("数据扩容至： " + newCapacity);
75+
elementData = Arrays.copyOf(elementData, newCapacity);
76+
}
77+
78+
}
79+
80+
private void checkIndex(int index){
81+
if (index<0 || index>= size)
82+
throw new IndexOutOfBoundsException ("index非法: " + index);
83+
}
84+
@Override
85+
public String toString(){
86+
87+
StringBuffer sb = new StringBuffer("");
88+
for(int i=0; i<size; i++){
89+
sb.append("["+ i +"]"+ elementData[i] + "-> ");
90+
}
91+
return sb.toString();
92+
}
93+
}

‎group04/120549547/base/src/com/coding/basic/BinaryTreeNode.java

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
package com.coding.basic;
2+
3+
public class BinaryTreeNode {
4+
5+
private Object data;
6+
private BinaryTreeNode left;
7+
private BinaryTreeNode right;
8+
9+
public Object getData() {
10+
return data;
11+
}
12+
public void setData(Object 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 insert(Object o){
29+
return null;
30+
}
31+
32+
}

‎group04/120549547/base/src/com/coding/basic/Iterator.java

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

‎group04/120549547/base/src/com/coding/basic/LinkedList.java

Lines changed: 127 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,127 @@
1+
package com.coding.basic;
2+
3+
public class LinkedList implements List {
4+
5+
private Node head;
6+
private int size;
7+
/*创建一个带头节点的单链表*/
8+
public LinkedList(){
9+
head = new Node(null);
10+
}
11+
12+
/*添加一个元素(尾插法)*/
13+
public void add(Object o){
14+
15+
Node node = new Node(o);
16+
Node pos = head;
17+
//找到最后一个元素位置
18+
while(pos.next != null){
19+
pos = pos.next;
20+
}
21+
pos.next = node;
22+
size++;
23+
24+
}
25+
26+
/*在index位置插入*/
27+
public void add(int index , Object o){
28+
//判断索引是否合法
29+
checkIndex(index);
30+
Node node = new Node(o);
31+
Node pos = head;
32+
//找到插入位置
33+
while(index-- != 0){
34+
pos = pos.next;
35+
}
36+
node.next = pos.next;
37+
pos.next = node;
38+
size++;
39+
40+
}
41+
public Object get(int index){
42+
checkIndex(index);
43+
if(this.isEmpty()){
44+
throw new IllegalArgumentException ("链表为空");
45+
}
46+
Node pos = head.next; //pos指向要获取的节点
47+
while(index-- !=0){
48+
pos = pos.next;
49+
}
50+
51+
return pos.data;
52+
}
53+
public Object remove(int index){
54+
checkIndex(index);
55+
if(this.isEmpty()){
56+
throw new IllegalArgumentException ("链表为空");
57+
}
58+
59+
Node pos = head; //pos指向要删除的前一个结点
60+
while(index-- != 0){
61+
pos = pos.next;
62+
}
63+
Node value = pos.next; //要删除的节点
64+
pos.next = value.next;
65+
size--;
66+
return value.data;
67+
68+
69+
}
70+
71+
public int size(){
72+
return size;
73+
}
74+
75+
public void addFirst(Object o){
76+
77+
}
78+
public void addLast(Object o){
79+
this.add(o);
80+
}
81+
public Object removeFirst(){
82+
if(this.isEmpty()){
83+
throw new IllegalArgumentException ("链表为空");
84+
}
85+
return remove(0);
86+
}
87+
public Object removeLast(){
88+
if(this.isEmpty()){
89+
throw new IllegalArgumentException ("链表为空");
90+
}
91+
return remove(size-1);
92+
}
93+
94+
public boolean isEmpty(){
95+
return size == 0;
96+
}
97+
public Iterator iterator(){
98+
return null;
99+
}
100+
101+
private void checkIndex(int index){
102+
if (index<0 || index>=size ){
103+
throw new IllegalArgumentException ("index不合法: " + index );
104+
}
105+
}
106+
107+
@Override
108+
public String toString(){
109+
110+
StringBuffer sb = new StringBuffer("");
111+
for(int i=0; i<size; i++){
112+
sb.append( this.get(i) + "-> ");
113+
}
114+
return sb.toString();
115+
}
116+
117+
private static class Node{
118+
public Object data;
119+
public Node next;
120+
121+
public Node(Object data){
122+
this.data = data;
123+
this.next = null;
124+
}
125+
126+
}
127+
}

‎group04/120549547/base/src/com/coding/basic/List.java

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,10 @@
1+
package com.coding.basic;
2+
3+
public interface List {
4+
5+
public void add(Object o);
6+
public void add(int index, Object o);
7+
public Object get(int index);
8+
public Object remove(int index);
9+
public int size();
10+
}

‎group04/120549547/base/src/com/coding/basic/Main.java

Lines changed: 85 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,85 @@
1+
package com.coding.basic;
2+
import com.coding.basic.*;
3+
4+
class Main{
5+
6+
public static void main(String[] args){
7+
System.out.println("数组测试开始");
8+
ArrayListTest();
9+
System.out.println("----------------分割线----------------");
10+
System.out.println("链表测试开始");
11+
LinkedListTest();
12+
System.out.println("----------------分割线----------------");
13+
System.out.println("栈测试开始");
14+
StatckTest();
15+
System.out.println("----------------分割线----------------");
16+
System.out.println("队测试开始");
17+
QueueTest();
18+
}
19+
20+
public static void ArrayListTest(){
21+
ArrayList list = new ArrayList(2);
22+
list.add("HelloBobi0");
23+
list.add("HelloBobi1");
24+
list.add("HelloBobi2");
25+
list.add("HelloBobi3");
26+
list.add("HelloBobi4");
27+
list.add("HelloBobi5");
28+
System.out.println((String)list.get(0));
29+
System.out.println((String)list.get(4));
30+
list.add(3, "Hei Man");
31+
list.remove(5);
32+
System.out.println(list);
33+
System.out.println("size:=" + list.size());
34+
}
35+
36+
public static void LinkedListTest(){
37+
LinkedList ll = new LinkedList();
38+
39+
40+
ll.add("SingleDog0");
41+
ll.add("SingleDog1");
42+
ll.add("SingleDog2");
43+
ll.add("SingleDog3");
44+
ll.add("SingleDog4");
45+
ll.add("SingleDog5");
46+
47+
System.out.println((String)(ll.get(1)));
48+
System.out.println(ll);
49+
System.out.println("size:=" + ll.size());
50+
ll.remove(0);
51+
ll.removeFirst();
52+
ll.removeLast();
53+
System.out.println(ll);
54+
}
55+
56+
public static void StatckTest(){
57+
Stack stack = new Stack();
58+
stack.push("虾师傅0");
59+
stack.push("虾师傅1");
60+
stack.push("虾师傅2");
61+
stack.push("虾师傅3");
62+
stack.push("虾师傅4");
63+
64+
stack.pop();
65+
System.out.println(stack.peek());
66+
System.out.println(stack);
67+
68+
}
69+
public static void QueueTest(){
70+
Queue queue = new Queue();
71+
queue.enQueue("龙师傅0");
72+
queue.enQueue("龙师傅1");
73+
queue.enQueue("龙师傅2");
74+
queue.enQueue("龙师傅3");
75+
queue.enQueue("龙师傅4");
76+
77+
System.out.println(queue.deQueue());
78+
System.out.println(queue.deQueue());
79+
System.out.println(queue.deQueue());
80+
System.out.println(queue.deQueue());
81+
System.out.println(queue.size());
82+
83+
84+
}
85+
}

‎group04/120549547/base/src/com/coding/basic/Queue.java

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
package com.coding.basic;
2+
import com.coding.basic.*;
3+
public class Queue {
4+
private LinkedList list;
5+
6+
public Queue(){
7+
list = new LinkedList();
8+
}
9+
/*入队*/
10+
public void enQueue(Object o){
11+
list.addLast(o);
12+
}
13+
14+
/*出队*/
15+
public Object deQueue(){
16+
if (isEmpty()){
17+
System.out.println("队空");
18+
}
19+
return list.removeFirst();
20+
}
21+
22+
public boolean isEmpty(){
23+
return list.isEmpty();
24+
}
25+
26+
public int size(){
27+
return list.size();
28+
}
29+
}

0 commit comments

Comments
 (0)