java基础知识
在java中，只有八种基本类型（byte,short,int,double,float,long,char,boolean）在调用时是值传递的调用，其他类型均为地址传递（引用）
所以，创建一个string类型的数组时，存放的是每个string类型的地址
创建一个数组的方法
1
2
3
| x = new int[3];
y = new int[]{1,2,3,4,5};
int [] z = {9,213,41,12};
|
类可以进行嵌套。如SLList里嵌套了IntNode类，IntNode只是SLList的一个子功能
泛型实例化不能直接对数组使用，而要通过
1
| items = (T[]) new Object[9];
|
语句实现
IntList
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| public class IntList
{
public int first;
public IntList rest;
public static void main(String[] args)
{
IntList L =new IntList();
L.first = 5;
L.rest = null;
L.rest = new IntList();
L.rest.first = 15;
L.rest.rest = new IntList();
L.rest.first = 20;
L.rest.rest.rest= null;
}
}
|
但当结点过多时，每次这样添加结点过于臃肿，所以为其添加构造函数，反向构建列表（尾插法）。并添加了大小和获取结点的方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| public class IntList
{
public int first;
public IntList rest;
public IntList(int f,IntList r)
{
first=f;
rest=r;
}
public int size1()
{
if(rest==null)
return 1;
return 1 + rest.size1();
}
public int size2()
{
int total = 0;
IntList p = this;
while(p!=null)
{
total+=1;
p=p.rest;
}
return total;
}
public int get1(int i)
{
if(i==0)return first;
return rest.get1(i-1);
}
public int get2(int i)
{
int place = 0;
IntList p = this;
while(place!=i)
{
place++;
p=p.rest;
}
return p.first;
}
public static void main(String[] args)
{
IntList L = new IntList(15,null);
L = new IntList(10,L);
L = new IntList(5,L);
System.out.println(L.size1());
System.out.println(L.size2());
System.out.println(L.get1(2));
System.out.println(L.get2(2));
}
}
|
SLList(singly-linked list)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
| public class SLList {
private class IntNode {
public int item;
public IntNode next;
public IntNode(int i, IntNode n) {
item = i;
next = n;
}
}
private int size;
private IntNode first;
public SLList(int x) {
first = new IntNode(x, null);
size = 1;
}
public SLList()
{
first = null;
size = 0;
}
public void addfirst(int x)
{
first = new IntNode(x,first);
size++;
}
public void addlast(int x)
{
IntNode p = first;
while(p!=null)
{
p = p.next;
}
p = new IntNode (x,null);
size++;
}
public int getfirst()
{
return first.item;
}
private int size(IntNode p)
{
if(p==null)return 1;
return 1 + size(p.next);
}
public int size()
{
return size;
}
public static void main(String[] args)
{
SLList p = new SLList(3);
p.addfirst(32);
System.out.println(p.getfirst());
}
}
|
但当我们对空列表进行尾插时，会发生报错，是因为Null不存在next，可以将特殊情况特判，但当方法很多时会过于臃肿。因此我们需要设置一个虚首节点“哨兵”
现存方法：头插法，尾插法，大小，得到第一个节点的值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| public class SLList {
private class IntNode {
public int item;
public IntNode next;
public IntNode(int i, IntNode n) {
item = i;
next = n;
}
}
private int size;
private IntNode Sentinel;
public SLList(int x) {
Sentinel = new IntNode(0,null);
Sentinel.next = new IntNode(x, null);
size = 1;
}
public SLList()
{
Sentinel = new IntNode(0,null);
size = 0;
}
public void addfirst(int x)
{
Sentinel.next = new IntNode(x,Sentinel.next);
size++;
}
public void addlast(int x)
{
IntNode p = Sentinel;
while(p.next!=null)
{
p = p.next;
}
p.next = new IntNode (x,null);
size++;
}
public int getfirst()
{
return Sentinel.next.item;
}
private int size(IntNode p)
{
if(p==null)return 1;
return 1 + size(p.next);
}
public int size()
{
return size;
}
public static void main(String[] args)
{
SLList p = new SLList(3);
p.addfirst(32);
System.out.println(p.getfirst());
}
}
|
DLList
上述尾插的时间复杂度为O(n)，为优化为O(1)，我们可以在链表末尾添加一个尾指针。但addlast函数就会存在问题。这时我们构建双向链表，但此时又存在尾指针指向“哨兵”的情况。解决方法有：在末尾再设置一个“哨兵”or将尾指针指向起始“哨兵”
AList
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| public class AList {
private int[] items;
private int size;
public AList() {
items = new int[100];
size = 0;
}
public void addlast(int x)
{
items[size] = x;
size++;
}
public int getlast()
{
return items[size-1];
}
public int get(int i)
{
return items[i];
}
public int size()
{
return size;
}
public int removelast()
{
int x = getlast();
size--;
return x;
}
private void resize(int capacity)
{
int [] a = new int [capacity];
System.arraycopy(items,0,a,0,size);
items = a;
}
public void addLast(int x)
{
if(size == items.length)resize(size * 2);
items[size]=x;
size++;
}
}
|
BST
二叉搜索树，由有序链表形成，需满足 1.二叉树 2.左边的子节点比本节点小，右边的节点比本节点大
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| static BST find(BST T , Key sk)
{
if(T == null) return null;
if(sk.equals(T.key)) return T;
else if(sk<T.key) return find(T.left , sk);
else return find(T.right , sk);
}
static BST insert(BST T , Key ik)
{
if(T == null) return new BST(ik);
if(ik < T.key) T.left = insert(T.left , ik);
else if(ik > T.key) T.right = insert(T.right , ik);
return T;
}
|
删除节点时，若无子节点直接取消引用，有一个子节点直接父节点指向子节点，有两个节点时，将所有子节点中最大/最小的节点作为根节点
