数据结构(每周更新版)

亦凉 2023-09-26 19:41 148阅读 0赞

--------------------

#### 文章目录 ####

*  前言
 *  一、数据结构的分类
 *  二、线性结构
 *   *  1.数组
     *  2.复杂度分析
 *  三、栈和队列
 *  四、队列的复杂度问题
 *   *   *  上代码:

--------------------

## 前言 ##

数据结构,顾名思义,就是每种数据的存储结构  
我们要研究的是: 数据如何在计算机中进行组织和存储,使得我们可以**高效**的获取数据与修改数据

--------------------

## 一、数据结构的分类 ##

> 数据结构主要分成三类

线性结构:  
数组, 队列, 栈, 链表, 哈希表…  
树型结构:  
二叉树, 二分搜索树, AVL树, 红黑树, 堆, Trie, 线段树,  
图结构:  
邻接矩阵, 邻接表, 排序算法

## 二、线性结构 ##

### 1.数组 ###

数组特点:

1.  存储相同的类型
2.  内存空间是连续的, 创建时指定大小
3.  创建方式指定大小: int\[\] arr = new int\[10\]  
    字面量赋值: int\[\] arr = \{1,2,3,4,5\}
4.  索引位置0~length-1
5.  异常:NullPointException,ArrayIndexOutofBoundsException

数组的使用:  
通过使用索引对数组查询  
优点:快速查询;  
缺点:在中间插入数据时, 插入点以及之后的数据均会后移, **与在尾部插入数据效率差距大**

### 2.复杂度分析 ###

时间复杂度分析  
通常用O(1),O(n),O(lgn),O(nlgn),O(n\*n)  
O(n): 算法运行时间和输入输出之间的关系  
具体详解:[请点击此处][Link 1]  
==在获取算法的时间复杂度时候, 通常是忽略常数的 ==  
而且分析时间复杂度时候,一般都是n趋于无穷

> 例如  
> T=2\*n+2 时间复杂度就是 O(n)
> 
> > T=2000*n+100000 时间复杂度就是 O(n)  
> > T=1*n*n+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

1.  从栈中取元素叫 入栈
2.  从栈中加元素叫 出栈
3.  查看栈顶元素
4.  栈中实际元素存放元素个数
5.  查看栈是否为空
6.  遍历栈  
    示意图:  
    ![在这里插入图片描述][431e993a87ef4feea53c7cbe66e608ee.png]

> 队列  
> 队列特点:先进先出

1.  入队
2.  出队
3.  查看队首元素
4.  查看队列的元素总个数
5.  判断队列是否是空

![在这里插入图片描述][3261b0cba4fb4649bdac8bf34db2ebb2.png]

## 四、队列的复杂度问题 ##

> 由于在队列中, 一个元素出队列她的复杂度总是O(n),所以要该进成复杂度是O(1)的复杂度

导致复杂度O(n)的原因:  
由于队列里的队首元素移除后, 其他元素都要向前移动,所以就会造成时间的堆积, 时间复杂度就增加了  
解决: 要让队首元素移动之后,不要让其他元素移动

图解:  
![在这里插入图片描述][fc5c9020e6674c89925c101df4d80181.png]

1.  `在如图定性分析一下后, 又有新问题,那就是新元素添加的索引地址如何确定呢?`  
    可以想到，在之前添加元素的时候的下标是移动的，这里的tail实际是数组的首地址0的位置，但是  
    按照添加元素的个数来说，已经添加了7个元素，已经满了，这是添加第八个元素（索引7的位置），  
    所以这里巧妙地给tail取模运算tail=tail%array.length,这样一来新的tail是0,就是添加下一个元素的地方
2.  `再想想,又有问题抛出,就是如何判断数组满呢?`  
    (tail%array.length=front%array,length, 但突然又想到,当数组是空的时候, 也是满足这个表达式的,所以索性就浪费与空间来表示空间满了的情况, (tail+1)%array.length = front%array,length

#### 上代码: ####

`循环队列底层的循环数组代码`

> 构造方法  
> ![上代码:][2358133cfa4842e39f4a73c7ba6887ef.png]

> 获取容积  
> ![在这里插入图片描述][98955829aa2f404aa3cfe566a7c8874e.png]>判断队列是否为空  
> ![在这里插入图片描述][b140d96c25784dfba08bc0f4d1c836a3.png]

> 尾部插入元素  
> ![在这里插入图片描述][4cc0a05caae4482692d58a101287c71b.png]

> 队首出元素  
> ![在这里插入图片描述][d538df302f0445f48b71d3098336dc55.png]  
> 查看队首元素  
> ![在这里插入图片描述][e1f0b2471062469c9eccbbae9ab2be1c.png]

> 扩容操作  
> ![在这里插入图片描述][174ae131e40a47449819b3bc3a3ab335.png]

![在这里插入图片描述][edbca48967354ed287b5d7bb468d00b9.jpeg]

[Link 1]: http://t.csdn.cn/Tn7aQ
[431e993a87ef4feea53c7cbe66e608ee.png]: https://img-blog.csdnimg.cn/431e993a87ef4feea53c7cbe66e608ee.png
[3261b0cba4fb4649bdac8bf34db2ebb2.png]: https://img-blog.csdnimg.cn/3261b0cba4fb4649bdac8bf34db2ebb2.png
[fc5c9020e6674c89925c101df4d80181.png]: https://img-blog.csdnimg.cn/fc5c9020e6674c89925c101df4d80181.png
[2358133cfa4842e39f4a73c7ba6887ef.png]: https://img-blog.csdnimg.cn/2358133cfa4842e39f4a73c7ba6887ef.png
[98955829aa2f404aa3cfe566a7c8874e.png]: https://img-blog.csdnimg.cn/98955829aa2f404aa3cfe566a7c8874e.png
[b140d96c25784dfba08bc0f4d1c836a3.png]: https://img-blog.csdnimg.cn/b140d96c25784dfba08bc0f4d1c836a3.png
[4cc0a05caae4482692d58a101287c71b.png]: https://img-blog.csdnimg.cn/4cc0a05caae4482692d58a101287c71b.png
[d538df302f0445f48b71d3098336dc55.png]: https://img-blog.csdnimg.cn/d538df302f0445f48b71d3098336dc55.png
[e1f0b2471062469c9eccbbae9ab2be1c.png]: https://img-blog.csdnimg.cn/e1f0b2471062469c9eccbbae9ab2be1c.png
[174ae131e40a47449819b3bc3a3ab335.png]: https://img-blog.csdnimg.cn/174ae131e40a47449819b3bc3a3ab335.png
[edbca48967354ed287b5d7bb468d00b9.jpeg]: https://img-blog.csdnimg.cn/edbca48967354ed287b5d7bb468d00b9.jpeg