前言
数据结构,顾名思义,就是每种数据的存储结构
我们要研究的是: 数据如何在计算机中进行组织和存储,使得我们可以高效的获取数据与修改数据
一、数据结构的分类
数据结构主要分成三类线性结构:
数组, 队列, 栈, 链表, 哈希表...
树型结构:
二叉树, 二分搜索树, AVL树, 红黑树, 堆, Trie, 线段树,
图结构:
邻接矩阵, 邻接表, 排序算法
二、线性结构
1.数组
数组特点:
- 存储相同的类型
- 内存空间是连续的, 创建时指定大小
- 创建方式指定大小: int[] arr = new int[10]
字面量赋值: int[] arr = {1,2,3,4,5} - 索引位置0~length-1
- 异常:NullPointException,ArrayIndexOutofBoundsException
数组的使用:
通过使用索引对数组查询
优点:快速查询;
缺点:在中间插入数据时, 插入点以及之后的数据均会后移, 与在尾部插入数据效率差距大
2.复杂度分析
时间复杂度分析
通常用O(1),O(n),O(lgn),O(nlgn),O(n*n)
O(n): 算法运行时间和输入输出之间的关系
具体详解:请点击此处
==在获取算法的时间复杂度时候, 通常是忽略常数的 ==
而且分析时间复杂度时候,一般都是n趋于无穷
例如
T=2*n+2 时间复杂度就是 O(n)T=2000*n+100000 时间复杂度就是 O(n)
T=1 nn+0 时间复杂度就是 O(n*n)
分析数组添加元素的时间复杂度:
在尾部添加元素: O(1)
在头部添加:O(n)
在任意位置添加元素: 最好情况是不移动,最坏情况O(n),平均下来就是O(n/2)--->O(n)
在更改数组元素时, 已知索引是O(1),不知道索引就O(n)
在查询数组元素时, 已知索引是O(1),不知道索引就O(n)
综合来说数组添加元素的时间复杂度是O(n)
数组删除元素的时间复杂度类似添加元素的时间复杂度,时间复杂度也是O(n)
==注意数组扩容时候==
扩容时候,要求原数组的所有元素移动到新数组里,并且新元素添加新数组里,
可以把添加最后一个元素时候的所有操作(移动老元素),均摊到之前的添加元素步骤上面,平均下来大约是O(2)_,叫做均摊时间复杂度
三、栈和队列
栈Stack
操作时,只能从栈顶进行操作,先进入栈的元素最后出,最后进来的元素先出来,即后进先出(First Last Out)FILO
- 从栈中取元素叫 入栈
- 从栈中加元素叫 出栈
- 查看栈顶元素
- 栈中实际元素存放元素个数
- 查看栈是否为空
- 遍历栈
示意图:
队列
队列特点:先进先出
- 入队
- 出队
- 查看队首元素
- 查看队列的元素总个数
- 判断队列是否是空
四、队列的复杂度问题
由于在队列中, 一个元素出队列她的复杂度总是O(n),所以要该进成复杂度是O(1)的复杂度
导致复杂度O(n)的原因:
由于队列里的队首元素移除后, 其他元素都要向前移动,所以就会造成时间的堆积, 时间复杂度就增加了
==解决: 要让队首元素移动之后,不要让其他元素移动==
图解:
在如图定性分析一下后, 又有新问题,那就是新元素添加的索引地址如何确定呢?
可以想到，在之前添加元素的时候的下标是移动的，这里的tail实际是数组的首地址0的位置，但是
按照添加元素的个数来说，已经添加了7个元素，已经满了，这是添加第八个元素（索引7的位置），
所以这里巧妙地给tail取模运算==tail=tail%array.length==,这样一来新的tail是0,就是添加下一个元素的地方
再想想,又有问题抛出,就是如何判断数组满呢?
==(tail%array.length=front%array,length==, 但突然又想到,当数组是空的时候, 也是满足这个表达式的,所以索性就浪费与空间来表示空间满了的情况, ==(tail+1)%array.length = front%array,length==
上代码:
循环队列底层的循环数组代码
构造方法
获取容积
>判断队列是否为空
尾部插入元素
队首出元素
查看队首元素扩容操作
