Bill's blog
首页
时间轴
留言板
AHUT
2021考研
Books
文章
友链
关于
avatar
文章
21
标签
27
分类
11
首页
时间轴
留言板
AHUT
2021考研
Books
文章
友链
关于
目录
  1. 1. 数据结构
  2. 2. FAQ
    1. 2.1. Q1: 为什么要学数据结构？
    2. 2.2. Q2：有哪些数据结构？
    3. 2.3. Q3：学习境界？
  3. 3. 算法
    1. 3.1. 什么是算法？
    2. 3.2. 算法特征：
  4. 4. 时间复杂度(Time Complexity)定义
  5. 5. 时间复杂度的计算
    1. 5.1. 时间复杂度计算例题
    2. 5.2. 常用的时间复杂度级别
  6. 6. 空间复杂度(Space Complexity)定义
  7. 7. 线性表(linearlist)
    1. 7.1. 数组
    2. 7.2. 链表 — 链式存储结构
  8. 8. 线性表实现
  9. 9. ArrayList实现
    1. 9.1. ArrayList类
    2. 9.2. TestArrayList类
  10. 10. LinkedList实现
    1. 10.1. LinkedList类
    2. 10.2. TestLinkedList类
  11. 11. 其他线性表
    1. 11.1. 双向链表
    2. 11.2. 循环链表
    3. 11.3. Java中
  12. 12. 栈和队列
  13. 13. 栈(Stack)
    1. 13.1. 栈的接口:
  14. 14. 队列（Quene）
    1. 14.1. 队列的接口:
    2. 14.2. 其他队列
    3. 14.3. 双端队列Deque
  15. 15. Java中的栈和队列类
    1. 15.1. 例：用栈实现10进制转2进制
  16. 16. Disruptor并发框架中的Quene
  17. 17. 树和二叉树
    1. 17.1. 什么是树？
    2. 17.2. 树（tree）是包含n（n>0）个结点的有穷集，其中：
    3. 17.3. 下面的关于Tree的术语主要来自维基百科
    4. 17.4. 相关术语 中文版
    5. 17.5. 下面通过几个图解释树的几个比较重要的概念
    6. 17.6. Edge、Root、Leaf
    7. 17.7. Path
    8. 17.8. Height
    9. 17.9. Depth
    10. 17.10. Level
  18. 18. 二叉树
  19. 19. 二叉树的分类
    1. 19.1. 完美/满二叉树(Perfect Binary Tree)
    2. 19.2. 完全二叉树(Complete Binary Tree)
  20. 20. 完满二叉树(Full Binary Tree)
  21. 21. 二叉树实现
    1. 21.1. 二叉树的遍历策略
    2. 21.2. 例：
    3. 21.3. 例题：
    4. 21.4. 按层次遍历（广度优先搜索）
  22. 22. 二叉树接口
    1. 22.1. 二叉链表节点
    2. 22.2. 二叉树接口
  23. 23. 二叉树操作
数据结构
|算法

数据结构

数据结构(data structure)是带有结构特性的数据元素的集合，它研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系，并对这种结构定义相适应的运算，设计出相应的算法，并确保经过这些运算以后所得到的新结构仍保持原来的结构类型。简而言之，数据结构是相互之间存在一种或多种特定关系的数据元素的集合，即带“结构”的数据元素的集合。“结构”就是指数据元素之间存在的关系，分为逻辑结构和存储结构。
数据的逻辑结构和物理结构是数据结构的两个密切相关的方面，同一逻辑结构可以对应不同的存储结构。算法的设计取决于数据的逻辑结构，而算法的实现依赖于指定的存储结构。
数据结构的研究内容是构造复杂软件系统的基础，它的核心技术是分解与抽象。通过分解可以划分出数据的3个层次；再通过抽象，舍弃数据元素的具体内容，就得到逻辑结构。类似地，通过分解将处理要求划分成各种功能，再通过抽象舍弃实现细节，就得到运算的定义。上述两个方面的结合可以将问题变换为数据结构。这是一个从具体（即具体问题）到抽象（即数据结构）的过程。然后，通过增加对实现细节的考虑进一步得到存储结构和实现运算，从而完成设计任务。这是一个从抽象（即数据结构）到具体（即具体实现）的过程。

FAQ

Q1: 为什么要学数据结构？

  • 承前启后：学语言->学算法->写程序
  • 高级计算机程序设计的理论指导
  • 提升编程能力
  • 面试中经常问到

Q2：有哪些数据结构？

  • 线性表、栈、（字符）串、数组、广义表、树、二叉树、图
  • 重点是线性表、二叉树
  • 对于每种数据结构会讲解其添加、更新、删除、查询、排序等操作的实现

Q3：学习境界？

  • 境界一 听懂理论，听懂算法思路
  • 境界二 完成主要数据结构的基本算法实现（入门）
  • 境界三 更多数据结构，更多算法的实现（进一步提高数据结构功底）
  • 境界四 融会贯通、举一反三，在后续开发中综合应用数据结构知识

算法

algorithm 英[ˈælɡərɪðəm] 美[ˈælɡərɪðəm]

什么是算法？

For Example: 求 1+2+3+…+100 = ?

  1. 依次相加
    c
    1
    2
    3
    4
    5
    int res = 0;
    for(int i = 0; i <= 100; i++){
        res += i;
    }
    cout << res << endl;
  2. 高斯求和
    c
    1
    2
    3
    4
    5
    6
    int res = 0;
    int add_max = 100;
    /* 梯形面积公式算法 */
    res = (1 + add_max) * add_max / 2;
    /* 三角形面积公式算法 (0+1+2+...+100, h = 101)*/
    res = add_max * (add_max + 1) / 2;
  3. 递归
    c
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    /*sum(100) = sum(99) + 100
    sum(99) = sum(98) + 99
    =>
    sum(100) = sum(98) + 99 + 100
    ...
    sum(100) = sum(1) + 2 + ... + 99 + 100*/
    int sum(int m){
        if(m > 1){
            return sum(m-1) + m;
        }else{
            return 1;
        }
    }
    int main(int argc, char *argv[]){
        cout << sum(100) << endl;
        return 0;
    }

以上3个算法显然高斯求和算法的时间复杂度及空间复杂度最优

算法特征：

  1. 输入
  2. 输出
  3. 可行性
  4. 有穷性
  5. 确定性

时间复杂度(Time Complexity)定义

  • （1）时间频度：T(n)，n表示问题的规模。一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。
  • （2）时间复杂度：一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T（n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。在T(n)=4n²-2n+2中，就有f(n)=n²，使得T（n)/f(n)的极限值为4，那么O(f(n))，也就是时间复杂度为O(n²)
  • 时间复杂度一般讨论最坏的时间复杂度
  • 定义O（最坏情况<=），例如T(n) = O(n²)
  • 定义Ω（最好情况>=），例如T(n) = Ω(n²)
  • 定义Θ（最好情况与最坏情况同阶），例如T(n) = Θ(n²)

时间复杂度的计算

  1. 找出算法中的基本语句

    执行次数最多的就是基本语句，通常是最内层循环的循环体
  2. 计算基本语句的执行次数的数量级
  3. 用O表示

一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。

　　一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T（n)/f (n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

　　在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为O(1),另外，在时间频度不相同时，时间复杂度有可能相同，如T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同，但时间复杂度相同，都为O(n2)。

时间复杂度计算例题

1.T(n) = 1, T(n) = O(1)

c
1
int count = 0;

100个简单语句其时间复杂度仍为O(1)

2.一个循环的时间复杂度为O(n)

c
1
2
3
4
int n = 8, count = 0;
for(int i = 0; i <= n; i++){
    count++;
}

T(n) = n, T(n) = O(n)

  1. 时间复杂度为O(log2(n))

    c
    1
    2
    3
    4
    5
    6
    7
    8
    int n = 8, count = 0;
    for(int i = 0; i <= n; i*=2){
        count++;
    }
    /*1,2,4,8,16,32,...
    设循环x次，则2^x = n => x = log2(n)
    T(n) = log2(n)
    T(n) = O(log2(n))*/

  2. 时间复杂度为O(n²)

    c
    1
    2
    3
    4
    5
    6
    int n = 8, count = 0;
    for(int i = 0; i <= n; i++)
        for(int j = 0; j <= n; j++)
            count++;
    /*T(n) = n x n
    T(n) = O(n²)*/

  3. 时间复杂度为O(nlog2(n))

    c
    1
    2
    3
    4
    int n = 8, count = 0;
    for(int i = 0; i <= n; i*=2)
        for(int j = 0; j <= n; j++)
            count++;

  4. 时间复杂度为O(n²)

    c
    1
    2
    3
    4
    5
    6
    int n = 8, count = 0;
    for(int i = 0; i <= n; i++)
        for(int j = 0; j <= i; j++)
            count++;
    /*T(n) = n x (1+2+3+...+n) = 0.5n + 0.5n²
    T(n) = O(n²)*/

常用的时间复杂度级别

常用的时间复杂度级别

空间复杂度(Space Complexity)定义

类似于时间复杂度的讨论，一个算法的空间复杂度S(n)定义为该算法所耗费的存储空间，它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。空间复杂度(SpaceComplexity)是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。算法的输入输出数据所占用的存储空间是由要解决的问题决定的，是通过参数表由调用函数传递而来的，它不随本算法的不同而改变。存储算法本身所占用的存储空间与算法书写的长短成正比，要压缩这方面的存储空间，就必须编写出较短的算法。算法在运行过程中临时占用的存储空间随算法的不同而异，有的算法只需要占用少量的临时工作单元，而且不随问题规模的大小而改变，我们称这种算法是“就地"进行的，是节省存储的算法，有的算法需要占用的临时工作单元数与解决问题的规模n有关，它随着n的增大而增大，当n较大时，将占用较多的存储单元，例如快速排序和归并排序算法就属于这种情况。

S(n) = O(g(n))

  1. 空间复杂度 O(1)。如果算法执行所需要的临时空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量，可表示为 O(1)
    举例：

    c
    1
    2
    3
    4
    5
    int i = 1;
    int j = 2;
    ++i;
    j++;
    int m = i + j;

    代码中的 i、j、m 所分配的空间都不随着处理数据量变化，因此它的空间复杂度 S(n) = O(1)

  2. 空间复杂度 O(n)

    c
    1
    2
    3
    4
    5
    6
    int[] m = new int[n]
    for(i=1; i<=n; ++i)
    {
       j = i;
       j++;
    }

    这段代码中，第一行new了一个数组出来，这个数据占用的大小为n，这段代码的2-6行，虽然有循环，但没有再分配新的空间，因此，这段代码的空间复杂度主要看第一行即可，即 S(n) = O(n)

由此可见，递归算法效率低下，体现在空间复杂度高。

线性表(linearlist)

  • Java的LinkList底层是双向链表
  • ArryList是顺序表
  1. 相同的数据类型
  2. 序列（顺序性）
  3. 有序

数组

数组是连续的一块内存空间

链表 — 链式存储结构

非连续的内存空间

线性表实现

  • Java中ArrayList底层采用数组实现
  • Java中LinkedList底层采用双向链表实现
  • 我们通过对ArrayList和LinkedList的简单实现练习线性表
  • 实际上的ArrayList和LinkedList比我们写的要复杂
  • 无论是ArrayList还是LinkedList，其都有以下（包括但不限于）方法，与存储结构无关。因此我们定义了如下接口，给ArrayList和LinkedList使用
java
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
package com.webpro.linetable;

/**
 * 线性表
 * 和存储结构无关
 */

public interface List {

    // 返回线性表的大小
    public int size();

    // 返回线性表中序号为 i 的数据元素
    public Object get(int i);

    // 线性表为空返回True，否则返回False
    public boolean isEmpty();

    // 判断线性表是否包含数据元素 e
    public boolean contains(Object e);

    // 返回数据元素e在线性表中的序号
    public int indexOf(Object e);

    // 将数据元素e插入到线性表中i号的位置
    public void add(int i, Object e);

    // 将数据元素e插入到线性表的末尾
    public void add(Object e);

    // 将数据元素e插入到object之前
    public boolean addBefore(Object obj, Object e);

    // 将数据元素e插入到object之后
    public boolean addAfter(Object obj, Object e);

    // 删除线性表序号为i的元素 并返回之
    public Object remove(int i);

    // 删除线性表中第一个与e相同的元素
    public boolean remove(Object e);

    // 替换线性表中序号为i的数据元素为e，返回原数据元素
    public Object replace(int i, Object e);

    // 输出List
    public String toString();
}

ArrayList实现

  • ArrayList底层是数组

Ⅰ. 用Java模拟实现ArrayList基本操作

ArrayList类

java
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
package com.webpro.linetable;

import java.util.Arrays;

/**
 * 顺序表
 * 底层采用数组，但是长度可以动态变化
 * 
 * java.util.ArrayList每次扩容操作增加 1/2
 *
 */

public class ArrayList implements List {
	
	private Object[] elementData; // 底层是一个数组，目前还没有确定长度
	
	/**
     * The size of the ArrayList (the number of elements it contains).
     */
    private int size; // 元素的个数
    
    public ArrayList() {
    	// 没有指定长度，默认长度为4
    	this(4);
    }

    /**
     * 构造方法
     * @param initialCapacity 数组的初始长度
     */
    public ArrayList(int initialCapacity) {
    	// 给数组分配指定数量空间
    	elementData = new Object[initialCapacity];
    	// 指定顺序表的元素个数
    	size = 0;
    }

	@Override
	public int size() {
		// TODO Auto-generated method stub
		return size;
	}

	@Override
	public Object get(int i) {
		if(i < 0 || i >= size) {
			throw new MyArrayIndexOutOfBoundsException("数组索引越界异常: " + i);
		}
		return elementData[i];
	}

	@Override
	public boolean isEmpty() {
		return size == 0;
	}

	@Override
	public boolean contains(Object e) {
		return indexOf(e) >= 0;
	}

	@Override
	public int indexOf(Object e) {
		if(e == null) {
			for(int i = 0; i < size; i++)
				if(elementData[i] == null)
					return i;
		}else {
			for(int i = 0; i < size; i++)
				if(e.equals(elementData[i]))
					return i;
		}
		return -1;
	}

	@Override
	public void add(int i, Object e) {
		// i 的位置要正确
		if(i < 0 || i > size) {
			throw new MyArrayIndexOutOfBoundsException("数组索引越界异常: " + i);
		}
		// 数组满了，就扩容
		if(size == elementData.length) {
			grow();
		}
		// 后移i及其后面的元素，从最后一个元素开始
		for(int j = size; j > i; j--) {
			elementData[j] = elementData[j-1];
		}
		elementData[i] = e;
		size++;
	}

	@Override
	public void add(Object e) {
		this.add(size, e);
	}

	private void grow() {
		// 创建一个新的数组，其长度是elementData的两倍
		elementData = Arrays.copyOf(elementData, elementData.length*2);
	}

	@Override
	public boolean addBefore(Object obj, Object e) {
		// 数组满了，就扩容
		if(size + 1 >= elementData.length) {
			grow();
		}
		for(int i = 0; i < size; i++){
			if(obj.equals(elementData[i])) {
				for(int j = size - 1; j >= i; j--)
					elementData[j+1] = elementData[j];
				elementData[i] = e;
				size++;
				return true;
			}
		}
		return false;
	}

	@Override
	public boolean addAfter(Object obj, Object e) {
		// addAfter可以看作是：找到obj的下一个元素，调用addBefore
		for(int i = 0; i < size; i++)
			if(obj.equals(elementData[i]))
				return addBefore(elementData[i + 1], e);
		return false;
	}

	@Override
	public Object remove(int i) {
		Object remove_obj = elementData[i];
		for(int j = i; j < size; j++) {
			elementData[j] = elementData[j+1];
		}
		size--;
		return remove_obj;
	}

	@Override
	public boolean remove(Object e) {
		int index = indexOf(e);
		if( index >= 0) {
			remove(index);
			return true;
		}else {
			return false;
		}
	}

	@Override
	public Object replace(int i, Object e) {
		elementData[i] = e;
		return e;
	}

	@Override
	public String toString() {
		if(size == 0) {
			return "[]";
		}
		StringBuilder builder = new StringBuilder("[");
		for(int i = 0; i < size; i++) {
			if(i != size - 1) {
				builder.append(elementData[i] + ",");
			}else {
				builder.append(elementData[i]);
			}
		}
		builder.append("]");
		return builder.toString();
	}

}

TestArrayList类

java
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
package com.webpro.linetable;

public class TestArrayList {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		ArrayList list = new ArrayList();
		list.add(123);
		list.add(321);
		list.add(456);
		list.add(654);
		list.add(678);
		list.add(789);
		list.add(678);
		list.add(5, 666);
		
		System.out.println(list.size());
		System.out.println(list.isEmpty());
		System.out.println(list.get(2));
		System.out.println(list.toString());
		System.out.println(list.contains(678));
		System.out.println(list.addBefore(321, 777));
		System.out.println(list.addAfter(321, 777));
		System.out.println(list.toString());
		System.out.println(list.get(2));
		System.out.println(list.remove(0));
		System.out.println(list.toString());
		
	}
}

Ⅱ. 用C语言模拟实现ArrayList基本操作

c
1
2


LinkedList实现

  • LinkedList底层是双向链表
  • 我们用单项链表实现MyLinkedList

Ⅰ. 用Java模拟实现LinkedList基本操作

LinkedList类

java
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
package com.webpro.linetable;

public class SingleLinkedList implements List {

	private Node head; // 头节点，不存储数据，为了编程

	private int size;  // 一共有几个节点

	public SingleLinkedList() {
		head = new Node();
	}

	@Override
	public int size() {
		return size;
	}

	@Override
	public Object get(int i) {
		// 和顺序表不一样，要从头节点逐个开始查找
		Node p = head;
		for(int j = 0; j <= i; j++) {
			p = p.next;
		}
		return p.data;
	}

	@Override
	public boolean isEmpty() {
		return size == 0;
	}

	@Override
	public boolean contains(Object e) {
		Node p = head.next;
		while(p.next != null) {
			if(p.data.equals(e))
				return true;
			p = p.next;
		}
		return false;
	}

	@Override
	public int indexOf(Object e) {
		Node p = head.next;
		for(int i = 0; i < size; i++) {
			if(p.data.equals(e))
				return i;
			p = p.next;
		}
		return -1;
	}

	@Override
	public void add(int i, Object e) {
		// 如果i的位置错误，报错
		if(i < 0 || i > size) {
			throw new MyArrayIndexOutOfBoundsException("数组指针越界异常: " + i);
		}
		// 找到前一个节点，从head开始找
		Node p = head;
		for(int j = 0; j < i; j++) {
			p = p.next;
		}
		// 创建一个节点
		Node newNode = new Node(e);
		// 指向新节点的直接后继
		newNode.next = p.next;
		// 指向新节点的直接前驱
		p.next = newNode;
		size++;
	}

	@Override
	public void add(Object e) {
		this.add(size, e);
	}

	@Override
	public boolean addBefore(Object obj, Object e) {
		Node p = head.next;
		Node pre = head;
		Node newNode = new Node(e);
		if(obj == null) {
			this.add(size, e);
			return true;
		}else {
			while(p.next != null) {
				if(p.data.equals(obj)) {
					pre.next = newNode;
					newNode.next = p;
					size++;
					return true;
				}
				p = p.next;
				pre = pre.next;
			}
			return false;
		}
	}

	@Override
	public boolean addAfter(Object obj, Object e) {
		// 取obj的下一个元素进行addBefore操作
		Node p = head.next;
		while(p.next != null) {
			if(p.data.equals(obj))
				return addBefore(p.next.data, e);
			p = p.next;
		}
		return false;
	}

	@Override
	public Object remove(int i) {
		Node p = head;
		for(int j = 0; j < i; j++)
			p = p.next;
		Node remove_obj = p.next;
		p.next = p.next.next;
		size--;
		return remove_obj;
	}

	@Override
	public boolean remove(Object e) {
		int index = indexOf(e);
		if(index >= 0) {
			remove(index);
			return true;
		}else {
			return false;
		}
	}

	@Override
	public Object replace(int i, Object e) {
		Node newNode = new Node(e);
		Node p = head;
		for(int j = 0; j < i; j++)
			p = p.next;
		Node old = p.next;
		newNode.next = p.next.next;
		p.next = newNode;
		return old;
	}

	@Override
	public String toString() {
		if(size == 0) {
			return "[]";
		}
		StringBuilder builder = new StringBuilder("[");
		Node p = head.next;
		for(int i = 0; i < size; i++) {
			if(i != size - 1) {
				builder.append(p.data + ",");
			}else {
				builder.append(p.data);
			}
			p = p.next;
		}
		builder.append("]");
		return builder.toString();
	}

}

TestLinkedList类

java
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
package com.webpro.linetable;

public class TestSingleLinkedList {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		SingleLinkedList list = new SingleLinkedList();
		list.add("123");
		list.add("321");
		list.add("456");
		list.add("654");
		list.add("678");
		list.add("789");
		list.add("678");
		
		System.out.println(list.toString());
		
		list.add(2, "666");
		
		System.out.println(list.size());
		System.out.println(list.isEmpty());
		System.out.println(list.get(5));
		System.out.println(list.toString());
		
		System.out.println(list.contains("678"));
		System.out.println(list.contains("66666"));
		
		System.out.println("addBefore  " + list.addBefore("123", "456"));
		System.out.println("addBefore  " + list.toString());
		
		System.out.println("addAfter   " + list.addAfter("678", "456"));
		System.out.println("addAfter   " + list.toString());
				
		System.out.println("addAfter   " + list.remove("456"));
		System.out.println("addAfter   " + list.toString());
	}
}

Ⅱ. 用C语言模拟实现LinkedList基本操作

c
1
2


其他线性表

  • 一般为了编程方便，头节点和尾节点（如果存在）是不存储数据的
  • 为了保持算法的一致性，有时添加首尾节点

双向链表

双向链表

循环链表

循环链表

Java中

  • Vector 顺序表
  • ArrayList 顺序表
  • LinkedList 双向链表

Vector、ArrayList底层均为可变长度的数组。Vector线程安全，效率低，已基本弃用；ArrayList线程不安全，效率高。ArrayList扩容策略为每次扩容原长度的50%。

栈和队列

本节分为

  • 栈（Stack）
  • 队列（Quene）
  • Java中的栈和队列
  • Disruptor并发框架中的Quene

栈(Stack)

  • 操作受限的线性表
  • 先进后出，删除与加入均在栈顶操作
  • 栈也称为堆栈，是一种线性表。
  • 堆栈的特性： 最先放入堆栈中的内容最后被拿出来，最后放入堆栈中的内容最先被拿出来， 被称为先进后出、后进先出。
  • 堆栈中两个最重要的操作是PUSH和POP，两个是相反的操作。
  • PUSH：在堆栈的顶部加入一 个元素。
  • POP：在堆栈顶部移去一个元素， 并将堆栈的大小减一。
  • 栈2
  • 栈1

其限制是仅允许在表的一端进行插入、删除操作，不允许在其他任何地方进行插入、删除操作。表中进行插入删除的一端称为栈顶（top），栈顶保存的元素称为栈顶元素。相对于表的另一端成为栈底（bottom）。

  • 插入操作 -> 入栈
  • 删除操作 -> 出栈
  • 专业词汇：push入栈，pop出栈，peek栈顶元素

栈的接口:

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public interface Stack {

    // 获取元素数量
    public int getSize();

    // 栈是否为空
    public boolean isEmpty();

    // 入栈
    public void push(Object e);

    // 出栈
    public void pop();

    // 取栈顶元素
    public Object peek();

}

队列（Quene）

队列(Queue)也是一种运算受限的线性表，它的运算限制与栈不同，是两头都有限制，插入只能在表的一端进行(只进不出)，而删除只能在表的另一端进行(只出不进)，允许删除的一端称为队尾(rear)，允许插入的一端称为队头 (Front),队列的操作原则是先进先出的，所以队列又称作FIFO表(First In First Out)

  • 顺序存储

  • 顺序存储

  • 环形队列

  • 环形队列

  • 环形队列

  • 技术案例：多线程中的就绪队列和阻塞队列
  • 主要操作：入队、出队

队列的接口:

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public interface Quene {

    // 获取队列长度
    public int getSize();

    // 队列是否为空
    public bollean isEmpty();

    // 入队
    public void enquence(Object e);

    // 出队
    public Object dequence();

    // 取队首元素
    public Object peek();

}

其他队列

双端队列Deque

  • 双端队列Deque

  • 双端队列Deque

  • 操作受限的双端队列Deque

Java中的栈和队列类

  • Stack类： 已过时，因为public class Stack<E> extends Vector<E>
  • Quene 队列类
  • Deque 双端队列（一般默认受限规则为栈操作）

例：用栈实现10进制转2进制

Ⅰ. Java语言实现

java
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
package com.webpro.stackquene;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 10进制转换成2进制
 * @author suxia
 *
 */
public class TestConvert {

	public static void main(String[] args) {
		// 给定一个10进制数
		int n = 100;
		
		// 定义一个空栈
		Deque<Integer> stack = new LinkedList<Integer>();
		
		// 把10进制数转2进制数
		int t = n; // 被除数
		
		do{
			// 除以2求余数
			int mod = t % 2;
			
			// 输出余数
//			System.out.println(mod);
			stack.push(mod);
			
			// 除以二得到商
			// 使用商做被除数
			t = t / 2;
			
		}while(t > 0); // 商>0
		
		// 输出结果
		System.out.print(n + "  --------> ");
		while(!stack.isEmpty()) {
			System.out.print(stack.pop());
		}
	}
}

Ⅱ. C语言实现

c
1
// I am C

Disruptor并发框架中的Quene

Disruptor框架介绍

  • 极高性能、并发、无锁的编程框架 - Disruptor

  • 建立在JVM平台上

  • 每秒可处理6百万订单[官方自述]

  • 运行在内存中

  • 采用事件源驱动方式

  • 无锁的Queue（高并发无锁队列事件）

[RingBuffer]是Disruptor的核心

RingBuffer采用数组实现，无首尾指针

  • Quene:

  • Quene

  • RingBuffer是一个环形队列，起到缓存的效果：

  • RingBuffer => RingBuffer

随着不停的填充RingBuffer，序号会一直增长，直到超过这个环的最大长度（会覆盖旧的序号）

如何计算序号指向的元素？采用mod运算，序号%长度=索引，例如计算上图10的索引，10%8=2，在第2的位置

关于设置环的最大长度。上图的环长度只有8，在实际情况>>8。长度尽量设置成2n，比如1024、2048

为什么长度尽量设置成2n？如此可采用”与”运算计算索引号，即序号&(长度-1)=索引号，其效率要高于mod计算效率

通过”生产者->RingBuffer->消费者”运作，下图是一个最简单的处理链

  • 生产者->RingBuffer->消费者

实际情况中，生产者和消费者必定是多个线程执行。

树和二叉树

树的基本概念

什么是树？

树状图是一种数据结构，它是由n（n>=1）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：
每个节点有零个或多个子节点；没有父节点的节点称为根节点；每一个非根节点有且只有一个父节点；除了根节点外，每个子节点可以分为多个不相交的子树；

  • 树

树（tree）是包含n（n>0）个结点的有穷集，其中：

  • （1）每个元素称为结点（node）；
  • （2）有一个特定的结点被称为根结点或树根（root）。
  • （3）除根结点之外的其余数据元素被分为m（m≥0）个互不相交的集合T1，T2，……Tm-1，其中每一个集合Ti（1<=i<=m）本身也是一棵树，被称作原树的子树（subtree）。

下面的关于Tree的术语主要来自维基百科

术语 中文 描述
Root 根节点 The top node in a tree.
Child 子节点 A node directly connected to another node when moving away from the Root.
Leaf 叶子节点 A node with no children
Edge 边 The connection between one node and another.
Path 路径 A sequence of nodes and edges connecting a node with a descendant.
Height 节点高度 The height of a node is the number of edges on the longest path between that node and a leaf.
Level 层级 The level of a node is defined by 1 + (the number of connections between the node and the root).
Depth 深度 The depth of a node is the number of edges from the tree’s root node to the node.
Degree 度 The number of subtrees of a node.

相关术语 中文版

  • 节点的度：一个节点含有的子树的个数称为该节点的度；
  • 叶节点或终端节点：度为0的节点称为叶节点；
  • 非终端节点或分支节点：度不为0的节点；
  • 双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；
  • 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；
  • 兄弟节点：具有相同父节点的节点互称为兄弟节点；
  • 树的度：一棵树中，最大的节点的度称为树的度；
  • 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
  • 树的高度或深度：树中节点的最大层次；
  • 堂兄弟节点：双亲在同一层的节点互为堂兄弟；
  • 节点的祖先：从根到该节点所经分支上的所有节点；
  • 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。
  • 森林：由m（m>=0）棵互不相交的树的集合称为森林；

下面通过几个图解释树的几个比较重要的概念

Edge、Root、Leaf

  • Edge、Root、Leaf

Path

  • Path

Height

  • Height

需要注意的是叶子节点的高度为0，如果树只有一个节点，那么这个节点的高也是0

Depth

  • Depth

需要注意的是根节点的深度（Depth）是0.

从Height和Depth的对比，它们的方向刚好是相反的。
对于Height和Depth不用死记，我们可以把树倒过来看，也就是我们现实生活当中的树，求某个节点的Height那肯定是从根部往上的方向；
如果是求某个节点的深度，方向肯定是向下的。

Level

  • Level

节点的Level是从1开始的，Level = Depth+1，根节点的Level=1

也有很多书籍上Level是从0开始的，这样的话Level就等于Depth，根节点的Level=0

二叉树

二叉树是一个每个最结最多只能有两个分支的树，左边的分支称之为左子树，右边的分支称之为右子树。

也就是说二叉树节点的度最大也就是2，而普通的树，节点的度是没有限制的。

二叉树的分类

完美/满二叉树(Perfect Binary Tree)

完美二叉树（满二叉树）。完美二叉树满足两个特性：

  1. 所有的几点都包含两个子节点
  2. 所有的叶子节点的Height或者Level都相等

例：

Level

完全二叉树(Complete Binary Tree)

完全二叉树是 除了最后一层都是满的（都有两个子节点），并且最后一层的节点是从左往右排列的。
完全二叉树，通俗点说就是节点按层从左往右排列。如果最后一层排满了就是完美二叉树，没有满则是完全二叉树。
所以完美二叉树一定是完全二叉树，完全二叉树不一定是完美二叉树。

一个完全二叉树可以高效的使用数组来表示。

例：

Level

完满二叉树(Full Binary Tree)

完满二叉树就简单了，就是每个节点都有两个子节点。也就是说它比完美二叉树少了一个条件。

例：

Level

二叉树实现

二叉树的遍历策略

将整个二叉树分为三部分

  • 根
  • 左子树
  • 右子树

遍历方式

  • 方式一
    • 先序（根）遍历 根->左子->右子
    • 中序（根）遍历 左子->根->右子
    • 后序（根）遍历 左子->右子->根
  • 方式二
    • 按层次遍历

例：

Level

  • 先序遍历（DLR）: 1 4 5 2 3 6 7
  • 中序遍历（LDR）: 4 5 1 3 2 6 7
  • 后序遍历（LRD）: 5 4 3 7 6 2 1

例题：

已知某二叉树，其
后序遍历结果为：5 4 3 7 6 2 1，
中序遍历结果为：4 5 1 3 2 6 7，
求其先序遍历（DLR）结果？

解：

∵ 后序遍历顺序为左子->右子->根

∴ 可知root节点为 1

由中序遍历结果得下图

Level

在分析根1的左子树，由于 4 5 是按照中序遍历排列，可推得
4为左子树的根，5为左子树的根的右子
或者
5为左子树的根，4为左子树根的左子

由于在后序遍历中排列顺序为 5 4 3 7 6 2 1，
5 4 是根1的左子树，顺序为左子->右子->根，由于左子树至少有根，因此排列顺序为右子->根，即得到如下图：

Level

现在我们来分析root的右子树排列状态：

由后序遍历结果 3 7 6 2 得2为右子树得根，又中序遍历结果为 3 2 6 7
因此我们可以得出下图：

Level

后序遍历结果 6 7 ， 中序遍历结果 7 6，易得7为根，6为右子，得出二叉树图形为：

Level

得先序遍历结果为：1 4 5 2 3 6 7

按层次遍历（广度优先搜索）

结果为 1 4 2 5 3 6 7

二叉树接口

二叉链表节点

java
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
package com.webpro.btree;
/**
 * 二叉链表的节点
 * @author suxia
 *
 */
public class Node {
	
	public Object value;     // 节点值
	public Node leftChild;   // 左子树引用
	public Node rightChild;  // 右子树引用
	
	public Node(Object value, Node leftChild, Node rightChild) {
		super();
		this.value = value;
		this.leftChild = leftChild;
		this.rightChild = rightChild;
	}
	
	public Node(Object value) {
		super();
		this.value = value;
		this.leftChild = null;
		this.rightChild = null;
	}

	@Override
	public String toString() {
		return "Node [value=" + value + ", leftChild=" + leftChild + ", rightChild=" + rightChild + "]";
	}
	
}

二叉树接口

java
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
62
63
64
65
66
67
68
package com.webpro.btree;
/**
 * 二叉树的接口
 * @author suxia
 *
 */
public interface BinaryTree {
	
	/**
	 * 是否空树
	 * @return
	 */
	public boolean isEmpty();
	
	/**
	 * 树节点数量
	 * @return
	 */
	public int size();
	
	/**
	 * 获取二叉树的高度
	 * @return
	 */
	public int getHeight();
	
	/**
	 * 查询指定值的节点
	 * @param value
	 * @return
	 */
	public Node findKey(Object value);
	
	/**
	 * 前序递归遍历
	 */
	public void preOrderTraverse();
	
	/**
	 * 中序递归遍历
	 */
	public void inOrderTraverse();
	
	/**
	 * 后序递归遍历
	 */
	public void postOrderTraverse();
	
	/**
	 * 中序遍历非递归操作
	 */
	public void inOrderByStack();
	
	/**
	 * 前序遍历非递归操作
	 */
	public void preOrderByStack();
	
	/**
	 * 后序遍历非递归操作
	 */
	public void postOrderByStack();
	
	/**
	 * 按照层次遍历二叉树
	 */
	public void levelOrderByStack();
}

二叉树操作

未完待续

文章作者: Bill
文章链接: http://blog.webpro.ltd/2019/09/29/study-datastructure/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Bill's blog！
数据结构 算法
评论
繁