首页 / 算法 / 数据结构与算法——数组
数据结构与算法——数组
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了数据结构与算法——数组,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含5647字,纯文字阅读大概需要9分钟。
内容图文
![数据结构与算法——数组](/upload/InfoBanner/zyjiaocheng/792/6e0e156e7c97413980fb99110c6573c3.jpg)
我们都知道数组是一种常见的数据类型,同时它也是一种最基础的数据结构。
数组是一种线性表数据结构,它用一组连续的内存空间,来存储一组具有相同类型的数据。通过接下来的解释来理解这句话。
线性表,顾名思义就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。除了数组,链表、队列、栈也是线性表数据结构。而与线性表对立的概念就是非线性表,比如二叉树、堆、图等。之所以叫非线性,是因为在非线性表中,数据之前并不是简单的前后关系。
连续的内存空间和相同类型的数据,由于这两点的限制,使得数组有了“随机访问”的特性,这个特性给数组带来访问便捷的同时也带来了一些弊端,致使如在数组中删除、插入一个数据,为了保证数组内元素的连续性,就需要做大量的数据搬移工作。
根据下标实现随机访问数组元素
我们拿一个长度为6的int类型的数组a为例,由下图可知计算机为数组a分配了一段连续的内存空间100-123,其中内存空间的首地址为base_address = 100。
元素下标 |
int a[6] |
内存地址 |
0 |
a[0] |
100-103 |
1 |
a[1] |
104-107 |
2 |
a[2] |
108-111 |
3 |
a[3] |
112-115 |
4 |
a[4] |
116-119 |
5 |
a[5] |
120-123 |
我们知道计算机会给每个内存单元分配一个地址,计算机通过地址来访问内存中的数据。当计算机需要随机访问数组中的某个元素时,它会首先通过下面的寻址公式,计算出该元素存储的内存地址:
a[i]_address = base_address + i * data_type_size
有时候我们会有一种误解认为数组查找的时间复杂度为O(1),其实正确的说法应该是,数组支持随机访问,根据下标随机访问的时间复杂度为O(1)。
低效的“插入”和“删除”
- 插入操作
假设数组的长度为n,现在如果我们需要将一个数据插入到数组的第k个位置。为了把第k个位置腾出来给新来的数据,我们需要将第k~n这部分的元素都顺序地往后挪一位。通过之前所了解的复杂度分析方法可知,最理想的情况下,将数据插入至数组末尾,此时不需要对数组内元素进行转移工作,最好情况时间复杂度为O(1)。最糟糕的情况下,即将数据插入至数组首部,此时需要将数组内所有元素向后移动一个单位,最坏情况时间复杂度为O(1)。通过计算每种概率下的时间复杂度可以得到平均时间复杂度为O(n)。
如果数组中的数据是有序的,我们插入一个新的元素时,就必须按照上述方法实现元素的插入。但是若数组中存储的数据并没有任何规律,且数组只是被当作一个存储数据的集合。在这种情况下,如果要将某个元素插入到第k个位置,为了避免大规模的数据搬移,我们可以直接将第k个数据转移到数组的尾后,再将插入元素存放在第k个位置,这样可以使得数组的插入操作时间复杂度始终保证为O(1),但是我们要知道,这种方法改变了数组当中其他元素的位置。
- 删除操作
与插入数据类似,如果我们要删除数组当中的第k个位置的数据,为了保证内存的连续性,也需要搬移数据,不然数组当中就会出现空洞,内存也就不再连续了。和插入类型,如果删除数组末尾的数据,则最好情况时间复杂度为O(1),如果删除开头的数据,则最坏情况时间复杂度为O(n),平均时间复杂度为O(n)。
在实际中的某些特殊场景下,我们并不一定非得追求数组中数据的连续性。如果我们将多次删除操作集中在一起执行,删除的效率会提高很多。比如我们需要依次删除数组中的第1、2、3个元素时,我们可以先记录下已经删除的数据。每次的删除操作并不是真正的搬移数据,只是记录数据已经被删除的位置。当数组没有更多空间存储数据时,我们再触发并执行一次真正的删除操作,这样就大大减少了删除操作导致的数据搬移。
数组下标越界问题
在C++中,通过下标访问不存在的元素是一种未定义行为,这会产生很严重的后果。所谓缓冲区溢出(buffer overflow)指的就是这类错误,这也是导致PC及其他设备上应用程序出现安全问题的一个重要原因。并且这类错误是编译器无法识别的,所以就需要我们程序员在编写代码时,注意确保数组的下标合法化。
- 确保下标合法的一种有效手段就是尽可能使用范围for语句。
容器与数组的关系
针对数组类型,C++STL中提供了容器类vector等。在项目开发的过程中,何时使用数组,何时使用容器是我们需要在意的问题。
- 容器vector相对于数组的优势:可以将很多数组操作的细节封装起来,并且它支持动态扩容。
数组本身在定义的时候需要预先指定大小,因为需要分配连续的内存空间。如果我们申请了大小为10的数组,当第11个数据需要存储到数组当中时,我们就需要重新分配一块更大的空间,将原来的数据复制过去,然后再将新的数据插入。
如果使用vector,我们就完全不需要关心底层的扩容逻辑,vector已经帮我们实现好了。每次存储空间不够的时候,它会将空间自动扩容为1.5倍的大小(在我的编译器下),不同环境下可能扩容的机制会不同。但是需要注意一点,在进行扩容操作时候底层会涉及内存申请和数据搬移,是比较耗时的。所以,如果事先能确定需要存储的数据大小,最好在创建vector的时候事先指定数据大小。
比如我们事先知道要从文件中取出100个string类型对象并放入vector中。我们观察下面的代码,相比之下,事先指定数据大小可以省掉最初的很多次扩容操作。
vector<string> svec(100);
for (int i = 0; i != 100; ++i)
{
svec.push_back(xxx);
}
当然数组也不是没有应用的地方,有的时候采用数组反而会更加适合。
- 如果数据大小事先已知,并且对数据的操作非常简单,用不到容器所提供大部分方法,可以直接选用数组。
- 当表示多维数组的时候,采用数组往往会更加直观。比如:int[ ][ ] array; 而用容器的话需要这样定义:vector<vector<int>> array;
做以总结:对于业务开发,直接使用容器就足够了,省时省力。毕竟损耗一点性能,完全不会影响到系统整体的性能。但是如果是非常底层的开发,比如开发网络框架,性能的优化就需要做到极致,这个时候数组就会优于容器,成为首选。毕竟针对于具体的情况下,容器当中给出的方法的复杂度不一定是最佳情况。
小思考:数组为什么要从0开始编号,而不是从1开始呢?
从数组存储的内存模型上来看,“下标”最确切的定义应该是“偏移(offset)”。前面也说过,如果用a表示数组的首地址,那么a[0]就表示偏移为0的位置,也就是首地址,a[i]就表示偏移i个type_size的位置,所以计算a[i]的内存地址只需要这个公式:
a[i]_address = base_address + i * data_type_size
但是,如果数组从1开始计数,那么我们计算数组元素a[i]的内存地址公式就会变为:
a[i]_address = base_address + (i - 1) * data_type_size
对比两个公式,我们发现,从1开始编号的话,每次随机访问数组元素都会多了一次减法运算,对于CPU来说,就是多了一次减法的指令。而数组作为非常基础的数据结构,通过下标随机访问数组元素又是其非常基础的编程操作,效率的优化就应该尽可能做到极致。所以为了减少一次减法操作,数组选择了从0开始编号,而不是从1开始。
内容总结
以上是互联网集市为您收集整理的数据结构与算法——数组全部内容,希望文章能够帮你解决数据结构与算法——数组所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。