主要是自己总结使用,写的比较笼统 -_-
- 数组
- 双端队列
- 栈
- 树
- 图
- 堆
- 字典
数组
介绍:
逻辑上是一种线性表,存储上内存可以是连续的和离散的
题目:
实现:
- Java
(1) 最原始的数组:[ ], 内存连续 // 比较底层, java的业务代码不推荐使用
//一维数组
E[] array = new E[array_size]; // 创建长度为 array_size 数据类型为 E的数组
for(int i = 0; i < length; i++){
array[i] = new E(); // 为数组中的每个引用new出一个对象
}
array[i] // invoke ...调用
(2) ArrayList : 可变长度数组,实质是对 [] 的封装, 它的内存是连续的,频繁的插入删除请不要使用
import java.util.ArrayList; //一维数组 ArrayListarr = new ArrayList (); // 增 arr.add(element : E); // 数组末尾添加 arr.add(idx : int, element : E) / / index 处添加 // 避免了繁琐的往后移动数组的操作 // 删 arr.remove(idx :index); //删除索引处的元素 arr.remove(element : E); // 删除数组中所有 element 元素, element 元素可以为空 //改 arr.set(idx: int, element:E); // 将索引idx处的对象更改为E //查 arr.get(idx : int); //查找 idx 处的元素 // more arr.size(); // 返回数组元素个数 arr.isEmpty(); // 数组是否为空 arr.contain(element : E); // 判断某个元素在数组中是否存在 arr.clear(); //清空所有数组;
(3) LinkedList :数组, 内存离散(基于链表实现),频繁插入删除请使用;
// 搞不懂为啥官方不提供一个 Array 的接口,并提供两种实现, 估计只有内存连续的才被定义为数组 import java.util.LinkedList; LinkedListarr = new LinkedList ();
双端队列
介绍:
可以从队列两端插入、删除、查询元素
题目:
实现:
- Java :队列(双端)
import java.util.Deque;
import java.util.ArrayList;
Deque deq = new ArrayDeque(); // 创建一个双端队列
que.isEmpty() -> true/false; // 判断队列是否为空
// 入队
que.offerFirst(element : E) -> true/false; // 从队首入队,如果队列空间不够返回 null
que.offerLast(element : E) -> true/false; // 从队尾入队,如果队列空间不够返回 null
//查询
que.peekFirst()-> element : E; // 查询队首元素
que.peekLast()-> element : E; // 查询队尾元素
//出队
que.pollFirst()-> element : E; // 从队首出队
que.pollLast() -> element : E; // 从队尾出队
栈
介绍:
先入后出、函数调用
题目:
实现:
- Java 实现 :(Java支持的 Stack 类过旧, 官方推荐使用双端队列实现)
import java.util.Deque;
import java.util.ArrayList;
Deque stk = new ArrayDeque(); // 使用一个双端队列创建一个栈
stk.isEmpty() -> true/false; // 判断栈是否为空
stk.offerFirst(element : E) ; //入栈;
stk.peekFirst() -> element : E; // 得到栈首元素, 如果栈为空返回null
stk.pollFirst(); -> return element : E // 得到栈首元素并移除,如果栈为空返回null
树
介绍:
各种各样的树,但是这里只介绍二叉树
题目:
实现:
- Java 实现 :java中并没有现成的类(这里写一种构造方法)
class Node{ // Tree Node E item; Node left; Node right; Node(E element) { this.item = element;} } Node root = new Node<>() Node newNode = new Node<>(); // construct newNode root.left = newNode; Node newNode = new Node<>(); // construct newNode root.right = newNode; // 需要注意 java 中left, right 会被自动初始化为null, 其他语言需手动
图
介绍:
图吗,几个节点之间互相连接
题目:
实现:
- Java 实现 :java没有提供图的官方api呦,@_@, 这里手动实现
(1)邻接矩阵 : 适合用于实现稠密图
// 使用 java 自带的二维数组实现
// 节点
int numNode = ?;
int numEdge = ?;
String [] nodes = new String[];
class Edge{
int src;
int dst;
int cost;
}
Edge edgs = new Edge[numEdge];
//创建表
E[][] graph = new E[numNode][numNode]; // 创建邻接矩阵
int src, dst;
for(Edge e : edges){
src = e.src;
dst = e.dst;
graph[src][dst] = e.cost; //有向图
// 若为无向图, 还需添加
graph[dst][src] = e.cost; //有向图
}
(2)邻接表:使用于稀疏矩阵
// 使用 LinkedList 实现
int numNode = ?;
int numEdge = ?;
String [] nodes = new String[];
class Edge{
int src;
int dst;
int cost;
}
Edge edgs = new Edge[numEdge];
class GraphNode{
int dst;
int cost;
GraphNode(int dst, int cost){
this.dst = dst;
this.cost = cost
}
}
LinkedList> graph= new LinkedList>(); // 创建邻接表;
for(int i = 0; i < numNode; i++){ /
graph.add(new LinkedList());
}
for(Edge e: edges){
src = graph.get(e.src);
src.add(new GraphNode(e.dst, e.cost))
}
// 当然也可以自定义链表实现
堆
介绍:
实质是优先队列 (大顶堆:当前节点的值大于左右孩子的值 / 小顶堆当前节点的值小于左右孩子的值)
题目:
实现:
- Java 实现 :
import java.util.PriporityQueue; // 需要添加可比较元素,默认升序 import java.util.Comparator PriporityQueueheap = new PriporityQueue (); heap.offer(element : E); // 向堆中添加元素 heap.peek(element : E): // 检索头部 heap.poll(element : E); //检索头部并删除 heap.size(); //返回队列元素数目; heap.isEmpty(); //是否为空; heap.clear(); // 清空; // 对于E是任意类的情况, 需要定义比较器 // 如果 E 是一个 雇员类 employee class Employee{ int id; } // 按照员工 id 排序,比较器可以这样定义 Comparator compareById = (Employee o1, Employee o2) -> o1.id.compareTo( o2.id); PriporityQueue heap = new PriporityQueue (compareById); // 定义带有比较器的堆
字典
介绍: 本质是散列表, 常用于暂存数据库中取出来的数据;
题目:
实现:
- Java 实现 :
import java.util.HashMap; HashMapdict = new HashMap (); //创建一个HashMap dict.put(key:T, vaule:E); // 字典中添加元素, 或者更改某键处的值 dict.get(key:T); //访问元素 dict.remove(key:T); // 删除元素 dict.containsKey(key:T) ; //是否包含某个键值 K dict.size(); dict.isEmpty(); // 字典遍历 Iterator > iterator = dict.entrySet().iterator(); // 创建迭代器 while(iterator.hasNext){ Map.Entry entry = iterator.next(); entry.getKey(); entry.getValue(); }
参考自菜鸟教程



