Skip to content

Commit c8ea7d6

Browse files
GreastateGreastate
authored
Merge pull request onlyliuxin#11 from wayss000/master
提交数据结构
2 parents 2e62dee + ccac23d commit c8ea7d6

File tree

7 files changed

+270
-54
lines changed

7 files changed

+270
-54
lines changed

‎group08/1144989424/firstPractice/src/basic/BinaryTreeNode.java

Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
package basic;
2+
3+
/**
4+
* 二叉树的数据结构
5+
* @author Wayss
6+
* 2017-02-25
7+
*/
8+
9+
public class BinaryTreeNode {
10+
11+
private Object data;
12+
private BinaryTreeNode left;
13+
private BinaryTreeNode right;
14+
15+
public BinaryTreeNode(){
16+
17+
}
18+
19+
public BinaryTreeNode(Integer val){
20+
data = val;
21+
left = null;
22+
right = null;
23+
}
24+
25+
26+
public Object getData() {
27+
return data;
28+
}
29+
public void setData(Object data) {
30+
this.data = data;
31+
}
32+
public BinaryTreeNode getLeft() {
33+
return left;
34+
}
35+
public void setLeft(BinaryTreeNode left) {
36+
this.left = left;
37+
}
38+
public BinaryTreeNode getRight() {
39+
return right;
40+
}
41+
public void setRight(BinaryTreeNode right) {
42+
this.right = right;
43+
}
44+
45+
public BinaryTreeNode insert(Object o){
46+
return null;
47+
}
48+
49+
}

‎group08/1144989424/firstPractice/src/basic/MyArrayList.java

Lines changed: 31 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,11 @@
11
package basic;
22

3+
/**
4+
* 我的ArrayList实现
5+
* @author Wayss
6+
* 2017-02-22
7+
*/
8+
39
public class MyArrayList implements MyList {
410

511
private int size = 0;
@@ -26,7 +32,7 @@ public void add(Object o){
2632
*/
2733
public void add(int index, Object o){
2834
int length = elementData.length;
29-
//0.先对index的值进行判断，不能小于0，且不能大于size
35+
//0.先对index的值进行判断，小于0，或者，大于size，越界
3036
if(index < 0 || index > size){
3137
throw new IndexOutOfBoundsException("插入的下标越界了:"+"插入的下标为："+index+"集合大小为："+size);
3238
}
@@ -43,15 +49,37 @@ public void add(int index, Object o){
4349
}
4450

4551
public Object get(int index){
46-
return null;
52+
int length = elementData.length;
53+
//0.先对index的值进行判断，小于0，或者，大于等于size，便越界
54+
if(index < 0 || index >= size){
55+
throw new IndexOutOfBoundsException("插入的下标越界了:"+"插入的下标为："+index+"集合大小为："+size);
56+
}
57+
//2.拿出index位置的值，
58+
Object o = elementData[index];
59+
60+
return o;
4761
}
4862

4963
public Object remove(int index){
64+
//remove 前两步的逻辑和get方法相同
65+
int length = elementData.length;
66+
//0.先对index的值进行判断，小于0，或者，大于等于size，便越界
67+
if(index < 0 || index >= size){
68+
throw new IndexOutOfBoundsException("插入的下标越界了:"+"插入的下标为："+index+"集合大小为："+size);
69+
}
70+
//2.拿出index位置的值，
71+
Object o = elementData[index];
72+
73+
//3.删除index位置的值，之后的值，向前移动。
74+
for(int i = index; i < size-1; i++){
75+
elementData[i] = elementData[i+1];
76+
}
77+
size--;
5078
return null;
5179
}
5280

5381
public int size(){
54-
return -1;
82+
return size;
5583
}
5684

5785
public MyIterator iterator(){

‎group08/1144989424/firstPractice/src/basic/MyBinaryTreeNode.java

Lines changed: 0 additions & 32 deletions
This file was deleted.

‎group08/1144989424/firstPractice/src/basic/MyLinkedList.java

Lines changed: 78 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -1,46 +1,113 @@
11
package basic;
22

3+
/**
4+
* 实现LinkedList基本功能
5+
* @author Wayss
6+
* 2017-02-23
7+
*/
8+
39
public class MyLinkedList implements MyList {
410

511
private Node head;
12+
private int size = 0;
613

714
public void add(Object o){
8-
15+
Node n = new Node(o);
16+
head.next = n;
17+
size++;
918
}
1019
public void add(int index , Object o){
11-
20+
//1.index校验
21+
if(index < 0 || index > size){
22+
throw new IndexOutOfBoundsException("插入的下标越界了:"+"插入的下标为："+index+"集合大小为："+size);
23+
}
24+
//2. 查找index位置的前一个节点
25+
//tempNode为当前链表的第一个节点
26+
Node tempNode = head.next;
27+
for(int i = 0; i < index - 1 ; i++){
28+
tempNode = tempNode.next;
29+
}
30+
Node behindNode = tempNode.next;
31+
Node insertNode = new Node(o);
32+
tempNode.next = insertNode;
33+
insertNode.next = behindNode;
34+
size++;
1235
}
1336
public Object get(int index){
14-
return null;
37+
//1.index校验
38+
if(index < 0 || index > size){
39+
throw new IndexOutOfBoundsException("插入的下标越界了:"+"插入的下标为："+index+"集合大小为："+size);
40+
}
41+
//2. 查找当前节点
42+
Node tempNode = head.next;
43+
for(int i = 0; i < index; i++){
44+
tempNode = tempNode.next;
45+
}
46+
return tempNode.data;
1547
}
1648
public Object remove(int index){
17-
return null;
49+
//1.index校验
50+
if(index < 0 || index > size){
51+
throw new IndexOutOfBoundsException("插入的下标越界了:"+"插入的下标为："+index+"集合大小为："+size);
52+
}
53+
//2. 查找当前节点的上一个节点
54+
Node tempNode = head.next;
55+
for(int i = 0; i < index - 1; i++){
56+
tempNode = tempNode.next;
57+
}
58+
Node deleteNode = tempNode.next;
59+
Node behideNode = tempNode.next.next;
60+
tempNode.next = behideNode;
61+
size--;
62+
return deleteNode.data;
1863
}
1964

2065
public int size(){
21-
return -1;
66+
return size;
2267
}
2368

2469
public void addFirst(Object o){
25-
70+
Node insertNode = new Node(o);
71+
insertNode.next = head.next;
72+
head.next = insertNode;
73+
size++;
2674
}
2775
public void addLast(Object o){
28-
76+
Node insertNode = new Node(o);
77+
Node tempNode = head.next;
78+
for(int i = 0; i < size; i++){
79+
tempNode = tempNode.next;
80+
}
81+
tempNode.next = insertNode;
82+
size++;
2983
}
3084
public Object removeFirst(){
31-
return null;
85+
Node firstNode = head.next;
86+
head = firstNode.next;
87+
size--;
88+
return firstNode;
3289
}
3390
public Object removeLast(){
34-
return null;
91+
Node tempNode = head.next;
92+
//1.移除需要找到最后一个点的前一个点
93+
for(int i = 0; i < size - 1; i++){
94+
tempNode = tempNode.next;
95+
}
96+
Node deleteNode = tempNode.next;
97+
tempNode.next = null;
98+
size--;
99+
return deleteNode;
35100
}
36101
public MyIterator iterator(){
37102
return null;
38103
}
39104

40105

41-
private static class Node{
106+
private static class Node{
42107
Object data;
43108
Node next;
44-
109+
public Node(Object data){
110+
this.data = data;
111+
}
45112
}
46113
}

‎group08/1144989424/firstPractice/src/basic/MyQueue.java

Lines changed: 15 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1,19 +1,31 @@
11
package basic;
22

3+
/**
4+
* 实现队列
5+
* @author Wayss
6+
* 2017-02-25
7+
*/
8+
39
public class MyQueue {
410

5-
public void enQueue(Object o){
11+
MyLinkedList linkList = new MyLinkedList();
12+
13+
public void enQueue(Object o){
14+
linkList.addLast(o);
615
}
716

817
public Object deQueue(){
9-
return null;
18+
return linkList.removeFirst();
1019
}
1120

1221
public boolean isEmpty(){
22+
if(linkList.size() == 0){
23+
return true;
24+
}
1325
return false;
1426
}
1527

1628
public int size(){
17-
return -1;
29+
return linkList.size();
1830
}
1931
}

‎group08/1144989424/firstPractice/src/basic/MySortBinaryTree.java

Lines changed: 81 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,81 @@
1+
package basic;
2+
3+
import java.util.Comparator;
4+
5+
/**
6+
* 实现二叉排序树，使左节点的值，始终父节点小，右节点的值，始终比父节点大
7+
* @author Wayss
8+
* 2017-02-25
9+
*/
10+
11+
public class MySortBinaryTree {
12+
13+
public BinaryTreeNode root = new BinaryTreeNode();
14+
15+
/**
16+
* 1. 添加时，先判断与root节点值的大小
17+
* 2. insert的值小于root的值，则插入到root的左边。
18+
* 3. insert的值大于root的值，则插入到root的右边。
19+
* PS:目前只支持Integer类型的对象插入
20+
* @param val
21+
*/
22+
public void add(Integer val){
23+
BinaryTreeNode treeNode = new BinaryTreeNode(val);
24+
insert(root, treeNode);
25+
}
26+
27+
private void insert(BinaryTreeNode node, BinaryTreeNode insertNode){
28+
29+
int result = compare((Integer)insertNode.getData(),(Integer)node.getData());
30+
31+
if(0 == result){
32+
//相等的话，当重复数据，不插了.呵呵
33+
}
34+
//insert的值小于root的值，则插入到root的左边。
35+
//如果左节点有值，则递归
36+
if(-1 == result){
37+
if(node.getLeft() != null){
38+
insert(node.getLeft(), insertNode);
39+
}else{
40+
node.setLeft(insertNode);
41+
}
42+
}
43+
//insert的值大于root的值，则插入到root的右边。
44+
if(1 == result){
45+
if(node.getRight() != null){
46+
insert(node.getRight(), insertNode);
47+
}else{
48+
node.setRight(insertNode);
49+
}
50+
}
51+
}
52+
53+
public MyArrayList getValue(){
54+
MyArrayList malist = new MyArrayList();
55+
getTreeValue(root,malist);
56+
return malist;
57+
}
58+
59+
private void getTreeValue(BinaryTreeNode node,MyArrayList list){
60+
//遍历左子数
61+
if(node.getLeft() != null){
62+
getTreeValue(node.getLeft(),list);
63+
}
64+
list.add(node.getData());
65+
//遍历右子数
66+
if(node.getRight() != null){
67+
getTreeValue(node.getRight(),list);
68+
}
69+
}
70+
71+
public static int compare(Integer i1, Integer i2){
72+
if(i1 < i2){
73+
return -1;
74+
}else if(i1 == i2){
75+
return 0;
76+
}else {
77+
return 1;
78+
}
79+
}
80+
81+
}

0 commit comments

Comments
 (0)