这是一份全面&详细的数据结构、算法学习指南
前言
- 背景:算法与数据结构作为技术开发者最基本的技术修养,在日常开发出现的频率非常高
- 本文目的:花尽可能短的时间,快速学习常见的数据结构知识及算法
- 适用阅读人群:所有技术开发者
本文主要内容:
- 常见、常考的数据结构知识
- 结合每种数据结构给出常见 & 经典的算法题
- 每个知识点 & 考题都会从题目知识考点、多种思路分析到手写代码整个过程进行详细解析
目录
基础知识
1. 数据结构是什么?
- 储备知识:数据的定义
- 定义
- 具体类型
- 核心内容
1.1 储备知识:数据是什么
1.2 定义
相互之间存在一种或多种关系的数据元素的集合。
1.3 具体类型
数据结构的具备类型包括2种:逻辑结构、物理结构。
1.4 核心学习内容
主要包括:
- 排序
- 线性表:数组、链表、栈与队列
- 树:含特殊的树,如二叉树、红黑树等
- 串:如字符串
- 查找
- 图
在后面的章节中,我会详细介绍上述数据结构。
2. 算法是什么?
- 定义
- 特点
- 算法设计要求
- 常见算法
2.1 定义
解决特定问题的求解步骤(在计算机中表现为多个指令 = 多个步骤操作)。
2.2 特点
- 可无输入,但一定有输出
- 步骤有限
- 确定性:每个步骤有确定含义、不会出现二义
2.3 算法设计要求
算法的设计需考虑以下性能要求:
- 可行性:即该算法是否 切实 能解决问题
- 健壮性:即该算法是否能全面解决问题,即 考虑、容纳所有异常逻辑,如输入是0、为空、长度不符合等
- 时间效率:即该算法是否能 快速 解决问题,此处采用 指标:时间复杂度 来衡量
- 空间效率:即运行该算法需耗费多少内存空间,此处采用 指标:空间复杂度 来衡量
时间复杂度、空间复杂度介绍如下:
常用数据结构及其算法应用
每类数据结构都会有对应的算法应用场景,具体如下:
具体说明
在下面的章节中,我会:
- 详细讲解每个算法的应用场景 & 对应经典算法题:知识考点 - 多种思路分析 - 图解算法 - 手写代码
- 旨在:手把手带你剖析常见的数据结构 & 对应经典算法题
排序
1. 简介
具体请看文章:算法总结:这是一份全面&详细的排序算法学习指南
2. 算法应用
- 最简单的排序算法:冒泡排序
- 数据量大时最该选择的算法:简单选择排序
- 不可不了解的排序算法:直接插入排序
- 复杂度最高的排序算法:希尔排序
- 数据量大时最该选择的算法:简单选择排序
- 内存占用最少的排序算法:堆排序
- 稳定性最高的排序算法:归并排序
查找
1. 简介
2. 算法应用
对于不同的查找需求场景,会采用不同的查找类型,最终采用的查找方式(查找算法)也有所不同,具体如下
具体请看文章:Carson带你学数据结构:图文详解 - 动态查找、静态查找、散列查找
线性表
线性表主要包括:数组、链表、栈与队列
1. 数组
1.1 简介
- 存储线性表的数据元素的方式 = 一段地址连续的存储单元
- 具备:起始位置、数组长度(最大存储容量) & 线性表长度(当前长度),具体如下:
概念 | 说明 |
---|---|
数组长度 | 存放线性表的空间长度(固定不变) |
线性表长度 | 存放线性表数据元素的长度(动态变化) |
地址 | 存储单元的编号 |
数组下标 | 第 i 个元素 = 数组下标第 i-1 的位置 |
具体请看文章:Carson带你学数据结构:线性表-数组
1.2 算法应用
典型应用1:寻找出现特定次数的数字
典型应用2:寻找符合特定条件的数字
典型应用3:不同类型数组的查找
典型应用4:数组内元素的排列组合
2. 链表
2.1 简介
具体请看文章:Carson带你学数据结构:链表
2.2 算法应用
典型应用1:寻找链表特定节点
典型应用2:复制 & 删除链表
典型应用3:翻转、合并 & 打印链表
3. 栈与队列
3.1 简介
具体请看文章:Carson带你学数据结构:图文解析特殊的线性表 - 栈 & 队列
3.2 算法应用
典型应用1:互相转换
典型应用2:求最大、最小值
树
1. 简介
2. 存储结构
包括:双亲表示法、孩子表示法、孩子兄弟表示法,具体介绍如下图
3. 树的类型
具体请看文章:Carson带你学数据结构:手把手教你学习-树
主要应用是二叉树,所以下面主要介绍二叉树算法的应用
4. 算法应用
典型应用1:基础树遍历算法
典型应用2:遍历应用
典型应用3:二叉树结构判断
典型应用4:二叉树查找
典型应用5:二叉树类型变式
串
1. 简介
2. 存储结构介绍
包括:顺序存储结构 & 链式存储结构
具体请看文章:Carson带你学数据结构:这是一份全面 & 详细的”串“讲解指南
3. 算法应用
典型应用1:字符串转换
典型应用2:字符查找
典型应用3:字符串的排列组合
典型应用4:字符串翻转
典型应用5:字符串匹配判断
图
1.1 简介
具体请看文章:Carson带你学数据结构:手把手带你了解 ”图“ 所有知识!(含DFS、BFS)
1.2 算法应用
典型应用1:基础遍历
典型应用2:最小生成树
典型应用3:最短路径
至此,关于常用的数据结构及典型算法解析已经讲解完毕。
总结
本文全面解析了数据结构及其对应常见算法,核心内容都已经记录在Github上: https://github.com/Carson-Ho/AlgorithmLearning,感谢各位关注点赞。
相关文章
- 【技术种草】cdn+轻量服务器+hugo=让博客“云原生”一下
- CLB运维&运营最佳实践 ---访问日志大洞察
- vnc方式登陆服务器
- 轻松学排序算法:眼睛直观感受几种常用排序算法
- 十二个经典的大数据项目
- 为什么使用 CDN 内容分发网络?
- 大数据——大数据默认端口号列表
- Weld 1.1.5.Final,JSR-299 的框架
- JavaFX 2012:彻底开源
- 提升as3程序性能的十大要点
- 通过凸面几何学进行独立于边际的在线多类学习
- 利用行动影响的规律性和部分已知的模型进行离线强化学习
- ModelLight:基于模型的交通信号控制的元强化学习
- 浅谈Visual Source Safe项目分支
- 基于先验知识的递归卡尔曼滤波的代理人联合状态和输入估计
- 结合网络结构和非线性恢复来提高声誉评估的性能
- 最佳实践丨云开发CloudBase多环境管理实践
- TimeVAE:用于生成多变量时间序列的变异自动编码器
- 具有线性阈值激活的神经网络:结构和算法
- 内网渗透之横向移动 -- 从域外向域内进行密码喷洒攻击