在学习算法的时候，看书讲到了数据结构，第一次学习，感觉基础还是很重要的，把内容整理如下，方便回顾。
数据结构
数组：
在计算机内存中，数据是相连的，如果空间不够，需要计算机重新分配可以容纳数据的内存空间，或者预留大块内存空间以供数据使用
缺点：
1.预留空间用不上，导致浪费内存。
2.预留内存空间仍然会不足。
链表：
里面每个元素都存储了下一个元素的地址，使得一系列内存地址可以串联在一起。
缺点：读取元素不如数组高效，数组只需要查index，就能推算出相应位置的元素，链表必须从头开始读区，1包含2的地址，2包含3的地址....
运行时间比较：
在中间插入，选链表，因为数组要插入元素，会导致后面元素一系列移动；链表只需要修改内存地址。
对于删除元素，总能成功。而插入会由于内存不足，可能导致操作失败。
数组支持：随机访问和顺序访问，而链表只能顺序访问。对于访问是读取行为，所以数组会更快一些。
链表擅长：插入和删除，数组擅长随机访问。
链表.png
数组链表操作运行时间.png
大O表示法来表示算法的运行时间，而算法的速度并非指时间，而是指操作的增速。也指算法执行的操作数。
关于更细致的理解，可以看这篇介绍博文大O表示法介绍
常见的操作数.png
时间比较.png
散列表(hash table)
散列函数：输入一个内容给你一个数字
- 给数字的结果必须一致
- 将不同的输入映射到不同的数字
在python中用dict来实现
应用
- 查找-电话、ip
- 防止重复-投票
- 缓存
冲突
散列函数基本不可能将所有不同键映射到数组不同的位置，也可能是不同键映射到同一个位置，此时产生冲突(collision)，解决办法是在这个位置存储一个链表。一个好的散列函数显得尤为重要。
性能
散列表一般情况取一个元素是常量时间O(1),最差的情况是线性时间O(n)。
(图数组、链表、散列表)
避免冲突
- 装填因子：元素数/位置数
- 装填因子>0.7,就可以调整散列表长度，通常将长度增加一倍。
- 有良好的散列函数：能让值比较均匀分布在数组中。
数据存储方式--补充
- 顺序存储：把数据存储在一块联系的存储介质中(硬盘、内存)
(数组)
由于数组是顺序存储的，存储数组的内存也是连续的，需要读取数组中的数据时，提供数组索引，就可以从内存中读数据。所以寻址读取容易，而插入和删除困难。
- 非顺序存储：
(链表)
链表存储数据内存有两块区域，一块用来存储数据，另一块来记录下一个数据保存的位置(下个数据的指针)。单向链表最后一个节点指向Null
链表在插入和删除容易，读取数据麻烦，要从头开始找。
- 栈
先进后出的数据结构，数据和链表都可以组成栈。先放入的被压在最下面，后进入的从最上面先出去。
- 队列
先进先出的数据结构，数组和链表都可以生成队列。先进入的可以先出列。
将栈和队列想成管子，栈时一头封死的，只能从一个口子，同一个口子出；队列一个口子负责进数据，一个口子负责出数据，先进的数据最后先从出口拿出。
网友评论