数据结构篇 - Java

文章目录

数据结构篇 - Java
- 一、学习路线梳理
- 二、入门
- - 2.1 复杂度的分析与度量
  - - 时间复杂度
    - 空间复杂度
    - 复杂度分析
  - 2.2 递归
  - 2.3 ADT
- 三、基本数据结构
- - 3.1 数组
  - 3.2 向量 - Vector
  - 3.3 列表 ( 链表 )
  - 3.4 栈
  - 3.5 队列
  - 3.6 二叉树
  - - 结构
    - 操作方法
    - 示例代码
  - 3.7 图
  - 3.8 搜索/查找树
- 四、高级数据结构
- - 4.1 高级搜索树
  - 4.2 词典
  - 4.3 优先级队列
- 五、算法
- - 5.1 再说
结束

数据结构篇 - Java

我觉得我这里面的内容还是非常粗浅的，我也没时间深入学咯，先干正事

文章目录
《数据结构（C++语言版）》
《图解算法数据结构》

一、学习路线梳理

基础知识
基本数据结构
- 向量
- 列表
- 栈/队列
- 二叉树
- 图
- 搜索树
高级数据结构
- 高级搜索树
- 词典
- 优先队列
算法
- 串
- 排序

二、入门 2.1 复杂度的分析与度量

我认为主要是讲述在某些场景下的数据结构的一个效率问题，主要是从时间复杂度/空间复杂度展开，一般分为最好、最坏以及平均情况

以下摘录《图解算法数据结构》—— Krahets

时间复杂度

根据从小到大排列，常见的算法时间复杂度主要有

O(1) < O(logN) < O(N) < O(NlogN) < O(N2) < O(2N) < O(N!)

简单来说，使用算法进行问题解决的时候，输入的数据量恒定为 N，我们要操作 y 次才能得到我们最终想要的结果

最佳情况 Ω(1) ： nums = [7, a, b, c, …] ，即当数组首个数字为 77 时，无论 nums 有多少元素，线性查找的循环次数都为 11 次；
最差情况 O(N) ： nums = [a, b, c, …] 且 nums 中所有数字都不为 77 ，此时线性查找会遍历整个数组，循环 NN 次；
平均情况 Θ ：需要考虑输入数据的分布情况，计算所有数据情况下的平均时间复杂度；例如本题目，需要考虑数组长度、数组元素的取值范围等；

空间复杂度

空间复杂度涉及的空间类型有：

输入空间：存储输入数据所需的空间大小；初始数据大小
暂存空间：算法运行过程中，存储所有中间变量和对象等数据所需的空间大小；数据计算时占用空间
输出空间：算法运行返回时，存储输出数据所需的空间大小；最终结果大小

根据从小到大排列，常见的算法空间复杂度有

O(1) < O(logN) < O(N) < O(N2) < O(2N)

复杂度分析

好难啊，我回来再看…

常数

对数

线性

多项式

指数

2.2 递归

简单理解，就是自己调用自己，然后写一个判断作为契机暂停这种递归

线性递归
递归模式
递归消除
二分递归

直接自闭了我靠…

2.3 ADT

抽象数据类型（Abstract Data Type，ADT）

ADT（数学模型）_百度百科 (baidu.com)

我觉得上面的资料对于我来说很难理解，简单描述就是：一个数学模型+这个数学模型上的操作，例如

数学模型：HashMap
操作方式：get()、put()

用现代编程语言的说法，，定义一个全新的数据类型，第一，需要提供数据存储的方式；第二，需要提供数据的操作方式

三、基本数据结构

非常贴近我们的生活，例如我们乘坐地铁人多时需要排队（队列），一落凳子（栈）等等

3.1 数组

数组：元素的内存地址与下表之间呈连续线性关系，可通过对应下标访问内部元素

 int[] ints = new int[]{1, 2, 3};
for (int anInt : ints) {
	System.out.println(anInt);
}

3.2 向量 - Vector

这个向量在Java中是Util包里的一个类，实现了类似于动态数组的功能

sync 线程安全类
用在事先不知道数组的大小，或者只是需要一个可以改变大小的数组的情况

向量的原理就是县城数组的一种抽象与泛化，里面的秩可以理解为数组的下标，但是它作为ADT的一种抽象数据结构，也实现了ADT内的数据操作接口

Java Vector 类 | 菜鸟教程 (runoob.com)

序号	方法描述
1	void add(int index, Object element) 在此向量的指定位置插入指定的元素。
2	boolean add(Object o) 将指定元素添加到此向量的末尾。
3	boolean addAll(Collection c) 将指定 Collection 中的所有元素添加到此向量的末尾，按照指定 collection 的迭代器所返回的顺序添加这些元素。
4	boolean addAll(int index, Collection c) 在指定位置将指定 Collection 中的所有元素插入到此向量中。
5	void addElement(Object obj) 将指定的组件添加到此向量的末尾，将其大小增加 1。
6	int capacity() 返回此向量的当前容量。
7	void clear() 从此向量中移除所有元素。
8	Object clone() 返回向量的一个副本。
9	boolean contains(Object elem) 如果此向量包含指定的元素，则返回 true。
10	boolean containsAll(Collection c) 如果此向量包含指定 Collection 中的所有元素，则返回 true。
11	void copyInto(Object[] anArray) 将此向量的组件复制到指定的数组中。
12	Object elementAt(int index) 返回指定索引处的组件。
13	Enumeration elements() 返回此向量的组件的枚举。
14	void ensureCapacity(int minCapacity) 增加此向量的容量（如有必要），以确保其至少能够保存最小容量参数指定的组件数。
15	boolean equals(Object o) 比较指定对象与此向量的相等性。
16	Object firstElement() 返回此向量的第一个组件（位于索引 0) 处的项）。
17	Object get(int index) 返回向量中指定位置的元素。
18	int hashCode() 返回此向量的哈希码值。
19	int indexOf(Object elem) 返回此向量中第一次出现的指定元素的索引，如果此向量不包含该元素，则返回 -1。
20	int indexOf(Object elem, int index) 返回此向量中第一次出现的指定元素的索引，从 index 处正向搜索，如果未找到该元素，则返回 -1。
21	void insertElementAt(Object obj, int index) 将指定对象作为此向量中的组件插入到指定的 index 处。
22	boolean isEmpty() 测试此向量是否不包含组件。
23	Object lastElement() 返回此向量的最后一个组件。
24	int lastIndexOf(Object elem) 返回此向量中最后一次出现的指定元素的索引；如果此向量不包含该元素，则返回 -1。
25	int lastIndexOf(Object elem, int index) 返回此向量中最后一次出现的指定元素的索引，从 index 处逆向搜索，如果未找到该元素，则返回 -1。
26	Object remove(int index) 移除此向量中指定位置的元素。
27	boolean remove(Object o) 移除此向量中指定元素的第一个匹配项，如果向量不包含该元素，则元素保持不变。
28	boolean removeAll(Collection c) 从此向量中移除包含在指定 Collection 中的所有元素。
29	void removeAllElements() 从此向量中移除全部组件，并将其大小设置为零。
30	boolean removeElement(Object obj) 从此向量中移除变量的第一个（索引最小的）匹配项。
31	void removeElementAt(int index) 删除指定索引处的组件。
32	protected void removeRange(int fromIndex, int toIndex) 从此 List 中移除其索引位于 fromIndex（包括）与 toIndex（不包括）之间的所有元素。
33	boolean retainAll(Collection c) 在此向量中仅保留包含在指定 Collection 中的元素。
34	Object set(int index, Object element) 用指定的元素替换此向量中指定位置处的元素。
35	void setElementAt(Object obj, int index) 将此向量指定 index 处的组件设置为指定的对象。
36	void setSize(int newSize) 设置此向量的大小。
37	int size() 返回此向量中的组件数。
38	List subList(int fromIndex, int toIndex) 返回此 List 的部分视图，元素范围为从 fromIndex（包括）到 toIndex（不包括）。
39	Object[] toArray() 返回一个数组，包含此向量中以恰当顺序存放的所有元素。
40	Object[] toArray(Object[] a) 返回一个数组，包含此向量中以恰当顺序存放的所有元素；返回数组的运行时类型为指定数组的类型。
41	String toString() 返回此向量的字符串表示形式，其中包含每个元素的 String 表示形式。
42	void trimToSize() 对此向量的容量进行微调，使其等于向量的当前大小。

3.3 列表 ( 链表 )

向量与列表非常相似，都是属于一种，依次排列的、可变的数组，但是它们在实现方式上有所不同

数据结构	实现
向量（Vector）	基于数组实现，因此也被称作数组列表（ArrayList）
列表（List）	基于链表实现，是对链表结构的抽象与扩展

如果从我的角度来看，列表，不如叫做链表

插入时，在已知位置的情况下只需要改变节点的引用即可
获取某个数据时，需要对这个链表进行遍历，所以时间复杂度为O(n)

假如通过代码去实现的话，你会发现很像树状结构，但是它的引用是单链路结构，而不像树不断岔开

3.4 栈

先入后出的数据结构，就像乌鸦喝水的故事，不断的往一个瓶里扔石头，如果要取出石头，也要从最上面的那颗开始取

Java中已经有实现了栈的数据结构类

Stack

数据结构篇 - Java

Java相关栏目本月热门文章