数据结构与算法
2022-08-20 12:41:54 0 举报AI智能生成
数据结构知识点梳理
作者其他创作
大纲/内容
算法
排序
内部——七大排序算法
插入排序
直接插入排序——稳定，O（n^2），当数组近乎有序时，插排效率还是很高的，近乎O（n）
希尔排序——不稳定，O（n^1.3-1.5）
分组，组内插排保证有序，不断/2缩小分组，直至分组为1
选择排序
选择排序——不稳定，O（n^2)
普通：每次在左边无序区间选最大元素，放入无序区间最右，缩小无序范围
进阶：遍历同时找到无序中最小和最大，分别放最左和最右，注意交换成功最小后，注意是否有影响到最大
堆排序——不稳定，O（nlogn)
先将数据堆化（升序建大根堆，降序建小根堆）（堆化：从最后一个非叶子节点到根节点，对每个结点进行下沉操作）
然后将堆顶元素跟最后元素交换，再重新堆化
交换排序
冒泡排序——稳定，O（n^2)
快排——不稳定，O（nlogn)
当数组近乎有序时，快排反而退化为O(n^2），因为二叉树结构单边倾斜
归并排序——稳定，O（nlogn）
外部
桶排序
基数排序
计数排序
分治
贪心
动规
二分
回溯
数据结构
线性结构
顺序表
顺序表的实现
定义——动态数组
准备工作：
构造方法
grow()方法
toString()方法
增加操作
尾部增加
data[size++]=value
头部增加
从后向前依次后移一位用以给头部腾出空间
data[i+1]=data[i]
任意位置增加
与头插法类似，for循环截止条件不同
data[i+1]=data[i]
删除操作
根据索引删
先判断删除位置是否合法
后面的元素覆盖前面的，并注意将删除前的最后一个元素置为0
data[i]=data[i+1]data[size]=0
根据元素值删
只删除第一次出现的元素值
for+ if (data[i] == value)
删除所有与之相等的
for+while(i!=size||data[i]==value))
修改操作
根据索引下标修改元素
注意判断输入的索引下标是否合法
data[index]=newdata
查找操作
是否能查找到
返回boolean类型
根据索引下标查元素
记得判断输入下标是否合法（index<0||index>=size)均不合法
根据元素查索引下标
查到，return(i),查不到，return -1
JDK——ArrayList
链表
链表的实现
单链表（普通）
定义
由Node类（节点类）和SingleList（链表类）两个类组成
其他方法
toString()方法
可将删、修、改的判断Index是否合法抽象为一个方法
增
头插法
链表为空表
if (head == null) {
head = node;
链表不为空
node.next=head;head=node;
中间任意位置插入
先判断输入的索引下标是否合法
if（index==0)——头插
for遍历找要插入位置的前驱节点pre for(int i=0;i<index-1;i++) pre=pre.next;
node.next=pre.next;pre.next=node
尾插法
若链表为空表——可调用头插法
链表不为空——可调用令index=size的中间插入法
删
删除指定索引位置的元素
先判断输入的索引值是否合法
判断删除的是否为头节点
if(index==0)Node temp=head;head=head.next;temp.next=null;size--;
else 用for循环遍历找到删除位置的前一个元素pre
Node cur=pre.next;pre.next=cur.next;cyr.next=null;size--;
根据元素值删除，只删除第一次出现的
头节点就是该元素
if(head.next!=null&&head.val==val)
其他位置删除,还是找前一个元素pre
while(pre.next!=null) if(pre.val==val) 删除操作 pre=pre,next;
根据元素值删元素，删除所有该元素
头节点
while(head!=null&&head.val==val) {删除头节点} if(head.next==null) return
非头节点
while(pre.next!=null) if(pre.val==val) 删除操作 else{pre=pre,next;}
改
修改指定索引位置处的元素
先判断索引值是否合法
for循环遍历找到该索引位置cur，cur.val==newValue
查
根据索引位置查元素并返回查到的元素值
先判断索引位置是否合法
for循环遍历查
查找是否能找到某元素，返回boolean类型
for(Node temp=head;node.next!=null;node=node.next
带虚拟头节点的单链表
虚拟头节点避免了单独处理头节点的特殊情况
虚拟头节点：Node dummyHead=new Node(value:-1),其中value为任意不在链表范围内的值
双链表
定义
头节点head,尾节点tail，每个节点既有前驱pre又有后继next
其他辅助方法
private boolean isRange(int index)
输入的索引是否合法
public String toString()
输出格式
public Node find(int index)
查找指定索引位置的节点或前节点
private void deleteNode(Node node)
删除节点node
增
头插、尾插、中间位置插入
删
删除指定索引位置，删除指定元素值
查
查找是否存在某值，查找具体索引位置的值
改
将指定索引位置的元素的值修改为新的值
带虚拟头节点的双链表
虚拟头节点避免了考虑头节点的特殊情况
JDK——LinkedList
相关面试/笔试题—
https://blog.csdn.net/m0_58652786/article/details/121731740
栈
基于数组实现
常用操作
push() ——入栈
pop() ——返回栈顶元素并删除栈顶
peek() ——返回栈顶元素
单调栈问题
https://blog.csdn.net/m0_58652786/article/details/122715063
应用场景
撤销操作
网页的回退
字符串倒序输出等
队列
基于链表实现
分类
基础队列
Queue
offer()/add
poll()/remove
peek()/element
基于优先级的队列
PriorityQueue
双端队列
Deque
循环队列
应用场景
解决现实情境，比如排队，次序问题
字符串
非线性结构
树形结构
常用的树形结构
二叉树
普通二叉树
左根右
根左右
左右根
层序
完全二叉树
满二叉树
BST——二分搜索树
定义
二叉树
子树根节点大于左子树所有结点，小于右子树所有结点
方法实现
插入add
新插入的结点最后一定插入在了叶子节点，所以可递归判断插左还是插右
判断是否存在某value值
递归找左右子树
查找并返回最大/小值
递归找最左/最右
删除最大/小值并返回
以最小值为例，删除最小值，再将最小值的右子树与最小值的根节点直接相连（递归中删除后返回右即可）
删除值为value的某节点
value值只有左结点没有右节点
删除后直接连接左节点即可
value值只有右节点没有左节点
删除后直接连接右节点即可
value值既有左又有右
找前驱替换value值，所谓前驱，可以是左子树中最大的也可以是右子树中最小的
替换value值
无法直接修改，只能先删除，再插入
注意！BST很高效，但是当BST左右子树高度严重不平衡时，比如退化成单链表
所以，引入了平衡二分搜索树
平衡二分搜索树
AVL——严格平衡，任意子树左右高度差<=1
红黑树——非严格平衡，只有黑节点遵循严格平衡
堆
大根堆/小根堆（基于二叉树）
构造方法
内部是动态数组
根据子节点序号找父节点序号——parent(int k)
根据父节点序号找左右子节点序号——leftChild(int k)、rightChild(int k)
上浮操作——siftUp(int k)
下沉操作——siftDown(int k)
向最大堆中添加一个新元素——add(int val)
将该元素添加到数组末尾，然后进行上浮操作
取到并删除当前堆的最大元素——pollMax()
最大元素即索引为0的，将该元素替换为最后一个元素，然后进行下沉操作
取到当前堆的最大元素——peekMax()
即索引为0的元素
将任意数组堆化——heapify
方式一：不断add元素，当数据量大时，不易操作，不建议
方式二：从最后一个非叶子节点-索引为0的结点依次进行下沉操作，最后一个非叶子节点即最后一个元素的父节点
优先级队列（基于最大堆/最小堆）JDK中内置的PriorityQueue默认是基于最小堆
内置方法
offer()/add()
poll()/remove()
peek()/element()
isEmpty()
自定义优先级
方法一：本类中实现Comparable接口，实现compareTo方法
方法二：新建类，实现Comparator接口，实现compare方法
TopK问题
取大用小（取前k个最大的，则建小根堆）
取小用大（取前k个最小的，建立大根堆）
并查集
字典树——字符串、线段树
散列表（HashMap)
添加键值对——put
根据Key值删除对应的键值对——remove(key)
查找是否存在某key值
查找是否存在某value值
扩容
图
集合框架
Iterable
Collection（接口）
List
ArrayList
顺序表，动态数组
线程不安全
扩容操作：默认扩容为1.5倍，并将原数组拷贝到新数组中
LinkedList
链表
线程不安全
Vector
Stack
线程安全，但是对所有操作直接加synchronized锁，效率极低，是“失败品”不建议使用
CopyOnWriteArratList
读操作不加锁，即只对增删改操作加锁
适用于多读少写的场景，比如黑名单
缺点
因为有数据拷贝，所以内存占用大
只能保证最终的数据一致性，并不能保证实时数据一致性
Queue
PriorityQueue
优先级队列，默认是基于小根堆
泛型类可自定义优先级
实现Comparable接口，覆写compareTo方法
实现Comparator接口，覆写compare方法
函数式编程也很好用
Queue<Student> mypri1 = new PriorityQueue<>(((o1, o2) -> o1.age - o2.age));
Deque
LinkedList
Deque是双端队列接口，LinkedList是实现类，一般队列和栈都用该类
Set
HashSet
本质其实就是HashMap，添加进的元素都是key值，value值为null或者虚值而已
SortedSet
TreeSet
有序的Set集合
Java类库中已有的类（实现过Comparable接口的）可以按照自然排序add
自定义类，必须实现Comparable接口并重写compareTo()方法才能add进去
Map
HashMap
(Key,Value)的键值对，key和value均可以为null
无序，插入顺序并不代表实际存储顺序
线程不安全
解决哈希冲突
闭散列
线性探测——向后查空余
二次探测——对得到的哈希值再次哈希，直到找到不冲突位置
开散列
把冲突位置转换为链表——HashMap使用的
底层结构与扩容问题
JDK1.7
数组+链表（链表是为了解决哈希冲突）
扩容：扩大为两倍后，重新计算原数组在新的数组中的索引位置，拷贝过去
JDK1.8
数组+链表+红黑树（当链表长度超过8（8是由泊松分布得来）且数据总量超过64转红黑树）
扩容：扩大为两倍后，无需重新计算索引位置，元素的位置在原来的位置，或者原来的位置 +oldCap (原来哈希表的长度）
只需要看看原来的 hash 值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引 + oldCap ”
扩容
默认负载因子 α = 填入表中的元素个数/散列表总长度 = 0.75，0.75是对时间和空间的折中
如果内存空间很充足，需要时间效率高的话可以降低α
如果内存空间紧张，时间效率要求不高的话可以提升α
超过α，就会扩容，扩容为原来的两倍，把每个元素重新计算在新数组中的位置拷贝过去
线程不安全
多线程拷贝时 头插 易形成环形链表——所以1.8就改成了尾插，尾插只是不至于死循环，但还是错的
多线程put操作数据易被覆盖丢失
put和get并发时，put时扩容，导致get到null值
put操作步骤
1.哈希运算得到存储索引下标
2.判断数组是否为空，如果为空，先resize初始化
3.根据索引下标插入
如果没有冲突，直接插入主题
如果有冲突，判断Key是否存在
如果存在直接覆盖原value值
如果不存在，如果插入位置是红黑树，直接插入
如果不存在，插入位置是链表，判断链表长度是否大于8
链表长度<8，直接插入链表
链表长度>8，且数据总长度<64，先扩容再插入
链表长度>8，且数据总长度>64，转红黑树插入
Hash算法
1.根据hashcode(key)计算出hashCode值——h = hashCode(key)
哈希函数Hashcode（）方法
常见的MD5算法
2.根据hashcode值计算出hash值——hash = h ^ ( h >>> 16)
为什么要高16位异或低16位，是为了在数组长度即使很小的时候，也保证高低位都参与到了Hash运算中同时不会有太大开销
3.对hash值进行取模得到最后的存储位置——hash&（length-1）
源代码中&length-1其实就是在取模——当 length 总是 2 的n次方时，h& (length-1) 运算等价于对length取模，也就是 h%length，但是 & 比 % 具有更高的效率。
遍历Map
获取所有key集合
Set<K> keys = map.keySet();
获取所有value集合
Collection<V> valusa = map.values();
获取所有key-value键值对
Set<Map.Entry<K,V>> entry = hashMap.entrySet();
for循环遍历
for(Map.Entry<String,Integer> temp : map.entrySet()){
System.out.print(temp.getKey() + "=" + temp.getValue() + " ");
}
LinkedHashMap
key和value都可为null
插入顺序就是输出顺序，在HashMap的基础上维护了一个链表用于记录元素插入顺序
HashTable
线程安全的，但是也是对所有操作直接加synchronized锁，key值不允许为null
ConcurrentMap
ConcurrentHashMap
1.8
数组+链表+红黑树
key值不允许为null
读操作没有加锁(但是使用了 volatile 保证从内存读取结果), 只对写操作进行加锁.
线程安全：CAS+synchronized.
加锁的方式仍然是是用 synchronized, 但是不是锁整个对象, 而是 "锁桶" ,只针对同一个链表的操作进行互斥；只有两个线程访问的恰好是同一个哈希桶上的数据才会锁冲突， 大大降低了锁冲突的概率
当前遇到扩容的线程，只扩容和搬一个元素（搬什么呢，把老数组中的每个key-value重新计算下标放入新数组新位置，只搬移一个，其他元素交给同时间的其他线程干），期间新老数组同时存在
SortedMap
TreeMap
有序的哈希表
Java类库中已有的类（实现过Comparable接口的）可以按照自然排序add
自定义类，必须实现Comparable接口并重写compareTo()方法才能add进去
底层结构：红黑树
key不能为null,value可以为null
迭代器
Iterator
可以遍历所有集合，如Map，List，Set
只能单向向前遍历
无法向集合中添加元素、修改元素、无法获取集合中元素的索引
ListIterator
只能遍历List实现的对象
可以向前也可以向后遍历
可以向集合中添加元素、set方法修改元素、也可以获取集合中元素的索引
0 条评论
下一页
