Skip to content

Commit ab88916

Browse files
zhijiaxinyuzhijiaxinyu
authored
Merge pull request onlyliuxin#6 from shixin-23/master
数据结构-第1次作业
2 parents c4a3bee + 234c38a commit ab88916

File tree

15 files changed

+635
-0
lines changed

15 files changed

+635
-0
lines changed

‎group10/353261578/.classpath

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,8 @@
1+
<?xml version="1.0" encoding="UTF-8"?>
2+
<classpath>
3+
<classpathentry kind="src" path="src"/>
4+
<classpathentry kind="src" path="test"/>
5+
<classpathentry kind="con" path="org.eclipse.jdt.launching.JRE_CONTAINER"/>
6+
<classpathentry kind="con" path="org.eclipse.jdt.junit.JUNIT_CONTAINER/4"/>
7+
<classpathentry kind="output" path="bin"/>
8+
</classpath>

‎group10/353261578/.gitignore

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1 @@
1+
/bin/

‎group10/353261578/.project

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
<?xml version="1.0" encoding="UTF-8"?>
2+
<projectDescription>
3+
<name>353261578Learning</name>
4+
<comment></comment>
5+
<projects>
6+
</projects>
7+
<buildSpec>
8+
<buildCommand>
9+
<name>org.eclipse.jdt.core.javabuilder</name>
10+
<arguments>
11+
</arguments>
12+
</buildCommand>
13+
</buildSpec>
14+
<natures>
15+
<nature>org.eclipse.jdt.core.javanature</nature>
16+
</natures>
17+
</projectDescription>

‎group10/353261578/src/com/sx/structures/BinaryNode.java

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
package com.sx.structures;
2+
3+
public class BinaryNode implements Comparable<BinaryNode>{
4+
private Object data;
5+
private BinaryNode left;
6+
private BinaryNode right;
7+
8+
public BinaryNode() {
9+
}
10+
public BinaryNode(Object o){
11+
data = o;
12+
left = null;
13+
right = null;
14+
}
15+
16+
public Object getData() {
17+
return data;
18+
}
19+
public void setData(Object data) {
20+
this.data = data;
21+
}
22+
public BinaryNode getLeft() {
23+
return left;
24+
}
25+
public void setLeft(BinaryNode left) {
26+
this.left = left;
27+
}
28+
public BinaryNode getRight() {
29+
return right;
30+
}
31+
public void setRight(BinaryNode right) {
32+
this.right = right;
33+
}
34+
@Override
35+
public int compareTo(BinaryNode o) {
36+
Integer to = (Integer)this.data;
37+
Integer co = (Integer)o.data;
38+
if(to<co)
39+
return -1;
40+
if(to>co)
41+
return 1;
42+
return 0;
43+
}
44+
}

‎group10/353261578/src/com/sx/structures/BinaryTree.java

Lines changed: 74 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,74 @@
1+
package com.sx.structures;
2+
3+
public class BinaryTree {
4+
5+
private BinaryNode root;
6+
7+
public BinaryTree(Object o) {
8+
root = new BinaryNode(o);
9+
}
10+
11+
public void insert(Object o) {
12+
BinaryNode node = new BinaryNode(o);
13+
insert(root, node);
14+
}
15+
16+
private void insert(BinaryNode root, BinaryNode node) {
17+
if (node.compareTo(root) > 0) {
18+
if (root.getRight() == null) {
19+
root.setRight(node);
20+
return;
21+
}
22+
insert(root.getRight(), node);
23+
} else {
24+
if (root.getLeft() == null) {
25+
root.setLeft(node);
26+
return;
27+
}
28+
insert(root.getLeft(), node);
29+
}
30+
31+
}
32+
33+
public void preOrder(BinaryNode root){
34+
order(root);
35+
if(root.getLeft()!=null)
36+
preOrder(root.getLeft());
37+
if(root.getRight()!=null)
38+
preOrder(root.getRight());
39+
}
40+
41+
public void postOrder(BinaryNode root){
42+
if(root.getLeft()!=null)
43+
postOrder(root.getLeft());
44+
if(root.getRight()!=null)
45+
postOrder(root.getRight());
46+
order(root);
47+
}
48+
49+
public void inOrder(BinaryNode root){
50+
if(root.getLeft()!=null)
51+
inOrder(root.getLeft());
52+
order(root);
53+
if(root.getRight()!=null)
54+
inOrder(root.getRight());
55+
}
56+
57+
/**
58+
* 未实现
59+
* @param root
60+
* @param node
61+
* @return
62+
*/
63+
private boolean remove(BinaryNode root, BinaryNode node){
64+
return false;
65+
}
66+
67+
public BinaryNode getRoot(){
68+
return root;
69+
}
70+
71+
private void order(BinaryNode root){
72+
System.out.print(root.getData()+" ");
73+
}
74+
}

‎group10/353261578/src/com/sx/structures/Iterator.java

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

‎group10/353261578/src/com/sx/structures/MyArrayList.java

Lines changed: 83 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,83 @@
1+
package com.sx.structures;
2+
3+
public class MyArrayList implements MyList {
4+
5+
private int size;
6+
private int ex=10;
7+
private int last=-1;
8+
private Object [] arr;
9+
10+
public MyArrayList() {
11+
size = 10;
12+
arr = new Object[size];
13+
}
14+
15+
@Override
16+
public void add(Object o) {
17+
last++;
18+
if(last==size){
19+
size += ex;
20+
Object[] temp = new Object[size];
21+
System.arraycopy(arr, 0, temp, 0, arr.length);
22+
arr = temp;
23+
}
24+
arr[last]=o;
25+
}
26+
27+
@Override
28+
public void add(int index, Object o) {
29+
add(o);
30+
for(int i=arr.length-1;i>index;i--)
31+
arr[i]=arr[i-1];
32+
arr[index]=o;
33+
}
34+
35+
@Override
36+
public Object get(int index) {
37+
return arr[index];
38+
}
39+
40+
@Override
41+
public Object remove(int index) {
42+
Object element = arr[index];
43+
for(int i=index;i<last;i++)
44+
arr[i]=arr[i+1];
45+
last--;
46+
return element;
47+
}
48+
49+
@Override
50+
public int size() {
51+
return last+1;
52+
}
53+
54+
public Iterator Iterator(){
55+
return new MyArrListIterator(this);
56+
}
57+
58+
private class MyArrListIterator implements Iterator{
59+
60+
private MyList list;
61+
private int p = 0;
62+
public MyArrListIterator(MyList list) {
63+
this.list = list;
64+
}
65+
66+
@Override
67+
public boolean hasNext() {
68+
p++;
69+
if(p>list.size())
70+
return false;
71+
return true;
72+
}
73+
74+
@Override
75+
public Object next() {
76+
if(hasNext())
77+
return list.get(p-1);
78+
return -1;
79+
}
80+
81+
}
82+
83+
}

‎group10/353261578/src/com/sx/structures/MyLinkedList.java

Lines changed: 105 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,105 @@
1+
package com.sx.structures;
2+
3+
public class MyLinkedList implements MyList{
4+
private Node head;
5+
private int size = 0;
6+
7+
public MyLinkedList() {
8+
head = new Node();
9+
}
10+
@Override
11+
public void add(Object o) {
12+
Node node = createNode(o);
13+
Node pre = head;
14+
while(pre.next!=null){
15+
pre = pre.next;
16+
}
17+
pre.next = node;
18+
size++;
19+
}
20+
21+
@Override
22+
public void add(int index, Object o) {
23+
if(index < 0){
24+
System.out.println("����Խ��");return;
25+
}
26+
Node node = createNode(o);
27+
Node pointer = head;
28+
while(index>0){
29+
pointer = pointer.next;
30+
index--;
31+
}
32+
node.next = pointer.next;
33+
pointer.next = node;
34+
size++;
35+
}
36+
37+
@Override
38+
public Object get(int index) {
39+
Node pointer = head;
40+
while(index>=0){
41+
pointer = pointer.next;
42+
index--;
43+
}
44+
return pointer.data;
45+
}
46+
47+
@Override
48+
public Object remove(int index) {
49+
Object data = null;
50+
Node pre = head;
51+
while(index>0){
52+
pre = pre.next;
53+
index--;
54+
}
55+
data = pre.next.data;
56+
pre.next = pre.next.next;
57+
size--;
58+
return data;
59+
}
60+
61+
@Override
62+
public int size() {
63+
return size;
64+
}
65+
66+
public void addFirst(Object o){
67+
add(0, o);
68+
}
69+
public void addLast(Object o){
70+
// Node node = createNode(o);
71+
// Node p = head;
72+
// while(p.next!=null)
73+
// p = p.next;
74+
// p.next = node;
75+
// size++;
76+
add(o);
77+
}
78+
public Object removeFirst(){
79+
return remove(0);
80+
}
81+
public Object removeLast(){
82+
Object data = null;
83+
Node re = head;
84+
Node pre = head;
85+
while(re.next!=null){
86+
re = re.next;
87+
pre = re;
88+
}
89+
data = re.data;
90+
re=null;
91+
pre.next = null;
92+
size--;
93+
return data;
94+
}
95+
private Node createNode(Object o){
96+
Node node = new Node();
97+
node.data=o;
98+
return node;
99+
}
100+
private static class Node{
101+
Object data = null;
102+
Node next = null;
103+
}
104+
105+
}

‎group10/353261578/src/com/sx/structures/MyList.java

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

‎group10/353261578/src/com/sx/structures/MyQueue.java

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
package com.sx.structures;
2+
3+
public class MyQueue {
4+
private MyLinkedList elements ;
5+
public MyQueue() {
6+
elements = new MyLinkedList();
7+
}
8+
9+
public void enQueue(Object o){
10+
elements.add(o);
11+
}
12+
13+
public Object deQueue(){
14+
return elements.removeFirst();
15+
}
16+
17+
public boolean isEmpty(){
18+
if(size()>0)
19+
return false;
20+
return true;
21+
}
22+
public int size(){
23+
return elements.size();
24+
}
25+
}

0 commit comments

Comments
 (0)