Skip to content

Commit d3b006b

Browse files
zavierzavier
authored
Merge pull request onlyliuxin#10 from lvxg/master
第一周
2 parents 676f50a + 62657a1 commit d3b006b

File tree

6 files changed

+417
-0
lines changed

6 files changed

+417
-0
lines changed

‎group01/819048836/lvxg2017/src/basic/BinaryTree.java

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
package basic;
2+
3+
public class BinaryTree {
4+
private BinaryTreeNode root;//¸ů˝Úľă
5+
6+
//˛ĺČë˛Ů×÷
7+
public void insert(int value){
8+
BinaryTreeNode newNode = new BinaryTreeNode(value);
9+
if(root==null){
10+
root = newNode;
11+
root.setLeft(null);
12+
root.setRight(null);
13+
}else{
14+
BinaryTreeNode currentNode = root;
15+
BinaryTreeNode parentNode;
16+
while(true)
17+
{
18+
parentNode = currentNode;
19+
//ÍůÓҡĹ
20+
if(newNode.getData()>currentNode.getData()){
21+
currentNode = currentNode.getRight();
22+
if(currentNode ==null){
23+
parentNode.setRight(newNode);
24+
return;
25+
}
26+
}else if(newNode.getData()<=currentNode.getData()){
27+
currentNode = currentNode.getLeft();
28+
if(currentNode ==null){
29+
parentNode.setLeft(newNode);
30+
return;
31+
}
32+
}
33+
34+
}
35+
36+
}
37+
38+
39+
}
40+
41+
}

‎group01/819048836/lvxg2017/src/basic/BinaryTreeNode.java

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
package basic;
2+
3+
//二叉树
4+
public class BinaryTreeNode {
5+
private int data;// 节点值
6+
private BinaryTreeNode left; //左子节点
7+
private BinaryTreeNode right;//右子节点
8+
public BinaryTreeNode(int data){
9+
this.data =data;
10+
this.left = null;
11+
this.right = null;
12+
}
13+
public void setDate(int data){
14+
this.data =data;
15+
}
16+
public int getData(){
17+
return data;
18+
}
19+
public BinaryTreeNode getLeft(){
20+
return left;
21+
}
22+
public BinaryTreeNode getRight(){
23+
return right;
24+
}
25+
public void setLeft(BinaryTreeNode left){
26+
this.left = left;
27+
}
28+
public void setRight(BinaryTreeNode right){
29+
this.right =right;
30+
}
31+
32+
33+
34+
}

‎group01/819048836/lvxg2017/src/basic/MyArrayList.java

Lines changed: 91 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,91 @@
1+
package basic;
2+
/**
3+
* arraylist，Linkedlist,栈，队列，二叉树，迭代器实现，一篇文章关于计算机组成原理 描述CPU，内存， 硬盘，指令之间的关系
4+
*
5+
* @author lvxg
6+
*
7+
*/
8+
public class MyArrayList {
9+
private Object[] element;
10+
private int size;
11+
private static final Object[] EMPTY = new Object[10];
12+
13+
public MyArrayList() {
14+
this.element = EMPTY;
15+
}
16+
17+
public boolean add(Object o) {
18+
// 如果数组没满
19+
if (size < element.length) {
20+
element[size] = o;
21+
size++;
22+
} else {
23+
// 数组扩容
24+
grow();
25+
element[size] = o;
26+
size++;
27+
}
28+
return true;
29+
}
30+
31+
// 根据索引添加数据
32+
public boolean add(int index, Object o) {
33+
rangeCheckForAdd(index);
34+
if (size < element.length + 1) {
35+
Object[] e = new Object[element.length+1];
36+
System.arraycopy(element, 0, e, 0, index);
37+
e[index] = o;
38+
System.arraycopy(element, index, e, index + 1, element.length-index);
39+
size++;
40+
}
41+
return true;
42+
}
43+
44+
public Object get(int index) {
45+
rangeCheck(index);
46+
return element[index];
47+
}
48+
49+
public Object remove(int index) {
50+
rangeCheck(index);
51+
Object oldValue = element[index];
52+
int numMoved = size - index-1;
53+
if(numMoved>0){
54+
System.arraycopy(element, index+1, element, index, numMoved);
55+
}
56+
element[--size] =null;
57+
return oldValue;
58+
}
59+
public int size() {
60+
return size;
61+
}
62+
private void rangeCheck(int index) {
63+
if (index >= size)
64+
throw new IndexOutOfBoundsException();
65+
}
66+
private void rangeCheckForAdd(int index) {
67+
if (index > size || index < 0) {
68+
throw new IndexOutOfBoundsException();
69+
}
70+
}
71+
72+
// 数组扩容方法
73+
private void grow() {
74+
Object[] e = new Object[size * 2];
75+
// 数组拷贝
76+
System.arraycopy(element, 0, e, 0, element.length);
77+
element = e;
78+
79+
}
80+
81+
public static void main(String[] args) {
82+
MyArrayList m = new MyArrayList();
83+
m.add("1");
84+
for (int i = 0; i < 10; i++) {
85+
m.add(i);
86+
}
87+
m.add(2, "123");
88+
m.remove(1);
89+
}
90+
91+
}

‎group01/819048836/lvxg2017/src/basic/MyLinkedList.java

Lines changed: 146 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,146 @@
1+
package basic;
2+
3+
import java.util.LinkedList;
4+
import java.util.Queue;
5+
6+
/**
7+
* 链表
8+
*
9+
* @author lvxg
10+
*
11+
*/
12+
public class MyLinkedList {
13+
// 头节点
14+
private Node first;
15+
// 尾节点
16+
private Node last;
17+
// 元素个数
18+
private int size = 0;
19+
20+
public boolean add(Object o) {
21+
linklast(o);
22+
return true;
23+
}
24+
/**
25+
* 根据索引插入节点
26+
* @param index
27+
* @param o
28+
*/
29+
public void add(int index, Object o) {
30+
// 判断index是否越界
31+
checkPositionIndex(index);
32+
if (index == size) {
33+
linklast(o);
34+
} else {
35+
final Node succ = node(index);
36+
final Node pred = succ.prev;
37+
Node newNode = new Node(o, pred, succ);
38+
// 如果前驱为空说明是头节点
39+
if (pred == null) {
40+
first = newNode;
41+
} else {
42+
pred.next = newNode;
43+
}
44+
size++;
45+
}
46+
}
47+
//根据索引删除节点
48+
@SuppressWarnings("unused")
49+
private Object remove(int index){
50+
Object x= unllink(node(index));
51+
return x;
52+
}
53+
//删除节点，无参
54+
@SuppressWarnings("unused")
55+
private Object remove(){
56+
Object x = unllink(node(size));
57+
return x;
58+
}
59+
60+
// 添加节点到链表末尾
61+
private void linklast(Object e) {
62+
final Node l = last;
63+
final Node newNode = new Node(e, null, l);
64+
last = newNode;
65+
if (l == null) {
66+
first = newNode;
67+
} else {
68+
l.next = newNode;
69+
}
70+
size++;
71+
72+
}
73+
74+
// 删除节点方法
75+
private Object unllink(Node x) {
76+
final Object element = x.data;
77+
final Node next = x.next;
78+
final Node prev = x.prev;
79+
// 前驱为空，表示删除的是头节点
80+
if (prev == null) {
81+
first = next;
82+
} else {
83+
prev.next = next;
84+
x.next = null;
85+
x.prev = null;
86+
}
87+
// 后继为空，表示删除的是尾节点
88+
if (next == null) {
89+
last = prev;
90+
x.next = null;
91+
}
92+
size--;
93+
x.data = null;
94+
return element;
95+
}
96+
97+
// 根据索引得到节点
98+
private Node node(int index) {
99+
if (index < (size >> 1)) { // 如果插入位置在前半段？？？
100+
Node x = first;
101+
for (int i = 0; i < index; i++) {
102+
x = x.next;
103+
}
104+
return x;
105+
} else {
106+
Node x = last;
107+
for (int i = size - 1; i > index; i--) {
108+
x = x.prev;
109+
}
110+
return x;
111+
}
112+
}
113+
114+
private static class Node {
115+
Object data; // 数据域
116+
Node next;// 后继
117+
Node prev;// 前驱
118+
119+
public Node(Object o, Node n, Node p) {
120+
this.data = o;
121+
this.prev = p;
122+
this.next = n;
123+
}
124+
}
125+
126+
private void checkPositionIndex(int index) {
127+
if (!isPositionIndex(index)) {
128+
throw new IndexOutOfBoundsException();
129+
}
130+
}
131+
132+
private boolean isPositionIndex(int index) {
133+
return index >= 0 && index <= size;
134+
}
135+
136+
public static void main(String[] args) {
137+
MyLinkedList l = new MyLinkedList();
138+
l.add("1");
139+
l.add("2");
140+
l.add("3");
141+
l.add(2, "4");
142+
l.remove();
143+
l.remove(1);
144+
}
145+
146+
}

‎group01/819048836/lvxg2017/src/basic/Queue.java

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
package basic;
2+
3+
public class Queue {
4+
// 头节点
5+
private Node first;
6+
// 尾节点
7+
private Node last;
8+
// 元素个数
9+
private int size = 0;
10+
11+
// 入列
12+
private void enQueue(Object o) {
13+
final Node f = first;
14+
final Node newNode = new Node(o, f, null);
15+
f.prev = newNode;
16+
}
17+
public int size(){
18+
return size;
19+
}
20+
public boolean isEmpty(){
21+
return size>=0;
22+
}
23+
// 出列
24+
private Object deQueue() {
25+
final Node l = last;
26+
final Node p = l.prev;
27+
last = p;
28+
p.next = null;
29+
return l;
30+
}
31+
32+
private static class Node {
33+
Object data; // 数据域
34+
Node next;// 后继
35+
Node prev;// 前驱
36+
37+
public Node(Object o, Node n, Node p) {
38+
this.data = o;
39+
this.prev = p;
40+
this.next = n;
41+
}
42+
}
43+
44+
}

0 commit comments

Comments
 (0)