Skip to content

Commit 6edb4f1

Browse files
author
wa122as
committed
基本数据结构作业
1 parent 0847c96 commit 6edb4f1

File tree

8 files changed

+563
-0
lines changed

8 files changed

+563
-0
lines changed

‎group15/1521_653895972/src/com/coding/basic/ArrayList.java

Lines changed: 81 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,81 @@
1+
package com.coding.basic;
2+
3+
import java.util.Arrays;
4+
import java.util.NoSuchElementException;
5+
6+
public class ArrayList implements List {
7+
//实例化空数组 不用每次都new
8+
private static final Object[] Empty_elementData = {};
9+
private int size = 0;
10+
11+
private Object[] elementData = new Object[100];
12+
13+
public ArrayList() {
14+
this.elementData = Empty_elementData;
15+
}
16+
//检查是否越界
17+
private void checkLenght(int index){
18+
if (index - size > 0)
19+
throw new IndexOutOfBoundsException();
20+
}
21+
//增加数组容量
22+
private void kuorong(){
23+
elementData = Arrays.copyOf(elementData, size + 1);
24+
}
25+
public void add(Object o) {
26+
kuorong();
27+
elementData[size++] = o;
28+
}
29+
30+
public void add(int index, Object o) {
31+
kuorong();
32+
System.arraycopy(elementData, index, elementData, index + 1, size - index);
33+
elementData[index] = o;
34+
size++;
35+
}
36+
37+
public Object get(int index) {
38+
checkLenght(index);
39+
return elementData[index];
40+
}
41+
42+
public Object remove(int index) {
43+
checkLenght(index);
44+
Object element =elementData[index];
45+
int movesize=size-index-1;
46+
System.arraycopy(elementData,index+1,elementData,index,movesize);
47+
elementData[--size]=null;
48+
return element;
49+
}
50+
51+
public int size() {
52+
return size;
53+
}
54+
55+
public Iterator iterator() {
56+
return new ArrayItr();
57+
}
58+
private class ArrayItr implements Iterator{
59+
int cursor;//游标
60+
@Override
61+
public boolean hasNext() {
62+
return cursor!=size;
63+
}
64+
65+
@Override
66+
public Object next() {
67+
int i=cursor;
68+
if (i>size)throw new NoSuchElementException();
69+
Object [] newElementData = ArrayList.this.elementData;
70+
if (i>newElementData.length)throw new IndexOutOfBoundsException();
71+
cursor=i+1;
72+
return newElementData[i];
73+
}
74+
}
75+
76+
@Override
77+
public String toString() {
78+
Object[] s = Arrays.copyOf(elementData,size);
79+
return Arrays.toString(s);
80+
}
81+
}

‎group15/1521_653895972/src/com/coding/basic/BasicTest.java

Lines changed: 150 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,150 @@
1+
package com.coding.basic;
2+
3+
import org.junit.Assert;
4+
import org.junit.Test;
5+
6+
/**
7+
* Created by wanc on 2017/2/21.
8+
*/
9+
public class BasicTest {
10+
11+
@Test
12+
public void test() {
13+
//测试
14+
// testArrayList();
15+
// testLinkedList();
16+
// testBinaryTreeNode();
17+
// testStack();
18+
testQueue();
19+
}
20+
21+
22+
public void testQueue(){
23+
Queue queue = new Queue();
24+
queue.enQueue("S");
25+
queue.enQueue("Y");
26+
queue.enQueue(5);
27+
System.out.println(queue);
28+
System.out.println("queue.size()="+queue.size());
29+
System.out.println("queue.deQueue()="+queue.deQueue());
30+
System.out.println(queue);
31+
System.out.println("queue.isEmpty()="+queue.isEmpty());
32+
System.out.println(queue);
33+
}
34+
public void testStack(){
35+
Stack stack = new Stack();
36+
stack.push("S");
37+
stack.push("Y");
38+
stack.push(5);
39+
System.out.println("stack.size()="+stack.size());
40+
System.out.println("stack.peek()="+stack.peek());
41+
System.out.println(stack);
42+
System.out.println("stack.isEmpty()="+stack.isEmpty());
43+
stack.pop();
44+
System.out.println(stack);
45+
}
46+
public void testBinaryTreeNode(){
47+
System.out.println("-------------------BinaryTreeNode 测试开始-------------------");
48+
System.out.println("new 一个实例");
49+
BinaryTreeNode root = new BinaryTreeNode();
50+
root.insert(5);
51+
root.insert(6);
52+
root.insert(9);
53+
root.insert(3);
54+
root.insert(3);
55+
root.insert(2);
56+
root.insert(10);
57+
System.out.println(root);
58+
System.out.println("-------------------LinkedList 测试结束-------------------");
59+
}
60+
public void testLinkedList() {
61+
System.out.println("-------------------LinkedList 测试开始-------------------");
62+
System.out.println("new 一个实例");
63+
LinkedList list = new LinkedList();
64+
System.out.println("1.add(\"A\") 添加元素----A");
65+
list.add("A");
66+
System.out.println("结果："+list);
67+
System.out.println();
68+
System.out.println("2.add(\"B\") 添加元素----B");
69+
list.add("B");
70+
System.out.println("结果："+list);
71+
System.out.println();
72+
System.out.println("3.add(3) 添加元素----3");
73+
list.add(3);
74+
System.out.println("结果："+list);
75+
System.out.println();
76+
System.out.println("4.add(1, 3) 在下标1插入元素----3");
77+
list.add(1, 3);
78+
System.out.println("结果："+list);
79+
System.out.println();
80+
System.out.println("5.add(3, 6) 在下标3插入元素----6");
81+
list.add(3, 6);
82+
System.out.println("结果："+list);
83+
System.out.println();
84+
System.out.println("6.remove(0) 删除下标0元素");
85+
list.remove(0);
86+
System.out.println("结果："+list);
87+
System.out.println();
88+
System.out.println("7.size() 获取size");
89+
System.out.println("结果："+list.size());
90+
System.out.println();
91+
System.out.println("8.addFirst(\"F\") 在首位前插入F");
92+
list.addFirst("F");
93+
System.out.println("结果："+list);
94+
System.out.println("9.addLast(\"K\") 在末位前插入K");
95+
list.addLast("K");
96+
System.out.println("结果："+list);
97+
System.out.println("10.removeFirst() 删除首位");
98+
list.removeFirst();
99+
System.out.println("结果："+list);
100+
System.out.println("11.removeLast() 删除末尾");
101+
list.removeLast();
102+
System.out.println("结果："+list);
103+
System.out.println();
104+
System.out.println("12.迭代器");
105+
Iterator i = list.iterator();
106+
while (i.hasNext()){
107+
System.out.println(i.next());
108+
}
109+
System.out.println("-------------------LinkedList 测试结束-------------------");
110+
}
111+
public void testArrayList() {
112+
System.out.println("-------------------ArrayList 测试开始-------------------");
113+
System.out.println("new 一个实例");
114+
ArrayList list = new ArrayList();
115+
System.out.println("1.添加元素----A");
116+
list.add("A");
117+
Assert.assertEquals(list.get(0),"A");
118+
System.out.println("结果："+list);
119+
System.out.println();
120+
System.out.println("2.添加元素----B");
121+
list.add("B");
122+
System.out.println("结果："+list);
123+
System.out.println();
124+
System.out.println("3.添加元素----3");
125+
list.add(3);
126+
System.out.println("结果："+list);
127+
System.out.println();
128+
System.out.println("4.在下标1插入元素----3");
129+
list.add(1, 3);
130+
System.out.println("结果："+list);
131+
System.out.println();
132+
System.out.println("5.在下标3插入元素----6");
133+
list.add(3, 6);
134+
System.out.println("结果："+list);
135+
System.out.println();
136+
System.out.println("6.删除下标0元素");
137+
list.remove(0);
138+
System.out.println("结果："+list);
139+
System.out.println();
140+
System.out.println("7.获取size");
141+
System.out.println("结果："+list.size());
142+
System.out.println();
143+
System.out.println("8.迭代器");
144+
Iterator i = list.iterator();
145+
while (i.hasNext()){
146+
System.out.println(i.next());
147+
}
148+
System.out.println("-------------------ArrayList 测试结束-------------------");
149+
}
150+
}

‎group15/1521_653895972/src/com/coding/basic/BinaryTreeNode.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+
3+
/**
4+
* 实现二叉树
5+
* left总比父节点小
6+
* right总比父节点大
7+
*/
8+
public class BinaryTreeNode {
9+
private Node root;
10+
private int size = 0;
11+
12+
public void insert(int data) {
13+
final Node newNode = new Node(data);
14+
if (root == null) {
15+
root = newNode;
16+
} else {
17+
Node current = root;
18+
while (true) {
19+
Node parent = current;
20+
if (data < current.data) {//left
21+
current = current.left;
22+
if (current == null) {
23+
parent.left = newNode;
24+
return;
25+
}
26+
} else {//right
27+
current = current.right;
28+
if (current == null) {
29+
parent.right = newNode;
30+
return;
31+
}
32+
}
33+
}
34+
}
35+
size++;
36+
}
37+
38+
39+
//先序遍历
40+
private String preTraverse(Node node) {
41+
if (node == null)
42+
return "";
43+
else
44+
return node.data + preJointComma(preTraverse(node.left)) + preJointComma(preTraverse(node.right));
45+
}
46+
//中序遍历
47+
private String midTraverse(Node node) {
48+
if (node == null)
49+
return "";
50+
else
51+
return midTraverse(node.left)+" "+node.data+" " +midTraverse(node.right);
52+
}
53+
//后序遍历
54+
private String posTraverse(Node node) {
55+
if (node == null)
56+
return "";
57+
else
58+
return posTraverse(node.left)+" " +posTraverse(node.right)+" "+node.data;
59+
}
60+
61+
private String preJointComma(String str) {
62+
return str == "" ? "" : "," + str;
63+
}
64+
65+
public int size() {
66+
return size;
67+
}
68+
69+
@Override
70+
public String toString() {
71+
return "["+midTraverse(root)+"]";
72+
}
73+
74+
private static class Node {
75+
int data;
76+
Node left;
77+
Node right;
78+
79+
Node(int data) {
80+
this.data = data;
81+
this.left = null;
82+
this.right = null;
83+
}
84+
}
85+
}

‎group15/1521_653895972/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+
}

0 commit comments

Comments
 (0)