Skip to content

Commit 06a6bd7

Browse files
onlyliuxinonlyliuxin
authored
Merge pull request onlyliuxin#30 from kingkeivn/master
19组作业合并
2 parents e0ab6d0 + 4a5568c commit 06a6bd7

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

75 files changed

+3858
-0
lines changed

‎group19/1294642551/.gitignore

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

‎group19/1294642551/readme.txt

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1 @@
1+
JaneZhou91's files

‎group19/1294642551/src/data_Structures/ArrayList.java

Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
package data_Structures;
2+
3+
4+
public class ArrayList implements List {
5+
6+
private int size = 0;
7+
8+
private Object[] elementData = new Object[100];
9+
10+
11+
public void add(Object o){
12+
13+
elementData[size] = o;
14+
size++;
15+
}
16+
public void add(int index, Object o){
17+
18+
int temp = size;
19+
while(temp > index)
20+
{
21+
elementData[temp] = elementData[temp-1];
22+
temp--;
23+
}
24+
25+
elementData[index] = o;
26+
27+
size++;
28+
29+
30+
}
31+
32+
public Object get(int index){
33+
return elementData[index];
34+
}
35+
36+
public Object remove(int index){
37+
38+
int temp = index;
39+
while(temp < size-1)
40+
{
41+
elementData[temp] = elementData[temp+1];
42+
temp++;
43+
}
44+
size--;
45+
46+
return elementData[index];
47+
}
48+
49+
public int size(){
50+
return size;
51+
}
52+
53+
public Iterator iterator(){
54+
return null;
55+
}
56+
57+
}

‎group19/1294642551/src/data_Structures/LinkedList.java

Lines changed: 125 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,125 @@
1+
package data_Structures;
2+
3+
4+
public class LinkedList implements List {
5+
6+
private Node head;
7+
private int size;
8+
9+
LinkedList()
10+
{
11+
size = 0;
12+
}
13+
14+
public void add(Object o){
15+
16+
Node newNode = new Node(o);
17+
18+
if(head == null)
19+
{
20+
head = newNode;
21+
}
22+
else
23+
{
24+
Node tempNode = head;
25+
while(tempNode.next != null)
26+
{
27+
tempNode = tempNode.next;
28+
}
29+
tempNode.next = newNode;
30+
31+
}
32+
33+
size++;
34+
}
35+
36+
public void add(int index , Object o){
37+
38+
Node newNode = new Node(o, getNode(index));
39+
getNode(index-1).next = newNode;
40+
41+
size++;
42+
43+
}
44+
45+
public Node getNode(int index)
46+
{
47+
Node tempNode = head;
48+
int i = 0;
49+
while(i < index)
50+
{
51+
tempNode = tempNode.next;
52+
i++;
53+
}
54+
55+
return tempNode;
56+
}
57+
58+
59+
60+
public Object get(int index){
61+
return getNode(index).data;
62+
}
63+
public Object remove(int index){
64+
65+
Node tempNode = getNode(index);
66+
getNode(index - 1).next = getNode(index+1);
67+
tempNode.next = null;
68+
tempNode.data = null;
69+
size--;
70+
return getNode(index).data;
71+
72+
}
73+
74+
public int size(){
75+
return size;
76+
}
77+
78+
public void addFirst(Object o){
79+
80+
Node tempNode = head;
81+
head = new Node(o);
82+
head.next = tempNode;
83+
84+
size++;
85+
}
86+
public void addLast(Object o){
87+
add(o);
88+
89+
}
90+
public Object removeFirst(){
91+
92+
Node tempNode = head;
93+
head = getNode(1);
94+
size--;
95+
96+
return tempNode.data;
97+
}
98+
public Object removeLast(){
99+
getNode(size-1).next = null;
100+
size--;
101+
return getNode(size).data;
102+
}
103+
public Iterator iterator(){
104+
return null;
105+
}
106+
107+
108+
private static class Node{
109+
Object data;
110+
Node next;
111+
112+
Node(Object data, Node next )
113+
{
114+
this.data = data;
115+
this.next = next;
116+
}
117+
118+
Node(Object data)
119+
{
120+
this.data = data;
121+
this.next = null;
122+
}
123+
124+
}
125+
}

‎group19/1294642551/src/data_Structures/List.java

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

‎group19/1294642551/src/data_Structures/Queue.java

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
package data_Structures;
2+
3+
public class Queue {
4+
5+
private LinkedList ll;
6+
7+
Queue()
8+
{
9+
ll = new LinkedList();
10+
}
11+
12+
public void enQueue(Object o){
13+
ll.add(o);;
14+
}
15+
16+
public Object deQueue(){
17+
return ll.removeFirst();
18+
}
19+
20+
public boolean isEmpty(){
21+
int size = ll.size();
22+
return (size == 0);
23+
}
24+
25+
public int size(){
26+
return ll.size();
27+
}
28+
}

‎group19/1294642551/src/data_Structures/Stack.java

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
package data_Structures;
2+
3+
public class Stack {
4+
// private ArrayList elementData = new ArrayList();
5+
6+
private LinkedList ll;
7+
Stack()
8+
{
9+
ll = new LinkedList();
10+
}
11+
12+
public void push(Object o){
13+
ll.addLast(o);
14+
}
15+
16+
public Object pop(){
17+
return ll.removeLast();
18+
}
19+
20+
public Object peek(){
21+
return null;
22+
}
23+
public boolean isEmpty(){
24+
return ll.size()==0;
25+
}
26+
public int size(){
27+
return ll.size();
28+
}
29+
}

‎group19/1592562638/.gitignore

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
/bin/
2+
*.class
3+
*.settings
4+
*.project
5+
*.classpath
6+
*/.settings
7+
*.iml
8+
/.idea
9+
/**/target/**/*

‎group19/1592562638/src/ArrayList_self.java

Lines changed: 126 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,126 @@
1+
/*范例名称：
2+
* 原文件名称：
3+
* 要点：
4+
* 1. 实现基本的数据结构类：ArrayList
5+
6+
*/
7+
public class ArrayList_self<T> implements KIList<T> {
8+
/***初始化容量大小***/
9+
private final static int INIT_CAPACITY=12;
10+
private Object[] mList=null;
11+
12+
/***当前容量***/
13+
private int mCurrentCapacity=0;
14+
/***容器中元素个数***/
15+
private int mSize=0;
16+
17+
public ArrayList_self(){
18+
mList=new Object[INIT_CAPACITY];
19+
mCurrentCapacity=INIT_CAPACITY;
20+
}
21+
22+
/**
23+
* 插入一个元素到ArrayList尾部
24+
* @param item
25+
* */
26+
@Override
27+
public void add(T item) {
28+
// TODO Auto-generated method stub
29+
if(mSize==mCurrentCapacity){
30+
expansion();//扩容
31+
}
32+
mList[mSize]=item;
33+
mSize++;
34+
}
35+
36+
/**
37+
* 插入一个元素到指定位置，从插入位置及其后面的元素往后移动一个位置
38+
* @param index 要插入的位置
39+
* @param item
40+
* */
41+
@Override
42+
public void add(int index, T item) {
43+
// TODO Auto-generated method stub
44+
if (index<0 || index>=mSize) {//不允许index小于0，或者index >= 数组当前大小
45+
throw new IndexOutOfBoundsException();//抛出越界异常
46+
}
47+
if(mSize==mCurrentCapacity){
48+
expansion();//扩容
49+
}
50+
Object[] newList=new Object[mCurrentCapacity];
51+
System.arraycopy(mList, 0, newList, 0, index);
52+
System.arraycopy(mList, index, newList, index+1, mSize-index);
53+
newList[index]=item;
54+
mList=newList;
55+
mSize++;
56+
}
57+
/**
58+
* 移除指定位置的元素，后面的元素向前移动一位
59+
* @param index
60+
* */
61+
@Override
62+
public T remove(int index) {
63+
// TODO Auto-generated method stub
64+
if(index<0 || index>=mSize){
65+
throw new IndexOutOfBoundsException();
66+
}
67+
Object[] newList=new Object[mCurrentCapacity];
68+
System.arraycopy(mList, 0, newList, 0, index);
69+
System.arraycopy(mList, index+1, newList, index, mSize - index);
70+
71+
T tempT=(T) mList[index];
72+
mList=newList;
73+
mSize--;
74+
75+
return tempT;
76+
}
77+
/**
78+
* 更新指定位置的元素
79+
* @param index
80+
* @param item
81+
* */
82+
@Override
83+
public void set(int index, T item) {
84+
// TODO Auto-generated method stub
85+
if(index<0 || index>=mSize){
86+
throw new IndexOutOfBoundsException();
87+
}
88+
mList[index]=item;
89+
}
90+
/**
91+
* 获取指定位置的元素
92+
* @param index
93+
* @return
94+
* */
95+
@Override
96+
public T get(int index) {
97+
// TODO Auto-generated method stub
98+
if(index<0 || index>=mSize){
99+
throw new IndexOutOfBoundsException();
100+
}
101+
102+
return (T)mList[index];
103+
}
104+
/**
105+
* 获取当前链表的长度
106+
* @return int
107+
* */
108+
@Override
109+
public int size() {
110+
// TODO Auto-generated method stub
111+
return mSize;
112+
}
113+
114+
/**
115+
* 扩容，当 mSize == mCurrentCapacity 时调用;当满的时候每次增加当前容量的50%
116+
* */
117+
private void expansion() {
118+
// TODO Auto-generated method stub
119+
Object[] oldList=mList;
120+
Object[] newList=new Object[mCurrentCapacity + (mCurrentCapacity >> 1)];
121+
System.arraycopy(oldList, 0, newList, 0, oldList.length);
122+
mList=newList;
123+
mCurrentCapacity=mCurrentCapacity + (mCurrentCapacity >> 1);
124+
}
125+
126+
}

0 commit comments

Comments
 (0)