数据结构
Last updated
Was this helpful?
Last updated
Was this helpful?
MST-数据结构java实现:https://www.cnblogs.com/yangyquin/p/4921664.html
算法题网址:https://leetcode-cn.com/problemset/all/
头条:https://leetcode-cn.com/explore/featured/card/bytedance/245/data-structure/1049/
newCoder:https://www.nowcoder.com/contestRoom
数据结构分类:
一、列表型
1、数组
开辟一片连续的空间,将元素依次放入其中;
数组的好处:可以进行随机访问,只需要一个下标就可以访问到该元素;但插入和删除会比较耗费时间,插入和删除操作都需要将之后的元素进行整体的移动,腾出空间来进行对应的操作。
2、链表
每一个节点通过 next 值链接起来;查找元素耗费时间O(n),需要一个计数器,从表头开始顺着 next 依次往后找,数到第 n 个就可以将第 n 个元素取出来;但插入和删除不会耗费时间,插入操作只需要将插入前后的两个集成打断,再将插入的元素连接起来即可;删除操作只要将要删除的元素跳过即可,
3、队列
不支持随机访问,只支持 push 和 pop 操作,push 将元素放进去,pop 将元素拿出来,拿出的顺序是先进先出
4、栈
不支持随机访问,只支持 push 和 pop 操作,push 将元素放进去,pop 将元素拿出来,拿出的顺序是先进后出
二、树型
1、二叉树
每个节点最多有两个孩子节点,分为左孩子节点和右孩子节点;
二叉树要点:
a.二叉树具有唯一的根节点;
b.二叉树中每个节点最多有两个孩子,每个节点最多有一个父亲节点;一个孩子也没有的叫做叶子节点
c.二叉树具有天然的递归结构【每个节点的左子树也是二叉树、每个节点的右子树也是二叉树】
2、搜索树
a.二分搜索树是二叉树
b.二分搜索树的每个节点的值:大于其左子树的所有节点的值且小于其右子树的所有节点的值
c.二分搜索树的每个子树也是二分搜索树
d.存储的元素必须具有可比较性【存储自定义数据类型,必须自定义好数据的比较方式】
3、优先队列
a.普通队列:先进先出,后进后出
b.优先队列:出队顺序和入队顺序无关;和优先级相关
三、图形
1、无向图
每个节点之间没有方向,可以从 a--b ,也可以 b--a ,但每个边有权重
2、有向图
所有的边都是单向的,只能从 a--b,b不能到 a,要让 b 到 a 则必须再加一条边
3、有向无环图
可以描述任务之间的层级关系,
相关算法:深度优先遍历【能够看到图的每个节点】
广度优先遍历【走迷宫,识别联通块】
拓扑排序【有很多先后的依赖关系,先做哪一个】
最短路径/最小生成树