前言
学习数据结构与算法能够让你了解该用什么数据结构储存数据,这涉及到编程中关键的性能和效率问题。
数据结构
数据结构是计算机存储、组织数据的方式,指相互之间存在一种或多种特定关系的数据元素的集合。
数据结构的基本功能,可归纳为增删改查及遍历。
数据结构可分为逻辑结构和物理结构:
逻辑结构
数据对象中数据元素的关系
- 集合结构:数据元素同属于一个集合,没有其他关系。
- 线性结构:数据元素之间事一对一的关系。
- 树状结构:数据元素之间是一对多关系。
- 图形结构:数据元素之间是多对多关系。
物理结构
数据的逻辑结构在计算机中的储存方式。
顺序结构:数据元素存放在地址连续的储存单元里,其数据间的逻辑关系和物理关系。
链式储存结构:数据元素存放在任意的储存单元里,同是需要指针储存下一个元素的地址。
算法
算法简单来说就是解决问题的步骤。
五要素
- 有穷性。
- 确定性。
- 可行性。
- 有输入。
- 有输出。
设计原则
- 正确性。
- 可读性。
- 健壮性。
- 高效率与低存储量需求。
复杂度
一般只关注时间复杂度。
注:当然,空间复杂度本身也有其存在的意义,尤其是在对空间效率非常在乎的应用场合,或者是当问题的输入规模极为庞大时。
时间复杂度
表示算法复杂度的度量记号大 O 级别,常见的时间复杂度:
- 常数阶O(1)
- 线性阶O(n)
- 平方阶O(n²)
- 对数阶O(log n)
- 线性对数阶O(n log n)
时间复杂度分析方法:
- 只关注循环执行次数最多的一段代码。
- 总复杂度等于量级最大的那段代码的复杂度。
- 嵌套代码的复杂度等于嵌套你内外代码复杂的的乘积。
空间复杂度分析
表示算法的储存空间与数据规模之间的增长关系。
int[] a = new int[n]
这段代码的空间复杂的就是O(n)。
数组
线性、顺序结构,储存同一种数据类型(Object数组除外)。
随机访问
因为是连续的内存空间,很容易根据下标定位到内存地址。
低效的插入和删除
插入和删除数组末尾,时间复杂度为O(1),其他位置插入元素设计到元素的位置的移动,平均复杂度为O(n),效率低下。
链表
线性、链式结构
链表类型
单链表
链表有一个头指针指向链表的第一个节点,最后一个节点指向空。
循环链表
循环链表的尾结点指针是指向链表的头结点。
双向链表
双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。所以,如果存储同样多的数据,双向链表要比单链表占用更多的内存空间。虽然两个指针比较浪费存储空间,但可以支持双向遍历。
查找慢、插入删除很快
一般我们都使用双向链表,因为它能够很快定位到前驱和后继节点。
因为链表是链式储存结构,定位元素只能通过遍历,复杂度为O(n);
针对链表的插入和删除操作,我们只需要考虑相邻结点的指针改变,所以对应的时间复杂度是 O(1)。
栈
只涉及在一端插入和删除数据,并且满足后进先出、先进后出的特性
栈的应用
- 符号匹配
- 中缀表达式转换为后缀表达式
- 计算后缀表达式
- 实现函数的嵌套调用
- HTML 和 XML 文件中的标签匹配
- 网浏览器中已访问页面的历史记录
队列
队列是一种线性表,它支持 先进先出(FIFO)
尾部添加、头部删除,跟我们生活中的排队类似
队列类型
单队列
单队列就是常见的队列, 每次添加元素时,都是添加到队尾:
单队列会出现“假溢出”现象,每次从队首删除元素,元素都要上前移动一个位置,能放的空位就相对减少了。
循环队列
我们可以将队列看成一个首位相连的环。当一个元素从队列删除后,新空余出来的空间可以作为队列的尾部。
队列应用
消息队列中间件
树
树状结构,像是一个倒挂的树。
基本术语
节点:根节点、叶节点、叶子节点、父节点、子节点、兄弟节点。
高度: