企业网站关键词放几个,wordpress注册用户无法登录,中山网站建设 760,中国建设网站官方网站数据结构基础小结
概述
什么是算法#xff1f;
在计算机领域里#xff0c;算法是一系列程序指令#xff0c;用于处理特定的运算和逻辑问题。
衡量算法优劣的主要标准是时间复杂度和空间复杂度。
什么是数据结构#xff1f;
数据结构#xff0c;对应的英文单词是 dat…数据结构基础小结
概述
什么是算法
在计算机领域里算法是一系列程序指令用于处理特定的运算和逻辑问题。
衡量算法优劣的主要标准是时间复杂度和空间复杂度。
什么是数据结构
数据结构对应的英文单词是 data structure是数据的组织、管理和存储格式其使用目的是为了高效地访问和修改数据。
数据结构都有哪些组成方式
基本数据结构 线性结构 线性结构是最简单的数据结构包括数组、链表以及由它们衍生出来的栈、 队列、哈希表。 树 树是相对复杂的数据结构其中比较有代表性的是二叉树由它又衍生出了二叉堆之类的数据结构。 图 图是更为复杂的数据结构因为在图中会呈现出多对多的关联关系。
其他数据结构
除上述所列的几种基本数据结构以外还有一些其他的千奇百怪的数据结构。它们由基本数据结构变形而来用于解决某些特定问题如跳表、哈希链表、位图等
时间复杂度
时间复杂度是对一个算法运行时间长短的量度。它描述了算法运行时间与输入大小之间的关系记作 T(n)O(f(n))。
时间复杂度通常用大 O 记号O表示来表示表示算法执行时间的上界。
因为渐进时间复杂度用大写 O 来表示所以也被称为大 O 表示法。
O(1) O(logn) O(n) On²)
空间复杂度
空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度它同样使用了大 O 表示法记作 S(n)O(f(n))。
线性结构
什么是数组
数组是由有限个相同类型的变量所组成的有序集合它的物理存储方式是顺序存储访问方式是随机访问。
利用下标查找数组元素的时间复杂度是 O(1)中间插入、删除数组元素的时间复杂度是 O(n)。
什么是链表
链表是一种链式数据结构由若干节点组成每个节点包含指向下一节点的指针。链表的物理存储方式是随机存储访问方式是顺序访问。和数组相反
查找链表节点的时间复杂度是 O(n)中间插入、删除节点的时间复杂度是 O(1)。
什么是栈
栈是一种线性逻辑结构可以用数组实现也可以用链表实现。栈包含入栈和出栈操作遵循先入后出的原则FILO。
什么是队列
队列也是一种线性逻辑结构可以用数组实现也可以用链表实现。队列包含入队和出队操作遵循先入先出的原则FIFO。
什么是散列表
散列表也叫哈希表是存储 Key-Value 映射的集合。对于某一个 Key散列表可以在接近 O(1) 的时间内进行读写操作。
散列表通过哈希函数实现 Key 和数组下标的转换通过【开放寻址法】和【链表法】来解决哈希冲突。 开放寻址法当发生冲突时它会尝试在哈希表中的其他位置继续寻找可用的位置来存储数据直到找到一个空闲的位置为止。 具体来说开放寻址法通过以下方式处理哈希冲突 线性探测法发生冲突时依次检查下一个位置直到找到一个空闲位置。二次探测法发生冲突时按照某个固定的二次探测序列依次检查下一个位置直到找到一个空闲位置。双重哈希法使用两个不同的哈希函数来计算下一个探测位置。 开放寻址法的优点是不需要额外的数据结构来存储冲突的数据节省了内存空间。但它的缺点是容易产生聚集性冲突导致哈希表的性能下降。 链表法它在哈希表的每个桶中维护一个链表或其他数据结构如红黑树当发生冲突时将冲突的数据存储在该桶的链表中。 具体来说链表法通过以下方式处理哈希冲突 将哈希表的每个桶初始化为一个空链表。当发生哈希冲突时将新的数据插入到对应桶的链表中。 链表法的优点是容易实现且能够有效地处理较多的哈希冲突。然而当链表过长时会影响哈希表的性能因为查找操作需要在链表上进行线性搜索。
树
什么是树
树是 n 个节点的有限集有且仅有一个特定的称为根的节点。
当 n1 时其余节点可分为 m 个互不相交的有限集每一个集合本身又是一个树并称为根的子树。
什么是二叉树
二叉树是树的一种特殊形式每一个节点最多有两个孩子节点。 二叉树包含【完全二叉树】和【满二叉树】两种特殊形式。 完全二叉树Complete Binary Tree除了最后一层可能不满外其他层的节点都必须是满的并且最后一层的节点都尽量靠左排列。 具体特点如下 所有叶子节点都集中在二叉树的最后两层。最后一层的叶子节点都靠左排列。如果一个节点只有右子树而没有左子树那么它必定是最后一层的节点。 完全二叉树在数组中的存储非常高效因为它的特殊结构允许用数组的形式表示无需使用额外的指针。 满二叉树Full Binary Tree除了叶子节点外每个节点都有两个子节点即每个节点的度数都是 2。 具体特点如下 所有非叶子节点都有两个子节点。所有叶子节点都在同一层上。 满二叉树的高度是固定的由节点数决定且在给定节点数下它的高度是最小的。但是满二叉树并不常见一般完全二叉树更为常见。 二叉树的遍历方式有四种根据遍历节点之间的关系可以分为以下 4 种方式 前序遍历Pre-order Traversal先访问根节点然后按照左子树、右子树的顺序递归遍历。根左右中序遍历In-order Traversal先按照左子树的顺序递归遍历然后访问根节点最后按照右子树的顺序递归遍历。左根右后序遍历Post-order Traversal先按照左子树、右子树的顺序递归遍历然后访问根节点。左右根层序遍历Level-order Traversal从上到下逐层遍历二叉树的节点同一层节点按照从左到右的顺序访问。上到下 另外从更宏观的角度划分二叉树的遍历方式可以分为两大类 深度优先遍历Depth-First Traversal以深度为优先级的遍历方式即先访问根节点然后递归遍历左子树和右子树。根左右广度优先遍历Breadth-First Traversal以广度为优先级的遍历方式即按照层序遍历的顺序逐层遍历二叉树的节点。
深度优先遍历适用于查找、搜索等问题栈而广度优先遍历适用于层次遍历和最短路径等问题队列。
什么是二叉堆
二叉堆是一种特殊的完全二叉树分为最大堆和最小堆。
在最大堆中任何一个父节点的值都大于或等于它左、右孩子节点的值。在最小堆中任何一个父节点的值都小于或等于它左、右孩子节点的值。
什么是优先队列
优先队列分为最大优先队列和最小优先队列。
在最大优先队列中无论入队顺序如何当前最大的元素都会优先出队这是基于最大堆实现的。在最小优先队列中无论入队顺序如何当前最小的元素都会优先出队这是基于最小堆实现的
图
什么是图
图是由一组节点顶点和连接这些节点的边组成的集合。
节点表示实体边表示节点之间的关系。
图可以是有向图Directed Graph即边有方向性也可以是无向图Undirected Graph边没有方向性。
图的分类
简单图图中没有自环和重复的边。带权图图的边带有权重表示节点之间的距离或代价。连通图任意两个节点之间都有路径连接。有向无环图DAG没有环的有向图常用于表示任务依赖关系。
图的表示方式
邻接矩阵使用二维数组表示节点之间的连接关系。邻接表使用链表或数组表示节点的邻居节点。
常见图算法
广度优先搜索BFS用于在图中查找最短路径或层次遍历。深度优先搜索DFS用于查找图中的所有路径或判断是否存在环。Dijkstra 算法用于找到带权图中的最短路径。Kruskal 算法用于求最小生成树适用于带权无向图。拓扑排序用于有向无环图中的任务调度。
实际应用
网络通信图可用于表示计算机网络中的节点和连接。社交网络图可用于表示用户之间的关系进行社交网络分析。路径规划图可用于地图导航、GPS 定位等。数据库查询优化用图的拓扑排序来优化数据库查询计划。任务调度用有向无环图表示任务依赖实现任务调度和并行处理。 BFS - 广度优先搜索Breadth-First SearchDFS - 深度优先搜索Depth-First SearchDAG - 有向无环图Directed Acyclic GraphGPS - 全球定位系统Global Positioning System 红黑树
红黑树是一种自平衡二叉搜索树通过颜色调整和旋转操作它在插入和删除节点时能够自动调整结构保持树的平衡性从而保证查找、插入和删除操作的时间复杂度稳定在 O(log n)。
红黑树特点
每个节点都是红色或黑色。根节点是黑色。叶子节点空节点都是黑色。红色节点的子节点都是黑色。 RED 节点的 parent 都是 BLACK从根节点到叶子节点的所有路径上不能有 2 个连续的 RED 节点 从任意节点到其每个叶子节点的路径上包含相同数量的黑色节点即相同的黑色高度。
红黑树的应用
TreeMap、TreeSet 以及 JDK1.8 的 HashMap 底层都用到了红黑树。
为什么要用红黑树
简单来说红黑树就是为了解决二叉查找树的缺陷因为二叉查找树在某些情况下会退化成一个线性结构。
布隆过滤器
布隆过滤器Bloom Filter是一种空间高效的概率型数据结构用于快速判断一个元素是否存在于一个集合中。
实际上是一个位数组通常用二进制位表示以及一系列哈希函数。
它的主要特点是快速查询、低存储消耗但可能会产生一定的误判率。
布隆过滤器通常用于以下场景
缓存加速在缓存中判断一个数据是否存在如果不存在则不需要从数据库或其他存储中加载数据从而加速数据的查询。数据库查询优化可以在数据库查询之前先通过布隆过滤器快速判断数据是否可能存在从而减少对数据库的查询负担。分布式系统在分布式系统中可以使用布隆过滤器来快速判断数据是否存在于分布式缓存或分布式数据库中。防止缓存穿透当请求的数据在缓存中不存在时可以使用布隆过滤器先进行判断如果判断结果为不存在则可以直接返回避免对数据库等存储系统的过多查询。
由于误判率的存在布隆过滤器不适合用于需要绝对精确判断的场景
具体实现步骤如下
初始化位数组创建一个位数组并将所有位初始化为 0。位数组的大小通常根据预期元素数量和期望的误判率来确定。添加元素将待添加的元素通过多个哈希函数计算出一系列哈希值然后将对应位置的位设置为 1。通常会选择多个不同的哈希函数以增加散列效果。查询元素将待查询的元素通过相同的哈希函数计算出一系列哈希值然后检查对应位置的位。如果所有位置的位都为 1则表示元素可能存在如果有任何一位为 0则表示元素一定不存在。
